GVN: If X > Y is true, then replace X == Y with false and X != Y with true

[aarzee]

Summary

Currently integer comparisons only.

Correctly optimizes this example file: https://ghostbin.com/paste/g382s

[eli.friedman]

Please don't copy-paste code.

[aarzee]

Should we create a function for this?

[aarzee]

Ping.

[eli.friedman]

Yes, create a function for it. And in general, assume the answer to "should I create a function for this" is yes.

[aarzee]

Outline replacement of instruction with constant. If X == Y is true, replace X >= Y with true and X > Y with false.

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

2032

This needs to be factored into a helper function of some sort, or something.
Adding 100 lines of dense duplicated code is ... bad :)

include/llvm/Transforms/Scalar/GVN.h

private:
   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 DominatesByEdge);
+  void replaceInst(uint32_t NextNum, uint32_t VNToReplace,
+                   Constant *ReplaceWith, const BasicBlockEdge &Root,
+                   bool DominatesByEdge, bool &Changed, bool RootDominatesEnd);
   bool processFoldableCondBr(BranchInst *BI);
   void addDeadBlock(BasicBlock *BB);
   void assignValNumForDeadCode();
 };
 
 /// Create a legacy GVN pass. This also allows parameterizing whether or not
 /// loads are eliminated by the pass.
 FunctionPass *createGVNPass(bool NoLoads = false);

lib/Transforms/Scalar/GVN.cpp

if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
         // FIXME: We should do this optimization if 'no signed zeros' is
         // applicable via an instruction-level fast-math-flag or some other
         // indicator that relaxed FP semantics are being used.
 
         if (isa<ConstantFP>(Op1) && !cast<ConstantFP>(Op1)->isZero())
           Worklist.push_back(std::make_pair(Op0, Op1));
       }
 
-      // If "A >= B" is known true, replace "A < B" with false everywhere.
-      CmpInst::Predicate NotPred = Cmp->getInversePredicate();
-      Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
-      // Since we don't have the instruction "A < B" immediately to hand, work
-      // out the value number that it would have and use that to find an
-      // appropriate instruction (if any).
       uint32_t NextNum = VN.getNextUnusedValueNumber();
-      uint32_t Num = VN.lookupOrAddCmp(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)) {
+
+      // Integer comparison propagation.
+      // If X > Y is true, X != Y is true.
+      // If X == Y is true, X > Y is false and X >= Y is true.
+      if (isa<ICmpInst>(Cmp)) {
+        if (cast<ICmpInst>(Cmp)->isRelational() &&
+            Cmp->isTrueWhenEqual() != isKnownTrue) {
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_EQ,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getFalse(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_NE,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getTrue(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+        }
+        if (Cmp->isEquality() && Cmp->isTrueWhenEqual() == isKnownTrue) {
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_UGT,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getFalse(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_UGE,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getTrue(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_ULT,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getFalse(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_ULE,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getTrue(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_SGT,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getFalse(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_SGE,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getTrue(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_SLT,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getFalse(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+          GVN::replaceInst(NextNum,
+                           VN.lookupOrAddCmp(
+                             Cmp->getOpcode(),
+                             CmpInst::Predicate::ICMP_SLE,
+                             Op0,
+                             Op1
+                           ),
+                           ConstantInt::getTrue(Cmp->getContext()),
+                           Root,
+                           DominatesByEdge,
+                           Changed,
+                           RootDominatesEnd);
+        }
+      }
+
+      // Float comparison propagation.
+      // If X > Y is true, X != Y is true.
+      // If X == Y is true, X > Y is false and X >= Y is true.
+
+      continue;
+    }
+  }
+
+  return Changed;
+}
+
+void GVN::replaceInst(uint32_t NextNum, uint32_t VNToReplace,
+    Constant *ReplaceWith, const BasicBlockEdge &Root, bool DominatesByEdge,
+    bool &Changed, bool RootDominatesEnd) {
+      if (VNToReplace < NextNum) {
+        Value *InstToReplace = findLeader(Root.getEnd(), VNToReplace);
+        if (InstToReplace && isa<Instruction>(InstToReplace)) {
           unsigned NumReplacements =
               DominatesByEdge
-                  ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
-                  : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
-                                             Root.getStart());
+                  ? replaceDominatedUsesWith(InstToReplace, ReplaceWith,
+                                             *DT, Root)
+                  : replaceDominatedUsesWith(InstToReplace, ReplaceWith,
+                                             *DT, Root.getStart());
           Changed |= NumReplacements > 0;
           NumGVNEqProp += NumReplacements;
         }
       }
-      // Ensure that any instruction in scope that gets the "A < B" value number
-      // is replaced with false.
+      // Ensure that any instruction in scope that gets the respective 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.
       if (RootDominatesEnd)
-        addToLeaderTable(Num, NotVal, Root.getEnd());
+        addToLeaderTable(VNToReplace, ReplaceWith, Root.getEnd());
 
-      continue;
-    }
-  }
-
-  return Changed;
 }
 
 /// When calculating availability, handle an instruction
 /// by inserting it into the appropriate sets
 bool GVN::processInstruction(Instruction *I) {
   // Ignore dbg info intrinsics.
   if (isa<DbgInfoIntrinsic>(I))
     return false;