[Float2Int] Make sure dependent ranges are calculated first (PR54669)

[nikic]

Summary

The range calculation in walkForwards() assumes that the ranges of the operands have already been calculated. With the used visit order, this is not necessarily the case when there are multiple roots. (There is nothing guaranteeing that instructions are visited in topological order.)

Fix this by queuing instructions for reprocessing if the operand ranges haven't been calculated yet.

Fixes https://github.com/llvm/llvm-project/issues/54669.

[xbolva00]

Possible to add a test?

[nikic]

Ooops ... this is supposed to include the test from https://github.com/llvm/llvm-project/issues/54669, but apparently I forgot to git add it.

[uabelho]

Nice! I've verified that this solves the problem I saw.
Thanks!

[nikic]

Add test

[spatel]

I haven't looked at this pass very much, but the patch LGTM.

llvm/include/llvm/Transforms/Scalar/Float2Int.h

 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 class DominatorTree;
 class Function;
 class Instruction;
 class LLVMContext;
+template <typename T> class Optional;
 class Type;
 class Value;
 
 class Float2IntPass : public PassInfoMixin<Float2IntPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for old PM.
   bool runImpl(Function &F, const DominatorTree &DT);
 
 private:
   void findRoots(Function &F, const DominatorTree &DT);
   void seen(Instruction *I, ConstantRange R);
   ConstantRange badRange();
   ConstantRange unknownRange();
   ConstantRange validateRange(ConstantRange R);
-  ConstantRange calcRange(Instruction *I);
+  Optional<ConstantRange> calcRange(Instruction *I);
   void walkBackwards();
   void walkForwards();
   bool validateAndTransform();
   Value *convert(Instruction *I, Type *ToTy);
   void cleanup();
 
   MapVector<Instruction *, ConstantRange> SeenInsts;
   SmallSetVector<Instruction *, 8> Roots;
   EquivalenceClasses<Instruction *> ECs;
   MapVector<Instruction *, Value *> ConvertedInsts;
   LLVMContext *Ctx;
 };
 }
 #endif // LLVM_TRANSFORMS_SCALAR_FLOAT2INT_H

llvm/lib/Transforms/Scalar/Float2Int.cpp

for (Value *O : I->operands()) {
       } else if (!isa<ConstantFP>(O)) {
         // Not an instruction or ConstantFP? we can't do anything.
         seen(I, badRange());
       }
     }
   }
 }
 
-// Calculate result range from operand ranges
-ConstantRange Float2IntPass::calcRange(Instruction *I) {
+// Calculate result range from operand ranges.
+// Return None if the range cannot be calculated yet.
+Optional<ConstantRange> Float2IntPass::calcRange(Instruction *I) {
   SmallVector<ConstantRange, 4> OpRanges;
   for (Value *O : I->operands()) {
     if (Instruction *OI = dyn_cast<Instruction>(O)) {
-      assert(SeenInsts.find(OI) != SeenInsts.end() &&
-             "def not seen before use!");
-      OpRanges.push_back(SeenInsts.find(OI)->second);
+      auto OpIt = SeenInsts.find(OI);
+      assert(OpIt != SeenInsts.end() && "def not seen before use!");
+      if (OpIt->second == unknownRange())
+        return None; // Wait until operand range has been calculated.
+      OpRanges.push_back(OpIt->second);
     } else if (ConstantFP *CF = dyn_cast<ConstantFP>(O)) {
       // Work out if the floating point number can be losslessly represented
       // as an integer.
       // APFloat::convertToInteger(&Exact) purports to do what we want, but
       // the exactness can be too precise. For example, negative zero can
       // never be exactly converted to an integer.
       //
       // Instead, we ask APFloat to round itself to an integral value - this
case Instruction::FCmp:
     assert(OpRanges.size() == 2 && "FCmp is a binary operator!");
     return OpRanges[0].unionWith(OpRanges[1]);
   }
 }
 
 // Walk forwards down the list of seen instructions, so we visit defs before
 // uses.
 void Float2IntPass::walkForwards() {
-  for (auto &It : reverse(SeenInsts)) {
-    if (It.second != unknownRange())
-      continue;
+  std::deque<Instruction *> Worklist;
+  for (const auto &Pair : SeenInsts)
+    if (Pair.second == unknownRange())
+      Worklist.push_back(Pair.first);
+
+  while (!Worklist.empty()) {
+    Instruction *I = Worklist.back();
+    Worklist.pop_back();
 
-    Instruction *I = It.first;
-    seen(I, calcRange(I));
+    if (Optional<ConstantRange> Range = calcRange(I))
+      seen(I, *Range);
+    else
+      Worklist.push_front(I); // Reprocess later.
   }
 }
 
 // If there is a valid transform to be done, do it.
 bool Float2IntPass::validateAndTransform() {
   bool MadeChange = false;
 
   // Iterate over every disjoint partition of the def-use graph.

llvm/test/Transforms/Float2Int/pr54669.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -float2int < %s | FileCheck %s
 
 declare void @use(i32)
 
-; FIXME: Currently being miscompiled.
-
 define i1 @src() {
 ; CHECK-LABEL: @src(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 2147483647, -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 -1, -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = fadd double 2.000000e+00, -1.000000e+00
   %mul = fmul double %add, 0x41EFFFFFFFE00000
   %conv = fptoui double %mul to i32
   %cmp = icmp eq i32 %conv, -1
   %conv2 = fptoui double %add to i32
   ret i1 %cmp
 }