compiler: Own block predecessor lists

a9e072134e573e0a712b70354cd27c8db4169e2dc35307d5a2a2f268c718af37
Alexis Sellier committed ago 1 parent 65bd5c22
lib/std/lang/lower.rad +22 -16
525 525
/// - A block is "open" if it has no terminator; instructions can be added.
526 526
/// - A block is "sealed" when all predecessor edges are known.
527 527
/// - Sealing resolves the predecessor arguments for block parameters.
528 528
///
529 529
/// This differs from the final [`il::Block`] which is immutable and fully formed.
530 -
record BlockData: Copy {
530 +
record BlockData {
531 531
    /// Block label for debugging and IL printing.
532 532
    label: *[u8],
533 533
    /// Block parameters for merging values at control flow joins. These
534 534
    /// receive values from predecessor edges when control flow merges.
535 535
    params: *unsafe mut [il::Param],
542 542
    /// Debug source locations, one per instruction. Only populated when
543 543
    /// debug info is enabled.
544 544
    locs: *unsafe mut [il::SrcLoc],
545 545
    /// Predecessor block ids. Used for SSA construction to propagate values
546 546
    /// from predecessors when a variable is used before being defined locally.
547 -
    preds: *unsafe mut [u32],
547 +
    preds: *mut [u32],
548 548
    /// The current SSA value of each variable in this block. Indexed by variable
549 549
    /// id. A `nil` means the variable wasn't assigned in this block. Updated by
550 550
    /// [`defVar`], queried by [`useVarInBlock`].
551 551
    vars: *unsafe mut [?il::Val],
552 552
    /// Sealing state. Once sealed, all predecessors are known and we can resolve
2232 2232
unsafe fn switchToAndSeal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
2233 2233
    try sealBlock(self, block);
2234 2234
    switchToBlock(self, block);
2235 2235
}
2236 2236
2237 -
/// Get a snapshot of a block's descriptors by block id.
2238 -
fn getBlock(blocks: &[BlockData], block: BlockId) -> BlockData {
2239 -
    return blocks[*block];
2237 +
/// Get the number of predecessors for a block.
2238 +
fn predecessorCount(blocks: &[BlockData], block: BlockId) -> u32 {
2239 +
    return blocks[*block].preds.len;
2240 2240
}
2241 2241
2242 2242
/// Get mutable block data by block id.
2243 2243
unsafe fn getBlockMut 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId) -> *unsafe mut BlockData where 'arena: 'phase, 'phase: 'function {
2244 2244
    return &mut self.blockData[*block];
2751 2751
//////////////////////////////////
2752 2752
2753 2753
/// Add a predecessor edge from `pred` to `target`.
2754 2754
/// Must be called before the target block is sealed. Duplicates are ignored.
2755 2755
unsafe fn addPredecessor 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, target: BlockId, pred: BlockId) where 'arena: 'phase, 'phase: 'function {
2756 -
    let blk = getBlockMut(self, target);
2757 -
    assert blk.sealState <> Sealed::Yes, "addPredecessor: adding predecessor to sealed block";
2756 +
    let allocator = alloc::arenaAllocator(self.arena);
2757 +
    insertPredecessor(&mut self.blockData[..], target, pred, allocator);
2758 +
}
2759 +
2760 +
/// Insert one distinct predecessor into an unsealed block's owned list.
2761 +
fn insertPredecessor(blocks: &mut [BlockData], target: BlockId, pred: BlockId, allocator: alloc::Allocator) {
2762 +
    let blk = &mut blocks[*target];
2763 +
    assert blk.sealState <> Sealed::Yes, "insertPredecessor: adding predecessor to sealed block";
2758 2764
    let preds = &mut blk.preds;
2759 2765
    for i in 0..preds.len {
2760 2766
        if preds[i] == *pred { // Avoid duplicate predecessor entries.
2761 2767
            return;
2762 2768
        }
2763 2769
    }
2764 -
    preds.append(*pred, alloc::arenaAllocator(self.arena));
2770 +
    preds.append(*pred, allocator);
2765 2771
}
2766 2772
2767 2773
/// Finalize all blocks and return the block array.
2768 2774
unsafe fn finalizeBlocks 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function) -> *unsafe [il::Block] throws (LowerError) where 'arena: 'phase, 'phase: 'function {
2769 2775
    let mut blocks: *mut [il::Block] = &mut [];
3105 3111
///
3106 3112
/// This representation avoids the need for phi nodes to reference their
3107 3113
/// predecessor blocks explicitly, since the control flow edges already encode
3108 3114
/// that information.
3109 3115
unsafe fn resolveBlockArgs 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var, paramIdx: u32) throws (LowerError) where 'arena: 'phase, 'phase: 'function {
3110 -
    let blk = getBlock(&self.blockData[..], block);
3116 +
    let count = predecessorCount(&self.blockData[..], block);
3111 3117
3112 3118
    // For each predecessor, recursively look up the variable's reaching definition
3113 3119
    // in that block, then patch the predecessor's terminator to pass that value
3114 3120
    // as an argument to this block's parameter.
3115 -
    for predId in blk.preds {
3116 -
        let pred = BlockId(predId);
3121 +
    for index in 0..count {
3122 +
        let pred = BlockId(self.blockData[*block].preds[index]);
3117 3123
        // This may recursively trigger more block arg resolution if the
3118 3124
        // predecessor also needs to look up the variable from its predecessors.
3119 3125
        let val = try useVarInBlock(self, pred, v);
3120 3126
        assert val <> il::Val::Undef, "createBlockParam: predecessor provides undef value for block parameter";
3121 3127
        patchTerminatorArg(self, pred, *block, paramIdx, val);
3123 3129
}
3124 3130
3125 3131
/// Check if a block parameter is trivial, i.e. all predecessors provide
3126 3132
/// the same value. Returns the trivial value if so.
3127 3133
unsafe fn getTrivialPhiVal 'arena 'phase 'function (self: &mut FnLowerer 'arena 'phase 'function, block: BlockId, v: Var) -> ?il::Val throws (LowerError) where 'arena: 'phase, 'phase: 'function {
3128 -
    let blk = getBlock(&self.blockData[..], block);
3134 +
    let count = predecessorCount(&self.blockData[..], block);
3129 3135
    // Get the block parameter register.
3130 -
    let paramReg = blk.vars[*v];
3136 +
    let paramReg = self.blockData[*block].vars[*v];
3131 3137
    // Check if all predecessors provide the same value.
3132 3138
    let mut sameVal: ?il::Val = nil;
3133 3139
3134 -
    for predId in blk.preds {
3135 -
        let pred = BlockId(predId);
3140 +
    for index in 0..count {
3141 +
        let pred = BlockId(self.blockData[*block].preds[index]);
3136 3142
        let val = try useVarInBlock(self, pred, v);
3137 3143
3138 3144
        // Check if this is a self-reference.
3139 3145
        // This happens in cycles where the loop back-edge passes the phi to
3140 3146
        // itself. We skip self-references when checking for trivial phis.
5728 5734
    exitLoop(self);
5729 5735
5730 5736
    // Only seal end block if it's actually reachable (ie. has predecessors).
5731 5737
    // If the loop has no breaks and only exits via return, the end block
5732 5738
    // remains unreachable and isn't added to the CFG.
5733 -
    if getBlock(&self.blockData[..], endBlock).preds.len > 0 {
5739 +
    if predecessorCount(&self.blockData[..], endBlock) > 0 {
5734 5740
        try switchToAndSeal(self, endBlock);
5735 5741
    }
5736 5742
}
5737 5743
5738 5744
/// Lower a while loop: `while <cond> { <body> }`.
test/tests/ssa.predecessor.storage.rad added +45 -0
1 +
//! returns: 0
2 +
3 +
/// Carry changing and identical values through loop and conditional joins.
4 +
fn run(limit: u32, choose: bool) -> u32 {
5 +
    let mut total: u32 = 3;
6 +
    let mut carry: u32 = 5;
7 +
    let mut stable: u32 = 11;
8 +
    for index in 0..limit {
9 +
        if choose and index % 2 == 0 {
10 +
            set carry += 7;
11 +
            set stable = 11;
12 +
        } else {
13 +
            set carry += 13;
14 +
            set stable = 11;
15 +
        }
16 +
        match index % 3 {
17 +
            case 0 => set total += carry,
18 +
            case 1 => set total += stable,
19 +
            else => set total += carry + stable,
20 +
        }
21 +
    }
22 +
    return total + carry + stable;
23 +
}
24 +
25 +
/// Compare both branch paths over empty and repeated loop iterations.
26 +
@default fn main() -> u32 {
27 +
    for limit in 0..32 {
28 +
        for choose in [false, true] {
29 +
            let mut total: u32 = 3;
30 +
            let mut carry: u32 = 5;
31 +
            for index in 0..limit {
32 +
                set carry += 7 if choose and index % 2 == 0 else 13;
33 +
                if index % 3 <> 1 {
34 +
                    set total += carry;
35 +
                }
36 +
                if index % 3 <> 0 {
37 +
                    set total += 11;
38 +
                }
39 +
            }
40 +
            assert run(limit, choose) == total + carry + 11;
41 +
            assert run(limit, choose) == total + carry + 11;
42 +
        }
43 +
    }
44 +
    return 0;
45 +
}