dominate.c

   1 // SPDX-License-Identifier: MIT
   2 //
   3 // dominate.c - compute the (iterated) dominance frontier of (a set of) nodes.
   4 //
   5 // Copyright (C) 2017 - Luc Van Oostenryck
   6 //
   7 // The algorithm used is the one described in:
   8 //      "A Linear Time Algorithm for Placing phi-nodes"
   9 //      by Vugranam C. Sreedhar and Guang R. Gao
  10 //
  11
  12 #include "dominate.h"
  13 #include "flowgraph.h"
  14 #include "linearize.h"
  15 #include "flow.h"
  16 #include <assert.h>
  17 #include <stdlib.h>
  18 #include <stdio.h>
  19
  20
  21 struct piggy {
  22         unsigned int max;
  23         struct basic_block_list *lists[0];
  24 };
  25
  26 static struct piggy *bank_init(unsigned levels)
  27 {
  28         struct piggy *bank;
  29         bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0]));
  30         bank->max = levels - 1;
  31         return bank;
  32 }
  33
  34 static void bank_free(struct piggy *bank, unsigned int levels)
  35 {
  36         for (; levels-- ;)
  37                 free_ptr_list(&bank->lists[levels]);
  38         free(bank);
  39 }
  40
  41 static void bank_put(struct piggy *bank, struct basic_block *bb)
  42 {
  43         unsigned int level = bb->dom_level;
  44         assert(level <= bank->max);
  45         add_bb(&bank->lists[level], bb);
  46 }
  47
  48 static inline struct basic_block *pop_bb(struct basic_block_list **list)
  49 {
  50         return delete_ptr_list_last((struct ptr_list **)list);
  51 }
  52
  53 static struct basic_block *bank_get(struct piggy *bank)
  54 {
  55         int level = bank->max;
  56         do {
  57                 struct basic_block *bb = pop_bb(&bank->lists[level]);
  58                 if (bb)
  59                         return bb;
  60                 if (!level)
  61                         return NULL;
  62                 bank->max = --level;
  63         } while (1);
  64 }
  65
  66
  67 #define VISITED 0x1
  68 #define INPHI   0x2
  69 #define ALPHA   0x4
  70 #define FLAGS   0x7
  71
  72 static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level)
  73 {
  74         struct basic_block *y;
  75
  76         x->generation |= 1;
  77         FOR_EACH_PTR(x->children, y) {
  78                 unsigned flags = y->generation & FLAGS;
  79                 if (y->idom == x)       // J-edges will be processed later
  80                         continue;
  81                 if (y->dom_level > curr_level)
  82                         continue;
  83                 if (flags & INPHI)
  84                         continue;
  85                 y->generation |= INPHI;
  86                 add_bb(idf, y);
  87                 if (flags & ALPHA)
  88                         continue;
  89                 bank_put(bank, y);
  90         } END_FOR_EACH_PTR(y);
  91
  92         FOR_EACH_PTR(x->doms, y) {
  93                 if (y->generation & VISITED)
  94                         continue;
  95                 visit(bank, idf, y, curr_level);
  96         } END_FOR_EACH_PTR(y);
  97 }
  98
  99 void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha)
 100 {
 101         int levels = ep->dom_levels;
 102         struct piggy *bank = bank_init(levels);
 103         struct basic_block *bb;
 104         unsigned long generation = bb_generation;
 105
 106         generation = bb_generation;
 107         generation += -generation & FLAGS;
 108         bb_generation = generation + (FLAGS + 1);
 109
 110         // init all the nodes
 111         FOR_EACH_PTR(ep->bbs, bb) {
 112                 // FIXME: this should be removed and the tests for
 113                 //        visited/in_phi/alpha should use a sparse set
 114                 bb->generation = generation;
 115         } END_FOR_EACH_PTR(bb);
 116
 117         FOR_EACH_PTR(alpha, bb) {
 118                 bb->generation = generation | ALPHA;
 119                 bank_put(bank, bb);
 120         } END_FOR_EACH_PTR(bb);
 121
 122         while ((bb = bank_get(bank))) {
 123                 visit(bank, idf, bb, bb->dom_level);
 124         }
 125
 126         bank_free(bank, levels);
 127 }
 128
 129 void idf_dump(struct entrypoint *ep)
 130 {
 131         struct basic_block *bb;
 132
 133         domtree_build(ep);
 134
 135         printf("%s's IDF:\n", show_ident(ep->name->ident));
 136         FOR_EACH_PTR(ep->bbs, bb) {
 137                 struct basic_block_list *alpha = NULL;
 138                 struct basic_block_list *idf = NULL;
 139                 struct basic_block *df;
 140
 141                 add_bb(&alpha, bb);
 142                 idf_compute(ep, &idf, alpha);
 143
 144                 printf("\t%s\t<-", show_label(bb));
 145                 FOR_EACH_PTR(idf, df) {
 146                         printf(" %s", show_label(df));
 147                 } END_FOR_EACH_PTR(df);
 148                 printf("\n");
 149
 150                 free_ptr_list(&idf);
 151                 free_ptr_list(&alpha);
 152         } END_FOR_EACH_PTR(bb);
 153 }