From 44bfb0d0cd3417f9d2494d9055d89b45cbf30ff8 Mon Sep 17 00:00:00 2001
From: Dejan Mircevski <deki@google.com>
Date: Mon, 18 Jan 2016 16:18:37 -0500
Subject: [PATCH] Implement inReadableOrder().

---
 SPIRV/CMakeLists.txt      |  1 +
 SPIRV/InReadableOrder.cpp | 64 +++++++++++++++++++++++++++++++++++++++++++++++
 SPIRV/spvIR.h             | 28 +++++++++++++++++----
 3 files changed, 88 insertions(+), 5 deletions(-)
 create mode 100644 SPIRV/InReadableOrder.cpp

diff --git a/SPIRV/CMakeLists.txt b/SPIRV/CMakeLists.txt
index 945350e..50cda68 100755
--- a/SPIRV/CMakeLists.txt
+++ b/SPIRV/CMakeLists.txt
@@ -2,6 +2,7 @@ cmake_minimum_required(VERSION 2.8)
 
 set(SOURCES
     GlslangToSpv.cpp
+    InReadableOrder.cpp
     SpvBuilder.cpp
     SPVRemapper.cpp
     doc.cpp
diff --git a/SPIRV/InReadableOrder.cpp b/SPIRV/InReadableOrder.cpp
new file mode 100644
index 0000000..f081212
--- /dev/null
+++ b/SPIRV/InReadableOrder.cpp
@@ -0,0 +1,64 @@
+// The SPIR-V spec requires code blocks to appear in an order satisfying the
+// dominator-tree direction (ie, dominator before the dominated).  This is,
+// actually, easy to achieve: any pre-order CFG traversal algorithm will do it.
+// Because such algorithms visit a block only after traversing some path to it
+// from the root, they necessarily visit the block's idom first.
+//
+// But not every graph-traversal algorithm outputs blocks in an order that
+// appears logical to human readers.  The problem is that unrelated branches may
+// be interspersed with each other, and merge blocks may come before some of the
+// branches being merged.
+//
+// A good, human-readable order of blocks may be achieved by performing
+// depth-first search but delaying merge nodes until after all their branches
+// have been visited.  This is implemented below by the inReadableOrder()
+// function.
+
+#include "spvIR.h"
+
+#include <algorithm>
+#include <deque>
+#include <unordered_map>
+#include <unordered_set>
+
+using spv::Block;
+using spv::Id;
+using BlockSet = std::unordered_set<Id>;
+using IdToBool = std::unordered_map<Id, bool>;
+
+namespace {
+// True if any of prerequisites have not yet been visited.
+bool delay(const BlockSet& prereqs, const IdToBool& visited) {
+  return std::any_of(prereqs.begin(), prereqs.end(),
+                     [&visited](Id b) { return !visited.count(b); });
+}
+}
+
+void spv::inReadableOrder(Block* root, std::function<void(Block*)> callback) {
+  // Prerequisites for a merge block; must be completed prior to visiting the
+  // merge block.
+  std::unordered_map<Id, BlockSet> prereqs;
+  IdToBool visited;               // Whether a block has already been visited.
+  std::deque<Block*> worklist;  // DFS worklist
+  worklist.push_back(root);
+  while (!worklist.empty()) {
+    Block* current = worklist.front();
+    worklist.pop_front();
+    // Nodes may be pushed repeadetly (before they're first visited) if they
+    // have multiple predecessors.  Skip the already-visited ones.
+    if (visited[current->getId()]) continue;
+    callback(current);
+    visited[current->getId()] = true;
+    if (auto merge = current->getMergeInstruction()) {
+      auto& mergePrereqs = prereqs[merge->getIdOperand(0)];
+      // Delay visiting merge blocks until all branches are visited.
+      for (const auto succ : current->getSuccessors())
+        mergePrereqs.insert(succ->getId());
+    }
+    for (auto succ : current->getSuccessors()) {
+      if (!visited[succ->getId()] && !delay(prereqs[succ->getId()], visited)) {
+        worklist.push_back(succ);
+      }
+    }
+  }
+}
diff --git a/SPIRV/spvIR.h b/SPIRV/spvIR.h
index 38e5197..a854384 100755
--- a/SPIRV/spvIR.h
+++ b/SPIRV/spvIR.h
@@ -52,10 +52,11 @@
 
 #include "spirv.hpp"
 
-#include <vector>
+#include <cassert>
+#include <functional>
 #include <iostream>
 #include <memory>
-#include <assert.h>
+#include <vector>
 
 namespace spv {
 
@@ -157,7 +158,7 @@ public:
     virtual ~Block()
     {
     }
-    
+
     Id getId() { return instructions.front()->getResultId(); }
 
     Function& getParent() const { return parent; }
@@ -168,6 +169,19 @@ public:
     const std::vector<Block*> getSuccessors() const { return successors; }
     void setUnreachable() { unreachable = true; }
     bool isUnreachable() const { return unreachable; }
+    // Returns the block's merge instruction, if one exists (otherwise null).
+    const Instruction* getMergeInstruction() const {
+        if (instructions.size() < 2) return nullptr;
+        const Instruction* nextToLast = *(instructions.cend() - 2);
+        switch (nextToLast->getOpCode()) {
+            case OpSelectionMerge:
+            case OpLoopMerge:
+                return nextToLast;
+            default:
+                return nullptr;
+        }
+        return nullptr;
+    }
 
     bool isTerminated() const
     {
@@ -217,6 +231,11 @@ protected:
     bool unreachable;
 };
 
+// Traverses the control-flow graph rooted at root in an order suited for
+// readable code generation.  Invokes callback at every node in the traversal
+// order.
+void inReadableOrder(Block* root, std::function<void(Block*)> callback);
+
 //
 // SPIR-V IR Function.
 //
@@ -253,8 +272,7 @@ public:
             parameterInstructions[p]->dump(out);
 
         // Blocks
-        for (int b = 0; b < (int)blocks.size(); ++b)
-            blocks[b]->dump(out);
+        inReadableOrder(blocks[0], [&out](const Block* b) { b->dump(out); });
         Instruction end(0, 0, OpFunctionEnd);
         end.dump(out);
     }
-- 
2.7.4