[gvn] Precisely propagate equalities to phi operands

[reames]

Summary

The code used for propagating equalities (e.g. assume facts) was conservative in two ways - one of which this patch fixes. Specifically, it shifts the code reasoning about whether a use is dominated by the end of the assume block to consider phi uses to exist on the predecessor edge. This matches the dominator tree handling for dominates(X, Use), and simply extends it to properlyDominates.

Note that the decision to use the end of the block is itself a conservative choice. The more precise option would be to use the later of the assume and the value, and replace all uses after that. GVN handles that case separately (with the replace operand mechanism) because it used to be expensive to ask dominator questions within blocks. With the new instruction ordering support, we should probably rewrite this code at some point to simplify.

[reames]

Rebase over landed tests.

[jdoerfert]

I don't understand how second commit message paragraph in this context but the logic seems fine. Second pair of eyes won't hurt though.

[nikic]

llvm/lib/Transforms/Utils/Local.cpp

2709

I'd suggest to write it like this:

Instruction *UserInst = cast<Instruction>(U.getUser());
if (auto *PN = dyn_cast<PHINode>(UserInst))
  return DT.dominates(BB, PN->getIncomingBlock());
else
  return DT.properlyDominates(BB, UserInst->getParent());

Though ideally this should be an API on DominatorTree. We currently have dominates(BasicBlockEdge, Use), but we're missing the dominates(BasicBlock, Use) variant.

[reames]

address review comments + rebase over landed change which causes a further test diff

[nikic]

LGTM

llvm/lib/Transforms/Utils/Local.cpp

unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
   };
   return ::replaceDominatedUsesWith(From, To, Root, Dominates);
 }
 
 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                         DominatorTree &DT,
                                         const BasicBlock *BB) {
   auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
-    auto *I = cast<Instruction>(U.getUser())->getParent();
-    return DT.properlyDominates(BB, I);
+    Instruction *UserInst = cast<Instruction>(U.getUser());
+    PHINode *PN = dyn_cast<PHINode>(UserInst);
+    // A phi use using a value from a block is dominated by the end of that
+    // block.  Note that the phi's parent block may not be.
+    if (PN && PN->getIncomingBlock(U) == BB)
+      return true;
+
+    const BasicBlock *UseBB;
+    if (PN)
+      UseBB = PN->getIncomingBlock(U);
+    else
+      UseBB = UserInst->getParent();
+    return DT.properlyDominates(BB, UseBB);
   };
   return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
 }
 
 bool llvm::callsGCLeafFunction(const CallBase *Call,
                                const TargetLibraryInfo &TLI) {
   // Check if the function is specifically marked as a gc leaf function.
   if (Call->hasFnAttr("gc-leaf-function"))

llvm/test/Transforms/GVN/phi.ll

 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
 ; CHECK-NEXT:    [[ASSUMPTION:%.*]] = icmp eq i64 [[A:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUMPTION]])
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       untaken:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI1:%.*]] = phi i64 [ [[A]], [[TAKEN]] ], [ [[B:%.*]], [[UNTAKEN]] ]
+; CHECK-NEXT:    [[PHI1:%.*]] = phi i64 [ 0, [[TAKEN]] ], [ [[B:%.*]], [[UNTAKEN]] ]
 ; CHECK-NEXT:    [[PHI2:%.*]] = phi i64 [ 0, [[TAKEN]] ], [ [[B]], [[UNTAKEN]] ]
 ; CHECK-NEXT:    [[RET:%.*]] = sub i64 [[PHI1]], [[PHI2]]
 ; CHECK-NEXT:    ret i64 [[RET]]
 ;
   br i1 %c, label %taken, label %untaken
 taken:
   %assumption = icmp eq i64 %a, 0
   call void @llvm.assume(i1 %assumption)

 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
 ; CHECK-NEXT:    [[ASSUMPTION:%.*]] = icmp eq i64 [[A:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUMPTION]])
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       untaken:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[A]], [[TAKEN]] ], [ 0, [[UNTAKEN]] ]
-; CHECK-NEXT:    ret i64 [[PHI]]
+; CHECK-NEXT:    ret i64 0
 ;
   br i1 %c, label %taken, label %untaken
 taken:
   %assumption = icmp eq i64 %a, 0
   call void @llvm.assume(i1 %assumption)
   br label %merge
 untaken:
   br label %merge
 merge:
   %phi = phi i64 [%a, %taken], [0, %untaken]
   ret i64 %phi
 }
 
 define i64 @test6(i1 %c, i64 %a) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
 ; CHECK-NEXT:    [[ASSUMPTION:%.*]] = icmp eq i64 [[A:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUMPTION]])
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       untaken:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[A]], [[TAKEN]] ], [ 0, [[UNTAKEN]] ]
-; CHECK-NEXT:    ret i64 [[PHI]]
+; CHECK-NEXT:    ret i64 0
 ;
   br i1 %c, label %taken, label %untaken
 taken:
   %assumption = icmp eq i64 %a, 0
   call void @llvm.assume(i1 %assumption)
   br label %next
 next:
   br label %merge