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 ↗

(On Diff #25737)

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 ↗

(On Diff #25737)

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 ↗

(On Diff #25750)

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 ↗

(On Diff #25750)

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

1 ↗

(On Diff #25750)

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)

llvm/trunk/include/llvm/Transforms/Utils/Local.h

 // program.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H
 #define LLVM_TRANSFORMS_UTILS_LOCAL_H
 
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Operator.h"
 
 namespace llvm {
 
 class User;
 class BasicBlock;

 /// Returns true if any basic block was removed.
 bool removeUnreachableBlocks(Function &F);
 
 /// \brief Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
+/// \brief Replace each use of 'From' with 'To' if that use is dominated by 
+/// the given edge.  Returns the number of replacements made.
+unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
+                                  const BasicBlockEdge &Edge);
 } // End llvm namespace
 
 #endif

llvm/trunk/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())
+    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
+            replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
+                                     BasicBlockEdge(Pred, BB));
+          }
+
   /// 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();

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

private:
     bool performScalarPRE(Instruction *I);
     bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
                                    unsigned int ValNo);
     Value *findLeader(const BasicBlock *BB, uint32_t num);
     void cleanupGlobalSets();
     void verifyRemoved(const Instruction *I) const;
     bool splitCriticalEdges();
     BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
-    unsigned replaceAllDominatedUsesWith(Value *From, Value *To,
-                                         const BasicBlockEdge &Root);
     bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root);
     bool processFoldableCondBr(BranchInst *BI);
     void addDeadBlock(BasicBlock *BB);
     void assignValNumForDeadCode();
   };
 
   char GVN::ID = 0;
 }
while (Next) {
     }
 
     Next = Next->Next;
   }
 
   return Val;
 }
 
-/// Replace all uses of 'From' with 'To' if the use is dominated by the given
-/// basic block.  Returns the number of uses that were replaced.
-unsigned GVN::replaceAllDominatedUsesWith(Value *From, Value *To,
-                                          const BasicBlockEdge &Root) {
-  unsigned Count = 0;
-  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
-       UI != UE; ) {
-    Use &U = *UI++;
-
-    if (DT->dominates(Root, U)) {
-      U.set(To);
-      ++Count;
-    }
-  }
-  return Count;
-}
-
 /// There is an edge from 'Src' to 'Dst'.  Return
 /// true if every path from the entry block to 'Dst' passes via this edge.  In
 /// particular 'Dst' must not be reachable via another edge from 'Src'.
 static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
                                        DominatorTree *DT) {
   // While in theory it is interesting to consider the case in which Dst has
   // more than one predecessor, because Dst might be part of a loop which is
   // only reachable from Src, in practice it is pointless since at the time
while (!Worklist.empty()) {
     // have the simple case where the edge dominates the end.
     if (RootDominatesEnd && !isa<Instruction>(RHS))
       addToLeaderTable(LVN, RHS, Root.getEnd());
 
     // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope.  As
     // LHS always has at least one use that is not dominated by Root, this will
     // never do anything if LHS has only one use.
     if (!LHS->hasOneUse()) {
-      unsigned NumReplacements = replaceAllDominatedUsesWith(LHS, RHS, Root);
+      unsigned NumReplacements = replaceDominatedUsesWith(LHS, RHS, *DT, Root);
       Changed |= NumReplacements > 0;
       NumGVNEqProp += NumReplacements;
     }
 
     // Now try to deduce additional equalities from this one. For example, if
     // the known equality was "(A != B)" == "false" then it follows that A and B
     // are equal in the scope. Only boolean equalities with an explicit true or
     // false RHS are currently supported.
if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
       uint32_t NextNum = VN.getNextUnusedValueNumber();
       uint32_t Num = VN.lookup_or_add_cmp(Cmp->getOpcode(), NotPred, Op0, Op1);
       // If the number we were assigned was brand new then there is no point in
       // looking for an instruction realizing it: there cannot be one!
       if (Num < NextNum) {
         Value *NotCmp = findLeader(Root.getEnd(), Num);
         if (NotCmp && isa<Instruction>(NotCmp)) {
           unsigned NumReplacements =
-            replaceAllDominatedUsesWith(NotCmp, NotVal, Root);
+            replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root);
           Changed |= NumReplacements > 0;
           NumGVNEqProp += NumReplacements;
         }
       }
       // Ensure that any instruction in scope that gets the "A < B" value number
       // is replaced with false.
       // The leader table only tracks basic blocks, not edges. Only add to if we
       // have the simple case where the edge dominates the end.

llvm/trunk/lib/Transforms/Utils/Local.cpp

switch (Kind) {
         break;
       case LLVMContext::MD_nonnull:
         // Only set the !nonnull if it is present in both instructions.
         K->setMetadata(Kind, JMD);
         break;
     }
   }
 }
+
+unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
+                                        DominatorTree &DT,
+                                        const BasicBlockEdge &Root) {
+  assert(From->getType() == To->getType());
+  
+  unsigned Count = 0;
+  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
+       UI != UE; ) {
+    Use &U = *UI++;
+    if (DT.dominates(Root, U)) {
+      U.set(To);
+      DEBUG(dbgs() << "Replace dominated use of '"
+            << From->getName() << "' as "
+            << *To << " in " << *U << "\n");
+      ++Count;
+    }
+  }
+  return Count;
+}

