[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

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.

lib/Transforms/Utils/SimplifyCFG.cpp

static bool removeUndefIntroducingPredecessor(BasicBlock *BB) {
   for (BasicBlock::iterator i = BB->begin();
        PHINode *PHI = dyn_cast<PHINode>(i); ++i)
     for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
       if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) {
         TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator();
         IRBuilder<> Builder(T);
         if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
           BB->removePredecessor(PHI->getIncomingBlock(i));
-          // Turn uncoditional branches into unreachables and remove the dead
+          // Turn unconditional branches into unreachables and remove the dead
           // destination from conditional branches.
           if (BI->isUnconditional())
             Builder.CreateUnreachable();
-          else
-            Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) :
-                                                         BI->getSuccessor(0));
+          else {
+            bool PickFirst = BI->getSuccessor(1) == BB;
+            Builder.CreateBr(PickFirst
+              ? BI->getSuccessor(0)
+              : BI->getSuccessor(1));
+            if (auto Cond = dyn_cast<Instruction>(BI->getCondition())) {
+              // Inline the result of the conditional check downstream as a
+              // constant, and then get rid of it if possible.
+              Value *Const = ConstantInt::get(Cond->getType(), PickFirst);
+              Cond->replaceAllUsesWith(Const);
+              RecursivelyDeleteTriviallyDeadInstructions(Cond);
+            }
+          }
           BI->eraseFromParent();
           return true;
         }
         // TODO: SwitchInst.
       }
 
   return false;
 }

test/Transforms/SimplifyCFG/load-means-not-null.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+declare void @g(i8)
+
+; CHECK-LABEL: @test_postdominate
+; CHECK-NEXT: a:
+; CHECK-NEXT: call void @g(i8 0)
+; CHECK: ret i1 true
+define i1 @test_postdominate(i8* %mem) {
+  %test = icmp eq i8* %mem, null
+  br i1 %test, label %a, label %b
+a:
+  call void @g(i8 0)
+  br label %c
+b:
+  br label %c
+c:
+  %join = phi i8* [ %mem, %a ], [ null, %b ]
+  %gep = getelementptr i8, i8* %join, i64 4
+  %res = load i8, i8* %gep
+  call void @g(i8 %res)
+  ret i1 %test
+}

test/Transforms/SimplifyCFG/phi-undef-loadstore.ll

if.then4:                                         ; preds = %if.else
   br label %if.end7
 
 if.end7:                                          ; preds = %if.else, %if.then4, %if.then
   %x.0 = phi i32* [ %a, %if.then ], [ %c, %if.then4 ], [ null, %if.else ]
   %tmp9 = load i32, i32* %x.0
   ret i32 %tmp9
 
 ; CHECK-LABEL: @test1(
-; CHECK: if.else:
-; CHECK: br label %if.end7
-
-; CHECK: phi i32* [ %a, %if.then ], [ %c, %if.else ]
+; CHECK: tail call void @bar()
+; CHECK: %c.a = select i1 %tobool, i32* %c, i32* %a
+; CHECK: %tmp9 = load i32, i32* %c.a
 }
 
 define i32 @test2(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   tail call void @bar() nounwind
   br label %if.end7
 
 if.else:                                          ; preds = %entry
   %tobool3 = icmp eq i32 %d, 0
   br i1 %tobool3, label %if.end7, label %if.then4
 
 if.then4:                                         ; preds = %if.else
   tail call void @bar() nounwind
   br label %if.end7
 
 if.end7:                                          ; preds = %if.else, %if.then4, %if.then
   %x.0 = phi i32* [ %a, %if.then ], [ null, %if.then4 ], [ null, %if.else ]
   %tmp9 = load i32, i32* %x.0
   ret i32 %tmp9
 ; CHECK-LABEL: @test2(
-; CHECK: if.else:
-; CHECK: unreachable
-
+; CHECK: tail call void @bar()
+; CHECK: %tmp9 = load i32, i32* %a
 ; CHECK-NOT: phi
 }
 
 define i32 @test3(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then