1 //===--------- 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 //===----------------------------------------------------------------------===// 10 11 #include "bolt/Passes/LoopInversionPass.h" 12 #include "bolt/Core/ParallelUtilities.h" 13 14 using namespace llvm; 15 16 namespace opts { 17 extern cl::OptionCategory BoltCategory; 18 19 extern cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks; 20 21 static cl::opt<bool> LoopReorder( 22 "loop-inversion-opt", 23 cl::desc("reorder unconditional jump instructions in loops optimization"), 24 cl::init(true), cl::cat(BoltCategory), cl::ReallyHidden); 25 } // namespace opts 26 27 namespace llvm { 28 namespace bolt { 29 30 bool LoopInversionPass::runOnFunction(BinaryFunction &BF) { 31 bool IsChanged = false; 32 if (BF.layout_size() < 3 || !BF.hasValidProfile()) 33 return false; 34 35 BF.updateLayoutIndices(); 36 for (BinaryBasicBlock *BB : BF.layout()) { 37 if (BB->succ_size() != 1 || BB->pred_size() != 1) 38 continue; 39 40 BinaryBasicBlock *SuccBB = *BB->succ_begin(); 41 BinaryBasicBlock *PredBB = *BB->pred_begin(); 42 const unsigned BBIndex = BB->getLayoutIndex(); 43 const unsigned SuccBBIndex = SuccBB->getLayoutIndex(); 44 if (SuccBB == PredBB && BB != SuccBB && BBIndex != 0 && SuccBBIndex != 0 && 45 SuccBB->succ_size() == 2 && BB->isCold() == SuccBB->isCold()) { 46 // Get the second successor (after loop BB) 47 BinaryBasicBlock *SecondSucc = nullptr; 48 for (BinaryBasicBlock *Succ : SuccBB->successors()) { 49 if (Succ != &*BB) { 50 SecondSucc = Succ; 51 break; 52 } 53 } 54 55 assert(SecondSucc != nullptr && "Unable to find second BB successor"); 56 const uint64_t BBCount = SuccBB->getBranchInfo(*BB).Count; 57 const uint64_t OtherCount = SuccBB->getBranchInfo(*SecondSucc).Count; 58 if ((BBCount < OtherCount) && (BBIndex > SuccBBIndex)) 59 continue; 60 61 IsChanged = true; 62 BB->setLayoutIndex(SuccBBIndex); 63 SuccBB->setLayoutIndex(BBIndex); 64 } 65 } 66 67 if (IsChanged) { 68 BinaryFunction::BasicBlockOrderType NewOrder = BF.getLayout(); 69 std::sort(NewOrder.begin(), NewOrder.end(), 70 [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) { 71 return BB1->getLayoutIndex() < BB2->getLayoutIndex(); 72 }); 73 BF.updateBasicBlockLayout(NewOrder); 74 } 75 76 return IsChanged; 77 } 78 79 void LoopInversionPass::runOnFunctions(BinaryContext &BC) { 80 std::atomic<uint64_t> ModifiedFuncCount{0}; 81 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE || 82 opts::LoopReorder == false) 83 return; 84 85 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) { 86 if (runOnFunction(BF)) 87 ++ModifiedFuncCount; 88 }; 89 90 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) { 91 return !shouldOptimize(BF); 92 }; 93 94 ParallelUtilities::runOnEachFunction( 95 BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc, 96 "LoopInversionPass"); 97 98 outs() << "BOLT-INFO: " << ModifiedFuncCount 99 << " Functions were reordered by LoopInversionPass\n"; 100 } 101 102 } // end namespace bolt 103 } // end namespace llvm 104