1 //===- bolt/Passes/AllocCombiner.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 AllocCombinerPass class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "bolt/Passes/AllocCombiner.h"
14
15 #define DEBUG_TYPE "alloccombiner"
16
17 using namespace llvm;
18
19 namespace opts {
20
21 extern cl::opt<bolt::FrameOptimizationType> FrameOptimization;
22
23 } // end namespace opts
24
25 namespace llvm {
26 namespace bolt {
27
getStackAdjustmentSize(const BinaryContext & BC,const MCInst & Inst,int64_t & Adjustment)28 static bool getStackAdjustmentSize(const BinaryContext &BC, const MCInst &Inst,
29 int64_t &Adjustment) {
30 return BC.MIB->evaluateStackOffsetExpr(
31 Inst, Adjustment, std::make_pair(BC.MIB->getStackPointer(), 0LL),
32 std::make_pair(0, 0LL));
33 }
34
isIndifferentToSP(const MCInst & Inst,const BinaryContext & BC)35 static bool isIndifferentToSP(const MCInst &Inst, const BinaryContext &BC) {
36 if (BC.MIB->isCFI(Inst))
37 return true;
38
39 const MCInstrDesc &II = BC.MII->get(Inst.getOpcode());
40 if (BC.MIB->isTerminator(Inst) ||
41 II.hasImplicitDefOfPhysReg(BC.MIB->getStackPointer(), BC.MRI.get()) ||
42 II.hasImplicitUseOfPhysReg(BC.MIB->getStackPointer()))
43 return false;
44
45 for (const MCOperand &Operand : MCPlus::primeOperands(Inst))
46 if (Operand.isReg() && Operand.getReg() == BC.MIB->getStackPointer())
47 return false;
48 return true;
49 }
50
shouldProcess(const BinaryFunction & Function)51 static bool shouldProcess(const BinaryFunction &Function) {
52 return Function.isSimple() && Function.hasCFG() && !Function.isIgnored();
53 }
54
runForAllWeCare(std::map<uint64_t,BinaryFunction> & BFs,std::function<void (BinaryFunction &)> Task)55 static void runForAllWeCare(std::map<uint64_t, BinaryFunction> &BFs,
56 std::function<void(BinaryFunction &)> Task) {
57 for (auto &It : BFs) {
58 BinaryFunction &Function = It.second;
59 if (shouldProcess(Function))
60 Task(Function);
61 }
62 }
63
combineAdjustments(BinaryFunction & BF)64 void AllocCombinerPass::combineAdjustments(BinaryFunction &BF) {
65 BinaryContext &BC = BF.getBinaryContext();
66 for (BinaryBasicBlock &BB : BF) {
67 MCInst *Prev = nullptr;
68 for (MCInst &Inst : llvm::reverse(BB)) {
69 if (isIndifferentToSP(Inst, BC))
70 continue; // Skip updating Prev
71
72 int64_t Adjustment = 0LL;
73 if (!Prev || !BC.MIB->isStackAdjustment(Inst) ||
74 !BC.MIB->isStackAdjustment(*Prev) ||
75 !getStackAdjustmentSize(BC, *Prev, Adjustment)) {
76 Prev = &Inst;
77 continue;
78 }
79
80 LLVM_DEBUG({
81 dbgs() << "At \"" << BF.getPrintName() << "\", combining: \n";
82 Inst.dump();
83 Prev->dump();
84 dbgs() << "Adjustment: " << Adjustment << "\n";
85 });
86
87 if (BC.MIB->isSUB(Inst))
88 Adjustment = -Adjustment;
89
90 BC.MIB->addToImm(Inst, Adjustment, BC.Ctx.get());
91
92 LLVM_DEBUG({
93 dbgs() << "After adjustment:\n";
94 Inst.dump();
95 });
96
97 BB.eraseInstruction(BB.findInstruction(Prev));
98 ++NumCombined;
99 DynamicCountCombined += BB.getKnownExecutionCount();
100 FuncsChanged.insert(&BF);
101 Prev = &Inst;
102 }
103 }
104 }
105
runOnFunctions(BinaryContext & BC)106 Error AllocCombinerPass::runOnFunctions(BinaryContext &BC) {
107 if (opts::FrameOptimization == FOP_NONE)
108 return Error::success();
109
110 runForAllWeCare(BC.getBinaryFunctions(), [&](BinaryFunction &Function) {
111 combineAdjustments(Function);
112 });
113
114 BC.outs() << "BOLT-INFO: Allocation combiner: " << NumCombined
115 << " empty spaces coalesced (dyn count: " << DynamicCountCombined
116 << ").\n";
117 return Error::success();
118 }
119
120 } // end namespace bolt
121 } // end namespace llvm
122