Fix for two constant propagation problems in GVN with assume intrinsic instruction

[Ray]

Summary

This patch fixes two constant propagation problems in GVN for assume intrinsic instruction. The first problem is filed in PR25285: when there are multiple instances of the same assume instructions in a basic block with a loop back-edge pointing to itself, the first assume instruction is incorrectly constant-propagated with the value "TRUE" and eliminated later on. The second problem is that, the value "TRUE" is incorrectly constant-propagated to the successor blocks that are not dominated by the basic block containing the assume instruction.

[Prazek]

Something is wrong with the review, because I can't look at code that wasn't modified.
I think the diff was not generated with -U99999.

[Ray]

This is the new diff generated with --diff-cmd=diff -x -U999999

[• dberlin]

include/llvm/Transforms/Utils/Local.h

320

I'm not sure this wording change makes sense.

It doesn't care whether it's the end of the block that dominates or not.
And by definition, uses in the same-block as their definitions must be dominated by those defs.

lib/Transforms/Scalar/GVN.cpp

2137

If there are multiple edges to the same BB, we should not do the replacement at all (we lack post-dominance info necessary to be safe in that case).

2201

If this problem only occurs with assume instructions, we shouldn't change the generic code.
If it's not a problem that only occur with assume instructions, we need
A. more testcases.
B. a more complete description of the problem that is happening and why this is the correct fix.

2277

Same comment as above :)

lib/Transforms/Utils/Local.cpp

1540

This is definitely not correct.
Local to a block, all uses are dominated by their definition, so you don't need properlyDominates to replace them legally.
It's up to the caller to determine whether this is safe *semantically*.

(Even if this change was correct, you've also now made the replacement functions completely inconsistent with each other.)

[• dberlin]

Also note, it's possible to have a case where root.start dominates but it
is not safe to propagate due to multiple edges from that block to to
root.getEnd.
The whole reason for having the edge is to avoid this case, AFAIK.

So i'm pretty sure using root.getStart() is just going to cause incorrect
transforms.

Note that all of propagateEquality is really somewhat of a hack to avoid
using proper control dependence, and at some point, we'll likely want to
just rip it out and use post-dominators to do this *right*.

I don't know whether the optimization capability we lose here by avoiding
assume in some cases makes us want to do that more (I leave that question
to data and chandler)

[Prazek]

I don't have much time right now to do it because of exams, but if it won't
get accept until friday, I will take a look.

[Ray]

lib/Transforms/Scalar/GVN.cpp

2137

Note that, there is a condition about "multiple edges to the same BB": it is from Root.Start to Root.End. That's when DominatesByEdge is set to false, and that's exactly the reason why DominatesByEdge was introduced as a parameter to this function. See the example added before

@_Z1ii in test/Transforms/GVN/assume-equal.ll

; This test checks if constant propagation works for multiple node edges
; CHECK-LABEL: define i32 @_Z1ii(i32 %p)
define i32 @_Z1ii(i32 %p) {
entry:

%cmp = icmp eq i32 %p, 42
call void @llvm.assume(i1 %cmp)

; CHECK: br i1 true, label %bb2, label %bb2
br i1 %cmp, label %bb2, label %bb2

bb2:

; CHECK: br i1 true, label %bb2, label %bb2
br i1 %cmp, label %bb2, label %bb2

; CHECK: ret i32 42
ret i32 %p

}

I was trying to make the comments in more detail. But if it is confusing, we can improve it.

2201

This is a general problem in GVN::propagateEquality with the following code:

unsigned NumReplacements =

DominatesByEdge
    ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
    : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());

When DominatesByEdge is TRUE, it passes the edge "Root" to replaceDominatedUsesWith, and we are fine. Since, if the edge "Root" dominates a USE, then Root.Start must dominates the USE.

When DominatesByEdge is FALSE, it passes the Root.End to replaceDominatedUsesWith, and we have a problem here. Since, if Root.End dominates a USE, it does not mean that Root.Start dominates the USE. We show in the test case _Z1im below.

In this case, we ideally need "RootDominatesEnd" (in GVN::propagateEquality) to further test before calling replaceDominatedWith(...Root.End), e.g.:

unsigned NumReplacements =

DominatesByEdge
    ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
    : 
RootDominatesEnd? replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd()) : 0;

However, when we cannot use the current RootDominatesEnd defined as below to test:

// For speed, compute a conservative fast approximation to
// DT->dominates(Root, Root.getEnd());
bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);

The reason is that, it only works when DominatesByEdge=TRUE, not when DominatesByEdge =FALSE where there are multiple edges (e.g., 2 edges) from Root.Start to Root.End, see @_Z1ii in test/Transforms/GVN/assume-equal.ll again.

And, we cannot use the following either,

boot RootDominatesEnd = DT->dominates(Root, Root.getEnd());

