[Polly][PM] Make the new-pm passes behave more like the legacy passes

[philip.pfaffe]

Summary

Testing the new-pm passes becomes much easier once they behave more like the
old passes in terms of the order in which Scops are processed and printed. This
requires three changes:

• ScopInfo: Use an ordered map to store scops
• ScopInfo: Iterate and print Scops in reverse order to match legacy PM behaviour
• ScopDetection: print function name in ScopAnalysisPrinter

[grosser]

LGTM.

We may want to discuss if a better path ordering is possible, but I would prefer to have (close-to) full test coverage before improving this.

lib/Analysis/ScopInfo.cpp

5293 ↗

(On Diff #109689)

Maybe add a comment why you are doing this.

polly/trunk/include/polly/ScopInfo.h

public:
 
   void print(raw_ostream &O, const Module *M = nullptr) const override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 };
 
 class ScopInfo {
 public:
-  using RegionToScopMapTy = DenseMap<Region *, std::unique_ptr<Scop>>;
+  using RegionToScopMapTy = MapVector<Region *, std::unique_ptr<Scop>>;
+  using reverse_iterator = RegionToScopMapTy::reverse_iterator;
+  using const_reverse_iterator = RegionToScopMapTy::const_reverse_iterator;
   using iterator = RegionToScopMapTy::iterator;
   using const_iterator = RegionToScopMapTy::const_iterator;
 
 private:
   /// A map of Region to its Scop object containing
   ///        Polly IR of static control part.
   RegionToScopMapTy RegionToScopMap;
 
if (MapIt != RegionToScopMap.end())
       return MapIt->second.get();
     return nullptr;
   }
 
   iterator begin() { return RegionToScopMap.begin(); }
   iterator end() { return RegionToScopMap.end(); }
   const_iterator begin() const { return RegionToScopMap.begin(); }
   const_iterator end() const { return RegionToScopMap.end(); }
+  reverse_iterator rbegin() { return RegionToScopMap.rbegin(); }
+  reverse_iterator rend() { return RegionToScopMap.rend(); }
+  const_reverse_iterator rbegin() const { return RegionToScopMap.rbegin(); }
+  const_reverse_iterator rend() const { return RegionToScopMap.rend(); }
   bool empty() const { return RegionToScopMap.empty(); }
 };
 
 struct ScopInfoAnalysis : public AnalysisInfoMixin<ScopInfoAnalysis> {
   static AnalysisKey Key;
   using Result = ScopInfo;
   Result run(Function &, FunctionAnalysisManager &);
 };

polly/trunk/lib/Analysis/ScopDetection.cpp

ScopDetection ScopAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
   auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
   auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
   return {F, DT, SE, LI, RI, AA, ORE};
 }
 
 PreservedAnalyses ScopAnalysisPrinterPass::run(Function &F,
                                                FunctionAnalysisManager &FAM) {
+  Stream << "Detected Scops in Function " << F.getName() << "\n";
   auto &SD = FAM.getResult<ScopAnalysis>(F);
   for (const Region *R : SD.ValidRegions)
     Stream << "Valid Region for Scop: " << R->getNameStr() << '\n';
 
   Stream << "\n";
   return PreservedAnalyses::all();
 }
 

polly/trunk/lib/Analysis/ScopInfo.cpp

ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,
   auto &AC = FAM.getResult<AssumptionAnalysis>(F);
   auto &DL = F.getParent()->getDataLayout();
   return {DL, SD, SE, LI, AA, DT, AC};
 }
 
 PreservedAnalyses ScopInfoPrinterPass::run(Function &F,
                                            FunctionAnalysisManager &FAM) {
   auto &SI = FAM.getResult<ScopInfoAnalysis>(F);
-  for (auto &It : SI) {
+  // Since the legacy PM processes Scops in bottom up, we print them in reverse
+  // order here to keep the output persistent
+  for (auto &It : reverse(SI)) {
     if (It.second)
       It.second->print(Stream, PollyPrintInstructions);
     else
       Stream << "Invalid Scop!\n";
   }
   return PreservedAnalyses::all();
 }