kit

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

opt.h (6662B)

      1 #ifndef KIT_OPT_H
      2 #define KIT_OPT_H
      3 
      4 #include "arch/mc.h"
      5 #include "arch/native_target.h"
      6 #include "cg/cgtarget.h" /* CgFinishPolicy + the CgTarget the optimizer lowers to */
      7 #include "cg/ir.h"
      8 #include "opt/ir.h"
      9 
     10 /* O1 input boundary: semantic cg/ir.h is recorded once, then lowered into the
     11  * optimizer-private Func/PReg view. During the O2 cutover window every
     12  * opt_level >= 1 is normalized internally to this O1 path. */
     13 CgTarget* opt_cgtarget_new(Compiler*, CgTarget* target, int level);
     14 Func* opt_func_from_cg_ir(Compiler*, const CgIrFunc*);
     15 void opt_set_finish_policy(CgTarget*, const CgFinishPolicy*);
     16 
     17 /* Interpreter tap: run the maximal target-independent subset of the O1 pipeline
     18  * (everything in opt_run_o1_native up to, but excluding, opt_machinize_native /
     19  * regalloc / MIR / native emit) and return the resulting Func for the threaded
     20  * bytecode interpreter to consume. At this point opt_reg_ssa==0, OPK_REG
     21  * operands carry virtual PReg ids, and there are no IR_PHI nodes. */
     22 Func* opt_run_o1_interp(Compiler*, const CgIrFunc*);
     23 
     24 /* ----- intra-procedural passes (run per retained Func at finalize on -O2)
     25  * ----- */
     26 void opt_build_cfg(Func*);
     27 typedef enum OptJumpCleanupStage {
     28   OPT_JUMP_CLEANUP_CFG,
     29   OPT_JUMP_CLEANUP_LAYOUT,
     30 } OptJumpCleanupStage;
     31 void opt_jump_cleanup(Func*, OptJumpCleanupStage);
     32 /* O1.md W9+W10: linear one-pass branch cleanup subset + constant cmp_branch
     33  * folding for the no-SSA O1 prepare path (rebuilds the CFG only if it changed
     34  * anything). */
     35 void opt_jump_cleanup_o1(Func*);
     36 void opt_block_cloning(Func*);
     37 void opt_build_reg_ssa(Func*);
     38 void opt_build_ssa(Func*);
     39 void opt_addr_xform(Func*);
     40 void opt_addr_xform_pregs(Func*); /* O1: PReg-namespace addr-of-local folding */
     41 void opt_promote_scalar_locals(Func*); /* O1: promote non-escaped scalar
     42                                           frame slots to mutable PRegs. */
     43 void opt_addr_of_global_cse(Func*);    /* O1: hoist duplicate ADDR_OF(global)
     44                                           defs to a single entry-block compute. */
     45 void opt_hoist_loop_consts(Func*);     /* O1: hoist loop-invariant LOAD_IMM
     46                                           materialization to the entry block. */
     47 void opt_lower_loop_imm_operands(
     48     Func*, NativeTarget*); /* O1: convert non-foldable inline imm operands in
     49                               loop bodies into IR_LOAD_IMM + reg uses so the
     50                               hoister can lift them. */
     51 void opt_simplify_local(Func*);
     52 void opt_simplify(Func*);
     53 void opt_gvn(Func*); /* incl. constprop, redundant-load elim */
     54 void opt_copy_cleanup(Func*);
     55 void opt_copy_prop(Func*); /* incl. redundant-extension elim */
     56 void opt_dse(Func*);       /* dead store elimination */
     57 void opt_ssa_dce(Func*);
     58 void opt_licm(Func*); /* requires loop tree built */
     59 void opt_pressure_relief(Func*);
     60 void opt_make_conventional_ssa(Func*);
     61 void opt_ssa_combine(Func*);
     62 void opt_undo_ssa(Func*);
     63 void opt_jump_opt(Func*);
     64 
     65 /* ----- lowering / backend prep (per Func, run before NativeTarget emission)
     66  * ----- */
     67 void opt_machinize_native(Func*, NativeTarget* target);
     68 /* Rebuild target-derived per-instruction fixed-register effects after an HIR
     69  * shape-changing pass. The O1 pipeline calls this at its final HIR boundary,
     70  * before liveness and allocation consume those effects. */
     71 void opt_refresh_machine_clobbers(Func*, NativeTarget* target);
     72 void opt_build_loop_tree(Func*);
     73 
     74 typedef struct OptBitset {
     75   Arena* arena;
     76   u64* words;
     77   u32 nwords;
     78   u32 active_words;
     79 } OptBitset;
     80 
     81 typedef struct OptBlockLive {
     82   OptBitset live_in;
     83   OptBitset live_out;
     84   OptBitset live_use;
     85   OptBitset live_def;
     86 } OptBlockLive;
     87 
     88 typedef struct OptLiveInfo {
     89   Arena* arena;
     90   Func* f;
     91   u32 words;
     92   u64 active_words;
     93   u64 block_bytes;
     94   u64 set_bit_scans;
     95   u64 bitset_words_touched;
     96   u64 dataflow_iterations;
     97   u64 dataflow_block_visits;
     98   OptBlockLive* blocks;
     99 } OptLiveInfo;
    100 
    101 #define OPT_RANGE_NONE ((u32)~0u)
    102 
    103 typedef struct OptLiveRange {
    104   PReg preg;
    105   u32 start;
    106   u32 end;
    107   u32 raw_start;
    108   u32 raw_end;
    109   u32 next;
    110   u32 block;
    111   u8 whole_block;
    112   u8 pad[3];
    113 } OptLiveRange;
    114 
    115 typedef struct OptLiveRangeSet {
    116   Arena* arena;
    117   Func* f;
    118   OptLiveRange* ranges;
    119   u32 nranges;
    120   u32 cap;
    121   u32* first_range_by_preg;
    122   u32* live_length_by_preg;
    123   u32* use_freq_by_preg;
    124   u32* def_freq_by_preg;
    125   u32* live_block_freq_by_preg;
    126   u32* live_across_call_freq_by_preg;
    127   u32* spill_cost_by_preg;
    128   u32 point_count;
    129   u32 raw_point_count;
    130   u32 max_ranges_per_preg;
    131   u32 max_live_length;
    132   u32 whole_block_spans;
    133   u64 range_point_visits;
    134   u64 preg_scans;
    135   u64 live_words_touched;
    136 } OptLiveRangeSet;
    137 
    138 typedef void (*OptBitsetIterFn)(PReg, void*);
    139 
    140 void opt_bitset_clear(OptBitset*);
    141 void opt_bitset_set(OptBitset*, PReg);
    142 void opt_bitset_clear_bit(OptBitset*, PReg);
    143 int opt_bitset_has(const OptBitset*, PReg);
    144 int opt_bitset_copy(OptBitset*, const OptBitset*);
    145 int opt_bitset_union(OptBitset*, const OptBitset*);
    146 int opt_bitset_union_and_not(OptBitset*, const OptBitset*, const OptBitset*);
    147 void opt_bitset_iter_set(const OptBitset*, OptBitsetIterFn, void* arg);
    148 
    149 void opt_live_blocks(Func*, OptLiveInfo*);
    150 void opt_live_dump_blocks(Func*, const OptLiveInfo*, Writer*);
    151 void opt_live_ranges_build(Func*, const OptLiveInfo*, OptLiveRangeSet*);
    152 void opt_live_dump_ranges(Func*, const OptLiveRangeSet*, Writer*);
    153 void opt_ir_dump(Func*, Writer*);
    154 void opt_ssa_dump(Func*, Writer*);
    155 void opt_rewrite_dump(Func*, Writer*);
    156 void opt_coalesce(Func*);
    157 void opt_regalloc_locations(Func*, OptLiveInfo* live_out);
    158 void opt_lower_to_mir(Func*, const OptLiveInfo*);
    159 void opt_mir_combine(Func*, NativeTarget* target);
    160 void opt_mir_dce(Func*);
    161 void opt_mir_jump_cleanup(Func*, OptJumpCleanupStage);
    162 void opt_mir_build_cfg(Func*);
    163 void opt_mir_verify(Func*, const char* stage);
    164 /* code selection: merge dependent insns. `target` (may be NULL) supplies the
    165  * immediate-legality oracle for the W6 cmp-imm / address-offset folds. */
    166 void opt_combine(Func*, NativeTarget* target);
    167 void opt_dce(Func*);           /* post-RA DCE */
    168 void opt_dead_def_elim(Func*); /* pre-RA dead-definition elimination */
    169 void opt_dead_def_elim_with_live(Func*, const OptLiveInfo*);
    170 
    171 /* Walks the lowered MIR and drives the physical native backend. */
    172 void opt_emit_native(Compiler*, Func*, NativeTarget* target);
    173 
    174 /* When set, the wrapper writes a textual dump of each function's recorded
    175  * tape to `w` on func_end, immediately before replay. Pass `w == NULL` to
    176  * disable. The format is line-oriented and stable enough for golden-file
    177  * diffs but otherwise unspecified. No-op if `t` is not an opt_cgtarget. */
    178 void opt_set_dump_writer(CgTarget* t, Writer* w);
    179 
    180 #endif