src/amd/compiler/aco_dominance.cpp

/*
 * Copyright © 2018 Valve Corporation
 *
 * SPDX-License-Identifier: MIT
 */

#ifndef ACO_DOMINANCE_CPP
#define ACO_DOMINANCE_CPP

#include "aco_ir.h"

/*
 * Implements the algorithms for computing the dominator tree from
 * "A Simple, Fast Dominance Algorithm" by Cooper, Harvey, and Kennedy.
 *
 * Different from the paper, our CFG allows to compute the dominator tree
 * in a single pass as it is guaranteed that the dominating predecessors
 * are processed before the current block.
 */

namespace aco {

namespace {

struct block_dom_info {
   uint32_t logical_descendants = 0;
   uint32_t linear_descendants = 0;
   uint32_t logical_depth = 0;
   uint32_t linear_depth = 0;
   small_vec<uint32_t, 4> logical_children;
   small_vec<uint32_t, 4> linear_children;
};

void
calc_indices(Program* program)
{
   std::vector<block_dom_info> info(program->blocks.size());

   /* Create the linear and logical dominance trees. Calculating logical_descendants and
    * linear_descendants requires no recursion because the immediate dominator of each block has a
    * lower index. */
   for (int i = program->blocks.size() - 1; i >= 0; i--) {
      Block& block = program->blocks[i];

      /* Add this as a child node of the parent. */
      if (block.logical_idom != i && block.logical_idom != -1) {
         assert(i > block.logical_idom);
         info[block.logical_idom].logical_children.push_back(i);
         /* Add this node's descendants and itself to the parent. */
         info[block.logical_idom].logical_descendants += info[i].logical_descendants + 1;
      }
      if (block.linear_idom != i) {
         assert(i > block.linear_idom);
         info[block.linear_idom].linear_children.push_back(i);
         info[block.linear_idom].linear_descendants += info[i].linear_descendants + 1;
      }
   }

   /* Fill in the indices that would be obtained in a preorder and postorder traversal of the
    * dominance trees. */
   for (unsigned i = 0; i < program->blocks.size(); i++) {
      Block& block = program->blocks[i];
      /* Because of block_kind_resume, the root node's indices start at the block index to avoid
       * reusing indices. */
      if (block.logical_idom == (int)i)
         block.logical_dom_pre_index = i;
      if (block.linear_idom == (int)i)
         block.linear_dom_pre_index = i;

      /* Visit each child and assign it's preorder indices and depth. */
      unsigned start = block.logical_dom_pre_index + 1;
      for (unsigned j = 0; j < info[i].logical_children.size(); j++) {
         unsigned child = info[i].logical_children[j];
         info[child].logical_depth = info[i].logical_depth + 1;
         program->blocks[child].logical_dom_pre_index = start;
         start += info[child].logical_descendants + 1;
      }
      start = block.linear_dom_pre_index + 1;
      for (unsigned j = 0; j < info[i].linear_children.size(); j++) {
         unsigned child = info[i].linear_children[j];
         info[child].linear_depth = info[i].linear_depth + 1;
         program->blocks[child].linear_dom_pre_index = start;
         start += info[child].linear_descendants + 1;
      }

      /* The postorder traversal is the same as the preorder traversal, except that when this block
       * is visited, we haven't visited it's ancestors and have already visited it's descendants.
       * This means that the postorder_index is preorder_index-depth+descendants. */
      block.logical_dom_post_index =
         block.logical_dom_pre_index - info[i].logical_depth + info[i].logical_descendants;
      block.linear_dom_post_index =
         block.linear_dom_pre_index - info[i].linear_depth + info[i].linear_descendants;
   }
}

} /* end namespace */

void
dominator_tree(Program* program)
{
   for (unsigned i = 0; i < program->blocks.size(); i++) {
      Block& block = program->blocks[i];

      /* If this block has no predecessor, it dominates itself by definition */
      if (block.linear_preds.empty()) {
         block.linear_idom = block.index;
         block.logical_idom = block.index;
         continue;
      }

      int new_logical_idom = -1;
      int new_linear_idom = -1;
      for (unsigned pred_idx : block.logical_preds) {
         if ((int)program->blocks[pred_idx].logical_idom == -1)
            continue;

         if (new_logical_idom == -1) {
            new_logical_idom = pred_idx;
            continue;
         }

         while ((int)pred_idx != new_logical_idom) {
            if ((int)pred_idx > new_logical_idom)
               pred_idx = program->blocks[pred_idx].logical_idom;
            if ((int)pred_idx < new_logical_idom)
               new_logical_idom = program->blocks[new_logical_idom].logical_idom;
         }
      }

      for (unsigned pred_idx : block.linear_preds) {
         if ((int)program->blocks[pred_idx].linear_idom == -1)
            continue;

         if (new_linear_idom == -1) {
            new_linear_idom = pred_idx;
            continue;
         }

         while ((int)pred_idx != new_linear_idom) {
            if ((int)pred_idx > new_linear_idom)
               pred_idx = program->blocks[pred_idx].linear_idom;
            if ((int)pred_idx < new_linear_idom)
               new_linear_idom = program->blocks[new_linear_idom].linear_idom;
         }
      }

      block.logical_idom = new_logical_idom;
      block.linear_idom = new_linear_idom;
   }

   calc_indices(program);
}

} // namespace aco
#endif