bolt/lib/Passes/ValidateInternalCalls.cpp

   1 //===- bolt/Passes/ValidateInternalCalls.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 ValidateInternalCalls class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/ValidateInternalCalls.h"
  14 #include "bolt/Core/BinaryBasicBlock.h"
  15 #include "bolt/Passes/DataflowInfoManager.h"
  16 #include "bolt/Passes/FrameAnalysis.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/MC/MCInstPrinter.h"
  19 #include <optional>
  20 #include <queue>
  21
  22 #define DEBUG_TYPE "bolt-internalcalls"
  23
  24 namespace llvm {
  25 namespace bolt {
  26
  27 namespace {
  28
  29 // Helper used to extract the target basic block used in an internal call.
  30 // Return nullptr if this is not an internal call target.
  31 BinaryBasicBlock *getInternalCallTarget(BinaryFunction &Function,
  32                                         const MCInst &Inst) {
  33   const BinaryContext &BC = Function.getBinaryContext();
  34   if (!BC.MIB->isCall(Inst) || MCPlus::getNumPrimeOperands(Inst) != 1 ||
  35       !Inst.getOperand(0).isExpr())
  36     return nullptr;
  37
  38   return Function.getBasicBlockForLabel(BC.MIB->getTargetSymbol(Inst));
  39 }
  40
  41 // A special StackPointerTracking that considers internal calls
  42 class StackPointerTrackingForInternalCalls
  43     : public StackPointerTrackingBase<StackPointerTrackingForInternalCalls> {
  44   friend class DataflowAnalysis<StackPointerTrackingForInternalCalls,
  45                                 std::pair<int, int>>;
  46
  47   std::optional<unsigned> AnnotationIndex;
  48
  49 protected:
  50   // We change the starting state to only consider the first block as an
  51   // entry point, otherwise the analysis won't converge (there will be two valid
  52   // stack offsets, one for an external call and another for an internal call).
  53   std::pair<int, int> getStartingStateAtBB(const BinaryBasicBlock &BB) {
  54     if (&BB == &*Func.begin())
  55       return std::make_pair(-8, getEmpty());
  56     return std::make_pair(getEmpty(), getEmpty());
  57   }
  58
  59   // Here we decrement SP for internal calls too, in addition to the regular
  60   // StackPointerTracking processing.
  61   std::pair<int, int> computeNext(const MCInst &Point,
  62                                   const std::pair<int, int> &Cur) {
  63     std::pair<int, int> Res = StackPointerTrackingBase<
  64         StackPointerTrackingForInternalCalls>::computeNext(Point, Cur);
  65     if (Res.first == StackPointerTracking::SUPERPOSITION ||
  66         Res.first == StackPointerTracking::EMPTY)
  67       return Res;
  68
  69     if (BC.MIB->isReturn(Point)) {
  70       Res.first += 8;
  71       return Res;
  72     }
  73
  74     BinaryBasicBlock *Target = getInternalCallTarget(Func, Point);
  75     if (!Target)
  76       return Res;
  77
  78     Res.first -= 8;
  79     return Res;
  80   }
  81
  82   StringRef getAnnotationName() const {
  83     return StringRef("StackPointerTrackingForInternalCalls");
  84   }
  85
  86 public:
  87   StackPointerTrackingForInternalCalls(BinaryFunction &BF)
  88       : StackPointerTrackingBase<StackPointerTrackingForInternalCalls>(BF) {}
  89
  90   void run() {
  91     StackPointerTrackingBase<StackPointerTrackingForInternalCalls>::run();
  92   }
  93 };
  94
  95 } // end anonymous namespace
  96
  97 void ValidateInternalCalls::fixCFGForPIC(BinaryFunction &Function) const {
  98   std::queue<BinaryBasicBlock *> Work;
  99   for (BinaryBasicBlock &BB : Function)
 100     Work.emplace(&BB);
 101
 102   while (!Work.empty()) {
 103     BinaryBasicBlock &BB = *Work.front();
 104     Work.pop();
 105
 106     // Search for the next internal call.
 107     const BinaryBasicBlock::iterator InternalCall =
 108         llvm::find_if(BB, [&](const MCInst &Inst) {
 109           return getInternalCallTarget(Function, Inst) != nullptr;
 110         });
 111
 112     // No internal call? Done with this block.
 113     if (InternalCall == BB.end())
 114       continue;
 115
 116     BinaryBasicBlock *Target = getInternalCallTarget(Function, *InternalCall);
 117     InstructionListType MovedInsts = BB.splitInstructions(&*InternalCall);
 118     if (!MovedInsts.empty()) {
 119       // Split this block at the call instruction.
 120       std::unique_ptr<BinaryBasicBlock> NewBB = Function.createBasicBlock();
 121       NewBB->addInstructions(MovedInsts.begin(), MovedInsts.end());
 122       BB.moveAllSuccessorsTo(NewBB.get());
 123
 124       Work.emplace(NewBB.get());
 125       std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;
 126       NewBBs.emplace_back(std::move(NewBB));
 127       Function.insertBasicBlocks(&BB, std::move(NewBBs));
 128     }
 129     // Update successors
 130     BB.removeAllSuccessors();
 131     BB.addSuccessor(Target, BB.getExecutionCount(), 0ULL);
 132   }
 133 }
 134
 135 bool ValidateInternalCalls::fixCFGForIC(BinaryFunction &Function) const {
 136   const BinaryContext &BC = Function.getBinaryContext();
 137   // Track SP value
 138   StackPointerTrackingForInternalCalls SPTIC(Function);
 139   SPTIC.run();
 140
 141   // Track instructions reaching a given point of the CFG to answer
 142   // "There is a path from entry to point A that contains instruction B"
 143   ReachingInsns<false> RI(Function);
 144   RI.run();
 145
 146   // We use the InsnToBB map that DataflowInfoManager provides us
 147   DataflowInfoManager Info(Function, nullptr, nullptr);
 148
 149   bool Updated = false;
 150
 151   auto processReturns = [&](BinaryBasicBlock &BB, MCInst &Return) {
 152     // Check all reaching internal calls
 153     for (auto I = RI.expr_begin(Return), E = RI.expr_end(); I != E; ++I) {
 154       MCInst &ReachingInst = **I;
 155       if (!getInternalCallTarget(Function, ReachingInst) ||
 156           BC.MIB->hasAnnotation(ReachingInst, getProcessedICTag()))
 157         continue;
 158
 159       // Stack pointer matching
 160       int SPAtCall = SPTIC.getStateAt(ReachingInst)->first;
 161       int SPAtRet = SPTIC.getStateAt(Return)->first;
 162       if (SPAtCall != StackPointerTracking::SUPERPOSITION &&
 163           SPAtRet != StackPointerTracking::SUPERPOSITION &&
 164           SPAtCall != SPAtRet - 8)
 165         continue;
 166
 167       Updated = true;
 168
 169       // Mark this call as processed, so we don't try to analyze it as a
 170       // PIC-computation internal call.
 171       BC.MIB->addAnnotation(ReachingInst, getProcessedICTag(), 0U);
 172
 173       // Connect this block with the returning block of the caller
 174       BinaryBasicBlock *CallerBlock = Info.getInsnToBBMap()[&ReachingInst];
 175       BinaryBasicBlock *ReturnDestBlock =
 176           Function.getLayout().getBasicBlockAfter(CallerBlock);
 177       BB.addSuccessor(ReturnDestBlock, BB.getExecutionCount(), 0);
 178     }
 179   };
 180
 181   // This will connect blocks terminated with RETs to their respective
 182   // internal caller return block. A note here: this is overly conservative
 183   // because in nested calls, or unrelated calls, it will create edges
 184   // connecting RETs to potentially unrelated internal calls. This is safe
 185   // and if this causes a problem to recover the stack offsets properly, we
 186   // will fail later.
 187   for (BinaryBasicBlock &BB : Function) {
 188     for (MCInst &Inst : BB) {
 189       if (!BC.MIB->isReturn(Inst))
 190         continue;
 191
 192       processReturns(BB, Inst);
 193     }
 194   }
 195   return Updated;
 196 }
 197
 198 bool ValidateInternalCalls::hasTailCallsInRange(
 199     BinaryFunction &Function) const {
 200   const BinaryContext &BC = Function.getBinaryContext();
 201   for (BinaryBasicBlock &BB : Function)
 202     for (MCInst &Inst : BB)
 203       if (BC.MIB->isTailCall(Inst))
 204         return true;
 205   return false;
 206 }
 207
 208 bool ValidateInternalCalls::analyzeFunction(BinaryFunction &Function) const {
 209   fixCFGForPIC(Function);
 210   while (fixCFGForIC(Function)) {
 211   }
 212
 213   BinaryContext &BC = Function.getBinaryContext();
 214   RegAnalysis RA = RegAnalysis(BC, nullptr, nullptr);
 215   RA.setConservativeStrategy(RegAnalysis::ConservativeStrategy::CLOBBERS_NONE);
 216   bool HasTailCalls = hasTailCallsInRange(Function);
 217
 218   for (BinaryBasicBlock &BB : Function) {
 219     for (MCInst &Inst : BB) {
 220       BinaryBasicBlock *Target = getInternalCallTarget(Function, Inst);
 221       if (!Target || BC.MIB->hasAnnotation(Inst, getProcessedICTag()))
 222         continue;
 223
 224       if (HasTailCalls) {
 225         LLVM_DEBUG(dbgs() << Function
 226                           << " has tail calls and internal calls.\n");
 227         return false;
 228       }
 229
 230       FrameIndexEntry FIE;
 231       int32_t SrcImm = 0;
 232       MCPhysReg Reg = 0;
 233       int64_t StackOffset = 0;
 234       bool IsIndexed = false;
 235       MCInst *TargetInst = ProgramPoint::getFirstPointAt(*Target).getInst();
 236       if (!BC.MIB->isStackAccess(*TargetInst, FIE.IsLoad, FIE.IsStore,
 237                                  FIE.IsStoreFromReg, Reg, SrcImm,
 238                                  FIE.StackPtrReg, StackOffset, FIE.Size,
 239                                  FIE.IsSimple, IsIndexed)) {
 240         LLVM_DEBUG({
 241           dbgs() << "Frame analysis failed - not simple: " << Function << "\n";
 242           Function.dump();
 243         });
 244         return false;
 245       }
 246       if (!FIE.IsLoad || FIE.StackPtrReg != BC.MIB->getStackPointer() ||
 247           StackOffset != 0) {
 248         LLVM_DEBUG({
 249           dbgs() << "Target instruction does not fetch return address - not "
 250                     "simple: "
 251                  << Function << "\n";
 252           Function.dump();
 253         });
 254         return false;
 255       }
 256       // Now track how the return address is used by tracking uses of Reg
 257       ReachingDefOrUse</*Def=*/false> RU =
 258           ReachingDefOrUse<false>(RA, Function, Reg);
 259       RU.run();
 260
 261       int64_t Offset = static_cast<int64_t>(Target->getInputOffset());
 262       bool UseDetected = false;
 263       for (auto I = RU.expr_begin(*RU.getStateBefore(*TargetInst)),
 264                 E = RU.expr_end();
 265            I != E; ++I) {
 266         MCInst &Use = **I;
 267         BitVector UsedRegs = BitVector(BC.MRI->getNumRegs(), false);
 268         BC.MIB->getTouchedRegs(Use, UsedRegs);
 269         if (!UsedRegs[Reg])
 270           continue;
 271         UseDetected = true;
 272         int64_t Output;
 273         std::pair<MCPhysReg, int64_t> Input1 = std::make_pair(Reg, 0);
 274         std::pair<MCPhysReg, int64_t> Input2 = std::make_pair(0, 0);
 275         if (!BC.MIB->evaluateStackOffsetExpr(Use, Output, Input1, Input2)) {
 276           LLVM_DEBUG(dbgs() << "Evaluate stack offset expr failed.\n");
 277           return false;
 278         }
 279         if (Offset + Output < 0 ||
 280             Offset + Output > static_cast<int64_t>(Function.getSize())) {
 281           LLVM_DEBUG({
 282             dbgs() << "Detected out-of-range PIC reference in " << Function
 283                    << "\nReturn address load: ";
 284             BC.InstPrinter->printInst(TargetInst, 0, "", *BC.STI, dbgs());
 285             dbgs() << "\nUse: ";
 286             BC.InstPrinter->printInst(&Use, 0, "", *BC.STI, dbgs());
 287             dbgs() << "\n";
 288             Function.dump();
 289           });
 290           return false;
 291         }
 292         LLVM_DEBUG({
 293           dbgs() << "Validated access: ";
 294           BC.InstPrinter->printInst(&Use, 0, "", *BC.STI, dbgs());
 295           dbgs() << "\n";
 296         });
 297       }
 298       if (!UseDetected) {
 299         LLVM_DEBUG(dbgs() << "No use detected.\n");
 300         return false;
 301       }
 302     }
 303   }
 304   return true;
 305 }
 306
 307 void ValidateInternalCalls::runOnFunctions(BinaryContext &BC) {
 308   if (!BC.isX86())
 309     return;
 310
 311   // Look for functions that need validation. This should be pretty rare.
 312   std::set<BinaryFunction *> NeedsValidation;
 313   for (auto &BFI : BC.getBinaryFunctions()) {
 314     BinaryFunction &Function = BFI.second;
 315     for (BinaryBasicBlock &BB : Function) {
 316       for (MCInst &Inst : BB) {
 317         if (getInternalCallTarget(Function, Inst)) {
 318           NeedsValidation.insert(&Function);
 319           Function.setSimple(false);
 320           break;
 321         }
 322       }
 323     }
 324   }
 325
 326   // Skip validation for non-relocation mode
 327   if (!BC.HasRelocations)
 328     return;
 329
 330   // Since few functions need validation, we can work with our most expensive
 331   // algorithms here. Fix the CFG treating internal calls as unconditional
 332   // jumps. This optimistically assumes this call is a PIC trick to get the PC
 333   // value, so it is not really a call, but a jump. If we find that it's not the
 334   // case, we mark this function as non-simple and stop processing it.
 335   std::set<BinaryFunction *> Invalid;
 336   for (BinaryFunction *Function : NeedsValidation) {
 337     LLVM_DEBUG(dbgs() << "Validating " << *Function << "\n");
 338     if (!analyzeFunction(*Function))
 339       Invalid.insert(Function);
 340     clearAnnotations(*Function);
 341   }
 342
 343   if (!Invalid.empty()) {
 344     errs() << "BOLT-WARNING: will skip the following function(s) as unsupported"
 345               " internal calls were detected:\n";
 346     for (BinaryFunction *Function : Invalid) {
 347       errs() << "              " << *Function << "\n";
 348       Function->setIgnored();
 349     }
 350   }
 351 }
 352
 353 } // namespace bolt
 354 } // namespace llvm