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