Constant propagation after hiting llvm.assume

After hitting @llvm.assume(X) we can:
- propagate equality that X == true
- if X is icmp/fcmp (with eq operation), and one of operand
  is constant we can change all variables with constants in the same BasicBlock

http://reviews.llvm.org/D11918

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@245265 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index f256af81fc86e2647338702948f022df6c8e0830..075fea8921253293d26c4aba454851d8326b2d89 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -608,6 +608,10 @@ namespace {
     DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
     BumpPtrAllocator TableAllocator;
 
+    // Block-local map of equivalent values to their leader, does not
+    // propagate to any successors. Entries added mid-block are applied
+    // to the remaining instructions in the block.
+    SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
     SmallVector<Instruction*, 8> InstrsToErase;
 
     typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
@@ -699,6 +703,7 @@ namespace {
     // Helper functions of redundant load elimination 
     bool processLoad(LoadInst *L);
     bool processNonLocalLoad(LoadInst *L);
+    bool processAssumeIntrinsic(IntrinsicInst *II);
     void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, 
                                  AvailValInBlkVect &ValuesPerBlock,
                                  UnavailBlkVect &UnavailableBlocks);
@@ -719,6 +724,7 @@ namespace {
     void verifyRemoved(const Instruction *I) const;
     bool splitCriticalEdges();
     BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
+    bool replaceOperandsWithConsts(Instruction *I) const;
     bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root);
     bool processFoldableCondBr(BranchInst *BI);
     void addDeadBlock(BasicBlock *BB);
@@ -1759,6 +1765,38 @@ bool GVN::processNonLocalLoad(LoadInst *LI) {
   return PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks);
 }
 
+bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) {
+  assert(IntrinsicI->getIntrinsicID() == Intrinsic::assume &&
+         "This function can only be called with llvm.assume intrinsic");
+  Value *V = IntrinsicI->getArgOperand(0);
+  Constant *True = ConstantInt::getTrue(V->getContext());
+  bool Changed = false;
+  for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
+    BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
+
+    // This property is only true in dominated successors, propagateEquality
+    // will check dominance for us.
+    Changed |= propagateEquality(V, True, Edge);
+  }
+
+  if (auto *CmpI = dyn_cast<CmpInst>(V)) {
+    if (CmpI->getPredicate() == CmpInst::Predicate::ICMP_EQ ||
+        CmpI->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
+        (CmpI->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
+         CmpI->getFastMathFlags().noNaNs())) {
+      Value *CmpLHS = CmpI->getOperand(0);
+      Value *CmpRHS = CmpI->getOperand(1);
+      if (isa<Constant>(CmpLHS))
+        std::swap(CmpLHS, CmpRHS);
+      auto *RHSConst = dyn_cast<Constant>(CmpRHS);
+
+      // If only one operand is constant.
+      if (RHSConst != nullptr && !isa<Constant>(CmpLHS))
+        ReplaceWithConstMap[CmpLHS] = RHSConst;
+    }
+  }
+  return Changed;
+}
 
 static void patchReplacementInstruction(Instruction *I, Value *Repl) {
   // Patch the replacement so that it is not more restrictive than the value
@@ -2031,6 +2069,21 @@ static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
   return Pred != nullptr;
 }
 
+// Tries to replace instruction with const, using information from
+// ReplaceWithConstMap.
+bool GVN::replaceOperandsWithConsts(Instruction *Instr) const {
+  bool Changed = false;
+  for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
+    Value *Operand = Instr->getOperand(OpNum);
+    auto it = ReplaceWithConstMap.find(Operand);
+    if (it != ReplaceWithConstMap.end()) {
+      Instr->setOperand(OpNum, it->second);
+      Changed = true;
+    }
+  }
+  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.
@@ -2047,11 +2100,13 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS,
     std::pair<Value*, Value*> Item = Worklist.pop_back_val();
     LHS = Item.first; RHS = Item.second;
 
-    if (LHS == RHS) continue;
+    if (LHS == RHS)
+      continue;
     assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
 
     // Don't try to propagate equalities between constants.
-    if (isa<Constant>(LHS) && isa<Constant>(RHS)) continue;
+    if (isa<Constant>(LHS) && isa<Constant>(RHS))
+      continue;
 
     // Prefer a constant on the right-hand side, or an Argument if no constants.
     if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
@@ -2202,6 +2257,10 @@ bool GVN::processInstruction(Instruction *I) {
     return true;
   }
 
+  if (IntrinsicInst *IntrinsicI = dyn_cast<IntrinsicInst>(I))
+    if (IntrinsicI->getIntrinsicID() == Intrinsic::assume)
+      return processAssumeIntrinsic(IntrinsicI);
+
   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
     if (processLoad(LI))
       return true;
