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 && 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().block_begin(), 76 BF.getLayout().block_end()); 77 llvm::sort(NewOrder, [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) { 78 return BB1->getLayoutIndex() < BB2->getLayoutIndex(); 79 }); 80 BF.getLayout().update(NewOrder); 81 } 82 83 return IsChanged; 84 } 85 86 void LoopInversionPass::runOnFunctions(BinaryContext &BC) { 87 std::atomic<uint64_t> ModifiedFuncCount{0}; 88 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE || 89 opts::LoopReorder == false) 90 return; 91 92 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) { 93 if (runOnFunction(BF)) 94 ++ModifiedFuncCount; 95 }; 96 97 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) { 98 return !shouldOptimize(BF); 99 }; 100 101 ParallelUtilities::runOnEachFunction( 102 BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc, 103 "LoopInversionPass"); 104 105 outs() << "BOLT-INFO: " << ModifiedFuncCount 106 << " Functions were reordered by LoopInversionPass\n"; 107 } 108 109 } // end namespace bolt 110 } // end namespace llvm 111