[SCCP] Calculate Null Pointer Comparisons

[njw45]

Summary

Loading from a null pointer is undefined; the SimplifyCfg pass correctly decides that any conditional branches that lead to a null pointer derefence can't be taken, and so replaces them with an unconditional branch. We can go further though; if the branch in question post-dominates the Value used to decide which branch to take, then we know exactly what constant that is everywhere in the function. If the Value is a cmp instruction, then we don't need to evaluate it any more - this patch replaces all uses of the comparison with the known constant and removes the unneeded instruction.

[• dberlin]

This looks generally good.

Do you have any numbers on how often it triggers/helps?
Same with compilation time cost.

It would be nice to know both. The first should be easy, just adding another Statistic to the top and looking at it.

[sanjoy]

I'm not sure that this is doing the right thing -- I don't think simply producing undef implies undefined behavior.

For instance, in

declare void @g()

define i1 @test_postdominate(i8* %mem) {
  %test = icmp eq i8* %mem, null
  br i1 %test, label %a, label %b
a:
  call void @g()
  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
}

if %mem is null, then we have to execute the call to @g, but this pass make the branch into a dead (so @f never calls @g). The fact that %gep is undef (or poison) does not make this program undefined. In fact, if inbounds GEP instructions could invoke UB, then we would not be able to hoist such instructions out of loops.

[njw45]

Change to SimplifyCFG, not SCCP

[njw45]

Does it make sense to make simplifycfg smarter instead of sccp?

Yes - that makes the code change much smaller (no need for a custom
visitor)! I've pushed a (completely) new version of the patch to
http://reviews.llvm.org/D9634 . Thanks -

Nick

[reames]

Please provide a real description of the change. You'll need a submission comment eventually, please write that and add it to the review. Also, please update the title. This is not specific to null checks.

lib/Transforms/Utils/SimplifyCFG.cpp

4626 ↗

(On Diff #25734)

This is wrong since the condition may not be in the same basic block as the branch we're reasoning about. You can replace dominated uses, but not all uses.

You might find these changes interesting:
http://reviews.llvm.org/D9312 - this ones directly analogous in JumpThreading.
http://reviews.llvm.org/D9763 - this prunes a lot of easy cases earlier in the pipeline, possibly removing a bunch of pass ordering problems

[njw45]

Ensure we only replace the conditional if we postdominate it (+test)

[njw45]

Please provide a real description of the change.

I've updated the review description - hope it's OK now!

You can replace dominated uses

Ah yes, I've carried that functionality forward from the SCCP version
of the patch. Unfortunately the SimplifyCFG pass has been updated to
use the new pass manager, but the post-dominator tree analysis hasn't,
so this patch now converts it to too (so it's now +250 -157). I've
also added another unit test to prove that it doesn't do the
optimisation when the branch doesn't post-dominate the test.

Thanks -

Nick

[njw45]

remove trailing whitespace from test

[reames]

To my knowledge, post-dominance information is not currently used within LLVM's existing passes. As a result, you'd need to justify the cost of the post-dom-tree computation.

I strongly request that you implement the trivial post dominance case (i.e. in same basic block as per the linked patch) to start with. If you then want to propose using post-dominance information more widely, I'm open to that discussion. I just don't want to couple of the optimization at hand with a broader (and harder to justify) discussion.

Once the optimizations in, we could either enhance it by pursuing the post-dominance information or by using the replaceDominatesUses mechanism from GVN and (soon) EarlyCSE.

p.s. You haven't updated any of the existing transforms to keep the post dominance info up to date. As a result, the code as currently structured is really, really wrong.

p.p.s. Your description mentions icmps. I don't get why you're making the restriction. Regardless of the source, you know the value of the Value. Your actual code doesn't seem to have this restriction.

lib/Transforms/Scalar/SampleProfile.cpp

100 ↗

(On Diff #25873)

I think you've mixed patches here?

[reames]

Removing myself as review from an aparently abandoned review. Feel free to readd me as a reviewer for new updates. I'm only removing so that I don't see this in my list of pending reviews.

include/llvm/Analysis/PtrUseVisitor.h

protected:
   /// Note that the constructor is protected because this class must be a base
   /// class, we can't create instances directly of this class.
   PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}
 
   /// \brief Enqueue the users of this instruction in the visit worklist.
   ///
   /// 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.
   ///
   /// This routine does the heavy lifting of the pointer walk by computing
   /// offsets and looking through GEPs.
   bool adjustOffsetForGEP(GetElementPtrInst &GEPI);
 };
 } // end namespace detail
class PtrUseVisitor : protected InstVisitor<DerivedT>,
   friend class InstVisitor<DerivedT>;
   typedef InstVisitor<DerivedT> Base;
 
 public:
   PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) {}
 
   /// \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.
     assert(I.getType()->isPointerTy());
     IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType()));
     IsOffsetKnown = true;
     Offset = APInt(IntPtrTy->getBitWidth(), 0);
     PI.reset();
 
     // Enqueue the uses of this pointer.
     enqueueUsers(I);
 
     // Visit all the uses off the worklist until it is empty.
     while (!Worklist.empty()) {
       UseToVisit ToVisit = Worklist.pop_back_val();
       U = ToVisit.UseAndIsOffsetKnown.getPointer();
       IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt();
       if (IsOffsetKnown)
         Offset = std::move(ToVisit.Offset);
 
-      Instruction *I = cast<Instruction>(U->getUser());
-      static_cast<DerivedT*>(this)->visit(I);
+      if (Instruction *I = dyn_cast<Instruction>(U->getUser()))
+        static_cast<DerivedT *>(this)->visit(I);
       if (PI.isAborted())
         break;
     }
     return PI;
   }
 
 protected:
   void visitStoreInst(StoreInst &SI) {
     if (SI.getValueOperand() == U->get())
       PI.setEscaped(&SI);
   }
 
   void visitBitCastInst(BitCastInst &BC) {
     enqueueUsers(BC);
   }
 
   void visitPtrToIntInst(PtrToIntInst &I) {
     PI.setEscaped(&I);
   }
 
