[Polly] Use containers with deterministic iteration order

[ctetreau]

Summary

Use MapVector in BlockGenerators and SmallSetVector in IslNodeBuilder.
DenseMap and SmallSet have non-deterministic iteration order, resulting
in differences in code generation between runs of the compiler on the
same input

[efriedma]

polly/include/polly/CodeGen/BlockGenerators.h

37

Where do we iterate over an AllocaMapTy?

polly/include/polly/CodeGen/IslNodeBuilder.h

291

Where do we iterate over PreloadedPtrs?

polly/include/polly/CodeGen/BlockGenerators.h

 /// Generate a new basic block for a polyhedral statement.
 class BlockGenerator {
 public:
   typedef llvm::SmallVector<ValueMapT, 8> VectorValueMapT;
 
   /// Map types to resolve scalar dependences.
   ///
   ///@{
-  using AllocaMapTy = DenseMap<const ScopArrayInfo *, AssertingVH<AllocaInst>>;
+  using AllocaMapTy = MapVector<const ScopArrayInfo *, AssertingVH<AllocaInst>>;
 
   /// Simple vector of instructions to store escape users.
   using EscapeUserVectorTy = SmallVector<Instruction *, 4>;
 
   /// Map type to resolve escaping users for scalar instructions.
   ///
   /// @see The EscapeMap member.
   using EscapeUsersAllocaMapTy =

polly/include/polly/CodeGen/IslNodeBuilder.h

protected:
   /// @param Mark The node we generate code for.
   virtual void createMark(__isl_take isl_ast_node *Marker);
 
   virtual void createFor(__isl_take isl_ast_node *For);
 
   /// Set to remember materialized invariant loads.
   ///
   /// An invariant load is identified by its pointer (the SCEV) and its type.
-  SmallSet<std::pair<const SCEV *, Type *>, 16> PreloadedPtrs;
+  SmallSetVector<std::pair<const SCEV *, Type *>, 16> PreloadedPtrs;
 
   /// Preload the memory access at @p AccessRange with @p Build.
   ///
   /// @returns The preloaded value casted to type @p Ty
   Value *preloadUnconditionally(__isl_take isl_set *AccessRange,
                                 isl_ast_build *Build, Instruction *AccInst);
 
   /// Preload the memory load access @p MA.

polly/lib/CodeGen/IslNodeBuilder.cpp

bool IslNodeBuilder::preloadInvariantEquivClass(
   // class was triggered earlier already and doesn't need to be done again.
   if (ValueMap.count(MA->getAccessInstruction()))
     return true;
 
   // Check for recursion which can be caused by additional constraints, e.g.,
   // non-finite loop constraints. In such a case we have to bail out and insert
   // a "false" runtime check that will cause the original code to be executed.
   auto PtrId = std::make_pair(IAClass.IdentifyingPointer, IAClass.AccessType);
-  if (!PreloadedPtrs.insert(PtrId).second)
+  if (!PreloadedPtrs.insert(PtrId))
     return false;
 
   // The execution context of the IAClass.
   isl::set &ExecutionCtx = IAClass.ExecutionContext;
 
   // If the base pointer of this class is dependent on another one we have to
   // make sure it was preloaded already.
   auto *SAI = MA->getScopArrayInfo();