Extend EarlyCSE to handle basic cases from JumpThreading and CVP

[reames]

Summary

This patch extends EarlyCSE to take advantage of the information that a controlling branch gives us about the value of a Value within this and dominated basic blocks. If the current block has a single predecessor with a controlling branch, we can infer what the branch condition must have been to execute this block. The actual change to support this is downright simple because EarlyCSE's existing scoped hash table logic deals with most of the complexity around merging.

The patch actually implements two optimizations.

• The first is analogous to JumpThreading in that it enables EarlyCSE's CSE handling to fold branches which are exactly redundant due to a previous branch to branches on constants. (It doesn't actually replace the branch or change the CFG.) This is pretty clearly a win since it enables substantial CFG simplification before we start trying to inline.
• The second is analogous to CVP in that it exploits the knowledge gained to replace dominated *uses* of the original value. EarlyCSE does not otherwise reason about specific uses, so this is the more arguable one. It does enable further simplication and constant folding within the rest of the visit by EarlyCSE.

In both cases, the added code only handles the easy dominance based case of each optimization. The general case is deferred to the existing passes.

I believe both optimizations are worth adding, but I'm open to being convinced that the second should either be removed, or done differently.

[• dberlin]

lib/Transforms/Scalar/EarlyCSE.cpp

490

Can you common this part with GVN's replaceAllDominatedUsesWith?

(IE just move that function somewhere common and use it?)

[reames]

lib/Transforms/Scalar/EarlyCSE.cpp

490

Absolutely. Didn't know that existed. Would it make sense to put that directly on Value? Or would you rather see it as a helper function in Local.h or someplace similar?

[• dberlin]

This is a good question.

I looked through, and i see that it is a common idiom, but often there
is a small amount of other code people are doing in the middle or as
part of replacement. For example,
Transforms/ObjCARC/ObjCARCContract.cpp:552

If it's not too much to ask, i actually think the best option may be
something like "a dominated use iterator".

IE

Instead of replaceAllDominatedUses(From, To, DomRoot)

for (auto &Use : dominated_edge_uses(From, DomRoot))

{
    // Do whatever extra stuff they  they want
   Use.set(To);
 }

and
instead of
replaceAllDominatedUses(From, To, From->getParent())

for (auto &Use: dominated_uses(From))

Use.set(To);

If that's too much, let's just put replaceAllDominatedUses in local.* for now.

[reames]

I'll throw it in Local.h/cpp for the moment, but I may go back and write
the dominated use iterator. Doing that as a filter on an iterator range
shouldn't be too challenging. I definitely want to do that refactor as
it's own change set though.

I'll update the patch with the commonned functionality in a moment. What
are you thoughts otherwise?

[reames]

Commoning functionality that now occurs in both GVN and EarlyCSE

[• dberlin]

include/llvm/Transforms/Utils/Local.h

290 ↗

