kit

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

pass_cfg.c (9439B)

      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 = (CgIrLocalStaticLabelAux*)in->extra.aux;
     82       if (aux) push_reachable(f, reachable, stack, sp, (u32)aux->target);
     83       break;
     84     }
     85     default:
     86       break;
     87   }
     88 }
     89 
     90 static u8* mark_reachable(Func* f) {
     91   u8* reachable = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u);
     92   if (f->entry >= f->nblocks) return reachable;
     93 
     94   u32* stack = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u);
     95   u32 sp = 0;
     96   push_reachable(f, reachable, stack, &sp, f->entry);
     97   while (sp) {
     98     u32 b = stack[--sp];
     99     if (b >= f->nblocks) continue;
    100     Block* bl = &f->blocks[b];
    101     for (u32 s = 0; s < bl->nsucc; ++s) {
    102       u32 t = bl->succ[s];
    103       push_reachable(f, reachable, stack, &sp, t);
    104     }
    105     for (u32 i = 0; i < bl->ninsts; ++i)
    106       mark_label_addr_targets_reachable(f, &bl->insts[i], reachable, stack,
    107                                         &sp);
    108   }
    109   return reachable;
    110 }
    111 
    112 static void prune_unreachable(Func* f, const u8* reachable) {
    113   for (u32 b = 0; b < f->nblocks; ++b) {
    114     if (reachable[b]) continue;
    115     Block* bl = &f->blocks[b];
    116     bl->insts = NULL;
    117     bl->ninsts = 0;
    118     bl->cap = 0;
    119     bl->preds = NULL;
    120     bl->npreds = 0;
    121     bl->nsucc = 0;
    122   }
    123 
    124   u32 w = 0;
    125   for (u32 i = 0; i < f->emit_order_n; ++i) {
    126     u32 b = f->emit_order[i];
    127     if (b < f->nblocks && reachable[b]) f->emit_order[w++] = b;
    128   }
    129   f->emit_order_n = w;
    130 }
    131 
    132 void opt_replace_succ_ref(Func* f, u32 pred, u32 old_succ, u32 new_succ) {
    133   if (!f || pred >= f->nblocks) return;
    134   Block* bl = &f->blocks[pred];
    135   for (u32 s = 0; s < bl->nsucc; ++s) {
    136     if (bl->succ[s] == old_succ) bl->succ[s] = new_succ;
    137   }
    138   if (!bl->ninsts) return;
    139   Inst* term = &bl->insts[bl->ninsts - 1u];
    140   if ((IROp)term->op == IR_SWITCH) {
    141     IRSwitchAux* aux = (IRSwitchAux*)term->extra.aux;
    142     if (!aux) return;
    143     for (u32 i = 0; i < aux->ncases; ++i)
    144       if (aux->cases[i].block == old_succ) aux->cases[i].block = new_succ;
    145     if (aux->default_block == old_succ) aux->default_block = new_succ;
    146   } else if ((IROp)term->op == IR_INDIRECT_BRANCH) {
    147     IRIndirectAux* aux = (IRIndirectAux*)term->extra.aux;
    148     if (!aux) return;
    149     for (u32 i = 0; i < aux->ntargets; ++i)
    150       if (aux->targets[i] == old_succ) aux->targets[i] = new_succ;
    151   }
    152 }
    153 
    154 void opt_emit_order_insert_after(Func* f, u32 after, u32 block) {
    155   if (!f) return;
    156   for (u32 i = 0; i < f->emit_order_n; ++i)
    157     if (f->emit_order[i] == block) return;
    158   if (f->emit_order_n == f->emit_order_cap) {
    159     u32 ncap = f->emit_order_cap ? f->emit_order_cap * 2u : 8u;
    160     u32* order = arena_array(f->arena, u32, ncap);
    161     if (f->emit_order)
    162       memcpy(order, f->emit_order, sizeof(order[0]) * f->emit_order_n);
    163     f->emit_order = order;
    164     f->emit_order_cap = ncap;
    165   }
    166   u32 pos = f->emit_order_n;
    167   for (u32 i = 0; i < f->emit_order_n; ++i) {
    168     if (f->emit_order[i] == after) {
    169       pos = i + 1u;
    170       break;
    171     }
    172   }
    173   for (u32 i = f->emit_order_n; i > pos; --i)
    174     f->emit_order[i] = f->emit_order[i - 1u];
    175   f->emit_order[pos] = block;
    176   ++f->emit_order_n;
    177 }
    178 
    179 int opt_edge_is_fallthrough(Func* f, u32 pred, u32 succ) {
    180   if (!f || pred >= f->nblocks) return 0;
    181   Block* bl = &f->blocks[pred];
    182   if (!bl->ninsts) return 0;
    183   IROp op = (IROp)bl->insts[bl->ninsts - 1u].op;
    184   if (op != IR_CMP_BRANCH && op != IR_CONDBR) return 0;
    185   return bl->nsucc >= 2 && bl->succ[1] == succ;
    186 }
    187 
    188 u32 opt_split_edge(Func* f, u32 pred, u32 succ) {
    189   if (!f) return 0;
    190   u32 edge = ir_block_new(f);
    191   Block* eb = &f->blocks[edge];
    192   Inst* br = ir_emit(f, edge, IR_BR);
    193   (void)br;
    194   eb->succ[0] = succ;
    195   eb->nsucc = 1;
    196   int place_after = opt_edge_is_fallthrough(f, pred, succ);
    197   opt_replace_succ_ref(f, pred, succ, edge);
    198   if (succ < f->nblocks) {
    199     Block* sb = &f->blocks[succ];
    200     for (u32 i = 0; i < sb->ninsts; ++i) {
    201       Inst* phi = &sb->insts[i];
    202       if ((IROp)phi->op != IR_PHI) break;
    203       IRPhiAux* aux = (IRPhiAux*)phi->extra.aux;
    204       if (!aux) continue;
    205       for (u32 p = 0; p < aux->npreds; ++p) {
    206         if (aux->pred_blocks[p] == pred) {
    207           aux->pred_blocks[p] = edge;
    208           aux->pred_vals[p] = phi->def;
    209         }
    210       }
    211     }
    212   }
    213   if (place_after) {
    214     opt_emit_order_insert_after(f, pred, edge);
    215   } else {
    216     ir_note_emit(f, edge);
    217   }
    218   opt_analysis_invalidate(
    219       f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP);
    220   return edge;
    221 }
    222 
    223 void opt_build_cfg(Func* f) {
    224   if (!f) return;
    225   opt_analysis_invalidate(
    226       f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP);
    227   for (u32 b = 0; b < f->nblocks; ++b) {
    228     f->blocks[b].preds = NULL;
    229     f->blocks[b].npreds = 0;
    230   }
    231 
    232   /* Trust the recorder's succ[] for terminators that don't have a fixed
    233    * succ count from the inst alone (IR_BR, IR_CONDBR, IR_CMP_BRANCH,
    234    * IR_BREAK_TO, IR_CONTINUE_TO). Only fix nsucc for ops where we can
    235    * read it directly from the op tag. */
    236   for (u32 b = 0; b < f->nblocks; ++b) {
    237     Block* bl = &f->blocks[b];
    238     if (bl->ninsts == 0) {
    239       /* Empty blocks are valid label-only blocks. Their fallthrough successor
    240        * is assigned by the lowering/layout pass and must survive CFG rebuilds
    241        * so branches to labels placed immediately before another block remain
    242        * connected. */
    243       continue;
    244     }
    245     const Inst* last = &bl->insts[bl->ninsts - 1];
    246     if (!is_terminator(last)) {
    247       u8 nsucc = 0;
    248       if (scope_control_succ_count(bl, last, &nsucc)) {
    249         bl->nsucc = nsucc;
    250         continue;
    251       }
    252       continue;
    253     }
    254     switch ((IROp)last->op) {
    255       case IR_RET:
    256         bl->nsucc = 0;
    257         break;
    258       case IR_UNREACHABLE:
    259         bl->nsucc = 0;
    260         break;
    261       case IR_INTRINSIC:
    262         bl->nsucc = 0;
    263         break;
    264       case IR_BR:
    265       case IR_BREAK_TO:
    266       case IR_CONTINUE_TO:
    267         bl->nsucc = 1;
    268         break;
    269       case IR_CONDBR:
    270       case IR_CMP_BRANCH:
    271         bl->nsucc = 2;
    272         break;
    273       case IR_SWITCH:
    274       case IR_INDIRECT_BRANCH:
    275         /* nsucc was set by the recorder at emit time; trust it. */
    276         break;
    277       default:
    278         break;
    279     }
    280   }
    281 
    282   u8* reachable = mark_reachable(f);
    283   prune_unreachable(f, reachable);
    284 
    285   /* Count predecessors. */
    286   u32* counts = arena_zarray(f->arena, u32, f->nblocks);
    287   for (u32 b = 0; b < f->nblocks; ++b) {
    288     Block* bl = &f->blocks[b];
    289     for (u32 s = 0; s < bl->nsucc; ++s) {
    290       u32 t = bl->succ[s];
    291       if (t < f->nblocks) counts[t]++;
    292     }
    293   }
    294   for (u32 b = 0; b < f->nblocks; ++b) {
    295     if (counts[b]) {
    296       f->blocks[b].preds = arena_array(f->arena, u32, counts[b]);
    297     }
    298   }
    299   for (u32 b = 0; b < f->nblocks; ++b) {
    300     Block* bl = &f->blocks[b];
    301     for (u32 s = 0; s < bl->nsucc; ++s) {
    302       u32 t = bl->succ[s];
    303       if (t >= f->nblocks) continue;
    304       f->blocks[t].preds[f->blocks[t].npreds++] = b;
    305     }
    306   }
    307 }