Constant propagation after hiting assume(icmp)

[majnemer]

lib/Transforms/Scalar/GVN.cpp

2101–2108

Avoid making changes not relevant to this change. This seems like a fine change to do separately.

2258–2263

The type is obvious so you could just use auto *. Also, consider splitting this into another function to reduce indentation.

2266–2269

Initialisms are typically capitalized.

2272

This could be written more concisely as: !LHSConst != !RHSConst. The xor is a little out of place considering you aren't doing anything with bits.

[nlewycky]

lib/Transforms/Scalar/GVN.cpp

611–612

The description is not wrong, but I would've described it differently:

// 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> LocalLeaderMap;

Notably there's nothing *const-y* about it. We often replace X with Y when both are Instructions, or when Y is an Argument, or in this case when Y is a Constant. What's special about this is that it's block-local.

727

s/instr/I/

2073

Extra blank.

2075

Extra spaces before semicolons

2260

Extr ablank.

2264

Extra blank.

2266–2267

LHS and RHS. If you're worried about shadowing the existing LHS and RHS, I'd suggest ICmpLHS and ICmpRHS or ICmpOp0 and ICmpOp1.

2271–2272

The common idiom is to check which is Constant and then use std::swap.

However, we canonicalize constants to the RHS when possible (ie., not "sub" instructions). Any reason it would be de-canonicalized at this point?

2276

Capitalize.

2277

Period.

2278–2280

Surely this fits on fewer lines?

2291

Extra blank.

2441

I suspect this should have a quick exit for the common case where ReplaceWithConstMap is empty. Putting the test here might make sense, so that we don't even call it at -O0.

We surely don't want to iterate over the operands calling find on an empty map.

test/Transforms/GVN/assume-ptr-equal-same-bb.ll

1 ↗

(On Diff #31712)

Please merge the two tests, using FileCheck for both of them. I think you can replace the grep with a CHECK: here.

[• dberlin]

So, this is essentially trying to start to get GVN to recognize that operations are made of operations on value numbers.

Except you are only handling the really special case where those value numbers are constant over the entire program (instead of also handling cases where the operations simplify, or have arithmetic niceties, etc. SimplifyInstruction will do some of this, but it won't notice some classes of things)

I'm generally biased against trying to bolt more into our current GVN, but hey, when you do stuff like this, it just makes New GVN a lot faster by comparison :)

So SGTM

lib/Transforms/Scalar/GVN.cpp

2263

Why only ICMP_EQ?

2277

This isn't quite right :)
There are cases that propagate equality checks, and cases we don't call it because it would do the wrong thing.

For example, i know your code doesn't quite work right with assume followed by certain types of switch statements (where there are multiple edges to the same successor).

See the code handling switch statements, that verifies there are not multiple edges to the same successor, and if there are not, *does not call propagateEquality* (old line 2259)

You are going to either need to unify or duplicate a lot of this kind of logic, depending on the terminator of the basic block the assume statement is in.

[Prazek]

lib/Transforms/Scalar/GVN.cpp

2272

!LHSConst != !RHSConst looks bad to me. I can change it to LHSConst != RHSConst

[Prazek]

lib/Transforms/Scalar/GVN.cpp

2263

You mean to add fcmp also?

[• dberlin]

Not just that.
llvm.assume asserts whatever the condition is, is true.
PropagateEquality will propagate equalities like (A < B) == true as
well, by replacing all dominated instances of A>= B == false.

So you should be able to "propagate" basically all the ICMP variants.

[Prazek]

LGTM someone?

[hfinkel]

lib/Transforms/Scalar/GVN.cpp

1778

It looks like all of the arguments could fit on one line (or at most two), please do that.

1782

I'd prefer a blank line between the } and the if.

1784

We can include FCMP_UEQ here if the fcmp has the nnans fast-math flag, please do so.

[nlewycky]

lib/Transforms/Scalar/GVN.cpp

1769

Please add a string to this: assert(expression && "Failure message"); See http://llvm.org/docs/CodingStandards.html#assert-liberally

1771

Wrong context. Use the same context from any Type or Value you have.

Let me explain what llvm contexts are for. They're intended to keep different threads separate, and keep them from accessing each others data, since llvm does not have internal locking. So the context owns the types and constant, and if two threads try to create "i1 true" at the same time then they'll race on updating the map. (Also, it's a verifier failure to have two Type*'s form two contexts involved in the same Module. By default everyone just uses the global context, but there may be a library user that does not.)

1773

"Successor". See http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

1776–1777

Reflow this comment.

2070–2071

Reflow this comment.

test/Transforms/GVN/assume-ptr-equal.ll

7–23

Please interleave the check statements with the function being tested. This helps show which calls should I expect to become direct calls to foo and bar.

16

Typo, CHECK-LABLE

[nlewycky]

lib/Transforms/Scalar/GVN.cpp

1777–1778

I think this comment could be made more clear. Why can't equality propagation be done for every successor? What does propagateEquality check? Something like:

"This property is only true in dominated successors, propagateEquality will check dominance for us."

perhaps?

2075

Operand

test/Transforms/GVN/assume-ptr-equal.ll

29

Is this a call to _ZN1A3fooEv or _Z1A3barEv? Put the CHECK line next to this line (usually right after).

[nlewycky]

LGTM

lib/Transforms/Scalar/GVN.cpp

class GVN : public FunctionPass {
     struct LeaderTableEntry {
       Value *Val;
       const BasicBlock *BB;
       LeaderTableEntry *Next;
     };
     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;
     typedef SmallVector<AvailableValueInBlock, 64> AvailValInBlkVect;
     typedef SmallVector<BasicBlock*, 64> UnavailBlkVect;
 
   public:
     static char ID; // Pass identification, replacement for typeid
void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addPreserved<AliasAnalysis>();
     }
 
 
     // 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);
     bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, 
                         UnavailBlkVect &UnavailableBlocks);
 
     // Other helper routines
     bool processInstruction(Instruction *I);
     bool processBlock(BasicBlock *BB);
     void dump(DenseMap<uint32_t, Value*> &d);
     bool iterateOnFunction(Function &F);
     bool performPRE(Function &F);
     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);
