Home | History | Annotate | Line # | Download | only in compiler 
      1 /*
      2  * Copyright  2018 Valve Corporation
      3  *
      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:
     10  *
     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
     13  * Software.
     14  *
     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
     21  * IN THE SOFTWARE.
     22  *
     23  */
     24 
     25 #ifndef ACO_DOMINANCE_CPP
     26 #define ACO_DOMINANCE_CPP
     27 
     28 #include "aco_ir.h"
     29 
     30 /*
     31  * Implements the algorithms for computing the dominator tree from
     32  * "A Simple, Fast Dominance Algorithm" by Cooper, Harvey, and Kennedy.
     33  *
     34  * Different from the paper, our CFG allows to compute the dominator tree
     35  * in a single pass as it is guaranteed that the dominating predecessors
     36  * are processed before the current block.
     37  */
     38 
     39 namespace aco {
     40 
     41 void
     42 dominator_tree(Program* program)
     43 {
     44    program->blocks[0].logical_idom = 0;
     45    program->blocks[0].linear_idom = 0;
     46 
     47    for (unsigned i = 1; i < program->blocks.size(); i++) {
     48       Block& block = program->blocks[i];
     49       int new_logical_idom = -1;
     50       int new_linear_idom = -1;
     51       for (unsigned pred_idx : block.logical_preds) {
     52          if ((int)program->blocks[pred_idx].logical_idom == -1)
     53             continue;
     54 
     55          if (new_logical_idom == -1) {
     56             new_logical_idom = pred_idx;
     57             continue;
     58          }
     59 
     60          while ((int)pred_idx != new_logical_idom) {
     61             if ((int)pred_idx > new_logical_idom)
     62                pred_idx = program->blocks[pred_idx].logical_idom;
     63             if ((int)pred_idx < new_logical_idom)
     64                new_logical_idom = program->blocks[new_logical_idom].logical_idom;
     65          }
     66       }
     67 
     68       for (unsigned pred_idx : block.linear_preds) {
     69          if ((int)program->blocks[pred_idx].linear_idom == -1)
     70             continue;
     71 
     72          if (new_linear_idom == -1) {
     73             new_linear_idom = pred_idx;
     74             continue;
     75          }
     76 
     77          while ((int)pred_idx != new_linear_idom) {
     78             if ((int)pred_idx > new_linear_idom)
     79                pred_idx = program->blocks[pred_idx].linear_idom;
     80             if ((int)pred_idx < new_linear_idom)
     81                new_linear_idom = program->blocks[new_linear_idom].linear_idom;
     82          }
     83       }
     84 
     85       block.logical_idom = new_logical_idom;
     86       block.linear_idom = new_linear_idom;
     87    }
     88 }
     89 
     90 } // namespace aco
     91 #endif
     92