113 lines · cpp
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-exception6//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 16using namespace llvm;17 18namespace opts {19extern cl::OptionCategory BoltCategory;20 21extern cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks;22 23static 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 opts28 29namespace llvm {30namespace bolt {31 32bool 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 87Error LoopInversionPass::runOnFunctions(BinaryContext &BC) {88 std::atomic<uint64_t> ModifiedFuncCount{0};89 if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE ||90 opts::LoopReorder == false)91 return Error::success();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 BC.outs() << "BOLT-INFO: " << ModifiedFuncCount107 << " Functions were reordered by LoopInversionPass\n";108 return Error::success();109}110 111} // end namespace bolt112} // end namespace llvm113