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