From 6f5c6adbcd287391f313231cd5dd13a85f02c3f1 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Wed, 25 Jul 2018 11:13:40 +0000 Subject: Recommit r333268: [IPSCCP] Use PredicateInfo to propagate facts from cmp instructions. r337828 resolves a PredicateInfo issue with unnamed types. Original message: This patch updates IPSCCP to use PredicateInfo to propagate facts to true branches predicated by EQ and to false branches predicated by NE. As a follow up, we should be able to extend it to also propagate additional facts about nonnull. Reviewers: davide, mssimpso, dberlin, efriedma Reviewed By: davide, dberlin llvm-svn: 337904 --- llvm/lib/Transforms/Scalar/SCCP.cpp | 126 +++++++++++++++++++++++++++++++++--- 1 file changed, 118 insertions(+), 8 deletions(-) (limited to 'llvm/lib/Transforms/Scalar/SCCP.cpp') diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp index 5e3ddeda2d4..c9d7810c5a3 100644 --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -55,6 +55,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/PredicateInfo.h" #include #include #include @@ -246,7 +247,21 @@ class SCCPSolver : public InstVisitor { using Edge = std::pair; DenseSet KnownFeasibleEdges; + DenseMap> PredInfos; + DenseMap> AdditionalUsers; + public: + void addPredInfo(Function &F, std::unique_ptr PI) { + PredInfos[&F] = std::move(PI); + } + + const PredicateBase *getPredicateInfoFor(Instruction *I) { + auto PI = PredInfos.find(I->getFunction()); + if (PI == PredInfos.end()) + return nullptr; + return PI->second->getPredicateInfoFor(I); + } + SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) : DL(DL), TLI(tli) {} @@ -558,6 +573,26 @@ private: visit(*I); } + // Add U as additional user of V. + void addAdditionalUser(Value *V, User *U) { + auto Iter = AdditionalUsers.insert({V, {}}); + Iter.first->second.insert(U); + } + + // Mark I's users as changed, including AdditionalUsers. + void markUsersAsChanged(Value *I) { + for (User *U : I->users()) + if (auto *UI = dyn_cast(U)) + OperandChangedState(UI); + + auto Iter = AdditionalUsers.find(I); + if (Iter != AdditionalUsers.end()) { + for (User *U : Iter->second) + if (auto *UI = dyn_cast(U)) + OperandChangedState(UI); + } + } + private: friend class InstVisitor; @@ -1119,6 +1154,65 @@ void SCCPSolver::visitCallSite(CallSite CS) { Function *F = CS.getCalledFunction(); Instruction *I = CS.getInstruction(); + if (auto *II = dyn_cast(I)) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) { + if (ValueState[I].isOverdefined()) + return; + + auto *PI = getPredicateInfoFor(I); + if (!PI) + return; + + auto *PBranch = dyn_cast(getPredicateInfoFor(I)); + if (!PBranch) { + mergeInValue(ValueState[I], I, getValueState(PI->OriginalOp)); + return; + } + + Value *CopyOf = I->getOperand(0); + Value *Cond = PBranch->Condition; + + // Everything below relies on the condition being a comparison. + auto *Cmp = dyn_cast(Cond); + if (!Cmp) { + mergeInValue(ValueState[I], I, getValueState(PI->OriginalOp)); + return; + } + + Value *CmpOp0 = Cmp->getOperand(0); + Value *CmpOp1 = Cmp->getOperand(1); + if (CopyOf != CmpOp0 && CopyOf != CmpOp1) { + mergeInValue(ValueState[I], I, getValueState(PI->OriginalOp)); + return; + } + + if (CmpOp0 != CopyOf) + std::swap(CmpOp0, CmpOp1); + + LatticeVal OriginalVal = getValueState(CopyOf); + LatticeVal EqVal = getValueState(CmpOp1); + LatticeVal &IV = ValueState[I]; + if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) { + addAdditionalUser(CmpOp1, I); + if (OriginalVal.isConstant()) + mergeInValue(IV, I, OriginalVal); + else + mergeInValue(IV, I, EqVal); + return; + } + if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) { + addAdditionalUser(CmpOp1, I); + if (OriginalVal.isConstant()) + mergeInValue(IV, I, OriginalVal); + else + mergeInValue(IV, I, EqVal); + return; + } + + return (void)mergeInValue(IV, I, getValueState(PBranch->OriginalOp)); + } + } + // The common case is that we aren't tracking the callee, either because we // are not doing interprocedural analysis or the callee is indirect, or is // external. Handle these cases first. @@ -1238,9 +1332,7 @@ void SCCPSolver::Solve() { // since all of its users will have already been marked as overdefined // Update all of the users of this instruction's value. // - for (User *U : I->users()) - if (auto *UI = dyn_cast(U)) - OperandChangedState(UI); + markUsersAsChanged(I); } // Process the instruction work list. @@ -1257,9 +1349,7 @@ void SCCPSolver::Solve() { // Update all of the users of this instruction's value. // if (I->getType()->isStructTy() || !getValueState(I).isOverdefined()) - for (User *U : I->users()) - if (auto *UI = dyn_cast(U)) - OperandChangedState(UI); + markUsersAsChanged(I); } // Process the basic block work list. @@ -1798,8 +1888,9 @@ static void findReturnsToZap(Function &F, } } -bool llvm::runIPSCCP(Module &M, const DataLayout &DL, - const TargetLibraryInfo *TLI) { +bool llvm::runIPSCCP( + Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, + function_ref(Function &)> getPredicateInfo) { SCCPSolver Solver(DL, TLI); // Loop over all functions, marking arguments to those with their addresses @@ -1808,6 +1899,7 @@ bool llvm::runIPSCCP(Module &M, const DataLayout &DL, if (F.isDeclaration()) continue; + Solver.addPredInfo(F, getPredicateInfo(F)); // Determine if we can track the function's return values. If so, add the // function to the solver's set of return-tracked functions. if (canTrackReturnsInterprocedurally(&F)) @@ -1960,6 +2052,24 @@ bool llvm::runIPSCCP(Module &M, const DataLayout &DL, F.getBasicBlockList().erase(DeadBB); } BlocksToErase.clear(); + + for (BasicBlock &BB : F) { + for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { + Instruction *Inst = &*BI++; + if (const PredicateBase *PI = Solver.getPredicateInfoFor(Inst)) { + if (auto *II = dyn_cast(Inst)) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) { + Value *Op = II->getOperand(0); + Inst->replaceAllUsesWith(Op); + Inst->eraseFromParent(); + continue; + } + } + Inst->replaceAllUsesWith(PI->OriginalOp); + Inst->eraseFromParent(); + } + } + } } // If we inferred constant or undef return values for a function, we replaced -- cgit v1.2.3