radiance · commit

Fuse `liveIn` computation for efficiency

ebab48233ba31cd9f6d83f0dcdd47c7ea527c6ff82bde6d17e5debe918f677e5

Alexis Sellier committed 1 month ago 1 parent 0e8a1cce

lib/std/lang/gen/regalloc/liveness.rad +21 -7


            if not bitset::eq(&liveOut[b], &scratch) {
                bitset::copy(&mut liveOut[b], &scratch);
                changed = true;
            }
            // Compute new liveIn = uses | (liveOut - defs)
            bitset::copy(&mut scratch, &liveOut[b]);
            bitset::subtract(&mut scratch, &defs[b]);
            bitset::union_(&mut scratch, &uses[b]);

            if not bitset::eq(&liveIn[b], &scratch) {
                bitset::copy(&mut liveIn[b], &scratch);
            if computeAndUpdateLiveIn(&mut liveIn[b], &liveOut[b], &defs[b], &uses[b]) {
                changed = true;
            }
        }
    }
    return LiveInfo { liveIn, liveOut, defs, uses, blockCount, maxReg };
}

/// Compute `liveIn = uses | (liveOut - defs)` and update `dst`.
/// Returns `true` if `dst` changed. Combined loop avoids multiple passes.
fn computeAndUpdateLiveIn(
    dst: *mut bitset::Bitset,
    liveOut: *bitset::Bitset,
    defs: *bitset::Bitset,
    uses: *bitset::Bitset
) -> bool {
    let numWords = bitset::wordsFor(dst.len);
    let mut changed = false;
    for i in 0..numWords {
        let newWord = uses.bits[i] | (liveOut.bits[i] & ~defs.bits[i]);
        if dst.bits[i] != newWord {
            dst.bits[i] = newWord;
            changed = true;
        }
    }
    return changed;
}

/// Compute local defs and uses for a single block.
fn computeLocalDefsUses(block: *il::Block, defs: *mut bitset::Bitset, uses: *mut bitset::Bitset) {
    for p in block.params {
        bitset::set(defs, p.value.n);
    }

130	130
131	131		if not bitset::eq(&liveOut[b], &scratch) {
132	132		bitset::copy(&mut liveOut[b], &scratch);
133	133		changed = true;
134	134		}
135		-	// Compute new liveIn = uses \| (liveOut - defs)
136		-	bitset::copy(&mut scratch, &liveOut[b]);
137		-	bitset::subtract(&mut scratch, &defs[b]);
138		-	bitset::union_(&mut scratch, &uses[b]);
139		-
140		-	if not bitset::eq(&liveIn[b], &scratch) {
141		-	bitset::copy(&mut liveIn[b], &scratch);
	135	+	if computeAndUpdateLiveIn(&mut liveIn[b], &liveOut[b], &defs[b], &uses[b]) {
142	136		changed = true;
143	137		}
144	138		}
145	139		}
146	140		return LiveInfo { liveIn, liveOut, defs, uses, blockCount, maxReg };
147	141		}
148	142
	143	+	/// Compute `liveIn = uses \| (liveOut - defs)` and update `dst`.
	144	+	/// Returns `true` if `dst` changed. Combined loop avoids multiple passes.
	145	+	fn computeAndUpdateLiveIn(
	146	+	dst: *mut bitset::Bitset,
	147	+	liveOut: *bitset::Bitset,
	148	+	defs: *bitset::Bitset,
	149	+	uses: *bitset::Bitset
	150	+	) -> bool {
	151	+	let numWords = bitset::wordsFor(dst.len);
	152	+	let mut changed = false;
	153	+	for i in 0..numWords {
	154	+	let newWord = uses.bits[i] \| (liveOut.bits[i] & ~defs.bits[i]);
	155	+	if dst.bits[i] != newWord {
	156	+	dst.bits[i] = newWord;
	157	+	changed = true;
	158	+	}
	159	+	}
	160	+	return changed;
	161	+	}
	162	+
149	163		/// Compute local defs and uses for a single block.
150	164		fn computeLocalDefsUses(block: il::Block, defs: mut bitset::Bitset, uses: *mut bitset::Bitset) {
151	165		for p in block.params {
152	166		bitset::set(defs, p.value.n);
153	167		}