since, it ran into the problem Prazek saw before, giving an assert when DominatesByEdge=FALSE. see @_Z1ii in test/Transforms/GVN/assume-equal.ll again

Now, If we modify RootDominatesEnd to

bool RootDominatesEnd = DT.dominates(Root.Start(), Root.End()), then it can be used:

unsigned NumReplacements =

DominatesByEdge
    ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
    : 
RootDominatesEnd? replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd()) : 0;

I didn't post this change, because 1) DT.dominates will slow down as comments show 2) the name RootDominatesEnd is not proper.

In fact, the simplest way is to

1. pass Root.Start to replaceDominatedUsesWith,
2. then change replaceDominatedUsesWith(... BasicBlock* BB) to replace the uses by the "END" of the BB.

These two changes together will give exactly the same effect as when passing an edge, i.e. ,replaceDominatedUsesWith(..... BasicBlockEdge Root).

Note that, currently GVN is the only caller of replaceDominatedUsesWith( ..., BasicBlock* BB). So, it is safe to change to use "properlyDominates".

Although it is a general problem with propagateEquality, I don't have any test cases other than those with assume instructions. The reason is that,

1. The problem only exists when DominatedByEdge = FALSE
2. GVN::processAssumeIntrinsic is the only caller to propagateEquality when DominatedByEdge=FALSE as below:
   
   for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
   
   BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
   
   Changed |= propagateEquality(V, True, Edge, false);
   
   }

lib/Transforms/Utils/Local.cpp

1540

Since propagateEquality in GVN is the only caller, that's why we changed the comments to inform other users that, this function will replace USES from the END of the BB.

If the called wants to replace the uses in the BB itself, the other overloaded interface replaceDomiantedUsesWith(..... BasicBlockEdge Root) can be used.

[Ray]

I actually agree with Daniel's comments, especially about the proposal to rewrite propagateEquality. I would see my fix as a necessary co-implementation with Piotr's earlier patch http://reviews.llvm.org/D12170, since my changes only happen in that particular commit.

Probably we can submit this "necessary" fix as well as the test cases (for "assume") first, and then think of restructure the propagateEquality.

I update this new patch to fix my previously wrong comments pointed out by Daniel. Thanks for that:)

[DavidKreitzer]

I like Ray's plan of first making the targeted stability fix and then deciding how best to restructure propagateEquality to make it clearer. The bug illustrated by the @_Z1im test case is pretty egregious and ought to be fixed promptly IMO.

Daniel, you suggested possibly splitting propagateEquality, but there is a lot of functionality in there that you'd like to share between the assume intrinsic caller and the other callers. For example, the code that infers A == 1 && B == 1 from A && B == 1 applies equally regardless of whether A && B == 1 came from "assume(A && B)" or "if (A && B)".

I think the fundamental difference between assume and the other callers of propagateEquality is that for assume, the equality property becomes known true immediately following the assume instruction while for the other callers, the equality property becomes known true along the outgoing edge of the block ending in the conditional branch or switch. It shouldn't be hard to make that distinction in the interface to propagateEquality. Perhaps something like this:

/// The given values are known to be equal at a certain point, P, in the program.
/// When DominatesByEdge is true, that point is the CFG edge Root.
/// When DominatesByEdge is false, that point is the Instruction Instr.
/// Exploit this, for example by replacing 'LHS' with 'RHS' at all uses dominated by P.
/// Returns whether a change was made.
bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
                            Instruction *Instr, bool DominatesByEdge) {

When DominatesByEdge is true, Instr would be ignored. And when DominatesByEdge is false, Root would be ignored. Then the dominance check for the assume case becomes one of "does this instruction dominate" rather than "does this block dominate". (Note that this lets us get rid of the "for each successor" loop inside processAssumeIntrinsic, which is pretty artificial. I suspect it was written that way just to make it easier to reuse propagateEquality.)

[• dberlin]

To start with, I'm fine with committing this patch if we agree to address
the other issues, *somehow*, in a followup (either by y'all or by Piotr).

[Ray]

Hi Piotr,

Did you get a time to look at the fix I uploaded for the second time? Does it look good to you?

Daniel’s suggestion on restructuring the propagateEquality is good and necessary, since many developers find this function confusing.

Dave and I tried the idea he mentioned below, i.e., the new interface, but it seems that it does not help much to eliminate the code confusion in that function, and not simpler than the current fix.

I am wondering if you have any plan to rewrite this function. Are you familiar with the code? If not, do you know who is familiar with this code, and can assist us in doing the rewriting. We can all help if needed, but we need an expert first.

Thank you very much!

Regards,
Ray
From: Daniel Berlin [mailto:[e-mail]]
Sent: Thursday, January 14, 2016 3:42 PM
To: [e-mail]
Cc: Zhang, Yuanrui <[e-mail]>; Nick Lewycky <[e-mail]>; Piotr Padlewski <[e-mail]>; Kreitzer, David L <[e-mail]>; llvm-commits <[e-mail]>
Subject: Re: [PATCH] D16100: Fix for two constant propagation problems in GVN with assume intrinsic instruction

To start with, I'm fine with committing this patch if we agree to address the other issues, *somehow*, in a followup (either by y'all or by Piotr).

[Prazek]

LGTM

include/llvm/Transforms/Utils/Local.h

 /// 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);
 /// \brief Replace each use of 'From' with 'To' if that use is dominated by
-/// the given BasicBlock. Returns the number of replacements made.
+/// the end of the given BasicBlock. Returns the number of replacements made.
 unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
                                   const BasicBlock *BB);
 
 
 /// \brief Return true if the CallSite CS calls a gc leaf function.
 ///
 /// A leaf function is a function that does not safepoint the thread during its
 /// execution.  During a call or invoke to such a function, the callers stack
 /// does not have to be made parseable.
 ///
 /// Most passes can and should ignore this information, and it is only used
 /// during lowering by the GC infrastructure.
 bool callsGCLeafFunction(ImmutableCallSite CS);
 
 } // End llvm namespace
 
 #endif

