1 //===- bolt/Passes/LoopInversionPass.cpp ----------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the LoopInversionPass class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "bolt/Passes/LoopInversionPass.h" 14 #include "bolt/Core/ParallelUtilities.h" 15 16 using namespace llvm; 17 18 namespace opts { 19 extern cl::OptionCategory BoltCategory; 20 21 extern cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks; 22 23 static cl::opt<bool> LoopReorder( 24 "loop-inversion-opt", 25 cl::desc("reorder unconditional jump instructions in loops optimization"), 26 cl::init(true), cl::cat(BoltCategory), cl::ReallyHidden); 27 } // namespace opts 28 29 namespace llvm { 30 namespace bolt { 31 32 bool LoopInversionPass::runOnFunction(BinaryFunction &BF) { 33 bool IsChanged = false; 34 if (BF.getLayout().block_size() < 3 || !BF.hasValidProfile()) 35 return false; 36 37 BF.getLayout().updateLayoutIndices(); 38 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) { 39 if (BB->succ_size() != 1 || BB->pred_size() != 1) 40 continue; 41 42 BinaryBasicBlock *SuccBB = *BB->succ_begin(); 43 BinaryBasicBlock *PredBB = *BB->pred_begin(); 44 const unsigned BBIndex = BB->getLayoutIndex(); 45 const unsigned SuccBBIndex = SuccBB->getLayoutIndex(); 46 if (SuccBB == PredBB && BB != SuccBB && BBIndex != 0 && SuccBBIndex != 0 && 47 SuccBB->succ_size() == 2 && 48 BB->getFragmentNum() == SuccBB->getFragmentNum()) { 49 // Get the second successor (after loop BB) 50 BinaryBasicBlock *SecondSucc = nullptr; 51 for (BinaryBasicBlock *Succ : SuccBB->successors()) { 52 if (Succ != &*BB) { 53 SecondSucc = Succ; 54 break; 55 } 56 } 57 58 assert(SecondSucc != nullptr && "Unable to find a second BB successor"); 59 const uint64_t LoopCount = SuccBB->getBranchInfo(*BB).Count; 60 const uint64_t ExitCount = SuccBB->getBranchInfo(*SecondSucc).Count; 61 62 if (LoopCount < ExitCount) { 63 if (BBIndex > SuccBBIndex) 64 continue; 65 } else if (BBIndex < SuccBBIndex) { 66 continue; 67 } 68 69 IsChanged = true; 70 BB->setLayoutIndex(SuccBBIndex); 71 SuccBB->setLayoutIndex(BBIndex); 72 } 73 } 74 75 if (IsChanged) { 76 BinaryFunction::BasicBlockOrderType NewOrder(BF.getLayout().block_begin(), 77 BF.getLayout().block_end()); 78 llvm::sort(NewOrder, [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) { 79 return BB1->getLayoutIndex() < BB2->getLayoutIndex(); 80 }); 81 BF.getLayout().update(NewOrder); 82 } 83 84 return IsChanged; 85 } 86 87 void LoopInversionPass::runOnFunctions(BinaryContext &BC) { 88 std::atomic<uint64_t> ModifiedFuncCount{0}; 89 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE || 90 opts::LoopReorder == false) 91 return; 92 93 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) { 94 if (runOnFunction(BF)) 95 ++ModifiedFuncCount; 96 }; 97 98 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) { 99 return !shouldOptimize(BF); 100 }; 101 102 ParallelUtilities::runOnEachFunction( 103 BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc, 104 "LoopInversionPass"); 105 106 outs() << "BOLT-INFO: " << ModifiedFuncCount 107 << " Functions were reordered by LoopInversionPass\n"; 108 } 109 110 } // end namespace bolt 111 } // end namespace llvm 112