244 lines · cpp
1//===- bolt/Passes/RegAnalysis.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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the RegAnalysis class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/RegAnalysis.h"14#include "bolt/Core/BinaryFunction.h"15#include "bolt/Core/CallGraphWalker.h"16#include "llvm/MC/MCRegisterInfo.h"17#include "llvm/Support/CommandLine.h"18 19#define DEBUG_TYPE "ra"20 21using namespace llvm;22 23namespace opts {24extern cl::opt<unsigned> Verbosity;25extern cl::OptionCategory BoltOptCategory;26 27cl::opt<bool> AssumeABI("assume-abi",28 cl::desc("assume the ABI is never violated"),29 cl::cat(BoltOptCategory));30}31 32namespace llvm {33namespace bolt {34 35RegAnalysis::RegAnalysis(BinaryContext &BC,36 std::map<uint64_t, BinaryFunction> *BFs,37 BinaryFunctionCallGraph *CG)38 : BC(BC), CS(opts::AssumeABI ? ConservativeStrategy::CLOBBERS_ABI39 : ConservativeStrategy::CLOBBERS_ALL) {40 if (!CG)41 return;42 43 CallGraphWalker CGWalker(*CG);44 45 CGWalker.registerVisitor([&](BinaryFunction *Func) -> bool {46 BitVector RegsKilled = getFunctionClobberList(Func);47 bool Updated = RegsKilledMap.find(Func) == RegsKilledMap.end() ||48 RegsKilledMap[Func] != RegsKilled;49 if (Updated)50 RegsKilledMap[Func] = std::move(RegsKilled);51 return Updated;52 });53 54 CGWalker.registerVisitor([&](BinaryFunction *Func) -> bool {55 BitVector RegsGen = getFunctionUsedRegsList(Func);56 bool Updated = RegsGenMap.find(Func) == RegsGenMap.end() ||57 RegsGenMap[Func] != RegsGen;58 if (Updated)59 RegsGenMap[Func] = std::move(RegsGen);60 return Updated;61 });62 63 CGWalker.walk();64 65 if (opts::Verbosity == 0) {66#ifndef NDEBUG67 if (!DebugFlag || !isCurrentDebugType(DEBUG_TYPE))68 return;69#else70 return;71#endif72 }73 74 if (!BFs)75 return;76 77 // This loop is for computing statistics only78 for (auto &MapEntry : *BFs) {79 BinaryFunction *Func = &MapEntry.second;80 auto Iter = RegsKilledMap.find(Func);81 assert(Iter != RegsKilledMap.end() &&82 "Failed to compute all clobbers list");83 if (Iter->second.all()) {84 uint64_t Count = Func->getExecutionCount();85 if (Count != BinaryFunction::COUNT_NO_PROFILE)86 CountFunctionsAllClobber += Count;87 ++NumFunctionsAllClobber;88 }89 DEBUG_WITH_TYPE("ra",90 dbgs() << "Killed regs set for func: " << Func->getPrintName() << "\n";91 const BitVector &RegsKilled = Iter->second;92 int RegIdx = RegsKilled.find_first();93 while (RegIdx != -1) {94 dbgs() << "\tREG" << RegIdx;95 RegIdx = RegsKilled.find_next(RegIdx);96 };97 dbgs() << "\nUsed regs set for func: " << Func->getPrintName() << "\n";98 const BitVector &RegsUsed = RegsGenMap.find(Func)->second;99 RegIdx = RegsUsed.find_first();100 while (RegIdx != -1) {101 dbgs() << "\tREG" << RegIdx;102 RegIdx = RegsUsed.find_next(RegIdx);103 };104 dbgs() << "\n";105 );106 }107}108 109void RegAnalysis::beConservative(BitVector &Result) const {110 switch (CS) {111 case ConservativeStrategy::CLOBBERS_ALL:112 Result.set();113 break;114 case ConservativeStrategy::CLOBBERS_ABI: {115 BitVector BV(BC.MRI->getNumRegs(), false);116 BC.MIB->getCalleeSavedRegs(BV);117 BV.flip();118 Result |= BV;119 break;120 }121 case ConservativeStrategy::CLOBBERS_NONE:122 Result.reset();123 break;124 }125}126 127bool RegAnalysis::isConservative(BitVector &Vec) const {128 switch (CS) {129 case ConservativeStrategy::CLOBBERS_ALL:130 return Vec.all();131 case ConservativeStrategy::CLOBBERS_ABI: {132 BitVector BV(BC.MRI->getNumRegs(), false);133 BC.MIB->getCalleeSavedRegs(BV);134 BV |= Vec;135 return BV.all();136 }137 case ConservativeStrategy::CLOBBERS_NONE:138 return Vec.none();139 }140 return false;141}142 143void RegAnalysis::getInstUsedRegsList(const MCInst &Inst, BitVector &RegSet,144 bool GetClobbers) const {145 if (!BC.MIB->isCall(Inst)) {146 if (GetClobbers)147 BC.MIB->getClobberedRegs(Inst, RegSet);148 else149 BC.MIB->getUsedRegs(Inst, RegSet);150 return;151 }152 153 // If no call graph supplied...154 if (RegsKilledMap.size() == 0) {155 beConservative(RegSet);156 return;157 }158 159 const MCSymbol *TargetSymbol = BC.MIB->getTargetSymbol(Inst);160 // If indirect call, we know nothing161 if (TargetSymbol == nullptr) {162 beConservative(RegSet);163 return;164 }165 166 const BinaryFunction *Function = BC.getFunctionForSymbol(TargetSymbol);167 if (Function == nullptr) {168 // Call to a function without a BinaryFunction object.169 // This should be a call to a PLT entry, and since it is a trampoline to170 // a DSO, we can't really know the code in advance.171 beConservative(RegSet);172 return;173 }174 if (GetClobbers) {175 auto BV = RegsKilledMap.find(Function);176 if (BV != RegsKilledMap.end()) {177 RegSet |= BV->second;178 return;179 }180 // Ignore calls to function whose clobber list wasn't yet calculated. This181 // instruction will be evaluated again once we have info for the callee.182 return;183 }184 auto BV = RegsGenMap.find(Function);185 if (BV != RegsGenMap.end()) {186 RegSet |= BV->second;187 return;188 }189}190 191void RegAnalysis::getInstClobberList(const MCInst &Inst,192 BitVector &KillSet) const {193 return getInstUsedRegsList(Inst, KillSet, /*GetClobbers*/ true);194}195 196BitVector RegAnalysis::getFunctionUsedRegsList(const BinaryFunction *Func) {197 BitVector UsedRegs = BitVector(BC.MRI->getNumRegs(), false);198 199 if (!Func->isSimple() || !Func->hasCFG()) {200 beConservative(UsedRegs);201 return UsedRegs;202 }203 204 for (const BinaryBasicBlock &BB : *Func) {205 for (const MCInst &Inst : BB) {206 getInstUsedRegsList(Inst, UsedRegs, /*GetClobbers*/ false);207 if (UsedRegs.all())208 return UsedRegs;209 }210 }211 212 return UsedRegs;213}214 215BitVector RegAnalysis::getFunctionClobberList(const BinaryFunction *Func) {216 BitVector RegsKilled = BitVector(BC.MRI->getNumRegs(), false);217 218 if (!Func->isSimple() || !Func->hasCFG()) {219 beConservative(RegsKilled);220 return RegsKilled;221 }222 223 for (const BinaryBasicBlock &BB : *Func) {224 for (const MCInst &Inst : BB) {225 getInstClobberList(Inst, RegsKilled);226 if (RegsKilled.all())227 return RegsKilled;228 }229 }230 231 return RegsKilled;232}233 234void RegAnalysis::printStats() {235 BC.outs() << "BOLT-INFO REG ANALYSIS: Number of functions conservatively "236 "treated as clobbering all registers: "237 << NumFunctionsAllClobber238 << format(" (%.1lf%% dyn cov)\n",239 (100.0 * CountFunctionsAllClobber / CountDenominator));240}241 242} // namespace bolt243} // namespace llvm244