commit a68bf13802fcf376e1f5331422e27e7457d37504
parent 2bca75d1fd472787b94d07a51196293622891597
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Thu, 21 May 2026 19:34:56 -0700
Optimize pressure relief pass
Diffstat:
4 files changed, 131 insertions(+), 17 deletions(-)
diff --git a/src/opt/ir.h b/src/opt/ir.h
@@ -468,6 +468,7 @@ typedef struct Func {
OptUse* opt_uses;
u32 opt_nuses, opt_uses_cap;
u32* opt_first_use_by_val; /* indexed by Val, OPT_USE_NONE if no uses */
+ u32 opt_first_use_by_val_cap;
u32 opt_valid_analyses;
Reg opt_hard_regs[OPT_REG_CLASSES][OPT_MAX_HARD_REGS];
diff --git a/src/opt/pass_analysis.c b/src/opt/pass_analysis.c
@@ -316,10 +316,16 @@ static void opt_collect_inst_uses(Func* f, u32 b, u32 i, Inst* in) {
}
void opt_rebuild_def_use(Func* f) {
+ u32 nheads;
if (!f) return;
f->opt_nuses = 0;
- f->opt_first_use_by_val =
- arena_array(f->arena, u32, f->nvals ? f->nvals : 1u);
+ nheads = f->nvals ? f->nvals : 1u;
+ if (nheads > f->opt_first_use_by_val_cap) {
+ u32 ncap = f->opt_first_use_by_val_cap ? f->opt_first_use_by_val_cap : 16u;
+ while (ncap < nheads) ncap *= 2u;
+ f->opt_first_use_by_val = arena_array(f->arena, u32, ncap);
+ f->opt_first_use_by_val_cap = ncap;
+ }
for (u32 v = 0; v < f->nvals; ++v) f->opt_first_use_by_val[v] = OPT_USE_NONE;
for (u32 b = 0; b < f->nblocks; ++b) {
Block* bl = &f->blocks[b];
diff --git a/src/opt/pass_o2.c b/src/opt/pass_o2.c
@@ -161,6 +161,18 @@ typedef struct LicmLoop {
u8* body;
} LicmLoop;
+typedef struct PressureBlockPlan {
+ u8* move_src;
+ u32* first_before;
+ u32* last_before;
+ u32* next_move;
+} PressureBlockPlan;
+
+typedef struct PressurePlan {
+ PressureBlockPlan* blocks;
+ u32 nmoves;
+} PressurePlan;
+
static u32 opt_inst_count(Func* f) {
u32 n = 0;
for (u32 b = 0; b < f->nblocks; ++b) n += f->blocks[b].ninsts;
@@ -2481,16 +2493,45 @@ static int pressure_can_move_within_block(Func* f, u32 b, u32 from, u32 to) {
return 1;
}
-static void pressure_move_before_use(Func* f, u32 b, u32 from, u32 use_inst) {
- Block* bl = &f->blocks[b];
- Inst moved = bl->insts[from];
- for (u32 i = from + 1u; i < use_inst; ++i) bl->insts[i - 1u] = bl->insts[i];
- bl->insts[use_inst - 1u] = moved;
- dse_refresh_def_locations(f);
+static PressureBlockPlan* pressure_block_plan(Func* f, PressurePlan* plan,
+ u32 b) {
+ if (!plan->blocks)
+ plan->blocks = arena_zarray(f->arena, PressureBlockPlan,
+ f->nblocks ? f->nblocks : 1u);
+ PressureBlockPlan* bp = &plan->blocks[b];
+ if (!bp->move_src) {
+ Block* bl = &f->blocks[b];
+ u32 n = bl->ninsts ? bl->ninsts : 1u;
+ bp->move_src = arena_zarray(f->arena, u8, n);
+ bp->first_before = arena_array(f->arena, u32, n);
+ bp->last_before = arena_array(f->arena, u32, n);
+ bp->next_move = arena_array(f->arena, u32, n);
+ for (u32 i = 0; i < n; ++i) {
+ bp->first_before[i] = OPT_BLOCK_NONE;
+ bp->last_before[i] = OPT_BLOCK_NONE;
+ bp->next_move[i] = OPT_BLOCK_NONE;
+ }
+ }
+ return bp;
}
-static int pressure_relief_once(Func* f) {
- opt_rebuild_def_use(f);
+static void pressure_plan_move(Func* f, PressurePlan* plan, u32 b, u32 from,
+ u32 to) {
+ PressureBlockPlan* bp = pressure_block_plan(f, plan, b);
+ if (bp->move_src[from]) return;
+ bp->move_src[from] = 1;
+ bp->next_move[from] = OPT_BLOCK_NONE;
+ if (bp->first_before[to] == OPT_BLOCK_NONE) {
+ bp->first_before[to] = from;
+ } else {
+ bp->next_move[bp->last_before[to]] = from;
+ }
+ bp->last_before[to] = from;
+ plan->nmoves++;
+}
+
+static int pressure_plan(Func* f, PressurePlan* plan) {
+ memset(plan, 0, sizeof *plan);
for (Val v = 1; v < f->nvals; ++v) {
u32 db = f->val_def_block[v];
u32 di = f->val_def_inst[v];
@@ -2506,11 +2547,40 @@ static int pressure_relief_once(Func* f) {
if (f->blocks[use.block].loop_depth > f->blocks[db].loop_depth) continue;
if (!pressure_can_move_within_block(f, db, di, use.inst)) continue;
- pressure_move_before_use(f, db, di, use.inst);
- opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
- return 1;
+ pressure_plan_move(f, plan, db, di, use.inst);
}
- return 0;
+ return plan->nmoves != 0;
+}
+
+static void pressure_apply_block(Func* f, u32 b, PressureBlockPlan* bp) {
+ Block* bl = &f->blocks[b];
+ Inst* old = bl->insts;
+ Inst* insts = arena_array(f->arena, Inst, bl->ninsts ? bl->ninsts : 1u);
+ u32 w = 0;
+ for (u32 i = 0; i < bl->ninsts; ++i) {
+ for (u32 m = bp->first_before[i]; m != OPT_BLOCK_NONE;
+ m = bp->next_move[m]) {
+ insts[w++] = old[m];
+ }
+ if (!bp->move_src[i]) insts[w++] = old[i];
+ }
+ bl->insts = insts;
+ bl->cap = bl->ninsts;
+ if (w != bl->ninsts) {
+ SrcLoc loc = {0, 0, 0};
+ compiler_panic(f->c, loc, "opt pressure-relief: bad rewrite (%u, %u)",
+ (unsigned)w, (unsigned)bl->ninsts);
+ }
+}
+
+static void pressure_apply(Func* f, PressurePlan* plan) {
+ if (!plan->blocks || !plan->nmoves) return;
+ for (u32 b = 0; b < f->nblocks; ++b) {
+ PressureBlockPlan* bp = &plan->blocks[b];
+ if (bp->move_src) pressure_apply_block(f, b, bp);
+ }
+ dse_refresh_def_locations(f);
+ opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
}
void opt_pressure_relief(Func* f) {
@@ -2520,9 +2590,9 @@ void opt_pressure_relief(Func* f) {
return;
}
- int changed = 0;
- while (pressure_relief_once(f)) changed = 1;
- if (changed) opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
+ PressurePlan plan;
+ opt_rebuild_def_use(f);
+ if (pressure_plan(f, &plan)) pressure_apply(f, &plan);
opt_rebuild_def_use(f);
}
diff --git a/test/opt/opt_test.c b/test/opt/opt_test.c
@@ -3803,6 +3803,42 @@ static void opt_pressure_relief_does_not_cross_memory_ops(void) {
tc_fini(&tc);
}
+static void opt_pressure_relief_sinks_many_immediates_in_one_pass(void) {
+ TestCtx tc;
+ tc_init(&tc);
+ Func* f = new_func(&tc);
+ Val x = add_val(f, tc.i32);
+ Val y = add_val(f, tc.i32);
+ Val imm[32];
+ Val out[32];
+ Val final;
+
+ emit_scalar_input(f, f->entry, x, tc.i32);
+ emit_scalar_input(f, f->entry, y, tc.i32);
+ for (u32 i = 0; i < 32; ++i) {
+ imm[i] = add_val(f, tc.i32);
+ emit_load_imm(f, f->entry, imm[i], tc.i32, (i64)i);
+ }
+ for (u32 i = 0; i < 32; ++i) {
+ out[i] = add_val(f, tc.i32);
+ emit_binop(f, f->entry, out[i], imm[i], x, tc.i32);
+ }
+ final = add_val(f, tc.i32);
+ emit_binop(f, f->entry, final, x, out[31], tc.i32);
+ emit_ret_val(f, f->entry, final, tc.i32);
+
+ opt_build_cfg(f);
+ opt_build_loop_tree(f);
+ opt_pressure_relief(f);
+ opt_verify(f, "test-pressure-many-sink");
+
+ for (u32 i = 0; i < 32; ++i) {
+ EXPECT(f->val_def_inst[imm[i]] + 1u == f->val_def_inst[out[i]],
+ "pressure relief should sink each immediate before its use");
+ }
+ tc_fini(&tc);
+}
+
static void opt_regalloc_priority(void) {
TestCtx tc;
tc_init(&tc);
@@ -5924,6 +5960,7 @@ int main(void) {
opt_pressure_relief_does_not_sink_into_loop();
opt_pressure_relief_preserves_multi_use_constant();
opt_pressure_relief_does_not_cross_memory_ops();
+ opt_pressure_relief_sinks_many_immediates_in_one_pass();
opt_liveness_branch();
opt_block_liveness_phase1();
opt_live_ranges_phase2();
