ir.c (9405B)
1 /* ir.c — Func/Block/Inst plumbing for the optimizer IR (doc/OPT.md §1). 2 * 3 * Each CGTarget call recorded by opt_cgtarget produces exactly one Inst. 4 * Storage is per- 5 * Func arena, allocated against c->tu so the Func survives until 6 * cgtarget_finalize. 7 * 8 * Invariants: 9 * - VAL_NONE (= 0) is reserved; first allocated Val is 1. 10 * - val_def_block / val_def_inst / val_type / val_cls are parallel 11 * arrays indexed by Val. 12 * - preg_type / preg_cls are parallel arrays indexed by mutable CG virtual 13 * Reg id. Before opt_build_reg_ssa, OPK_REG operands name these pseudos. 14 */ 15 16 #include "opt/ir.h" 17 18 #include <string.h> 19 20 #include <kit/cg.h> 21 22 #include "core/arena.h" 23 #include "core/core.h" 24 25 /* Register class for a value of type `ty`. A float lands in an FP register only 26 * when the float ABI has a register that wide (flen); a soft float, or a float 27 * wider than flen (double under ilp32f/ilp32), is INT-class and carried in GPRs 28 * (a GPR pair for a 2-word double) like an integer of the same width, so it is 29 * never bit-cast through an FP register (illegal fmv.d.x on rv32). flen: 30 * SINGLE 4, DOUBLE 8, SOFT 0; DEFAULT maps to the pointer width, preserving 31 * lp64d / x86-64 / rv64 (double 8 <= 8 -> FP). EVERY value-class decision in 32 * the optimizer routes through here so they agree — the verifier cross-checks 33 * the SSA value class, param/local class, and physical-reg class against it. */ 34 u8 opt_value_reg_class(Compiler* c, KitCgTypeId ty) { 35 KitCompiler* pc = (KitCompiler*)c; 36 u32 flen; 37 if (kit_cg_type_kind(pc, ty) != KIT_CG_TYPE_FLOAT) return RC_INT; 38 switch (c->target.float_abi) { 39 case KIT_FLOAT_ABI_SINGLE: flen = 4u; break; 40 case KIT_FLOAT_ABI_DOUBLE: flen = 8u; break; 41 case KIT_FLOAT_ABI_SOFT: flen = 0u; break; 42 default: flen = c->target.ptr_size; break; /* DEFAULT: historical */ 43 } 44 return (flen && kit_cg_type_size(pc, ty) <= (uint64_t)flen) ? RC_FP : RC_INT; 45 } 46 47 /* ---- val table ---- */ 48 49 static void val_table_grow(Func* f, u32 needed) { 50 if (needed <= f->vals_cap) return; 51 u32 ncap = f->vals_cap ? f->vals_cap : 16u; 52 while (ncap < needed) ncap *= 2u; 53 u32* nb_blk = arena_zarray(f->arena, u32, ncap); 54 u32* nb_ins = arena_zarray(f->arena, u32, ncap); 55 KitCgTypeId* nb_ty = arena_zarray(f->arena, KitCgTypeId, ncap); 56 u8* nb_cls = arena_zarray(f->arena, u8, ncap); 57 if (f->nvals) { 58 memcpy(nb_blk, f->val_def_block, sizeof(u32) * f->nvals); 59 memcpy(nb_ins, f->val_def_inst, sizeof(u32) * f->nvals); 60 memcpy(nb_ty, f->val_type, sizeof(KitCgTypeId) * f->nvals); 61 memcpy(nb_cls, f->val_cls, sizeof(u8) * f->nvals); 62 } 63 f->val_def_block = nb_blk; 64 f->val_def_inst = nb_ins; 65 f->val_type = nb_ty; 66 f->val_cls = nb_cls; 67 f->vals_cap = ncap; 68 } 69 70 Val ir_alloc_val(Func* f, KitCgTypeId t, u8 cls) { 71 Val v; 72 if (f->nvals == 0) { 73 val_table_grow(f, 16); 74 f->nvals = 1; /* reserve slot 0 for VAL_NONE */ 75 } 76 if (f->nvals == f->vals_cap) val_table_grow(f, f->nvals + 1); 77 v = f->nvals++; 78 f->val_def_block[v] = 0; 79 f->val_def_inst[v] = 0; 80 f->val_type[v] = t; 81 f->val_cls[v] = cls; 82 return v; 83 } 84 85 void ir_ensure_val(Func* f, Val v, KitCgTypeId t, u8 cls) { 86 if (v == VAL_NONE) return; 87 if (f->nvals == 0) { 88 val_table_grow(f, 16); 89 f->nvals = 1; /* reserve slot 0 for VAL_NONE */ 90 } 91 if (v >= f->vals_cap) val_table_grow(f, v + 1u); 92 while (f->nvals <= v) { 93 f->val_def_block[f->nvals] = 0; 94 f->val_def_inst[f->nvals] = 0; 95 f->val_type[f->nvals] = 0; 96 f->val_cls[f->nvals] = RC_INT; 97 f->nvals++; 98 } 99 if (!f->val_type[v]) f->val_type[v] = t; 100 f->val_cls[v] = cls; 101 } 102 103 /* ---- mutable pseudo-register table ---- */ 104 105 static void preg_table_grow(Func* f, u32 needed) { 106 if (needed <= f->pregs_cap) return; 107 u32 ncap = f->pregs_cap ? f->pregs_cap : 16u; 108 while (ncap < needed) ncap *= 2u; 109 KitCgTypeId* nb_ty = arena_zarray(f->arena, KitCgTypeId, ncap); 110 u8* nb_cls = arena_zarray(f->arena, u8, ncap); 111 if (f->npregs) { 112 memcpy(nb_ty, f->preg_type, sizeof(KitCgTypeId) * f->npregs); 113 memcpy(nb_cls, f->preg_cls, sizeof(u8) * f->npregs); 114 } 115 f->preg_type = nb_ty; 116 f->preg_cls = nb_cls; 117 f->pregs_cap = ncap; 118 } 119 120 void ir_ensure_preg(Func* f, PReg r, KitCgTypeId t, u8 cls) { 121 if (r == PREG_NONE || r == 0) return; 122 if (f->npregs == 0) { 123 preg_table_grow(f, 16); 124 f->npregs = 1; 125 } 126 if (r >= f->pregs_cap) preg_table_grow(f, r + 1u); 127 while (f->npregs <= r) { 128 f->preg_type[f->npregs] = 0; 129 f->preg_cls[f->npregs] = RC_INT; 130 f->npregs++; 131 } 132 if (!f->preg_type[r]) f->preg_type[r] = t; 133 f->preg_cls[r] = cls; 134 } 135 136 PReg ir_alloc_preg(Func* f, KitCgTypeId t, u8 cls) { 137 if (f->npregs == 0) { 138 preg_table_grow(f, 16); 139 f->npregs = 1; 140 } 141 if (f->npregs == f->pregs_cap) preg_table_grow(f, f->npregs + 1u); 142 PReg r = (PReg)f->npregs; 143 ir_ensure_preg(f, r, t, cls); 144 return r; 145 } 146 147 /* ---- blocks ---- */ 148 149 u32 ir_block_new(Func* f) { 150 Block* b; 151 if (f->nblocks == f->blocks_cap) { 152 u32 ncap = f->blocks_cap ? f->blocks_cap * 2u : 8u; 153 Block* nb = arena_zarray(f->arena, Block, ncap); 154 if (f->blocks) memcpy(nb, f->blocks, sizeof(Block) * f->nblocks); 155 f->blocks = nb; 156 f->blocks_cap = ncap; 157 } 158 b = &f->blocks[f->nblocks]; 159 memset(b, 0, sizeof *b); 160 b->id = f->nblocks; 161 b->succ = arena_zarray(f->arena, u32, 2); 162 b->succ_cap = 2; 163 b->mc_label = MC_LABEL_NONE; 164 return f->nblocks++; 165 } 166 167 void ir_block_set_nsucc(Func* f, u32 block, u32 n) { 168 Block* bl; 169 if (block >= f->nblocks) return; 170 bl = &f->blocks[block]; 171 if (n > bl->succ_cap) { 172 u32* nb = arena_zarray(f->arena, u32, n); 173 if (bl->succ && bl->nsucc) memcpy(nb, bl->succ, sizeof(u32) * bl->nsucc); 174 bl->succ = nb; 175 bl->succ_cap = n; 176 } 177 bl->nsucc = n; 178 } 179 180 /* ---- emit order ---- */ 181 182 void ir_note_emit(Func* f, u32 block) { 183 /* Linear scan: emit_order is small in practice (one entry per 184 * placed block, dozens at most for the corpus) and we only ever 185 * append, so a hash table would be overkill. */ 186 for (u32 i = 0; i < f->emit_order_n; ++i) 187 if (f->emit_order[i] == block) return; 188 if (f->emit_order_n == f->emit_order_cap) { 189 u32 ncap = f->emit_order_cap ? f->emit_order_cap * 2u : 8u; 190 u32* nb = arena_array(f->arena, u32, ncap); 191 if (f->emit_order) memcpy(nb, f->emit_order, sizeof(u32) * f->emit_order_n); 192 f->emit_order = nb; 193 f->emit_order_cap = ncap; 194 } 195 f->emit_order[f->emit_order_n++] = block; 196 } 197 198 /* ---- inst append ---- */ 199 200 Inst* ir_emit(Func* f, u32 block, IROp op) { 201 Block* b = &f->blocks[block]; 202 Inst* in; 203 if (b->ninsts == b->cap) { 204 u32 ncap = b->cap ? b->cap * 2u : 8u; 205 Inst* nb = arena_zarray(f->arena, Inst, ncap); 206 if (b->insts) memcpy(nb, b->insts, sizeof(Inst) * b->ninsts); 207 b->insts = nb; 208 b->cap = ncap; 209 } 210 in = &b->insts[b->ninsts++]; 211 memset(in, 0, sizeof *in); 212 in->op = (u16)op; 213 ir_assign_inst_id(f, in); 214 return in; 215 } 216 217 InstId ir_inst_id_new(Func* f) { 218 if (!f->next_inst_id) f->next_inst_id = 1; 219 return f->next_inst_id++; 220 } 221 222 void ir_assign_inst_id(Func* f, Inst* in) { 223 if (!f || !in || in->id != INST_ID_NONE) return; 224 in->id = ir_inst_id_new(f); 225 } 226 227 /* ---- frame slots / params ---- */ 228 229 FrameSlot ir_frame_slot_new(Func* f, const FrameSlotDesc* d) { 230 IRFrameSlot* s; 231 FrameSlot id; 232 if (f->nframe_slots == f->frame_slots_cap) { 233 u32 ncap = f->frame_slots_cap ? f->frame_slots_cap * 2u : 8u; 234 IRFrameSlot* nb = arena_zarray(f->arena, IRFrameSlot, ncap); 235 if (f->frame_slots) 236 memcpy(nb, f->frame_slots, sizeof(IRFrameSlot) * f->nframe_slots); 237 f->frame_slots = nb; 238 f->frame_slots_cap = ncap; 239 } 240 id = (FrameSlot)(f->nframe_slots + 1); 241 s = &f->frame_slots[f->nframe_slots++]; 242 s->id = id; 243 s->type = d->type; 244 s->name = d->name; 245 s->loc = d->loc; 246 s->size = d->size; 247 s->align = d->align; 248 s->kind = d->kind; 249 s->flags = d->flags; 250 return id; 251 } 252 253 void ir_param_add(Func* f, const CGParamDesc* d) { 254 IRParam* p; 255 if (f->nparams == f->params_cap) { 256 u32 ncap = f->params_cap ? f->params_cap * 2u : 4u; 257 IRParam* nb = arena_zarray(f->arena, IRParam, ncap); 258 if (f->params) memcpy(nb, f->params, sizeof(IRParam) * f->nparams); 259 f->params = nb; 260 f->params_cap = ncap; 261 } 262 p = &f->params[f->nparams++]; 263 p->index = d->index; 264 p->name = d->name; 265 p->type = d->type; 266 p->size = d->size; 267 p->align = d->align; 268 p->flags = d->flags; 269 p->storage = d->storage; 270 p->abi = d->abi; 271 p->loc = d->loc; 272 } 273 274 u32 ir_local_add(Func* f, const CGLocalDesc* d, CGLocalStorage storage) { 275 IRLocal* l; 276 if (f->nlocals == f->locals_cap) { 277 u32 ncap = f->locals_cap ? f->locals_cap * 2u : 8u; 278 IRLocal* nb = arena_zarray(f->arena, IRLocal, ncap); 279 if (f->locals) memcpy(nb, f->locals, sizeof(IRLocal) * f->nlocals); 280 f->locals = nb; 281 f->locals_cap = ncap; 282 } 283 l = &f->locals[f->nlocals]; 284 l->id = f->nlocals + 1u; 285 l->desc = *d; 286 l->storage = storage; 287 ++f->nlocals; 288 return l->id; 289 } 290 291 /* ---- construction ---- */ 292 293 Func* ir_func_new(Compiler* c, const CGFuncDesc* desc) { 294 Func* f = arena_znew(c->tu, Func); 295 f->arena = c->tu; 296 f->c = c; 297 f->desc = *desc; 298 f->name = desc->sym; 299 f->type = desc->fn_type; 300 /* Reserve slot 0 of the val table eagerly so the very first ir_alloc_val 301 * returns Val=1. */ 302 val_table_grow(f, 16); 303 f->nvals = 1; 304 preg_table_grow(f, 16); 305 f->npregs = 1; 306 /* Caller is expected to ir_block_new(f) for entry, then assign 307 * f->entry. */ 308 return f; 309 }