bolt/lib/Passes/RegAnalysis.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-exception
   6 //
   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/Passes/CallGraphWalker.h"
  16 #include "llvm/MC/MCRegisterInfo.h"
  17 #include "llvm/Support/CommandLine.h"
  18
  19 #define DEBUG_TYPE "ra"
  20
  21 using namespace llvm;
  22
  23 namespace opts {
  24 extern cl::opt<unsigned> Verbosity;
  25 extern cl::OptionCategory BoltOptCategory;
  26
  27 cl::opt<bool> AssumeABI("assume-abi",
  28                         cl::desc("assume the ABI is never violated"),
  29                         cl::cat(BoltOptCategory));
  30 }
  31
  32 namespace llvm {
  33 namespace bolt {
  34
  35 RegAnalysis::RegAnalysis(BinaryContext &BC,
  36                          std::map<uint64_t, BinaryFunction> *BFs,
  37                          BinaryFunctionCallGraph *CG)
  38     : BC(BC), CS(opts::AssumeABI ? ConservativeStrategy::CLOBBERS_ABI
  39                                  : 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 NDEBUG
  67     if (!DebugFlag || !isCurrentDebugType(DEBUG_TYPE))
  68       return;
  69 #else
  70     return;
  71 #endif
  72   }
  73
  74   if (!BFs)
  75     return;
  76
  77   // This loop is for computing statistics only
  78   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
 109 void 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
 127 bool 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
 143 void 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     else
 149       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 nothing
 161   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 to
 170     // 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. This
 181     // 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
 191 void RegAnalysis::getInstClobberList(const MCInst &Inst,
 192                                      BitVector &KillSet) const {
 193   return getInstUsedRegsList(Inst, KillSet, /*GetClobbers*/ true);
 194 }
 195
 196 BitVector 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
 215 BitVector 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
 234 void RegAnalysis::printStats() {
 235   outs() << "BOLT-INFO REG ANALYSIS: Number of functions conservatively "
 236             "treated as clobbering all registers: "
 237          << NumFunctionsAllClobber
 238          << format(" (%.1lf%% dyn cov)\n",
 239                    (100.0 * CountFunctionsAllClobber / CountDenominator));
 240 }
 241
 242 } // namespace bolt
 243 } // namespace llvm