llvm/trunk/test/Transforms/EarlyCSE/conditional.ll

+; RUN: opt -early-cse -S < %s | FileCheck %s
+
+; Can we CSE a known condition to a constant?
+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
+}
+
+; We can CSE the condition, but we *don't* know it's value after the merge
+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
+}
+
+; Check specifically for a case where we have a unique predecessor, but
+; not a single predecessor.  We can not know the value of the condition here.
+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
+}
+
+; Not legal to replace use given it's not dominated by edge
+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
+}
+
+; Another single predecessor test, but for dominated use
+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
+}
+

llvm/trunk/test/Transforms/EarlyCSE/edge.ll

+; RUN: opt -early-cse -S < %s | FileCheck %s
+; Same as GVN/edge.ll, but updated to reflect EarlyCSE's less powerful
+; implementation.  EarlyCSE doesn't yet handle uses on edges where the
+; source is dominated, but the dest is not.  Nor does it reason about 
+; fcmps. This file can basically be seen as a list of TODOs.
+
+define i32 @f1(i32 %x) {
+  ; CHECK-LABEL: define i32 @f1(
+bb0:
+  %cmp = icmp eq i32 %x, 0
+  br i1 %cmp, label %bb2, label %bb1
+bb1:
+  br label %bb2
+bb2:
+  %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ]
+  %foo = add i32 %cond, %x
+  ret i32 %foo
+  ; CHECK: bb2:
+  ; CHECK: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ]
+}
+
+define i32 @f2(i32 %x) {
+  ; CHECK-LABEL: define i32 @f2(
+bb0:
+  %cmp = icmp ne i32 %x, 0
+  br i1 %cmp, label %bb1, label %bb2
+bb1:
+  br label %bb2
+bb2:
+  %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ]
+  %foo = add i32 %cond, %x
+  ret i32 %foo
+  ; CHECK: bb2:
+  ; CHECK: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ]
+}
+
+define i32 @f3(i32 %x) {
+  ; CHECK-LABEL: define i32 @f3(
+bb0:
+  switch i32 %x, label %bb1 [ i32 0, label %bb2]
+bb1:
+  br label %bb2
+bb2:
+  %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ]
+  %foo = add i32 %cond, %x
+  ret i32 %foo
+  ; CHECK: bb2:
+  ; CHECK: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ]
+}
+
+declare void @g(i1)
+define void @f4(i8 * %x)  {
+; CHECK-LABEL: define void @f4(
+bb0:
+  %y = icmp eq i8* null, %x
+  br i1 %y, label %bb2, label %bb1
+bb1:
+  br label %bb2
+bb2:
+  %zed = icmp eq i8* null, %x
+  call void @g(i1 %zed)
+; CHECK: call void @g(i1 %y)
+  ret void
+}
+
+define double @fcmp_oeq_not_zero(double %x, double %y) {
+entry:
+  %cmp = fcmp oeq double %y, 2.0
+  br i1 %cmp, label %if, label %return
+
+if:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %if ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_oeq_not_zero(
+; CHECK: %div = fdiv double %x, %y
+}
+
+define double @fcmp_une_not_zero(double %x, double %y) {
+entry:
+  %cmp = fcmp une double %y, 2.0
+  br i1 %cmp, label %return, label %else
+
+else:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %else ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_une_not_zero(
+; CHECK: %div = fdiv double %x, %y
+}
+
+; PR22376 - We can't propagate zero constants because -0.0 
+; compares equal to 0.0. If %y is -0.0 in this test case,
+; we would produce the wrong sign on the infinity return value.
+define double @fcmp_oeq_zero(double %x, double %y) {
+entry:
+  %cmp = fcmp oeq double %y, 0.0
+  br i1 %cmp, label %if, label %return
+
+if:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %if ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_oeq_zero(
+; CHECK: %div = fdiv double %x, %y
+}
+
+define double @fcmp_une_zero(double %x, double %y) {
+entry:
+  %cmp = fcmp une double %y, -0.0
+  br i1 %cmp, label %return, label %else
+
+else:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %else ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_une_zero(
+; CHECK: %div = fdiv double %x, %y
+}
+
+; We also cannot propagate a value if it's not a constant.
+; This is because the value could be 0.0 or -0.0.
+
+define double @fcmp_oeq_maybe_zero(double %x, double %y, double %z1, double %z2) {
+entry:
+ %z = fadd double %z1, %z2
+ %cmp = fcmp oeq double %y, %z
+ br i1 %cmp, label %if, label %return
+
+if:
+ %div = fdiv double %x, %z
+ br label %return
+
+return:
+ %retval = phi double [ %div, %if ], [ %x, %entry ]
+ ret double %retval
+
+; CHECK-LABEL: define double @fcmp_oeq_maybe_zero(
+; CHECK: %div = fdiv double %x, %z
+}
+
+define double @fcmp_une_maybe_zero(double %x, double %y, double %z1, double %z2) {
+entry:
+ %z = fadd double %z1, %z2
+ %cmp = fcmp une double %y, %z
+ br i1 %cmp, label %return, label %else
+
+else:
+ %div = fdiv double %x, %z
+ br label %return
+
+return:
+ %retval = phi double [ %div, %else ], [ %x, %entry ]
+ ret double %retval
+
+; CHECK-LABEL: define double @fcmp_une_maybe_zero(
+; CHECK: %div = fdiv double %x, %z
+}