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/MC/MCInstPrinter.h" 18 #include <optional> 19 #include <queue> 20 21 #define DEBUG_TYPE "bolt-internalcalls" 22 23 namespace llvm { 24 namespace bolt { 25 26 namespace { 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. 30 BinaryBasicBlock *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 calls 41 class StackPointerTrackingForInternalCalls 42 : public StackPointerTrackingBase<StackPointerTrackingForInternalCalls> { 43 friend class DataflowAnalysis<StackPointerTrackingForInternalCalls, 44 std::pair<int, int>>; 45 46 std::optional<unsigned> AnnotationIndex; 47 48 protected: 49 // We change the starting state to only consider the first block as an 50 // entry point, otherwise the analysis won't converge (there will be two valid 51 // 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 regular 59 // 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 85 public: 86 StackPointerTrackingForInternalCalls(BinaryFunction &BF) 87 : StackPointerTrackingBase<StackPointerTrackingForInternalCalls>(BF) {} 88 89 void run() { 90 StackPointerTrackingBase<StackPointerTrackingForInternalCalls>::run(); 91 } 92 }; 93 94 } // end anonymous namespace 95 96 void 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 successors 129 BB.removeAllSuccessors(); 130 BB.addSuccessor(Target, BB.getExecutionCount(), 0ULL); 131 } 132 } 133 134 bool ValidateInternalCalls::fixCFGForIC(BinaryFunction &Function) const { 135 const BinaryContext &BC = Function.getBinaryContext(); 136 // Track SP value 137 StackPointerTrackingForInternalCalls SPTIC(Function); 138 SPTIC.run(); 139 140 // Track instructions reaching a given point of the CFG to answer 141 // "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 us 146 DataflowInfoManager Info(Function, nullptr, nullptr); 147 148 bool Updated = false; 149 150 auto processReturns = [&](BinaryBasicBlock &BB, MCInst &Return) { 151 // Check all reaching internal calls 152 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 matching 159 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 a 169 // PIC-computation internal call. 170 BC.MIB->addAnnotation(ReachingInst, getProcessedICTag(), 0U); 171 172 // Connect this block with the returning block of the caller 173 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 respective 181 // internal caller return block. A note here: this is overly conservative 182 // because in nested calls, or unrelated calls, it will create edges 183 // connecting RETs to potentially unrelated internal calls. This is safe 184 // and if this causes a problem to recover the stack offsets properly, we 185 // 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 197 bool 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 207 bool 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() << Function 225 << " 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 Reg 256 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 " << Function 282 << "\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 304 Error 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 mode 327 if (!BC.HasRelocations) 328 return Error::success(); 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 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 bolt 356 } // namespace llvm 357