2 * Copyright © 2018 Valve Corporation
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
24 * Daniel Schürmann (daniel.schuermann@campus.tu-berlin.de)
28 #ifndef ACO_DOMINANCE_CPP
29 #define ACO_DOMINANCE_CPP
34 * Implements the algorithms for computing the dominator tree from
35 * "A Simple, Fast Dominance Algorithm" by Cooper, Harvey, and Kennedy.
37 * Different from the paper, our CFG allows to compute the dominator tree
38 * in a single pass as it is guaranteed that the dominating predecessors
39 * are processed before the current block.
44 void dominator_tree(Program
* program
)
46 program
->blocks
[0].logical_idom
= 0;
47 program
->blocks
[0].linear_idom
= 0;
49 for (unsigned i
= 1; i
< program
->blocks
.size(); i
++) {
50 Block
& block
= program
->blocks
[i
];
51 int new_logical_idom
= -1;
52 int new_linear_idom
= -1;
53 for (unsigned pred_idx
: block
.logical_preds
) {
54 if ((int) program
->blocks
[pred_idx
].logical_idom
== -1)
57 if (new_logical_idom
== -1) {
58 new_logical_idom
= pred_idx
;
62 while ((int) pred_idx
!= new_logical_idom
) {
63 if ((int) pred_idx
> new_logical_idom
)
64 pred_idx
= program
->blocks
[pred_idx
].logical_idom
;
65 if ((int) pred_idx
< new_logical_idom
)
66 new_logical_idom
= program
->blocks
[new_logical_idom
].logical_idom
;
70 for (unsigned pred_idx
: block
.linear_preds
) {
71 if ((int) program
->blocks
[pred_idx
].linear_idom
== -1)
74 if (new_linear_idom
== -1) {
75 new_linear_idom
= pred_idx
;
79 while ((int) pred_idx
!= new_linear_idom
) {
80 if ((int) pred_idx
> new_linear_idom
)
81 pred_idx
= program
->blocks
[pred_idx
].linear_idom
;
82 if ((int) pred_idx
< new_linear_idom
)
83 new_linear_idom
= program
->blocks
[new_linear_idom
].linear_idom
;
87 block
.logical_idom
= new_logical_idom
;
88 block
.linear_idom
= new_linear_idom
;