Index: include/llvm/Analysis/PtrUseVisitor.h =================================================================== --- include/llvm/Analysis/PtrUseVisitor.h +++ include/llvm/Analysis/PtrUseVisitor.h @@ -154,7 +154,7 @@ /// /// This will visit the users with the same offset of the current visit /// (including an unknown offset if that is the current state). - void enqueueUsers(Instruction &I); + void enqueueUsers(Value &I); /// \brief Walk the operands of a GEP and adjust the offset as appropriate. /// @@ -200,7 +200,7 @@ /// \brief Recursively visit the uses of the given pointer. /// \returns An info struct about the pointer. See \c PtrInfo for details. - PtrInfo visitPtr(Instruction &I) { + PtrInfo visitPtr(Value &I) { // This must be a pointer type. Get an integer type suitable to hold // offsets on this pointer. // FIXME: Support a vector of pointers. @@ -221,8 +221,8 @@ if (IsOffsetKnown) Offset = std::move(ToVisit.Offset); - Instruction *I = cast(U->getUser()); - static_cast(this)->visit(I); + if (Instruction *I = dyn_cast(U->getUser())) + static_cast(this)->visit(I); if (PI.isAborted()) break; } @@ -243,6 +243,8 @@ PI.setEscaped(&I); } + void visitPHINode(PHINode &PHI) { enqueueUsers(PHI); } + void visitGetElementPtrInst(GetElementPtrInst &GEPI) { if (GEPI.use_empty()) return; Index: lib/Analysis/PtrUseVisitor.cpp =================================================================== --- lib/Analysis/PtrUseVisitor.cpp +++ lib/Analysis/PtrUseVisitor.cpp @@ -15,7 +15,7 @@ using namespace llvm; -void detail::PtrUseVisitorBase::enqueueUsers(Instruction &I) { +void detail::PtrUseVisitorBase::enqueueUsers(Value &I) { for (Use &U : I.uses()) { if (VisitedUses.insert(&U).second) { UseToVisit NewU = { Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -25,6 +25,8 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/Analysis/PtrUseVisitor.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" @@ -156,6 +158,7 @@ class SCCPSolver : public InstVisitor { const DataLayout &DL; const TargetLibraryInfo *TLI; + const PostDominatorTree *PDT; SmallPtrSet BBExecutable; // The BBs that are executable. DenseMap ValueState; // The state each value is in. @@ -206,8 +209,9 @@ typedef std::pair Edge; DenseSet KnownFeasibleEdges; public: - SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) - : DL(DL), TLI(tli) {} + SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli, + const PostDominatorTree *PDT) + : DL(DL), TLI(tli), PDT(PDT) {} /// 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. @@ -458,6 +462,8 @@ } private: + class NullChecker; + friend class SCCPSolver::NullChecker; friend class InstVisitor; // visit implementations - Something changed in this instruction. Either an @@ -901,6 +907,38 @@ markOverdefined(&I); } +class SCCPSolver::NullChecker : public PtrUseVisitor { + friend class PtrUseVisitor; + friend class InstVisitor; + typedef PtrUseVisitor Base; + + SCCPSolver &Solver; + CmpInst &I; + LatticeVal &IV; + const PostDominatorTree *PDT; + +public: + NullChecker(const DataLayout &DL, SCCPSolver &Solver, CmpInst &I, + LatticeVal &IV, const PostDominatorTree *PDT) + : PtrUseVisitor(DL), Solver(Solver), I(I), IV(IV), PDT(PDT) { + } + + void visitGetElementPtrInst(GetElementPtrInst &GEPI) { + if (GEPI.isInBounds() && GEPI.getAddressSpace() == 0 && + PDT->dominates(GEPI.getParent(), I.getParent())) { + + assert(I.isEquality() && "Logic only handles equality cases"); + auto CmpResult = I.isTrueWhenEqual() ? ConstantInt::getFalse(I.getType()) + : ConstantInt::getTrue(I.getType()); + + Solver.markConstant(IV, &I, CmpResult); + PI.setAborted(&GEPI); + } else { + Base::visitGetElementPtrInst(GEPI); + } + } +}; + // Handle ICmpInst instruction. void SCCPSolver::visitCmpInst(CmpInst &I) { LatticeVal V1State = getValueState(I.getOperand(0)); @@ -914,6 +952,17 @@ V1State.getConstant(), V2State.getConstant())); + if (I.getOperand(0)->getType()->isPointerTy() && I.isEquality() && + ((V1State.isConstant() && V1State.getConstant()->isNullValue()) || + (V2State.isConstant() && V2State.getConstant()->isNullValue()))) { + + // Get the Value is a compared against a null pointer + Value *V = I.getOperand(V1State.isConstant() ? 1 : 0); + auto Info = NullChecker(DL, *this, I, IV, PDT).visitPtr(*V); + if (Info.isAborted()) + return; // we marked it a constant + } + // If operands are still undefined, wait for it to resolve. if (!V1State.isOverdefined() && !V2State.isOverdefined()) return; @@ -1506,6 +1555,7 @@ struct SCCP : public FunctionPass { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); + AU.addRequired(); } static char ID; // Pass identification, replacement for typeid SCCP() : FunctionPass(ID) { @@ -1520,8 +1570,11 @@ } // end anonymous namespace char SCCP::ID = 0; -INITIALIZE_PASS(SCCP, "sccp", - "Sparse Conditional Constant Propagation", false, false) +INITIALIZE_PASS_BEGIN(SCCP, "sccp", "Sparse Conditional Constant Propagation", + false, false) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) +INITIALIZE_PASS_END(SCCP, "sccp", "Sparse Conditional Constant Propagation", + false, false) // createSCCPPass - This is the public interface to this file. FunctionPass *llvm::createSCCPPass() { @@ -1565,7 +1618,8 @@ const DataLayout &DL = F.getParent()->getDataLayout(); const TargetLibraryInfo *TLI = &getAnalysis().getTLI(); - SCCPSolver Solver(DL, TLI); + const PostDominatorTree *PDT = &getAnalysis(); + SCCPSolver Solver(DL, TLI, PDT); // Mark the first block of the function as being executable. Solver.MarkBlockExecutable(F.begin()); @@ -1653,6 +1707,7 @@ "Interprocedural Sparse Conditional Constant Propagation", false, false) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) INITIALIZE_PASS_END(IPSCCP, "ipsccp", "Interprocedural Sparse Conditional Constant Propagation", false, false) @@ -1694,7 +1749,8 @@ const DataLayout &DL = M.getDataLayout(); const TargetLibraryInfo *TLI = &getAnalysis().getTLI(); - SCCPSolver Solver(DL, TLI); + const PostDominatorTree *PDT = &getAnalysis(); + SCCPSolver Solver(DL, TLI, PDT); // AddressTakenFunctions - This set keeps track of the address-taken functions // that are in the input. As IPSCCP runs through and simplifies code, Index: test/Transforms/SCCP/gep-inbounds-postdominate.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/gep-inbounds-postdominate.ll @@ -0,0 +1,47 @@ +; RUN: opt < %s -sccp -S | FileCheck %s + +; CHECK-LABEL: @test_false +; CHECK: ret i1 false +define i1 @test_false(i8* %mem) { + %test = icmp eq i8* %mem, null + %gep = getelementptr inbounds i8, i8* %mem, i64 4 + ret i1 %test +} + +; CHECK-LABEL: @test_true +; CHECK: ret i1 true +define i1 @test_true(i8* %mem) { + %test = icmp ne i8* %mem, null + %gep = getelementptr inbounds i8, i8* %mem, i64 4 + ret i1 %test +} + +; CHECK-LABEL: @test_postdominate +; CHECK: ret i1 false +define i1 @test_postdominate(i8* %mem) { + %test = icmp eq i8* %mem, null + br i1 %test, label %a, label %b +a: + br label %c +b: + br label %c +c: + %join = phi i8* [ %mem, %a ], [ null, %b ] + %gep = getelementptr inbounds i8, i8* %join, i64 4 + ret i1 %test +} + +; CHECK-LABEL: @test_no_postdominate +; CHECK: ret i1 %test +define i1 @test_no_postdominate(i8* %mem) { + %test = icmp eq i8* %mem, null + br i1 %test, label %a, label %b +a: + br label %c +b: + %gep = getelementptr inbounds i8, i8* %mem, i64 4 + br label %c +c: + %join = phi i8* [ %mem, %a ], [ null, %b ] + ret i1 %test +}