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