-
Notifications
You must be signed in to change notification settings - Fork 194
Expand file tree
/
Copy pathhigh_use_def_chains.txt
More file actions
46 lines (40 loc) · 2.44 KB
/
high_use_def_chains.txt
File metadata and controls
46 lines (40 loc) · 2.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
HIGH PRIORITY: Add use-def chains to the IR
Problem:
Every optimization pass independently scans all instructions to find uses of values.
DCE builds a HashSet<u32> by walking everything (collect_used_values, dce.rs:58-72).
Constant folding runs fixpoint loops that can never propagate constants to downstream
users because it only sees literal Operand::Const values, not "this Value was folded
to a constant". GVN replaces redundant instructions with Copy but cannot propagate
the replacement to users. Simplify cannot see that an operand was defined as zero
in a prior instruction.
The pipeline now runs 14 passes across 3 iterations, meaning each function
undergoes 30+ full instruction scans per compilation. Each scan walks every
block, every instruction, and pattern-matches all 28+ Instruction variants.
Current state (passes/mod.rs, run_passes):
14 passes (cfg_simplify, copy_prop, div_by_const, narrow, simplify,
constant_fold, gvn, licm, ivsr, if_convert, copy_prop, dce, cfg_simplify,
ipcp), iterated up to 3 times with dirty tracking and dependency-based
skip logic. Each pass takes &mut IrModule, returns usize count, no shared
state between passes.
What to do:
1. Add a UseDefInfo struct that maintains, for each Value:
- A list of instructions that use this value (use-chain)
- The instruction that defines this value (def-chain)
2. Build it once before the pass pipeline starts
3. Update it incrementally as passes mutate the IR (instruction replacement,
deletion, operand rewriting)
4. Replace collect_used_values in DCE with a use-count check (use_count == 0 => dead)
5. Enable constant folding to rewrite operands of downstream users when a value
is folded to a constant
6. Enable copy propagation (when %x = copy %y, replace all uses of %x with %y)
This is the single highest-leverage infrastructure improvement for the optimizer.
It turns O(passes * instructions) repeated scanning into O(1) per-value lookups,
and unlocks optimizations that are currently impossible (forward propagation of
constants and copies).
Key files:
- src/passes/dce.rs (collect_used_values, collect_instruction_uses: 110-line match)
- src/passes/constant_fold.rs (try_fold: cannot propagate, fixpoint is useless)
- src/passes/gvn.rs (replaces with Copy, cannot propagate to users)
- src/passes/simplify.rs (cannot see defining instruction of operands)
- src/passes/mod.rs (run_passes: no shared context between passes)
- src/ir/ir.rs (Instruction enum, Operand enum, Value type)