Change the RegionSet type to a SetVector

[dpeixott]

Summary

This patch changes the RegionSet type used in ScopDetection from a
std::set to a llvm::SetVector. The reason for the change is to
ensure deterministic output when printing the result of the
analysis. We had a windows buildbot failure for the modified test
because the output was coming in a different order.

Only one test case needed to be modified for this change. We could
use CHECK-DAG directives instead of CHECK in the analysis test cases
because the actual order of scops does not matter, but I think that
change should be done in a separate patch that modifies all the
appliciable tests. I simply modified the test to reflect the
expected deterministic output.

[dpeixott]

Closed by commit rL220423 (authored by @dpeixott).

include/polly/ScopDetection.h

 // creating a larger non canonical region.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOP_DETECTION_H
 #define POLLY_SCOP_DETECTION_H
 
 #include "llvm/Pass.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 
 #include "polly/ScopDetectionDiagnostic.h"
 
 #include "llvm/ADT/SetVector.h"
 
 #include <set>
 #include <map>

 
 /// @brief A function attribute which will cause Polly to skip the function
 extern llvm::StringRef PollySkipFnAttr;
 
 //===----------------------------------------------------------------------===//
 /// @brief Pass to detect the maximal static control parts (Scops) of a
 /// function.
 class ScopDetection : public FunctionPass {
+public:
+  typedef SetVector<const Region *> RegionSet;
+
+private:
   //===--------------------------------------------------------------------===//
   ScopDetection(const ScopDetection &) LLVM_DELETED_FUNCTION;
   const ScopDetection &operator=(const ScopDetection &) LLVM_DELETED_FUNCTION;
 
   /// @brief Analysis passes used.
   //@{
   ScalarEvolution *SE;
   LoopInfo *LI;
struct DetectionContext {
     SetVector<const SCEVUnknown *> NonAffineAccesses;
     BaseToElSize ElementSize;
 
     DetectionContext(Region &R, AliasAnalysis &AA, bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R) {}
   };
 
   // Remember the valid regions
-  typedef std::set<const Region *> RegionSet;
   RegionSet ValidRegions;
 
   // Remember a list of errors for every region.
   mutable RejectLogsContainer RejectLogs;
 
   // Delinearize all non affine memory accesses and return false when there
   // exists a non affine memory access that cannot be delinearized. Return true
   // when all array accesses are affine after delinearization.

lib/Analysis/ScopDetection.cpp

static bool regionWithoutLoops(Region &R, LoopInfo *LI) {
 
   return true;
 }
 
 // Remove all direct and indirect children of region R from the region set Regs,
 // but do not recurse further if the first child has been found.
 //
 // Return the number of regions erased from Regs.
-static unsigned eraseAllChildren(std::set<const Region *> &Regs,
+static unsigned eraseAllChildren(ScopDetection::RegionSet &Regs,
                                  const Region &R) {
   unsigned Count = 0;
   for (auto &SubRegion : R) {
-    if (Regs.find(SubRegion.get()) != Regs.end()) {
+    if (Regs.count(SubRegion.get())) {
       ++Count;
-      Regs.erase(SubRegion.get());
+      Regs.remove(SubRegion.get());
     } else {
       Count += eraseAllChildren(Regs, *SubRegion);
     }
   }
   return Count;
 }
 
 void ScopDetection::findScops(Region &R) {
void ScopDetection::findScops(Region &R) {
   for (Region *CurrentRegion : ToExpand) {
     // Skip regions that had errors.
     bool HadErrors = RejectLogs.hasErrors(CurrentRegion);
     if (HadErrors)
       continue;
 
     // Skip invalid regions. Regions may become invalid, if they are element of
     // an already expanded region.
-    if (ValidRegions.find(CurrentRegion) == ValidRegions.end())
+    if (!ValidRegions.count(CurrentRegion))
       continue;
 
     Region *ExpandedR = expandRegion(*CurrentRegion);
 
     if (!ExpandedR)
       continue;
 
     R.addSubRegion(ExpandedR, true);
     ValidRegions.insert(ExpandedR);
-    ValidRegions.erase(CurrentRegion);
+    ValidRegions.remove(CurrentRegion);
 
     // Erase all (direct and indirect) children of ExpandedR from the valid
     // regions and update the number of valid regions.
     ValidRegion -= eraseAllChildren(ValidRegions, *ExpandedR);
   }
 }
 
 bool ScopDetection::allBlocksValid(DetectionContext &Context) const {

test/ScopInfo/multi-scop.ll

for.body81:                                       ; preds = %for.body81, %for.end
   store double undef, double* %arrayidx139, align 8
   %add169 = add nsw i32 %j.19, 2
   br i1 false, label %for.body81, label %for.end170
 
 for.end170:                                       ; preds = %for.body81
   ret void
 }
 
-; CHECK: Valid Region for Scop: for.body81 => for.end170
 ; CHECK: Valid Region for Scop: entry.split => for.end
+; CHECK: Valid Region for Scop: for.body81 => for.end170