(On Diff #25750)

\brief?

lib/Transforms/Scalar/EarlyCSE.cpp

471

Even GVN does not handle switch with case value, even when it can determine the case value as a constant. It is not as simple as one would thing because it's not about dominance, but control dependence.

(and DT->dominates will fail the single edge assertion in those cases, even though it's a reasonable thing to test)

487

I'm not sure i agree with either of these TODO's.
It's really 100% unclear to me how far this rabbithole we should go for EarlyCSE
I would just leave them (and the above one) out for now, and we can evaluate it when someone has data these are worthwhile to chase.

test/Transforms/EarlyCSE/conditional.ll

2

Can you add descriptions of what each test is testing?
I can kind of figure it out, but not entirely.

Can you also add a few fallthrough edge tests similar to edge.ll from transforms/GVN to make sure it does the right thing?

In fact, i would just copy that and shove the right answers in for earlycse's current impl.

That will make sure nobody accidentally breaks the trickier cases here.

[• dberlin]

Once done, LGTM

[• dberlin]

Comment at: lib/Transforms/Scalar/EarlyCSE.cpp:471
@@ +470,3 @@
+ if (BasicBlock *Pred = BB->getSinglePredecessor())
+ // TODO: handle switch with case value as well

+ if (auto *BI = dyn_cast<BranchInst>(Pred->getTerminator()))

Even GVN does not handle switch with case value, even when it can determine the case value as a constant. It is not as simple as one would thing because it's not about dominance, but control dependence.

(and DT->dominates will fail the single edge assertion in those cases, even though it's a reasonable thing to test)

Just to explain this:

getSinglePredecessor returns true if all edges lead to the same block.
Thus, a switch with multiple edges to the same block will return a
block to getSinglePredecessor.

Dominates(Edge, anything) asserts isSingleEdge(Edge).
isSingleEdge asserts that the edge is singular in the sense that
"multiple edges do not exist from block EdgeStart to block EdgeEnd".
Thus, getSinglePredecessor will happily give you blocks from switch
statements that fail this test (any switch with case statements
leading to the same block), such that you can't test dominance on
them.

GVN goes to the trouble of tracking how many edges lead to a target
block, and only propagates equalities if a single edge reaches a given
target block to avoid this assert.

This is true *even if* it could prove that only one of the edges to
the target block is reachable (because it would still hit the
isSingleEdge assert).

At some point, that assert should simply be removed (or such was the
conclusion of the folks who added it when i asked them, since the
justification given for it makes no sense), but it does mean that
"handling switch with case value" is not a trivial TODO :)

(note, of course, that splitting all critical edges also solves this
particular problem)

lib/Transforms/Scalar/EarlyCSE.cpp

bool EarlyCSE::processNode(DomTreeNode *Node) {
   // of the domtree node and all of the live out memory values are still current
   // in this block.  If this block has multiple predecessors, then they could
   // have invalidated the live-out memory values of our parent value.  For now,
   // just be conservative and invalidate memory if this block has multiple
   // predecessors.
   if (!BB->getSinglePredecessor())
     ++CurrentGeneration;
 
+  // If this node has a single predecessor which ends in a conditional branch,
+  // we can infer the value of the branch condition given that we took this
+  // path.  We need the single predeccesor to ensure there's not another path
+  // which reaches this block where the condition might hold a different
+  // value.  Since we're adding this to the scoped hash table (like any other
+  // def), it will have been popped if we encounter a future merge block.
+  if (BasicBlock *Pred = BB->getSinglePredecessor())
+    // TODO: handle switch with case value as well
+    if (auto *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
+      if (BI->isConditional())
+        if (auto *CondInst = dyn_cast<Instruction>(BI->getCondition()))
+          if (SimpleValue::canHandle(CondInst)) {
+            assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
+            auto *ConditionalConstant = (BI->getSuccessor(0) == BB) ?
+              ConstantInt::getTrue(BB->getContext()) :
+              ConstantInt::getFalse(BB->getContext());
+            AvailableValues.insert(CondInst, ConditionalConstant);
+            DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
+                  << CondInst->getName() << "' as " << *ConditionalConstant
+                  << " in " << BB->getName() << "\n");
+            // Replace all dominated uses with the known value
+            SmallVector<Instruction*, 16> ToUpdate;
+            for (User *U : CondInst->users())
+              if (auto *IU = dyn_cast<Instruction>(U))
+                if (DT.dominates(BB, IU->getParent()))
+                  ToUpdate.push_back(IU);
+            for (Instruction *UserI : ToUpdate) {
+              DEBUG(dbgs() << "EarlyCSE CVP: Replace dominated use of '"
+                    << CondInst->getName() << "' as "
+                    << *ConditionalConstant << " in " << *UserI << "\n");
+              UserI->replaceUsesOfWith(CondInst, ConditionalConstant);
+            }
+            // TODO: Exploit icmp eq %v, C to get value for C
+            // TODO: Look through and/or sequences to get more known conditions
+          }
+
   /// LastStore - Keep track of the last non-volatile store that we saw... for
   /// as long as there in no instruction that reads memory.  If we see a store
   /// to the same location, we delete the dead store.  This zaps trivial dead
   /// stores which can occur in bitfield code among other things.
   Instruction *LastStore = nullptr;
 
   bool Changed = false;
   const DataLayout &DL = BB->getModule()->getDataLayout();

test/Transforms/EarlyCSE/conditional.ll

+; RUN: opt -early-cse -S < %s | FileCheck %s
+
+define i1 @test(i8* %p) {
+; CHECK-LABEL: @test
+entry:
+  %cnd1 = icmp eq i8* %p, null
+  br i1 %cnd1, label %taken, label %untaken
+
+taken:
+; CHECK-LABEL: taken:
+; CHECK-NEXT: ret i1 true
+  %cnd2 = icmp eq i8* %p, null
+  ret i1 %cnd2
+
+untaken:
+; CHECK-LABEL: untaken:
+; CHECK-NEXT: ret i1 false
+  %cnd3 = icmp eq i8* %p, null
+  ret i1 %cnd3
+}
+
+define i1 @test_neg1(i8* %p) {
+; CHECK-LABEL: @test_neg1
+entry:
+  %cnd1 = icmp eq i8* %p, null
+  br i1 %cnd1, label %taken, label %untaken
+
+taken:
+  br label %merge
+
+untaken:
+  br label %merge
+
+merge:
+; CHECK-LABEL: merge:
+; CHECK-NEXT: ret i1 %cnd1
+  %cnd3 = icmp eq i8* %p, null
+  ret i1 %cnd3
+}
+
+define i1 @test_neg2(i8* %p) {
+; CHECK-LABEL: @test_neg2
+entry:
+  %cnd1 = icmp eq i8* %p, null
+  br i1 %cnd1, label %merge, label %merge
+
+merge:
+; CHECK-LABEL: merge:
+; CHECK-NEXT: ret i1 %cnd1
+  %cnd3 = icmp eq i8* %p, null
+  ret i1 %cnd3
+}
+
+; Replace a use rather than CSE
+define i1 @test2(i8* %p) {
+; CHECK-LABEL: @test2
+entry:
+  %cnd = icmp eq i8* %p, null
+  br i1 %cnd, label %taken, label %untaken
+
+taken:
+; CHECK-LABEL: taken:
+; CHECK-NEXT: ret i1 true
+  ret i1 %cnd
+
+untaken:
+; CHECK-LABEL: untaken:
+; CHECK-NEXT: ret i1 false
+  ret i1 %cnd
+}
+
+define i1 @test2_neg1(i8* %p) {
+; CHECK-LABEL: @test2_neg1
+entry:
+  %cnd1 = icmp eq i8* %p, null
+  br i1 %cnd1, label %taken, label %untaken
+
+taken:
+  br label %merge
+
+untaken:
+  br label %merge
+
+merge:
+; CHECK-LABEL: merge:
+; CHECK-NEXT: ret i1 %cnd1
+  ret i1 %cnd1
+}
+
+define i1 @test2_neg2(i8* %p) {
+; CHECK-LABEL: @test2_neg2
+entry:
+  %cnd1 = icmp eq i8* %p, null
+  br i1 %cnd1, label %merge, label %merge
+
+merge:
+; CHECK-LABEL: merge:
+; CHECK-NEXT: ret i1 %cnd1
+  ret i1 %cnd1
+}
+