2455 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// \file10// This file implements the Sparse Conditional Constant Propagation (SCCP)11// utility.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/Transforms/Utils/SCCPSolver.h"16#include "llvm/ADT/SetVector.h"17#include "llvm/Analysis/ConstantFolding.h"18#include "llvm/Analysis/InstructionSimplify.h"19#include "llvm/Analysis/ValueLattice.h"20#include "llvm/Analysis/ValueLatticeUtils.h"21#include "llvm/Analysis/ValueTracking.h"22#include "llvm/IR/ConstantRange.h"23#include "llvm/IR/DerivedTypes.h"24#include "llvm/IR/IRBuilder.h"25#include "llvm/IR/InstVisitor.h"26#include "llvm/IR/Instructions.h"27#include "llvm/IR/NoFolder.h"28#include "llvm/IR/PatternMatch.h"29#include "llvm/Support/Casting.h"30#include "llvm/Support/Debug.h"31#include "llvm/Support/ErrorHandling.h"32#include "llvm/Support/raw_ostream.h"33#include "llvm/Transforms/Utils/Local.h"34#include <cassert>35#include <utility>36#include <vector>37 38using namespace llvm;39using namespace PatternMatch;40 41#define DEBUG_TYPE "sccp"42 43// The maximum number of range extensions allowed for operations requiring44// widening.45static const unsigned MaxNumRangeExtensions = 10;46 47/// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.48static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() {49 return ValueLatticeElement::MergeOptions().setMaxWidenSteps(50 MaxNumRangeExtensions);51}52 53namespace llvm {54 55bool SCCPSolver::isConstant(const ValueLatticeElement &LV) {56 return LV.isConstant() ||57 (LV.isConstantRange() && LV.getConstantRange().isSingleElement());58}59 60bool SCCPSolver::isOverdefined(const ValueLatticeElement &LV) {61 return !LV.isUnknownOrUndef() && !SCCPSolver::isConstant(LV);62}63 64bool SCCPSolver::tryToReplaceWithConstant(Value *V) {65 Constant *Const = getConstantOrNull(V);66 if (!Const)67 return false;68 // Replacing `musttail` instructions with constant breaks `musttail` invariant69 // unless the call itself can be removed.70 // Calls with "clang.arc.attachedcall" implicitly use the return value and71 // those uses cannot be updated with a constant.72 CallBase *CB = dyn_cast<CallBase>(V);73 if (CB && ((CB->isMustTailCall() && !wouldInstructionBeTriviallyDead(CB)) ||74 CB->getOperandBundle(LLVMContext::OB_clang_arc_attachedcall))) {75 Function *F = CB->getCalledFunction();76 77 // Don't zap returns of the callee78 if (F)79 addToMustPreserveReturnsInFunctions(F);80 81 LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB82 << " as a constant\n");83 return false;84 }85 86 LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');87 88 // Replaces all of the uses of a variable with uses of the constant.89 V->replaceAllUsesWith(Const);90 return true;91}92 93/// Helper for getting ranges from \p Solver. Instructions inserted during94/// simplification are unavailable in the solver, so we return a full range for95/// them.96static ConstantRange getRange(Value *Op, SCCPSolver &Solver,97 const SmallPtrSetImpl<Value *> &InsertedValues) {98 if (auto *Const = dyn_cast<Constant>(Op))99 return Const->toConstantRange();100 if (InsertedValues.contains(Op)) {101 unsigned Bitwidth = Op->getType()->getScalarSizeInBits();102 return ConstantRange::getFull(Bitwidth);103 }104 return Solver.getLatticeValueFor(Op).asConstantRange(Op->getType(),105 /*UndefAllowed=*/false);106}107 108/// Try to use \p Inst's value range from \p Solver to infer the NUW flag.109static bool refineInstruction(SCCPSolver &Solver,110 const SmallPtrSetImpl<Value *> &InsertedValues,111 Instruction &Inst) {112 bool Changed = false;113 auto GetRange = [&Solver, &InsertedValues](Value *Op) {114 return getRange(Op, Solver, InsertedValues);115 };116 117 if (isa<OverflowingBinaryOperator>(Inst)) {118 if (Inst.hasNoSignedWrap() && Inst.hasNoUnsignedWrap())119 return false;120 121 auto RangeA = GetRange(Inst.getOperand(0));122 auto RangeB = GetRange(Inst.getOperand(1));123 if (!Inst.hasNoUnsignedWrap()) {124 auto NUWRange = ConstantRange::makeGuaranteedNoWrapRegion(125 Instruction::BinaryOps(Inst.getOpcode()), RangeB,126 OverflowingBinaryOperator::NoUnsignedWrap);127 if (NUWRange.contains(RangeA)) {128 Inst.setHasNoUnsignedWrap();129 Changed = true;130 }131 }132 if (!Inst.hasNoSignedWrap()) {133 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(134 Instruction::BinaryOps(Inst.getOpcode()), RangeB,135 OverflowingBinaryOperator::NoSignedWrap);136 if (NSWRange.contains(RangeA)) {137 Inst.setHasNoSignedWrap();138 Changed = true;139 }140 }141 } else if (isa<PossiblyNonNegInst>(Inst) && !Inst.hasNonNeg()) {142 auto Range = GetRange(Inst.getOperand(0));143 if (Range.isAllNonNegative()) {144 Inst.setNonNeg();145 Changed = true;146 }147 } else if (TruncInst *TI = dyn_cast<TruncInst>(&Inst)) {148 if (TI->hasNoSignedWrap() && TI->hasNoUnsignedWrap())149 return false;150 151 auto Range = GetRange(Inst.getOperand(0));152 uint64_t DestWidth = TI->getDestTy()->getScalarSizeInBits();153 if (!TI->hasNoUnsignedWrap()) {154 if (Range.getActiveBits() <= DestWidth) {155 TI->setHasNoUnsignedWrap(true);156 Changed = true;157 }158 }159 if (!TI->hasNoSignedWrap()) {160 if (Range.getMinSignedBits() <= DestWidth) {161 TI->setHasNoSignedWrap(true);162 Changed = true;163 }164 }165 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst)) {166 if (GEP->hasNoUnsignedWrap() || !GEP->hasNoUnsignedSignedWrap())167 return false;168 169 if (all_of(GEP->indices(),170 [&](Value *V) { return GetRange(V).isAllNonNegative(); })) {171 GEP->setNoWrapFlags(GEP->getNoWrapFlags() |172 GEPNoWrapFlags::noUnsignedWrap());173 Changed = true;174 }175 }176 177 return Changed;178}179 180/// Try to replace signed instructions with their unsigned equivalent.181static bool replaceSignedInst(SCCPSolver &Solver,182 SmallPtrSetImpl<Value *> &InsertedValues,183 Instruction &Inst) {184 // Determine if a signed value is known to be >= 0.185 auto isNonNegative = [&Solver, &InsertedValues](Value *V) {186 return getRange(V, Solver, InsertedValues).isAllNonNegative();187 };188 189 Instruction *NewInst = nullptr;190 switch (Inst.getOpcode()) {191 case Instruction::SIToFP:192 case Instruction::SExt: {193 // If the source value is not negative, this is a zext/uitofp.194 Value *Op0 = Inst.getOperand(0);195 if (!isNonNegative(Op0))196 return false;197 NewInst = CastInst::Create(Inst.getOpcode() == Instruction::SExt198 ? Instruction::ZExt199 : Instruction::UIToFP,200 Op0, Inst.getType(), "", Inst.getIterator());201 NewInst->setNonNeg();202 break;203 }204 case Instruction::AShr: {205 // If the shifted value is not negative, this is a logical shift right.206 Value *Op0 = Inst.getOperand(0);207 if (!isNonNegative(Op0))208 return false;209 NewInst = BinaryOperator::CreateLShr(Op0, Inst.getOperand(1), "", Inst.getIterator());210 NewInst->setIsExact(Inst.isExact());211 break;212 }213 case Instruction::SDiv:214 case Instruction::SRem: {215 // If both operands are not negative, this is the same as udiv/urem.216 Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1);217 if (!isNonNegative(Op0) || !isNonNegative(Op1))218 return false;219 auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv220 : Instruction::URem;221 NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", Inst.getIterator());222 if (Inst.getOpcode() == Instruction::SDiv)223 NewInst->setIsExact(Inst.isExact());224 break;225 }226 default:227 return false;228 }229 230 // Wire up the new instruction and update state.231 assert(NewInst && "Expected replacement instruction");232 NewInst->takeName(&Inst);233 InsertedValues.insert(NewInst);234 Inst.replaceAllUsesWith(NewInst);235 NewInst->setDebugLoc(Inst.getDebugLoc());236 Solver.removeLatticeValueFor(&Inst);237 Inst.eraseFromParent();238 return true;239}240 241/// Try to use \p Inst's value range from \p Solver to simplify it.242static Value *simplifyInstruction(SCCPSolver &Solver,243 SmallPtrSetImpl<Value *> &InsertedValues,244 Instruction &Inst) {245 auto GetRange = [&Solver, &InsertedValues](Value *Op) {246 return getRange(Op, Solver, InsertedValues);247 };248 249 Value *X;250 const APInt *RHSC;251 // Remove masking operations.252 if (match(&Inst, m_And(m_Value(X), m_LowBitMask(RHSC)))) {253 ConstantRange LRange = GetRange(X);254 if (LRange.getUnsignedMax().ule(*RHSC))255 return X;256 }257 258 // Check if we can simplify [us]cmp(X, Y) to X - Y.259 if (auto *Cmp = dyn_cast<CmpIntrinsic>(&Inst)) {260 Value *LHS = Cmp->getOperand(0);261 Value *RHS = Cmp->getOperand(1);262 unsigned BitWidth = LHS->getType()->getScalarSizeInBits();263 // Bail out on 1-bit comparisons.264 if (BitWidth == 1)265 return nullptr;266 ConstantRange LRange = GetRange(LHS);267 if (LRange.isSizeLargerThan(3))268 return nullptr;269 ConstantRange RRange = GetRange(RHS);270 if (RRange.isSizeLargerThan(3))271 return nullptr;272 ConstantRange RHSLower = RRange.sub(APInt(BitWidth, 1));273 ConstantRange RHSUpper = RRange.add(APInt(BitWidth, 1));274 ICmpInst::Predicate Pred =275 Cmp->isSigned() ? CmpInst::ICMP_SLE : CmpInst::ICMP_ULE;276 if (!RHSLower.icmp(Pred, LRange) || !LRange.icmp(Pred, RHSUpper))277 return nullptr;278 279 IRBuilder<NoFolder> Builder(&Inst);280 Value *Sub = Builder.CreateSub(LHS, RHS, Inst.getName(), /*HasNUW=*/false,281 /*HasNSW=*/Cmp->isSigned());282 InsertedValues.insert(Sub);283 if (Sub->getType() != Inst.getType()) {284 Sub = Builder.CreateSExtOrTrunc(Sub, Inst.getType());285 InsertedValues.insert(Sub);286 }287 return Sub;288 }289 290 // Relax range checks.291 if (auto *ICmp = dyn_cast<ICmpInst>(&Inst)) {292 Value *X;293 auto MatchTwoInstructionExactRangeCheck =294 [&]() -> std::optional<ConstantRange> {295 const APInt *RHSC;296 if (!match(ICmp->getOperand(1), m_APInt(RHSC)))297 return std::nullopt;298 299 Value *LHS = ICmp->getOperand(0);300 ICmpInst::Predicate Pred = ICmp->getPredicate();301 const APInt *Offset;302 if (match(LHS, m_OneUse(m_AddLike(m_Value(X), m_APInt(Offset)))))303 return ConstantRange::makeExactICmpRegion(Pred, *RHSC).sub(*Offset);304 // Match icmp eq/ne X & NegPow2, C305 if (ICmp->isEquality()) {306 const APInt *Mask;307 if (match(LHS, m_OneUse(m_And(m_Value(X), m_NegatedPower2(Mask)))) &&308 RHSC->countr_zero() >= Mask->countr_zero()) {309 ConstantRange CR(*RHSC, *RHSC - *Mask);310 return Pred == ICmpInst::ICMP_EQ ? CR : CR.inverse();311 }312 }313 return std::nullopt;314 };315 316 if (auto CR = MatchTwoInstructionExactRangeCheck()) {317 ConstantRange LRange = GetRange(X);318 // Early exit if we know nothing about X.319 if (LRange.isFullSet())320 return nullptr;321 auto ConvertCRToICmp =322 [&](const std::optional<ConstantRange> &NewCR) -> Value * {323 ICmpInst::Predicate Pred;324 APInt RHS;325 // Check if we can represent NewCR as an icmp predicate.326 if (NewCR && NewCR->getEquivalentICmp(Pred, RHS)) {327 IRBuilder<NoFolder> Builder(&Inst);328 Value *NewICmp =329 Builder.CreateICmp(Pred, X, ConstantInt::get(X->getType(), RHS));330 InsertedValues.insert(NewICmp);331 return NewICmp;332 }333 return nullptr;334 };335 // We are allowed to refine the comparison to either true or false for out336 // of range inputs.337 // Here we refine the comparison to false, and check if we can narrow the338 // range check to a simpler test.339 if (auto *V = ConvertCRToICmp(CR->exactIntersectWith(LRange)))340 return V;341 // Here we refine the comparison to true, i.e. we relax the range check.342 if (auto *V = ConvertCRToICmp(CR->exactUnionWith(LRange.inverse())))343 return V;344 }345 }346 347 return nullptr;348}349 350bool SCCPSolver::simplifyInstsInBlock(BasicBlock &BB,351 SmallPtrSetImpl<Value *> &InsertedValues,352 Statistic &InstRemovedStat,353 Statistic &InstReplacedStat) {354 bool MadeChanges = false;355 for (Instruction &Inst : make_early_inc_range(BB)) {356 if (Inst.getType()->isVoidTy())357 continue;358 if (tryToReplaceWithConstant(&Inst)) {359 if (wouldInstructionBeTriviallyDead(&Inst))360 Inst.eraseFromParent();361 362 MadeChanges = true;363 ++InstRemovedStat;364 } else if (replaceSignedInst(*this, InsertedValues, Inst)) {365 MadeChanges = true;366 ++InstReplacedStat;367 } else if (refineInstruction(*this, InsertedValues, Inst)) {368 MadeChanges = true;369 } else if (auto *V = simplifyInstruction(*this, InsertedValues, Inst)) {370 Inst.replaceAllUsesWith(V);371 Inst.eraseFromParent();372 ++InstRemovedStat;373 MadeChanges = true;374 }375 }376 return MadeChanges;377}378 379bool SCCPSolver::removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,380 BasicBlock *&NewUnreachableBB) const {381 SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;382 bool HasNonFeasibleEdges = false;383 for (BasicBlock *Succ : successors(BB)) {384 if (isEdgeFeasible(BB, Succ))385 FeasibleSuccessors.insert(Succ);386 else387 HasNonFeasibleEdges = true;388 }389 390 // All edges feasible, nothing to do.391 if (!HasNonFeasibleEdges)392 return false;393 394 // SCCP can only determine non-feasible edges for br, switch and indirectbr.395 Instruction *TI = BB->getTerminator();396 assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||397 isa<IndirectBrInst>(TI)) &&398 "Terminator must be a br, switch or indirectbr");399 400 if (FeasibleSuccessors.size() == 0) {401 // Branch on undef/poison, replace with unreachable.402 SmallPtrSet<BasicBlock *, 8> SeenSuccs;403 SmallVector<DominatorTree::UpdateType, 8> Updates;404 for (BasicBlock *Succ : successors(BB)) {405 Succ->removePredecessor(BB);406 if (SeenSuccs.insert(Succ).second)407 Updates.push_back({DominatorTree::Delete, BB, Succ});408 }409 TI->eraseFromParent();410 new UnreachableInst(BB->getContext(), BB);411 DTU.applyUpdatesPermissive(Updates);412 } else if (FeasibleSuccessors.size() == 1) {413 // Replace with an unconditional branch to the only feasible successor.414 BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();415 SmallVector<DominatorTree::UpdateType, 8> Updates;416 bool HaveSeenOnlyFeasibleSuccessor = false;417 for (BasicBlock *Succ : successors(BB)) {418 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {419 // Don't remove the edge to the only feasible successor the first time420 // we see it. We still do need to remove any multi-edges to it though.421 HaveSeenOnlyFeasibleSuccessor = true;422 continue;423 }424 425 Succ->removePredecessor(BB);426 Updates.push_back({DominatorTree::Delete, BB, Succ});427 }428 429 Instruction *BI = BranchInst::Create(OnlyFeasibleSuccessor, BB);430 BI->setDebugLoc(TI->getDebugLoc());431 TI->eraseFromParent();432 DTU.applyUpdatesPermissive(Updates);433 } else if (FeasibleSuccessors.size() > 1) {434 SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));435 SmallVector<DominatorTree::UpdateType, 8> Updates;436 437 // If the default destination is unfeasible it will never be taken. Replace438 // it with a new block with a single Unreachable instruction.439 BasicBlock *DefaultDest = SI->getDefaultDest();440 if (!FeasibleSuccessors.contains(DefaultDest)) {441 if (!NewUnreachableBB) {442 NewUnreachableBB =443 BasicBlock::Create(DefaultDest->getContext(), "default.unreachable",444 DefaultDest->getParent(), DefaultDest);445 auto *UI =446 new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);447 UI->setDebugLoc(DebugLoc::getTemporary());448 }449 450 DefaultDest->removePredecessor(BB);451 SI->setDefaultDest(NewUnreachableBB);452 Updates.push_back({DominatorTree::Delete, BB, DefaultDest});453 Updates.push_back({DominatorTree::Insert, BB, NewUnreachableBB});454 }455 456 for (auto CI = SI->case_begin(); CI != SI->case_end();) {457 if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {458 ++CI;459 continue;460 }461 462 BasicBlock *Succ = CI->getCaseSuccessor();463 Succ->removePredecessor(BB);464 Updates.push_back({DominatorTree::Delete, BB, Succ});465 SI.removeCase(CI);466 // Don't increment CI, as we removed a case.467 }468 469 DTU.applyUpdatesPermissive(Updates);470 } else {471 llvm_unreachable("Must have at least one feasible successor");472 }473 return true;474}475 476static void inferAttribute(Function *F, unsigned AttrIndex,477 const ValueLatticeElement &Val) {478 // If there is a known constant range for the value, add range attribute.479 if (Val.isConstantRange() && !Val.getConstantRange().isSingleElement()) {480 // Do not add range attribute if the value may include undef.481 if (Val.isConstantRangeIncludingUndef())482 return;483 484 // Take the intersection of the existing attribute and the inferred range.485 Attribute OldAttr = F->getAttributeAtIndex(AttrIndex, Attribute::Range);486 ConstantRange CR = Val.getConstantRange();487 if (OldAttr.isValid())488 CR = CR.intersectWith(OldAttr.getRange());489 F->addAttributeAtIndex(490 AttrIndex, Attribute::get(F->getContext(), Attribute::Range, CR));491 return;492 }493 // Infer nonnull attribute.494 if (Val.isNotConstant() && Val.getNotConstant()->getType()->isPointerTy() &&495 Val.getNotConstant()->isNullValue() &&496 !F->hasAttributeAtIndex(AttrIndex, Attribute::NonNull)) {497 F->addAttributeAtIndex(AttrIndex,498 Attribute::get(F->getContext(), Attribute::NonNull));499 }500}501 502void SCCPSolver::inferReturnAttributes() const {503 for (const auto &[F, ReturnValue] : getTrackedRetVals())504 inferAttribute(F, AttributeList::ReturnIndex, ReturnValue);505}506 507void SCCPSolver::inferArgAttributes() const {508 for (Function *F : getArgumentTrackedFunctions()) {509 if (!isBlockExecutable(&F->front()))510 continue;511 for (Argument &A : F->args())512 if (!A.getType()->isStructTy())513 inferAttribute(F, AttributeList::FirstArgIndex + A.getArgNo(),514 getLatticeValueFor(&A));515 }516}517 518/// Helper class for SCCPSolver. This implements the instruction visitor and519/// holds all the state.520class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {521 const DataLayout &DL;522 std::function<const TargetLibraryInfo &(Function &)> GetTLI;523 /// Basic blocks that are executable (but may not have been visited yet).524 SmallPtrSet<BasicBlock *, 8> BBExecutable;525 /// Basic blocks that are executable and have been visited at least once.526 SmallPtrSet<BasicBlock *, 8> BBVisited;527 DenseMap<Value *, ValueLatticeElement>528 ValueState; // The state each value is in.529 530 /// StructValueState - This maintains ValueState for values that have531 /// StructType, for example for formal arguments, calls, insertelement, etc.532 DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement> StructValueState;533 534 /// GlobalValue - If we are tracking any values for the contents of a global535 /// variable, we keep a mapping from the constant accessor to the element of536 /// the global, to the currently known value. If the value becomes537 /// overdefined, it's entry is simply removed from this map.538 DenseMap<GlobalVariable *, ValueLatticeElement> TrackedGlobals;539 540 /// TrackedRetVals - If we are tracking arguments into and the return541 /// value out of a function, it will have an entry in this map, indicating542 /// what the known return value for the function is.543 MapVector<Function *, ValueLatticeElement> TrackedRetVals;544 545 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions546 /// that return multiple values.547 MapVector<std::pair<Function *, unsigned>, ValueLatticeElement>548 TrackedMultipleRetVals;549 550 /// The set of values whose lattice has been invalidated.551 /// Populated by resetLatticeValueFor(), cleared after resolving undefs.552 DenseSet<Value *> Invalidated;553 554 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is555 /// represented here for efficient lookup.556 SmallPtrSet<Function *, 16> MRVFunctionsTracked;557 558 /// A list of functions whose return cannot be modified.559 SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions;560 561 /// TrackingIncomingArguments - This is the set of functions for whose562 /// arguments we make optimistic assumptions about and try to prove as563 /// constants.564 SmallPtrSet<Function *, 16> TrackingIncomingArguments;565 566 /// Worklist of instructions to re-visit. This only includes instructions567 /// in blocks that have already been visited at least once.568 SmallSetVector<Instruction *, 16> InstWorkList;569 570 /// Current instruction while visiting a block for the first time, used to571 /// avoid unnecessary instruction worklist insertions. Null if an instruction572 /// is visited outside a whole-block visitation.573 Instruction *CurI = nullptr;574 575 // The BasicBlock work list576 SmallVector<BasicBlock *, 64> BBWorkList;577 578 /// KnownFeasibleEdges - Entries in this set are edges which have already had579 /// PHI nodes retriggered.580 using Edge = std::pair<BasicBlock *, BasicBlock *>;581 DenseSet<Edge> KnownFeasibleEdges;582 583 DenseMap<Function *, std::unique_ptr<PredicateInfo>> FnPredicateInfo;584 585 DenseMap<Value *, SmallSetVector<User *, 2>> AdditionalUsers;586 587 LLVMContext &Ctx;588 589 BumpPtrAllocator PredicateInfoAllocator;590 591private:592 ConstantInt *getConstantInt(const ValueLatticeElement &IV, Type *Ty) const {593 return dyn_cast_or_null<ConstantInt>(getConstant(IV, Ty));594 }595 596 /// Push instruction \p I to the worklist.597 void pushToWorkList(Instruction *I);598 599 /// Push users of value \p V to the worklist.600 void pushUsersToWorkList(Value *V);601 602 /// Like pushUsersToWorkList(), but also prints a debug message with the603 /// updated value.604 void pushUsersToWorkListMsg(ValueLatticeElement &IV, Value *V);605 606 // markConstant - Make a value be marked as "constant". If the value607 // is not already a constant, add it to the instruction work list so that608 // the users of the instruction are updated later.609 bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,610 bool MayIncludeUndef = false);611 612 bool markConstant(Value *V, Constant *C) {613 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");614 return markConstant(ValueState[V], V, C);615 }616 617 bool markNotConstant(ValueLatticeElement &IV, Value *V, Constant *C);618 619 bool markNotNull(ValueLatticeElement &IV, Value *V) {620 return markNotConstant(IV, V, Constant::getNullValue(V->getType()));621 }622 623 /// markConstantRange - Mark the object as constant range with \p CR. If the624 /// object is not a constant range with the range \p CR, add it to the625 /// instruction work list so that the users of the instruction are updated626 /// later.627 bool markConstantRange(ValueLatticeElement &IV, Value *V,628 const ConstantRange &CR);629 630 // markOverdefined - Make a value be marked as "overdefined". If the631 // value is not already overdefined, add it to the overdefined instruction632 // work list so that the users of the instruction are updated later.633 bool markOverdefined(ValueLatticeElement &IV, Value *V);634 635 /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV636 /// changes.637 bool mergeInValue(ValueLatticeElement &IV, Value *V,638 const ValueLatticeElement &MergeWithV,639 ValueLatticeElement::MergeOptions Opts = {640 /*MayIncludeUndef=*/false, /*CheckWiden=*/false});641 642 /// getValueState - Return the ValueLatticeElement object that corresponds to643 /// the value. This function handles the case when the value hasn't been seen644 /// yet by properly seeding constants etc.645 ValueLatticeElement &getValueState(Value *V) {646 assert(!V->getType()->isStructTy() && "Should use getStructValueState");647 648 auto I = ValueState.try_emplace(V);649 ValueLatticeElement &LV = I.first->second;650 651 if (!I.second)652 return LV; // Common case, already in the map.653 654 if (auto *C = dyn_cast<Constant>(V))655 LV.markConstant(C); // Constants are constant656 657 // All others are unknown by default.658 return LV;659 }660 661 /// getStructValueState - Return the ValueLatticeElement object that662 /// corresponds to the value/field pair. This function handles the case when663 /// the value hasn't been seen yet by properly seeding constants etc.664 ValueLatticeElement &getStructValueState(Value *V, unsigned i) {665 assert(V->getType()->isStructTy() && "Should use getValueState");666 assert(i < cast<StructType>(V->getType())->getNumElements() &&667 "Invalid element #");668 669 auto I = StructValueState.insert(670 std::make_pair(std::make_pair(V, i), ValueLatticeElement()));671 ValueLatticeElement &LV = I.first->second;672 673 if (!I.second)674 return LV; // Common case, already in the map.675 676 if (auto *C = dyn_cast<Constant>(V)) {677 Constant *Elt = C->getAggregateElement(i);678 679 if (!Elt)680 LV.markOverdefined(); // Unknown sort of constant.681 else682 LV.markConstant(Elt); // Constants are constant.683 }684 685 // All others are underdefined by default.686 return LV;687 }688 689 /// Traverse the use-def chain of \p Call, marking itself and its users as690 /// "unknown" on the way.691 void invalidate(CallBase *Call) {692 SmallVector<Instruction *, 64> ToInvalidate;693 ToInvalidate.push_back(Call);694 695 while (!ToInvalidate.empty()) {696 Instruction *Inst = ToInvalidate.pop_back_val();697 698 if (!Invalidated.insert(Inst).second)699 continue;700 701 if (!BBExecutable.count(Inst->getParent()))702 continue;703 704 Value *V = nullptr;705 // For return instructions we need to invalidate the tracked returns map.706 // Anything else has its lattice in the value map.707 if (auto *RetInst = dyn_cast<ReturnInst>(Inst)) {708 Function *F = RetInst->getParent()->getParent();709 if (auto It = TrackedRetVals.find(F); It != TrackedRetVals.end()) {710 It->second = ValueLatticeElement();711 V = F;712 } else if (MRVFunctionsTracked.count(F)) {713 auto *STy = cast<StructType>(F->getReturnType());714 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)715 TrackedMultipleRetVals[{F, I}] = ValueLatticeElement();716 V = F;717 }718 } else if (auto *STy = dyn_cast<StructType>(Inst->getType())) {719 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {720 if (auto It = StructValueState.find({Inst, I});721 It != StructValueState.end()) {722 It->second = ValueLatticeElement();723 V = Inst;724 }725 }726 } else if (auto It = ValueState.find(Inst); It != ValueState.end()) {727 It->second = ValueLatticeElement();728 V = Inst;729 }730 731 if (V) {732 LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n");733 734 for (User *U : V->users())735 if (auto *UI = dyn_cast<Instruction>(U))736 ToInvalidate.push_back(UI);737 738 auto It = AdditionalUsers.find(V);739 if (It != AdditionalUsers.end())740 for (User *U : It->second)741 if (auto *UI = dyn_cast<Instruction>(U))742 ToInvalidate.push_back(UI);743 }744 }745 }746 747 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB748 /// work list if it is not already executable.749 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);750 751 // getFeasibleSuccessors - Return a vector of booleans to indicate which752 // successors are reachable from a given terminator instruction.753 void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);754 755 // Add U as additional user of V.756 void addAdditionalUser(Value *V, User *U) { AdditionalUsers[V].insert(U); }757 758 void handlePredicate(Instruction *I, Value *CopyOf, const PredicateBase *PI);759 void handleCallOverdefined(CallBase &CB);760 void handleCallResult(CallBase &CB);761 void handleCallArguments(CallBase &CB);762 void handleExtractOfWithOverflow(ExtractValueInst &EVI,763 const WithOverflowInst *WO, unsigned Idx);764 bool isInstFullyOverDefined(Instruction &Inst);765 766private:767 friend class InstVisitor<SCCPInstVisitor>;768 769 // visit implementations - Something changed in this instruction. Either an770 // operand made a transition, or the instruction is newly executable. Change771 // the value type of I to reflect these changes if appropriate.772 void visitPHINode(PHINode &I);773 774 // Terminators775 776 void visitReturnInst(ReturnInst &I);777 void visitTerminator(Instruction &TI);778 779 void visitCastInst(CastInst &I);780 void visitSelectInst(SelectInst &I);781 void visitUnaryOperator(Instruction &I);782 void visitFreezeInst(FreezeInst &I);783 void visitBinaryOperator(Instruction &I);784 void visitCmpInst(CmpInst &I);785 void visitExtractValueInst(ExtractValueInst &EVI);786 void visitInsertValueInst(InsertValueInst &IVI);787 788 void visitCatchSwitchInst(CatchSwitchInst &CPI) {789 markOverdefined(&CPI);790 visitTerminator(CPI);791 }792 793 // Instructions that cannot be folded away.794 795 void visitStoreInst(StoreInst &I);796 void visitLoadInst(LoadInst &I);797 void visitGetElementPtrInst(GetElementPtrInst &I);798 void visitAllocaInst(AllocaInst &AI);799 800 void visitInvokeInst(InvokeInst &II) {801 visitCallBase(II);802 visitTerminator(II);803 }804 805 void visitCallBrInst(CallBrInst &CBI) {806 visitCallBase(CBI);807 visitTerminator(CBI);808 }809 810 void visitCallBase(CallBase &CB);811 void visitResumeInst(ResumeInst &I) { /*returns void*/812 }813 void visitUnreachableInst(UnreachableInst &I) { /*returns void*/814 }815 void visitFenceInst(FenceInst &I) { /*returns void*/816 }817 818 void visitInstruction(Instruction &I);819 820public:821 void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC) {822 FnPredicateInfo.insert({&F, std::make_unique<PredicateInfo>(823 F, DT, AC, PredicateInfoAllocator)});824 }825 826 void removeSSACopies(Function &F) {827 auto It = FnPredicateInfo.find(&F);828 if (It == FnPredicateInfo.end())829 return;830 831 for (BasicBlock &BB : F) {832 for (Instruction &Inst : llvm::make_early_inc_range(BB)) {833 if (auto *BC = dyn_cast<BitCastInst>(&Inst)) {834 if (BC->getType() == BC->getOperand(0)->getType()) {835 if (It->second->getPredicateInfoFor(&Inst)) {836 Value *Op = BC->getOperand(0);837 Inst.replaceAllUsesWith(Op);838 Inst.eraseFromParent();839 }840 }841 }842 }843 }844 }845 846 void visitCallInst(CallInst &I) { visitCallBase(I); }847 848 bool markBlockExecutable(BasicBlock *BB);849 850 const PredicateBase *getPredicateInfoFor(Instruction *I) {851 auto It = FnPredicateInfo.find(I->getParent()->getParent());852 if (It == FnPredicateInfo.end())853 return nullptr;854 return It->second->getPredicateInfoFor(I);855 }856 857 SCCPInstVisitor(const DataLayout &DL,858 std::function<const TargetLibraryInfo &(Function &)> GetTLI,859 LLVMContext &Ctx)860 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}861 862 void trackValueOfGlobalVariable(GlobalVariable *GV) {863 // We only track the contents of scalar globals.864 if (GV->getValueType()->isSingleValueType()) {865 ValueLatticeElement &IV = TrackedGlobals[GV];866 IV.markConstant(GV->getInitializer());867 }868 }869 870 void addTrackedFunction(Function *F) {871 // Add an entry, F -> undef.872 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {873 MRVFunctionsTracked.insert(F);874 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)875 TrackedMultipleRetVals.try_emplace(std::make_pair(F, i));876 } else if (!F->getReturnType()->isVoidTy())877 TrackedRetVals.try_emplace(F);878 }879 880 void addToMustPreserveReturnsInFunctions(Function *F) {881 MustPreserveReturnsInFunctions.insert(F);882 }883 884 bool mustPreserveReturn(Function *F) {885 return MustPreserveReturnsInFunctions.count(F);886 }887 888 void addArgumentTrackedFunction(Function *F) {889 TrackingIncomingArguments.insert(F);890 }891 892 bool isArgumentTrackedFunction(Function *F) {893 return TrackingIncomingArguments.count(F);894 }895 896 const SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() const {897 return TrackingIncomingArguments;898 }899 900 void solve();901 902 bool resolvedUndef(Instruction &I);903 904 bool resolvedUndefsIn(Function &F);905 906 bool isBlockExecutable(BasicBlock *BB) const {907 return BBExecutable.count(BB);908 }909 910 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;911 912 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {913 std::vector<ValueLatticeElement> StructValues;914 auto *STy = dyn_cast<StructType>(V->getType());915 assert(STy && "getStructLatticeValueFor() can be called only on structs");916 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {917 auto I = StructValueState.find(std::make_pair(V, i));918 assert(I != StructValueState.end() && "Value not in valuemap!");919 StructValues.push_back(I->second);920 }921 return StructValues;922 }923 924 void removeLatticeValueFor(Value *V) { ValueState.erase(V); }925 926 /// Invalidate the Lattice Value of \p Call and its users after specializing927 /// the call. Then recompute it.928 void resetLatticeValueFor(CallBase *Call) {929 // Calls to void returning functions do not need invalidation.930 Function *F = Call->getCalledFunction();931 (void)F;932 assert(!F->getReturnType()->isVoidTy() &&933 (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) &&934 "All non void specializations should be tracked");935 invalidate(Call);936 handleCallResult(*Call);937 }938 939 const ValueLatticeElement &getLatticeValueFor(Value *V) const {940 assert(!V->getType()->isStructTy() &&941 "Should use getStructLatticeValueFor");942 DenseMap<Value *, ValueLatticeElement>::const_iterator I =943 ValueState.find(V);944 assert(I != ValueState.end() &&945 "V not found in ValueState nor Paramstate map!");946 return I->second;947 }948 949 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() const {950 return TrackedRetVals;951 }952 953 const DenseMap<GlobalVariable *, ValueLatticeElement> &954 getTrackedGlobals() const {955 return TrackedGlobals;956 }957 958 const SmallPtrSet<Function *, 16> &getMRVFunctionsTracked() const {959 return MRVFunctionsTracked;960 }961 962 void markOverdefined(Value *V) {963 if (auto *STy = dyn_cast<StructType>(V->getType()))964 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)965 markOverdefined(getStructValueState(V, i), V);966 else967 markOverdefined(ValueState[V], V);968 }969 970 ValueLatticeElement getArgAttributeVL(Argument *A) {971 if (A->getType()->isIntOrIntVectorTy()) {972 if (std::optional<ConstantRange> Range = A->getRange())973 return ValueLatticeElement::getRange(*Range);974 }975 if (A->hasNonNullAttr())976 return ValueLatticeElement::getNot(Constant::getNullValue(A->getType()));977 // Assume nothing about the incoming arguments without attributes.978 return ValueLatticeElement::getOverdefined();979 }980 981 void trackValueOfArgument(Argument *A) {982 if (A->getType()->isStructTy())983 return (void)markOverdefined(A);984 mergeInValue(ValueState[A], A, getArgAttributeVL(A));985 }986 987 bool isStructLatticeConstant(Function *F, StructType *STy);988 989 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const;990 991 Constant *getConstantOrNull(Value *V) const;992 993 void setLatticeValueForSpecializationArguments(Function *F,994 const SmallVectorImpl<ArgInfo> &Args);995 996 void markFunctionUnreachable(Function *F) {997 for (auto &BB : *F)998 BBExecutable.erase(&BB);999 }1000 1001 void solveWhileResolvedUndefsIn(Module &M) {1002 bool ResolvedUndefs = true;1003 while (ResolvedUndefs) {1004 solve();1005 ResolvedUndefs = false;1006 for (Function &F : M)1007 ResolvedUndefs |= resolvedUndefsIn(F);1008 }1009 }1010 1011 void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {1012 bool ResolvedUndefs = true;1013 while (ResolvedUndefs) {1014 solve();1015 ResolvedUndefs = false;1016 for (Function *F : WorkList)1017 ResolvedUndefs |= resolvedUndefsIn(*F);1018 }1019 }1020 1021 void solveWhileResolvedUndefs() {1022 bool ResolvedUndefs = true;1023 while (ResolvedUndefs) {1024 solve();1025 ResolvedUndefs = false;1026 for (Value *V : Invalidated)1027 if (auto *I = dyn_cast<Instruction>(V))1028 ResolvedUndefs |= resolvedUndef(*I);1029 }1030 Invalidated.clear();1031 }1032};1033 1034} // namespace llvm1035 1036bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) {1037 if (!BBExecutable.insert(BB).second)1038 return false;1039 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');1040 BBWorkList.push_back(BB); // Add the block to the work list!1041 return true;1042}1043 1044void SCCPInstVisitor::pushToWorkList(Instruction *I) {1045 // If we're currently visiting a block, do not push any instructions in the1046 // same blocks that are after the current one, as they will be visited1047 // anyway. We do have to push updates to earlier instructions (e.g. phi1048 // nodes or loads of tracked globals).1049 if (CurI && I->getParent() == CurI->getParent() && !I->comesBefore(CurI))1050 return;1051 // Only push instructions in already visited blocks. Otherwise we'll handle1052 // it when we visit the block for the first time.1053 if (BBVisited.contains(I->getParent()))1054 InstWorkList.insert(I);1055}1056 1057void SCCPInstVisitor::pushUsersToWorkList(Value *V) {1058 for (User *U : V->users())1059 if (auto *UI = dyn_cast<Instruction>(U))1060 pushToWorkList(UI);1061 1062 auto Iter = AdditionalUsers.find(V);1063 if (Iter != AdditionalUsers.end()) {1064 // Copy additional users before notifying them of changes, because new1065 // users may be added, potentially invalidating the iterator.1066 SmallVector<Instruction *, 2> ToNotify;1067 for (User *U : Iter->second)1068 if (auto *UI = dyn_cast<Instruction>(U))1069 ToNotify.push_back(UI);1070 for (Instruction *UI : ToNotify)1071 pushToWorkList(UI);1072 }1073}1074 1075void SCCPInstVisitor::pushUsersToWorkListMsg(ValueLatticeElement &IV,1076 Value *V) {1077 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');1078 pushUsersToWorkList(V);1079}1080 1081bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,1082 Constant *C, bool MayIncludeUndef) {1083 if (!IV.markConstant(C, MayIncludeUndef))1084 return false;1085 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');1086 pushUsersToWorkList(V);1087 return true;1088}1089 1090bool SCCPInstVisitor::markNotConstant(ValueLatticeElement &IV, Value *V,1091 Constant *C) {1092 if (!IV.markNotConstant(C))1093 return false;1094 LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n');1095 pushUsersToWorkList(V);1096 return true;1097}1098 1099bool SCCPInstVisitor::markConstantRange(ValueLatticeElement &IV, Value *V,1100 const ConstantRange &CR) {1101 if (!IV.markConstantRange(CR))1102 return false;1103 LLVM_DEBUG(dbgs() << "markConstantRange: " << CR << ": " << *V << '\n');1104 pushUsersToWorkList(V);1105 return true;1106}1107 1108bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {1109 if (!IV.markOverdefined())1110 return false;1111 1112 LLVM_DEBUG(dbgs() << "markOverdefined: ";1113 if (auto *F = dyn_cast<Function>(V)) dbgs()1114 << "Function '" << F->getName() << "'\n";1115 else dbgs() << *V << '\n');1116 // Only instructions go on the work list1117 pushUsersToWorkList(V);1118 return true;1119}1120 1121bool SCCPInstVisitor::isStructLatticeConstant(Function *F, StructType *STy) {1122 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {1123 const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));1124 assert(It != TrackedMultipleRetVals.end());1125 if (!SCCPSolver::isConstant(It->second))1126 return false;1127 }1128 return true;1129}1130 1131Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV,1132 Type *Ty) const {1133 if (LV.isConstant()) {1134 Constant *C = LV.getConstant();1135 assert(C->getType() == Ty && "Type mismatch");1136 return C;1137 }1138 1139 if (LV.isConstantRange()) {1140 const auto &CR = LV.getConstantRange();1141 if (CR.getSingleElement())1142 return ConstantInt::get(Ty, *CR.getSingleElement());1143 }1144 return nullptr;1145}1146 1147Constant *SCCPInstVisitor::getConstantOrNull(Value *V) const {1148 Constant *Const = nullptr;1149 if (V->getType()->isStructTy()) {1150 std::vector<ValueLatticeElement> LVs = getStructLatticeValueFor(V);1151 if (any_of(LVs, SCCPSolver::isOverdefined))1152 return nullptr;1153 std::vector<Constant *> ConstVals;1154 auto *ST = cast<StructType>(V->getType());1155 for (unsigned I = 0, E = ST->getNumElements(); I != E; ++I) {1156 const ValueLatticeElement &LV = LVs[I];1157 ConstVals.push_back(SCCPSolver::isConstant(LV)1158 ? getConstant(LV, ST->getElementType(I))1159 : UndefValue::get(ST->getElementType(I)));1160 }1161 Const = ConstantStruct::get(ST, ConstVals);1162 } else {1163 const ValueLatticeElement &LV = getLatticeValueFor(V);1164 if (SCCPSolver::isOverdefined(LV))1165 return nullptr;1166 Const = SCCPSolver::isConstant(LV) ? getConstant(LV, V->getType())1167 : UndefValue::get(V->getType());1168 }1169 assert(Const && "Constant is nullptr here!");1170 return Const;1171}1172 1173void SCCPInstVisitor::setLatticeValueForSpecializationArguments(Function *F,1174 const SmallVectorImpl<ArgInfo> &Args) {1175 assert(!Args.empty() && "Specialization without arguments");1176 assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&1177 "Functions should have the same number of arguments");1178 1179 auto Iter = Args.begin();1180 Function::arg_iterator NewArg = F->arg_begin();1181 Function::arg_iterator OldArg = Args[0].Formal->getParent()->arg_begin();1182 for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {1183 1184 LLVM_DEBUG(dbgs() << "SCCP: Marking argument "1185 << NewArg->getNameOrAsOperand() << "\n");1186 1187 // Mark the argument constants in the new function1188 // or copy the lattice state over from the old function.1189 if (Iter != Args.end() && Iter->Formal == &*OldArg) {1190 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) {1191 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {1192 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];1193 NewValue.markConstant(Iter->Actual->getAggregateElement(I));1194 }1195 } else {1196 ValueState[&*NewArg].markConstant(Iter->Actual);1197 }1198 ++Iter;1199 } else {1200 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) {1201 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {1202 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];1203 NewValue = StructValueState[{&*OldArg, I}];1204 }1205 } else {1206 ValueLatticeElement &NewValue = ValueState[&*NewArg];1207 NewValue = ValueState[&*OldArg];1208 }1209 }1210 }1211}1212 1213void SCCPInstVisitor::visitInstruction(Instruction &I) {1214 // All the instructions we don't do any special handling for just1215 // go to overdefined.1216 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');1217 markOverdefined(&I);1218}1219 1220bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,1221 const ValueLatticeElement &MergeWithV,1222 ValueLatticeElement::MergeOptions Opts) {1223 if (IV.mergeIn(MergeWithV, Opts)) {1224 pushUsersToWorkList(V);1225 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "1226 << IV << "\n");1227 return true;1228 }1229 return false;1230}1231 1232bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {1233 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)1234 return false; // This edge is already known to be executable!1235 1236 if (!markBlockExecutable(Dest)) {1237 // If the destination is already executable, we just made an *edge*1238 // feasible that wasn't before. Revisit the PHI nodes in the block1239 // because they have potentially new operands.1240 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()1241 << " -> " << Dest->getName() << '\n');1242 1243 for (PHINode &PN : Dest->phis())1244 pushToWorkList(&PN);1245 }1246 return true;1247}1248 1249// getFeasibleSuccessors - Return a vector of booleans to indicate which1250// successors are reachable from a given terminator instruction.1251void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,1252 SmallVectorImpl<bool> &Succs) {1253 Succs.resize(TI.getNumSuccessors());1254 if (auto *BI = dyn_cast<BranchInst>(&TI)) {1255 if (BI->isUnconditional()) {1256 Succs[0] = true;1257 return;1258 }1259 1260 const ValueLatticeElement &BCValue = getValueState(BI->getCondition());1261 ConstantInt *CI = getConstantInt(BCValue, BI->getCondition()->getType());1262 if (!CI) {1263 // Overdefined condition variables, and branches on unfoldable constant1264 // conditions, mean the branch could go either way.1265 if (!BCValue.isUnknownOrUndef())1266 Succs[0] = Succs[1] = true;1267 return;1268 }1269 1270 // Constant condition variables mean the branch can only go a single way.1271 Succs[CI->isZero()] = true;1272 return;1273 }1274 1275 // We cannot analyze special terminators, so consider all successors1276 // executable.1277 if (TI.isSpecialTerminator()) {1278 Succs.assign(TI.getNumSuccessors(), true);1279 return;1280 }1281 1282 if (auto *SI = dyn_cast<SwitchInst>(&TI)) {1283 if (!SI->getNumCases()) {1284 Succs[0] = true;1285 return;1286 }1287 const ValueLatticeElement &SCValue = getValueState(SI->getCondition());1288 if (ConstantInt *CI =1289 getConstantInt(SCValue, SI->getCondition()->getType())) {1290 Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;1291 return;1292 }1293 1294 // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM1295 // is ready.1296 if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {1297 const ConstantRange &Range = SCValue.getConstantRange();1298 unsigned ReachableCaseCount = 0;1299 for (const auto &Case : SI->cases()) {1300 const APInt &CaseValue = Case.getCaseValue()->getValue();1301 if (Range.contains(CaseValue)) {1302 Succs[Case.getSuccessorIndex()] = true;1303 ++ReachableCaseCount;1304 }1305 }1306 1307 Succs[SI->case_default()->getSuccessorIndex()] =1308 Range.isSizeLargerThan(ReachableCaseCount);1309 return;1310 }1311 1312 // Overdefined or unknown condition? All destinations are executable!1313 if (!SCValue.isUnknownOrUndef())1314 Succs.assign(TI.getNumSuccessors(), true);1315 return;1316 }1317 1318 // In case of indirect branch and its address is a blockaddress, we mark1319 // the target as executable.1320 if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {1321 // Casts are folded by visitCastInst.1322 const ValueLatticeElement &IBRValue = getValueState(IBR->getAddress());1323 BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(1324 getConstant(IBRValue, IBR->getAddress()->getType()));1325 if (!Addr) { // Overdefined or unknown condition?1326 // All destinations are executable!1327 if (!IBRValue.isUnknownOrUndef())1328 Succs.assign(TI.getNumSuccessors(), true);1329 return;1330 }1331 1332 BasicBlock *T = Addr->getBasicBlock();1333 assert(Addr->getFunction() == T->getParent() &&1334 "Block address of a different function ?");1335 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {1336 // This is the target.1337 if (IBR->getDestination(i) == T) {1338 Succs[i] = true;1339 return;1340 }1341 }1342 1343 // If we didn't find our destination in the IBR successor list, then we1344 // have undefined behavior. Its ok to assume no successor is executable.1345 return;1346 }1347 1348 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');1349 llvm_unreachable("SCCP: Don't know how to handle this terminator!");1350}1351 1352// isEdgeFeasible - Return true if the control flow edge from the 'From' basic1353// block to the 'To' basic block is currently feasible.1354bool SCCPInstVisitor::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {1355 // Check if we've called markEdgeExecutable on the edge yet. (We could1356 // be more aggressive and try to consider edges which haven't been marked1357 // yet, but there isn't any need.)1358 return KnownFeasibleEdges.count(Edge(From, To));1359}1360 1361// visit Implementations - Something changed in this instruction, either an1362// operand made a transition, or the instruction is newly executable. Change1363// the value type of I to reflect these changes if appropriate. This method1364// makes sure to do the following actions:1365//1366// 1. If a phi node merges two constants in, and has conflicting value coming1367// from different branches, or if the PHI node merges in an overdefined1368// value, then the PHI node becomes overdefined.1369// 2. If a phi node merges only constants in, and they all agree on value, the1370// PHI node becomes a constant value equal to that.1371// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant1372// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined1373// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined1374// 6. If a conditional branch has a value that is constant, make the selected1375// destination executable1376// 7. If a conditional branch has a value that is overdefined, make all1377// successors executable.1378void SCCPInstVisitor::visitPHINode(PHINode &PN) {1379 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,1380 // and slow us down a lot. Just mark them overdefined.1381 if (PN.getNumIncomingValues() > 64)1382 return (void)markOverdefined(&PN);1383 1384 if (isInstFullyOverDefined(PN))1385 return;1386 SmallVector<unsigned> FeasibleIncomingIndices;1387 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {1388 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))1389 continue;1390 FeasibleIncomingIndices.push_back(i);1391 }1392 1393 // Look at all of the executable operands of the PHI node. If any of them1394 // are overdefined, the PHI becomes overdefined as well. If they are all1395 // constant, and they agree with each other, the PHI becomes the identical1396 // constant. If they are constant and don't agree, the PHI is a constant1397 // range. If there are no executable operands, the PHI remains unknown.1398 if (StructType *STy = dyn_cast<StructType>(PN.getType())) {1399 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {1400 ValueLatticeElement PhiState = getStructValueState(&PN, i);1401 if (PhiState.isOverdefined())1402 continue;1403 for (unsigned j : FeasibleIncomingIndices) {1404 const ValueLatticeElement &IV =1405 getStructValueState(PN.getIncomingValue(j), i);1406 PhiState.mergeIn(IV);1407 if (PhiState.isOverdefined())1408 break;1409 }1410 ValueLatticeElement &PhiStateRef = getStructValueState(&PN, i);1411 mergeInValue(PhiStateRef, &PN, PhiState,1412 ValueLatticeElement::MergeOptions().setMaxWidenSteps(1413 FeasibleIncomingIndices.size() + 1));1414 PhiStateRef.setNumRangeExtensions(1415 std::max((unsigned)FeasibleIncomingIndices.size(),1416 PhiStateRef.getNumRangeExtensions()));1417 }1418 } else {1419 ValueLatticeElement PhiState = getValueState(&PN);1420 for (unsigned i : FeasibleIncomingIndices) {1421 const ValueLatticeElement &IV = getValueState(PN.getIncomingValue(i));1422 PhiState.mergeIn(IV);1423 if (PhiState.isOverdefined())1424 break;1425 }1426 // We allow up to 1 range extension per active incoming value and one1427 // additional extension. Note that we manually adjust the number of range1428 // extensions to match the number of active incoming values. This helps to1429 // limit multiple extensions caused by the same incoming value, if other1430 // incoming values are equal.1431 ValueLatticeElement &PhiStateRef = ValueState[&PN];1432 mergeInValue(PhiStateRef, &PN, PhiState,1433 ValueLatticeElement::MergeOptions().setMaxWidenSteps(1434 FeasibleIncomingIndices.size() + 1));1435 PhiStateRef.setNumRangeExtensions(1436 std::max((unsigned)FeasibleIncomingIndices.size(),1437 PhiStateRef.getNumRangeExtensions()));1438 }1439}1440 1441void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {1442 if (I.getNumOperands() == 0)1443 return; // ret void1444 1445 Function *F = I.getParent()->getParent();1446 Value *ResultOp = I.getOperand(0);1447 1448 // If we are tracking the return value of this function, merge it in.1449 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {1450 auto TFRVI = TrackedRetVals.find(F);1451 if (TFRVI != TrackedRetVals.end()) {1452 mergeInValue(TFRVI->second, F, getValueState(ResultOp));1453 return;1454 }1455 }1456 1457 // Handle functions that return multiple values.1458 if (!TrackedMultipleRetVals.empty()) {1459 if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))1460 if (MRVFunctionsTracked.count(F))1461 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)1462 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,1463 getStructValueState(ResultOp, i));1464 }1465}1466 1467void SCCPInstVisitor::visitTerminator(Instruction &TI) {1468 SmallVector<bool, 16> SuccFeasible;1469 getFeasibleSuccessors(TI, SuccFeasible);1470 1471 BasicBlock *BB = TI.getParent();1472 1473 // Mark all feasible successors executable.1474 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)1475 if (SuccFeasible[i])1476 markEdgeExecutable(BB, TI.getSuccessor(i));1477}1478 1479void SCCPInstVisitor::visitCastInst(CastInst &I) {1480 // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would1481 // discover a concrete value later.1482 if (ValueState[&I].isOverdefined())1483 return;1484 1485 if (auto *BC = dyn_cast<BitCastInst>(&I)) {1486 if (BC->getType() == BC->getOperand(0)->getType()) {1487 if (const PredicateBase *PI = getPredicateInfoFor(&I)) {1488 handlePredicate(&I, I.getOperand(0), PI);1489 return;1490 }1491 }1492 }1493 1494 const ValueLatticeElement &OpSt = getValueState(I.getOperand(0));1495 if (OpSt.isUnknownOrUndef())1496 return;1497 1498 if (Constant *OpC = getConstant(OpSt, I.getOperand(0)->getType())) {1499 // Fold the constant as we build.1500 if (Constant *C =1501 ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL))1502 return (void)markConstant(&I, C);1503 }1504 1505 // Ignore bitcasts, as they may change the number of vector elements.1506 if (I.getDestTy()->isIntOrIntVectorTy() &&1507 I.getSrcTy()->isIntOrIntVectorTy() &&1508 I.getOpcode() != Instruction::BitCast) {1509 ConstantRange OpRange =1510 OpSt.asConstantRange(I.getSrcTy(), /*UndefAllowed=*/false);1511 auto &LV = getValueState(&I);1512 1513 Type *DestTy = I.getDestTy();1514 ConstantRange Res = ConstantRange::getEmpty(DestTy->getScalarSizeInBits());1515 if (auto *Trunc = dyn_cast<TruncInst>(&I))1516 Res = OpRange.truncate(DestTy->getScalarSizeInBits(),1517 Trunc->getNoWrapKind());1518 else1519 Res = OpRange.castOp(I.getOpcode(), DestTy->getScalarSizeInBits());1520 mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));1521 } else1522 markOverdefined(&I);1523}1524 1525void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,1526 const WithOverflowInst *WO,1527 unsigned Idx) {1528 Value *LHS = WO->getLHS(), *RHS = WO->getRHS();1529 Type *Ty = LHS->getType();1530 1531 addAdditionalUser(LHS, &EVI);1532 addAdditionalUser(RHS, &EVI);1533 1534 const ValueLatticeElement &L = getValueState(LHS);1535 if (L.isUnknownOrUndef())1536 return; // Wait to resolve.1537 ConstantRange LR = L.asConstantRange(Ty, /*UndefAllowed=*/false);1538 1539 const ValueLatticeElement &R = getValueState(RHS);1540 if (R.isUnknownOrUndef())1541 return; // Wait to resolve.1542 1543 ConstantRange RR = R.asConstantRange(Ty, /*UndefAllowed=*/false);1544 if (Idx == 0) {1545 ConstantRange Res = LR.binaryOp(WO->getBinaryOp(), RR);1546 mergeInValue(ValueState[&EVI], &EVI, ValueLatticeElement::getRange(Res));1547 } else {1548 assert(Idx == 1 && "Index can only be 0 or 1");1549 ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(1550 WO->getBinaryOp(), RR, WO->getNoWrapKind());1551 if (NWRegion.contains(LR))1552 return (void)markConstant(&EVI, ConstantInt::getFalse(EVI.getType()));1553 markOverdefined(&EVI);1554 }1555}1556 1557void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {1558 // If this returns a struct, mark all elements over defined, we don't track1559 // structs in structs.1560 if (EVI.getType()->isStructTy())1561 return (void)markOverdefined(&EVI);1562 1563 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would1564 // discover a concrete value later.1565 if (ValueState[&EVI].isOverdefined())1566 return (void)markOverdefined(&EVI);1567 1568 // If this is extracting from more than one level of struct, we don't know.1569 if (EVI.getNumIndices() != 1)1570 return (void)markOverdefined(&EVI);1571 1572 Value *AggVal = EVI.getAggregateOperand();1573 if (AggVal->getType()->isStructTy()) {1574 unsigned i = *EVI.idx_begin();1575 if (auto *WO = dyn_cast<WithOverflowInst>(AggVal))1576 return handleExtractOfWithOverflow(EVI, WO, i);1577 ValueLatticeElement EltVal = getStructValueState(AggVal, i);1578 mergeInValue(ValueState[&EVI], &EVI, EltVal);1579 } else {1580 // Otherwise, must be extracting from an array.1581 return (void)markOverdefined(&EVI);1582 }1583}1584 1585void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {1586 auto *STy = dyn_cast<StructType>(IVI.getType());1587 if (!STy)1588 return (void)markOverdefined(&IVI);1589 1590 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would1591 // discover a concrete value later.1592 if (ValueState[&IVI].isOverdefined())1593 return (void)markOverdefined(&IVI);1594 1595 // If this has more than one index, we can't handle it, drive all results to1596 // undef.1597 if (IVI.getNumIndices() != 1)1598 return (void)markOverdefined(&IVI);1599 1600 Value *Aggr = IVI.getAggregateOperand();1601 unsigned Idx = *IVI.idx_begin();1602 1603 // Compute the result based on what we're inserting.1604 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {1605 // This passes through all values that aren't the inserted element.1606 if (i != Idx) {1607 ValueLatticeElement EltVal = getStructValueState(Aggr, i);1608 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);1609 continue;1610 }1611 1612 Value *Val = IVI.getInsertedValueOperand();1613 if (Val->getType()->isStructTy())1614 // We don't track structs in structs.1615 markOverdefined(getStructValueState(&IVI, i), &IVI);1616 else {1617 ValueLatticeElement InVal = getValueState(Val);1618 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);1619 }1620 }1621}1622 1623void SCCPInstVisitor::visitSelectInst(SelectInst &I) {1624 // If this select returns a struct, just mark the result overdefined.1625 // TODO: We could do a lot better than this if code actually uses this.1626 if (I.getType()->isStructTy())1627 return (void)markOverdefined(&I);1628 1629 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would1630 // discover a concrete value later.1631 if (ValueState[&I].isOverdefined())1632 return (void)markOverdefined(&I);1633 1634 const ValueLatticeElement &CondValue = getValueState(I.getCondition());1635 if (CondValue.isUnknownOrUndef())1636 return;1637 1638 if (ConstantInt *CondCB =1639 getConstantInt(CondValue, I.getCondition()->getType())) {1640 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();1641 const ValueLatticeElement &OpValState = getValueState(OpVal);1642 // Safety: ValueState[&I] doesn't invalidate OpValState since it is already1643 // in the map.1644 assert(ValueState.contains(&I) && "&I is not in ValueState map.");1645 mergeInValue(ValueState[&I], &I, OpValState);1646 return;1647 }1648 1649 // Otherwise, the condition is overdefined or a constant we can't evaluate.1650 // See if we can produce something better than overdefined based on the T/F1651 // value.1652 ValueLatticeElement TVal = getValueState(I.getTrueValue());1653 ValueLatticeElement FVal = getValueState(I.getFalseValue());1654 1655 ValueLatticeElement &State = ValueState[&I];1656 bool Changed = State.mergeIn(TVal);1657 Changed |= State.mergeIn(FVal);1658 if (Changed)1659 pushUsersToWorkListMsg(State, &I);1660}1661 1662// Handle Unary Operators.1663void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {1664 ValueLatticeElement V0State = getValueState(I.getOperand(0));1665 1666 ValueLatticeElement &IV = ValueState[&I];1667 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would1668 // discover a concrete value later.1669 if (IV.isOverdefined())1670 return (void)markOverdefined(&I);1671 1672 // If something is unknown/undef, wait for it to resolve.1673 if (V0State.isUnknownOrUndef())1674 return;1675 1676 if (SCCPSolver::isConstant(V0State))1677 if (Constant *C = ConstantFoldUnaryOpOperand(1678 I.getOpcode(), getConstant(V0State, I.getType()), DL))1679 return (void)markConstant(IV, &I, C);1680 1681 markOverdefined(&I);1682}1683 1684void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) {1685 // If this freeze returns a struct, just mark the result overdefined.1686 // TODO: We could do a lot better than this.1687 if (I.getType()->isStructTy())1688 return (void)markOverdefined(&I);1689 1690 ValueLatticeElement V0State = getValueState(I.getOperand(0));1691 ValueLatticeElement &IV = ValueState[&I];1692 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would1693 // discover a concrete value later.1694 if (IV.isOverdefined())1695 return (void)markOverdefined(&I);1696 1697 // If something is unknown/undef, wait for it to resolve.1698 if (V0State.isUnknownOrUndef())1699 return;1700 1701 if (SCCPSolver::isConstant(V0State) &&1702 isGuaranteedNotToBeUndefOrPoison(getConstant(V0State, I.getType())))1703 return (void)markConstant(IV, &I, getConstant(V0State, I.getType()));1704 1705 markOverdefined(&I);1706}1707 1708// Handle Binary Operators.1709void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {1710 ValueLatticeElement V1State = getValueState(I.getOperand(0));1711 ValueLatticeElement V2State = getValueState(I.getOperand(1));1712 1713 ValueLatticeElement &IV = ValueState[&I];1714 if (IV.isOverdefined())1715 return;1716 1717 // If something is undef, wait for it to resolve.1718 if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())1719 return;1720 1721 if (V1State.isOverdefined() && V2State.isOverdefined())1722 return (void)markOverdefined(&I);1723 1724 // If either of the operands is a constant, try to fold it to a constant.1725 // TODO: Use information from notconstant better.1726 if ((V1State.isConstant() || V2State.isConstant())) {1727 Value *V1 = SCCPSolver::isConstant(V1State)1728 ? getConstant(V1State, I.getOperand(0)->getType())1729 : I.getOperand(0);1730 Value *V2 = SCCPSolver::isConstant(V2State)1731 ? getConstant(V2State, I.getOperand(1)->getType())1732 : I.getOperand(1);1733 Value *R = simplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL, &I));1734 auto *C = dyn_cast_or_null<Constant>(R);1735 if (C) {1736 // Conservatively assume that the result may be based on operands that may1737 // be undef. Note that we use mergeInValue to combine the constant with1738 // the existing lattice value for I, as different constants might be found1739 // after one of the operands go to overdefined, e.g. due to one operand1740 // being a special floating value.1741 ValueLatticeElement NewV;1742 NewV.markConstant(C, /*MayIncludeUndef=*/true);1743 return (void)mergeInValue(ValueState[&I], &I, NewV);1744 }1745 }1746 1747 // Only use ranges for binary operators on integers.1748 if (!I.getType()->isIntOrIntVectorTy())1749 return markOverdefined(&I);1750 1751 // Try to simplify to a constant range.1752 ConstantRange A =1753 V1State.asConstantRange(I.getType(), /*UndefAllowed=*/false);1754 ConstantRange B =1755 V2State.asConstantRange(I.getType(), /*UndefAllowed=*/false);1756 1757 auto *BO = cast<BinaryOperator>(&I);1758 ConstantRange R = ConstantRange::getEmpty(I.getType()->getScalarSizeInBits());1759 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO))1760 R = A.overflowingBinaryOp(BO->getOpcode(), B, OBO->getNoWrapKind());1761 else1762 R = A.binaryOp(BO->getOpcode(), B);1763 mergeInValue(ValueState[&I], &I, ValueLatticeElement::getRange(R));1764 1765 // TODO: Currently we do not exploit special values that produce something1766 // better than overdefined with an overdefined operand for vector or floating1767 // point types, like and <4 x i32> overdefined, zeroinitializer.1768}1769 1770// Handle ICmpInst instruction.1771void SCCPInstVisitor::visitCmpInst(CmpInst &I) {1772 // Do not cache this lookup, getValueState calls later in the function might1773 // invalidate the reference.1774 if (ValueState[&I].isOverdefined())1775 return (void)markOverdefined(&I);1776 1777 Value *Op1 = I.getOperand(0);1778 Value *Op2 = I.getOperand(1);1779 1780 // For parameters, use ParamState which includes constant range info if1781 // available.1782 auto V1State = getValueState(Op1);1783 auto V2State = getValueState(Op2);1784 1785 Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State, DL);1786 if (C) {1787 ValueLatticeElement CV;1788 CV.markConstant(C);1789 mergeInValue(ValueState[&I], &I, CV);1790 return;1791 }1792 1793 // If operands are still unknown, wait for it to resolve.1794 if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&1795 !SCCPSolver::isConstant(ValueState[&I]))1796 return;1797 1798 markOverdefined(&I);1799}1800 1801// Handle getelementptr instructions. If all operands are constants then we1802// can turn this into a getelementptr ConstantExpr.1803void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {1804 if (ValueState[&I].isOverdefined())1805 return (void)markOverdefined(&I);1806 1807 const ValueLatticeElement &PtrState = getValueState(I.getPointerOperand());1808 if (PtrState.isUnknownOrUndef())1809 return;1810 1811 // gep inbounds/nuw of non-null is non-null.1812 if (PtrState.isNotConstant() && PtrState.getNotConstant()->isNullValue()) {1813 if (I.hasNoUnsignedWrap() ||1814 (I.isInBounds() &&1815 !NullPointerIsDefined(I.getFunction(), I.getAddressSpace())))1816 return (void)markNotNull(ValueState[&I], &I);1817 return (void)markOverdefined(&I);1818 }1819 1820 SmallVector<Constant *, 8> Operands;1821 Operands.reserve(I.getNumOperands());1822 1823 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {1824 const ValueLatticeElement &State = getValueState(I.getOperand(i));1825 if (State.isUnknownOrUndef())1826 return; // Operands are not resolved yet.1827 1828 if (Constant *C = getConstant(State, I.getOperand(i)->getType())) {1829 Operands.push_back(C);1830 continue;1831 }1832 1833 return (void)markOverdefined(&I);1834 }1835 1836 if (Constant *C = ConstantFoldInstOperands(&I, Operands, DL))1837 markConstant(&I, C);1838 else1839 markOverdefined(&I);1840}1841 1842void SCCPInstVisitor::visitAllocaInst(AllocaInst &I) {1843 if (!NullPointerIsDefined(I.getFunction(), I.getAddressSpace()))1844 return (void)markNotNull(ValueState[&I], &I);1845 1846 markOverdefined(&I);1847}1848 1849void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {1850 // If this store is of a struct, ignore it.1851 if (SI.getOperand(0)->getType()->isStructTy())1852 return;1853 1854 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))1855 return;1856 1857 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));1858 auto I = TrackedGlobals.find(GV);1859 if (I == TrackedGlobals.end())1860 return;1861 1862 // Get the value we are storing into the global, then merge it.1863 mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),1864 ValueLatticeElement::MergeOptions().setCheckWiden(false));1865 if (I->second.isOverdefined())1866 TrackedGlobals.erase(I); // No need to keep tracking this!1867}1868 1869static ValueLatticeElement getValueFromMetadata(const Instruction *I) {1870 if (const auto *CB = dyn_cast<CallBase>(I)) {1871 if (CB->getType()->isIntOrIntVectorTy())1872 if (std::optional<ConstantRange> Range = CB->getRange())1873 return ValueLatticeElement::getRange(*Range);1874 if (CB->getType()->isPointerTy() && CB->isReturnNonNull())1875 return ValueLatticeElement::getNot(1876 ConstantPointerNull::get(cast<PointerType>(I->getType())));1877 }1878 1879 if (I->getType()->isIntOrIntVectorTy())1880 if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))1881 return ValueLatticeElement::getRange(1882 getConstantRangeFromMetadata(*Ranges));1883 if (I->hasMetadata(LLVMContext::MD_nonnull))1884 return ValueLatticeElement::getNot(1885 ConstantPointerNull::get(cast<PointerType>(I->getType())));1886 1887 return ValueLatticeElement::getOverdefined();1888}1889 1890// Handle load instructions. If the operand is a constant pointer to a constant1891// global, we can replace the load with the loaded constant value!1892void SCCPInstVisitor::visitLoadInst(LoadInst &I) {1893 // If this load is of a struct or the load is volatile, just mark the result1894 // as overdefined.1895 if (I.getType()->isStructTy() || I.isVolatile())1896 return (void)markOverdefined(&I);1897 1898 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would1899 // discover a concrete value later.1900 if (ValueState[&I].isOverdefined())1901 return (void)markOverdefined(&I);1902 1903 const ValueLatticeElement &PtrVal = getValueState(I.getOperand(0));1904 if (PtrVal.isUnknownOrUndef())1905 return; // The pointer is not resolved yet!1906 1907 if (SCCPSolver::isConstant(PtrVal)) {1908 Constant *Ptr = getConstant(PtrVal, I.getOperand(0)->getType());1909 ValueLatticeElement &IV = ValueState[&I];1910 1911 // load null is undefined.1912 if (isa<ConstantPointerNull>(Ptr)) {1913 if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))1914 return (void)markOverdefined(IV, &I);1915 else1916 return;1917 }1918 1919 // Transform load (constant global) into the value loaded.1920 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {1921 if (!TrackedGlobals.empty()) {1922 // If we are tracking this global, merge in the known value for it.1923 auto It = TrackedGlobals.find(GV);1924 if (It != TrackedGlobals.end()) {1925 mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts());1926 return;1927 }1928 }1929 }1930 1931 // Transform load from a constant into a constant if possible.1932 if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL))1933 return (void)markConstant(IV, &I, C);1934 }1935 1936 // Fall back to metadata.1937 mergeInValue(ValueState[&I], &I, getValueFromMetadata(&I));1938}1939 1940void SCCPInstVisitor::visitCallBase(CallBase &CB) {1941 handleCallResult(CB);1942 handleCallArguments(CB);1943}1944 1945void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {1946 Function *F = CB.getCalledFunction();1947 1948 // Void return and not tracking callee, just bail.1949 if (CB.getType()->isVoidTy())1950 return;1951 1952 // Always mark struct return as overdefined.1953 if (CB.getType()->isStructTy())1954 return (void)markOverdefined(&CB);1955 1956 // Otherwise, if we have a single return value case, and if the function is1957 // a declaration, maybe we can constant fold it.1958 if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {1959 SmallVector<Constant *, 8> Operands;1960 for (const Use &A : CB.args()) {1961 if (A.get()->getType()->isStructTy())1962 return markOverdefined(&CB); // Can't handle struct args.1963 if (A.get()->getType()->isMetadataTy())1964 continue; // Carried in CB, not allowed in Operands.1965 const ValueLatticeElement &State = getValueState(A);1966 1967 if (State.isUnknownOrUndef())1968 return; // Operands are not resolved yet.1969 if (SCCPSolver::isOverdefined(State))1970 return (void)markOverdefined(&CB);1971 assert(SCCPSolver::isConstant(State) && "Unknown state!");1972 Operands.push_back(getConstant(State, A->getType()));1973 }1974 1975 if (SCCPSolver::isOverdefined(getValueState(&CB)))1976 return (void)markOverdefined(&CB);1977 1978 // If we can constant fold this, mark the result of the call as a1979 // constant.1980 if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F)))1981 return (void)markConstant(&CB, C);1982 }1983 1984 // Fall back to metadata.1985 mergeInValue(ValueState[&CB], &CB, getValueFromMetadata(&CB));1986}1987 1988void SCCPInstVisitor::handleCallArguments(CallBase &CB) {1989 Function *F = CB.getCalledFunction();1990 // If this is a local function that doesn't have its address taken, mark its1991 // entry block executable and merge in the actual arguments to the call into1992 // the formal arguments of the function.1993 if (TrackingIncomingArguments.count(F)) {1994 markBlockExecutable(&F->front());1995 1996 // Propagate information from this call site into the callee.1997 auto CAI = CB.arg_begin();1998 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;1999 ++AI, ++CAI) {2000 // If this argument is byval, and if the function is not readonly, there2001 // will be an implicit copy formed of the input aggregate.2002 if (AI->hasByValAttr() && !F->onlyReadsMemory()) {2003 markOverdefined(&*AI);2004 continue;2005 }2006 2007 if (auto *STy = dyn_cast<StructType>(AI->getType())) {2008 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {2009 ValueLatticeElement CallArg = getStructValueState(*CAI, i);2010 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,2011 getMaxWidenStepsOpts());2012 }2013 } else {2014 ValueLatticeElement CallArg =2015 getValueState(*CAI).intersect(getArgAttributeVL(&*AI));2016 mergeInValue(ValueState[&*AI], &*AI, CallArg, getMaxWidenStepsOpts());2017 }2018 }2019 }2020}2021 2022void SCCPInstVisitor::handlePredicate(Instruction *I, Value *CopyOf,2023 const PredicateBase *PI) {2024 ValueLatticeElement CopyOfVal = getValueState(CopyOf);2025 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();2026 if (!Constraint) {2027 mergeInValue(ValueState[I], I, CopyOfVal);2028 return;2029 }2030 2031 CmpInst::Predicate Pred = Constraint->Predicate;2032 Value *OtherOp = Constraint->OtherOp;2033 2034 // Wait until OtherOp is resolved.2035 if (getValueState(OtherOp).isUnknown()) {2036 addAdditionalUser(OtherOp, I);2037 return;2038 }2039 2040 ValueLatticeElement CondVal = getValueState(OtherOp);2041 ValueLatticeElement &IV = ValueState[I];2042 if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {2043 auto ImposedCR =2044 ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));2045 2046 // Get the range imposed by the condition.2047 if (CondVal.isConstantRange())2048 ImposedCR = ConstantRange::makeAllowedICmpRegion(2049 Pred, CondVal.getConstantRange());2050 2051 // Combine range info for the original value with the new range from the2052 // condition.2053 auto CopyOfCR = CopyOfVal.asConstantRange(CopyOf->getType(),2054 /*UndefAllowed=*/true);2055 // Treat an unresolved input like a full range.2056 if (CopyOfCR.isEmptySet())2057 CopyOfCR = ConstantRange::getFull(CopyOfCR.getBitWidth());2058 auto NewCR = ImposedCR.intersectWith(CopyOfCR);2059 // If the existing information is != x, do not use the information from2060 // a chained predicate, as the != x information is more likely to be2061 // helpful in practice.2062 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())2063 NewCR = CopyOfCR;2064 2065 // The new range is based on a branch condition. That guarantees that2066 // neither of the compare operands can be undef in the branch targets,2067 // unless we have conditions that are always true/false (e.g. icmp ule2068 // i32, %a, i32_max). For the latter overdefined/empty range will be2069 // inferred, but the branch will get folded accordingly anyways.2070 addAdditionalUser(OtherOp, I);2071 mergeInValue(2072 IV, I, ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef*/ false));2073 return;2074 } else if (Pred == CmpInst::ICMP_EQ &&2075 (CondVal.isConstant() || CondVal.isNotConstant())) {2076 // For non-integer values or integer constant expressions, only2077 // propagate equal constants or not-constants.2078 addAdditionalUser(OtherOp, I);2079 mergeInValue(IV, I, CondVal);2080 return;2081 } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {2082 // Propagate inequalities.2083 addAdditionalUser(OtherOp, I);2084 mergeInValue(IV, I, ValueLatticeElement::getNot(CondVal.getConstant()));2085 return;2086 }2087 2088 return (void)mergeInValue(IV, I, CopyOfVal);2089}2090 2091void SCCPInstVisitor::handleCallResult(CallBase &CB) {2092 Function *F = CB.getCalledFunction();2093 2094 if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {2095 if (II->getIntrinsicID() == Intrinsic::vscale) {2096 unsigned BitWidth = CB.getType()->getScalarSizeInBits();2097 const ConstantRange Result = getVScaleRange(II->getFunction(), BitWidth);2098 return (void)mergeInValue(ValueState[II], II,2099 ValueLatticeElement::getRange(Result));2100 }2101 if (II->getIntrinsicID() == Intrinsic::experimental_get_vector_length) {2102 Value *CountArg = II->getArgOperand(0);2103 Value *VF = II->getArgOperand(1);2104 bool Scalable = cast<ConstantInt>(II->getArgOperand(2))->isOne();2105 2106 // Computation happens in the larger type.2107 unsigned BitWidth = std::max(CountArg->getType()->getScalarSizeInBits(),2108 VF->getType()->getScalarSizeInBits());2109 2110 ConstantRange Count = getValueState(CountArg)2111 .asConstantRange(CountArg->getType(), false)2112 .zeroExtend(BitWidth);2113 ConstantRange MaxLanes = getValueState(VF)2114 .asConstantRange(VF->getType(), false)2115 .zeroExtend(BitWidth);2116 if (Scalable)2117 MaxLanes =2118 MaxLanes.multiply(getVScaleRange(II->getFunction(), BitWidth));2119 2120 // The result is always less than both Count and MaxLanes.2121 ConstantRange Result(2122 APInt::getZero(BitWidth),2123 APIntOps::umin(Count.getUpper(), MaxLanes.getUpper()));2124 2125 // If Count <= MaxLanes, getvectorlength(Count, MaxLanes) = Count2126 if (Count.icmp(CmpInst::ICMP_ULE, MaxLanes))2127 Result = Count;2128 2129 Result = Result.truncate(II->getType()->getScalarSizeInBits());2130 return (void)mergeInValue(ValueState[II], II,2131 ValueLatticeElement::getRange(Result));2132 }2133 2134 if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {2135 // Compute result range for intrinsics supported by ConstantRange.2136 // Do this even if we don't know a range for all operands, as we may2137 // still know something about the result range, e.g. of abs(x).2138 SmallVector<ConstantRange, 2> OpRanges;2139 for (Value *Op : II->args()) {2140 const ValueLatticeElement &State = getValueState(Op);2141 if (State.isUnknownOrUndef())2142 return;2143 OpRanges.push_back(2144 State.asConstantRange(Op->getType(), /*UndefAllowed=*/false));2145 }2146 2147 ConstantRange Result =2148 ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);2149 return (void)mergeInValue(ValueState[II], II,2150 ValueLatticeElement::getRange(Result));2151 }2152 }2153 2154 // The common case is that we aren't tracking the callee, either because we2155 // are not doing interprocedural analysis or the callee is indirect, or is2156 // external. Handle these cases first.2157 if (!F || F->isDeclaration())2158 return handleCallOverdefined(CB);2159 2160 // If this is a single/zero retval case, see if we're tracking the function.2161 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {2162 if (!MRVFunctionsTracked.count(F))2163 return handleCallOverdefined(CB); // Not tracking this callee.2164 2165 // If we are tracking this callee, propagate the result of the function2166 // into this call site.2167 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)2168 mergeInValue(getStructValueState(&CB, i), &CB,2169 TrackedMultipleRetVals[std::make_pair(F, i)],2170 getMaxWidenStepsOpts());2171 } else {2172 auto TFRVI = TrackedRetVals.find(F);2173 if (TFRVI == TrackedRetVals.end())2174 return handleCallOverdefined(CB); // Not tracking this callee.2175 2176 // If so, propagate the return value of the callee into this call result.2177 mergeInValue(ValueState[&CB], &CB, TFRVI->second, getMaxWidenStepsOpts());2178 }2179}2180 2181bool SCCPInstVisitor::isInstFullyOverDefined(Instruction &Inst) {2182 // For structure Type, we handle each member separately.2183 // A structure object won't be considered as overdefined when2184 // there is at least one member that is not overdefined.2185 if (StructType *STy = dyn_cast<StructType>(Inst.getType())) {2186 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) {2187 if (!getStructValueState(&Inst, i).isOverdefined())2188 return false;2189 }2190 return true;2191 }2192 2193 return getValueState(&Inst).isOverdefined();2194}2195 2196void SCCPInstVisitor::solve() {2197 // Process the work lists until they are empty!2198 while (!BBWorkList.empty() || !InstWorkList.empty()) {2199 // Process the instruction work list.2200 while (!InstWorkList.empty()) {2201 Instruction *I = InstWorkList.pop_back_val();2202 Invalidated.erase(I);2203 2204 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');2205 2206 visit(I);2207 }2208 2209 // Process the basic block work list.2210 while (!BBWorkList.empty()) {2211 BasicBlock *BB = BBWorkList.pop_back_val();2212 BBVisited.insert(BB);2213 2214 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');2215 for (Instruction &I : *BB) {2216 CurI = &I;2217 visit(I);2218 }2219 CurI = nullptr;2220 }2221 }2222}2223 2224bool SCCPInstVisitor::resolvedUndef(Instruction &I) {2225 // Look for instructions which produce undef values.2226 if (I.getType()->isVoidTy())2227 return false;2228 2229 if (auto *STy = dyn_cast<StructType>(I.getType())) {2230 // Only a few things that can be structs matter for undef.2231 2232 // Tracked calls must never be marked overdefined in resolvedUndefsIn.2233 if (auto *CB = dyn_cast<CallBase>(&I))2234 if (Function *F = CB->getCalledFunction())2235 if (MRVFunctionsTracked.count(F))2236 return false;2237 2238 // extractvalue and insertvalue don't need to be marked; they are2239 // tracked as precisely as their operands.2240 if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))2241 return false;2242 // Send the results of everything else to overdefined. We could be2243 // more precise than this but it isn't worth bothering.2244 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {2245 ValueLatticeElement &LV = getStructValueState(&I, i);2246 if (LV.isUnknown()) {2247 markOverdefined(LV, &I);2248 return true;2249 }2250 }2251 return false;2252 }2253 2254 ValueLatticeElement &LV = getValueState(&I);2255 if (!LV.isUnknown())2256 return false;2257 2258 // There are two reasons a call can have an undef result2259 // 1. It could be tracked.2260 // 2. It could be constant-foldable.2261 // Because of the way we solve return values, tracked calls must2262 // never be marked overdefined in resolvedUndefsIn.2263 if (auto *CB = dyn_cast<CallBase>(&I))2264 if (Function *F = CB->getCalledFunction())2265 if (TrackedRetVals.count(F))2266 return false;2267 2268 if (isa<LoadInst>(I)) {2269 // A load here means one of two things: a load of undef from a global,2270 // a load from an unknown pointer. Either way, having it return undef2271 // is okay.2272 return false;2273 }2274 2275 markOverdefined(&I);2276 return true;2277}2278 2279/// While solving the dataflow for a function, we don't compute a result for2280/// operations with an undef operand, to allow undef to be lowered to a2281/// constant later. For example, constant folding of "zext i8 undef to i16"2282/// would result in "i16 0", and if undef is later lowered to "i8 1", then the2283/// zext result would become "i16 1" and would result into an overdefined2284/// lattice value once merged with the previous result. Not computing the2285/// result of the zext (treating undef the same as unknown) allows us to handle2286/// a later undef->constant lowering more optimally.2287///2288/// However, if the operand remains undef when the solver returns, we do need2289/// to assign some result to the instruction (otherwise we would treat it as2290/// unreachable). For simplicity, we mark any instructions that are still2291/// unknown as overdefined.2292bool SCCPInstVisitor::resolvedUndefsIn(Function &F) {2293 bool MadeChange = false;2294 for (BasicBlock &BB : F) {2295 if (!BBExecutable.count(&BB))2296 continue;2297 2298 for (Instruction &I : BB)2299 MadeChange |= resolvedUndef(I);2300 }2301 2302 LLVM_DEBUG(if (MadeChange) dbgs()2303 << "\nResolved undefs in " << F.getName() << '\n');2304 2305 return MadeChange;2306}2307 2308//===----------------------------------------------------------------------===//2309//2310// SCCPSolver implementations2311//2312SCCPSolver::SCCPSolver(2313 const DataLayout &DL,2314 std::function<const TargetLibraryInfo &(Function &)> GetTLI,2315 LLVMContext &Ctx)2316 : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}2317 2318SCCPSolver::~SCCPSolver() = default;2319 2320void SCCPSolver::addPredicateInfo(Function &F, DominatorTree &DT,2321 AssumptionCache &AC) {2322 Visitor->addPredicateInfo(F, DT, AC);2323}2324 2325void SCCPSolver::removeSSACopies(Function &F) {2326 Visitor->removeSSACopies(F);2327}2328 2329bool SCCPSolver::markBlockExecutable(BasicBlock *BB) {2330 return Visitor->markBlockExecutable(BB);2331}2332 2333const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) {2334 return Visitor->getPredicateInfoFor(I);2335}2336 2337void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) {2338 Visitor->trackValueOfGlobalVariable(GV);2339}2340 2341void SCCPSolver::addTrackedFunction(Function *F) {2342 Visitor->addTrackedFunction(F);2343}2344 2345void SCCPSolver::addToMustPreserveReturnsInFunctions(Function *F) {2346 Visitor->addToMustPreserveReturnsInFunctions(F);2347}2348 2349bool SCCPSolver::mustPreserveReturn(Function *F) {2350 return Visitor->mustPreserveReturn(F);2351}2352 2353void SCCPSolver::addArgumentTrackedFunction(Function *F) {2354 Visitor->addArgumentTrackedFunction(F);2355}2356 2357bool SCCPSolver::isArgumentTrackedFunction(Function *F) {2358 return Visitor->isArgumentTrackedFunction(F);2359}2360 2361const SmallPtrSetImpl<Function *> &2362SCCPSolver::getArgumentTrackedFunctions() const {2363 return Visitor->getArgumentTrackedFunctions();2364}2365 2366void SCCPSolver::solve() { Visitor->solve(); }2367 2368bool SCCPSolver::resolvedUndefsIn(Function &F) {2369 return Visitor->resolvedUndefsIn(F);2370}2371 2372void SCCPSolver::solveWhileResolvedUndefsIn(Module &M) {2373 Visitor->solveWhileResolvedUndefsIn(M);2374}2375 2376void2377SCCPSolver::solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {2378 Visitor->solveWhileResolvedUndefsIn(WorkList);2379}2380 2381void SCCPSolver::solveWhileResolvedUndefs() {2382 Visitor->solveWhileResolvedUndefs();2383}2384 2385bool SCCPSolver::isBlockExecutable(BasicBlock *BB) const {2386 return Visitor->isBlockExecutable(BB);2387}2388 2389bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {2390 return Visitor->isEdgeFeasible(From, To);2391}2392 2393std::vector<ValueLatticeElement>2394SCCPSolver::getStructLatticeValueFor(Value *V) const {2395 return Visitor->getStructLatticeValueFor(V);2396}2397 2398void SCCPSolver::removeLatticeValueFor(Value *V) {2399 return Visitor->removeLatticeValueFor(V);2400}2401 2402void SCCPSolver::resetLatticeValueFor(CallBase *Call) {2403 Visitor->resetLatticeValueFor(Call);2404}2405 2406const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const {2407 return Visitor->getLatticeValueFor(V);2408}2409 2410const MapVector<Function *, ValueLatticeElement> &2411SCCPSolver::getTrackedRetVals() const {2412 return Visitor->getTrackedRetVals();2413}2414 2415const DenseMap<GlobalVariable *, ValueLatticeElement> &2416SCCPSolver::getTrackedGlobals() const {2417 return Visitor->getTrackedGlobals();2418}2419 2420const SmallPtrSet<Function *, 16> &SCCPSolver::getMRVFunctionsTracked() const {2421 return Visitor->getMRVFunctionsTracked();2422}2423 2424void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }2425 2426void SCCPSolver::trackValueOfArgument(Argument *V) {2427 Visitor->trackValueOfArgument(V);2428}2429 2430bool SCCPSolver::isStructLatticeConstant(Function *F, StructType *STy) {2431 return Visitor->isStructLatticeConstant(F, STy);2432}2433 2434Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV,2435 Type *Ty) const {2436 return Visitor->getConstant(LV, Ty);2437}2438 2439Constant *SCCPSolver::getConstantOrNull(Value *V) const {2440 return Visitor->getConstantOrNull(V);2441}2442 2443void SCCPSolver::setLatticeValueForSpecializationArguments(Function *F,2444 const SmallVectorImpl<ArgInfo> &Args) {2445 Visitor->setLatticeValueForSpecializationArguments(F, Args);2446}2447 2448void SCCPSolver::markFunctionUnreachable(Function *F) {2449 Visitor->markFunctionUnreachable(F);2450}2451 2452void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }2453 2454void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }2455