diff options
Diffstat (limited to 'lib/Transforms/Scalar/SCCP.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/SCCP.cpp | 556 |
1 files changed, 252 insertions, 304 deletions
diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 66608ec631f6..5e3ddeda2d49 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -17,7 +17,6 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/IPO/SCCP.h" #include "llvm/Transforms/Scalar/SCCP.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" @@ -30,6 +29,7 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueLattice.h" #include "llvm/Analysis/ValueLatticeUtils.h" #include "llvm/IR/BasicBlock.h" @@ -54,9 +54,7 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/IPO.h" #include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/Local.h" #include <cassert> #include <utility> #include <vector> @@ -71,8 +69,6 @@ STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); -STATISTIC(IPNumRangeInfoUsed, "Number of times constant range info was used by" - "IPSCCP"); namespace { @@ -223,6 +219,10 @@ class SCCPSolver : public InstVisitor<SCCPSolver> { /// represented here for efficient lookup. SmallPtrSet<Function *, 16> MRVFunctionsTracked; + /// MustTailFunctions - Each function here is a callee of non-removable + /// musttail call site. + SmallPtrSet<Function *, 16> MustTailCallees; + /// TrackingIncomingArguments - This is the set of functions for whose /// arguments we make optimistic assumptions about and try to prove as /// constants. @@ -257,7 +257,7 @@ public: bool MarkBlockExecutable(BasicBlock *BB) { if (!BBExecutable.insert(BB).second) return false; - DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); + LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); BBWorkList.push_back(BB); // Add the block to the work list! return true; } @@ -289,6 +289,18 @@ public: TrackedRetVals.insert(std::make_pair(F, LatticeVal())); } + /// AddMustTailCallee - If the SCCP solver finds that this function is called + /// from non-removable musttail call site. + void AddMustTailCallee(Function *F) { + MustTailCallees.insert(F); + } + + /// Returns true if the given function is called from non-removable musttail + /// call site. + bool isMustTailCallee(Function *F) { + return MustTailCallees.count(F); + } + void AddArgumentTrackedFunction(Function *F) { TrackingIncomingArguments.insert(F); } @@ -313,6 +325,10 @@ public: return BBExecutable.count(BB); } + // isEdgeFeasible - Return true if the control flow edge from the 'From' basic + // block to the 'To' basic block is currently feasible. + bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); + std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const { std::vector<LatticeVal> StructValues; auto *STy = dyn_cast<StructType>(V->getType()); @@ -325,20 +341,13 @@ public: return StructValues; } - ValueLatticeElement getLatticeValueFor(Value *V) { + const LatticeVal &getLatticeValueFor(Value *V) const { assert(!V->getType()->isStructTy() && "Should use getStructLatticeValueFor"); - std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool> - PI = ParamState.insert(std::make_pair(V, ValueLatticeElement())); - ValueLatticeElement &LV = PI.first->second; - if (PI.second) { - DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V); - assert(I != ValueState.end() && - "V not found in ValueState nor Paramstate map!"); - LV = I->second.toValueLattice(); - } - - return LV; + DenseMap<Value *, LatticeVal>::const_iterator I = ValueState.find(V); + assert(I != ValueState.end() && + "V not found in ValueState nor Paramstate map!"); + return I->second; } /// getTrackedRetVals - Get the inferred return value map. @@ -358,6 +367,12 @@ public: return MRVFunctionsTracked; } + /// getMustTailCallees - Get the set of functions which are called + /// from non-removable musttail call sites. + const SmallPtrSet<Function *, 16> getMustTailCallees() { + return MustTailCallees; + } + /// markOverdefined - Mark the specified value overdefined. This /// works with both scalars and structs. void markOverdefined(Value *V) { @@ -393,55 +408,57 @@ private: // markConstant - Make a value be marked as "constant". If the value // is not already a constant, add it to the instruction work list so that // the users of the instruction are updated later. - void markConstant(LatticeVal &IV, Value *V, Constant *C) { - if (!IV.markConstant(C)) return; - DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); + bool markConstant(LatticeVal &IV, Value *V, Constant *C) { + if (!IV.markConstant(C)) return false; + LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); pushToWorkList(IV, V); + return true; } - void markConstant(Value *V, Constant *C) { + bool markConstant(Value *V, Constant *C) { assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); - markConstant(ValueState[V], V, C); + return markConstant(ValueState[V], V, C); } void markForcedConstant(Value *V, Constant *C) { assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); LatticeVal &IV = ValueState[V]; IV.markForcedConstant(C); - DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); + LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); pushToWorkList(IV, V); } // markOverdefined - Make a value be marked as "overdefined". If the // value is not already overdefined, add it to the overdefined instruction // work list so that the users of the instruction are updated later. - void markOverdefined(LatticeVal &IV, Value *V) { - if (!IV.markOverdefined()) return; - - DEBUG(dbgs() << "markOverdefined: "; - if (auto *F = dyn_cast<Function>(V)) - dbgs() << "Function '" << F->getName() << "'\n"; - else - dbgs() << *V << '\n'); + bool markOverdefined(LatticeVal &IV, Value *V) { + if (!IV.markOverdefined()) return false; + + LLVM_DEBUG(dbgs() << "markOverdefined: "; + if (auto *F = dyn_cast<Function>(V)) dbgs() + << "Function '" << F->getName() << "'\n"; + else dbgs() << *V << '\n'); // Only instructions go on the work list pushToWorkList(IV, V); + return true; } - void mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { + bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { if (IV.isOverdefined() || MergeWithV.isUnknown()) - return; // Noop. + return false; // Noop. if (MergeWithV.isOverdefined()) return markOverdefined(IV, V); if (IV.isUnknown()) return markConstant(IV, V, MergeWithV.getConstant()); if (IV.getConstant() != MergeWithV.getConstant()) return markOverdefined(IV, V); + return false; } - void mergeInValue(Value *V, LatticeVal MergeWithV) { + bool mergeInValue(Value *V, LatticeVal MergeWithV) { assert(!V->getType()->isStructTy() && "non-structs should use markConstant"); - mergeInValue(ValueState[V], V, MergeWithV); + return mergeInValue(ValueState[V], V, MergeWithV); } /// getValueState - Return the LatticeVal object that corresponds to the @@ -512,32 +529,27 @@ private: /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB /// work list if it is not already executable. - void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { + bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) - return; // This edge is already known to be executable! + return false; // This edge is already known to be executable! if (!MarkBlockExecutable(Dest)) { // If the destination is already executable, we just made an *edge* // feasible that wasn't before. Revisit the PHI nodes in the block // because they have potentially new operands. - DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() - << " -> " << Dest->getName() << '\n'); + LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() + << " -> " << Dest->getName() << '\n'); - PHINode *PN; - for (BasicBlock::iterator I = Dest->begin(); - (PN = dyn_cast<PHINode>(I)); ++I) - visitPHINode(*PN); + for (PHINode &PN : Dest->phis()) + visitPHINode(PN); } + return true; } // getFeasibleSuccessors - Return a vector of booleans to indicate which // successors are reachable from a given terminator instruction. void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs); - // isEdgeFeasible - Return true if the control flow edge from the 'From' basic - // block to the 'To' basic block is currently feasible. - bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); - // OperandChangedState - This method is invoked on all of the users of an // instruction that was just changed state somehow. Based on this // information, we need to update the specified user of this instruction. @@ -594,7 +606,7 @@ private: void visitInstruction(Instruction &I) { // All the instructions we don't do any special handling for just // go to overdefined. - DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n'); + LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n'); markOverdefined(&I); } }; @@ -681,68 +693,17 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, return; } - DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n'); + LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n'); llvm_unreachable("SCCP: Don't know how to handle this terminator!"); } // isEdgeFeasible - Return true if the control flow edge from the 'From' basic // block to the 'To' basic block is currently feasible. bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { - assert(BBExecutable.count(To) && "Dest should always be alive!"); - - // Make sure the source basic block is executable!! - if (!BBExecutable.count(From)) return false; - - // Check to make sure this edge itself is actually feasible now. - TerminatorInst *TI = From->getTerminator(); - if (auto *BI = dyn_cast<BranchInst>(TI)) { - if (BI->isUnconditional()) - return true; - - LatticeVal BCValue = getValueState(BI->getCondition()); - - // Overdefined condition variables mean the branch could go either way, - // undef conditions mean that neither edge is feasible yet. - ConstantInt *CI = BCValue.getConstantInt(); - if (!CI) - return !BCValue.isUnknown(); - - // Constant condition variables mean the branch can only go a single way. - return BI->getSuccessor(CI->isZero()) == To; - } - - // Unwinding instructions successors are always executable. - if (TI->isExceptional()) - return true; - - if (auto *SI = dyn_cast<SwitchInst>(TI)) { - if (SI->getNumCases() < 1) - return true; - - LatticeVal SCValue = getValueState(SI->getCondition()); - ConstantInt *CI = SCValue.getConstantInt(); - - if (!CI) - return !SCValue.isUnknown(); - - return SI->findCaseValue(CI)->getCaseSuccessor() == To; - } - - // In case of indirect branch and its address is a blockaddress, we mark - // the target as executable. - if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) { - LatticeVal IBRValue = getValueState(IBR->getAddress()); - BlockAddress *Addr = IBRValue.getBlockAddress(); - - if (!Addr) - return !IBRValue.isUnknown(); - - // At this point, the indirectbr is branching on a blockaddress. - return Addr->getBasicBlock() == To; - } - - DEBUG(dbgs() << "Unknown terminator instruction: " << *TI << '\n'); - llvm_unreachable("SCCP: Don't know how to handle this terminator!"); + // Check if we've called markEdgeExecutable on the edge yet. (We could + // be more aggressive and try to consider edges which haven't been marked + // yet, but there isn't any need.) + return KnownFeasibleEdges.count(Edge(From, To)); } // visit Implementations - Something changed in this instruction, either an @@ -766,7 +727,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // If this PN returns a struct, just mark the result overdefined. // TODO: We could do a lot better than this if code actually uses this. if (PN.getType()->isStructTy()) - return markOverdefined(&PN); + return (void)markOverdefined(&PN); if (getValueState(&PN).isOverdefined()) return; // Quick exit @@ -774,7 +735,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, // and slow us down a lot. Just mark them overdefined. if (PN.getNumIncomingValues() > 64) - return markOverdefined(&PN); + return (void)markOverdefined(&PN); // Look at all of the executable operands of the PHI node. If any of them // are overdefined, the PHI becomes overdefined as well. If they are all @@ -790,7 +751,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { continue; if (IV.isOverdefined()) // PHI node becomes overdefined! - return markOverdefined(&PN); + return (void)markOverdefined(&PN); if (!OperandVal) { // Grab the first value. OperandVal = IV.getConstant(); @@ -804,7 +765,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // Check to see if there are two different constants merging, if so, the PHI // node is overdefined. if (IV.getConstant() != OperandVal) - return markOverdefined(&PN); + return (void)markOverdefined(&PN); } // If we exited the loop, this means that the PHI node only has constant @@ -872,11 +833,11 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { // If this returns a struct, mark all elements over defined, we don't track // structs in structs. if (EVI.getType()->isStructTy()) - return markOverdefined(&EVI); + return (void)markOverdefined(&EVI); // If this is extracting from more than one level of struct, we don't know. if (EVI.getNumIndices() != 1) - return markOverdefined(&EVI); + return (void)markOverdefined(&EVI); Value *AggVal = EVI.getAggregateOperand(); if (AggVal->getType()->isStructTy()) { @@ -885,19 +846,19 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { mergeInValue(getValueState(&EVI), &EVI, EltVal); } else { // Otherwise, must be extracting from an array. - return markOverdefined(&EVI); + return (void)markOverdefined(&EVI); } } void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { auto *STy = dyn_cast<StructType>(IVI.getType()); if (!STy) - return markOverdefined(&IVI); + return (void)markOverdefined(&IVI); // If this has more than one index, we can't handle it, drive all results to // undef. if (IVI.getNumIndices() != 1) - return markOverdefined(&IVI); + return (void)markOverdefined(&IVI); Value *Aggr = IVI.getAggregateOperand(); unsigned Idx = *IVI.idx_begin(); @@ -926,7 +887,7 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { // If this select returns a struct, just mark the result overdefined. // TODO: We could do a lot better than this if code actually uses this. if (I.getType()->isStructTy()) - return markOverdefined(&I); + return (void)markOverdefined(&I); LatticeVal CondValue = getValueState(I.getCondition()); if (CondValue.isUnknown()) @@ -947,12 +908,12 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { // select ?, C, C -> C. if (TVal.isConstant() && FVal.isConstant() && TVal.getConstant() == FVal.getConstant()) - return markConstant(&I, FVal.getConstant()); + return (void)markConstant(&I, FVal.getConstant()); if (TVal.isUnknown()) // select ?, undef, X -> X. - return mergeInValue(&I, FVal); + return (void)mergeInValue(&I, FVal); if (FVal.isUnknown()) // select ?, X, undef -> X. - return mergeInValue(&I, TVal); + return (void)mergeInValue(&I, TVal); markOverdefined(&I); } @@ -970,7 +931,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // X op Y -> undef. if (isa<UndefValue>(C)) return; - return markConstant(IV, &I, C); + return (void)markConstant(IV, &I, C); } // If something is undef, wait for it to resolve. @@ -983,7 +944,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // overdefined, and we can replace it with zero. if (I.getOpcode() == Instruction::UDiv || I.getOpcode() == Instruction::SDiv) if (V1State.isConstant() && V1State.getConstant()->isNullValue()) - return markConstant(IV, &I, V1State.getConstant()); + return (void)markConstant(IV, &I, V1State.getConstant()); // If this is: // -> AND/MUL with 0 @@ -1006,12 +967,12 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // X and 0 = 0 // X * 0 = 0 if (NonOverdefVal->getConstant()->isNullValue()) - return markConstant(IV, &I, NonOverdefVal->getConstant()); + return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); } else { // X or -1 = -1 if (ConstantInt *CI = NonOverdefVal->getConstantInt()) if (CI->isMinusOne()) - return markConstant(IV, &I, NonOverdefVal->getConstant()); + return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); } } } @@ -1021,22 +982,36 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // Handle ICmpInst instruction. void SCCPSolver::visitCmpInst(CmpInst &I) { - LatticeVal V1State = getValueState(I.getOperand(0)); - LatticeVal V2State = getValueState(I.getOperand(1)); - LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) return; - if (V1State.isConstant() && V2State.isConstant()) { - Constant *C = ConstantExpr::getCompare( - I.getPredicate(), V1State.getConstant(), V2State.getConstant()); + Value *Op1 = I.getOperand(0); + Value *Op2 = I.getOperand(1); + + // For parameters, use ParamState which includes constant range info if + // available. + auto V1Param = ParamState.find(Op1); + ValueLatticeElement V1State = (V1Param != ParamState.end()) + ? V1Param->second + : getValueState(Op1).toValueLattice(); + + auto V2Param = ParamState.find(Op2); + ValueLatticeElement V2State = V2Param != ParamState.end() + ? V2Param->second + : getValueState(Op2).toValueLattice(); + + Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State); + if (C) { if (isa<UndefValue>(C)) return; - return markConstant(IV, &I, C); + LatticeVal CV; + CV.markConstant(C); + mergeInValue(&I, CV); + return; } // If operands are still unknown, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined()) + if (!V1State.isOverdefined() && !V2State.isOverdefined() && !IV.isConstant()) return; markOverdefined(&I); @@ -1056,7 +1031,7 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { return; // Operands are not resolved yet. if (State.isOverdefined()) - return markOverdefined(&I); + return (void)markOverdefined(&I); assert(State.isConstant() && "Unknown state!"); Operands.push_back(State.getConstant()); @@ -1094,7 +1069,7 @@ void SCCPSolver::visitStoreInst(StoreInst &SI) { void SCCPSolver::visitLoadInst(LoadInst &I) { // If this load is of a struct, just mark the result overdefined. if (I.getType()->isStructTy()) - return markOverdefined(&I); + return (void)markOverdefined(&I); LatticeVal PtrVal = getValueState(I.getOperand(0)); if (PtrVal.isUnknown()) return; // The pointer is not resolved yet! @@ -1103,13 +1078,17 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (IV.isOverdefined()) return; if (!PtrVal.isConstant() || I.isVolatile()) - return markOverdefined(IV, &I); + return (void)markOverdefined(IV, &I); Constant *Ptr = PtrVal.getConstant(); // load null is undefined. - if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0) - return; + if (isa<ConstantPointerNull>(Ptr)) { + if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace())) + return (void)markOverdefined(IV, &I); + else + return; + } // Transform load (constant global) into the value loaded. if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) { @@ -1128,7 +1107,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) { if (isa<UndefValue>(C)) return; - return markConstant(IV, &I, C); + return (void)markConstant(IV, &I, C); } // Otherwise we cannot say for certain what value this load will produce. @@ -1160,7 +1139,7 @@ CallOverdefined: if (State.isUnknown()) return; // Operands are not resolved yet. if (State.isOverdefined()) - return markOverdefined(I); + return (void)markOverdefined(I); assert(State.isConstant() && "Unknown state!"); Operands.push_back(State.getConstant()); } @@ -1174,12 +1153,12 @@ CallOverdefined: // call -> undef. if (isa<UndefValue>(C)) return; - return markConstant(I, C); + return (void)markConstant(I, C); } } // Otherwise, we don't know anything about this call, mark it overdefined. - return markOverdefined(I); + return (void)markOverdefined(I); } // If this is a local function that doesn't have its address taken, mark its @@ -1207,8 +1186,16 @@ CallOverdefined: } else { // Most other parts of the Solver still only use the simpler value // lattice, so we propagate changes for parameters to both lattices. - getParamState(&*AI).mergeIn(getValueState(*CAI).toValueLattice(), DL); - mergeInValue(&*AI, getValueState(*CAI)); + LatticeVal ConcreteArgument = getValueState(*CAI); + bool ParamChanged = + getParamState(&*AI).mergeIn(ConcreteArgument.toValueLattice(), DL); + bool ValueChanged = mergeInValue(&*AI, ConcreteArgument); + // Add argument to work list, if the state of a parameter changes but + // ValueState does not change (because it is already overdefined there), + // We have to take changes in ParamState into account, as it is used + // when evaluating Cmp instructions. + if (!ValueChanged && ParamChanged) + pushToWorkList(ValueState[&*AI], &*AI); } } } @@ -1242,7 +1229,7 @@ void SCCPSolver::Solve() { while (!OverdefinedInstWorkList.empty()) { Value *I = OverdefinedInstWorkList.pop_back_val(); - DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n'); + LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n'); // "I" got into the work list because it either made the transition from // bottom to constant, or to overdefined. @@ -1260,7 +1247,7 @@ void SCCPSolver::Solve() { while (!InstWorkList.empty()) { Value *I = InstWorkList.pop_back_val(); - DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n'); + LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n'); // "I" got into the work list because it made the transition from undef to // constant. @@ -1280,7 +1267,7 @@ void SCCPSolver::Solve() { BasicBlock *BB = BBWorkList.back(); BBWorkList.pop_back(); - DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n'); + LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n'); // Notify all instructions in this basic block that they are newly // executable. @@ -1501,7 +1488,11 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { break; case Instruction::ICmp: // X == undef -> undef. Other comparisons get more complicated. - if (cast<ICmpInst>(&I)->isEquality()) + Op0LV = getValueState(I.getOperand(0)); + Op1LV = getValueState(I.getOperand(1)); + + if ((Op0LV.isUnknown() || Op1LV.isUnknown()) && + cast<ICmpInst>(&I)->isEquality()) break; markOverdefined(&I); return true; @@ -1546,11 +1537,14 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { } // Otherwise, it is a branch on a symbolic value which is currently - // considered to be undef. Handle this by forcing the input value to the - // branch to false. - markForcedConstant(BI->getCondition(), - ConstantInt::getFalse(TI->getContext())); - return true; + // considered to be undef. Make sure some edge is executable, so a + // branch on "undef" always flows somewhere. + // FIXME: Distinguish between dead code and an LLVM "undef" value. + BasicBlock *DefaultSuccessor = TI->getSuccessor(1); + if (markEdgeExecutable(&BB, DefaultSuccessor)) + return true; + + continue; } if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) { @@ -1571,11 +1565,15 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { } // Otherwise, it is a branch on a symbolic value which is currently - // considered to be undef. Handle this by forcing the input value to the - // branch to the first successor. - markForcedConstant(IBR->getAddress(), - BlockAddress::get(IBR->getSuccessor(0))); - return true; + // considered to be undef. Make sure some edge is executable, so a + // branch on "undef" always flows somewhere. + // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere: + // we can assume the branch has undefined behavior instead. + BasicBlock *DefaultSuccessor = IBR->getSuccessor(0); + if (markEdgeExecutable(&BB, DefaultSuccessor)) + return true; + + continue; } if (auto *SI = dyn_cast<SwitchInst>(TI)) { @@ -1590,56 +1588,19 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { return true; } - markForcedConstant(SI->getCondition(), SI->case_begin()->getCaseValue()); - return true; - } - } - - return false; -} - -static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) { - bool Changed = false; - - // Currently we only use range information for integer values. - if (!V->getType()->isIntegerTy()) - return false; - - const ValueLatticeElement &IV = Solver.getLatticeValueFor(V); - if (!IV.isConstantRange()) - return false; + // Otherwise, it is a branch on a symbolic value which is currently + // considered to be undef. Make sure some edge is executable, so a + // branch on "undef" always flows somewhere. + // FIXME: Distinguish between dead code and an LLVM "undef" value. + BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor(); + if (markEdgeExecutable(&BB, DefaultSuccessor)) + return true; - for (auto UI = V->uses().begin(), E = V->uses().end(); UI != E;) { - const Use &U = *UI++; - auto *Icmp = dyn_cast<ICmpInst>(U.getUser()); - if (!Icmp || !Solver.isBlockExecutable(Icmp->getParent())) continue; - - auto getIcmpLatticeValue = [&](Value *Op) { - if (auto *C = dyn_cast<Constant>(Op)) - return ValueLatticeElement::get(C); - return Solver.getLatticeValueFor(Op); - }; - - ValueLatticeElement A = getIcmpLatticeValue(Icmp->getOperand(0)); - ValueLatticeElement B = getIcmpLatticeValue(Icmp->getOperand(1)); - - Constant *C = nullptr; - if (A.satisfiesPredicate(Icmp->getPredicate(), B)) - C = ConstantInt::getTrue(Icmp->getType()); - else if (A.satisfiesPredicate(Icmp->getInversePredicate(), B)) - C = ConstantInt::getFalse(Icmp->getType()); - - if (C) { - Icmp->replaceAllUsesWith(C); - DEBUG(dbgs() << "Replacing " << *Icmp << " with " << *C - << ", because of range information " << A << " " << B - << "\n"); - Icmp->eraseFromParent(); - Changed = true; } } - return Changed; + + return false; } static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { @@ -1659,22 +1620,31 @@ static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { } Const = ConstantStruct::get(ST, ConstVals); } else { - const ValueLatticeElement &IV = Solver.getLatticeValueFor(V); + const LatticeVal &IV = Solver.getLatticeValueFor(V); if (IV.isOverdefined()) return false; - if (IV.isConstantRange()) { - if (IV.getConstantRange().isSingleElement()) - Const = - ConstantInt::get(V->getType(), IV.asConstantInteger().getValue()); - else - return false; - } else - Const = - IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); + Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); } assert(Const && "Constant is nullptr here!"); - DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n'); + + // Replacing `musttail` instructions with constant breaks `musttail` invariant + // unless the call itself can be removed + CallInst *CI = dyn_cast<CallInst>(V); + if (CI && CI->isMustTailCall() && !CI->isSafeToRemove()) { + CallSite CS(CI); + Function *F = CS.getCalledFunction(); + + // Don't zap returns of the callee + if (F) + Solver.AddMustTailCallee(F); + + LLVM_DEBUG(dbgs() << " Can\'t treat the result of musttail call : " << *CI + << " as a constant\n"); + return false; + } + + LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n'); // Replaces all of the uses of a variable with uses of the constant. V->replaceAllUsesWith(Const); @@ -1685,7 +1655,7 @@ static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { // and return true if the function was modified. static bool runSCCP(Function &F, const DataLayout &DL, const TargetLibraryInfo *TLI) { - DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); + LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); SCCPSolver Solver(DL, TLI); // Mark the first block of the function as being executable. @@ -1699,7 +1669,7 @@ static bool runSCCP(Function &F, const DataLayout &DL, bool ResolvedUndefs = true; while (ResolvedUndefs) { Solver.Solve(); - DEBUG(dbgs() << "RESOLVING UNDEFs\n"); + LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n"); ResolvedUndefs = Solver.ResolvedUndefsIn(F); } @@ -1711,7 +1681,7 @@ static bool runSCCP(Function &F, const DataLayout &DL, for (BasicBlock &BB : F) { if (!Solver.isBlockExecutable(&BB)) { - DEBUG(dbgs() << " BasicBlock Dead:" << BB); + LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); ++NumDeadBlocks; NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB); @@ -1748,6 +1718,7 @@ PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) { auto PA = PreservedAnalyses(); PA.preserve<GlobalsAA>(); + PA.preserveSet<CFGAnalyses>(); return PA; } @@ -1770,6 +1741,7 @@ public: void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired<TargetLibraryInfoWrapperPass>(); AU.addPreserved<GlobalsAAWrapperPass>(); + AU.setPreservesCFG(); } // runOnFunction - Run the Sparse Conditional Constant Propagation @@ -1804,14 +1776,30 @@ static void findReturnsToZap(Function &F, if (!Solver.isArgumentTrackedFunction(&F)) return; - for (BasicBlock &BB : F) + // There is a non-removable musttail call site of this function. Zapping + // returns is not allowed. + if (Solver.isMustTailCallee(&F)) { + LLVM_DEBUG(dbgs() << "Can't zap returns of the function : " << F.getName() + << " due to present musttail call of it\n"); + return; + } + + for (BasicBlock &BB : F) { + if (CallInst *CI = BB.getTerminatingMustTailCall()) { + LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present " + << "musttail call : " << *CI << "\n"); + (void)CI; + return; + } + if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator())) if (!isa<UndefValue>(RI->getOperand(0))) ReturnsToZap.push_back(RI); + } } -static bool runIPSCCP(Module &M, const DataLayout &DL, - const TargetLibraryInfo *TLI) { +bool llvm::runIPSCCP(Module &M, const DataLayout &DL, + const TargetLibraryInfo *TLI) { SCCPSolver Solver(DL, TLI); // Loop over all functions, marking arguments to those with their addresses @@ -1851,13 +1839,17 @@ static bool runIPSCCP(Module &M, const DataLayout &DL, // Solve for constants. bool ResolvedUndefs = true; + Solver.Solve(); while (ResolvedUndefs) { - Solver.Solve(); - - DEBUG(dbgs() << "RESOLVING UNDEFS\n"); + LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n"); ResolvedUndefs = false; for (Function &F : M) - ResolvedUndefs |= Solver.ResolvedUndefsIn(F); + if (Solver.ResolvedUndefsIn(F)) { + // We run Solve() after we resolved an undef in a function, because + // we might deduce a fact that eliminates an undef in another function. + Solver.Solve(); + ResolvedUndefs = true; + } } bool MadeChanges = false; @@ -1877,18 +1869,12 @@ static bool runIPSCCP(Module &M, const DataLayout &DL, ++IPNumArgsElimed; continue; } - - if (!AI->use_empty() && tryToReplaceWithConstantRange(Solver, &*AI)) - ++IPNumRangeInfoUsed; } for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (!Solver.isBlockExecutable(&*BB)) { - DEBUG(dbgs() << " BasicBlock Dead:" << *BB); - + LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB); ++NumDeadBlocks; - NumInstRemoved += - changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false); MadeChanges = true; @@ -1902,7 +1888,7 @@ static bool runIPSCCP(Module &M, const DataLayout &DL, if (Inst->getType()->isVoidTy()) continue; if (tryToReplaceWithConstant(Solver, Inst)) { - if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst)) + if (Inst->isSafeToRemove()) Inst->eraseFromParent(); // Hey, we just changed something! MadeChanges = true; @@ -1911,6 +1897,17 @@ static bool runIPSCCP(Module &M, const DataLayout &DL, } } + // Change dead blocks to unreachable. We do it after replacing constants in + // all executable blocks, because changeToUnreachable may remove PHI nodes + // in executable blocks we found values for. The function's entry block is + // not part of BlocksToErase, so we have to handle it separately. + for (BasicBlock *BB : BlocksToErase) + NumInstRemoved += + changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false); + if (!Solver.isBlockExecutable(&F.front())) + NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), + /*UseLLVMTrap=*/false); + // Now that all instructions in the function are constant folded, erase dead // blocks, because we can now use ConstantFoldTerminator to get rid of // in-edges. @@ -1930,31 +1927,33 @@ static bool runIPSCCP(Module &M, const DataLayout &DL, bool Folded = ConstantFoldTerminator(I->getParent()); if (!Folded) { - // The constant folder may not have been able to fold the terminator - // if this is a branch or switch on undef. Fold it manually as a - // branch to the first successor. -#ifndef NDEBUG - if (auto *BI = dyn_cast<BranchInst>(I)) { - assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) && - "Branch should be foldable!"); - } else if (auto *SI = dyn_cast<SwitchInst>(I)) { - assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold"); + // If the branch can't be folded, we must have forced an edge + // for an indeterminate value. Force the terminator to fold + // to that edge. + Constant *C; + BasicBlock *Dest; + if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { + Dest = SI->case_begin()->getCaseSuccessor(); + C = SI->case_begin()->getCaseValue(); + } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) { + Dest = BI->getSuccessor(1); + C = ConstantInt::getFalse(BI->getContext()); + } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) { + Dest = IBR->getSuccessor(0); + C = BlockAddress::get(IBR->getSuccessor(0)); } else { - llvm_unreachable("Didn't fold away reference to block!"); + llvm_unreachable("Unexpected terminator instruction"); } -#endif + assert(Solver.isEdgeFeasible(I->getParent(), Dest) && + "Didn't find feasible edge?"); + (void)Dest; - // Make this an uncond branch to the first successor. - TerminatorInst *TI = I->getParent()->getTerminator(); - BranchInst::Create(TI->getSuccessor(0), TI); - - // Remove entries in successor phi nodes to remove edges. - for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) - TI->getSuccessor(i)->removePredecessor(TI->getParent()); - - // Remove the old terminator. - TI->eraseFromParent(); + I->setOperand(0, C); + Folded = ConstantFoldTerminator(I->getParent()); } + assert(Folded && + "Expect TermInst on constantint or blockaddress to be folded"); + (void) Folded; } // Finally, delete the basic block. @@ -2005,7 +2004,8 @@ static bool runIPSCCP(Module &M, const DataLayout &DL, GlobalVariable *GV = I->first; assert(!I->second.isOverdefined() && "Overdefined values should have been taken out of the map!"); - DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n"); + LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName() + << "' is constant!\n"); while (!GV->use_empty()) { StoreInst *SI = cast<StoreInst>(GV->user_back()); SI->eraseFromParent(); @@ -2016,55 +2016,3 @@ static bool runIPSCCP(Module &M, const DataLayout &DL, return MadeChanges; } - -PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) { - const DataLayout &DL = M.getDataLayout(); - auto &TLI = AM.getResult<TargetLibraryAnalysis>(M); - if (!runIPSCCP(M, DL, &TLI)) - return PreservedAnalyses::all(); - return PreservedAnalyses::none(); -} - -namespace { - -//===--------------------------------------------------------------------===// -// -/// IPSCCP Class - This class implements interprocedural Sparse Conditional -/// Constant Propagation. -/// -class IPSCCPLegacyPass : public ModulePass { -public: - static char ID; - - IPSCCPLegacyPass() : ModulePass(ID) { - initializeIPSCCPLegacyPassPass(*PassRegistry::getPassRegistry()); - } - - bool runOnModule(Module &M) override { - if (skipModule(M)) - return false; - const DataLayout &DL = M.getDataLayout(); - const TargetLibraryInfo *TLI = - &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); - return runIPSCCP(M, DL, TLI); - } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired<TargetLibraryInfoWrapperPass>(); - } -}; - -} // end anonymous namespace - -char IPSCCPLegacyPass::ID = 0; - -INITIALIZE_PASS_BEGIN(IPSCCPLegacyPass, "ipsccp", - "Interprocedural Sparse Conditional Constant Propagation", - false, false) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_END(IPSCCPLegacyPass, "ipsccp", - "Interprocedural Sparse Conditional Constant Propagation", - false, false) - -// createIPSCCPPass - This is the public interface to this file. -ModulePass *llvm::createIPSCCPPass() { return new IPSCCPLegacyPass(); } |