Visitar URL original
Add duplicate_exits_without_lineno (disabled) and Block: Clone · RustPython/RustPython@0cd225f · GitHub
Skip to content

Commit 0cd225f

Browse files
committed
Add duplicate_exits_without_lineno (disabled) and Block: Clone
Prepare infrastructure for exit block duplication optimization. Currently disabled pending stackdepth integration.
1 parent f8927e1 commit 0cd225f

1 file changed

Lines changed: 103 additions & 5 deletions

File tree

‎crates/codegen/src/ir.rs‎

Lines changed: 103 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -125,7 +125,7 @@ pub struct ExceptHandlerInfo {
125125
// spell-checker:ignore petgraph
126126
// TODO: look into using petgraph for handling blocks and stuff? it's heavier than this, but it
127127
// might enable more analysis/optimizations
128-
#[derive(Debug)]
128+
#[derive(Debug, Clone)]
129129
pub struct Block {
130130
pub instructions: Vec<InstructionInfo>,
131131
pub next: BlockIdx,
@@ -225,6 +225,8 @@ impl CodeInfo {
225225
normalize_jumps(&mut self.blocks);
226226
self.dce(); // re-run within-block DCE after normalize_jumps creates new instructions
227227
self.eliminate_unreachable_blocks();
228+
// TODO: duplicate_exits_without_lineno disabled pending stackdepth fix
229+
// duplicate_exits_without_lineno(&mut self.blocks);
228230
duplicate_end_returns(&mut self.blocks);
229231
self.dce(); // truncate after terminal in blocks that got return duplicated
230232
self.eliminate_unreachable_blocks(); // remove now-unreachable last block
@@ -2496,11 +2498,107 @@ fn normalize_jumps(blocks: &mut Vec<Block>) {
24962498
}
24972499
}
24982500

2501+
#[allow(dead_code)]
2502+
fn is_simple_return_block(block: &Block) -> bool {
2503+
block.instructions.len() == 1
2504+
&& matches!(
2505+
block.instructions[0].instr.real(),
2506+
Some(Instruction::ReturnValue)
2507+
)
2508+
}
2509+
2510+
/// Follow chain of empty blocks to find first non-empty block.
2511+
fn next_nonempty_block(blocks: &[Block], mut idx: BlockIdx) -> BlockIdx {
2512+
while idx != BlockIdx::NULL
2513+
&& blocks[idx.idx()].instructions.is_empty()
2514+
&& blocks[idx.idx()].next != BlockIdx::NULL
2515+
{
2516+
idx = blocks[idx.idx()].next;
2517+
}
2518+
idx
2519+
}
2520+
2521+
#[allow(dead_code)]
2522+
fn duplicate_exits_without_lineno(blocks: &mut Vec<Block>) {
2523+
// Count predecessors for each block
2524+
let mut predecessors = vec![0u32; blocks.len()];
2525+
let mut current = BlockIdx(0);
2526+
while current != BlockIdx::NULL {
2527+
let block = &blocks[current.idx()];
2528+
// Fall-through predecessor
2529+
let next = next_nonempty_block(blocks, block.next);
2530+
if next != BlockIdx::NULL {
2531+
let has_fallthrough = block.instructions.last().map_or(true, |ins| {
2532+
!ins.instr.is_scope_exit() && !ins.instr.is_unconditional_jump()
2533+
});
2534+
if has_fallthrough {
2535+
predecessors[next.idx()] += 1;
2536+
}
2537+
}
2538+
// Jump target predecessor
2539+
for ins in &block.instructions {
2540+
if ins.target != BlockIdx::NULL {
2541+
let target = next_nonempty_block(blocks, ins.target);
2542+
if target != BlockIdx::NULL {
2543+
predecessors[target.idx()] += 1;
2544+
}
2545+
}
2546+
}
2547+
current = block.next;
2548+
}
2549+
2550+
// For each block, if its last instruction jumps to an exit block without lineno
2551+
// that has >1 predecessor, copy that exit block.
2552+
current = BlockIdx(0);
2553+
while current != BlockIdx::NULL {
2554+
let block = &blocks[current.idx()];
2555+
let last = match block.instructions.last() {
2556+
Some(ins) if ins.target != BlockIdx::NULL => ins,
2557+
_ => {
2558+
current = blocks[current.idx()].next;
2559+
continue;
2560+
}
2561+
};
2562+
if !last.instr.is_unconditional_jump() && !is_conditional_jump(&last.instr) {
2563+
current = blocks[current.idx()].next;
2564+
continue;
2565+
}
2566+
2567+
let target = next_nonempty_block(blocks, last.target);
2568+
if target == BlockIdx::NULL || !is_simple_return_block(&blocks[target.idx()]) {
2569+
current = blocks[current.idx()].next;
2570+
continue;
2571+
}
2572+
if predecessors[target.idx()] <= 1 {
2573+
current = blocks[current.idx()].next;
2574+
continue;
2575+
}
2576+
2577+
// Copy the exit block
2578+
let new_idx = BlockIdx(blocks.len() as u32);
2579+
let mut new_block = blocks[target.idx()].clone();
2580+
// Set location from the jump instruction
2581+
let jump_loc = blocks[current.idx()].instructions.last().unwrap().location;
2582+
let jump_end_loc = blocks[current.idx()].instructions.last().unwrap().end_location;
2583+
if let Some(first) = new_block.instructions.first_mut() {
2584+
first.location = jump_loc;
2585+
first.end_location = jump_end_loc;
2586+
}
2587+
new_block.next = blocks[target.idx()].next;
2588+
blocks.push(new_block);
2589+
2590+
// Update the jump target
2591+
let last_mut = blocks[current.idx()].instructions.last_mut().unwrap();
2592+
last_mut.target = new_idx;
2593+
predecessors[target.idx()] -= 1;
2594+
2595+
current = blocks[current.idx()].next;
2596+
}
2597+
}
2598+
24992599
/// Duplicate `LOAD_CONST None + RETURN_VALUE` for blocks that fall through
2500-
/// to the final return block. Matches CPython's behavior of ensuring every
2501-
/// code path that reaches the end of a function/module has its own explicit
2502-
/// return instruction.
2503-
fn duplicate_end_returns(blocks: &mut [Block]) {
2600+
/// to the final return block.
2601+
fn duplicate_end_returns(blocks: &mut Vec<Block>) {
25042602
// Walk the block chain to find the last block
25052603
let mut last_block = BlockIdx(0);
25062604
let mut current = BlockIdx(0);

0 commit comments

Comments
 (0)