kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

pass_cfg.c (9542B)

      1 /* pass_cfg.c — derive Block.preds and Block.succ/nsucc from each
      2  * block's terminator. doc/OPT.md §3 Phase 3.
      3  *
      4  * Terminator inventory:
      5  *   IR_BR                          — 1 succ (succ[0])
      6  *   IR_CONDBR                      — 2 succs ([true, false])
      7  *   IR_CMP_BRANCH                  — 2 succs ([taken, fallthrough])
      8  *   IR_RET                         — 0 succs
      9  *   IR_INTRINSIC LONGJMP/TRAP/UNREACHABLE — 0 succs
     10  *   IR_BREAK_TO / IR_CONTINUE_TO   — 0 succs (control transferred to
     11  *                                    the scope's break/continue label,
     12  *                                    which is a successor encoded on
     13  *                                    the IRScopeAux; pass populates
     14  *                                    succ from there)
     15  *
     16  * INTRIN_SETJMP falls through, so pass_cfg sees it as a normal inst.
     17  *
     18  * For scope ops the wrapper's recording assigns succ[] at emit time
     19  * (since it owns the vlabel→block_id mapping). pass_cfg trusts that
     20  * and only repopulates from the trailing terminator inst when one is
     21  * present. */
     22 
     23 #include <string.h>
     24 
     25 #include "core/arena.h"
     26 #include "core/core.h"
     27 #include "opt/opt_internal.h"
     28 
     29 static int is_terminator(const Inst* in) {
     30   switch ((IROp)in->op) {
     31     case IR_BR:
     32     case IR_CONDBR:
     33     case IR_CMP_BRANCH:
     34     case IR_SWITCH:
     35     case IR_INDIRECT_BRANCH:
     36     case IR_RET:
     37     case IR_UNREACHABLE:
     38     case IR_BREAK_TO:
     39     case IR_CONTINUE_TO:
     40       return 1;
     41     case IR_INTRINSIC: {
     42       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
     43       return aux && (aux->kind == INTRIN_LONGJMP || aux->kind == INTRIN_TRAP);
     44     }
     45     default:
     46       return 0;
     47   }
     48 }
     49 
     50 static int scope_control_succ_count(const Block* bl, const Inst* in,
     51                                     u8* nsucc_out) {
     52   switch ((IROp)in->op) {
     53     case IR_SCOPE_BEGIN: {
     54       *nsucc_out = bl->nsucc;
     55       return bl->nsucc != 0;
     56     }
     57     case IR_SCOPE_END:
     58       *nsucc_out = bl->nsucc;
     59       return bl->nsucc != 0;
     60     default:
     61       return 0;
     62   }
     63 }
     64 
     65 static void push_reachable(Func* f, u8* reachable, u32* stack, u32* sp,
     66                            u32 block) {
     67   if (block < f->nblocks && !reachable[block]) {
     68     reachable[block] = 1;
     69     stack[(*sp)++] = block;
     70   }
     71 }
     72 
     73 static void mark_label_addr_targets_reachable(Func* f, const Inst* in,
     74                                               u8* reachable, u32* stack,
     75                                               u32* sp) {
     76   switch ((IROp)in->op) {
     77     case IR_LOAD_LABEL_ADDR:
     78       push_reachable(f, reachable, stack, sp, (u32)in->extra.imm);
     79       break;
     80     case IR_LOCAL_STATIC_DATA_LABEL_ADDR: {
     81       CgIrLocalStaticLabelAux* aux =
     82           (CgIrLocalStaticLabelAux*)in->extra.aux;
     83       if (aux) push_reachable(f, reachable, stack, sp, (u32)aux->target);
     84       break;
     85     }
     86     default:
     87       break;
     88   }
     89 }
     90 
     91 static u8* mark_reachable(Func* f) {
     92   u8* reachable = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u);
     93   if (f->entry >= f->nblocks) return reachable;
     94 
     95   u32* stack = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u);
     96   u32 sp = 0;
     97   push_reachable(f, reachable, stack, &sp, f->entry);
     98   while (sp) {
     99     u32 b = stack[--sp];
    100     if (b >= f->nblocks) continue;
    101     Block* bl = &f->blocks[b];
    102     for (u32 s = 0; s < bl->nsucc; ++s) {
    103       u32 t = bl->succ[s];
    104       push_reachable(f, reachable, stack, &sp, t);
    105     }
    106     for (u32 i = 0; i < bl->ninsts; ++i)
    107       mark_label_addr_targets_reachable(f, &bl->insts[i], reachable, stack,
    108                                         &sp);
    109   }
    110   return reachable;
    111 }
    112 
    113 static void prune_unreachable(Func* f, const u8* reachable) {
    114   for (u32 b = 0; b < f->nblocks; ++b) {
    115     if (reachable[b]) continue;
    116     Block* bl = &f->blocks[b];
    117     bl->insts = NULL;
    118     bl->ninsts = 0;
    119     bl->cap = 0;
    120     bl->preds = NULL;
    121     bl->npreds = 0;
    122     bl->nsucc = 0;
    123   }
    124 
    125   u32 w = 0;
    126   for (u32 i = 0; i < f->emit_order_n; ++i) {
    127     u32 b = f->emit_order[i];
    128     if (b < f->nblocks && reachable[b]) f->emit_order[w++] = b;
    129   }
    130   f->emit_order_n = w;
    131 }
    132 
    133 void opt_replace_succ_ref(Func* f, u32 pred, u32 old_succ, u32 new_succ) {
    134   if (!f || pred >= f->nblocks) return;
    135   Block* bl = &f->blocks[pred];
    136   for (u32 s = 0; s < bl->nsucc; ++s) {
    137     if (bl->succ[s] == old_succ) bl->succ[s] = new_succ;
    138   }
    139   if (!bl->ninsts) return;
    140   Inst* term = &bl->insts[bl->ninsts - 1u];
    141   if ((IROp)term->op == IR_SWITCH) {
    142     IRSwitchAux* aux = (IRSwitchAux*)term->extra.aux;
    143     if (!aux) return;
    144     for (u32 i = 0; i < aux->ncases; ++i)
    145       if (aux->cases[i].block == old_succ) aux->cases[i].block = new_succ;
    146     if (aux->default_block == old_succ) aux->default_block = new_succ;
    147   } else if ((IROp)term->op == IR_INDIRECT_BRANCH) {
    148     IRIndirectAux* aux = (IRIndirectAux*)term->extra.aux;
    149     if (!aux) return;
    150     for (u32 i = 0; i < aux->ntargets; ++i)
    151       if (aux->targets[i] == old_succ) aux->targets[i] = new_succ;
    152   }
    153 }
    154 
    155 void opt_emit_order_insert_after(Func* f, u32 after, u32 block) {
    156   if (!f) return;
    157   for (u32 i = 0; i < f->emit_order_n; ++i)
    158     if (f->emit_order[i] == block) return;
    159   if (f->emit_order_n == f->emit_order_cap) {
    160     u32 ncap = f->emit_order_cap ? f->emit_order_cap * 2u : 8u;
    161     u32* order = arena_array(f->arena, u32, ncap);
    162     if (f->emit_order)
    163       memcpy(order, f->emit_order, sizeof(order[0]) * f->emit_order_n);
    164     f->emit_order = order;
    165     f->emit_order_cap = ncap;
    166   }
    167   u32 pos = f->emit_order_n;
    168   for (u32 i = 0; i < f->emit_order_n; ++i) {
    169     if (f->emit_order[i] == after) {
    170       pos = i + 1u;
    171       break;
    172     }
    173   }
    174   for (u32 i = f->emit_order_n; i > pos; --i)
    175     f->emit_order[i] = f->emit_order[i - 1u];
    176   f->emit_order[pos] = block;
    177   ++f->emit_order_n;
    178 }
    179 
    180 int opt_edge_is_fallthrough(Func* f, u32 pred, u32 succ) {
    181   if (!f || pred >= f->nblocks) return 0;
    182   Block* bl = &f->blocks[pred];
    183   if (!bl->ninsts) return 0;
    184   IROp op = (IROp)bl->insts[bl->ninsts - 1u].op;
    185   if (op != IR_CMP_BRANCH && op != IR_CONDBR) return 0;
    186   return bl->nsucc >= 2 && bl->succ[1] == succ;
    187 }
    188 
    189 u32 opt_split_edge(Func* f, u32 pred, u32 succ) {
    190   if (!f) return 0;
    191   u32 edge = ir_block_new(f);
    192   Block* eb = &f->blocks[edge];
    193   Inst* br = ir_emit(f, edge, IR_BR);
    194   (void)br;
    195   eb->succ[0] = succ;
    196   eb->nsucc = 1;
    197   int place_after = opt_edge_is_fallthrough(f, pred, succ);
    198   opt_replace_succ_ref(f, pred, succ, edge);
    199   if (succ < f->nblocks) {
    200     Block* sb = &f->blocks[succ];
    201     for (u32 i = 0; i < sb->ninsts; ++i) {
    202       Inst* phi = &sb->insts[i];
    203       if ((IROp)phi->op != IR_PHI) break;
    204       IRPhiAux* aux = (IRPhiAux*)phi->extra.aux;
    205       if (!aux) continue;
    206       for (u32 p = 0; p < aux->npreds; ++p) {
    207         if (aux->pred_blocks[p] == pred) {
    208           aux->pred_blocks[p] = edge;
    209           aux->pred_vals[p] = phi->def;
    210         }
    211       }
    212     }
    213   }
    214   if (place_after) {
    215     opt_emit_order_insert_after(f, pred, edge);
    216   } else {
    217     ir_note_emit(f, edge);
    218   }
    219   opt_analysis_invalidate(f, OPT_ANALYSIS_CFG | OPT_ANALYSIS_DEF_USE |
    220                                  OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP);
    221   return edge;
    222 }
    223 
    224 void opt_build_cfg(Func* f) {
    225   if (!f) return;
    226   opt_analysis_invalidate(
    227       f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP);
    228   for (u32 b = 0; b < f->nblocks; ++b) {
    229     f->blocks[b].preds = NULL;
    230     f->blocks[b].npreds = 0;
    231   }
    232 
    233   /* Trust the recorder's succ[] for terminators that don't have a fixed
    234    * succ count from the inst alone (IR_BR, IR_CONDBR, IR_CMP_BRANCH,
    235    * IR_BREAK_TO, IR_CONTINUE_TO). Only fix nsucc for ops where we can
    236    * read it directly from the op tag. */
    237   for (u32 b = 0; b < f->nblocks; ++b) {
    238     Block* bl = &f->blocks[b];
    239     if (bl->ninsts == 0) {
    240       /* Empty blocks are valid label-only blocks. Their fallthrough successor
    241        * is assigned by the lowering/layout pass and must survive CFG rebuilds
    242        * so branches to labels placed immediately before another block remain
    243        * connected. */
    244       continue;
    245     }
    246     const Inst* last = &bl->insts[bl->ninsts - 1];
    247     if (!is_terminator(last)) {
    248       u8 nsucc = 0;
    249       if (scope_control_succ_count(bl, last, &nsucc)) {
    250         bl->nsucc = nsucc;
    251         continue;
    252       }
    253       continue;
    254     }
    255     switch ((IROp)last->op) {
    256       case IR_RET:
    257         bl->nsucc = 0;
    258         break;
    259       case IR_UNREACHABLE:
    260         bl->nsucc = 0;
    261         break;
    262       case IR_INTRINSIC:
    263         bl->nsucc = 0;
    264         break;
    265       case IR_BR:
    266       case IR_BREAK_TO:
    267       case IR_CONTINUE_TO:
    268         bl->nsucc = 1;
    269         break;
    270       case IR_CONDBR:
    271       case IR_CMP_BRANCH:
    272         bl->nsucc = 2;
    273         break;
    274       case IR_SWITCH:
    275       case IR_INDIRECT_BRANCH:
    276         /* nsucc was set by the recorder at emit time; trust it. */
    277         break;
    278       default:
    279         break;
    280     }
    281   }
    282 
    283   u8* reachable = mark_reachable(f);
    284   prune_unreachable(f, reachable);
    285 
    286   /* Count predecessors. */
    287   u32* counts = arena_zarray(f->arena, u32, f->nblocks);
    288   for (u32 b = 0; b < f->nblocks; ++b) {
    289     Block* bl = &f->blocks[b];
    290     for (u32 s = 0; s < bl->nsucc; ++s) {
    291       u32 t = bl->succ[s];
    292       if (t < f->nblocks) counts[t]++;
    293     }
    294   }
    295   for (u32 b = 0; b < f->nblocks; ++b) {
    296     if (counts[b]) {
    297       f->blocks[b].preds = arena_array(f->arena, u32, counts[b]);
    298     }
    299   }
    300   for (u32 b = 0; b < f->nblocks; ++b) {
    301     Block* bl = &f->blocks[b];
    302     for (u32 s = 0; s < bl->nsucc; ++s) {
    303       u32 t = bl->succ[s];
    304       if (t >= f->nblocks) continue;
    305       f->blocks[t].preds[f->blocks[t].npreds++] = b;
    306     }
    307   }
    308   opt_analysis_mark_valid(f, OPT_ANALYSIS_CFG);
    309 }