Chris Fallin
940bc40fae
Redundant move eliminator.
2021-06-08 00:08:28 -07:00
Chris Fallin
c6bcd3c941
WIP: redundant-move elimination.
2021-06-07 21:15:32 -07:00
Chris Fallin
2be7bdbc22
Split-at-first-conflict: first conflict is first of (start of our range), (start of conflict range), not just the latter; otherwise we have a too-early split sometimes
2021-06-07 12:27:58 -07:00
Chris Fallin
0eaa0fde06
Fix to checker: analyze all blocks, even if out-state of entry block is empty
2021-06-05 14:47:55 -07:00
Chris Fallin
30f42a8717
Fix fuzzbug: properly detect too-many-live-regs condition on fuzzing input. Must be careful in how we probe the BTree when we have multiple "equal" (overlapping) keys.
2021-06-03 23:48:33 -07:00
Chris Fallin
5560499b80
Adaptive commitment-map scanning: re-probe from root if we skip too many entries in linear BTree scan
2021-06-03 18:17:28 -07:00
Chris Fallin
00e4240c93
merge bundles much faster by just concatenating range-lists and unstable-sorting, rather than a merge-sort-like traversal. Rust stdlib sort is very optimized. clang.wasm 9.1s -> 6.8s now.
2021-06-03 17:34:19 -07:00
Chris Fallin
6a0739b62a
Implement spill-bundle: move all empty ranges, and empty leading/trailing pieces surrounding split points, to a single spill bundle, in an attempt to avoid excessive movement
2021-06-03 00:18:27 -07:00
Chris Fallin
dc2b0d1913
Add a perf idea to TODO list
2021-06-01 23:13:08 -07:00
Chris Fallin
2fe276ca04
BTreeMap probe fix (fuzzbug): BTree does not interact nicely with LiveRangeKey definition of equality; need to probe with one-less-than start to get proper range
2021-06-01 23:10:34 -07:00
Chris Fallin
a2a770ec50
Fuzzbug fix
2021-06-01 18:57:07 -07:00
Chris Fallin
2614eac21e
fuzzbug fix: restore clean error exit required by regalloc.rs fuzzer on too-many-live-regs error
2021-06-01 16:31:33 -07:00
Chris Fallin
e49727dc75
Fuzzbug fix: fix some weirdness with BTree iteration inner loop
2021-06-01 15:32:12 -07:00
Chris Fallin
44ca1893c3
Fuzzbug fix: properly check for conflicting reqs before merging bundles (cached values are not computed yet)
2021-06-01 14:52:59 -07:00
Chris Fallin
f49167e0fe
emit annotations at Info level, for easier selective perf-debugging
2021-05-28 18:40:39 -07:00
Chris Fallin
789651f947
Rework inner allocation-loop code: choose more wisely between splitting and evicting based on costs (and unify the fixed-reg-constraint case)
2021-05-28 17:36:06 -07:00
Chris Fallin
43d7095cbd
Properly split when we hit a fixed conflict
2021-05-28 16:49:32 -07:00
Chris Fallin
7171624750
Don't generate r1->scratch,scratch-r1 sequence for cyclic moves of r1->r1 that are generated to change vreg ownership and keep the checker happy. Seems to eliminate a bit of braindeadness and improve bz2 by ~5-10%.
2021-05-26 21:35:43 -07:00
Chris Fallin
13bde99d7d
bugfix with clean-spill opt: avoid if liverange starts at start of block (this is like a def) or if has starts-at-def flag.
2021-05-26 18:08:41 -07:00
Chris Fallin
e521811b88
Avoid re-spilling to spillslot when still clean: intra-block edition (inter-block needs more analysis and careful thought)
2021-05-26 17:08:14 -07:00
Chris Fallin
dcf6f473ca
inline some things
2021-05-26 00:48:41 -07:00
Chris Fallin
4e0dd1f296
little tweak to avoid a div/mod on every iter of a PReg alloc loop
2021-05-26 00:38:53 -07:00
Chris Fallin
b3dc2b25a5
Alloc spillsets for whole vreg, not just spilled LRs. This is a prerequisite to allowing a "clean" value to remain in spillslot while also in reg and avoiding the re-spill. It should also reduce stack-to-stack moves (though they can still come from progmoves).
2021-05-25 18:19:25 -07:00
Chris Fallin
ca5f24f6b7
Hint the same PReg for both halves of a split
2021-05-24 23:49:47 -07:00
Chris Fallin
7cdcb2031e
Split heuristic: split before entering deeper loop nest
2021-05-24 23:09:05 -07:00
Chris Fallin
8887077b59
small fix: preserve starts-at-def flag when setting liverange weight
2021-05-24 22:45:25 -07:00
Chris Fallin
3382f9a2e8
Split based on first conflict of lowest-weight conflict, not first conflict. Also stop scanning PRegs when max bundle weight in conflict bundle list exceeds current best option.
2021-05-24 22:26:57 -07:00
Chris Fallin
5b47462e0c
Loop depth instead of hot/cold, with fast O(n) loop-depth computation. Use this to compute use weights.
2021-05-24 22:09:41 -07:00
Chris Fallin
5895ae8a2d
Remove precomputed requirements from ranges and bundles; cost of struct size and updates is not worth it. Instead, do a simple conflicting-requirements check on each attempted merge, but minimize cost by (i) only checking after ruling out overlaps, and (ii) only checking if we know one of the sides has at least one non-register constraint.
2021-05-24 21:32:41 -07:00
Chris Fallin
5120681730
Fuzzbug fix for requirement recomputation on minimal bundles with multiple LRs
2021-05-24 17:49:45 -07:00
Chris Fallin
10d926557a
avoid some redundant work by computing initial reqs only once
2021-05-24 15:52:14 -07:00
Chris Fallin
78c009181c
Fuzzbug fix re: new requirements computation and multi-fixed-reg fixup.
2021-05-24 15:47:15 -07:00
Chris Fallin
46feacc654
Fuzzbug fix: don't merge bundles that have conflicting requirements. (Normally splitting would fix this, but let's just not merge in the first place.)
2021-05-24 15:32:05 -07:00
Chris Fallin
59967ff756
TODO-list update: braindump of next ideas to work on.
2021-05-23 20:04:28 -07:00
Chris Fallin
107c09181f
Simple speedup in bundle merge: set bundle while everything is in cache (same pass), and only check non-overlap with debug assertions enabled. Alloc time on clang.wasm: 9.1s old backtracking RA vs. 7.2s with this regalloc2 RA.
2021-05-22 16:36:44 -07:00
Chris Fallin
a6c89b1c01
Avoid O(n^2) in liverange construction: we always build LRs in (reverse) order, so we can just append (prepend) to running list and reverse at end. Likewise for uses.
2021-05-22 15:12:35 -07:00
Chris Fallin
469669155f
Another fuzzbug fix: proper checker-hint ordering when V-R and V-V moves are back-to-back and RReg ownership changes
2021-05-22 14:37:56 -07:00
Chris Fallin
4b46c6388a
Fuzzbug fixes for simpler splitting
2021-05-22 14:26:49 -07:00
Chris Fallin
466ea2cd9a
Simpler / possibly better splitting: split based on conflict position, always, and use a reg hint to put the before-conflict part in the place where we determined it fit before.
2021-05-21 01:34:52 -07:00
Chris Fallin
ec7fdeb8ed
Properly handle RReg-RReg moves in new scheme
2021-05-20 20:38:50 -07:00
Chris Fallin
2a5f571b80
WIP: Handle moves between realregs (pregs) and vregs somewhat specially, by converting into operand constraints
...
Still has a fuzzbug in interaction between R->R and V->R moves. Will
likely rework to make pinned-vreg handling more general but want to save
a checkpoint here; idea for rework:
- set allocs immediately if an Operand is a pinned vreg;
- reserve preg ranges;
- then, in rest of liveness computation / LR construction, convert
pinned-vregs to operands with constraints, but otherwise do not
special-case as we do in this commit.
2021-05-20 19:53:19 -07:00
Chris Fallin
f0b24cf9fa
Remove all-empty-ranges-to-spill-bundle: prioritizing same-alloc for all empty ranges over allowing some to live in registers results in too much spilling
2021-05-20 10:21:22 -07:00
Chris Fallin
ce935c1040
Add all empty LRs to a single "spill bundle", to avoid many small bundles and excessive moves
2021-05-19 22:12:22 -07:00
Chris Fallin
f56676fb8d
Fixed all fuzzer targets (some API changes)
2021-05-19 18:25:34 -07:00
Chris Fallin
f1c6dfe807
Optionally show annotations in final allocation/program dump based on RegallocOptions flag
2021-05-19 16:36:36 -07:00
Chris Fallin
e1f67e860f
Pinned VRegs for use with regalloc.rs shim to support RealRegs.
2021-05-18 22:40:43 -07:00
Chris Fallin
04c8e46787
Only do annotations in debug builds
2021-05-18 18:52:34 -07:00
Chris Fallin
c3513b94b0
Bugfix: don't do a split-at-intermediate-defs split if the first such point is the start of the bundle.
2021-05-18 15:16:19 -07:00
Chris Fallin
4389f16156
debugging log message for liveins
2021-05-18 12:14:59 -07:00
Chris Fallin
8e0d0f1de0
fuzzbug fix
2021-05-18 00:26:38 -07:00
