llvm-project
112 строк · 3.6 Кб
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
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",25cl::desc("reorder unconditional jump instructions in loops optimization"),26cl::init(true), cl::cat(BoltCategory), cl::ReallyHidden);27} // namespace opts28
29namespace llvm {30namespace bolt {31
32bool LoopInversionPass::runOnFunction(BinaryFunction &BF) {33bool IsChanged = false;34if (BF.getLayout().block_size() < 3 || !BF.hasValidProfile())35return false;36
37BF.getLayout().updateLayoutIndices();38for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {39if (BB->succ_size() != 1 || BB->pred_size() != 1)40continue;41
42BinaryBasicBlock *SuccBB = *BB->succ_begin();43BinaryBasicBlock *PredBB = *BB->pred_begin();44const unsigned BBIndex = BB->getLayoutIndex();45const unsigned SuccBBIndex = SuccBB->getLayoutIndex();46if (SuccBB == PredBB && BB != SuccBB && BBIndex != 0 && SuccBBIndex != 0 &&47SuccBB->succ_size() == 2 &&48BB->getFragmentNum() == SuccBB->getFragmentNum()) {49// Get the second successor (after loop BB)50BinaryBasicBlock *SecondSucc = nullptr;51for (BinaryBasicBlock *Succ : SuccBB->successors()) {52if (Succ != &*BB) {53SecondSucc = Succ;54break;55}56}57
58assert(SecondSucc != nullptr && "Unable to find a second BB successor");59const uint64_t LoopCount = SuccBB->getBranchInfo(*BB).Count;60const uint64_t ExitCount = SuccBB->getBranchInfo(*SecondSucc).Count;61
62if (LoopCount < ExitCount) {63if (BBIndex > SuccBBIndex)64continue;65} else if (BBIndex < SuccBBIndex) {66continue;67}68
69IsChanged = true;70BB->setLayoutIndex(SuccBBIndex);71SuccBB->setLayoutIndex(BBIndex);72}73}74
75if (IsChanged) {76BinaryFunction::BasicBlockOrderType NewOrder(BF.getLayout().block_begin(),77BF.getLayout().block_end());78llvm::sort(NewOrder, [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) {79return BB1->getLayoutIndex() < BB2->getLayoutIndex();80});81BF.getLayout().update(NewOrder);82}83
84return IsChanged;85}
86
87Error LoopInversionPass::runOnFunctions(BinaryContext &BC) {88std::atomic<uint64_t> ModifiedFuncCount{0};89if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE ||90opts::LoopReorder == false)91return Error::success();92
93ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {94if (runOnFunction(BF))95++ModifiedFuncCount;96};97
98ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {99return !shouldOptimize(BF);100};101
102ParallelUtilities::runOnEachFunction(103BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc,104"LoopInversionPass");105
106BC.outs() << "BOLT-INFO: " << ModifiedFuncCount107<< " Functions were reordered by LoopInversionPass\n";108return Error::success();109}
110
111} // end namespace bolt112} // end namespace llvm113