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 a second BB successor"); 58 const uint64_t LoopCount = SuccBB->getBranchInfo(*BB).Count; 59 const uint64_t ExitCount = SuccBB->getBranchInfo(*SecondSucc).Count; 60 61 if (LoopCount < ExitCount) { 62 if (BBIndex > SuccBBIndex) 63 continue; 64 } else if (BBIndex < SuccBBIndex) { 65 continue; 66 } 67 68 IsChanged = true; 69 BB->setLayoutIndex(SuccBBIndex); 70 SuccBB->setLayoutIndex(BBIndex); 71 } 72 } 73 74 if (IsChanged) { 75 BinaryFunction::BasicBlockOrderType NewOrder = BF.getLayout(); 76 llvm::sort(NewOrder, [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) { 77 return BB1->getLayoutIndex() < BB2->getLayoutIndex(); 78 }); 79 BF.updateBasicBlockLayout(NewOrder); 80 } 81 82 return IsChanged; 83 } 84 85 void LoopInversionPass::runOnFunctions(BinaryContext &BC) { 86 std::atomic<uint64_t> ModifiedFuncCount{0}; 87 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE || 88 opts::LoopReorder == false) 89 return; 90 91 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) { 92 if (runOnFunction(BF)) 93 ++ModifiedFuncCount; 94 }; 95 96 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) { 97 return !shouldOptimize(BF); 98 }; 99 100 ParallelUtilities::runOnEachFunction( 101 BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc, 102 "LoopInversionPass"); 103 104 outs() << "BOLT-INFO: " << ModifiedFuncCount 105 << " Functions were reordered by LoopInversionPass\n"; 106 } 107 108 } // end namespace bolt 109 } // end namespace llvm 110