kit

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

opt_internal.h (10048B)

      1 #ifndef KIT_OPT_INTERNAL_H
      2 #define KIT_OPT_INTERNAL_H
      3 
      4 #include "opt/opt.h"
      5 
      6 #define OPT_USE_NONE 0xffffffffu
      7 
      8 typedef struct OptHardRegSet {
      9   u32 cls[OPT_REG_CLASSES];
     10 } OptHardRegSet;
     11 
     12 /* Mask-only physical-register effects for consumers that do not need use
     13  * multiplicity. Keep this separate from OptRegEffects so hot liveness and
     14  * native-emission paths never clear or update the detailed 3x32 count table. */
     15 typedef struct OptRegEffectMasks {
     16   OptHardRegSet uses;
     17   OptHardRegSet defs;
     18   OptHardRegSet clobbers;
     19 } OptRegEffectMasks;
     20 
     21 /* Canonical physical-register effects of one instruction. `uses` and `defs`
     22  * are the registers named by the instruction/ABI operands; `clobbers` are
     23  * implicit kills (call ABI, inline asm, and target machine constraints).
     24  * Emission temporaries are private to native emission and never appear here.
     25  * Keeping defs separate from clobbers matters to DCE: an implicit kill is not
     26  * a produced value. */
     27 typedef struct OptRegEffects {
     28   union {
     29     OptRegEffectMasks masks;
     30     struct {
     31       OptHardRegSet uses;
     32       OptHardRegSet defs;
     33       OptHardRegSet clobbers;
     34     };
     35   };
     36   /* Per-register explicit-use multiplicity, saturated at two. This keeps
     37    * combine's single-use decisions in the same canonical operand model (and
     38    * preserves the double-reference case `[r + r*scale]`). */
     39   u8 use_count[OPT_REG_CLASSES][OPT_MAX_HARD_REGS];
     40 } OptRegEffects;
     41 
     42 typedef struct OptHardBlockLive {
     43   OptHardRegSet live_in;
     44   OptHardRegSet live_out;
     45   OptHardRegSet live_use;
     46   OptHardRegSet live_def;
     47 } OptHardBlockLive;
     48 
     49 typedef struct FuncSet FuncSet;
     50 struct FuncSet {
     51   Compiler* c;
     52   Arena* arena;
     53   Func** funcs;
     54   u32 nfuncs;
     55   u32 cap;
     56   /* Opaque InlineIndex* (pass_inline.c): a symbol->index map plus per-function
     57    * SCC ids, built once by opt_inline so callee resolution and the
     58    * recursion/SCC gate are O(1) instead of linear scans over `funcs`. NULL for
     59    * the ad-hoc 2-element sets the streaming tiny-inliner builds, which fall back
     60    * to the direct linear scan / reachability DFS. */
     61   void* index;
     62 };
     63 
     64 typedef struct OptBlockList {
     65   u32* items;
     66   u32 n;
     67   u32 cap;
     68 } OptBlockList;
     69 
     70 typedef struct OptAnalysis {
     71   Arena* arena;
     72   Func* f;
     73   u32 nblocks;
     74   u32 entry;
     75   u32* po;
     76   u32* rpo;
     77   u32* po_index;
     78   u8* reachable;
     79   u32 npo;
     80   u32 nrpo;
     81   u32* idom;
     82   OptBlockList* dom_children;
     83   OptBlockList* dom_frontier;
     84 } OptAnalysis;
     85 
     86 typedef enum OptAnalysisFlag {
     87   /* OPT_ANALYSIS_CFG was tracked but never queried (opt_build_cfg always
     88    * rebuilt unconditionally), so the bit and its maintenance were removed.
     89    * Values stay stable to keep any persisted masks unambiguous. */
     90   OPT_ANALYSIS_DEF_USE = 1u << 1,
     91   OPT_ANALYSIS_DOM = 1u << 2,
     92   OPT_ANALYSIS_LOOP = 1u << 3,
     93 } OptAnalysisFlag;
     94 
     95 typedef void (*OptOperandWalkFn)(Func*, Inst*, Operand*, int is_def, void*);
     96 
     97 static inline u32 opt_reg_count(const Func* f) {
     98   if (!f) return 0;
     99   if (f->opt_reg_ssa) return f->nvals;
    100   /* Real recorded O1 functions have npregs > 1. The nvals fallback keeps
    101    * standalone pass tests that hand-build Val-shaped IR working without
    102    * making ir_ensure_preg grow the Val table. */
    103   return f->npregs > 1 ? f->npregs : f->nvals;
    104 }
    105 
    106 static inline int opt_reg_valid(const Func* f, PReg r) {
    107   return r != PREG_NONE && r != 0 && r < opt_reg_count(f);
    108 }
    109 
    110 static inline KitCgTypeId opt_reg_type(const Func* f, PReg r) {
    111   if (!opt_reg_valid(f, r)) return 0;
    112   if (f->opt_reg_ssa || f->npregs <= 1) return f->val_type[(Val)r];
    113   return f->preg_type[r];
    114 }
    115 
    116 static inline u8 opt_reg_cls(const Func* f, PReg r) {
    117   if (!opt_reg_valid(f, r)) return RC_INT;
    118   if (f->opt_reg_ssa || f->npregs <= 1) return f->val_cls[(Val)r];
    119   return f->preg_cls[r];
    120 }
    121 
    122 static inline const OptLoc* opt_preg_loc(const Func* f, PReg r) {
    123   if (!f || !f->preg_locs || !opt_reg_valid(f, r)) return NULL;
    124   return &f->preg_locs[r];
    125 }
    126 
    127 static inline u8 opt_preg_alloc_kind(const Func* f, PReg r) {
    128   const OptLoc* loc = opt_preg_loc(f, r);
    129   if (loc) {
    130     switch ((OptLocKind)loc->kind) {
    131       case OPT_LOC_HARD:
    132         return OPT_ALLOC_HARD;
    133       case OPT_LOC_STACK:
    134         return OPT_ALLOC_SPILL;
    135       case OPT_LOC_NONE:
    136       default:
    137         break;
    138     }
    139   }
    140   if (!f || !f->preg_info || !opt_reg_valid(f, r)) return OPT_ALLOC_NONE;
    141   return f->preg_info[r].alloc_kind;
    142 }
    143 
    144 static inline u8 opt_preg_loc_cls(const Func* f, PReg r) {
    145   const OptLoc* loc = opt_preg_loc(f, r);
    146   if (loc && loc->kind != OPT_LOC_NONE) return loc->cls;
    147   if (f && f->preg_info && opt_reg_valid(f, r)) return f->preg_info[r].cls;
    148   return opt_reg_cls(f, r);
    149 }
    150 
    151 static inline Reg opt_preg_hard_reg(const Func* f, PReg r) {
    152   const OptLoc* loc = opt_preg_loc(f, r);
    153   if (loc && loc->kind == OPT_LOC_HARD) return loc->hard_reg;
    154   if (f && f->preg_info && opt_reg_valid(f, r)) return f->preg_info[r].hard_reg;
    155   return REG_NONE;
    156 }
    157 
    158 static inline FrameSlot opt_preg_spill_slot(const Func* f, PReg r) {
    159   const OptLoc* loc = opt_preg_loc(f, r);
    160   if (loc && loc->kind == OPT_LOC_STACK) return loc->spill_slot;
    161   if (f && f->preg_info && opt_reg_valid(f, r))
    162     return f->preg_info[r].spill_slot;
    163   return FRAME_SLOT_NONE;
    164 }
    165 
    166 void opt_analysis_mark_valid(Func*, u32 flags);
    167 void opt_analysis_invalidate(Func*, u32 flags);
    168 int opt_analysis_has(Func*, u32 flags);
    169 void opt_analysis_build_order(Func*, OptAnalysis*);
    170 void opt_analysis_build_dominators(Func*, OptAnalysis*);
    171 void opt_analysis_build_dom_frontier(Func*, OptAnalysis*);
    172 int opt_analysis_dominates(const OptAnalysis*, u32 dom, u32 node);
    173 void opt_rebuild_def_use(Func*);
    174 void opt_verify(Func*, const char* stage);
    175 void opt_replace_succ_ref(Func*, u32 pred, u32 old_succ, u32 new_succ);
    176 void opt_emit_order_insert_after(Func*, u32 after, u32 block);
    177 int opt_edge_is_fallthrough(Func*, u32 pred, u32 succ);
    178 u32 opt_split_edge(Func*, u32 pred, u32 succ);
    179 
    180 int opt_val_in_inst_defs(const Inst*, Val);
    181 /* One authority for the scalar types which may occupy an indirect index.
    182  * Address synthesis and MIR verification must agree on this boundary. */
    183 int opt_indirect_index_type_valid(Func*, KitCgTypeId);
    184 /* Canonical role of a direct instruction operand. Unlike legacy def-id
    185  * inference, this remains valid after PRegs have been rewritten to physical
    186  * registers or frame locations. Aux operands are classified by the central
    187  * walker below. */
    188 int opt_inst_operand_is_def(const Inst*, u32 index);
    189 void opt_walk_operand(Func*, Inst*, Operand*, int is_def, OptOperandWalkFn,
    190                       void*);
    191 void opt_walk_abivalue(Func*, Inst*, CGABIValue*, int storage_def,
    192                        OptOperandWalkFn, void*);
    193 void opt_walk_inst_operands(Func*, Inst*, OptOperandWalkFn, void*);
    194 
    195 /* Build the structural view used while rewriting HIR into MIR.  Block/CFG and
    196  * function-wide mutable storage is independent, but instruction arrays remain
    197  * read-only HIR borrows until rewrite_func replaces every one. */
    198 void opt_mir_prepare_rewrite(Func* dst, const Func* src);
    199 /* Deep-copy one instruction into MIR-owned storage. */
    200 void opt_mir_clone_inst(Arena* arena, Inst* dst, const Inst* src);
    201 
    202 /* Present the independently owned MIR graph through the ordinary Func pass
    203  * interface.  The view deliberately drops HIR pointer-based analyses; callers
    204  * must rebuild any analysis they need over MIR.  Passes which may replace graph
    205  * storage commit those fields, plus any extended instruction-id namespace,
    206  * back through opt_mir_commit. */
    207 int opt_mir_view(Func* f, Func* out);
    208 void opt_mir_commit(Func* f, const Func* view);
    209 
    210 /* Make room for k new instructions starting at index `at` in block `bl`.
    211  * Returns a pointer to the first new slot (zero-initialized). Grows the
    212  * block's inst array (doubling) as needed. */
    213 Inst* opt_block_insert_at(Func*, Block* bl, u32 at, u32 k);
    214 
    215 int opt_mem_observable(const MemAccess*);
    216 u32 opt_call_clobber_mask_for(Func*, const Inst*, u8 cls);
    217 const u32* opt_inst_machine_clobber_masks(Func*, const Inst*);
    218 
    219 int opt_inst_has_side_effect(Func*, const Inst*);
    220 
    221 /* Inlining. opt_inline is the whole-program driver (FuncSet over all retained
    222  * funcs). opt_try_tiny_inline is the streaming O1 entry: it inlines tiny
    223  * direct callees into one caller, resolving callee bodies through `lookup`
    224  * (returns a fresh pre-machinize Func for a symbol, or NULL to skip). Returns
    225  * the number of call sites inlined. */
    226 typedef Func* (*OptInlineCalleeLookup)(void* ctx, ObjSymId callee_sym);
    227 int opt_try_tiny_inline(Func* caller, OptInlineCalleeLookup lookup, void* ctx);
    228 void opt_inline(FuncSet*, int max_iters);
    229 
    230 int opt_hard_empty(const OptHardRegSet*);
    231 int opt_hard_intersects(const OptHardRegSet*, const OptHardRegSet*);
    232 void opt_hard_live_step(OptHardRegSet* live, const OptHardRegSet* use,
    233                         const OptHardRegSet* def);
    234 void opt_inst_reg_effects(Func*, const Inst*, OptRegEffects*);
    235 void opt_reg_effect_kills(const OptRegEffects*, OptHardRegSet*);
    236 void opt_inst_reg_effect_masks(Func*, const Inst*, OptRegEffectMasks*);
    237 void opt_reg_effect_mask_kills(const OptRegEffectMasks*, OptHardRegSet*);
    238 void opt_inst_reg_kills(Func*, const Inst*, OptHardRegSet*);
    239 OptHardBlockLive* opt_maybe_build_hard_live(Func*);
    240 OptHardRegSet opt_hard_live_out_for_block(const OptHardBlockLive*);
    241 int opt_block_live_out_has_phys_reg(Func*, const OptHardBlockLive*, u32 block,
    242                                     const Operand*);
    243 void opt_coalesce_ranges(Func*, const OptLiveRangeSet*);
    244 /* Linear (no O(n^2) conflict matrix) move coalescer for the no-SSA O1 regalloc
    245  * path. Populates f->opt_coalesce_parent before opt_assign_ranges and sets
    246  * f->opt_o1_coalescing. */
    247 void opt_coalesce_linear(Func*, const OptLiveRangeSet*);
    248 /* Return 0 (no overlap), 1 (a single unit-length overlap), or 2 (real
    249  * conflict: an overlap longer than one point, or two or more disjoint
    250  * unit-length overlaps). A unit overlap is the safe swap-friendly case
    251  * where one PReg dies exactly where another is born (`dst = op(... src ...)`
    252  * with dst placed in src's reg). */
    253 int opt_ranges_overlap_kind(const OptLiveRangeSet*, PReg a, PReg b);
    254 
    255 #endif