1 //===- bolt/Passes/StokeInfo.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 StokeInfo class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "bolt/Passes/StokeInfo.h"
14 #include "bolt/Core/BinaryFunctionCallGraph.h"
15 #include "bolt/Passes/DataflowInfoManager.h"
16 #include "llvm/Support/CommandLine.h"
17
18 #define DEBUG_TYPE "stoke"
19
20 using namespace llvm;
21 using namespace bolt;
22
23 namespace opts {
24 cl::OptionCategory StokeOptCategory("STOKE pass options");
25
26 static cl::opt<std::string>
27 StokeOutputDataFilename("stoke-out",
28 cl::desc("output data (.csv) for Stoke's use"),
29 cl::Optional,
30 cl::cat(StokeOptCategory));
31 }
32
33 namespace llvm {
34 namespace bolt {
35
getRegNameFromBitVec(const BinaryContext & BC,const BitVector & RegV,std::set<std::string> * NameVec=nullptr)36 void getRegNameFromBitVec(const BinaryContext &BC, const BitVector &RegV,
37 std::set<std::string> *NameVec = nullptr) {
38 for (int RegIdx : RegV.set_bits()) {
39 LLVM_DEBUG(dbgs() << BC.MRI->getName(RegIdx) << " ");
40 if (NameVec)
41 NameVec->insert(std::string(BC.MRI->getName(RegIdx)));
42 }
43 LLVM_DEBUG(dbgs() << "\n");
44 }
45
checkInstr(const BinaryFunction & BF,StokeFuncInfo & FuncInfo)46 void StokeInfo::checkInstr(const BinaryFunction &BF, StokeFuncInfo &FuncInfo) {
47 MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();
48 BitVector RegV(NumRegs, false);
49 for (const BinaryBasicBlock *BB : BF.getLayout().blocks()) {
50 if (BB->empty())
51 continue;
52
53 // Skip function with exception handling.
54 if (BB->throw_size() || BB->lp_size()) {
55 FuncInfo.Omitted = true;
56 return;
57 }
58
59 for (const MCInst &It : *BB) {
60 if (MIB->isPseudo(It))
61 continue;
62 // skip function with exception handling yet
63 if (MIB->isInvoke(It)) {
64 FuncInfo.Omitted = true;
65 return;
66 }
67 // check if this function contains call instruction
68 if (MIB->isCall(It)) {
69 FuncInfo.HasCall = true;
70 const MCSymbol *TargetSymbol = MIB->getTargetSymbol(It);
71 // if it is an indirect call, skip
72 if (TargetSymbol == nullptr) {
73 FuncInfo.Omitted = true;
74 return;
75 }
76 }
77 // check if this function modify stack or heap
78 // TODO: more accurate analysis
79 bool IsPush = MIB->isPush(It);
80 bool IsRipAddr = MIB->hasPCRelOperand(It);
81 if (IsPush)
82 FuncInfo.StackOut = true;
83
84 if (MIB->mayStore(It) && !IsPush && !IsRipAddr)
85 FuncInfo.HeapOut = true;
86
87 if (IsRipAddr)
88 FuncInfo.HasRipAddr = true;
89 } // end of for (auto &It : ...)
90 } // end of for (auto *BB : ...)
91 }
92
checkFunction(BinaryFunction & BF,DataflowInfoManager & DInfo,RegAnalysis & RA,StokeFuncInfo & FuncInfo)93 bool StokeInfo::checkFunction(BinaryFunction &BF, DataflowInfoManager &DInfo,
94 RegAnalysis &RA, StokeFuncInfo &FuncInfo) {
95
96 std::string Name = BF.getSymbol()->getName().str();
97
98 if (!BF.isSimple() || BF.isMultiEntry() || BF.empty())
99 return false;
100 BF.getBinaryContext().outs()
101 << " STOKE-INFO: analyzing function " << Name << "\n";
102
103 FuncInfo.FuncName = Name;
104 FuncInfo.Offset = BF.getFileOffset();
105 FuncInfo.Size = BF.getMaxSize();
106 FuncInfo.NumInstrs = BF.getNumNonPseudos();
107 FuncInfo.NumBlocks = BF.size();
108 // early stop for large functions
109 if (FuncInfo.NumInstrs > 500)
110 return false;
111
112 FuncInfo.IsLoopFree = BF.isLoopFree();
113 if (!FuncInfo.IsLoopFree) {
114 const BinaryLoopInfo &BLI = BF.getLoopInfo();
115 FuncInfo.NumLoops = BLI.OuterLoops;
116 FuncInfo.MaxLoopDepth = BLI.MaximumDepth;
117 }
118
119 FuncInfo.HotSize = BF.estimateHotSize();
120 FuncInfo.TotalSize = BF.estimateSize();
121 FuncInfo.Score = BF.getFunctionScore();
122
123 checkInstr(BF, FuncInfo);
124
125 // register analysis
126 BinaryBasicBlock &EntryBB = BF.front();
127 assert(EntryBB.isEntryPoint() && "Weird, this should be the entry block!");
128
129 MCInst *FirstNonPseudo = EntryBB.getFirstNonPseudoInstr();
130 if (!FirstNonPseudo)
131 return false;
132
133 LLVM_DEBUG(dbgs() << "\t [DefIn]\n\t ");
134 BitVector LiveInBV =
135 *(DInfo.getLivenessAnalysis().getStateAt(FirstNonPseudo));
136 LiveInBV &= DefaultDefInMask;
137 getRegNameFromBitVec(BF.getBinaryContext(), LiveInBV, &FuncInfo.DefIn);
138
139 LLVM_DEBUG(dbgs() << "\t [LiveOut]\n\t ");
140 BitVector LiveOutBV = RA.getFunctionClobberList(&BF);
141 LiveOutBV &= DefaultLiveOutMask;
142 getRegNameFromBitVec(BF.getBinaryContext(), LiveOutBV, &FuncInfo.LiveOut);
143
144 BF.getBinaryContext().outs() << " STOKE-INFO: end function \n";
145 return true;
146 }
147
runOnFunctions(BinaryContext & BC)148 Error StokeInfo::runOnFunctions(BinaryContext &BC) {
149 BC.outs() << "STOKE-INFO: begin of stoke pass\n";
150
151 std::ofstream Outfile;
152 if (!opts::StokeOutputDataFilename.empty()) {
153 Outfile.open(opts::StokeOutputDataFilename);
154 } else {
155 BC.errs() << "STOKE-INFO: output file is required\n";
156 return Error::success();
157 }
158
159 // check some context meta data
160 LLVM_DEBUG(dbgs() << "\tTarget: " << BC.TheTarget->getName() << "\n");
161 LLVM_DEBUG(dbgs() << "\tTripleName " << BC.TripleName << "\n");
162 LLVM_DEBUG(dbgs() << "\tgetNumRegs " << BC.MRI->getNumRegs() << "\n");
163
164 BinaryFunctionCallGraph CG = buildCallGraph(BC);
165 RegAnalysis RA(BC, &BC.getBinaryFunctions(), &CG);
166
167 NumRegs = BC.MRI->getNumRegs();
168 assert(NumRegs > 0 && "STOKE-INFO: the target register number is incorrect!");
169
170 DefaultDefInMask.resize(NumRegs, false);
171 DefaultLiveOutMask.resize(NumRegs, false);
172
173 BC.MIB->getDefaultDefIn(DefaultDefInMask);
174 BC.MIB->getDefaultLiveOut(DefaultLiveOutMask);
175
176 getRegNameFromBitVec(BC, DefaultDefInMask);
177 getRegNameFromBitVec(BC, DefaultLiveOutMask);
178
179 StokeFuncInfo FuncInfo;
180 // analyze all functions
181 FuncInfo.printCsvHeader(Outfile);
182 for (auto &BF : BC.getBinaryFunctions()) {
183 DataflowInfoManager DInfo(BF.second, &RA, nullptr);
184 FuncInfo.reset();
185 if (checkFunction(BF.second, DInfo, RA, FuncInfo))
186 FuncInfo.printData(Outfile);
187 }
188
189 BC.outs() << "STOKE-INFO: end of stoke pass\n";
190 return Error::success();
191 }
192
193 } // namespace bolt
194 } // namespace llvm
195