[Float2Int] Make iteration over Roots deterministic

[bjope]

Summary

Use a SmallSetVector instead of a SmallPtrSet when collecting
and storing Roots.

The iteration order for a SmallPtrSet is not deterministic,
so in the past the order of items inserted in the WorkList
inside walkBackwards has been non-deterministic. This patch
intends to make the order of rewrites done in Float2Int
deterministic by changing the container for the Roots set.

The semantics result of the transformation should not be
any different afaict. But at least naming of IR variables
(when outputting the result as an ll file) should be more
stable now.

[bjope]

(not sure whom to add as reviewer to patches like this, added some random people who has contributed to this pass earlier)

Also see https://reviews.llvm.org/D74533 for a preparatory cleanup patch.

[bjope]

Removed the need for D74533 as pre-commit, by removing the passing of
the Roots member variable as argument to member functions.

[spatel]

llvm/lib/Transforms/Scalar/Float2Int.cpp

527–529

Isn't the change use the member variable directly (rather than passing a param to it) truly NFC?
IIUC, we should make that change first (no need for pre-commit review).

[bjope]

Rebased after pre-commit of the cleanup (we no longer pass around references to Roots).

[spatel]

I'd say we reduced this as much as possible. :)
LGTM

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

 //===-- Float2Int.h - Demote floating point ops to work on integers -------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file provides the Float2Int pass, which aims to demote floating
 // point operations to work on integers, where that is losslessly possible.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_FLOAT2INT_H
 #define LLVM_TRANSFORMS_SCALAR_FLOAT2INT_H
 
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 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,
-                 SmallPtrSet<Instruction *, 8> &Roots);
+  void findRoots(Function &F, const DominatorTree &DT);
   void seen(Instruction *I, ConstantRange R);
   ConstantRange badRange();
   ConstantRange unknownRange();
   ConstantRange validateRange(ConstantRange R);
-  void walkBackwards(const SmallPtrSetImpl<Instruction *> &Roots);
+  void walkBackwards();
   void walkForwards();
   bool validateAndTransform();
   Value *convert(Instruction *I, Type *ToTy);
   void cleanup();
 
   MapVector<Instruction *, ConstantRange> SeenInsts;
-  SmallPtrSet<Instruction *, 8> Roots;
+  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

 //===- Float2Int.cpp - Demote floating point ops to work on integers ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
static Instruction::BinaryOps mapBinOpcode(unsigned Opcode) {
   case Instruction::FAdd: return Instruction::Add;
   case Instruction::FSub: return Instruction::Sub;
   case Instruction::FMul: return Instruction::Mul;
   }
 }
 
 // Find the roots - instructions that convert from the FP domain to
 // integer domain.
-void Float2IntPass::findRoots(Function &F, const DominatorTree &DT,
-                              SmallPtrSet<Instruction*,8> &Roots) {
+void Float2IntPass::findRoots(Function &F, const DominatorTree &DT) {
   for (BasicBlock &BB : F) {
     // Unreachable code can take on strange forms that we are not prepared to
     // handle. For example, an instruction may have itself as an operand.
     if (!DT.isReachableFromEntry(&BB))
       continue;
 
     for (Instruction &I : BB) {
       if (isa<VectorType>(I.getType()))

 //                     instructions and poison values if they're obvious and
 //                     cheap to compute. Calculate the equivalance set structure
 //                     while we're here too.
 //   - walkForwards:  Iterate over SeenInsts in reverse order, so we visit
 //                     defs before their uses. Calculate the real range info.
 
 // Breadth-first walk of the use-def graph; determine the set of nodes
 // we care about and eagerly determine if some of them are poisonous.
-void Float2IntPass::walkBackwards(const SmallPtrSetImpl<Instruction*> &Roots) {
+void Float2IntPass::walkBackwards() {
   std::deque<Instruction*> Worklist(Roots.begin(), Roots.end());
   while (!Worklist.empty()) {
     Instruction *I = Worklist.back();
     Worklist.pop_back();
 
     if (SeenInsts.find(I) != SeenInsts.end())
       // Seen already.
       continue;
bool Float2IntPass::runImpl(Function &F, const DominatorTree &DT) {
   // Clear out all state.
   ECs = EquivalenceClasses<Instruction*>();
   SeenInsts.clear();
   ConvertedInsts.clear();
   Roots.clear();
 
   Ctx = &F.getParent()->getContext();
 
-  findRoots(F, DT, Roots);
+  findRoots(F, DT);
 
-  walkBackwards(Roots);
+  walkBackwards();
   walkForwards();
 
   bool Modified = validateAndTransform();
   if (Modified)
     cleanup();
   return Modified;
 }