diff options
Diffstat (limited to 'lib/Transforms/Scalar/SCCP.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/SCCP.cpp | 601 |
1 files changed, 289 insertions, 312 deletions
diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 8569e080873c9..da700f18cdafb 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -17,15 +17,15 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/IPO/SCCP.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" @@ -38,6 +38,8 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/SCCP.h" #include "llvm/Transforms/Utils/Local.h" #include <algorithm> using namespace llvm; @@ -57,8 +59,8 @@ namespace { /// class LatticeVal { enum LatticeValueTy { - /// undefined - This LLVM Value has no known value yet. - undefined, + /// unknown - This LLVM Value has no known value yet. + unknown, /// constant - This LLVM Value has a specific constant value. constant, @@ -83,9 +85,9 @@ class LatticeVal { } public: - LatticeVal() : Val(nullptr, undefined) {} + LatticeVal() : Val(nullptr, unknown) {} - bool isUndefined() const { return getLatticeValue() == undefined; } + bool isUnknown() const { return getLatticeValue() == unknown; } bool isConstant() const { return getLatticeValue() == constant || getLatticeValue() == forcedconstant; } @@ -112,7 +114,7 @@ public: return false; } - if (isUndefined()) { + if (isUnknown()) { Val.setInt(constant); assert(V && "Marking constant with NULL"); Val.setPointer(V); @@ -139,7 +141,7 @@ public: } void markForcedConstant(Constant *V) { - assert(isUndefined() && "Can't force a defined value!"); + assert(isUnknown() && "Can't force a defined value!"); Val.setInt(forcedconstant); Val.setPointer(V); } @@ -228,7 +230,7 @@ public: /// performing Interprocedural SCCP. void TrackValueOfGlobalVariable(GlobalVariable *GV) { // We only track the contents of scalar globals. - if (GV->getType()->getElementType()->isSingleValueType()) { + if (GV->getValueType()->isSingleValueType()) { LatticeVal &IV = TrackedGlobals[GV]; if (!isa<UndefValue>(GV->getInitializer())) IV.markConstant(GV->getInitializer()); @@ -268,6 +270,18 @@ public: return BBExecutable.count(BB); } + std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const { + std::vector<LatticeVal> StructValues; + StructType *STy = dyn_cast<StructType>(V->getType()); + assert(STy && "getStructLatticeValueFor() can be called only on structs"); + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { + auto I = StructValueState.find(std::make_pair(V, i)); + assert(I != StructValueState.end() && "Value not in valuemap!"); + StructValues.push_back(I->second); + } + return StructValues; + } + LatticeVal getLatticeValueFor(Value *V) const { DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V); assert(I != ValueState.end() && "V is not in valuemap!"); @@ -302,6 +316,13 @@ public: } private: + // pushToWorkList - Helper for markConstant/markForcedConstant + void pushToWorkList(LatticeVal &IV, Value *V) { + if (IV.isOverdefined()) + return OverdefinedInstWorkList.push_back(V); + InstWorkList.push_back(V); + } + // 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. @@ -309,10 +330,7 @@ private: void markConstant(LatticeVal &IV, Value *V, Constant *C) { if (!IV.markConstant(C)) return; DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); - if (IV.isOverdefined()) - OverdefinedInstWorkList.push_back(V); - else - InstWorkList.push_back(V); + pushToWorkList(IV, V); } void markConstant(Value *V, Constant *C) { @@ -325,10 +343,7 @@ private: LatticeVal &IV = ValueState[V]; IV.markForcedConstant(C); DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); - if (IV.isOverdefined()) - OverdefinedInstWorkList.push_back(V); - else - InstWorkList.push_back(V); + pushToWorkList(IV, V); } @@ -348,14 +363,14 @@ private: } void mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { - if (IV.isOverdefined() || MergeWithV.isUndefined()) + if (IV.isOverdefined() || MergeWithV.isUnknown()) return; // Noop. if (MergeWithV.isOverdefined()) - markOverdefined(IV, V); - else if (IV.isUndefined()) - markConstant(IV, V, MergeWithV.getConstant()); - else if (IV.getConstant() != MergeWithV.getConstant()) - markOverdefined(IV, V); + return markOverdefined(IV, V); + if (IV.isUnknown()) + return markConstant(IV, V, MergeWithV.getConstant()); + if (IV.getConstant() != MergeWithV.getConstant()) + return markOverdefined(IV, V); } void mergeInValue(Value *V, LatticeVal MergeWithV) { @@ -378,7 +393,7 @@ private: return LV; // Common case, already in the map. if (Constant *C = dyn_cast<Constant>(V)) { - // Undef values remain undefined. + // Undef values remain unknown. if (!isa<UndefValue>(V)) LV.markConstant(C); // Constants are constant } @@ -409,7 +424,7 @@ private: if (!Elt) LV.markOverdefined(); // Unknown sort of constant. else if (isa<UndefValue>(Elt)) - ; // Undef values remain undefined. + ; // Undef values remain unknown. else LV.markConstant(Elt); // Constants are constant. } @@ -537,7 +552,7 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, if (!CI) { // Overdefined condition variables, and branches on unfoldable constant // conditions, mean the branch could go either way. - if (!BCValue.isUndefined()) + if (!BCValue.isUnknown()) Succs[0] = Succs[1] = true; return; } @@ -561,9 +576,9 @@ void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, LatticeVal SCValue = getValueState(SI->getCondition()); ConstantInt *CI = SCValue.getConstantInt(); - if (!CI) { // Overdefined or undefined condition? + if (!CI) { // Overdefined or unknown condition? // All destinations are executable! - if (!SCValue.isUndefined()) + if (!SCValue.isUnknown()) Succs.assign(TI.getNumSuccessors(), true); return; } @@ -607,7 +622,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { // undef conditions mean that neither edge is feasible yet. ConstantInt *CI = BCValue.getConstantInt(); if (!CI) - return !BCValue.isUndefined(); + return !BCValue.isUnknown(); // Constant condition variables mean the branch can only go a single way. return BI->getSuccessor(CI->isZero()) == To; @@ -625,7 +640,7 @@ bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { ConstantInt *CI = SCValue.getConstantInt(); if (!CI) - return !SCValue.isUndefined(); + return !SCValue.isUnknown(); return SI->findCaseValue(CI).getCaseSuccessor() == To; } @@ -677,12 +692,12 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // are overdefined, the PHI becomes overdefined as well. If they are all // constant, and they agree with each other, the PHI becomes the identical // constant. If they are constant and don't agree, the PHI is overdefined. - // If there are no executable operands, the PHI remains undefined. + // If there are no executable operands, the PHI remains unknown. // Constant *OperandVal = nullptr; for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { LatticeVal IV = getValueState(PN.getIncomingValue(i)); - if (IV.isUndefined()) continue; // Doesn't influence PHI node. + if (IV.isUnknown()) continue; // Doesn't influence PHI node. if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) continue; @@ -708,7 +723,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // If we exited the loop, this means that the PHI node only has constant // arguments that agree with each other(and OperandVal is the constant) or // OperandVal is null because there are no defined incoming arguments. If - // this is the case, the PHI remains undefined. + // this is the case, the PHI remains unknown. // if (OperandVal) markConstant(&PN, OperandVal); // Acquire operand value @@ -758,8 +773,9 @@ void SCCPSolver::visitCastInst(CastInst &I) { if (OpSt.isOverdefined()) // Inherit overdefinedness of operand markOverdefined(&I); else if (OpSt.isConstant()) { - Constant *C = - ConstantExpr::getCast(I.getOpcode(), OpSt.getConstant(), I.getType()); + // Fold the constant as we build. + Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(), + I.getType(), DL); if (isa<UndefValue>(C)) return; // Propagate constant value @@ -829,7 +845,7 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { return markAnythingOverdefined(&I); LatticeVal CondValue = getValueState(I.getCondition()); - if (CondValue.isUndefined()) + if (CondValue.isUnknown()) return; if (ConstantInt *CondCB = CondValue.getConstantInt()) { @@ -849,9 +865,9 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { TVal.getConstant() == FVal.getConstant()) return markConstant(&I, FVal.getConstant()); - if (TVal.isUndefined()) // select ?, undef, X -> X. + if (TVal.isUnknown()) // select ?, undef, X -> X. return mergeInValue(&I, FVal); - if (FVal.isUndefined()) // select ?, X, undef -> X. + if (FVal.isUnknown()) // select ?, X, undef -> X. return mergeInValue(&I, TVal); markOverdefined(&I); } @@ -890,7 +906,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { NonOverdefVal = &V2State; if (NonOverdefVal) { - if (NonOverdefVal->isUndefined()) { + if (NonOverdefVal->isUnknown()) { // Could annihilate value. if (I.getOpcode() == Instruction::And) markConstant(IV, &I, Constant::getNullValue(I.getType())); @@ -934,7 +950,7 @@ void SCCPSolver::visitCmpInst(CmpInst &I) { return markConstant(IV, &I, C); } - // If operands are still undefined, wait for it to resolve. + // If operands are still unknown, wait for it to resolve. if (!V1State.isOverdefined() && !V2State.isOverdefined()) return; @@ -944,69 +960,16 @@ void SCCPSolver::visitCmpInst(CmpInst &I) { void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { // TODO : SCCP does not handle vectors properly. return markOverdefined(&I); - -#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) { // TODO : SCCP does not handle vectors properly. return markOverdefined(&I); -#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) { // TODO : SCCP does not handle vectors properly. return markOverdefined(&I); -#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 @@ -1020,7 +983,7 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { LatticeVal State = getValueState(I.getOperand(i)); - if (State.isUndefined()) + if (State.isUnknown()) return; // Operands are not resolved yet. if (State.isOverdefined()) @@ -1066,7 +1029,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { return markAnythingOverdefined(&I); LatticeVal PtrVal = getValueState(I.getOperand(0)); - if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! + if (PtrVal.isUnknown()) return; // The pointer is not resolved yet! LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) return; @@ -1094,7 +1057,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { } // Transform load from a constant into a constant if possible. - if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, DL)) { + if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) { if (isa<UndefValue>(C)) return; return markConstant(IV, &I, C); @@ -1127,7 +1090,7 @@ CallOverdefined: AI != E; ++AI) { LatticeVal State = getValueState(*AI); - if (State.isUndefined()) + if (State.isUnknown()) return; // Operands are not resolved yet. if (State.isOverdefined()) return markOverdefined(I); @@ -1275,11 +1238,11 @@ void SCCPSolver::Solve() { /// 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)) + for (BasicBlock &BB : F) { + if (!BBExecutable.count(&BB)) continue; - for (Instruction &I : *BB) { + for (Instruction &I : BB) { // Look for instructions which produce undef values. if (I.getType()->isVoidTy()) continue; @@ -1301,14 +1264,14 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // more precise than this but it isn't worth bothering. for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { LatticeVal &LV = getStructValueState(&I, i); - if (LV.isUndefined()) + if (LV.isUnknown()) markOverdefined(LV, &I); } continue; } LatticeVal &LV = getValueState(&I); - if (!LV.isUndefined()) continue; + if (!LV.isUnknown()) continue; // extractvalue is safe; check here because the argument is a struct. if (isa<ExtractValueInst>(I)) @@ -1347,7 +1310,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::FDiv: case Instruction::FRem: // Floating-point binary operation: be conservative. - if (Op0LV.isUndefined() && Op1LV.isUndefined()) + if (Op0LV.isUnknown() && Op1LV.isUnknown()) markForcedConstant(&I, Constant::getNullValue(ITy)); else markOverdefined(&I); @@ -1367,7 +1330,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::Mul: case Instruction::And: // Both operands undef -> undef - if (Op0LV.isUndefined() && Op1LV.isUndefined()) + if (Op0LV.isUnknown() && Op1LV.isUnknown()) break; // undef * X -> 0. X could be zero. // undef & X -> 0. X could be zero. @@ -1376,7 +1339,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::Or: // Both operands undef -> undef - if (Op0LV.isUndefined() && Op1LV.isUndefined()) + if (Op0LV.isUnknown() && Op1LV.isUnknown()) break; // undef | X -> -1. X could be -1. markForcedConstant(&I, Constant::getAllOnesValue(ITy)); @@ -1386,7 +1349,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // undef ^ undef -> 0; strictly speaking, this is not strictly // necessary, but we try to be nice to people who expect this // behavior in simple cases - if (Op0LV.isUndefined() && Op1LV.isUndefined()) { + if (Op0LV.isUnknown() && Op1LV.isUnknown()) { markForcedConstant(&I, Constant::getNullValue(ITy)); return true; } @@ -1399,7 +1362,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::URem: // X / undef -> undef. No change. // X % undef -> undef. No change. - if (Op1LV.isUndefined()) break; + if (Op1LV.isUnknown()) break; // X / 0 -> undef. No change. // X % 0 -> undef. No change. @@ -1413,7 +1376,15 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::AShr: // X >>a undef -> undef. - if (Op1LV.isUndefined()) break; + if (Op1LV.isUnknown()) break; + + // Shifting by the bitwidth or more is undefined. + if (Op1LV.isConstant()) { + if (auto *ShiftAmt = Op1LV.getConstantInt()) + if (ShiftAmt->getLimitedValue() >= + ShiftAmt->getType()->getScalarSizeInBits()) + break; + } // undef >>a X -> all ones markForcedConstant(&I, Constant::getAllOnesValue(ITy)); @@ -1422,7 +1393,15 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::Shl: // X << undef -> undef. // X >> undef -> undef. - if (Op1LV.isUndefined()) break; + if (Op1LV.isUnknown()) break; + + // Shifting by the bitwidth or more is undefined. + if (Op1LV.isConstant()) { + if (auto *ShiftAmt = Op1LV.getConstantInt()) + if (ShiftAmt->getLimitedValue() >= + ShiftAmt->getType()->getScalarSizeInBits()) + break; + } // undef << X -> 0 // undef >> X -> 0 @@ -1431,13 +1410,13 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { case Instruction::Select: Op1LV = getValueState(I.getOperand(1)); // undef ? X : Y -> X or Y. There could be commonality between X/Y. - if (Op0LV.isUndefined()) { + if (Op0LV.isUnknown()) { if (!Op1LV.isConstant()) // Pick the constant one if there is any. Op1LV = getValueState(I.getOperand(2)); - } else if (Op1LV.isUndefined()) { + } else if (Op1LV.isUnknown()) { // c ? undef : undef -> undef. No change. Op1LV = getValueState(I.getOperand(2)); - if (Op1LV.isUndefined()) + if (Op1LV.isUnknown()) break; // Otherwise, c ? undef : x -> x. } else { @@ -1487,17 +1466,17 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // Check to see if we have a branch or switch on an undefined value. If so // we force the branch to go one way or the other to make the successor // values live. It doesn't really matter which way we force it. - TerminatorInst *TI = BB->getTerminator(); + TerminatorInst *TI = BB.getTerminator(); if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { if (!BI->isConditional()) continue; - if (!getValueState(BI->getCondition()).isUndefined()) + if (!getValueState(BI->getCondition()).isUnknown()) continue; // If the input to SCCP is actually branch on undef, fix the undef to // false. if (isa<UndefValue>(BI->getCondition())) { BI->setCondition(ConstantInt::getFalse(BI->getContext())); - markEdgeExecutable(&*BB, TI->getSuccessor(1)); + markEdgeExecutable(&BB, TI->getSuccessor(1)); return true; } @@ -1510,16 +1489,14 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { } if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { - if (!SI->getNumCases()) - continue; - if (!getValueState(SI->getCondition()).isUndefined()) + if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown()) continue; // If the input to SCCP is actually switch on undef, fix the undef to // the first constant. if (isa<UndefValue>(SI->getCondition())) { SI->setCondition(SI->case_begin().getCaseValue()); - markEdgeExecutable(&*BB, SI->case_begin().getCaseSuccessor()); + markEdgeExecutable(&BB, SI->case_begin().getCaseSuccessor()); return true; } @@ -1531,75 +1508,53 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { return false; } - -namespace { - //===--------------------------------------------------------------------===// - // - /// SCCP Class - This class uses the SCCPSolver to implement a per-function - /// Sparse Conditional Constant Propagator. - /// - struct SCCP : public FunctionPass { - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired<TargetLibraryInfoWrapperPass>(); - AU.addPreserved<GlobalsAAWrapperPass>(); - } - static char ID; // Pass identification, replacement for typeid - SCCP() : FunctionPass(ID) { - initializeSCCPPass(*PassRegistry::getPassRegistry()); +static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { + Constant *Const = nullptr; + if (V->getType()->isStructTy()) { + std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V); + if (std::any_of(IVs.begin(), IVs.end(), + [](LatticeVal &LV) { return LV.isOverdefined(); })) + return false; + std::vector<Constant *> ConstVals; + StructType *ST = dyn_cast<StructType>(V->getType()); + for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { + LatticeVal V = IVs[i]; + ConstVals.push_back(V.isConstant() + ? V.getConstant() + : UndefValue::get(ST->getElementType(i))); } + Const = ConstantStruct::get(ST, ConstVals); + } else { + LatticeVal IV = Solver.getLatticeValueFor(V); + if (IV.isOverdefined()) + return false; + Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); + } + assert(Const && "Constant is nullptr here!"); + DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n'); - // runOnFunction - Run the Sparse Conditional Constant Propagation - // algorithm, and return true if the function was modified. - // - bool runOnFunction(Function &F) override; - }; -} // end anonymous namespace - -char SCCP::ID = 0; -INITIALIZE_PASS(SCCP, "sccp", - "Sparse Conditional Constant Propagation", false, false) - -// createSCCPPass - This is the public interface to this file. -FunctionPass *llvm::createSCCPPass() { - return new SCCP(); + // Replaces all of the uses of a variable with uses of the constant. + V->replaceAllUsesWith(Const); + return true; } -static void DeleteInstructionInBlock(BasicBlock *BB) { - DEBUG(dbgs() << " BasicBlock Dead:" << *BB); - ++NumDeadBlocks; - - // Check to see if there are non-terminating instructions to delete. - if (isa<TerminatorInst>(BB->begin())) - return; +static bool tryToReplaceInstWithConstant(SCCPSolver &Solver, Instruction *Inst, + bool shouldEraseFromParent) { + if (!tryToReplaceWithConstant(Solver, Inst)) + return false; - // Delete the instructions backwards, as it has a reduced likelihood of having - // to update as many def-use and use-def chains. - Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. - while (EndInst != BB->begin()) { - // Delete the next to last instruction. - Instruction *Inst = &*--EndInst->getIterator(); - if (!Inst->use_empty()) - Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); - if (Inst->isEHPad()) { - EndInst = Inst; - continue; - } - BB->getInstList().erase(Inst); - ++NumInstRemoved; - } + // Delete the instruction. + if (shouldEraseFromParent) + Inst->eraseFromParent(); + return true; } -// runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, +// runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, // and return true if the function was modified. // -bool SCCP::runOnFunction(Function &F) { - if (skipOptnoneFunction(F)) - return false; - +static bool runSCCP(Function &F, const DataLayout &DL, + const TargetLibraryInfo *TLI) { DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); - const DataLayout &DL = F.getParent()->getDataLayout(); - const TargetLibraryInfo *TLI = - &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); SCCPSolver Solver(DL, TLI); // Mark the first block of the function as being executable. @@ -1623,9 +1578,13 @@ 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. - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { - if (!Solver.isBlockExecutable(&*BB)) { - DeleteInstructionInBlock(&*BB); + for (BasicBlock &BB : F) { + if (!Solver.isBlockExecutable(&BB)) { + DEBUG(dbgs() << " BasicBlock Dead:" << BB); + + ++NumDeadBlocks; + NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB); + MadeChanges = true; continue; } @@ -1633,70 +1592,74 @@ bool SCCP::runOnFunction(Function &F) { // Iterate over all of the instructions in a function, replacing them with // constants if we have found them to be of constant values. // - for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { + for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { Instruction *Inst = &*BI++; if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst)) continue; - // TODO: Reconstruct structs from their elements. - if (Inst->getType()->isStructTy()) - continue; - - LatticeVal IV = Solver.getLatticeValueFor(Inst); - if (IV.isOverdefined()) - continue; - - Constant *Const = IV.isConstant() - ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n'); - - // Replaces all of the uses of a variable with uses of the constant. - Inst->replaceAllUsesWith(Const); - - // Delete the instruction. - Inst->eraseFromParent(); - - // Hey, we just changed something! - MadeChanges = true; - ++NumInstRemoved; + if (tryToReplaceInstWithConstant(Solver, Inst, + true /* shouldEraseFromParent */)) { + // Hey, we just changed something! + MadeChanges = true; + ++NumInstRemoved; + } } } return MadeChanges; } +PreservedAnalyses SCCPPass::run(Function &F, AnalysisManager<Function> &AM) { + const DataLayout &DL = F.getParent()->getDataLayout(); + auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); + if (!runSCCP(F, DL, &TLI)) + return PreservedAnalyses::all(); + + auto PA = PreservedAnalyses(); + PA.preserve<GlobalsAA>(); + return PA; +} + namespace { - //===--------------------------------------------------------------------===// +//===--------------------------------------------------------------------===// +// +/// SCCP Class - This class uses the SCCPSolver to implement a per-function +/// Sparse Conditional Constant Propagator. +/// +class SCCPLegacyPass : public FunctionPass { +public: + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<TargetLibraryInfoWrapperPass>(); + AU.addPreserved<GlobalsAAWrapperPass>(); + } + static char ID; // Pass identification, replacement for typeid + SCCPLegacyPass() : FunctionPass(ID) { + initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + // runOnFunction - Run the Sparse Conditional Constant Propagation + // algorithm, and return true if the function was modified. // - /// IPSCCP Class - This class implements interprocedural Sparse Conditional - /// Constant Propagation. - /// - struct IPSCCP : public ModulePass { - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired<TargetLibraryInfoWrapperPass>(); - } - static char ID; - IPSCCP() : ModulePass(ID) { - initializeIPSCCPPass(*PassRegistry::getPassRegistry()); - } - bool runOnModule(Module &M) override; - }; + bool runOnFunction(Function &F) override { + if (skipFunction(F)) + return false; + const DataLayout &DL = F.getParent()->getDataLayout(); + const TargetLibraryInfo *TLI = + &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); + return runSCCP(F, DL, TLI); + } +}; } // end anonymous namespace -char IPSCCP::ID = 0; -INITIALIZE_PASS_BEGIN(IPSCCP, "ipsccp", - "Interprocedural Sparse Conditional Constant Propagation", - false, false) +char SCCPLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp", + "Sparse Conditional Constant Propagation", false, false) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_END(IPSCCP, "ipsccp", - "Interprocedural Sparse Conditional Constant Propagation", - false, false) - -// createIPSCCPPass - This is the public interface to this file. -ModulePass *llvm::createIPSCCPPass() { - return new IPSCCP(); -} +INITIALIZE_PASS_END(SCCPLegacyPass, "sccp", + "Sparse Conditional Constant Propagation", false, false) +// createSCCPPass - This is the public interface to this file. +FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); } static bool AddressIsTaken(const GlobalValue *GV) { // Delete any dead constantexpr klingons. @@ -1725,10 +1688,8 @@ static bool AddressIsTaken(const GlobalValue *GV) { return false; } -bool IPSCCP::runOnModule(Module &M) { - const DataLayout &DL = M.getDataLayout(); - const TargetLibraryInfo *TLI = - &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); +static bool runIPSCCP(Module &M, const DataLayout &DL, + const TargetLibraryInfo *TLI) { SCCPSolver Solver(DL, TLI); // AddressTakenFunctions - This set keeps track of the address-taken functions @@ -1741,32 +1702,32 @@ bool IPSCCP::runOnModule(Module &M) { // Loop over all functions, marking arguments to those with their addresses // taken or that are external as overdefined. // - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) + for (Function &F : M) { + if (F.isDeclaration()) continue; - // If this is a strong or ODR definition of this function, then we can - // propagate information about its result into callsites of it. - if (!F->mayBeOverridden()) - Solver.AddTrackedFunction(&*F); + // If this is an exact definition of this function, then we can propagate + // information about its result into callsites of it. + if (F.hasExactDefinition()) + Solver.AddTrackedFunction(&F); // If this function only has direct calls that we can see, we can track its // arguments and return value aggressively, and can assume it is not called // unless we see evidence to the contrary. - if (F->hasLocalLinkage()) { - if (AddressIsTaken(&*F)) - AddressTakenFunctions.insert(&*F); + if (F.hasLocalLinkage()) { + if (AddressIsTaken(&F)) + AddressTakenFunctions.insert(&F); else { - Solver.AddArgumentTrackedFunction(&*F); + Solver.AddArgumentTrackedFunction(&F); continue; } } // Assume the function is called. - Solver.MarkBlockExecutable(&F->front()); + Solver.MarkBlockExecutable(&F.front()); // Assume nothing about the incoming arguments. - for (Argument &AI : F->args()) + for (Argument &AI : F.args()) Solver.markAnythingOverdefined(&AI); } @@ -1784,8 +1745,8 @@ bool IPSCCP::runOnModule(Module &M) { DEBUG(dbgs() << "RESOLVING UNDEFS\n"); ResolvedUndefs = false; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) - ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); + for (Function &F : M) + ResolvedUndefs |= Solver.ResolvedUndefsIn(F); } bool MadeChanges = false; @@ -1795,79 +1756,47 @@ bool IPSCCP::runOnModule(Module &M) { // SmallVector<BasicBlock*, 512> BlocksToErase; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { - if (F->isDeclaration()) + for (Function &F : M) { + if (F.isDeclaration()) continue; - if (Solver.isBlockExecutable(&F->front())) { - for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); - AI != E; ++AI) { - if (AI->use_empty() || AI->getType()->isStructTy()) continue; - - // TODO: Could use getStructLatticeValueFor to find out if the entire - // result is a constant and replace it entirely if so. - - LatticeVal IV = Solver.getLatticeValueFor(&*AI); - if (IV.isOverdefined()) continue; - - Constant *CST = IV.isConstant() ? - IV.getConstant() : UndefValue::get(AI->getType()); - DEBUG(dbgs() << "*** Arg " << *AI << " = " << *CST <<"\n"); - - // Replaces all of the uses of a variable with uses of the - // constant. - AI->replaceAllUsesWith(CST); - ++IPNumArgsElimed; + if (Solver.isBlockExecutable(&F.front())) { + for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; + ++AI) { + if (AI->use_empty()) + continue; + if (tryToReplaceWithConstant(Solver, &*AI)) + ++IPNumArgsElimed; } } - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (!Solver.isBlockExecutable(&*BB)) { - DeleteInstructionInBlock(&*BB); - MadeChanges = true; + DEBUG(dbgs() << " BasicBlock Dead:" << *BB); - TerminatorInst *TI = BB->getTerminator(); - for (BasicBlock *Succ : TI->successors()) { - if (!Succ->empty() && isa<PHINode>(Succ->begin())) - Succ->removePredecessor(&*BB); - } - if (!TI->use_empty()) - TI->replaceAllUsesWith(UndefValue::get(TI->getType())); - TI->eraseFromParent(); - new UnreachableInst(M.getContext(), &*BB); + ++NumDeadBlocks; + NumInstRemoved += + changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false); + + MadeChanges = true; - if (&*BB != &F->front()) + if (&*BB != &F.front()) BlocksToErase.push_back(&*BB); continue; } for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { Instruction *Inst = &*BI++; - if (Inst->getType()->isVoidTy() || Inst->getType()->isStructTy()) + if (Inst->getType()->isVoidTy()) continue; - - // TODO: Could use getStructLatticeValueFor to find out if the entire - // result is a constant and replace it entirely if so. - - LatticeVal IV = Solver.getLatticeValueFor(Inst); - if (IV.isOverdefined()) - continue; - - Constant *Const = IV.isConstant() - ? IV.getConstant() : UndefValue::get(Inst->getType()); - DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n'); - - // Replaces all of the uses of a variable with uses of the - // constant. - Inst->replaceAllUsesWith(Const); - - // Delete the instruction. - if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst)) - Inst->eraseFromParent(); - - // Hey, we just changed something! - MadeChanges = true; - ++IPNumInstRemoved; + if (tryToReplaceInstWithConstant( + Solver, Inst, + !isa<CallInst>(Inst) && + !isa<TerminatorInst>(Inst) /* shouldEraseFromParent */)) { + // Hey, we just changed something! + MadeChanges = true; + ++IPNumInstRemoved; + } } } @@ -1918,7 +1847,7 @@ bool IPSCCP::runOnModule(Module &M) { } // Finally, delete the basic block. - F->getBasicBlockList().erase(DeadBB); + F.getBasicBlockList().erase(DeadBB); } BlocksToErase.clear(); } @@ -1937,18 +1866,17 @@ bool IPSCCP::runOnModule(Module &M) { // TODO: Process multiple value ret instructions also. const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals(); - for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(), - E = RV.end(); I != E; ++I) { - Function *F = I->first; - if (I->second.isOverdefined() || F->getReturnType()->isVoidTy()) + for (const auto &I : RV) { + Function *F = I.first; + if (I.second.isOverdefined() || F->getReturnType()->isVoidTy()) continue; // We can only do this if we know that nothing else can call the function. if (!F->hasLocalLinkage() || AddressTakenFunctions.count(F)) continue; - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) + for (BasicBlock &BB : *F) + if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) if (!isa<UndefValue>(RI->getOperand(0))) ReturnsToZap.push_back(RI); } @@ -1978,3 +1906,52 @@ bool IPSCCP::runOnModule(Module &M) { return MadeChanges; } + +PreservedAnalyses IPSCCPPass::run(Module &M, AnalysisManager<Module> &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(); } |