[LegacyPM] Use MapVector for OnTheFlyPassManagers.

[fhahn]

Summary

Currently the iteration order of OnTheFlyManagers is not deterministic
between executions, which means some of test/Other/opt-*-pipeline.ll
tests fail non-deterministically if an additional on-the-fly manager is
added, as in D45330.

By using MapVector, we always iterate in the insertion order. As we are
not removing elements, there shouldn't be a performance hit, except that
we store an additional vector with the keys.

[efriedma]

LGTM.

llvm/trunk/lib/IR/LegacyPassManager.cpp

 //===- LegacyPassManager.cpp - LLVM Pass Infrastructure Implementation ----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the legacy LLVM Pass Manager infrastructure.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/LegacyPassManager.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManagers.h"
 #include "llvm/IR/LegacyPassNameParser.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Chrono.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/Mutex.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
-#include <map>
 #include <unordered_set>
 using namespace llvm;
 using namespace llvm::legacy;
 
 // See PassManagers.h for Pass Manager infrastructure overview.
 
 //===----------------------------------------------------------------------===//
 // Pass debugging information.  Often it is useful to find out what pass is
public:
   Pass *getAsPass() override { return this; }
 
   // Print passes managed by this manager
   void dumpPassStructure(unsigned Offset) override {
     dbgs().indent(Offset*2) << "ModulePass Manager\n";
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       ModulePass *MP = getContainedPass(Index);
       MP->dumpPassStructure(Offset + 1);
-      std::map<Pass *, FunctionPassManagerImpl *>::const_iterator I =
+      MapVector<Pass *, FunctionPassManagerImpl *>::const_iterator I =
           OnTheFlyManagers.find(MP);
       if (I != OnTheFlyManagers.end())
         I->second->dumpPassStructure(Offset + 2);
       dumpLastUses(MP, Offset+1);
     }
   }
 
   ModulePass *getContainedPass(unsigned N) {
     assert(N < PassVector.size() && "Pass number out of range!");
     return static_cast<ModulePass *>(PassVector[N]);
   }
 
   PassManagerType getPassManagerType() const override {
     return PMT_ModulePassManager;
   }
 
  private:
   /// Collection of on the fly FPPassManagers. These managers manage
   /// function passes that are required by module passes.
-  std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
+   MapVector<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
 };
 
 char MPPassManager::ID = 0;
 } // End anonymous namespace
 
 namespace llvm {
 namespace legacy {
 //===----------------------------------------------------------------------===//