1 //===- SCCPSolver.cpp - SCCP Utility --------------------------- *- C++ -*-===// 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 // \file 10 // This file implements the Sparse Conditional Constant Propagation (SCCP) 11 // utility. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/Utils/SCCPSolver.h" 16 #include "llvm/Analysis/ConstantFolding.h" 17 #include "llvm/Analysis/InstructionSimplify.h" 18 #include "llvm/Analysis/ValueLattice.h" 19 #include "llvm/Analysis/ValueLatticeUtils.h" 20 #include "llvm/Analysis/ValueTracking.h" 21 #include "llvm/IR/InstVisitor.h" 22 #include "llvm/Support/Casting.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include "llvm/Support/raw_ostream.h" 26 #include "llvm/Transforms/Utils/Local.h" 27 #include <cassert> 28 #include <utility> 29 #include <vector> 30 31 using namespace llvm; 32 33 #define DEBUG_TYPE "sccp" 34 35 // The maximum number of range extensions allowed for operations requiring 36 // widening. 37 static const unsigned MaxNumRangeExtensions = 10; 38 39 /// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions. 40 static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() { 41 return ValueLatticeElement::MergeOptions().setMaxWidenSteps( 42 MaxNumRangeExtensions); 43 } 44 45 static ConstantRange getConstantRange(const ValueLatticeElement &LV, Type *Ty, 46 bool UndefAllowed = true) { 47 assert(Ty->isIntOrIntVectorTy() && "Should be int or int vector"); 48 if (LV.isConstantRange(UndefAllowed)) 49 return LV.getConstantRange(); 50 return ConstantRange::getFull(Ty->getScalarSizeInBits()); 51 } 52 53 namespace llvm { 54 55 bool SCCPSolver::isConstant(const ValueLatticeElement &LV) { 56 return LV.isConstant() || 57 (LV.isConstantRange() && LV.getConstantRange().isSingleElement()); 58 } 59 60 bool SCCPSolver::isOverdefined(const ValueLatticeElement &LV) { 61 return !LV.isUnknownOrUndef() && !SCCPSolver::isConstant(LV); 62 } 63 64 static bool canRemoveInstruction(Instruction *I) { 65 if (wouldInstructionBeTriviallyDead(I)) 66 return true; 67 68 // Some instructions can be handled but are rejected above. Catch 69 // those cases by falling through to here. 70 // TODO: Mark globals as being constant earlier, so 71 // TODO: wouldInstructionBeTriviallyDead() knows that atomic loads 72 // TODO: are safe to remove. 73 return isa<LoadInst>(I); 74 } 75 76 bool SCCPSolver::tryToReplaceWithConstant(Value *V) { 77 Constant *Const = getConstantOrNull(V); 78 if (!Const) 79 return false; 80 // Replacing `musttail` instructions with constant breaks `musttail` invariant 81 // unless the call itself can be removed. 82 // Calls with "clang.arc.attachedcall" implicitly use the return value and 83 // those uses cannot be updated with a constant. 84 CallBase *CB = dyn_cast<CallBase>(V); 85 if (CB && ((CB->isMustTailCall() && 86 !canRemoveInstruction(CB)) || 87 CB->getOperandBundle(LLVMContext::OB_clang_arc_attachedcall))) { 88 Function *F = CB->getCalledFunction(); 89 90 // Don't zap returns of the callee 91 if (F) 92 addToMustPreserveReturnsInFunctions(F); 93 94 LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB 95 << " as a constant\n"); 96 return false; 97 } 98 99 LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n'); 100 101 // Replaces all of the uses of a variable with uses of the constant. 102 V->replaceAllUsesWith(Const); 103 return true; 104 } 105 106 /// Try to use \p Inst's value range from \p Solver to infer the NUW flag. 107 static bool refineInstruction(SCCPSolver &Solver, 108 const SmallPtrSetImpl<Value *> &InsertedValues, 109 Instruction &Inst) { 110 if (!isa<OverflowingBinaryOperator>(Inst)) 111 return false; 112 113 auto GetRange = [&Solver, &InsertedValues](Value *Op) { 114 if (auto *Const = dyn_cast<ConstantInt>(Op)) 115 return ConstantRange(Const->getValue()); 116 if (isa<Constant>(Op) || InsertedValues.contains(Op)) { 117 unsigned Bitwidth = Op->getType()->getScalarSizeInBits(); 118 return ConstantRange::getFull(Bitwidth); 119 } 120 return getConstantRange(Solver.getLatticeValueFor(Op), Op->getType(), 121 /*UndefAllowed=*/false); 122 }; 123 auto RangeA = GetRange(Inst.getOperand(0)); 124 auto RangeB = GetRange(Inst.getOperand(1)); 125 bool Changed = false; 126 if (!Inst.hasNoUnsignedWrap()) { 127 auto NUWRange = ConstantRange::makeGuaranteedNoWrapRegion( 128 Instruction::BinaryOps(Inst.getOpcode()), RangeB, 129 OverflowingBinaryOperator::NoUnsignedWrap); 130 if (NUWRange.contains(RangeA)) { 131 Inst.setHasNoUnsignedWrap(); 132 Changed = true; 133 } 134 } 135 if (!Inst.hasNoSignedWrap()) { 136 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion( 137 Instruction::BinaryOps(Inst.getOpcode()), RangeB, OverflowingBinaryOperator::NoSignedWrap); 138 if (NSWRange.contains(RangeA)) { 139 Inst.setHasNoSignedWrap(); 140 Changed = true; 141 } 142 } 143 144 return Changed; 145 } 146 147 /// Try to replace signed instructions with their unsigned equivalent. 148 static bool replaceSignedInst(SCCPSolver &Solver, 149 SmallPtrSetImpl<Value *> &InsertedValues, 150 Instruction &Inst) { 151 // Determine if a signed value is known to be >= 0. 152 auto isNonNegative = [&Solver](Value *V) { 153 // If this value was constant-folded, it may not have a solver entry. 154 // Handle integers. Otherwise, return false. 155 if (auto *C = dyn_cast<Constant>(V)) { 156 auto *CInt = dyn_cast<ConstantInt>(C); 157 return CInt && !CInt->isNegative(); 158 } 159 const ValueLatticeElement &IV = Solver.getLatticeValueFor(V); 160 return IV.isConstantRange(/*UndefAllowed=*/false) && 161 IV.getConstantRange().isAllNonNegative(); 162 }; 163 164 Instruction *NewInst = nullptr; 165 switch (Inst.getOpcode()) { 166 // Note: We do not fold sitofp -> uitofp here because that could be more 167 // expensive in codegen and may not be reversible in the backend. 168 case Instruction::SExt: { 169 // If the source value is not negative, this is a zext. 170 Value *Op0 = Inst.getOperand(0); 171 if (InsertedValues.count(Op0) || !isNonNegative(Op0)) 172 return false; 173 NewInst = new ZExtInst(Op0, Inst.getType(), "", &Inst); 174 break; 175 } 176 case Instruction::AShr: { 177 // If the shifted value is not negative, this is a logical shift right. 178 Value *Op0 = Inst.getOperand(0); 179 if (InsertedValues.count(Op0) || !isNonNegative(Op0)) 180 return false; 181 NewInst = BinaryOperator::CreateLShr(Op0, Inst.getOperand(1), "", &Inst); 182 break; 183 } 184 case Instruction::SDiv: 185 case Instruction::SRem: { 186 // If both operands are not negative, this is the same as udiv/urem. 187 Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1); 188 if (InsertedValues.count(Op0) || InsertedValues.count(Op1) || 189 !isNonNegative(Op0) || !isNonNegative(Op1)) 190 return false; 191 auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv 192 : Instruction::URem; 193 NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", &Inst); 194 break; 195 } 196 default: 197 return false; 198 } 199 200 // Wire up the new instruction and update state. 201 assert(NewInst && "Expected replacement instruction"); 202 NewInst->takeName(&Inst); 203 InsertedValues.insert(NewInst); 204 Inst.replaceAllUsesWith(NewInst); 205 Solver.removeLatticeValueFor(&Inst); 206 Inst.eraseFromParent(); 207 return true; 208 } 209 210 bool SCCPSolver::simplifyInstsInBlock(BasicBlock &BB, 211 SmallPtrSetImpl<Value *> &InsertedValues, 212 Statistic &InstRemovedStat, 213 Statistic &InstReplacedStat) { 214 bool MadeChanges = false; 215 for (Instruction &Inst : make_early_inc_range(BB)) { 216 if (Inst.getType()->isVoidTy()) 217 continue; 218 if (tryToReplaceWithConstant(&Inst)) { 219 if (canRemoveInstruction(&Inst)) 220 Inst.eraseFromParent(); 221 222 MadeChanges = true; 223 ++InstRemovedStat; 224 } else if (replaceSignedInst(*this, InsertedValues, Inst)) { 225 MadeChanges = true; 226 ++InstReplacedStat; 227 } else if (refineInstruction(*this, InsertedValues, Inst)) { 228 MadeChanges = true; 229 } 230 } 231 return MadeChanges; 232 } 233 234 bool SCCPSolver::removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, 235 BasicBlock *&NewUnreachableBB) const { 236 SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors; 237 bool HasNonFeasibleEdges = false; 238 for (BasicBlock *Succ : successors(BB)) { 239 if (isEdgeFeasible(BB, Succ)) 240 FeasibleSuccessors.insert(Succ); 241 else 242 HasNonFeasibleEdges = true; 243 } 244 245 // All edges feasible, nothing to do. 246 if (!HasNonFeasibleEdges) 247 return false; 248 249 // SCCP can only determine non-feasible edges for br, switch and indirectbr. 250 Instruction *TI = BB->getTerminator(); 251 assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) || 252 isa<IndirectBrInst>(TI)) && 253 "Terminator must be a br, switch or indirectbr"); 254 255 if (FeasibleSuccessors.size() == 0) { 256 // Branch on undef/poison, replace with unreachable. 257 SmallPtrSet<BasicBlock *, 8> SeenSuccs; 258 SmallVector<DominatorTree::UpdateType, 8> Updates; 259 for (BasicBlock *Succ : successors(BB)) { 260 Succ->removePredecessor(BB); 261 if (SeenSuccs.insert(Succ).second) 262 Updates.push_back({DominatorTree::Delete, BB, Succ}); 263 } 264 TI->eraseFromParent(); 265 new UnreachableInst(BB->getContext(), BB); 266 DTU.applyUpdatesPermissive(Updates); 267 } else if (FeasibleSuccessors.size() == 1) { 268 // Replace with an unconditional branch to the only feasible successor. 269 BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin(); 270 SmallVector<DominatorTree::UpdateType, 8> Updates; 271 bool HaveSeenOnlyFeasibleSuccessor = false; 272 for (BasicBlock *Succ : successors(BB)) { 273 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) { 274 // Don't remove the edge to the only feasible successor the first time 275 // we see it. We still do need to remove any multi-edges to it though. 276 HaveSeenOnlyFeasibleSuccessor = true; 277 continue; 278 } 279 280 Succ->removePredecessor(BB); 281 Updates.push_back({DominatorTree::Delete, BB, Succ}); 282 } 283 284 BranchInst::Create(OnlyFeasibleSuccessor, BB); 285 TI->eraseFromParent(); 286 DTU.applyUpdatesPermissive(Updates); 287 } else if (FeasibleSuccessors.size() > 1) { 288 SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI)); 289 SmallVector<DominatorTree::UpdateType, 8> Updates; 290 291 // If the default destination is unfeasible it will never be taken. Replace 292 // it with a new block with a single Unreachable instruction. 293 BasicBlock *DefaultDest = SI->getDefaultDest(); 294 if (!FeasibleSuccessors.contains(DefaultDest)) { 295 if (!NewUnreachableBB) { 296 NewUnreachableBB = 297 BasicBlock::Create(DefaultDest->getContext(), "default.unreachable", 298 DefaultDest->getParent(), DefaultDest); 299 new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB); 300 } 301 302 SI->setDefaultDest(NewUnreachableBB); 303 Updates.push_back({DominatorTree::Delete, BB, DefaultDest}); 304 Updates.push_back({DominatorTree::Insert, BB, NewUnreachableBB}); 305 } 306 307 for (auto CI = SI->case_begin(); CI != SI->case_end();) { 308 if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) { 309 ++CI; 310 continue; 311 } 312 313 BasicBlock *Succ = CI->getCaseSuccessor(); 314 Succ->removePredecessor(BB); 315 Updates.push_back({DominatorTree::Delete, BB, Succ}); 316 SI.removeCase(CI); 317 // Don't increment CI, as we removed a case. 318 } 319 320 DTU.applyUpdatesPermissive(Updates); 321 } else { 322 llvm_unreachable("Must have at least one feasible successor"); 323 } 324 return true; 325 } 326 327 /// Helper class for SCCPSolver. This implements the instruction visitor and 328 /// holds all the state. 329 class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> { 330 const DataLayout &DL; 331 std::function<const TargetLibraryInfo &(Function &)> GetTLI; 332 SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable. 333 DenseMap<Value *, ValueLatticeElement> 334 ValueState; // The state each value is in. 335 336 /// StructValueState - This maintains ValueState for values that have 337 /// StructType, for example for formal arguments, calls, insertelement, etc. 338 DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement> StructValueState; 339 340 /// GlobalValue - If we are tracking any values for the contents of a global 341 /// variable, we keep a mapping from the constant accessor to the element of 342 /// the global, to the currently known value. If the value becomes 343 /// overdefined, it's entry is simply removed from this map. 344 DenseMap<GlobalVariable *, ValueLatticeElement> TrackedGlobals; 345 346 /// TrackedRetVals - If we are tracking arguments into and the return 347 /// value out of a function, it will have an entry in this map, indicating 348 /// what the known return value for the function is. 349 MapVector<Function *, ValueLatticeElement> TrackedRetVals; 350 351 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions 352 /// that return multiple values. 353 MapVector<std::pair<Function *, unsigned>, ValueLatticeElement> 354 TrackedMultipleRetVals; 355 356 /// The set of values whose lattice has been invalidated. 357 /// Populated by resetLatticeValueFor(), cleared after resolving undefs. 358 DenseSet<Value *> Invalidated; 359 360 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is 361 /// represented here for efficient lookup. 362 SmallPtrSet<Function *, 16> MRVFunctionsTracked; 363 364 /// A list of functions whose return cannot be modified. 365 SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions; 366 367 /// TrackingIncomingArguments - This is the set of functions for whose 368 /// arguments we make optimistic assumptions about and try to prove as 369 /// constants. 370 SmallPtrSet<Function *, 16> TrackingIncomingArguments; 371 372 /// The reason for two worklists is that overdefined is the lowest state 373 /// on the lattice, and moving things to overdefined as fast as possible 374 /// makes SCCP converge much faster. 375 /// 376 /// By having a separate worklist, we accomplish this because everything 377 /// possibly overdefined will become overdefined at the soonest possible 378 /// point. 379 SmallVector<Value *, 64> OverdefinedInstWorkList; 380 SmallVector<Value *, 64> InstWorkList; 381 382 // The BasicBlock work list 383 SmallVector<BasicBlock *, 64> BBWorkList; 384 385 /// KnownFeasibleEdges - Entries in this set are edges which have already had 386 /// PHI nodes retriggered. 387 using Edge = std::pair<BasicBlock *, BasicBlock *>; 388 DenseSet<Edge> KnownFeasibleEdges; 389 390 DenseMap<Function *, std::unique_ptr<PredicateInfo>> FnPredicateInfo; 391 392 DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers; 393 394 LLVMContext &Ctx; 395 396 private: 397 ConstantInt *getConstantInt(const ValueLatticeElement &IV, Type *Ty) const { 398 return dyn_cast_or_null<ConstantInt>(getConstant(IV, Ty)); 399 } 400 401 // pushToWorkList - Helper for markConstant/markOverdefined 402 void pushToWorkList(ValueLatticeElement &IV, Value *V); 403 404 // Helper to push \p V to the worklist, after updating it to \p IV. Also 405 // prints a debug message with the updated value. 406 void pushToWorkListMsg(ValueLatticeElement &IV, Value *V); 407 408 // markConstant - Make a value be marked as "constant". If the value 409 // is not already a constant, add it to the instruction work list so that 410 // the users of the instruction are updated later. 411 bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C, 412 bool MayIncludeUndef = false); 413 414 bool markConstant(Value *V, Constant *C) { 415 assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); 416 return markConstant(ValueState[V], V, C); 417 } 418 419 // markOverdefined - Make a value be marked as "overdefined". If the 420 // value is not already overdefined, add it to the overdefined instruction 421 // work list so that the users of the instruction are updated later. 422 bool markOverdefined(ValueLatticeElement &IV, Value *V); 423 424 /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV 425 /// changes. 426 bool mergeInValue(ValueLatticeElement &IV, Value *V, 427 ValueLatticeElement MergeWithV, 428 ValueLatticeElement::MergeOptions Opts = { 429 /*MayIncludeUndef=*/false, /*CheckWiden=*/false}); 430 431 bool mergeInValue(Value *V, ValueLatticeElement MergeWithV, 432 ValueLatticeElement::MergeOptions Opts = { 433 /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) { 434 assert(!V->getType()->isStructTy() && 435 "non-structs should use markConstant"); 436 return mergeInValue(ValueState[V], V, MergeWithV, Opts); 437 } 438 439 /// getValueState - Return the ValueLatticeElement object that corresponds to 440 /// the value. This function handles the case when the value hasn't been seen 441 /// yet by properly seeding constants etc. 442 ValueLatticeElement &getValueState(Value *V) { 443 assert(!V->getType()->isStructTy() && "Should use getStructValueState"); 444 445 auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement())); 446 ValueLatticeElement &LV = I.first->second; 447 448 if (!I.second) 449 return LV; // Common case, already in the map. 450 451 if (auto *C = dyn_cast<Constant>(V)) 452 LV.markConstant(C); // Constants are constant 453 454 // All others are unknown by default. 455 return LV; 456 } 457 458 /// getStructValueState - Return the ValueLatticeElement object that 459 /// corresponds to the value/field pair. This function handles the case when 460 /// the value hasn't been seen yet by properly seeding constants etc. 461 ValueLatticeElement &getStructValueState(Value *V, unsigned i) { 462 assert(V->getType()->isStructTy() && "Should use getValueState"); 463 assert(i < cast<StructType>(V->getType())->getNumElements() && 464 "Invalid element #"); 465 466 auto I = StructValueState.insert( 467 std::make_pair(std::make_pair(V, i), ValueLatticeElement())); 468 ValueLatticeElement &LV = I.first->second; 469 470 if (!I.second) 471 return LV; // Common case, already in the map. 472 473 if (auto *C = dyn_cast<Constant>(V)) { 474 Constant *Elt = C->getAggregateElement(i); 475 476 if (!Elt) 477 LV.markOverdefined(); // Unknown sort of constant. 478 else 479 LV.markConstant(Elt); // Constants are constant. 480 } 481 482 // All others are underdefined by default. 483 return LV; 484 } 485 486 /// Traverse the use-def chain of \p Call, marking itself and its users as 487 /// "unknown" on the way. 488 void invalidate(CallBase *Call) { 489 SmallVector<Instruction *, 64> ToInvalidate; 490 ToInvalidate.push_back(Call); 491 492 while (!ToInvalidate.empty()) { 493 Instruction *Inst = ToInvalidate.pop_back_val(); 494 495 if (!Invalidated.insert(Inst).second) 496 continue; 497 498 if (!BBExecutable.count(Inst->getParent())) 499 continue; 500 501 Value *V = nullptr; 502 // For return instructions we need to invalidate the tracked returns map. 503 // Anything else has its lattice in the value map. 504 if (auto *RetInst = dyn_cast<ReturnInst>(Inst)) { 505 Function *F = RetInst->getParent()->getParent(); 506 if (auto It = TrackedRetVals.find(F); It != TrackedRetVals.end()) { 507 It->second = ValueLatticeElement(); 508 V = F; 509 } else if (MRVFunctionsTracked.count(F)) { 510 auto *STy = cast<StructType>(F->getReturnType()); 511 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) 512 TrackedMultipleRetVals[{F, I}] = ValueLatticeElement(); 513 V = F; 514 } 515 } else if (auto *STy = dyn_cast<StructType>(Inst->getType())) { 516 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) { 517 if (auto It = StructValueState.find({Inst, I}); 518 It != StructValueState.end()) { 519 It->second = ValueLatticeElement(); 520 V = Inst; 521 } 522 } 523 } else if (auto It = ValueState.find(Inst); It != ValueState.end()) { 524 It->second = ValueLatticeElement(); 525 V = Inst; 526 } 527 528 if (V) { 529 LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n"); 530 531 for (User *U : V->users()) 532 if (auto *UI = dyn_cast<Instruction>(U)) 533 ToInvalidate.push_back(UI); 534 535 auto It = AdditionalUsers.find(V); 536 if (It != AdditionalUsers.end()) 537 for (User *U : It->second) 538 if (auto *UI = dyn_cast<Instruction>(U)) 539 ToInvalidate.push_back(UI); 540 } 541 } 542 } 543 544 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 545 /// work list if it is not already executable. 546 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest); 547 548 // getFeasibleSuccessors - Return a vector of booleans to indicate which 549 // successors are reachable from a given terminator instruction. 550 void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs); 551 552 // OperandChangedState - This method is invoked on all of the users of an 553 // instruction that was just changed state somehow. Based on this 554 // information, we need to update the specified user of this instruction. 555 void operandChangedState(Instruction *I) { 556 if (BBExecutable.count(I->getParent())) // Inst is executable? 557 visit(*I); 558 } 559 560 // Add U as additional user of V. 561 void addAdditionalUser(Value *V, User *U) { 562 auto Iter = AdditionalUsers.insert({V, {}}); 563 Iter.first->second.insert(U); 564 } 565 566 // Mark I's users as changed, including AdditionalUsers. 567 void markUsersAsChanged(Value *I) { 568 // Functions include their arguments in the use-list. Changed function 569 // values mean that the result of the function changed. We only need to 570 // update the call sites with the new function result and do not have to 571 // propagate the call arguments. 572 if (isa<Function>(I)) { 573 for (User *U : I->users()) { 574 if (auto *CB = dyn_cast<CallBase>(U)) 575 handleCallResult(*CB); 576 } 577 } else { 578 for (User *U : I->users()) 579 if (auto *UI = dyn_cast<Instruction>(U)) 580 operandChangedState(UI); 581 } 582 583 auto Iter = AdditionalUsers.find(I); 584 if (Iter != AdditionalUsers.end()) { 585 // Copy additional users before notifying them of changes, because new 586 // users may be added, potentially invalidating the iterator. 587 SmallVector<Instruction *, 2> ToNotify; 588 for (User *U : Iter->second) 589 if (auto *UI = dyn_cast<Instruction>(U)) 590 ToNotify.push_back(UI); 591 for (Instruction *UI : ToNotify) 592 operandChangedState(UI); 593 } 594 } 595 void handleCallOverdefined(CallBase &CB); 596 void handleCallResult(CallBase &CB); 597 void handleCallArguments(CallBase &CB); 598 void handleExtractOfWithOverflow(ExtractValueInst &EVI, 599 const WithOverflowInst *WO, unsigned Idx); 600 601 private: 602 friend class InstVisitor<SCCPInstVisitor>; 603 604 // visit implementations - Something changed in this instruction. Either an 605 // operand made a transition, or the instruction is newly executable. Change 606 // the value type of I to reflect these changes if appropriate. 607 void visitPHINode(PHINode &I); 608 609 // Terminators 610 611 void visitReturnInst(ReturnInst &I); 612 void visitTerminator(Instruction &TI); 613 614 void visitCastInst(CastInst &I); 615 void visitSelectInst(SelectInst &I); 616 void visitUnaryOperator(Instruction &I); 617 void visitFreezeInst(FreezeInst &I); 618 void visitBinaryOperator(Instruction &I); 619 void visitCmpInst(CmpInst &I); 620 void visitExtractValueInst(ExtractValueInst &EVI); 621 void visitInsertValueInst(InsertValueInst &IVI); 622 623 void visitCatchSwitchInst(CatchSwitchInst &CPI) { 624 markOverdefined(&CPI); 625 visitTerminator(CPI); 626 } 627 628 // Instructions that cannot be folded away. 629 630 void visitStoreInst(StoreInst &I); 631 void visitLoadInst(LoadInst &I); 632 void visitGetElementPtrInst(GetElementPtrInst &I); 633 634 void visitInvokeInst(InvokeInst &II) { 635 visitCallBase(II); 636 visitTerminator(II); 637 } 638 639 void visitCallBrInst(CallBrInst &CBI) { 640 visitCallBase(CBI); 641 visitTerminator(CBI); 642 } 643 644 void visitCallBase(CallBase &CB); 645 void visitResumeInst(ResumeInst &I) { /*returns void*/ 646 } 647 void visitUnreachableInst(UnreachableInst &I) { /*returns void*/ 648 } 649 void visitFenceInst(FenceInst &I) { /*returns void*/ 650 } 651 652 void visitInstruction(Instruction &I); 653 654 public: 655 void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC) { 656 FnPredicateInfo.insert({&F, std::make_unique<PredicateInfo>(F, DT, AC)}); 657 } 658 659 void visitCallInst(CallInst &I) { visitCallBase(I); } 660 661 bool markBlockExecutable(BasicBlock *BB); 662 663 const PredicateBase *getPredicateInfoFor(Instruction *I) { 664 auto It = FnPredicateInfo.find(I->getParent()->getParent()); 665 if (It == FnPredicateInfo.end()) 666 return nullptr; 667 return It->second->getPredicateInfoFor(I); 668 } 669 670 SCCPInstVisitor(const DataLayout &DL, 671 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 672 LLVMContext &Ctx) 673 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {} 674 675 void trackValueOfGlobalVariable(GlobalVariable *GV) { 676 // We only track the contents of scalar globals. 677 if (GV->getValueType()->isSingleValueType()) { 678 ValueLatticeElement &IV = TrackedGlobals[GV]; 679 IV.markConstant(GV->getInitializer()); 680 } 681 } 682 683 void addTrackedFunction(Function *F) { 684 // Add an entry, F -> undef. 685 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) { 686 MRVFunctionsTracked.insert(F); 687 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 688 TrackedMultipleRetVals.insert( 689 std::make_pair(std::make_pair(F, i), ValueLatticeElement())); 690 } else if (!F->getReturnType()->isVoidTy()) 691 TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement())); 692 } 693 694 void addToMustPreserveReturnsInFunctions(Function *F) { 695 MustPreserveReturnsInFunctions.insert(F); 696 } 697 698 bool mustPreserveReturn(Function *F) { 699 return MustPreserveReturnsInFunctions.count(F); 700 } 701 702 void addArgumentTrackedFunction(Function *F) { 703 TrackingIncomingArguments.insert(F); 704 } 705 706 bool isArgumentTrackedFunction(Function *F) { 707 return TrackingIncomingArguments.count(F); 708 } 709 710 void solve(); 711 712 bool resolvedUndef(Instruction &I); 713 714 bool resolvedUndefsIn(Function &F); 715 716 bool isBlockExecutable(BasicBlock *BB) const { 717 return BBExecutable.count(BB); 718 } 719 720 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; 721 722 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const { 723 std::vector<ValueLatticeElement> StructValues; 724 auto *STy = dyn_cast<StructType>(V->getType()); 725 assert(STy && "getStructLatticeValueFor() can be called only on structs"); 726 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 727 auto I = StructValueState.find(std::make_pair(V, i)); 728 assert(I != StructValueState.end() && "Value not in valuemap!"); 729 StructValues.push_back(I->second); 730 } 731 return StructValues; 732 } 733 734 void removeLatticeValueFor(Value *V) { ValueState.erase(V); } 735 736 /// Invalidate the Lattice Value of \p Call and its users after specializing 737 /// the call. Then recompute it. 738 void resetLatticeValueFor(CallBase *Call) { 739 // Calls to void returning functions do not need invalidation. 740 Function *F = Call->getCalledFunction(); 741 (void)F; 742 assert(!F->getReturnType()->isVoidTy() && 743 (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) && 744 "All non void specializations should be tracked"); 745 invalidate(Call); 746 handleCallResult(*Call); 747 } 748 749 const ValueLatticeElement &getLatticeValueFor(Value *V) const { 750 assert(!V->getType()->isStructTy() && 751 "Should use getStructLatticeValueFor"); 752 DenseMap<Value *, ValueLatticeElement>::const_iterator I = 753 ValueState.find(V); 754 assert(I != ValueState.end() && 755 "V not found in ValueState nor Paramstate map!"); 756 return I->second; 757 } 758 759 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() { 760 return TrackedRetVals; 761 } 762 763 const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals() { 764 return TrackedGlobals; 765 } 766 767 const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() { 768 return MRVFunctionsTracked; 769 } 770 771 void markOverdefined(Value *V) { 772 if (auto *STy = dyn_cast<StructType>(V->getType())) 773 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 774 markOverdefined(getStructValueState(V, i), V); 775 else 776 markOverdefined(ValueState[V], V); 777 } 778 779 bool isStructLatticeConstant(Function *F, StructType *STy); 780 781 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const; 782 783 Constant *getConstantOrNull(Value *V) const; 784 785 SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() { 786 return TrackingIncomingArguments; 787 } 788 789 void setLatticeValueForSpecializationArguments(Function *F, 790 const SmallVectorImpl<ArgInfo> &Args); 791 792 void markFunctionUnreachable(Function *F) { 793 for (auto &BB : *F) 794 BBExecutable.erase(&BB); 795 } 796 797 void solveWhileResolvedUndefsIn(Module &M) { 798 bool ResolvedUndefs = true; 799 while (ResolvedUndefs) { 800 solve(); 801 ResolvedUndefs = false; 802 for (Function &F : M) 803 ResolvedUndefs |= resolvedUndefsIn(F); 804 } 805 } 806 807 void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) { 808 bool ResolvedUndefs = true; 809 while (ResolvedUndefs) { 810 solve(); 811 ResolvedUndefs = false; 812 for (Function *F : WorkList) 813 ResolvedUndefs |= resolvedUndefsIn(*F); 814 } 815 } 816 817 void solveWhileResolvedUndefs() { 818 bool ResolvedUndefs = true; 819 while (ResolvedUndefs) { 820 solve(); 821 ResolvedUndefs = false; 822 for (Value *V : Invalidated) 823 if (auto *I = dyn_cast<Instruction>(V)) 824 ResolvedUndefs |= resolvedUndef(*I); 825 } 826 Invalidated.clear(); 827 } 828 }; 829 830 } // namespace llvm 831 832 bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) { 833 if (!BBExecutable.insert(BB).second) 834 return false; 835 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); 836 BBWorkList.push_back(BB); // Add the block to the work list! 837 return true; 838 } 839 840 void SCCPInstVisitor::pushToWorkList(ValueLatticeElement &IV, Value *V) { 841 if (IV.isOverdefined()) { 842 if (OverdefinedInstWorkList.empty() || OverdefinedInstWorkList.back() != V) 843 OverdefinedInstWorkList.push_back(V); 844 return; 845 } 846 if (InstWorkList.empty() || InstWorkList.back() != V) 847 InstWorkList.push_back(V); 848 } 849 850 void SCCPInstVisitor::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) { 851 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n'); 852 pushToWorkList(IV, V); 853 } 854 855 bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V, 856 Constant *C, bool MayIncludeUndef) { 857 if (!IV.markConstant(C, MayIncludeUndef)) 858 return false; 859 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); 860 pushToWorkList(IV, V); 861 return true; 862 } 863 864 bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) { 865 if (!IV.markOverdefined()) 866 return false; 867 868 LLVM_DEBUG(dbgs() << "markOverdefined: "; 869 if (auto *F = dyn_cast<Function>(V)) dbgs() 870 << "Function '" << F->getName() << "'\n"; 871 else dbgs() << *V << '\n'); 872 // Only instructions go on the work list 873 pushToWorkList(IV, V); 874 return true; 875 } 876 877 bool SCCPInstVisitor::isStructLatticeConstant(Function *F, StructType *STy) { 878 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 879 const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i)); 880 assert(It != TrackedMultipleRetVals.end()); 881 ValueLatticeElement LV = It->second; 882 if (!SCCPSolver::isConstant(LV)) 883 return false; 884 } 885 return true; 886 } 887 888 Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV, 889 Type *Ty) const { 890 if (LV.isConstant()) { 891 Constant *C = LV.getConstant(); 892 assert(C->getType() == Ty && "Type mismatch"); 893 return C; 894 } 895 896 if (LV.isConstantRange()) { 897 const auto &CR = LV.getConstantRange(); 898 if (CR.getSingleElement()) 899 return ConstantInt::get(Ty, *CR.getSingleElement()); 900 } 901 return nullptr; 902 } 903 904 Constant *SCCPInstVisitor::getConstantOrNull(Value *V) const { 905 Constant *Const = nullptr; 906 if (V->getType()->isStructTy()) { 907 std::vector<ValueLatticeElement> LVs = getStructLatticeValueFor(V); 908 if (any_of(LVs, SCCPSolver::isOverdefined)) 909 return nullptr; 910 std::vector<Constant *> ConstVals; 911 auto *ST = cast<StructType>(V->getType()); 912 for (unsigned I = 0, E = ST->getNumElements(); I != E; ++I) { 913 ValueLatticeElement LV = LVs[I]; 914 ConstVals.push_back(SCCPSolver::isConstant(LV) 915 ? getConstant(LV, ST->getElementType(I)) 916 : UndefValue::get(ST->getElementType(I))); 917 } 918 Const = ConstantStruct::get(ST, ConstVals); 919 } else { 920 const ValueLatticeElement &LV = getLatticeValueFor(V); 921 if (SCCPSolver::isOverdefined(LV)) 922 return nullptr; 923 Const = SCCPSolver::isConstant(LV) ? getConstant(LV, V->getType()) 924 : UndefValue::get(V->getType()); 925 } 926 assert(Const && "Constant is nullptr here!"); 927 return Const; 928 } 929 930 void SCCPInstVisitor::setLatticeValueForSpecializationArguments(Function *F, 931 const SmallVectorImpl<ArgInfo> &Args) { 932 assert(!Args.empty() && "Specialization without arguments"); 933 assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() && 934 "Functions should have the same number of arguments"); 935 936 auto Iter = Args.begin(); 937 Function::arg_iterator NewArg = F->arg_begin(); 938 Function::arg_iterator OldArg = Args[0].Formal->getParent()->arg_begin(); 939 for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) { 940 941 LLVM_DEBUG(dbgs() << "SCCP: Marking argument " 942 << NewArg->getNameOrAsOperand() << "\n"); 943 944 // Mark the argument constants in the new function 945 // or copy the lattice state over from the old function. 946 if (Iter != Args.end() && Iter->Formal == &*OldArg) { 947 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) { 948 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) { 949 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}]; 950 NewValue.markConstant(Iter->Actual->getAggregateElement(I)); 951 } 952 } else { 953 ValueState[&*NewArg].markConstant(Iter->Actual); 954 } 955 ++Iter; 956 } else { 957 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) { 958 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) { 959 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}]; 960 NewValue = StructValueState[{&*OldArg, I}]; 961 } 962 } else { 963 ValueLatticeElement &NewValue = ValueState[&*NewArg]; 964 NewValue = ValueState[&*OldArg]; 965 } 966 } 967 } 968 } 969 970 void SCCPInstVisitor::visitInstruction(Instruction &I) { 971 // All the instructions we don't do any special handling for just 972 // go to overdefined. 973 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n'); 974 markOverdefined(&I); 975 } 976 977 bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V, 978 ValueLatticeElement MergeWithV, 979 ValueLatticeElement::MergeOptions Opts) { 980 if (IV.mergeIn(MergeWithV, Opts)) { 981 pushToWorkList(IV, V); 982 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : " 983 << IV << "\n"); 984 return true; 985 } 986 return false; 987 } 988 989 bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 990 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 991 return false; // This edge is already known to be executable! 992 993 if (!markBlockExecutable(Dest)) { 994 // If the destination is already executable, we just made an *edge* 995 // feasible that wasn't before. Revisit the PHI nodes in the block 996 // because they have potentially new operands. 997 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() 998 << " -> " << Dest->getName() << '\n'); 999 1000 for (PHINode &PN : Dest->phis()) 1001 visitPHINode(PN); 1002 } 1003 return true; 1004 } 1005 1006 // getFeasibleSuccessors - Return a vector of booleans to indicate which 1007 // successors are reachable from a given terminator instruction. 1008 void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI, 1009 SmallVectorImpl<bool> &Succs) { 1010 Succs.resize(TI.getNumSuccessors()); 1011 if (auto *BI = dyn_cast<BranchInst>(&TI)) { 1012 if (BI->isUnconditional()) { 1013 Succs[0] = true; 1014 return; 1015 } 1016 1017 ValueLatticeElement BCValue = getValueState(BI->getCondition()); 1018 ConstantInt *CI = getConstantInt(BCValue, BI->getCondition()->getType()); 1019 if (!CI) { 1020 // Overdefined condition variables, and branches on unfoldable constant 1021 // conditions, mean the branch could go either way. 1022 if (!BCValue.isUnknownOrUndef()) 1023 Succs[0] = Succs[1] = true; 1024 return; 1025 } 1026 1027 // Constant condition variables mean the branch can only go a single way. 1028 Succs[CI->isZero()] = true; 1029 return; 1030 } 1031 1032 // Unwinding instructions successors are always executable. 1033 if (TI.isExceptionalTerminator()) { 1034 Succs.assign(TI.getNumSuccessors(), true); 1035 return; 1036 } 1037 1038 if (auto *SI = dyn_cast<SwitchInst>(&TI)) { 1039 if (!SI->getNumCases()) { 1040 Succs[0] = true; 1041 return; 1042 } 1043 const ValueLatticeElement &SCValue = getValueState(SI->getCondition()); 1044 if (ConstantInt *CI = 1045 getConstantInt(SCValue, SI->getCondition()->getType())) { 1046 Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true; 1047 return; 1048 } 1049 1050 // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM 1051 // is ready. 1052 if (SCValue.isConstantRange(/*UndefAllowed=*/false)) { 1053 const ConstantRange &Range = SCValue.getConstantRange(); 1054 for (const auto &Case : SI->cases()) { 1055 const APInt &CaseValue = Case.getCaseValue()->getValue(); 1056 if (Range.contains(CaseValue)) 1057 Succs[Case.getSuccessorIndex()] = true; 1058 } 1059 1060 // TODO: Determine whether default case is reachable. 1061 Succs[SI->case_default()->getSuccessorIndex()] = true; 1062 return; 1063 } 1064 1065 // Overdefined or unknown condition? All destinations are executable! 1066 if (!SCValue.isUnknownOrUndef()) 1067 Succs.assign(TI.getNumSuccessors(), true); 1068 return; 1069 } 1070 1071 // In case of indirect branch and its address is a blockaddress, we mark 1072 // the target as executable. 1073 if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) { 1074 // Casts are folded by visitCastInst. 1075 ValueLatticeElement IBRValue = getValueState(IBR->getAddress()); 1076 BlockAddress *Addr = dyn_cast_or_null<BlockAddress>( 1077 getConstant(IBRValue, IBR->getAddress()->getType())); 1078 if (!Addr) { // Overdefined or unknown condition? 1079 // All destinations are executable! 1080 if (!IBRValue.isUnknownOrUndef()) 1081 Succs.assign(TI.getNumSuccessors(), true); 1082 return; 1083 } 1084 1085 BasicBlock *T = Addr->getBasicBlock(); 1086 assert(Addr->getFunction() == T->getParent() && 1087 "Block address of a different function ?"); 1088 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) { 1089 // This is the target. 1090 if (IBR->getDestination(i) == T) { 1091 Succs[i] = true; 1092 return; 1093 } 1094 } 1095 1096 // If we didn't find our destination in the IBR successor list, then we 1097 // have undefined behavior. Its ok to assume no successor is executable. 1098 return; 1099 } 1100 1101 // In case of callbr, we pessimistically assume that all successors are 1102 // feasible. 1103 if (isa<CallBrInst>(&TI)) { 1104 Succs.assign(TI.getNumSuccessors(), true); 1105 return; 1106 } 1107 1108 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n'); 1109 llvm_unreachable("SCCP: Don't know how to handle this terminator!"); 1110 } 1111 1112 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 1113 // block to the 'To' basic block is currently feasible. 1114 bool SCCPInstVisitor::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const { 1115 // Check if we've called markEdgeExecutable on the edge yet. (We could 1116 // be more aggressive and try to consider edges which haven't been marked 1117 // yet, but there isn't any need.) 1118 return KnownFeasibleEdges.count(Edge(From, To)); 1119 } 1120 1121 // visit Implementations - Something changed in this instruction, either an 1122 // operand made a transition, or the instruction is newly executable. Change 1123 // the value type of I to reflect these changes if appropriate. This method 1124 // makes sure to do the following actions: 1125 // 1126 // 1. If a phi node merges two constants in, and has conflicting value coming 1127 // from different branches, or if the PHI node merges in an overdefined 1128 // value, then the PHI node becomes overdefined. 1129 // 2. If a phi node merges only constants in, and they all agree on value, the 1130 // PHI node becomes a constant value equal to that. 1131 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 1132 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 1133 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 1134 // 6. If a conditional branch has a value that is constant, make the selected 1135 // destination executable 1136 // 7. If a conditional branch has a value that is overdefined, make all 1137 // successors executable. 1138 void SCCPInstVisitor::visitPHINode(PHINode &PN) { 1139 // If this PN returns a struct, just mark the result overdefined. 1140 // TODO: We could do a lot better than this if code actually uses this. 1141 if (PN.getType()->isStructTy()) 1142 return (void)markOverdefined(&PN); 1143 1144 if (getValueState(&PN).isOverdefined()) 1145 return; // Quick exit 1146 1147 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 1148 // and slow us down a lot. Just mark them overdefined. 1149 if (PN.getNumIncomingValues() > 64) 1150 return (void)markOverdefined(&PN); 1151 1152 unsigned NumActiveIncoming = 0; 1153 1154 // Look at all of the executable operands of the PHI node. If any of them 1155 // are overdefined, the PHI becomes overdefined as well. If they are all 1156 // constant, and they agree with each other, the PHI becomes the identical 1157 // constant. If they are constant and don't agree, the PHI is a constant 1158 // range. If there are no executable operands, the PHI remains unknown. 1159 ValueLatticeElement PhiState = getValueState(&PN); 1160 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 1161 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) 1162 continue; 1163 1164 ValueLatticeElement IV = getValueState(PN.getIncomingValue(i)); 1165 PhiState.mergeIn(IV); 1166 NumActiveIncoming++; 1167 if (PhiState.isOverdefined()) 1168 break; 1169 } 1170 1171 // We allow up to 1 range extension per active incoming value and one 1172 // additional extension. Note that we manually adjust the number of range 1173 // extensions to match the number of active incoming values. This helps to 1174 // limit multiple extensions caused by the same incoming value, if other 1175 // incoming values are equal. 1176 mergeInValue(&PN, PhiState, 1177 ValueLatticeElement::MergeOptions().setMaxWidenSteps( 1178 NumActiveIncoming + 1)); 1179 ValueLatticeElement &PhiStateRef = getValueState(&PN); 1180 PhiStateRef.setNumRangeExtensions( 1181 std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions())); 1182 } 1183 1184 void SCCPInstVisitor::visitReturnInst(ReturnInst &I) { 1185 if (I.getNumOperands() == 0) 1186 return; // ret void 1187 1188 Function *F = I.getParent()->getParent(); 1189 Value *ResultOp = I.getOperand(0); 1190 1191 // If we are tracking the return value of this function, merge it in. 1192 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) { 1193 auto TFRVI = TrackedRetVals.find(F); 1194 if (TFRVI != TrackedRetVals.end()) { 1195 mergeInValue(TFRVI->second, F, getValueState(ResultOp)); 1196 return; 1197 } 1198 } 1199 1200 // Handle functions that return multiple values. 1201 if (!TrackedMultipleRetVals.empty()) { 1202 if (auto *STy = dyn_cast<StructType>(ResultOp->getType())) 1203 if (MRVFunctionsTracked.count(F)) 1204 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1205 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F, 1206 getStructValueState(ResultOp, i)); 1207 } 1208 } 1209 1210 void SCCPInstVisitor::visitTerminator(Instruction &TI) { 1211 SmallVector<bool, 16> SuccFeasible; 1212 getFeasibleSuccessors(TI, SuccFeasible); 1213 1214 BasicBlock *BB = TI.getParent(); 1215 1216 // Mark all feasible successors executable. 1217 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 1218 if (SuccFeasible[i]) 1219 markEdgeExecutable(BB, TI.getSuccessor(i)); 1220 } 1221 1222 void SCCPInstVisitor::visitCastInst(CastInst &I) { 1223 // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would 1224 // discover a concrete value later. 1225 if (ValueState[&I].isOverdefined()) 1226 return; 1227 1228 ValueLatticeElement OpSt = getValueState(I.getOperand(0)); 1229 if (OpSt.isUnknownOrUndef()) 1230 return; 1231 1232 if (Constant *OpC = getConstant(OpSt, I.getOperand(0)->getType())) { 1233 // Fold the constant as we build. 1234 Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL); 1235 markConstant(&I, C); 1236 } else if (I.getDestTy()->isIntegerTy() && 1237 I.getSrcTy()->isIntOrIntVectorTy()) { 1238 auto &LV = getValueState(&I); 1239 ConstantRange OpRange = getConstantRange(OpSt, I.getSrcTy()); 1240 1241 Type *DestTy = I.getDestTy(); 1242 // Vectors where all elements have the same known constant range are treated 1243 // as a single constant range in the lattice. When bitcasting such vectors, 1244 // there is a mis-match between the width of the lattice value (single 1245 // constant range) and the original operands (vector). Go to overdefined in 1246 // that case. 1247 if (I.getOpcode() == Instruction::BitCast && 1248 I.getOperand(0)->getType()->isVectorTy() && 1249 OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy)) 1250 return (void)markOverdefined(&I); 1251 1252 ConstantRange Res = 1253 OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy)); 1254 mergeInValue(LV, &I, ValueLatticeElement::getRange(Res)); 1255 } else 1256 markOverdefined(&I); 1257 } 1258 1259 void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI, 1260 const WithOverflowInst *WO, 1261 unsigned Idx) { 1262 Value *LHS = WO->getLHS(), *RHS = WO->getRHS(); 1263 ValueLatticeElement L = getValueState(LHS); 1264 ValueLatticeElement R = getValueState(RHS); 1265 addAdditionalUser(LHS, &EVI); 1266 addAdditionalUser(RHS, &EVI); 1267 if (L.isUnknownOrUndef() || R.isUnknownOrUndef()) 1268 return; // Wait to resolve. 1269 1270 Type *Ty = LHS->getType(); 1271 ConstantRange LR = getConstantRange(L, Ty); 1272 ConstantRange RR = getConstantRange(R, Ty); 1273 if (Idx == 0) { 1274 ConstantRange Res = LR.binaryOp(WO->getBinaryOp(), RR); 1275 mergeInValue(&EVI, ValueLatticeElement::getRange(Res)); 1276 } else { 1277 assert(Idx == 1 && "Index can only be 0 or 1"); 1278 ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 1279 WO->getBinaryOp(), RR, WO->getNoWrapKind()); 1280 if (NWRegion.contains(LR)) 1281 return (void)markConstant(&EVI, ConstantInt::getFalse(EVI.getType())); 1282 markOverdefined(&EVI); 1283 } 1284 } 1285 1286 void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) { 1287 // If this returns a struct, mark all elements over defined, we don't track 1288 // structs in structs. 1289 if (EVI.getType()->isStructTy()) 1290 return (void)markOverdefined(&EVI); 1291 1292 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would 1293 // discover a concrete value later. 1294 if (ValueState[&EVI].isOverdefined()) 1295 return (void)markOverdefined(&EVI); 1296 1297 // If this is extracting from more than one level of struct, we don't know. 1298 if (EVI.getNumIndices() != 1) 1299 return (void)markOverdefined(&EVI); 1300 1301 Value *AggVal = EVI.getAggregateOperand(); 1302 if (AggVal->getType()->isStructTy()) { 1303 unsigned i = *EVI.idx_begin(); 1304 if (auto *WO = dyn_cast<WithOverflowInst>(AggVal)) 1305 return handleExtractOfWithOverflow(EVI, WO, i); 1306 ValueLatticeElement EltVal = getStructValueState(AggVal, i); 1307 mergeInValue(getValueState(&EVI), &EVI, EltVal); 1308 } else { 1309 // Otherwise, must be extracting from an array. 1310 return (void)markOverdefined(&EVI); 1311 } 1312 } 1313 1314 void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) { 1315 auto *STy = dyn_cast<StructType>(IVI.getType()); 1316 if (!STy) 1317 return (void)markOverdefined(&IVI); 1318 1319 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would 1320 // discover a concrete value later. 1321 if (SCCPSolver::isOverdefined(ValueState[&IVI])) 1322 return (void)markOverdefined(&IVI); 1323 1324 // If this has more than one index, we can't handle it, drive all results to 1325 // undef. 1326 if (IVI.getNumIndices() != 1) 1327 return (void)markOverdefined(&IVI); 1328 1329 Value *Aggr = IVI.getAggregateOperand(); 1330 unsigned Idx = *IVI.idx_begin(); 1331 1332 // Compute the result based on what we're inserting. 1333 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1334 // This passes through all values that aren't the inserted element. 1335 if (i != Idx) { 1336 ValueLatticeElement EltVal = getStructValueState(Aggr, i); 1337 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal); 1338 continue; 1339 } 1340 1341 Value *Val = IVI.getInsertedValueOperand(); 1342 if (Val->getType()->isStructTy()) 1343 // We don't track structs in structs. 1344 markOverdefined(getStructValueState(&IVI, i), &IVI); 1345 else { 1346 ValueLatticeElement InVal = getValueState(Val); 1347 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal); 1348 } 1349 } 1350 } 1351 1352 void SCCPInstVisitor::visitSelectInst(SelectInst &I) { 1353 // If this select returns a struct, just mark the result overdefined. 1354 // TODO: We could do a lot better than this if code actually uses this. 1355 if (I.getType()->isStructTy()) 1356 return (void)markOverdefined(&I); 1357 1358 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would 1359 // discover a concrete value later. 1360 if (ValueState[&I].isOverdefined()) 1361 return (void)markOverdefined(&I); 1362 1363 ValueLatticeElement CondValue = getValueState(I.getCondition()); 1364 if (CondValue.isUnknownOrUndef()) 1365 return; 1366 1367 if (ConstantInt *CondCB = 1368 getConstantInt(CondValue, I.getCondition()->getType())) { 1369 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue(); 1370 mergeInValue(&I, getValueState(OpVal)); 1371 return; 1372 } 1373 1374 // Otherwise, the condition is overdefined or a constant we can't evaluate. 1375 // See if we can produce something better than overdefined based on the T/F 1376 // value. 1377 ValueLatticeElement TVal = getValueState(I.getTrueValue()); 1378 ValueLatticeElement FVal = getValueState(I.getFalseValue()); 1379 1380 bool Changed = ValueState[&I].mergeIn(TVal); 1381 Changed |= ValueState[&I].mergeIn(FVal); 1382 if (Changed) 1383 pushToWorkListMsg(ValueState[&I], &I); 1384 } 1385 1386 // Handle Unary Operators. 1387 void SCCPInstVisitor::visitUnaryOperator(Instruction &I) { 1388 ValueLatticeElement V0State = getValueState(I.getOperand(0)); 1389 1390 ValueLatticeElement &IV = ValueState[&I]; 1391 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would 1392 // discover a concrete value later. 1393 if (SCCPSolver::isOverdefined(IV)) 1394 return (void)markOverdefined(&I); 1395 1396 // If something is unknown/undef, wait for it to resolve. 1397 if (V0State.isUnknownOrUndef()) 1398 return; 1399 1400 if (SCCPSolver::isConstant(V0State)) 1401 if (Constant *C = ConstantFoldUnaryOpOperand( 1402 I.getOpcode(), getConstant(V0State, I.getType()), DL)) 1403 return (void)markConstant(IV, &I, C); 1404 1405 markOverdefined(&I); 1406 } 1407 1408 void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) { 1409 // If this freeze returns a struct, just mark the result overdefined. 1410 // TODO: We could do a lot better than this. 1411 if (I.getType()->isStructTy()) 1412 return (void)markOverdefined(&I); 1413 1414 ValueLatticeElement V0State = getValueState(I.getOperand(0)); 1415 ValueLatticeElement &IV = ValueState[&I]; 1416 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would 1417 // discover a concrete value later. 1418 if (SCCPSolver::isOverdefined(IV)) 1419 return (void)markOverdefined(&I); 1420 1421 // If something is unknown/undef, wait for it to resolve. 1422 if (V0State.isUnknownOrUndef()) 1423 return; 1424 1425 if (SCCPSolver::isConstant(V0State) && 1426 isGuaranteedNotToBeUndefOrPoison(getConstant(V0State, I.getType()))) 1427 return (void)markConstant(IV, &I, getConstant(V0State, I.getType())); 1428 1429 markOverdefined(&I); 1430 } 1431 1432 // Handle Binary Operators. 1433 void SCCPInstVisitor::visitBinaryOperator(Instruction &I) { 1434 ValueLatticeElement V1State = getValueState(I.getOperand(0)); 1435 ValueLatticeElement V2State = getValueState(I.getOperand(1)); 1436 1437 ValueLatticeElement &IV = ValueState[&I]; 1438 if (IV.isOverdefined()) 1439 return; 1440 1441 // If something is undef, wait for it to resolve. 1442 if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) 1443 return; 1444 1445 if (V1State.isOverdefined() && V2State.isOverdefined()) 1446 return (void)markOverdefined(&I); 1447 1448 // If either of the operands is a constant, try to fold it to a constant. 1449 // TODO: Use information from notconstant better. 1450 if ((V1State.isConstant() || V2State.isConstant())) { 1451 Value *V1 = SCCPSolver::isConstant(V1State) 1452 ? getConstant(V1State, I.getOperand(0)->getType()) 1453 : I.getOperand(0); 1454 Value *V2 = SCCPSolver::isConstant(V2State) 1455 ? getConstant(V2State, I.getOperand(1)->getType()) 1456 : I.getOperand(1); 1457 Value *R = simplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL)); 1458 auto *C = dyn_cast_or_null<Constant>(R); 1459 if (C) { 1460 // Conservatively assume that the result may be based on operands that may 1461 // be undef. Note that we use mergeInValue to combine the constant with 1462 // the existing lattice value for I, as different constants might be found 1463 // after one of the operands go to overdefined, e.g. due to one operand 1464 // being a special floating value. 1465 ValueLatticeElement NewV; 1466 NewV.markConstant(C, /*MayIncludeUndef=*/true); 1467 return (void)mergeInValue(&I, NewV); 1468 } 1469 } 1470 1471 // Only use ranges for binary operators on integers. 1472 if (!I.getType()->isIntegerTy()) 1473 return markOverdefined(&I); 1474 1475 // Try to simplify to a constant range. 1476 ConstantRange A = getConstantRange(V1State, I.getType()); 1477 ConstantRange B = getConstantRange(V2State, I.getType()); 1478 ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B); 1479 mergeInValue(&I, ValueLatticeElement::getRange(R)); 1480 1481 // TODO: Currently we do not exploit special values that produce something 1482 // better than overdefined with an overdefined operand for vector or floating 1483 // point types, like and <4 x i32> overdefined, zeroinitializer. 1484 } 1485 1486 // Handle ICmpInst instruction. 1487 void SCCPInstVisitor::visitCmpInst(CmpInst &I) { 1488 // Do not cache this lookup, getValueState calls later in the function might 1489 // invalidate the reference. 1490 if (SCCPSolver::isOverdefined(ValueState[&I])) 1491 return (void)markOverdefined(&I); 1492 1493 Value *Op1 = I.getOperand(0); 1494 Value *Op2 = I.getOperand(1); 1495 1496 // For parameters, use ParamState which includes constant range info if 1497 // available. 1498 auto V1State = getValueState(Op1); 1499 auto V2State = getValueState(Op2); 1500 1501 Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State, DL); 1502 if (C) { 1503 ValueLatticeElement CV; 1504 CV.markConstant(C); 1505 mergeInValue(&I, CV); 1506 return; 1507 } 1508 1509 // If operands are still unknown, wait for it to resolve. 1510 if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) && 1511 !SCCPSolver::isConstant(ValueState[&I])) 1512 return; 1513 1514 markOverdefined(&I); 1515 } 1516 1517 // Handle getelementptr instructions. If all operands are constants then we 1518 // can turn this into a getelementptr ConstantExpr. 1519 void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) { 1520 if (SCCPSolver::isOverdefined(ValueState[&I])) 1521 return (void)markOverdefined(&I); 1522 1523 SmallVector<Constant *, 8> Operands; 1524 Operands.reserve(I.getNumOperands()); 1525 1526 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 1527 ValueLatticeElement State = getValueState(I.getOperand(i)); 1528 if (State.isUnknownOrUndef()) 1529 return; // Operands are not resolved yet. 1530 1531 if (SCCPSolver::isOverdefined(State)) 1532 return (void)markOverdefined(&I); 1533 1534 if (Constant *C = getConstant(State, I.getOperand(i)->getType())) { 1535 Operands.push_back(C); 1536 continue; 1537 } 1538 1539 return (void)markOverdefined(&I); 1540 } 1541 1542 Constant *Ptr = Operands[0]; 1543 auto Indices = ArrayRef(Operands.begin() + 1, Operands.end()); 1544 Constant *C = 1545 ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices); 1546 markConstant(&I, C); 1547 } 1548 1549 void SCCPInstVisitor::visitStoreInst(StoreInst &SI) { 1550 // If this store is of a struct, ignore it. 1551 if (SI.getOperand(0)->getType()->isStructTy()) 1552 return; 1553 1554 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1))) 1555 return; 1556 1557 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); 1558 auto I = TrackedGlobals.find(GV); 1559 if (I == TrackedGlobals.end()) 1560 return; 1561 1562 // Get the value we are storing into the global, then merge it. 1563 mergeInValue(I->second, GV, getValueState(SI.getOperand(0)), 1564 ValueLatticeElement::MergeOptions().setCheckWiden(false)); 1565 if (I->second.isOverdefined()) 1566 TrackedGlobals.erase(I); // No need to keep tracking this! 1567 } 1568 1569 static ValueLatticeElement getValueFromMetadata(const Instruction *I) { 1570 if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range)) 1571 if (I->getType()->isIntegerTy()) 1572 return ValueLatticeElement::getRange( 1573 getConstantRangeFromMetadata(*Ranges)); 1574 if (I->hasMetadata(LLVMContext::MD_nonnull)) 1575 return ValueLatticeElement::getNot( 1576 ConstantPointerNull::get(cast<PointerType>(I->getType()))); 1577 return ValueLatticeElement::getOverdefined(); 1578 } 1579 1580 // Handle load instructions. If the operand is a constant pointer to a constant 1581 // global, we can replace the load with the loaded constant value! 1582 void SCCPInstVisitor::visitLoadInst(LoadInst &I) { 1583 // If this load is of a struct or the load is volatile, just mark the result 1584 // as overdefined. 1585 if (I.getType()->isStructTy() || I.isVolatile()) 1586 return (void)markOverdefined(&I); 1587 1588 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would 1589 // discover a concrete value later. 1590 if (ValueState[&I].isOverdefined()) 1591 return (void)markOverdefined(&I); 1592 1593 ValueLatticeElement PtrVal = getValueState(I.getOperand(0)); 1594 if (PtrVal.isUnknownOrUndef()) 1595 return; // The pointer is not resolved yet! 1596 1597 ValueLatticeElement &IV = ValueState[&I]; 1598 1599 if (SCCPSolver::isConstant(PtrVal)) { 1600 Constant *Ptr = getConstant(PtrVal, I.getOperand(0)->getType()); 1601 1602 // load null is undefined. 1603 if (isa<ConstantPointerNull>(Ptr)) { 1604 if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace())) 1605 return (void)markOverdefined(IV, &I); 1606 else 1607 return; 1608 } 1609 1610 // Transform load (constant global) into the value loaded. 1611 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) { 1612 if (!TrackedGlobals.empty()) { 1613 // If we are tracking this global, merge in the known value for it. 1614 auto It = TrackedGlobals.find(GV); 1615 if (It != TrackedGlobals.end()) { 1616 mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts()); 1617 return; 1618 } 1619 } 1620 } 1621 1622 // Transform load from a constant into a constant if possible. 1623 if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) 1624 return (void)markConstant(IV, &I, C); 1625 } 1626 1627 // Fall back to metadata. 1628 mergeInValue(&I, getValueFromMetadata(&I)); 1629 } 1630 1631 void SCCPInstVisitor::visitCallBase(CallBase &CB) { 1632 handleCallResult(CB); 1633 handleCallArguments(CB); 1634 } 1635 1636 void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) { 1637 Function *F = CB.getCalledFunction(); 1638 1639 // Void return and not tracking callee, just bail. 1640 if (CB.getType()->isVoidTy()) 1641 return; 1642 1643 // Always mark struct return as overdefined. 1644 if (CB.getType()->isStructTy()) 1645 return (void)markOverdefined(&CB); 1646 1647 // Otherwise, if we have a single return value case, and if the function is 1648 // a declaration, maybe we can constant fold it. 1649 if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) { 1650 SmallVector<Constant *, 8> Operands; 1651 for (const Use &A : CB.args()) { 1652 if (A.get()->getType()->isStructTy()) 1653 return markOverdefined(&CB); // Can't handle struct args. 1654 if (A.get()->getType()->isMetadataTy()) 1655 continue; // Carried in CB, not allowed in Operands. 1656 ValueLatticeElement State = getValueState(A); 1657 1658 if (State.isUnknownOrUndef()) 1659 return; // Operands are not resolved yet. 1660 if (SCCPSolver::isOverdefined(State)) 1661 return (void)markOverdefined(&CB); 1662 assert(SCCPSolver::isConstant(State) && "Unknown state!"); 1663 Operands.push_back(getConstant(State, A->getType())); 1664 } 1665 1666 if (SCCPSolver::isOverdefined(getValueState(&CB))) 1667 return (void)markOverdefined(&CB); 1668 1669 // If we can constant fold this, mark the result of the call as a 1670 // constant. 1671 if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F))) 1672 return (void)markConstant(&CB, C); 1673 } 1674 1675 // Fall back to metadata. 1676 mergeInValue(&CB, getValueFromMetadata(&CB)); 1677 } 1678 1679 void SCCPInstVisitor::handleCallArguments(CallBase &CB) { 1680 Function *F = CB.getCalledFunction(); 1681 // If this is a local function that doesn't have its address taken, mark its 1682 // entry block executable and merge in the actual arguments to the call into 1683 // the formal arguments of the function. 1684 if (TrackingIncomingArguments.count(F)) { 1685 markBlockExecutable(&F->front()); 1686 1687 // Propagate information from this call site into the callee. 1688 auto CAI = CB.arg_begin(); 1689 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; 1690 ++AI, ++CAI) { 1691 // If this argument is byval, and if the function is not readonly, there 1692 // will be an implicit copy formed of the input aggregate. 1693 if (AI->hasByValAttr() && !F->onlyReadsMemory()) { 1694 markOverdefined(&*AI); 1695 continue; 1696 } 1697 1698 if (auto *STy = dyn_cast<StructType>(AI->getType())) { 1699 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1700 ValueLatticeElement CallArg = getStructValueState(*CAI, i); 1701 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg, 1702 getMaxWidenStepsOpts()); 1703 } 1704 } else 1705 mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts()); 1706 } 1707 } 1708 } 1709 1710 void SCCPInstVisitor::handleCallResult(CallBase &CB) { 1711 Function *F = CB.getCalledFunction(); 1712 1713 if (auto *II = dyn_cast<IntrinsicInst>(&CB)) { 1714 if (II->getIntrinsicID() == Intrinsic::ssa_copy) { 1715 if (ValueState[&CB].isOverdefined()) 1716 return; 1717 1718 Value *CopyOf = CB.getOperand(0); 1719 ValueLatticeElement CopyOfVal = getValueState(CopyOf); 1720 const auto *PI = getPredicateInfoFor(&CB); 1721 assert(PI && "Missing predicate info for ssa.copy"); 1722 1723 const std::optional<PredicateConstraint> &Constraint = 1724 PI->getConstraint(); 1725 if (!Constraint) { 1726 mergeInValue(ValueState[&CB], &CB, CopyOfVal); 1727 return; 1728 } 1729 1730 CmpInst::Predicate Pred = Constraint->Predicate; 1731 Value *OtherOp = Constraint->OtherOp; 1732 1733 // Wait until OtherOp is resolved. 1734 if (getValueState(OtherOp).isUnknown()) { 1735 addAdditionalUser(OtherOp, &CB); 1736 return; 1737 } 1738 1739 ValueLatticeElement CondVal = getValueState(OtherOp); 1740 ValueLatticeElement &IV = ValueState[&CB]; 1741 if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) { 1742 auto ImposedCR = 1743 ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType())); 1744 1745 // Get the range imposed by the condition. 1746 if (CondVal.isConstantRange()) 1747 ImposedCR = ConstantRange::makeAllowedICmpRegion( 1748 Pred, CondVal.getConstantRange()); 1749 1750 // Combine range info for the original value with the new range from the 1751 // condition. 1752 auto CopyOfCR = getConstantRange(CopyOfVal, CopyOf->getType()); 1753 auto NewCR = ImposedCR.intersectWith(CopyOfCR); 1754 // If the existing information is != x, do not use the information from 1755 // a chained predicate, as the != x information is more likely to be 1756 // helpful in practice. 1757 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement()) 1758 NewCR = CopyOfCR; 1759 1760 // The new range is based on a branch condition. That guarantees that 1761 // neither of the compare operands can be undef in the branch targets, 1762 // unless we have conditions that are always true/false (e.g. icmp ule 1763 // i32, %a, i32_max). For the latter overdefined/empty range will be 1764 // inferred, but the branch will get folded accordingly anyways. 1765 addAdditionalUser(OtherOp, &CB); 1766 mergeInValue( 1767 IV, &CB, 1768 ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef*/ false)); 1769 return; 1770 } else if (Pred == CmpInst::ICMP_EQ && 1771 (CondVal.isConstant() || CondVal.isNotConstant())) { 1772 // For non-integer values or integer constant expressions, only 1773 // propagate equal constants or not-constants. 1774 addAdditionalUser(OtherOp, &CB); 1775 mergeInValue(IV, &CB, CondVal); 1776 return; 1777 } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) { 1778 // Propagate inequalities. 1779 addAdditionalUser(OtherOp, &CB); 1780 mergeInValue(IV, &CB, 1781 ValueLatticeElement::getNot(CondVal.getConstant())); 1782 return; 1783 } 1784 1785 return (void)mergeInValue(IV, &CB, CopyOfVal); 1786 } 1787 1788 if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) { 1789 // Compute result range for intrinsics supported by ConstantRange. 1790 // Do this even if we don't know a range for all operands, as we may 1791 // still know something about the result range, e.g. of abs(x). 1792 SmallVector<ConstantRange, 2> OpRanges; 1793 for (Value *Op : II->args()) { 1794 const ValueLatticeElement &State = getValueState(Op); 1795 if (State.isUnknownOrUndef()) 1796 return; 1797 OpRanges.push_back(getConstantRange(State, Op->getType())); 1798 } 1799 1800 ConstantRange Result = 1801 ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges); 1802 return (void)mergeInValue(II, ValueLatticeElement::getRange(Result)); 1803 } 1804 } 1805 1806 // The common case is that we aren't tracking the callee, either because we 1807 // are not doing interprocedural analysis or the callee is indirect, or is 1808 // external. Handle these cases first. 1809 if (!F || F->isDeclaration()) 1810 return handleCallOverdefined(CB); 1811 1812 // If this is a single/zero retval case, see if we're tracking the function. 1813 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) { 1814 if (!MRVFunctionsTracked.count(F)) 1815 return handleCallOverdefined(CB); // Not tracking this callee. 1816 1817 // If we are tracking this callee, propagate the result of the function 1818 // into this call site. 1819 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1820 mergeInValue(getStructValueState(&CB, i), &CB, 1821 TrackedMultipleRetVals[std::make_pair(F, i)], 1822 getMaxWidenStepsOpts()); 1823 } else { 1824 auto TFRVI = TrackedRetVals.find(F); 1825 if (TFRVI == TrackedRetVals.end()) 1826 return handleCallOverdefined(CB); // Not tracking this callee. 1827 1828 // If so, propagate the return value of the callee into this call result. 1829 mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts()); 1830 } 1831 } 1832 1833 void SCCPInstVisitor::solve() { 1834 // Process the work lists until they are empty! 1835 while (!BBWorkList.empty() || !InstWorkList.empty() || 1836 !OverdefinedInstWorkList.empty()) { 1837 // Process the overdefined instruction's work list first, which drives other 1838 // things to overdefined more quickly. 1839 while (!OverdefinedInstWorkList.empty()) { 1840 Value *I = OverdefinedInstWorkList.pop_back_val(); 1841 Invalidated.erase(I); 1842 1843 LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n'); 1844 1845 // "I" got into the work list because it either made the transition from 1846 // bottom to constant, or to overdefined. 1847 // 1848 // Anything on this worklist that is overdefined need not be visited 1849 // since all of its users will have already been marked as overdefined 1850 // Update all of the users of this instruction's value. 1851 // 1852 markUsersAsChanged(I); 1853 } 1854 1855 // Process the instruction work list. 1856 while (!InstWorkList.empty()) { 1857 Value *I = InstWorkList.pop_back_val(); 1858 Invalidated.erase(I); 1859 1860 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n'); 1861 1862 // "I" got into the work list because it made the transition from undef to 1863 // constant. 1864 // 1865 // Anything on this worklist that is overdefined need not be visited 1866 // since all of its users will have already been marked as overdefined. 1867 // Update all of the users of this instruction's value. 1868 // 1869 if (I->getType()->isStructTy() || !getValueState(I).isOverdefined()) 1870 markUsersAsChanged(I); 1871 } 1872 1873 // Process the basic block work list. 1874 while (!BBWorkList.empty()) { 1875 BasicBlock *BB = BBWorkList.pop_back_val(); 1876 1877 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n'); 1878 1879 // Notify all instructions in this basic block that they are newly 1880 // executable. 1881 visit(BB); 1882 } 1883 } 1884 } 1885 1886 bool SCCPInstVisitor::resolvedUndef(Instruction &I) { 1887 // Look for instructions which produce undef values. 1888 if (I.getType()->isVoidTy()) 1889 return false; 1890 1891 if (auto *STy = dyn_cast<StructType>(I.getType())) { 1892 // Only a few things that can be structs matter for undef. 1893 1894 // Tracked calls must never be marked overdefined in resolvedUndefsIn. 1895 if (auto *CB = dyn_cast<CallBase>(&I)) 1896 if (Function *F = CB->getCalledFunction()) 1897 if (MRVFunctionsTracked.count(F)) 1898 return false; 1899 1900 // extractvalue and insertvalue don't need to be marked; they are 1901 // tracked as precisely as their operands. 1902 if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I)) 1903 return false; 1904 // Send the results of everything else to overdefined. We could be 1905 // more precise than this but it isn't worth bothering. 1906 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1907 ValueLatticeElement &LV = getStructValueState(&I, i); 1908 if (LV.isUnknown()) { 1909 markOverdefined(LV, &I); 1910 return true; 1911 } 1912 } 1913 return false; 1914 } 1915 1916 ValueLatticeElement &LV = getValueState(&I); 1917 if (!LV.isUnknown()) 1918 return false; 1919 1920 // There are two reasons a call can have an undef result 1921 // 1. It could be tracked. 1922 // 2. It could be constant-foldable. 1923 // Because of the way we solve return values, tracked calls must 1924 // never be marked overdefined in resolvedUndefsIn. 1925 if (auto *CB = dyn_cast<CallBase>(&I)) 1926 if (Function *F = CB->getCalledFunction()) 1927 if (TrackedRetVals.count(F)) 1928 return false; 1929 1930 if (isa<LoadInst>(I)) { 1931 // A load here means one of two things: a load of undef from a global, 1932 // a load from an unknown pointer. Either way, having it return undef 1933 // is okay. 1934 return false; 1935 } 1936 1937 markOverdefined(&I); 1938 return true; 1939 } 1940 1941 /// While solving the dataflow for a function, we don't compute a result for 1942 /// operations with an undef operand, to allow undef to be lowered to a 1943 /// constant later. For example, constant folding of "zext i8 undef to i16" 1944 /// would result in "i16 0", and if undef is later lowered to "i8 1", then the 1945 /// zext result would become "i16 1" and would result into an overdefined 1946 /// lattice value once merged with the previous result. Not computing the 1947 /// result of the zext (treating undef the same as unknown) allows us to handle 1948 /// a later undef->constant lowering more optimally. 1949 /// 1950 /// However, if the operand remains undef when the solver returns, we do need 1951 /// to assign some result to the instruction (otherwise we would treat it as 1952 /// unreachable). For simplicity, we mark any instructions that are still 1953 /// unknown as overdefined. 1954 bool SCCPInstVisitor::resolvedUndefsIn(Function &F) { 1955 bool MadeChange = false; 1956 for (BasicBlock &BB : F) { 1957 if (!BBExecutable.count(&BB)) 1958 continue; 1959 1960 for (Instruction &I : BB) 1961 MadeChange |= resolvedUndef(I); 1962 } 1963 1964 LLVM_DEBUG(if (MadeChange) dbgs() 1965 << "\nResolved undefs in " << F.getName() << '\n'); 1966 1967 return MadeChange; 1968 } 1969 1970 //===----------------------------------------------------------------------===// 1971 // 1972 // SCCPSolver implementations 1973 // 1974 SCCPSolver::SCCPSolver( 1975 const DataLayout &DL, 1976 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 1977 LLVMContext &Ctx) 1978 : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {} 1979 1980 SCCPSolver::~SCCPSolver() = default; 1981 1982 void SCCPSolver::addPredicateInfo(Function &F, DominatorTree &DT, 1983 AssumptionCache &AC) { 1984 Visitor->addPredicateInfo(F, DT, AC); 1985 } 1986 1987 bool SCCPSolver::markBlockExecutable(BasicBlock *BB) { 1988 return Visitor->markBlockExecutable(BB); 1989 } 1990 1991 const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) { 1992 return Visitor->getPredicateInfoFor(I); 1993 } 1994 1995 void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) { 1996 Visitor->trackValueOfGlobalVariable(GV); 1997 } 1998 1999 void SCCPSolver::addTrackedFunction(Function *F) { 2000 Visitor->addTrackedFunction(F); 2001 } 2002 2003 void SCCPSolver::addToMustPreserveReturnsInFunctions(Function *F) { 2004 Visitor->addToMustPreserveReturnsInFunctions(F); 2005 } 2006 2007 bool SCCPSolver::mustPreserveReturn(Function *F) { 2008 return Visitor->mustPreserveReturn(F); 2009 } 2010 2011 void SCCPSolver::addArgumentTrackedFunction(Function *F) { 2012 Visitor->addArgumentTrackedFunction(F); 2013 } 2014 2015 bool SCCPSolver::isArgumentTrackedFunction(Function *F) { 2016 return Visitor->isArgumentTrackedFunction(F); 2017 } 2018 2019 void SCCPSolver::solve() { Visitor->solve(); } 2020 2021 bool SCCPSolver::resolvedUndefsIn(Function &F) { 2022 return Visitor->resolvedUndefsIn(F); 2023 } 2024 2025 void SCCPSolver::solveWhileResolvedUndefsIn(Module &M) { 2026 Visitor->solveWhileResolvedUndefsIn(M); 2027 } 2028 2029 void 2030 SCCPSolver::solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) { 2031 Visitor->solveWhileResolvedUndefsIn(WorkList); 2032 } 2033 2034 void SCCPSolver::solveWhileResolvedUndefs() { 2035 Visitor->solveWhileResolvedUndefs(); 2036 } 2037 2038 bool SCCPSolver::isBlockExecutable(BasicBlock *BB) const { 2039 return Visitor->isBlockExecutable(BB); 2040 } 2041 2042 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const { 2043 return Visitor->isEdgeFeasible(From, To); 2044 } 2045 2046 std::vector<ValueLatticeElement> 2047 SCCPSolver::getStructLatticeValueFor(Value *V) const { 2048 return Visitor->getStructLatticeValueFor(V); 2049 } 2050 2051 void SCCPSolver::removeLatticeValueFor(Value *V) { 2052 return Visitor->removeLatticeValueFor(V); 2053 } 2054 2055 void SCCPSolver::resetLatticeValueFor(CallBase *Call) { 2056 Visitor->resetLatticeValueFor(Call); 2057 } 2058 2059 const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const { 2060 return Visitor->getLatticeValueFor(V); 2061 } 2062 2063 const MapVector<Function *, ValueLatticeElement> & 2064 SCCPSolver::getTrackedRetVals() { 2065 return Visitor->getTrackedRetVals(); 2066 } 2067 2068 const DenseMap<GlobalVariable *, ValueLatticeElement> & 2069 SCCPSolver::getTrackedGlobals() { 2070 return Visitor->getTrackedGlobals(); 2071 } 2072 2073 const SmallPtrSet<Function *, 16> SCCPSolver::getMRVFunctionsTracked() { 2074 return Visitor->getMRVFunctionsTracked(); 2075 } 2076 2077 void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); } 2078 2079 bool SCCPSolver::isStructLatticeConstant(Function *F, StructType *STy) { 2080 return Visitor->isStructLatticeConstant(F, STy); 2081 } 2082 2083 Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV, 2084 Type *Ty) const { 2085 return Visitor->getConstant(LV, Ty); 2086 } 2087 2088 Constant *SCCPSolver::getConstantOrNull(Value *V) const { 2089 return Visitor->getConstantOrNull(V); 2090 } 2091 2092 SmallPtrSetImpl<Function *> &SCCPSolver::getArgumentTrackedFunctions() { 2093 return Visitor->getArgumentTrackedFunctions(); 2094 } 2095 2096 void SCCPSolver::setLatticeValueForSpecializationArguments(Function *F, 2097 const SmallVectorImpl<ArgInfo> &Args) { 2098 Visitor->setLatticeValueForSpecializationArguments(F, Args); 2099 } 2100 2101 void SCCPSolver::markFunctionUnreachable(Function *F) { 2102 Visitor->markFunctionUnreachable(F); 2103 } 2104 2105 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); } 2106 2107 void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); } 2108