SPIRV/InReadableOrder.cpp

   1 // The SPIR-V spec requires code blocks to appear in an order satisfying the
   2 // dominator-tree direction (ie, dominator before the dominated).  This is,
   3 // actually, easy to achieve: any pre-order CFG traversal algorithm will do it.
   4 // Because such algorithms visit a block only after traversing some path to it
   5 // from the root, they necessarily visit the block's idom first.
   6 //
   7 // But not every graph-traversal algorithm outputs blocks in an order that
   8 // appears logical to human readers.  The problem is that unrelated branches may
   9 // be interspersed with each other, and merge blocks may come before some of the
  10 // branches being merged.
  11 //
  12 // A good, human-readable order of blocks may be achieved by performing
  13 // depth-first search but delaying merge nodes until after all their branches
  14 // have been visited.  This is implemented below by the inReadableOrder()
  15 // function.
  16
  17 #include "spvIR.h"
  18
  19 #include <algorithm>
  20 #include <deque>
  21 #include <unordered_map>
  22 #include <unordered_set>
  23
  24 using spv::Block;
  25 using spv::Id;
  26 using BlockSet = std::unordered_set<Id>;
  27 using IdToBool = std::unordered_map<Id, bool>;
  28
  29 namespace {
  30 // True if any of prerequisites have not yet been visited.
  31 bool delay(const BlockSet& prereqs, const IdToBool& visited) {
  32   return std::any_of(prereqs.begin(), prereqs.end(),
  33                      [&visited](Id b) { return !visited.count(b); });
  34 }
  35 }
  36
  37 void spv::inReadableOrder(Block* root, std::function<void(Block*)> callback) {
  38   // Prerequisites for a merge block; must be completed prior to visiting the
  39   // merge block.
  40   std::unordered_map<Id, BlockSet> prereqs;
  41   IdToBool visited;               // Whether a block has already been visited.
  42   std::deque<Block*> worklist;  // DFS worklist
  43   worklist.push_back(root);
  44   while (!worklist.empty()) {
  45     Block* current = worklist.front();
  46     worklist.pop_front();
  47     // Nodes may be pushed repeadetly (before they're first visited) if they
  48     // have multiple predecessors.  Skip the already-visited ones.
  49     if (visited[current->getId()]) continue;
  50     callback(current);
  51     visited[current->getId()] = true;
  52     if (auto merge = current->getMergeInstruction()) {
  53       auto& mergePrereqs = prereqs[merge->getIdOperand(0)];
  54       // Delay visiting merge blocks until all branches are visited.
  55       for (const auto succ : current->getSuccessors())
  56         mergePrereqs.insert(succ->getId());
  57     }
  58     for (auto succ : current->getSuccessors()) {
  59       if (!visited[succ->getId()] && !delay(prereqs[succ->getId()], visited)) {
  60         worklist.push_back(succ);
  61       }
  62     }
  63   }
  64 }