lib/Transforms/Scalar/GVN.cpp

for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
     }
   }
   return Changed;
 }
 
 /// The given values are known to be equal in every block
 /// dominated by 'Root'.  Exploit this, for example by replacing 'LHS' with
 /// 'RHS' everywhere in the scope.  Returns whether a change was made.
-/// If DominatesByEdge is false, then it means that it is dominated by Root.End.
+/// If DominatesByEdge is false, it means that there might be multiple edges
+/// from Root.Start to Root.End, in which case we need to pass Root.Start and
+/// use a different implementation of replaceDominatedUsesWith to test.
+//
 bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
                             bool DominatesByEdge) {
   SmallVector<std::pair<Value*, Value*>, 4> Worklist;
   Worklist.push_back(std::make_pair(LHS, RHS));
   bool Changed = false;
   // For speed, compute a conservative fast approximation to
   // DT->dominates(Root, Root.getEnd());
   bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
while (!Worklist.empty()) {
 
     // 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 =
           DominatesByEdge
               ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
-              : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd());
+              : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
 
       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
if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
       // 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 =
               DominatesByEdge
                   ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
                   : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
-                                             Root.getEnd());
+                                             Root.getStart());
           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.

lib/Transforms/Utils/Local.cpp

unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                         const BasicBlock *BB) {
   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++;
     auto *I = cast<Instruction>(U.getUser());
-    if (DT.dominates(BB, I->getParent())) {
+    if (DT.properlyDominates(BB, I->getParent())) {
       U.set(To);
       DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
                    << *To << " in " << *U << "\n");
       ++Count;
     }
   }
   return Count;
 }

test/Transforms/GVN/assume-equal.ll

bb2:
   %cmp3 = icmp eq i32 %p, 43
   ; CHECK: store i8 undef, i8* null
   call void @llvm.assume(i1 %cmp3)
   ret i32 15
 bb3:
   ret i32 17
 }
 
+; This test checks if GVN can do the constant propagation correctly
+; when there are multiple uses of the same assume value in the 
+; basic block that has a loop back-edge pointing to itself.
+;
+; CHECK-LABEL: define i32 @_Z1il(i32 %val, i1 %k)
+define i32 @_Z1il(i32 %val, i1 %k) {
+  br label %next
+
+next:
+; CHECK: tail call void @llvm.assume(i1 %k)
+; CHECK-NEXT: %cmp = icmp eq i32 %val, 50
+  tail call void @llvm.assume(i1 %k)
+  tail call void @llvm.assume(i1 %k)
+  %cmp = icmp eq i32 %val, 50
+  br i1 %cmp, label %next, label %meh
+
+meh:
+  ret i32 0 
+}
+
+; This test checks if GVN can prevent the constant propagation correctly
+; in the successor blocks that are not dominated by the basic block
+; with the assume instruction.
+;
+; CHECK-LABEL: define i1 @_z1im(i32 %val, i1 %k, i1 %j)
+define i1 @_z1im(i32 %val, i1 %k, i1 %j) {
+  br i1 %j, label %next, label %meh
+
+next:
+; CHECK: tail call void @llvm.assume(i1 %k)
+; CHECK-NEXT: br label %meh
+  tail call void @llvm.assume(i1 %k)
+  tail call void @llvm.assume(i1 %k)
+  br label %meh
+
+meh:
+; CHECK: ret i1 %k
+  ret i1 %k
+}
+
 declare noalias i8* @_Znwm(i64)
 declare void @_ZN1AC1Ev(%struct.A*)
 declare void @llvm.assume(i1)
 declare i32 @_ZN1A3fooEv(%struct.A*)
 declare i32 @_ZN1A3barEv(%struct.A*)
 
 !0 = !{!"struct A"}