+    bool replaceOperandsWithConsts(Instruction *I) const;
     bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root);
     bool processFoldableCondBr(BranchInst *BI);
     void addDeadBlock(BasicBlock *BB);
     void assignValNumForDeadCode();
   };
 
   char GVN::ID = 0;
 }
bool GVN::processNonLocalLoad(LoadInst *LI) {
 
   // Step 4: Eliminate partial redundancy.
   if (!EnablePRE || !EnableLoadPRE)
     return false;
 
   return PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks);
 }
 
+bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) {
+  assert(IntrinsicI->getIntrinsicID() == Intrinsic::assume);
+  Value *V = IntrinsicI->getArgOperand(0);
+  Constant *True = ConstantInt::getTrue(getGlobalContext());
+  bool Changed = false;
+  for (BasicBlock *successor : successors(IntrinsicI->getParent())) {
+    BasicBlockEdge Edge(IntrinsicI->getParent(), successor);
+
+    // Equality propagation can't be done for every
+    // successor, but propagateEquality checks it.
+    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) {
+      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
   // being replaced.
   BinaryOperator *Op = dyn_cast<BinaryOperator>(I);
   BinaryOperator *ReplOp = dyn_cast<BinaryOperator>(Repl);
   if (Op && ReplOp)
     ReplOp->andIRFlags(Op);
static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
   // been changed to have only one predecessor, namely Src.
   const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
   const BasicBlock *Src = E.getStart();
   assert((!Pred || Pred == Src) && "No edge between these basic blocks!");
   (void)Src;
   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.
 bool GVN::propagateEquality(Value *LHS, Value *RHS,
                             const BasicBlockEdge &Root) {
   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()) {
     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)))
       std::swap(LHS, RHS);
     assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
 
     // If there is no obvious reason to prefer the left-hand side over the
     // right-hand side, ensure the longest lived term is on the right-hand side,
     // so the shortest lived term will be replaced by the longest lived.
if (Value *V = SimplifyInstruction(I, DL, TLI, DT, AC)) {
     I->replaceAllUsesWith(V);
     if (MD && V->getType()->getScalarType()->isPointerTy())
       MD->invalidateCachedPointerInfo(V);
     markInstructionForDeletion(I);
     ++NumGVNSimpl;
     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;
 
     unsigned Num = VN.lookup_or_add(LI);
     addToLeaderTable(Num, LI, LI->getParent());
     return false;
   }
 
   // For conditional branches, we can perform simple conditional propagation on
   // the condition value itself.
   if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
     if (!BI->isConditional())
       return false;
 
     if (isa<Constant>(BI->getCondition()))
       return processFoldableCondBr(BI);
 
     Value *BranchCond = BI->getCondition();
     BasicBlock *TrueSucc = BI->getSuccessor(0);
     BasicBlock *FalseSucc = BI->getSuccessor(1);
     // Avoid multiple edges early.
     if (TrueSucc == FalseSucc)
       return false;
 
     BasicBlock *Parent = BI->getParent();
     bool Changed = false;
 
     Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext());
     BasicBlockEdge TrueE(Parent, TrueSucc);
     Changed |= propagateEquality(BranchCond, TrueVal, TrueE);
 
     Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext());
     BasicBlockEdge FalseE(Parent, FalseSucc);
     Changed |= propagateEquality(BranchCond, FalseVal, FalseE);
 
     return Changed;
   }
for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
         Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E);
       }
     }
     return Changed;
   }
 
   // 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);
 
   // Allocations are always uniquely numbered, so we can save time and memory
   // by fast failing them.
   if (isa<AllocaInst>(I) || isa<TerminatorInst>(I) || isa<PHINode>(I)) {
     addToLeaderTable(Num, I, I->getParent());

 bool GVN::processBlock(BasicBlock *BB) {
   // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
   // (and incrementing BI before processing an instruction).
   assert(InstrsToErase.empty() &&
          "We expect InstrsToErase to be empty across iterations");
   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;
       continue;
     }
 
     // If we need some instructions deleted, do it now.
     NumGVNInstr += InstrsToErase.size();

test/Transforms/GVN/assume-ptr-equal.ll

+; RUN: opt < %s -gvn -S | FileCheck %s
+
+; 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(
+; CHECK: call i32 @_ZN1A3fooEv(
+; CHECK: call i32 @_ZN1A3barEv(
+
+; Checking const propagation in the same BB
+; CHECK-LABEL: define i32 @main()
+; CHECK: call i32 @_ZN1A3fooEv(
+
+; CHECK-LABLE: define float @_Z1gf(float %p)
+; CHECK: ret float 3.000000e+00
+
+%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*
+
+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
+  %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*)**
+  %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
+}
+
+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*)**
+  %2 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vtable1.cast, align 8
+  %call2 = tail call i32 %2(%struct.A* %0)
+  ret i32 0
+}
+
+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)
+  
+  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*)
+