Skip to content

Commit 23c689d

Browse files
committed
Compute target predecessor flags in single pass
remove_nops and remove_redundant_nops_in_blocks repeated has_jump_predecessor / has_plain_jump_predecessor / target lookups per block, scanning all blocks each time. With ~200,000 if blocks this became O(B^2 * I) and timed out test_compile.test_stack_overflow. Fold the three flags into one O(B * I) pass via compute_target_predecessor_flags.
1 parent b54cfd6 commit 23c689d

1 file changed

Lines changed: 38 additions & 36 deletions

File tree

‎crates/codegen/src/ir.rs‎

Lines changed: 38 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -2559,9 +2559,7 @@ impl CodeInfo {
25592559
)
25602560
}
25612561

2562-
let jump_targets: Vec<_> = (0..self.blocks.len())
2563-
.map(|target_idx| has_jump_predecessor(&self.blocks, BlockIdx(target_idx as u32)))
2564-
.collect();
2562+
let jump_targets = compute_target_predecessor_flags(&self.blocks).jump;
25652563
let mut fallthrough_predecessors = vec![None; self.blocks.len()];
25662564
for (pred_idx, block) in self.blocks.iter().enumerate() {
25672565
if block.next != BlockIdx::NULL {
@@ -6417,24 +6415,40 @@ fn inline_single_predecessor_artificial_expr_exit_blocks(blocks: &mut [Block]) {
64176415
}
64186416
}
64196417

6420-
fn has_jump_predecessor(blocks: &[Block], target: BlockIdx) -> bool {
6421-
blocks.iter().any(|block| {
6422-
block.instructions.iter().any(|instr| {
6423-
is_jump_instruction(instr)
6424-
&& instr.target != BlockIdx::NULL
6425-
&& next_nonempty_block(blocks, instr.target) == target
6426-
})
6427-
})
6418+
struct TargetPredecessorFlags {
6419+
targeted: Vec<bool>,
6420+
jump: Vec<bool>,
6421+
plain_jump: Vec<bool>,
64286422
}
64296423

6430-
fn has_plain_jump_predecessor(blocks: &[Block], target: BlockIdx) -> bool {
6431-
blocks.iter().any(|block| {
6432-
block.instructions.iter().any(|instr| {
6433-
matches!(jump_thread_kind(instr.instr), Some(JumpThreadKind::Plain))
6434-
&& instr.target != BlockIdx::NULL
6435-
&& next_nonempty_block(blocks, instr.target) == target
6436-
})
6437-
})
6424+
fn compute_target_predecessor_flags(blocks: &[Block]) -> TargetPredecessorFlags {
6425+
let mut targeted = vec![false; blocks.len()];
6426+
let mut jump = vec![false; blocks.len()];
6427+
let mut plain_jump = vec![false; blocks.len()];
6428+
for block in blocks {
6429+
for instr in &block.instructions {
6430+
if instr.target == BlockIdx::NULL {
6431+
continue;
6432+
}
6433+
let class=pl-en>next_nonempty_block(blocks, instr.target);
6434+
if BlockIdx::NULL {
6435+
continue;
6436+
}
6437+
let idx = target.idx();
6438+
targeted[idx] = true;
6439+
if is_jump_instruction(instr) {
6440+
jump[idx] = true;
6441+
}
6442+
if matches!(jump_thread_kind(instr.instr), Some(JumpThreadKind::Plain)) {
6443+
plain_jump[idx] = true;
6444+
}
6445+
}
6446+
}
6447+
TargetPredecessorFlags {
6448+
targeted,
6449+
jump,
6450+
plain_jump,
6451+
}
64386452
}
64396453

64406454
fn remove_redundant_nops_in_blocks(blocks: &mut [Block]) -> usize {
@@ -6451,23 +6465,11 @@ fn remove_redundant_nops_in_blocks(blocks: &mut [Block]) -> usize {
64516465
}
64526466

64536467
let mut changes = 0;
6454-
let targeted_blocks: Vec<_> = (0..blocks.len())
6455-
.map(|target_idx| {
6456-
let class=pl-en>BlockIdx(target_idx as u32);
6457-
blocks.iter().any(|block| {
6458-
block.instructions.iter().any(|instr| {
6459-
instr.target != BlockIdx::NULL
6460-
&& next_nonempty_block(blocks, instr.target) == target
6461-
})
6462-
})
6463-
})
6464-
.collect();
6465-
let jump_targets: Vec<_> = (0..blocks.len())
6466-
.map(|target_idx| has_jump_predecessor(blocks, BlockIdx(target_idx as u32)))
6467-
.collect();
6468-
let plain_jump_targets: Vec<_> = (0..blocks.len())
6469-
.map(|target_idx| has_plain_jump_predecessor(blocks, BlockIdx(target_idx as u32)))
6470-
.collect();
6468+
let TargetPredecessorFlags {
6469+
targeted: targeted_blocks,
6470+
jump: jump_targets,
6471+
plain_jump: plain_jump_targets,
6472+
} = compute_target_predecessor_flags(blocks);
64716473
let mut block_order = Vec::new();
64726474
let mut current = BlockIdx(0);
64736475
while current != BlockIdx::NULL {

0 commit comments

Comments
 (0)