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.layout_size() < 3 || !BF.hasValidProfile()) 35 return false; 36 37 BF.updateLayoutIndices(); 38 for (BinaryBasicBlock *BB : BF.layout()) { 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 && BB->isCold() == SuccBB->isCold()) { 48 // Get the second successor (after loop BB) 49 BinaryBasicBlock *SecondSucc = nullptr; 50 for (BinaryBasicBlock *Succ : SuccBB->successors()) { 51 if (Succ != &*BB) { 52 SecondSucc = Succ; 53 break; 54 } 55 } 56 57 assert(SecondSucc != nullptr && "Unable to find second BB successor"); 58 const uint64_t BBCount = SuccBB->getBranchInfo(*BB).Count; 59 const uint64_t OtherCount = SuccBB->getBranchInfo(*SecondSucc).Count; 60 if ((BBCount < OtherCount) && (BBIndex > SuccBBIndex)) 61 continue; 62 63 IsChanged = true; 64 BB->setLayoutIndex(SuccBBIndex); 65 SuccBB->setLayoutIndex(BBIndex); 66 } 67 } 68 69 if (IsChanged) { 70 BinaryFunction::BasicBlockOrderType NewOrder = BF.getLayout(); 71 std::sort(NewOrder.begin(), NewOrder.end(), 72 [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) { 73 return BB1->getLayoutIndex() < BB2->getLayoutIndex(); 74 }); 75 BF.updateBasicBlockLayout(NewOrder); 76 } 77 78 return IsChanged; 79 } 80 81 void LoopInversionPass::runOnFunctions(BinaryContext &BC) { 82 std::atomic<uint64_t> ModifiedFuncCount{0}; 83 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE || 84 opts::LoopReorder == false) 85 return; 86 87 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) { 88 if (runOnFunction(BF)) 89 ++ModifiedFuncCount; 90 }; 91 92 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) { 93 return !shouldOptimize(BF); 94 }; 95 96 ParallelUtilities::runOnEachFunction( 97 BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc, 98 "LoopInversionPass"); 99 100 outs() << "BOLT-INFO: " << ModifiedFuncCount 101 << " Functions were reordered by LoopInversionPass\n"; 102 } 103 104 } // end namespace bolt 105 } // end namespace llvm 106