X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSCCP.cpp;h=3a607cbd5f6de031543fa0065140820d49334dd9;hb=b15147ea4cc6716924ced6eff65358a95c35bd16;hp=491ca73fa3b3b8bdc650e70c793686fdd0d5f9a8;hpb=ebe61201d182123b699241e31d5123206836515c;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 491ca73fa3b..3a607cbd5f6 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -28,32 +28,55 @@ #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" #include "llvm/Pass.h" -#include "llvm/Support/InstVisitor.h" +#include "llvm/Analysis/ConstantFolding.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Support/CallSite.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" -#include "llvm/ADT/hash_map" +#include "llvm/Support/InstVisitor.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" #include -#include using namespace llvm; -// LatticeVal class - This class represents the different lattice values that an -// instruction may occupy. It is a simple class with value semantics. -// -namespace { +STATISTIC(NumInstRemoved, "Number of instructions removed"); +STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); + +STATISTIC(IPNumInstRemoved, "Number ofinstructions removed by IPSCCP"); +STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP"); +STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); +STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); -class LatticeVal { +namespace { +/// LatticeVal class - This class represents the different lattice values that +/// an LLVM value may occupy. It is a simple class with value semantics. +/// +class VISIBILITY_HIDDEN LatticeVal { enum { - undefined, // This instruction has no known value - constant, // This instruction has a constant value - overdefined // This instruction has an unknown value - } LatticeValue; // The current lattice position + /// undefined - This LLVM Value has no known value yet. + undefined, + + /// constant - This LLVM Value has a specific constant value. + constant, + + /// forcedconstant - This LLVM Value was thought to be undef until + /// ResolvedUndefsIn. This is treated just like 'constant', but if merged + /// with another (different) constant, it goes to overdefined, instead of + /// asserting. + forcedconstant, + + /// overdefined - This instruction is not known to be constant, and we know + /// it has a value. + overdefined + } LatticeValue; // The current lattice position + Constant *ConstantVal; // If Constant value, the current value public: inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {} - + // markOverdefined - Return true if this is a new status to be in... inline bool markOverdefined() { if (LatticeValue != overdefined) { @@ -63,11 +86,24 @@ public: return false; } - // markConstant - Return true if this is a new status for us... + // markConstant - Return true if this is a new status for us. inline bool markConstant(Constant *V) { if (LatticeValue != constant) { - LatticeValue = constant; - ConstantVal = V; + if (LatticeValue == undefined) { + LatticeValue = constant; + assert(V && "Marking constant with NULL"); + ConstantVal = V; + } else { + assert(LatticeValue == forcedconstant && + "Cannot move from overdefined to constant!"); + // Stay at forcedconstant if the constant is the same. + if (V == ConstantVal) return false; + + // Otherwise, we go to overdefined. Assumptions made based on the + // forced value are possibly wrong. Assuming this is another constant + // could expose a contradiction. + LatticeValue = overdefined; + } return true; } else { assert(ConstantVal == V && "Marking constant with different value"); @@ -75,8 +111,16 @@ public: return false; } - inline bool isUndefined() const { return LatticeValue == undefined; } - inline bool isConstant() const { return LatticeValue == constant; } + inline void markForcedConstant(Constant *V) { + assert(LatticeValue == undefined && "Can't force a defined value!"); + LatticeValue = forcedconstant; + ConstantVal = V; + } + + inline bool isUndefined() const { return LatticeValue == undefined; } + inline bool isConstant() const { + return LatticeValue == constant || LatticeValue == forcedconstant; + } inline bool isOverdefined() const { return LatticeValue == overdefined; } inline Constant *getConstant() const { @@ -85,28 +129,25 @@ public: } }; -} // end anonymous namespace - - //===----------------------------------------------------------------------===// // /// SCCPSolver - This class is a general purpose solver for Sparse Conditional /// Constant Propagation. /// class SCCPSolver : public InstVisitor { - std::set BBExecutable;// The basic blocks that are executable - hash_map ValueState; // The state each value is in... + SmallSet BBExecutable;// The basic blocks that are executable + std::map ValueState; // The state each value is in. /// GlobalValue - If we are tracking any values for the contents of a global /// variable, we keep a mapping from the constant accessor to the element of /// the global, to the currently known value. If the value becomes /// overdefined, it's entry is simply removed from this map. - hash_map TrackedGlobals; + DenseMap TrackedGlobals; /// TrackedFunctionRetVals - If we are tracking arguments into and the return /// value out of a function, it will have an entry in this map, indicating /// what the known return value for the function is. - hash_map TrackedFunctionRetVals; + DenseMap TrackedFunctionRetVals; // The reason for two worklists is that overdefined is the lowest state // on the lattice, and moving things to overdefined as fast as possible @@ -133,7 +174,7 @@ public: /// MarkBlockExecutable - This method can be used by clients to mark all of /// the blocks that are known to be intrinsically live in the processed unit. void MarkBlockExecutable(BasicBlock *BB) { - DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n"); + DOUT << "Marking Block Executable: " << BB->getName() << "\n"; BBExecutable.insert(BB); // Basic block is executable! BBWorkList.push_back(BB); // Add the block to the work list! } @@ -164,37 +205,40 @@ public: /// void Solve(); - /// ResolveBranchesIn - While solving the dataflow for a function, we assume + /// ResolvedUndefsIn - While solving the dataflow for a function, we assume /// that branches on undef values cannot reach any of their successors. /// However, this is not a safe assumption. After we solve dataflow, this /// method should be use to handle this. If this returns true, the solver /// should be rerun. - bool ResolveBranchesIn(Function &F); + bool ResolvedUndefsIn(Function &F); /// getExecutableBlocks - Once we have solved for constants, return the set of /// blocks that is known to be executable. - std::set &getExecutableBlocks() { + SmallSet &getExecutableBlocks() { return BBExecutable; } /// getValueMapping - Once we have solved for constants, return the mapping of /// LLVM values to LatticeVals. - hash_map &getValueMapping() { + std::map &getValueMapping() { return ValueState; } /// getTrackedFunctionRetVals - Get the inferred return value map. /// - const hash_map &getTrackedFunctionRetVals() { + const DenseMap &getTrackedFunctionRetVals() { return TrackedFunctionRetVals; } /// getTrackedGlobals - Get and return the set of inferred initializers for /// global variables. - const hash_map &getTrackedGlobals() { + const DenseMap &getTrackedGlobals() { return TrackedGlobals; } + inline void markOverdefined(Value *V) { + markOverdefined(ValueState[V], V); + } private: // markConstant - Make a value be marked as "constant". If the value @@ -203,10 +247,17 @@ private: // inline void markConstant(LatticeVal &IV, Value *V, Constant *C) { if (IV.markConstant(C)) { - DEBUG(std::cerr << "markConstant: " << *C << ": " << *V); + DOUT << "markConstant: " << *C << ": " << *V; InstWorkList.push_back(V); } } + + inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) { + IV.markForcedConstant(C); + DOUT << "markForcedConstant: " << *C << ": " << *V; + InstWorkList.push_back(V); + } + inline void markConstant(Value *V, Constant *C) { markConstant(ValueState[V], V, C); } @@ -217,18 +268,15 @@ private: inline void markOverdefined(LatticeVal &IV, Value *V) { if (IV.markOverdefined()) { - DEBUG(std::cerr << "markOverdefined: "; + DEBUG(DOUT << "markOverdefined: "; if (Function *F = dyn_cast(V)) - std::cerr << "Function '" << F->getName() << "'\n"; + DOUT << "Function '" << F->getName() << "'\n"; else - std::cerr << *V); + DOUT << *V); // Only instructions go on the work list OverdefinedInstWorkList.push_back(V); } } - inline void markOverdefined(Value *V) { - markOverdefined(ValueState[V], V); - } inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) { if (IV.isOverdefined() || MergeWithV.isUndefined()) @@ -240,6 +288,11 @@ private: else if (IV.getConstant() != MergeWithV.getConstant()) markOverdefined(IV, V); } + + inline void mergeInValue(Value *V, LatticeVal &MergeWithV) { + return mergeInValue(ValueState[V], V, MergeWithV); + } + // getValueState - Return the LatticeVal object that corresponds to the value. // This function is necessary because not all values should start out in the @@ -248,14 +301,16 @@ private: // Instruction object, then use this accessor to get its value from the map. // inline LatticeVal &getValueState(Value *V) { - hash_map::iterator I = ValueState.find(V); + std::map::iterator I = ValueState.find(V); if (I != ValueState.end()) return I->second; // Common case, in the map - if (Constant *CPV = dyn_cast(V)) { + if (Constant *C = dyn_cast(V)) { if (isa(V)) { // Nothing to do, remain undefined. } else { - ValueState[CPV].markConstant(CPV); // Constants are constant + LatticeVal &LV = ValueState[C]; + LV.markConstant(C); // Constants are constant + return LV; } } // All others are underdefined by default... @@ -270,8 +325,8 @@ private: return; // This edge is already known to be executable! if (BBExecutable.count(Dest)) { - DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName() - << " -> " << Dest->getName() << "\n"); + DOUT << "Marking Edge Executable: " << Source->getName() + << " -> " << Dest->getName() << "\n"; // The destination is already executable, but we just made an edge // feasible that wasn't before. Revisit the PHI nodes in the block @@ -287,7 +342,7 @@ private: // getFeasibleSuccessors - Return a vector of booleans to indicate which // successors are reachable from a given terminator instruction. // - void getFeasibleSuccessors(TerminatorInst &TI, std::vector &Succs); + void getFeasibleSuccessors(TerminatorInst &TI, SmallVector &Succs); // isEdgeFeasible - Return true if the control flow edge from the 'From' basic // block to the 'To' basic block is currently feasible... @@ -321,7 +376,10 @@ private: void visitCastInst(CastInst &I); void visitSelectInst(SelectInst &I); void visitBinaryOperator(Instruction &I); - void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); } + void visitCmpInst(CmpInst &I); + void visitExtractElementInst(ExtractElementInst &I); + void visitInsertElementInst(InsertElementInst &I); + void visitShuffleVectorInst(ShuffleVectorInst &I); // Instructions that cannot be folded away... void visitStoreInst (Instruction &I); @@ -342,16 +400,19 @@ private: void visitInstruction(Instruction &I) { // If a new instruction is added to LLVM that we don't handle... - std::cerr << "SCCP: Don't know how to handle: " << I; + cerr << "SCCP: Don't know how to handle: " << I; markOverdefined(&I); // Just in case } }; +} // end anonymous namespace + + // getFeasibleSuccessors - Return a vector of booleans to indicate which // successors are reachable from a given terminator instruction. // void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, - std::vector &Succs) { + SmallVector &Succs) { Succs.resize(TI.getNumSuccessors()); if (BranchInst *BI = dyn_cast(&TI)) { if (BI->isUnconditional()) { @@ -359,16 +420,16 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, } else { LatticeVal &BCValue = getValueState(BI->getCondition()); if (BCValue.isOverdefined() || - (BCValue.isConstant() && !isa(BCValue.getConstant()))) { + (BCValue.isConstant() && !isa(BCValue.getConstant()))) { // Overdefined condition variables, and branches on unfoldable constant // conditions, mean the branch could go either way. Succs[0] = Succs[1] = true; } else if (BCValue.isConstant()) { // Constant condition variables mean the branch can only go a single way - Succs[BCValue.getConstant() == ConstantBool::False] = true; + Succs[BCValue.getConstant() == ConstantInt::getFalse()] = true; } } - } else if (InvokeInst *II = dyn_cast(&TI)) { + } else if (isa(&TI)) { // Invoke instructions successors are always executable. Succs[0] = Succs[1] = true; } else if (SwitchInst *SI = dyn_cast(&TI)) { @@ -392,8 +453,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, Succs[0] = true; } } else { - std::cerr << "SCCP: Don't know how to handle: " << TI; - Succs.assign(TI.getNumSuccessors(), true); + assert(0 && "SCCP: Don't know how to handle this terminator!"); } } @@ -419,15 +479,15 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { return true; } else if (BCValue.isConstant()) { // Not branching on an evaluatable constant? - if (!isa(BCValue.getConstant())) return true; + if (!isa(BCValue.getConstant())) return true; // Constant condition variables mean the branch can only go a single way return BI->getSuccessor(BCValue.getConstant() == - ConstantBool::False) == To; + ConstantInt::getFalse()) == To; } return false; } - } else if (InvokeInst *II = dyn_cast(TI)) { + } else if (isa(TI)) { // Invoke instructions successors are always executable. return true; } else if (SwitchInst *SI = dyn_cast(TI)) { @@ -451,7 +511,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { } return false; } else { - std::cerr << "Unknown terminator instruction: " << *TI; + cerr << "Unknown terminator instruction: " << *TI; abort(); } } @@ -483,8 +543,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { std::multimap::iterator I, E; tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); if (I != E) { - std::vector Users; - Users.reserve(std::distance(I, E)); + SmallVector Users; for (; I != E; ++I) Users.push_back(I->second); while (!Users.empty()) { visit(Users.back()); @@ -552,7 +611,7 @@ void SCCPSolver::visitReturnInst(ReturnInst &I) { // If we are tracking the return value of this function, merge it in. Function *F = I.getParent()->getParent(); if (F->hasInternalLinkage() && !TrackedFunctionRetVals.empty()) { - hash_map::iterator TFRVI = + DenseMap::iterator TFRVI = TrackedFunctionRetVals.find(F); if (TFRVI != TrackedFunctionRetVals.end() && !TFRVI->second.isOverdefined()) { @@ -564,7 +623,7 @@ void SCCPSolver::visitReturnInst(ReturnInst &I) { void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { - std::vector SuccFeasible; + SmallVector SuccFeasible; getFeasibleSuccessors(TI, SuccFeasible); BasicBlock *BB = TI.getParent(); @@ -581,28 +640,41 @@ void SCCPSolver::visitCastInst(CastInst &I) { if (VState.isOverdefined()) // Inherit overdefinedness of operand markOverdefined(&I); else if (VState.isConstant()) // Propagate constant value - markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType())); + markConstant(&I, ConstantExpr::getCast(I.getOpcode(), + VState.getConstant(), I.getType())); } void SCCPSolver::visitSelectInst(SelectInst &I) { LatticeVal &CondValue = getValueState(I.getCondition()); - if (CondValue.isOverdefined()) + if (CondValue.isUndefined()) + return; + if (CondValue.isConstant()) { + if (ConstantInt *CondCB = dyn_cast(CondValue.getConstant())){ + mergeInValue(&I, getValueState(CondCB->getZExtValue() ? I.getTrueValue() + : I.getFalseValue())); + return; + } + } + + // Otherwise, the condition is overdefined or a constant we can't evaluate. + // See if we can produce something better than overdefined based on the T/F + // value. + LatticeVal &TVal = getValueState(I.getTrueValue()); + LatticeVal &FVal = getValueState(I.getFalseValue()); + + // select ?, C, C -> C. + if (TVal.isConstant() && FVal.isConstant() && + TVal.getConstant() == FVal.getConstant()) { + markConstant(&I, FVal.getConstant()); + return; + } + + if (TVal.isUndefined()) { // select ?, undef, X -> X. + mergeInValue(&I, FVal); + } else if (FVal.isUndefined()) { // select ?, X, undef -> X. + mergeInValue(&I, TVal); + } else { markOverdefined(&I); - else if (CondValue.isConstant()) { - if (CondValue.getConstant() == ConstantBool::True) { - LatticeVal &Val = getValueState(I.getTrueValue()); - if (Val.isOverdefined()) - markOverdefined(&I); - else if (Val.isConstant()) - markConstant(&I, Val.getConstant()); - } else if (CondValue.getConstant() == ConstantBool::False) { - LatticeVal &Val = getValueState(I.getFalseValue()); - if (Val.isOverdefined()) - markOverdefined(&I); - else if (Val.isConstant()) - markConstant(&I, Val.getConstant()); - } else - markOverdefined(&I); } } @@ -630,6 +702,8 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // Could annihilate value. if (I.getOpcode() == Instruction::And) markConstant(IV, &I, Constant::getNullValue(I.getType())); + else if (const VectorType *PT = dyn_cast(I.getType())) + markConstant(IV, &I, ConstantVector::getAllOnesValue(PT)); else markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType())); return; @@ -637,11 +711,11 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { if (I.getOpcode() == Instruction::And) { if (NonOverdefVal->getConstant()->isNullValue()) { markConstant(IV, &I, NonOverdefVal->getConstant()); - return; // X or 0 = -1 + return; // X and 0 = 0 } } else { - if (ConstantIntegral *CI = - dyn_cast(NonOverdefVal->getConstant())) + if (ConstantInt *CI = + dyn_cast(NonOverdefVal->getConstant())) if (CI->isAllOnesValue()) { markConstant(IV, &I, NonOverdefVal->getConstant()); return; // X or -1 = -1 @@ -728,6 +802,164 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { } } +// Handle ICmpInst instruction... +void SCCPSolver::visitCmpInst(CmpInst &I) { + LatticeVal &IV = ValueState[&I]; + if (IV.isOverdefined()) return; + + LatticeVal &V1State = getValueState(I.getOperand(0)); + LatticeVal &V2State = getValueState(I.getOperand(1)); + + if (V1State.isOverdefined() || V2State.isOverdefined()) { + // If both operands are PHI nodes, it is possible that this instruction has + // a constant value, despite the fact that the PHI node doesn't. Check for + // this condition now. + if (PHINode *PN1 = dyn_cast(I.getOperand(0))) + if (PHINode *PN2 = dyn_cast(I.getOperand(1))) + if (PN1->getParent() == PN2->getParent()) { + // Since the two PHI nodes are in the same basic block, they must have + // entries for the same predecessors. Walk the predecessor list, and + // if all of the incoming values are constants, and the result of + // evaluating this expression with all incoming value pairs is the + // same, then this expression is a constant even though the PHI node + // is not a constant! + LatticeVal Result; + for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { + LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); + BasicBlock *InBlock = PN1->getIncomingBlock(i); + LatticeVal &In2 = + getValueState(PN2->getIncomingValueForBlock(InBlock)); + + if (In1.isOverdefined() || In2.isOverdefined()) { + Result.markOverdefined(); + break; // Cannot fold this operation over the PHI nodes! + } else if (In1.isConstant() && In2.isConstant()) { + Constant *V = ConstantExpr::getCompare(I.getPredicate(), + In1.getConstant(), + In2.getConstant()); + if (Result.isUndefined()) + Result.markConstant(V); + else if (Result.isConstant() && Result.getConstant() != V) { + Result.markOverdefined(); + break; + } + } + } + + // If we found a constant value here, then we know the instruction is + // constant despite the fact that the PHI nodes are overdefined. + if (Result.isConstant()) { + markConstant(IV, &I, Result.getConstant()); + // Remember that this instruction is virtually using the PHI node + // operands. + UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); + UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); + return; + } else if (Result.isUndefined()) { + return; + } + + // Okay, this really is overdefined now. Since we might have + // speculatively thought that this was not overdefined before, and + // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, + // make sure to clean out any entries that we put there, for + // efficiency. + std::multimap::iterator It, E; + tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); + while (It != E) { + if (It->second == &I) { + UsersOfOverdefinedPHIs.erase(It++); + } else + ++It; + } + tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); + while (It != E) { + if (It->second == &I) { + UsersOfOverdefinedPHIs.erase(It++); + } else + ++It; + } + } + + markOverdefined(IV, &I); + } else if (V1State.isConstant() && V2State.isConstant()) { + markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), + V1State.getConstant(), + V2State.getConstant())); + } +} + +void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { + // FIXME : SCCP does not handle vectors properly. + markOverdefined(&I); + return; + +#if 0 + LatticeVal &ValState = getValueState(I.getOperand(0)); + LatticeVal &IdxState = getValueState(I.getOperand(1)); + + if (ValState.isOverdefined() || IdxState.isOverdefined()) + markOverdefined(&I); + else if(ValState.isConstant() && IdxState.isConstant()) + markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(), + IdxState.getConstant())); +#endif +} + +void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { + // FIXME : SCCP does not handle vectors properly. + markOverdefined(&I); + return; +#if 0 + LatticeVal &ValState = getValueState(I.getOperand(0)); + LatticeVal &EltState = getValueState(I.getOperand(1)); + LatticeVal &IdxState = getValueState(I.getOperand(2)); + + if (ValState.isOverdefined() || EltState.isOverdefined() || + IdxState.isOverdefined()) + markOverdefined(&I); + else if(ValState.isConstant() && EltState.isConstant() && + IdxState.isConstant()) + markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(), + EltState.getConstant(), + IdxState.getConstant())); + else if (ValState.isUndefined() && EltState.isConstant() && + IdxState.isConstant()) + markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()), + EltState.getConstant(), + IdxState.getConstant())); +#endif +} + +void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { + // FIXME : SCCP does not handle vectors properly. + markOverdefined(&I); + return; +#if 0 + LatticeVal &V1State = getValueState(I.getOperand(0)); + LatticeVal &V2State = getValueState(I.getOperand(1)); + LatticeVal &MaskState = getValueState(I.getOperand(2)); + + if (MaskState.isUndefined() || + (V1State.isUndefined() && V2State.isUndefined())) + return; // Undefined output if mask or both inputs undefined. + + if (V1State.isOverdefined() || V2State.isOverdefined() || + MaskState.isOverdefined()) { + markOverdefined(&I); + } else { + // A mix of constant/undef inputs. + Constant *V1 = V1State.isConstant() ? + V1State.getConstant() : UndefValue::get(I.getType()); + Constant *V2 = V2State.isConstant() ? + V2State.getConstant() : UndefValue::get(I.getType()); + Constant *Mask = MaskState.isConstant() ? + MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType()); + markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask)); + } +#endif +} + // Handle getelementptr instructions... if all operands are constants then we // can turn this into a getelementptr ConstantExpr. // @@ -735,7 +967,7 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) return; - std::vector Operands; + SmallVector Operands; Operands.reserve(I.getNumOperands()); for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { @@ -753,14 +985,15 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { Constant *Ptr = Operands[0]; Operands.erase(Operands.begin()); // Erase the pointer from idx list... - markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands)); + markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0], + Operands.size())); } void SCCPSolver::visitStoreInst(Instruction &SI) { if (TrackedGlobals.empty() || !isa(SI.getOperand(1))) return; GlobalVariable *GV = cast(SI.getOperand(1)); - hash_map::iterator I = TrackedGlobals.find(GV); + DenseMap::iterator I = TrackedGlobals.find(GV); if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; // Get the value we are storing into the global. @@ -782,7 +1015,9 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! if (PtrVal.isConstant() && !I.isVolatile()) { Value *Ptr = PtrVal.getConstant(); - if (isa(Ptr)) { + // TODO: Consider a target hook for valid address spaces for this xform. + if (isa(Ptr) && + cast(Ptr->getType())->getAddressSpace() == 0) { // load null -> null markConstant(IV, &I, Constant::getNullValue(I.getType())); return; @@ -791,13 +1026,13 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { // Transform load (constant global) into the value loaded. if (GlobalVariable *GV = dyn_cast(Ptr)) { if (GV->isConstant()) { - if (!GV->isExternal()) { + if (!GV->isDeclaration()) { markConstant(IV, &I, GV->getInitializer()); return; } } else if (!TrackedGlobals.empty()) { // If we are tracking this global, merge in the known value for it. - hash_map::iterator It = + DenseMap::iterator It = TrackedGlobals.find(GV); if (It != TrackedGlobals.end()) { mergeInValue(IV, &I, It->second); @@ -810,7 +1045,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (ConstantExpr *CE = dyn_cast(Ptr)) if (CE->getOpcode() == Instruction::GetElementPtr) if (GlobalVariable *GV = dyn_cast(CE->getOperand(0))) - if (GV->isConstant() && !GV->isExternal()) + if (GV->isConstant() && !GV->isDeclaration()) if (Constant *V = ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) { markConstant(IV, &I, V); @@ -828,7 +1063,7 @@ void SCCPSolver::visitCallSite(CallSite CS) { // If we are tracking this function, we must make sure to bind arguments as // appropriate. - hash_map::iterator TFRVI =TrackedFunctionRetVals.end(); + DenseMap::iterator TFRVI =TrackedFunctionRetVals.end(); if (F && F->hasInternalLinkage()) TFRVI = TrackedFunctionRetVals.find(F); @@ -858,12 +1093,12 @@ void SCCPSolver::visitCallSite(CallSite CS) { return; } - if (F == 0 || !F->isExternal() || !canConstantFoldCallTo(F)) { + if (F == 0 || !F->isDeclaration() || !canConstantFoldCallTo(F)) { markOverdefined(IV, I); return; } - std::vector Operands; + SmallVector Operands; Operands.reserve(I->getNumOperands()-1); for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); @@ -879,7 +1114,7 @@ void SCCPSolver::visitCallSite(CallSite CS) { Operands.push_back(State.getConstant()); } - if (Constant *C = ConstantFoldCall(F, Operands)) + if (Constant *C = ConstantFoldCall(F, &Operands[0], Operands.size())) markConstant(IV, I, C); else markOverdefined(IV, I); @@ -895,7 +1130,7 @@ void SCCPSolver::Solve() { Value *I = OverdefinedInstWorkList.back(); OverdefinedInstWorkList.pop_back(); - DEBUG(std::cerr << "\nPopped off OI-WL: " << *I); + DOUT << "\nPopped off OI-WL: " << *I; // "I" got into the work list because it either made the transition from // bottom to constant @@ -913,7 +1148,7 @@ void SCCPSolver::Solve() { Value *I = InstWorkList.back(); InstWorkList.pop_back(); - DEBUG(std::cerr << "\nPopped off I-WL: " << *I); + DOUT << "\nPopped off I-WL: " << *I; // "I" got into the work list because it either made the transition from // bottom to constant @@ -933,7 +1168,7 @@ void SCCPSolver::Solve() { BasicBlock *BB = BBWorkList.back(); BBWorkList.pop_back(); - DEBUG(std::cerr << "\nPopped off BBWL: " << *BB); + DOUT << "\nPopped off BBWL: " << *BB; // Notify all instructions in this basic block that they are newly // executable. @@ -942,50 +1177,168 @@ void SCCPSolver::Solve() { } } -/// ResolveBranchesIn - While solving the dataflow for a function, we assume +/// ResolvedUndefsIn - While solving the dataflow for a function, we assume /// that branches on undef values cannot reach any of their successors. /// However, this is not a safe assumption. After we solve dataflow, this /// method should be use to handle this. If this returns true, the solver /// should be rerun. -bool SCCPSolver::ResolveBranchesIn(Function &F) { - bool BranchesResolved = false; - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - if (BBExecutable.count(BB)) { - TerminatorInst *TI = BB->getTerminator(); - if (BranchInst *BI = dyn_cast(TI)) { - if (BI->isConditional()) { - LatticeVal &BCValue = getValueState(BI->getCondition()); - if (BCValue.isUndefined()) { - BI->setCondition(ConstantBool::True); - BranchesResolved = true; - visit(BI); - } - } - } else if (SwitchInst *SI = dyn_cast(TI)) { - LatticeVal &SCValue = getValueState(SI->getCondition()); - if (SCValue.isUndefined()) { - const Type *CondTy = SI->getCondition()->getType(); - SI->setCondition(Constant::getNullValue(CondTy)); - BranchesResolved = true; - visit(SI); +/// +/// This method handles this by finding an unresolved branch and marking it one +/// of the edges from the block as being feasible, even though the condition +/// doesn't say it would otherwise be. This allows SCCP to find the rest of the +/// CFG and only slightly pessimizes the analysis results (by marking one, +/// potentially infeasible, edge feasible). This cannot usefully modify the +/// constraints on the condition of the branch, as that would impact other users +/// of the value. +/// +/// This scan also checks for values that use undefs, whose results are actually +/// defined. For example, 'zext i8 undef to i32' should produce all zeros +/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero, +/// even if X isn't defined. +bool SCCPSolver::ResolvedUndefsIn(Function &F) { + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { + if (!BBExecutable.count(BB)) + continue; + + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + // Look for instructions which produce undef values. + if (I->getType() == Type::VoidTy) continue; + + LatticeVal &LV = getValueState(I); + if (!LV.isUndefined()) continue; + + // Get the lattice values of the first two operands for use below. + LatticeVal &Op0LV = getValueState(I->getOperand(0)); + LatticeVal Op1LV; + if (I->getNumOperands() == 2) { + // If this is a two-operand instruction, and if both operands are + // undefs, the result stays undef. + Op1LV = getValueState(I->getOperand(1)); + if (Op0LV.isUndefined() && Op1LV.isUndefined()) + continue; + } + + // If this is an instructions whose result is defined even if the input is + // not fully defined, propagate the information. + const Type *ITy = I->getType(); + switch (I->getOpcode()) { + default: break; // Leave the instruction as an undef. + case Instruction::ZExt: + // After a zero extend, we know the top part is zero. SExt doesn't have + // to be handled here, because we don't know whether the top part is 1's + // or 0's. + assert(Op0LV.isUndefined()); + markForcedConstant(LV, I, Constant::getNullValue(ITy)); + return true; + case Instruction::Mul: + case Instruction::And: + // undef * X -> 0. X could be zero. + // undef & X -> 0. X could be zero. + markForcedConstant(LV, I, Constant::getNullValue(ITy)); + return true; + + case Instruction::Or: + // undef | X -> -1. X could be -1. + if (const VectorType *PTy = dyn_cast(ITy)) + markForcedConstant(LV, I, ConstantVector::getAllOnesValue(PTy)); + else + markForcedConstant(LV, I, ConstantInt::getAllOnesValue(ITy)); + return true; + + case Instruction::SDiv: + case Instruction::UDiv: + case Instruction::SRem: + case Instruction::URem: + // X / undef -> undef. No change. + // X % undef -> undef. No change. + if (Op1LV.isUndefined()) break; + + // undef / X -> 0. X could be maxint. + // undef % X -> 0. X could be 1. + markForcedConstant(LV, I, Constant::getNullValue(ITy)); + return true; + + case Instruction::AShr: + // undef >>s X -> undef. No change. + if (Op0LV.isUndefined()) break; + + // X >>s undef -> X. X could be 0, X could have the high-bit known set. + if (Op0LV.isConstant()) + markForcedConstant(LV, I, Op0LV.getConstant()); + else + markOverdefined(LV, I); + return true; + case Instruction::LShr: + case Instruction::Shl: + // undef >> X -> undef. No change. + // undef << X -> undef. No change. + if (Op0LV.isUndefined()) break; + + // X >> undef -> 0. X could be 0. + // X << undef -> 0. X could be 0. + markForcedConstant(LV, I, Constant::getNullValue(ITy)); + return true; + case Instruction::Select: + // undef ? X : Y -> X or Y. There could be commonality between X/Y. + if (Op0LV.isUndefined()) { + if (!Op1LV.isConstant()) // Pick the constant one if there is any. + Op1LV = getValueState(I->getOperand(2)); + } else if (Op1LV.isUndefined()) { + // c ? undef : undef -> undef. No change. + Op1LV = getValueState(I->getOperand(2)); + if (Op1LV.isUndefined()) + break; + // Otherwise, c ? undef : x -> x. + } else { + // Leave Op1LV as Operand(1)'s LatticeValue. } + + if (Op1LV.isConstant()) + markForcedConstant(LV, I, Op1LV.getConstant()); + else + markOverdefined(LV, I); + return true; } } + + TerminatorInst *TI = BB->getTerminator(); + if (BranchInst *BI = dyn_cast(TI)) { + if (!BI->isConditional()) continue; + if (!getValueState(BI->getCondition()).isUndefined()) + continue; + } else if (SwitchInst *SI = dyn_cast(TI)) { + if (!getValueState(SI->getCondition()).isUndefined()) + continue; + } else { + continue; + } + + // If the edge to the first successor isn't thought to be feasible yet, mark + // it so now. + if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(0)))) + continue; + + // Otherwise, it isn't already thought to be feasible. Mark it as such now + // and return. This will make other blocks reachable, which will allow new + // values to be discovered and existing ones to be moved in the lattice. + markEdgeExecutable(BB, TI->getSuccessor(0)); + return true; + } - return BranchesResolved; + return false; } namespace { - Statistic<> NumInstRemoved("sccp", "Number of instructions removed"); - Statistic<> NumDeadBlocks ("sccp", "Number of basic blocks unreachable"); - //===--------------------------------------------------------------------===// // /// SCCP Class - This class uses the SCCPSolver to implement a per-function - /// Sparse Conditional COnstant Propagator. + /// Sparse Conditional Constant Propagator. /// - struct SCCP : public FunctionPass { + struct VISIBILITY_HIDDEN SCCP : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + SCCP() : FunctionPass((intptr_t)&ID) {} + // runOnFunction - Run the Sparse Conditional Constant Propagation // algorithm, and return true if the function was modified. // @@ -996,7 +1349,8 @@ namespace { } }; - RegisterOpt X("sccp", "Sparse Conditional Constant Propagation"); + char SCCP::ID = 0; + RegisterPass X("sccp", "Sparse Conditional Constant Propagation"); } // end anonymous namespace @@ -1010,23 +1364,22 @@ FunctionPass *llvm::createSCCPPass() { // and return true if the function was modified. // bool SCCP::runOnFunction(Function &F) { - DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n"); + DOUT << "SCCP on function '" << F.getName() << "'\n"; SCCPSolver Solver; // Mark the first block of the function as being executable. Solver.MarkBlockExecutable(F.begin()); // Mark all arguments to the function as being overdefined. - hash_map &Values = Solver.getValueMapping(); - for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI) - Values[AI].markOverdefined(); + for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) + Solver.markOverdefined(AI); // Solve for constants. - bool ResolvedBranches = true; - while (ResolvedBranches) { + bool ResolvedUndefs = true; + while (ResolvedUndefs) { Solver.Solve(); - DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n"); - ResolvedBranches = Solver.ResolveBranchesIn(F); + DOUT << "RESOLVING UNDEFs\n"; + ResolvedUndefs = Solver.ResolvedUndefsIn(F); } bool MadeChanges = false; @@ -1035,15 +1388,17 @@ bool SCCP::runOnFunction(Function &F) { // delete their contents now. Note that we cannot actually delete the blocks, // as we cannot modify the CFG of the function. // - std::set &ExecutableBBs = Solver.getExecutableBlocks(); + SmallSet &ExecutableBBs = Solver.getExecutableBlocks(); + SmallVector Insts; + std::map &Values = Solver.getValueMapping(); + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) if (!ExecutableBBs.count(BB)) { - DEBUG(std::cerr << " BasicBlock Dead:" << *BB); + DOUT << " BasicBlock Dead:" << *BB; ++NumDeadBlocks; // Delete the instructions backwards, as it has a reduced likelihood of // having to update as many def-use and use-def chains. - std::vector Insts; for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator(); I != E; ++I) Insts.push_back(I); @@ -1064,11 +1419,11 @@ bool SCCP::runOnFunction(Function &F) { Instruction *Inst = BI++; if (Inst->getType() != Type::VoidTy) { LatticeVal &IV = Values[Inst]; - if (IV.isConstant() || IV.isUndefined() && + if ((IV.isConstant() || IV.isUndefined()) && !isa(Inst)) { Constant *Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(std::cerr << " Constant: " << *Const << " = " << *Inst); + DOUT << " Constant: " << *Const << " = " << *Inst; // Replaces all of the uses of a variable with uses of the constant. Inst->replaceAllUsesWith(Const); @@ -1088,23 +1443,19 @@ bool SCCP::runOnFunction(Function &F) { } namespace { - Statistic<> IPNumInstRemoved("ipsccp", "Number of instructions removed"); - Statistic<> IPNumDeadBlocks ("ipsccp", "Number of basic blocks unreachable"); - Statistic<> IPNumArgsElimed ("ipsccp", - "Number of arguments constant propagated"); - Statistic<> IPNumGlobalConst("ipsccp", - "Number of globals found to be constant"); - //===--------------------------------------------------------------------===// // /// IPSCCP Class - This class implements interprocedural Sparse Conditional /// Constant Propagation. /// - struct IPSCCP : public ModulePass { + struct VISIBILITY_HIDDEN IPSCCP : public ModulePass { + static char ID; + IPSCCP() : ModulePass((intptr_t)&ID) {} bool runOnModule(Module &M); }; - RegisterOpt + char IPSCCP::ID = 0; + RegisterPass Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); } // end anonymous namespace @@ -1145,14 +1496,13 @@ bool IPSCCP::runOnModule(Module &M) { // Loop over all functions, marking arguments to those with their addresses // taken or that are external as overdefined. // - hash_map &Values = Solver.getValueMapping(); for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) if (!F->hasInternalLinkage() || AddressIsTaken(F)) { - if (!F->isExternal()) + if (!F->isDeclaration()) Solver.MarkBlockExecutable(F->begin()); for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI) - Values[AI].markOverdefined(); + Solver.markOverdefined(AI); } else { Solver.AddTrackedFunction(F); } @@ -1166,14 +1516,14 @@ bool IPSCCP::runOnModule(Module &M) { Solver.TrackValueOfGlobalVariable(G); // Solve for constants. - bool ResolvedBranches = true; - while (ResolvedBranches) { + bool ResolvedUndefs = true; + while (ResolvedUndefs) { Solver.Solve(); - DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n"); - ResolvedBranches = false; + DOUT << "RESOLVING UNDEFS\n"; + ResolvedUndefs = false; for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) - ResolvedBranches |= Solver.ResolveBranchesIn(*F); + ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); } bool MadeChanges = false; @@ -1181,7 +1531,11 @@ bool IPSCCP::runOnModule(Module &M) { // Iterate over all of the instructions in the module, replacing them with // constants if we have found them to be of constant values. // - std::set &ExecutableBBs = Solver.getExecutableBlocks(); + SmallSet &ExecutableBBs = Solver.getExecutableBlocks(); + SmallVector Insts; + SmallVector BlocksToErase; + std::map &Values = Solver.getValueMapping(); + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI) @@ -1190,7 +1544,7 @@ bool IPSCCP::runOnModule(Module &M) { if (IV.isConstant() || IV.isUndefined()) { Constant *CST = IV.isConstant() ? IV.getConstant() : UndefValue::get(AI->getType()); - DEBUG(std::cerr << "*** Arg " << *AI << " = " << *CST <<"\n"); + DOUT << "*** Arg " << *AI << " = " << *CST <<"\n"; // Replaces all of the uses of a variable with uses of the // constant. @@ -1199,15 +1553,13 @@ bool IPSCCP::runOnModule(Module &M) { } } - std::vector BlocksToErase; for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) if (!ExecutableBBs.count(BB)) { - DEBUG(std::cerr << " BasicBlock Dead:" << *BB); + DOUT << " BasicBlock Dead:" << *BB; ++IPNumDeadBlocks; // Delete the instructions backwards, as it has a reduced likelihood of // having to update as many def-use and use-def chains. - std::vector Insts; TerminatorInst *TI = BB->getTerminator(); for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I) Insts.push_back(I); @@ -1224,7 +1576,7 @@ bool IPSCCP::runOnModule(Module &M) { for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { BasicBlock *Succ = TI->getSuccessor(i); - if (Succ->begin() != Succ->end() && isa(Succ->begin())) + if (!Succ->empty() && isa(Succ->begin())) TI->getSuccessor(i)->removePredecessor(BB); } if (!TI->use_empty()) @@ -1245,7 +1597,7 @@ bool IPSCCP::runOnModule(Module &M) { !isa(Inst)) { Constant *Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(std::cerr << " Constant: " << *Const << " = " << *Inst); + DOUT << " Constant: " << *Const << " = " << *Inst; // Replaces all of the uses of a variable with uses of the // constant. @@ -1272,20 +1624,44 @@ bool IPSCCP::runOnModule(Module &M) { while (!DeadBB->use_empty()) { Instruction *I = cast(DeadBB->use_back()); bool Folded = ConstantFoldTerminator(I->getParent()); - assert(Folded && "Didn't fold away reference to block!"); + 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. + if (BranchInst *BI = dyn_cast(I)) { + assert(BI->isConditional() && isa(BI->getCondition()) && + "Branch should be foldable!"); + } else if (SwitchInst *SI = dyn_cast(I)) { + assert(isa(SI->getCondition()) && "Switch should fold"); + } else { + assert(0 && "Didn't fold away reference to block!"); + } + + // Make this an uncond branch to the first successor. + TerminatorInst *TI = I->getParent()->getTerminator(); + new BranchInst(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(); + } } // Finally, delete the basic block. F->getBasicBlockList().erase(DeadBB); } + BlocksToErase.clear(); } // If we inferred constant or undef return values for a function, we replaced // all call uses with the inferred value. This means we don't need to bother // actually returning anything from the function. Replace all return // instructions with return undef. - const hash_map &RV =Solver.getTrackedFunctionRetVals(); - for (hash_map::const_iterator I = RV.begin(), + const DenseMap &RV =Solver.getTrackedFunctionRetVals(); + for (DenseMap::const_iterator I = RV.begin(), E = RV.end(); I != E; ++I) if (!I->second.isOverdefined() && I->first->getReturnType() != Type::VoidTy) { @@ -1298,13 +1674,13 @@ bool IPSCCP::runOnModule(Module &M) { // If we infered constant or undef values for globals variables, we can delete // the global and any stores that remain to it. - const hash_map &TG = Solver.getTrackedGlobals(); - for (hash_map::const_iterator I = TG.begin(), + const DenseMap &TG = Solver.getTrackedGlobals(); + for (DenseMap::const_iterator I = TG.begin(), E = TG.end(); I != E; ++I) { GlobalVariable *GV = I->first; assert(!I->second.isOverdefined() && "Overdefined values should have been taken out of the map!"); - DEBUG(std::cerr << "Found that GV '" << GV->getName()<< "' is constant!\n"); + DOUT << "Found that GV '" << GV->getName()<< "' is constant!\n"; while (!GV->use_empty()) { StoreInst *SI = cast(GV->use_back()); SI->eraseFromParent();