SPIRV/InReadableOrder.cpp

   1 //
   2 //Copyright (C) 2016 Google, Inc.
   3 //
   4 //All rights reserved.
   5 //
   6 //Redistribution and use in source and binary forms, with or without
   7 //modification, are permitted provided that the following conditions
   8 //are met:
   9 //
  10 //    Redistributions of source code must retain the above copyright
  11 //    notice, this list of conditions and the following disclaimer.
  12 //
  13 //    Redistributions in binary form must reproduce the above
  14 //    copyright notice, this list of conditions and the following
  15 //    disclaimer in the documentation and/or other materials provided
  16 //    with the distribution.
  17 //
  18 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
  19 //    contributors may be used to endorse or promote products derived
  20 //    from this software without specific prior written permission.
  21 //
  22 //THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23 //"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24 //LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25 //FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  26 //COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27 //INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28 //BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29 //LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  30 //CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31 //LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  32 //ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33 //POSSIBILITY OF SUCH DAMAGE.
  34
  35 //
  36 // Author: Dejan Mircevski, Google
  37 //
  38
  39 // The SPIR-V spec requires code blocks to appear in an order satisfying the
  40 // dominator-tree direction (ie, dominator before the dominated).  This is,
  41 // actually, easy to achieve: any pre-order CFG traversal algorithm will do it.
  42 // Because such algorithms visit a block only after traversing some path to it
  43 // from the root, they necessarily visit the block's idom first.
  44 //
  45 // But not every graph-traversal algorithm outputs blocks in an order that
  46 // appears logical to human readers.  The problem is that unrelated branches may
  47 // be interspersed with each other, and merge blocks may come before some of the
  48 // branches being merged.
  49 //
  50 // A good, human-readable order of blocks may be achieved by performing
  51 // depth-first search but delaying merge nodes until after all their branches
  52 // have been visited.  This is implemented below by the inReadableOrder()
  53 // function.
  54
  55 #include "spvIR.h"
  56
  57 #include <cassert>
  58 #include <unordered_map>
  59
  60 using spv::Block;
  61 using spv::Id;
  62
  63 namespace {
  64 // Traverses CFG in a readable order, invoking a pre-set callback on each block.
  65 // Use by calling visit() on the root block.
  66 class ReadableOrderTraverser {
  67  public:
  68   explicit ReadableOrderTraverser(std::function<void(Block*)> callback)
  69       : callback_(callback) {}
  70
  71   // Visits the block if it hasn't been visited already and isn't currently
  72   // being delayed.  Invokes callback(block), then descends into its successors.
  73   // Delays merge-block processing until all the branches have been completed.
  74   void visit(Block* block) {
  75     assert(block);
  76     if (visited_[block] || delayed_[block]) return;
  77     callback_(block);
  78     visited_[block] = true;
  79     Block* mergeBlock = nullptr;
  80     auto mergeInst = block->getMergeInstruction();
  81     if (mergeInst) {
  82       Id mergeId = mergeInst->getIdOperand(0);
  83       mergeBlock =
  84           block->getParent().getParent().getInstruction(mergeId)->getBlock();
  85       delayed_[mergeBlock] = true;
  86     }
  87     for (const auto succ : block->getSuccessors()) visit(succ);
  88     if (mergeBlock) {
  89       delayed_[mergeBlock] = false;
  90       visit(mergeBlock);
  91     }
  92   }
  93
  94  private:
  95   std::function<void(Block*)> callback_;
  96   // Whether a block has already been visited or is being delayed.
  97   std::unordered_map<Block*, bool> visited_, delayed_;
  98 };
  99 }
 100
 101 void spv::inReadableOrder(Block* root, std::function<void(Block*)> callback) {
 102   ReadableOrderTraverser(callback).visit(root);
 103 }