@@ -2266,7 +2325,8 @@ bool GVN::processInstruction(Instruction *I) {
 
   // Instructions with void type don't return a value, so there's
   // no point in trying to find redundancies in them.
-  if (I->getType()->isVoidTy()) return false;
+  if (I->getType()->isVoidTy())
+    return false;
 
   uint32_t NextNum = VN.getNextUnusedValueNumber();
   unsigned Num = VN.lookup_or_add(I);
@@ -2373,10 +2433,15 @@ bool GVN::processBlock(BasicBlock *BB) {
   if (DeadBlocks.count(BB))
     return false;
 
+  // Clearing map before every BB because it can be used only for single BB.
+  ReplaceWithConstMap.clear();
   bool ChangedFunction = false;
 
   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
        BI != BE;) {
+    if (!ReplaceWithConstMap.empty())
+      ChangedFunction |= replaceOperandsWithConsts(BI);
+
     ChangedFunction |= processInstruction(BI);
     if (InstrsToErase.empty()) {
       ++BI;

diff --git a/test/Transforms/GVN/assume-equal.ll b/test/Transforms/GVN/assume-equal.ll
new file mode 100644 (file)
index 0000000..c1665bd
--- /dev/null
+++ b/test/Transforms/GVN/assume-equal.ll
@@ -0,0 +1,122 @@
+; RUN: opt < %s -gvn -S | FileCheck %s
+
+%struct.A = type { i32 (...)** }
+@_ZTV1A = available_externally unnamed_addr constant [4 x i8*] [i8* null, i8* bitcast (i8** @_ZTI1A to i8*), i8* bitcast (i32 (%struct.A*)* @_ZN1A3fooEv to i8*), i8* bitcast (i32 (%struct.A*)* @_ZN1A3barEv to i8*)], align 8
+@_ZTI1A = external constant i8*
+
+; Checks if indirect calls can be replaced with direct
+; assuming that %vtable == @_ZTV1A (with alignment).
+; Checking const propagation across other BBs
+; CHECK-LABEL: define void @_Z1gb(
+
+define void @_Z1gb(i1 zeroext %p) {
+entry:
+  %call = tail call noalias i8* @_Znwm(i64 8) #4
+  %0 = bitcast i8* %call to %struct.A*
+  tail call void @_ZN1AC1Ev(%struct.A* %0) #1
+  %1 = bitcast i8* %call to i8***
+  %vtable = load i8**, i8*** %1, align 8
+  %cmp.vtables = icmp eq i8** %vtable, getelementptr inbounds ([4 x i8*], [4 x i8*]* @_ZTV1A, i64 0, i64 2)
+  tail call void @llvm.assume(i1 %cmp.vtables)
+  br i1 %p, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %vtable1.cast = bitcast i8** %vtable to i32 (%struct.A*)**
+  %2 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vtable1.cast, align 8
+  
+  ; CHECK: call i32 @_ZN1A3fooEv(
+  %call2 = tail call i32 %2(%struct.A* %0) #1
+  
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %vfn47 = getelementptr inbounds i8*, i8** %vtable, i64 1
+  %vfn4 = bitcast i8** %vfn47 to i32 (%struct.A*)**
+  
+  ; CHECK: call i32 @_ZN1A3barEv(
+  %3 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vfn4, align 8
+  
+  %call5 = tail call i32 %3(%struct.A* %0) #1
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+; Checking const propagation in the same BB
+; CHECK-LABEL: define i32 @main()
+
+define i32 @main() {
+entry:
+  %call = tail call noalias i8* @_Znwm(i64 8) 
+  %0 = bitcast i8* %call to %struct.A*
+  tail call void @_ZN1AC1Ev(%struct.A* %0) 
+  %1 = bitcast i8* %call to i8***
+  %vtable = load i8**, i8*** %1, align 8
+  %cmp.vtables = icmp eq i8** %vtable, getelementptr inbounds ([4 x i8*], [4 x i8*]* @_ZTV1A, i64 0, i64 2)
+  tail call void @llvm.assume(i1 %cmp.vtables)
+  %vtable1.cast = bitcast i8** %vtable to i32 (%struct.A*)**
+  
+  ; CHECK: call i32 @_ZN1A3fooEv(
+  %2 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vtable1.cast, align 8
+  
+  %call2 = tail call i32 %2(%struct.A* %0)
+  ret i32 0
+}
+
+; This tests checks const propatation with fcmp instruction.
+; CHECK-LABEL: define float @_Z1gf(float %p)
+
+define float @_Z1gf(float %p) {
+entry:
+  %p.addr = alloca float, align 4
+  %f = alloca float, align 4
+  store float %p, float* %p.addr, align 4
+  
+  store float 3.000000e+00, float* %f, align 4
+  %0 = load float, float* %p.addr, align 4
+  %1 = load float, float* %f, align 4
+  %cmp = fcmp oeq float %1, %0 ; note const on lhs
+  call void @llvm.assume(i1 %cmp)
+  
+  ; CHECK: ret float 3.000000e+00
+  ret float %0
+}
+
+; CHECK-LABEL: define float @_Z1hf(float %p)
+
+define float @_Z1hf(float %p) {
+entry:
+  %p.addr = alloca float, align 4
+  store float %p, float* %p.addr, align 4
+  
+  %0 = load float, float* %p.addr, align 4
+  %cmp = fcmp nnan ueq float %0, 3.000000e+00
+  call void @llvm.assume(i1 %cmp)
+  
+  ; CHECK: ret float 3.000000e+00
+  ret float %0
+}
+
+; CHECK-LABEL: define float @_Z1if(float %p)
+
+
+define float @_Z1if(float %p) {
+entry:
+  %p.addr = alloca float, align 4
+  store float %p, float* %p.addr, align 4
+  
+  %0 = load float, float* %p.addr, align 4
+  %cmp = fcmp ueq float %0, 3.000000e+00 ; no nnan flag - can't propagate
+  call void @llvm.assume(i1 %cmp)
+  
+  ; CHECK-NOT: ret float 3.000000e+00
+  ret float %0
+}
+
+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*)
+