1/*
2 * Copyright © 2014 Intel Corporation
3 * Copyright © 2021 Valve Corporation
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 *
24 */
25
26#include "ir3.h"
27#include "ralloc.h"
28
29/*
30 * Implements the algorithms for computing the dominance tree and the
31 * dominance frontier from "A Simple, Fast Dominance Algorithm" by Cooper,
32 * Harvey, and Kennedy.
33 */
34
35static struct ir3_block *
36intersect(struct ir3_block *b1, struct ir3_block *b2)
37{
38   while (b1 != b2) {
39      /*
40       * Note, the comparisons here are the opposite of what the paper says
41       * because we index blocks from beginning -> end (i.e. reverse
42       * post-order) instead of post-order like they assume.
43       */
44      while (b1->index > b2->index)
45         b1 = b1->imm_dom;
46      while (b2->index > b1->index)
47         b2 = b2->imm_dom;
48   }
49
50   return b1;
51}
52
53static bool
54calc_dominance(struct ir3_block *block)
55{
56   struct ir3_block *new_idom = NULL;
57   for (unsigned i = 0; i < block->predecessors_count; i++) {
58      struct ir3_block *pred = block->predecessors[i];
59
60      if (pred->imm_dom) {
61         if (new_idom)
62            new_idom = intersect(pred, new_idom);
63         else
64            new_idom = pred;
65      }
66   }
67
68   if (block->imm_dom != new_idom) {
69      block->imm_dom = new_idom;
70      return true;
71   }
72
73   return false;
74}
75
76static unsigned
77calc_dfs_indices(struct ir3_block *block, unsigned index)
78{
79   block->dom_pre_index = index++;
80   for (unsigned i = 0; i < block->dom_children_count; i++)
81      index = calc_dfs_indices(block->dom_children[i], index);
82   block->dom_post_index = index++;
83   return index;
84}
85
86void
87ir3_calc_dominance(struct ir3 *ir)
88{
89   unsigned i = 0;
90   foreach_block (block, &ir->block_list) {
91      block->index = i++;
92      if (block == ir3_start_block(ir))
93         block->imm_dom = block;
94      else
95         block->imm_dom = NULL;
96      block->dom_children = NULL;
97      block->dom_children_count = block->dom_children_sz = 0;
98   }
99
100   bool progress = true;
101   while (progress) {
102      progress = false;
103      foreach_block (block, &ir->block_list) {
104         if (block != ir3_start_block(ir))
105            progress |= calc_dominance(block);
106      }
107   }
108
109   ir3_start_block(ir)->imm_dom = NULL;
110
111   foreach_block (block, &ir->block_list) {
112      if (block->imm_dom)
113         array_insert(block->imm_dom, block->imm_dom->dom_children, block);
114   }
115
116   calc_dfs_indices(ir3_start_block(ir), 0);
117}
118
119/* Return true if a dominates b. This includes if a == b. */
120bool
121ir3_block_dominates(struct ir3_block *a, struct ir3_block *b)
122{
123   return a->dom_pre_index <= b->dom_pre_index &&
124          a->dom_post_index >= b->dom_post_index;
125}
126