+  void visitPHINode(PHINode &PHI) { enqueueUsers(PHI); }
+
   void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
     if (GEPI.use_empty())
       return;
 
     // If we can't walk the GEP, clear the offset.
     if (!adjustOffsetForGEP(GEPI)) {
       IsOffsetKnown = false;
       Offset = APInt();

lib/Analysis/PtrUseVisitor.cpp

 /// Implementation of the pointer use visitors.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/PtrUseVisitor.h"
 
 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 = {
         UseToVisit::UseAndIsOffsetKnownPair(&U, IsOffsetKnown),
         Offset
       };
       Worklist.push_back(std::move(NewU));
     }

lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/Transforms/Scalar.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/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"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"

 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
 /// Constant Propagation.
 ///
 class SCCPSolver : public InstVisitor<SCCPSolver> {
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
+  const PostDominatorTree *PDT;
   SmallPtrSet<BasicBlock*, 8> BBExecutable; // The BBs that are executable.
   DenseMap<Value*, LatticeVal> ValueState;  // The state each value is in.
 
   /// StructValueState - This maintains ValueState for values that have
   /// StructType, for example for formal arguments, calls, insertelement, etc.
   ///
   DenseMap<std::pair<Value*, unsigned>, LatticeVal> StructValueState;
 
class SCCPSolver : public InstVisitor<SCCPSolver> {
 
   SmallVector<BasicBlock*, 64>  BBWorkList;  // The BasicBlock work list
 
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   typedef std::pair<BasicBlock*, BasicBlock*> Edge;
   DenseSet<Edge> 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.
   ///
   /// This returns true if the block was not considered live before.
   bool MarkBlockExecutable(BasicBlock *BB) {
     if (!BBExecutable.insert(BB).second)
       return false;
private:
   // information, we need to update the specified user of this instruction.
   //
   void OperandChangedState(Instruction *I) {
     if (BBExecutable.count(I->getParent()))   // Inst is executable?
       visit(*I);
   }
 
 private:
+  class NullChecker;
+  friend class SCCPSolver::NullChecker;
   friend class InstVisitor<SCCPSolver>;
 
   // visit implementations - Something changed in this instruction.  Either an
   // operand made a transition, or the instruction is newly executable.  Change
   // the value type of I to reflect these changes if appropriate.
   void visitPHINode(PHINode &I);
 
   // Terminators
if (NonOverdefVal) {
       }
     }
   }
 
 
   markOverdefined(&I);
 }
 
+class SCCPSolver::NullChecker : public PtrUseVisitor<NullChecker> {
+  friend class PtrUseVisitor<NullChecker>;
+  friend class InstVisitor<NullChecker>;
+  typedef PtrUseVisitor<NullChecker> 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<NullChecker>(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));
   LatticeVal V2State = getValueState(I.getOperand(1));
 
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined()) return;
 
   if (V1State.isConstant() && V2State.isConstant())
     return markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(),
                                                          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;
 
   markOverdefined(&I);
 }
 
 void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) {
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.addRequired<PostDominatorTree>();
     }
     static char ID; // Pass identification, replacement for typeid
     SCCP() : FunctionPass(ID) {
       initializeSCCPPass(*PassRegistry::getPassRegistry());
     }
 
     // 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)
+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() {
   return new SCCP();
 }
 
 static void DeleteInstructionInBlock(BasicBlock *BB) {
   DEBUG(dbgs() << "  BasicBlock Dead:" << *BB);

 bool SCCP::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
   const DataLayout &DL = F.getParent()->getDataLayout();
   const TargetLibraryInfo *TLI =
       &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
-  SCCPSolver Solver(DL, TLI);
+  const PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
+  SCCPSolver Solver(DL, TLI, PDT);
 
   // Mark the first block of the function as being executable.
   Solver.MarkBlockExecutable(F.begin());
 
   // Mark all arguments to the function as being overdefined.
   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI)
     Solver.markAnythingOverdefined(AI);
 
namespace {
   };
 } // end anonymous namespace
 
 char IPSCCP::ID = 0;
 INITIALIZE_PASS_BEGIN(IPSCCP, "ipsccp",
                 "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)
 
 // createIPSCCPPass - This is the public interface to this file.
 ModulePass *llvm::createIPSCCPPass() {
   return new IPSCCP();
 }
static bool AddressIsTaken(const GlobalValue *GV) {
   }
   return false;
 }
 
 bool IPSCCP::runOnModule(Module &M) {
   const DataLayout &DL = M.getDataLayout();
   const TargetLibraryInfo *TLI =
       &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
-  SCCPSolver Solver(DL, TLI);
+  const PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
+  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,
   // functions that were address taken can end up losing their
   // address-taken-ness.  Because of this, we keep track of their addresses from
   // the first pass so we can use them for the later simplification pass.
   SmallPtrSet<Function*, 32> AddressTakenFunctions;
 

test/Transforms/SCCP/gep-inbounds-postdominate.ll

+; 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
+}