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