Pass a std::uinque_ptr to ParseAssembly to make the ownership explicit. NFC.

[oota-llvm.git] / lib / Bitcode / Writer / ValueEnumerator.cpp

diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp
index 144e8fb08cd772d52a7635d6511db9d8ae9de9d1..4ed739ebe4abe72b5752ab929170ff60765f274f 100644 (file)
--- a/lib/Bitcode/Writer/ValueEnumerator.cpp
+++ b/lib/Bitcode/Writer/ValueEnumerator.cpp
@@ -28,6 +28,17 @@ using namespace llvm;
 namespace {
 struct OrderMap {
   DenseMap<const Value *, std::pair<unsigned, bool>> IDs;
+  unsigned LastGlobalConstantID;
+  unsigned LastGlobalValueID;
+
+  OrderMap() : LastGlobalConstantID(0), LastGlobalValueID(0) {}
+
+  bool isGlobalConstant(unsigned ID) const {
+    return ID <= LastGlobalConstantID;
+  }
+  bool isGlobalValue(unsigned ID) const {
+    return ID <= LastGlobalValueID && !isGlobalConstant(ID);
+  }
 
   unsigned size() const { return IDs.size(); }
   std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }
@@ -49,7 +60,7 @@ static void orderValue(const Value *V, OrderMap &OM) {
   if (const Constant *C = dyn_cast<Constant>(V))
     if (C->getNumOperands() && !isa<GlobalValue>(C))
       for (const Value *Op : C->operands())
-        if (!isa<BasicBlock>(Op))
+        if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
           orderValue(Op, OM);
 
   // Note: we cannot cache this lookup above, since inserting into the map
@@ -62,20 +73,39 @@ static OrderMap orderModule(const Module *M) {
   // and ValueEnumerator::incorporateFunction().
   OrderMap OM;
 
+  // In the reader, initializers of GlobalValues are set *after* all the
+  // globals have been read.  Rather than awkwardly modeling this behaviour
+  // directly in predictValueUseListOrderImpl(), just assign IDs to
+  // initializers of GlobalValues before GlobalValues themselves to model this
+  // implicitly.
   for (const GlobalVariable &G : M->globals())
-    orderValue(&G, OM);
+    if (G.hasInitializer())
+      if (!isa<GlobalValue>(G.getInitializer()))
+        orderValue(G.getInitializer(), OM);
+  for (const GlobalAlias &A : M->aliases())
+    if (!isa<GlobalValue>(A.getAliasee()))
+      orderValue(A.getAliasee(), OM);
+  for (const Function &F : *M)
+    if (F.hasPrefixData())
+      if (!isa<GlobalValue>(F.getPrefixData()))
+        orderValue(F.getPrefixData(), OM);
+  OM.LastGlobalConstantID = OM.size();
+
+  // Initializers of GlobalValues are processed in
+  // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
+  // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
+  // by giving IDs in reverse order.
+  //
+  // Since GlobalValues never reference each other directly (just through
+  // initializers), their relative IDs only matter for determining order of
+  // uses in their initializers.
   for (const Function &F : *M)
     orderValue(&F, OM);
   for (const GlobalAlias &A : M->aliases())
     orderValue(&A, OM);
   for (const GlobalVariable &G : M->globals())
-    if (G.hasInitializer())
-      orderValue(G.getInitializer(), OM);
-  for (const GlobalAlias &A : M->aliases())
-    orderValue(A.getAliasee(), OM);
-  for (const Function &F : *M)
-    if (F.hasPrefixData())
-      orderValue(F.getPrefixData(), OM);
+    orderValue(&G, OM);
+  OM.LastGlobalValueID = OM.size();
 
   for (const Function &F : *M) {
     if (F.isDeclaration())
@@ -115,8 +145,8 @@ static void predictValueUseListOrderImpl(const Value *V, const Function *F,
     // We may have lost some users.
     return;
 
-  std::sort(List.begin(), List.end(),
-            [&OM, ID](const Entry &L, const Entry &R) {
+  bool IsGlobalValue = OM.isGlobalValue(ID);
+  std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) {
     const Use *LU = L.first;
     const Use *RU = R.first;
     if (LU == RU)
@@ -124,22 +154,36 @@ static void predictValueUseListOrderImpl(const Value *V, const Function *F,
 
     auto LID = OM.lookup(LU->getUser()).first;
     auto RID = OM.lookup(RU->getUser()).first;
+
+    // Global values are processed in reverse order.
+    //
+    // Moreover, initializers of GlobalValues are set *after* all the globals
+    // have been read (despite having earlier IDs).  Rather than awkwardly
+    // modeling this behaviour here, orderModule() has assigned IDs to
+    // initializers of GlobalValues before GlobalValues themselves.
+    if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID))
+      return LID < RID;
+
     // If ID is 4, then expect: 7 6 5 1 2 3.
     if (LID < RID) {
-      if (RID < ID)
-        return true;
+      if (RID <= ID)
+        if (!IsGlobalValue) // GlobalValue uses don't get reversed.
+          return true;
       return false;
     }
     if (RID < LID) {
-      if (LID < ID)
-        return false;
+      if (LID <= ID)
+        if (!IsGlobalValue) // GlobalValue uses don't get reversed.
+          return false;
       return true;
     }
+
     // LID and RID are equal, so we have different operands of the same user.
     // Assume operands are added in order for all instructions.
-    if (LU->getOperandNo() < RU->getOperandNo())
-      return LID < ID;
-    return ID < LID;
+    if (LID <= ID)
+      if (!IsGlobalValue) // GlobalValue uses don't get reversed.
+        return LU->getOperandNo() < RU->getOperandNo();
+    return LU->getOperandNo() > RU->getOperandNo();
   });
 
   if (std::is_sorted(
@@ -170,9 +214,9 @@ static void predictValueUseListOrder(const Value *V, const Function *F,
 
   // Recursive descent into constants.
   if (const Constant *C = dyn_cast<Constant>(V))
-    if (C->getNumOperands() && !isa<GlobalValue>(C))
+    if (C->getNumOperands()) // Visit GlobalValues.
       for (const Value *Op : C->operands())
-        if (isa<Constant>(Op) && !isa<GlobalValue>(Op))
+        if (isa<Constant>(Op)) // Visit GlobalValues.
           predictValueUseListOrder(Op, F, OM, Stack);
 }
 
@@ -200,8 +244,7 @@ static UseListOrderStack predictUseListOrder(const Module *M) {
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)
         for (const Value *Op : I.operands())
-          if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
-              isa<InlineAsm>(*Op))
+          if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
             predictValueUseListOrder(Op, &F, OM, Stack);
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB)