[polly] Fix non-determinism in polly BlockGenerators

[mgrang]

Summary

Iterating over SeenBlocks which is a SmallPtrSet results in non-determinism in codegen

[mgrang]

Here is the run-to-run difference in IR which causes difference in codegen. Notice the order of the predicates.

Run1:
polly.stmt.if.then587: ; preds = %polly.stmt.for.end521, %polly.stmt.lor.lhs.false523

Run2:
polly.stmt.if.then587: ; preds = %polly.stmt.lor.lhs.false523, %polly.stmt.for.end521

[grosser]

This patch LGTM!

[grosser]

Can you commit this yourself or do you need me to commit this?

[mgrang]

Thanks Tobias. I can commit myself :)

polly/trunk/lib/CodeGen/BlockGenerators.cpp

void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);
 
   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
     if (!R->contains(*PI))
       BlockMap[*PI] = EntryBBCopy;
 
   // Iterate over all blocks in the region in a breadth-first search.
   std::deque<BasicBlock *> Blocks;
-  SmallPtrSet<BasicBlock *, 8> SeenBlocks;
+  SmallSetVector<BasicBlock *, 8> SeenBlocks;
   Blocks.push_back(EntryBB);
   SeenBlocks.insert(EntryBB);
 
   while (!Blocks.empty()) {
     BasicBlock *BB = Blocks.front();
     Blocks.pop_front();
 
     // First split the block and update dominance information.
while (!Blocks.empty()) {
 
     // Add values to incomplete PHI nodes waiting for this block to be copied.
     for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
       addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
     IncompletePHINodeMap[BB].clear();
 
     // And continue with new successors inside the region.
     for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)
-      if (R->contains(*SI) && SeenBlocks.insert(*SI).second)
+      if (R->contains(*SI) && SeenBlocks.insert(*SI))
         Blocks.push_back(*SI);
 
     // Remember value in case it is visible after this subregion.
     if (isDominatingSubregionExit(DT, R, BB))
       ValueMap.insert(RegionMap.begin(), RegionMap.end());
   }
 
   // Now create a new dedicated region exit block and add it to the region map.