use core::ops::{Deref, DerefMut, Index, IndexMut};
use crate::{IndexMap, IndexSet, error::InternalError};
use malachite_bigint::BigInt;
use num_complex::Complex;
use num_traits::{ToPrimitive, Zero};
use rustpython_wtf8::Wtf8Buf;
use rustpython_compiler_core::{
OneIndexed, SourceLocation, SourceLocationRange as LineTableLocation,
bytecode::{
AnyInstruction, AnyOpcode, CO_FAST_ARG_KW, CO_FAST_ARG_POS, CO_FAST_ARG_VAR, CO_FAST_CELL,
CO_FAST_FREE, CO_FAST_HIDDEN, CO_FAST_LOCAL, CodeFlags, CodeObject, CodeUnit, CodeUnits,
ConstantData, InstrDisplayContext, Instruction, IntrinsicFunction1, OpArg, OpArgByte,
Opcode, PseudoInstruction, PseudoOpcode, PyCodeLocationInfoKind, oparg,
},
varint::{write_signed_varint, write_varint},
};
#[derive(Clone, Copy)]
struct InstructionLocation {
semantic_location: Option,
location: SourceLocation,
end_location: SourceLocation,
lineno_override: Option,
}
pub(crate) const LINE_ONLY_LOCATION_OVERRIDE: i32 = -4;
pub(crate) const NEXT_LOCATION_OVERRIDE: i32 = -2;
pub(crate) const NO_LOCATION_OVERRIDE: i32 = -1;
const MAX_INT_SIZE: u64 = 128;
const MAX_COLLECTION_SIZE: usize = 256;
const DEFAULT_CODE_SIZE: usize = 128;
const DEFAULT_LNOTAB_SIZE: usize = 16;
const DEFAULT_CNOTAB_SIZE: usize = 32;
const DEFAULT_BLOCK_SIZE: usize = 16;
const INITIAL_INSTR_SEQUENCE_SIZE: usize = 100;
const INITIAL_INSTR_SEQUENCE_LABELS_MAP_SIZE: usize = 10;
const MAX_REAL_OPCODE: u16 = 254;
const MAX_OPCODE: u16 = 511;
const MAX_TOTAL_ITEMS: isize = 1024;
const MAX_STR_SIZE: usize = 4096;
const MIN_CONST_SEQUENCE_SIZE: usize = 3;
const STACK_USE_GUIDELINE: usize = 30;
/// pycore_opcode_utils.h IS_WITHIN_OPCODE_RANGE
fn is_within_opcode_range(opcode: AnyOpcode) -> bool {
match opcode {
AnyOpcode::Real(opcode) => u16::from(opcode.as_u8()) opcode.as_u16() bool {
match constant {
ConstantData::Float { value } => value.is_nan(),
ConstantData::Complex { value } => value.re.is_nan() || value.im.is_nan(),
ConstantData::Tuple { elements } | ConstantData::Frozenset { elements } => {
elements.iter().any(Self::constant_contains_nan)
}
ConstantData::Slice { elements } => elements.iter().any(Self::constant_contains_nan),
_ => false,
}
}
fn frozenset_key_contains(elements: &[ConstantData], needle: &ConstantData) -> bool {
if Self::constant_contains_nan(needle) {
return false;
}
elements.iter().any(|element| {
!Self::constant_contains_nan(element) && Self::constant_key_eq(element, needle)
})
}
fn frozenset_key_eq(left: &[ConstantData], right: &[ConstantData]) -> bool {
left.iter()
.all(|element| Self::frozenset_key_contains(right, element))
&& right
.iter()
.all(|element| Self::frozenset_key_contains(left, element))
}
fn constant_key_eq(left: &ConstantData, right: &ConstantData) -> bool {
match (left, right) {
(ConstantData::Tuple { elements: left }, ConstantData::Tuple { elements: right }) => {
left.len() == right.len()
&& left
.iter()
.zip(right.iter())
.all(|(left, right)| Self::constant_key_eq(left, right))
}
(
ConstantData::Frozenset { elements: left },
ConstantData::Frozenset { elements: right },
) => Self::frozenset_key_eq(left, right),
(ConstantData::Slice { elements: left }, ConstantData::Slice { elements: right }) => {
left.iter()
.zip(right.iter())
.all(|(left, right)| Self::constant_key_eq(left, right))
}
_ => left == right,
}
}
fn canonicalize_constant_key(constant: ConstantData) -> crate::InternalResult {
match constant {
ConstantData::Tuple { elements } => {
let mut canonical = Vec::new();
canonical
.try_reserve_exact(elements.len())
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
for element in elements {
canonical.push(Self::canonicalize_constant_key(element)?);
}
Ok(ConstantData::Tuple {
elements: canonical,
})
}
ConstantData::Slice { elements } => {
let [start, stop, step] = *elements;
Ok(ConstantData::Slice {
elements: Box::new([
Self::canonicalize_constant_key(start)?,
Self::canonicalize_constant_key(stop)?,
Self::canonicalize_constant_key(step)?,
]),
})
}
ConstantData::Frozenset { elements } => {
let mut canonical = Vec::new();
canonical
.try_reserve_exact(elements.len())
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
for element in elements {
let element = Self::canonicalize_constant_key(element)?;
if !Self::frozenset_key_contains(&canonical, &element) {
canonical.push(element);
}
}
Ok(ConstantData::Frozenset {
elements: canonical,
})
}
other => Ok(other),
}
}
fn canonicalize_constant_key_infallible(constant: ConstantData) -> ConstantData {
Self::canonicalize_constant_key(constant)
.expect("constant key canonicalization only fails on allocation error")
}
/// Index of an already-stored constant equal to `constant`, if any.
/// _PyCode_ConstantKey() keeps NaN-bearing constants distinct because
/// Python-level NaN keys do not compare equal.
fn find_existing(&self, constant: &ConstantData) -> Option {
if Self::constant_contains_nan(constant) {
return None;
}
self.constants
.iter()
.position(|existing| Self::constant_key_eq(existing, constant))
}
pub fn insert_full(&mut self, constant: ConstantData) -> (usize, bool) {
let constant = Self::canonicalize_constant_key_infallible(constant);
if let Some(idx) = self.find_existing(&constant) {
return (idx, false);
}
let idx = self.constants.len();
self.constants.push(constant);
(idx, true)
}
fn try_insert_full(&mut self, constant: ConstantData) -> crate::InternalResult {
let constant = Self::canonicalize_constant_key(constant)?;
if let Some(idx) = self.find_existing(&constant) {
return Ok((idx, false));
}
self.constants
.try_reserve_exact(1)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
let idx = self.constants.len();
self.constants.push(constant);
Ok((idx, true))
}
pub fn insert(&mut self, constant: ConstantData) -> bool {
self.insert_full(constant).1
}
#[must_use]
pub fn from_ordered(constants: Vec) -> Self {
Self { constants }
}
#[must_use]
pub fn into_vec(self) -> Vec {
self.constants
}
#[must_use]
pub fn get_index(&self, idx: usize) -> Option {
self.constants.get(idx)
}
pub fn iter(&self) -> core::slice::Iter crate::InternalResult {
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
self[block_idx].predecessors = 0;
block_idx = self[block_idx].next;
}
let mut stack = self.make_cfg_traversal_stack()?;
self[0].predecessors = 1;
stack.push(BlockIdx(0));
self[0].visited = true;
while let Some(current) = stack.pop() {
let idx = current.idx();
let next = self[idx].next;
if next != BlockIdx::NULL && self[idx].bb_has_fallthrough() {
if !self[next].visited {
debug_assert_eq!(self[next].predecessors, 0);
stack.push(next);
self[next].visited = true;
}
self[next].predecessors += 1;
}
let instr_count = self[idx].instruction_used;
for i in 0..instr_count {
let instr = self[idx].instructions[i];
if instr.is_jump() || instr.is_block_push() {
let target = instr.target;
debug_assert!(target != BlockIdx::NULL);
let target_idx = target.idx();
if !self[target_idx].visited {
stack.push(target);
self[target_idx].visited = true;
}
self[target_idx].predecessors += 1;
}
}
}
block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next = self[block_idx].next;
if self[block_idx].predecessors == 0 {
let block = &mut self[block_idx];
block.basicblock_clear();
block.except_handler = false;
}
block_idx = next;
}
Ok(())
}
/// flowgraph.c basicblock_append_instructions
fn basicblock_append_block_instructions(
&mut self,
to: BlockIdx,
from: BlockIdx,
) -> crate::InternalResult {
debug_assert_ne!(to, from);
let from_len = self[from].instruction_used;
for i in 0..from_len {
let info = self[from].instructions[i];
let off = self[to].basicblock_next_instr()?;
self[to].instructions[off] = info;
}
Ok(())
}
/// flowgraph.c copy_basicblock
fn copy_basicblock(&mut self, block_idx: BlockIdx) -> crate::InternalResult {
debug_assert!(self[block_idx].bb_no_fallthrough());
let result = self.blocks_new_block()?;
self.basicblock_append_block_instructions(result, block_idx)?;
Ok(result)
}
fn duplicate_exits_without_lineno(&mut self) -> crate::InternalResult {
let mut next_lbl = get_max_label(self) + 1;
let entryblock = BlockIdx(0);
let mut b = entryblock;
while b != BlockIdx::NULL {
let Some(last) = self[b].basicblock_last_instr().copied() else {
b = self[b].next;
continue;
};
if last.is_jump() {
debug_assert!(last.target != BlockIdx::NULL);
let target = next_nonempty_block(self, last.target);
debug_assert!(target != BlockIdx::NULL);
if self[target].is_exit_or_eval_check_without_lineno()
&& self[target].predecessors > 1
{
let new_target = self.copy_basicblock(target)?;
self[new_target].instructions[0].instr_set_location(last.instr_location());
let last_mut = self[b].basicblock_last_instr_mut().unwrap();
last_mut.target = new_target;
self[target].predecessors -= 1;
self[new_target].predecessors = 1;
self[new_target].next = self[target].next;
self[new_target].cpython_label = InstructionSequenceLabel(next_lbl);
next_lbl += 1;
self[target].next = new_target;
}
}
b = self[b].next;
}
b = entryblock;
while b != BlockIdx::NULL {
let next = self[b].next;
if self[b].bb_has_fallthrough()
&& next != BlockIdx::NULL
&& self[b].instruction_used != 0
&& self[next].is_exit_or_eval_check_without_lineno()
{
let last = *self[b]
.basicblock_last_instr()
.expect("block has instructions");
self[next].instructions[0].instr_set_location(last.instr_location());
}
b = self[b].next;
}
Ok(())
}
fn resolve_line_numbers(&mut self, _firstlineno: OneIndexed) -> crate::InternalResult {
self.duplicate_exits_without_lineno()?;
self.propagate_line_numbers();
Ok(())
}
/// flowgraph.c optimize_basic_block
fn optimize_basic_block(
&mut self,
metadata: &mut CodeUnitMetadata,
block_idx: BlockIdx,
) -> crate::InternalResult {
let mut nop = InstructionInfo {
instr: Instruction::Nop.into(),
arg: OpArg::NULL,
target: BlockIdx::NULL,
location: SourceLocation::default(),
end_location: SourceLocation::default(),
except_handler: None,
semantic_location: None,
lineno_override: None,
};
nop.instr_set_op0(Instruction::Nop.into());
let mut i = 0;
while i < self[block_idx].instruction_used {
let inst = self[block_idx].instructions[i];
debug_assert!(!inst.instr.is_assembler());
let target = if inst.instr.has_target() {
let target = inst.target;
debug_assert!(target != BlockIdx::NULL);
debug_assert!(self[target.idx()].instruction_used != 0);
debug_assert!(!self[target.idx()].instructions[0].instr.is_assembler());
self[target.idx()].instructions[0]
} else {
nop
};
let nextop = self[block_idx]
.instructions
.get(i + 1)
.and_then(|next| next.instr.real());
match inst.instr {
AnyInstruction::Real(Instruction::BuildTuple { .. }) => {
let oparg = u32::from(inst.arg);
if matches!(nextop, Some(Instruction::UnpackSequence { .. }))
&& u32::from(self[block_idx].instructions[i + 1].arg) == oparg
{
match oparg {
1 => {
self[block_idx].instructions[i].set_to_nop();
self[block_idx].instructions[i + 1].set_to_nop();
i += 1;
continue;
}
2 | 3 => {
self[block_idx].instructions[i].set_to_nop();
self[block_idx].instructions[i + 1].instr = Opcode::Swap.into();
i += 1;
continue;
}
_ => {}
}
}
fold_tuple_of_constants(metadata, &mut self[block_idx], i)?;
}
AnyInstruction::Real(
Instruction::BuildList { .. } | Instruction::BuildSet { .. },
) => {
optimize_lists_and_sets(metadata, &mut self[block_idx], i, nextop)?;
}
AnyInstruction::Real(
Instruction::PopJumpIfNotNone { .. } | Instruction::PopJumpIfNone { .. },
) if matches!(target.instr.into(), AnyOpcode::Pseudo(PseudoOpcode::Jump))
&& self.jump_thread(block_idx, i, &target, inst.instr)? =>
{
continue;
}
AnyInstruction::Real(Instruction::PopJumpIfFalse { .. })
if matches!(target.instr.into(), AnyOpcode::Pseudo(PseudoOpcode::Jump))
&& self.jump_thread(block_idx, i, &target, inst.instr)? =>
{
continue;
}
AnyInstruction::Real(Instruction::PopJumpIfTrue { .. })
if matches!(target.instr.into(), AnyOpcode::Pseudo(PseudoOpcode::Jump))
&& self.jump_thread(block_idx, i, &target, inst.instr)? =>
{
continue;
}
AnyInstruction::Pseudo(
pseudo @ (PseudoInstruction::JumpIfFalse { .. }
| PseudoInstruction::JumpIfTrue { .. }),
) => {
let opcode = pseudo.into();
let opcode_is_false = matches!(pseudo, PseudoInstruction::JumpIfFalse { .. });
match target.instr.pseudo().map(Into::into) {
Some(PseudoOpcode::Jump)
if self.jump_thread(block_idx, i, &target, opcode)? =>
{
continue;
}
Some(PseudoOpcode::JumpIfFalse)
if opcode_is_false
&& self.jump_thread(block_idx, i, &target, opcode)? =>
{
continue;
}
Some(PseudoOpcode::JumpIfTrue)
if !opcode_is_false
&& self.jump_thread(block_idx, i, &target, opcode)? =>
{
continue;
}
Some(PseudoOpcode::JumpIfTrue) if opcode_is_false => {
let next = self[inst.target].next;
debug_assert!(next != BlockIdx::NULL);
debug_assert!(next != inst.target);
self[block_idx].instructions[i].target = next;
continue;
}
Some(PseudoOpcode::JumpIfFalse) if !opcode_is_false => {
let next = self[inst.target].next;
debug_assert!(next != BlockIdx::NULL);
debug_assert!(next != inst.target);
self[block_idx].instructions[i].target = next;
continue;
}
_ => {}
}
}
AnyInstruction::Pseudo(
PseudoInstruction::Jump { .. } | PseudoInstruction::JumpNoInterrupt { .. },
) => match target.instr.into() {
AnyOpcode::Pseudo(PseudoOpcode::Jump)
if self.jump_thread(
block_idx,
i,
&target,
PseudoOpcode::Jump.into(),
)? =>
{
continue;
}
AnyOpcode::Pseudo(PseudoOpcode::JumpNoInterrupt)
if self.jump_thread(block_idx, i, &target, inst.instr)? =>
{
continue;
}
_ => {}
},
// CPython leaves FOR_ITER jump threading disabled.
AnyInstruction::Real(Instruction::ForIter { .. }) => {}
AnyInstruction::Real(Instruction::StoreFast { .. })
if matches!(nextop, Some(Instruction::StoreFast { .. }))
&& u32::from(inst.arg)
== u32::from(self[block_idx].instructions[i + 1].arg)
&& self[block_idx].instructions[i].instruction_lineno()
== self[block_idx].instructions[i + 1].instruction_lineno() =>
{
self[block_idx].instructions[i].instr = Instruction::PopTop.into();
self[block_idx].instructions[i].arg = OpArg::NULL;
}
AnyInstruction::Real(Instruction::Swap { .. }) if u32::from(inst.arg) == 1 => {
self[block_idx].instructions[i].set_to_nop();
}
AnyInstruction::Real(Instruction::LoadGlobal { .. })
if matches!(nextop, Some(Instruction::PushNull))
&& (u32::from(inst.arg) & 1) == 0 =>
{
self[block_idx].instructions[i]
.instr_set_op1(inst.instr, OpArg::new(u32::from(inst.arg) | 1));
self[block_idx].instructions[i + 1].set_to_nop();
}
AnyInstruction::Real(Instruction::CompareOp { .. })
if matches!(nextop, Some(Instruction::ToBool)) =>
{
self[block_idx].instructions[i].set_to_nop();
self[block_idx].instructions[i + 1].instr_set_op1(
inst.instr,
OpArg::new(u32::from(inst.arg) | oparg::COMPARE_OP_BOOL_MASK),
);
i += 1;
continue;
}
AnyInstruction::Real(Instruction::ContainsOp { .. } | Instruction::IsOp { .. })
if matches!(nextop, Some(Instruction::ToBool)) =>
{
self[block_idx].instructions[i].set_to_nop();
self[block_idx].instructions[i + 1].instr_set_op1(inst.instr, inst.arg);
i += 1;
continue;
}
AnyInstruction::Real(Instruction::ContainsOp { .. } | Instruction::IsOp { .. })
if matches!(nextop, Some(Instruction::UnaryNot)) =>
{
self[block_idx].instructions[i].set_to_nop();
let inverted = u32::from(inst.arg) ^ 1;
debug_assert!(inverted == 0 || inverted == 1);
self[block_idx].instructions[i + 1]
.instr_set_op1(inst.instr, OpArg::new(inverted));
i += 1;
continue;
}
AnyInstruction::Real(Instruction::ToBool)
if matches!(nextop, Some(Instruction::ToBool)) =>
{
self[block_idx].instructions[i].set_to_nop();
i += 1;
continue;
}
AnyInstruction::Real(Instruction::UnaryNot) => {
if matches!(nextop, Some(Instruction::ToBool)) {
self[block_idx].instructions[i].set_to_nop();
self[block_idx].instructions[i + 1].instr_set_op0(inst.instr);
i += 1;
continue;
}
if matches!(nextop, Some(Instruction::UnaryNot)) {
self[block_idx].instructions[i].set_to_nop();
self[block_idx].instructions[i + 1].set_to_nop();
i += 1;
continue;
}
fold_const_unaryop(metadata, &mut self[block_idx], i)?;
}
AnyInstruction::Real(Instruction::UnaryInvert | Instruction::UnaryNegative) => {
fold_const_unaryop(metadata, &mut self[block_idx], i)?;
}
AnyInstruction::Real(Instruction::CallIntrinsic1 { func }) => {
match func.get(inst.arg) {
IntrinsicFunction1::ListToTuple => {
fold_constant_sequence_into_load_const(
metadata,
&mut self[block_idx],
i,
)?;
if matches!(
self[block_idx].instructions[i].instr.real(),
Some(Instruction::CallIntrinsic1 { .. })
) && matches!(nextop, Some(Instruction::GetIter { .. }))
{
self[block_idx].instructions[i].set_to_nop();
}
}
IntrinsicFunction1::UnaryPositive => {
fold_const_unaryop(metadata, &mut self[block_idx], i)?;
}
_ => {}
}
}
AnyInstruction::Real(
Instruction::ListAppend { .. } | Instruction::SetAdd { .. },
) if u32::from(inst.arg) == 1
&& matches!(
nextop,
Some(Instruction::GetIter { .. } | Instruction::ContainsOp { .. })
) =>
{
fold_constant_sequence_into_load_const(metadata, &mut self[block_idx], i)?;
}
AnyInstruction::Real(Instruction::BinaryOp { .. }) => {
fold_const_binop(metadata, &mut self[block_idx], i)?;
}
_ => {}
}
i += 1;
}
self[block_idx].apply_static_swaps_block()?;
Ok(())
}
/// flowgraph.c _PyCfg_ToInstructionSequence
fn cfg_to_instruction_sequence(
&mut self,
instr_sequence: &mut InstructionSequence,
) -> crate::InternalResult {
let mut label_id = 0;
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
self[block_idx].cpython_label = InstructionSequenceLabel::from_index(label_id);
label_id += 1;
block_idx = self[block_idx].next;
}
block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let block_label = self[block_idx].cpython_label;
debug_assert!(is_label(block_label));
instruction_sequence_use_label(instr_sequence, block_label)?;
let instr_count = self[block_idx].instruction_used;
for i in 0..instr_count {
if self[block_idx].instructions[i].instr.has_target() {
let target_block = self[block_idx].instructions[i].target;
debug_assert!(target_block != BlockIdx::NULL);
let lbl = self[target_block].cpython_label;
debug_assert!(is_label(lbl));
self[block_idx].instructions[i].arg = OpArg::new(lbl.0 as u32);
}
let mut info = self[block_idx].instructions[i];
info.target = BlockIdx::NULL;
let except_handler = info.except_handler.take();
let entry = instruction_sequence_addop(instr_sequence, info)?;
let hi = &mut entry.except_handler;
if let Some(handler) = except_handler {
debug_assert!(handler.handler_block != BlockIdx::NULL);
let lbl = self[handler.handler_block].cpython_label;
debug_assert!(is_label(lbl));
let start_depth = self[handler.handler_block].start_depth;
debug_assert!(start_depth >= 0);
hi.h_label = lbl.0;
hi.start_depth = start_depth;
hi.preserve_lasti = i32::from(handler.preserve_lasti);
} else {
hi.h_label = NO_EXCEPTION_HANDLER_LABEL;
}
}
block_idx = self[block_idx].next;
}
instruction_sequence_apply_label_map(instr_sequence);
Ok(())
}
fn optimize_load_fast(&mut self) -> crate::InternalResult {
let mut max_instrs = 0;
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
max_instrs = max_instrs.max(self[current].instruction_used);
current = self[current].next;
}
let mut instr_flags = Vec::new();
instr_flags
.try_reserve_exact(max_instrs)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
instr_flags.resize(max_instrs, 0u8);
let mut refs = RefStack {
refs: Vec::new(),
size: 0,
capacity: 0,
};
let mut worklist = self.make_cfg_traversal_stack()?;
worklist.push(BlockIdx(0));
self[0].start_depth = 0;
self[0].visited = true;
while let Some(block_idx) = worklist.pop() {
let instr_count = self[block_idx].instruction_used;
instr_flags[..instr_count].fill(0);
debug_assert!(self[block_idx].start_depth >= 0);
let start_depth = self[block_idx].start_depth as usize;
ref_stack_clear(&mut refs);
for _ in 0..start_depth {
push_ref(&mut refs, DUMMY_INSTR, NOT_LOCAL)?;
}
for i in 0..instr_count {
let info = self[block_idx].instructions[i];
let instr = info.instr;
let arg_u32 = u32::from(info.arg);
debug_assert!(!matches!(instr.real(), Some(Instruction::ExtendedArg)));
match instr {
AnyInstruction::Real(Instruction::DeleteFast { var_num }) => {
kill_local(
&mut instr_flags,
&refs,
local_as_ref_local(usize::from(var_num.get(info.arg))),
);
}
AnyInstruction::Real(Instruction::LoadFast { var_num }) => {
push_ref(
&mut refs,
i as isize,
local_as_ref_local(usize::from(var_num.get(info.arg))),
)?;
}
AnyInstruction::Real(Instruction::LoadFastAndClear { var_num }) => {
let local = local_as_ref_local(usize::from(var_num.get(info.arg)));
kill_local(&mut instr_flags, &refs, local);
push_ref(&mut refs, i as isize, local)?;
}
AnyInstruction::Real(Instruction::LoadFastLoadFast { .. }) => {
let local1 = (arg_u32 >> 4) as isize;
let local2 = (arg_u32 & 15) as isize;
push_ref(&mut refs, i as isize, local1)?;
push_ref(&mut refs, i as isize, local2)?;
}
AnyInstruction::Real(Instruction::StoreFast { var_num }) => {
let r = ref_stack_pop(&mut refs);
store_local(
&mut instr_flags,
&refs,
local_as_ref_local(usize::from(var_num.get(info.arg))),
r,
);
}
AnyInstruction::Real(Instruction::StoreFastLoadFast { .. }) => {
let r = ref_stack_pop(&mut refs);
store_local(&mut instr_flags, &refs, (arg_u32 >> 4) as isize, r);
push_ref(&mut refs, i as isize, (arg_u32 & 15) as isize)?;
}
AnyInstruction::Real(Instruction::StoreFastStoreFast { .. }) => {
let r1 = ref_stack_pop(&mut refs);
store_local(&mut instr_flags, &refs, (arg_u32 >> 4) as isize, r1);
let r2 = ref_stack_pop(&mut refs);
store_local(&mut instr_flags, &refs, (arg_u32 & 15) as isize, r2);
}
AnyInstruction::Real(Instruction::Copy { i: _ }) => {
let depth = arg_u32 as usize;
assert!(depth > 0);
assert!(refs.size >= depth);
let r = ref_stack_at(&refs, refs.size - depth);
push_ref(&mut refs, r.instr, r.local)?;
}
AnyInstruction::Real(Instruction::Swap { i: _ }) => {
let depth = arg_u32 as usize;
assert!(depth >= 2);
assert!(refs.size >= depth);
ref_stack_swap_top(&mut refs, depth);
}
AnyInstruction::Real(
Instruction::FormatSimple
| Instruction::GetAnext
| Instruction::GetLen
| Instruction::GetIter { .. }
| Instruction::ImportFrom { .. }
| Instruction::MatchKeys
| Instruction::MatchMapping
| Instruction::MatchSequence
| Instruction::WithExceptStart,
) => {
let effect = instr.stack_effect_info(arg_u32);
let net_pushed = effect.pushed() as isize - effect.popped() as isize;
debug_assert!(net_pushed >= 0);
for _ in 0..net_pushed {
push_ref(&mut refs, i as isize, NOT_LOCAL)?;
}
}
AnyInstruction::Real(
Instruction::DictMerge { .. }
| Instruction::DictUpdate { .. }
| Instruction::ListAppend { .. }
| Instruction::ListExtend { .. }
| Instruction::MapAdd { .. }
| Instruction::Reraise { .. }
| Instruction::SetAdd { .. }
| Instruction::SetUpdate { .. },
) => {
let effect = instr.stack_effect_info(arg_u32);
let net_popped = effect.popped() as isize - effect.pushed() as isize;
debug_assert!(net_popped > 0);
for _ in 0..net_popped {
let _ = ref_stack_pop(&mut refs);
}
}
AnyInstruction::Real(
Instruction::EndSend | Instruction::SetFunctionAttribute { .. },
) => {
let effect = instr.stack_effect_info(arg_u32);
debug_assert_eq!(
effect.popped(),
if matches!(instr.real(), Some(Instruction::EndSend)) {
3
} else {
2
}
);
debug_assert_eq!(effect.pushed(), 1);
let tos = ref_stack_pop(&mut refs);
for _ in 1..effect.popped() {
let _ = ref_stack_pop(&mut refs);
}
push_ref(&mut refs, tos.instr, tos.local)?;
}
AnyInstruction::Real(Instruction::CheckExcMatch) => {
let _ = ref_stack_pop(&mut refs);
push_ref(&mut refs, i as isize, NOT_LOCAL)?;
}
AnyInstruction::Real(Instruction::ForIter { .. }) => {
let target = info.target;
debug_assert!(target != BlockIdx::NULL);
load_fast_push_block(&mut worklist, self, target, refs.size + 1);
push_ref(&mut refs, i as isize, NOT_LOCAL)?;
}
AnyInstruction::Real(
Instruction::LoadAttr { .. } | Instruction::LoadSuperAttr { .. },
) => {
let self_ref = ref_stack_pop(&mut refs);
if matches!(instr.real(), Some(Instruction::LoadSuperAttr { .. })) {
let _ = ref_stack_pop(&mut refs);
let _ = ref_stack_pop(&mut refs);
}
push_ref(&mut refs, i as isize, NOT_LOCAL)?;
if arg_u32 & 1 != 0 {
push_ref(&mut refs, self_ref.instr, self_ref.local)?;
}
}
AnyInstruction::Real(
Instruction::LoadSpecial { .. } | Instruction::PushExcInfo,
) => {
let tos = ref_stack_pop(&mut refs);
push_ref(&mut refs, i as isize, NOT_LOCAL)?;
push_ref(&mut refs, tos.instr, tos.local)?;
}
AnyInstruction::Real(Instruction::Send { .. }) => {
let target = info.target;
debug_assert!(target != BlockIdx::NULL);
load_fast_push_block(&mut worklist, self, target, refs.size);
let _ = ref_stack_pop(&mut refs);
push_ref(&mut refs, i as isize, NOT_LOCAL)?;
}
_ => {
let effect = instr.stack_effect_info(arg_u32);
let num_popped = effect.popped() as usize;
let num_pushed = effect.pushed() as usize;
let target = info.target;
if instr.has_target() {
debug_assert!(target != BlockIdx::NULL);
debug_assert!(refs.size >= num_popped);
let target_depth = refs.size - num_popped + num_pushed;
load_fast_push_block(&mut worklist, self, target, target_depth);
}
if !info.is_block_push() {
for _ in 0..num_popped {
let _ = ref_stack_pop(&mut refs);
}
for _ in 0..num_pushed {
push_ref(&mut refs, i as isize, NOT_LOCAL)?;
}
}
}
}
}
let fallthrough = self[block_idx].next;
let term = self[block_idx].basicblock_last_instr().copied();
if let Some(term) = term
&& fallthrough != BlockIdx::NULL
&& !term.instr.is_unconditional_jump()
&& !term.instr.is_scope_exit()
{
debug_assert!(self[block_idx].bb_has_fallthrough());
load_fast_push_block(&mut worklist, self, fallthrough, refs.size);
}
for i in 0..refs.size {
let r = ref_stack_at(&refs, i);
if r.instr != DUMMY_INSTR {
instr_flags[r.instr as usize] |= LoadFastInstrFlag::RefUnconsumed as u8;
}
}
let block = &mut self[block_idx];
let iused = block.instruction_used;
let mut i = 0;
while i < iused {
let info = &mut block.instructions[i];
if instr_flags[i] != 0 {
i += 1;
continue;
}
match info.instr.real_opcode() {
Some(Opcode::LoadFast) => {
info.instr = Opcode::LoadFastBorrow.into();
}
Some(Opcode::LoadFastLoadFast) => {
info.instr = Opcode::LoadFastBorrowLoadFastBorrow.into();
}
_ => {}
}
i += 1;
}
}
Ok(())
}
fn propagate_line_numbers(&mut self) {
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
let Some(last) = self[current].basicblock_last_instr().copied() else {
current = self[current].next;
continue;
};
let mut prev_location = no_instruction_location();
for i in 0..self[current].instruction_used {
if self[current].instructions[i].instruction_is_no_location() {
self[current].instructions[i].instr_set_location(prev_location);
} else {
prev_location = self[current].instructions[i].instr_location();
}
}
let next = self[current].next;
if self[current].bb_has_fallthrough() {
debug_assert!(next != BlockIdx::NULL);
if next != BlockIdx::NULL
&& self[next].predecessors == 1
&& self[next].instruction_used != 0
&& self[next].instructions[0].instruction_is_no_location()
{
self[next].instructions[0].instr_set_location(prev_location);
}
}
if last.is_jump() {
let target = last.target;
debug_assert!(target != BlockIdx::NULL);
if self[target].predecessors == 1 {
let instr = self[target].basicblock_raw_first_instr_mut();
if instr.instruction_is_no_location() {
instr.instr_set_location(prev_location);
}
}
}
current = self[current].next;
}
}
/// flowgraph.c remove_redundant_nops_and_pairs
fn remove_redundant_nops_and_pairs(&mut self) {
let mut done = false;
while !done {
done = true;
let mut instr: Option = None;
let mut block_idx = BlockIdx::new(0);
while block_idx != BlockIdx::NULL {
self.basicblock_remove_redundant_nops(block_idx);
if is_label(self[block_idx].cpython_label) {
instr = None;
}
let len = self[block_idx].instruction_used;
for instr_idx in 0..len {
let prev_instr = instr;
instr = Some((block_idx, instr_idx));
let instr_info = self[block_idx].instructions[instr_idx];
let mut prev_opcode = None;
let prev_oparg = if let Some((prev_block, prev_instr_idx)) = prev_instr {
let prev_info = self[prev_block].instructions[prev_instr_idx];
prev_opcode = prev_info.instr.real_opcode();
match prev_info.instr.real() {
Some(Instruction::Copy { i }) => i.get(prev_info.arg),
_ => u32::from(prev_info.arg),
}
} else {
0
};
let opcode = instr_info.instr.real_opcode();
let is_redundant_pair = matches!(opcode, Some(Opcode::PopTop))
&& (matches!(
prev_opcode,
Some(
Opcode::LoadConst
| Opcode::LoadSmallInt
| Opcode::LoadCommonConstant
)
) || (prev_oparg == 1 && matches!(prev_opcode, Some(Opcode::Copy))));
if is_redundant_pair {
let (prev_block, prev_instr_idx) =
prev_instr.expect("redundant pair has previous");
self[prev_block].instructions[prev_instr_idx].set_to_nop();
self[block_idx].instructions[instr_idx].set_to_nop();
done = false;
}
}
let instr_is_jump = instr.is_some_and(|(instr_block, instr_idx)| {
self[instr_block].instructions[instr_idx].is_jump()
});
let block = &self[block_idx];
if instr_is_jump || !block.bb_has_fallthrough() {
instr = None;
}
block_idx = block.next;
}
}
}
/// flowgraph.c calculate_stackdepth
fn calculate_stackdepth(&mut self) -> crate::InternalResult {
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
self[current.idx()].start_depth = START_DEPTH_UNSET;
current = self[current.idx()].next;
}
let mut stack = self.make_cfg_traversal_stack()?;
let mut maxdepth = 0i32;
stackdepth_push(&mut stack, self, BlockIdx(0), 0)?;
while let Some(block_idx) = stack.pop() {
let mut depth = self[block_idx].start_depth;
debug_assert!(depth >= 0);
let mut next = self[block_idx].next;
let instr_count = self[block_idx].instruction_used;
for i in 0..instr_count {
let ins = self[block_idx].instructions[i];
let instr = &ins.instr;
let effects = get_stack_effects(*instr, ins.arg, 0)?;
let new_depth = depth + effects.net;
if new_depth < 0 {
return Err(InternalError::StackUnderflow);
}
maxdepth = maxdepth.max(depth);
if instr.has_target() && !matches!(instr.real(), Some(Instruction::EndAsyncFor)) {
debug_assert!(ins.target != BlockIdx::NULL);
let effects = get_stack_effects(*instr, ins.arg, 1)?;
let target_depth = depth + effects.net;
debug_assert!(target_depth >= 0);
maxdepth = maxdepth.max(depth);
stackdepth_push(&mut stack, self, ins.target, target_depth)?;
}
depth = new_depth;
debug_assert!(!instr.is_assembler());
if instr.is_unconditional_jump() || instr.is_scope_exit() {
next = BlockIdx::NULL;
break;
}
}
if next != BlockIdx::NULL {
debug_assert!(self[block_idx].bb_has_fallthrough());
stackdepth_push(&mut stack, self, next, depth)?;
}
}
let stackdepth = maxdepth;
Ok(stackdepth as u32)
}
/// flowgraph.c make_cfg_traversal_stack
fn make_cfg_traversal_stack(&mut self) -> crate::InternalResult {
debug_assert!(!self.is_empty());
let mut nblocks = 0;
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
self[current].visited = false;
nblocks += 1;
current = self[current].next;
}
debug_assert!(nblocks > 0);
let mut stack = Vec::new();
stack
.try_reserve_exact(nblocks)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
stack.resize(nblocks, BlockIdx::NULL);
let stack = CfgTraversalStack { stack, sp: 0 };
debug_assert_eq!(stack.capacity(), nblocks);
Ok(stack)
}
/// flowgraph.c normalize_jumps
fn normalize_jumps(&mut self) -> crate::InternalResult {
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
self[current].visited = false;
current = self[current].next;
}
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
self[current].visited = true;
self.normalize_jumps_in_block(current)?;
current = self[current].next;
}
Ok(())
}
/// flowgraph.c remove_unused_consts
fn remove_unused_consts(&mut self, consts: &mut ConstantPool) -> crate::InternalResult {
let nconsts = consts.len();
if nconsts == 0 {
return Ok(());
}
let mut index_map = Vec::new();
index_map
.try_reserve_exact(nconsts)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
index_map.resize(nconsts, 0isize);
index_map[1..nconsts].fill(-1);
// The first constant may be docstring; keep it always.
index_map[0] = 0;
// Mark used consts.
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let block = &self[block_idx];
for instr in block.instructions.iter().take(block.instruction_used) {
if instr.instr.has_const() {
let index = u32::from(instr.arg) as usize;
debug_assert!(index < nconsts);
index_map[index] = index as isize;
}
}
block_idx = block.next;
}
// Now index_map[i] == i if consts[i] is used, -1 otherwise.
// Condense consts.
let mut n_used_consts = 0;
for i in 0..nconsts {
if index_map[i] != -1 {
debug_assert_eq!(index_map[i], i as isize);
index_map[n_used_consts] = index_map[i];
n_used_consts += 1;
}
}
if n_used_consts == nconsts {
return Ok(());
}
// Move all used consts to the beginning of the consts list.
debug_assert!(n_used_consts < nconsts);
for (i, item) in index_map.iter().enumerate().take(n_used_consts) {
let old_index = *item as usize;
debug_assert!(i = 0);
debug_assert!(reverse_index_map[index] < n_used_consts as isize);
instr.arg = OpArg::new(reverse_index_map[index] as u32);
}
}
block_idx = next_block;
}
Ok(())
}
/// flowgraph.c insert_superinstructions
fn insert_superinstructions(&mut self) -> usize {
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next_block = self[block_idx].next;
let block = &mut self[block_idx];
for i in 0..block.instruction_used {
let nextop = (i + 1 < block.instruction_used)
.then(|| block.instructions[i + 1].instr.real_opcode())
.flatten();
let super_op = match (block.instructions[i].instr.real_opcode(), nextop) {
(Some(Opcode::LoadFast), Some(Opcode::LoadFast)) => {
Some(Opcode::LoadFastLoadFast)
}
(Some(Opcode::StoreFast), Some(Opcode::LoadFast)) => {
Some(Opcode::StoreFastLoadFast)
}
(Some(Opcode::StoreFast), Some(Opcode::StoreFast)) => {
Some(Opcode::StoreFastStoreFast)
}
(_, _) => None,
};
if let Some(super_op) = super_op {
let (inst1, rest) = block.instructions[i..].split_at_mut(1);
InstructionInfo::make_super_instruction(
&mut inst1[0],
&mut rest[0],
super_op.into(),
);
}
}
block_idx = next_block;
}
let res = self.remove_redundant_nops();
#[cfg(debug_assertions)]
assert!(self.no_redundant_nops());
res
}
/// Mark exception handler target blocks.
/// flowgraph.c mark_except_handlers
pub(crate) fn mark_except_handlers(&mut self) {
#[cfg(debug_assertions)]
{
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
assert!(!self[block_idx].except_handler);
block_idx = self[block_idx].next;
}
}
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next = self[block_idx].next;
let instr_count = self[block_idx].instruction_used;
for i in 0..instr_count {
let instr = self[block_idx].instructions[i];
if instr.is_block_push() {
debug_assert!(instr.target != BlockIdx::NULL);
self[instr.target].except_handler = true;
}
}
block_idx = next;
}
}
/// flowgraph.c mark_cold (two-pass).
///
/// Phase 1 (mark_warm): propagate "warm" from entry via fall-through and
/// jump targets. The pass asserts while visiting warm blocks that they are not
/// exception handlers.
///
/// Phase 2 (mark_cold): propagate "cold" from except_handler blocks via
/// forward edges. Blocks reached only via runtime exception dispatch are
/// marked cold and pushed to the end by push_cold_blocks_to_end.
///
/// Blocks reached by neither phase remain `cold=false`. They are typically
/// empty unreachable placeholders left by remove_unreachable; they stay in
/// their original chain position (e.g. between entry and the post-try
/// continuation for a nested try/except whose inner_end was emptied by
/// optimize_cfg). This is necessary for
/// optimize_load_fast to terminate fall-through at those placeholders.
/// flowgraph.c mark_warm
fn mark_warm(&mut self) -> crate::InternalResult {
let mut stack = self.make_cfg_traversal_stack()?;
stack.push(BlockIdx(0));
self[0].visited = true;
while let Some(block_idx) = stack.pop() {
debug_assert!(!self[block_idx].except_handler);
self[block_idx].warm = true;
let next = self[block_idx].next;
if next != BlockIdx::NULL && self[block_idx].bb_has_fallthrough() && !self[next].visited
{
stack.push(next);
self[next].visited = true;
}
let instr_count = self[block_idx].instruction_used;
for i in 0..instr_count {
let instr = self[block_idx].instructions[i];
if instr.is_jump() {
let target = instr.target;
debug_assert!(target != BlockIdx::NULL);
if !self[target].visited {
stack.push(target);
self[target].visited = true;
}
}
}
}
Ok(())
}
fn mark_cold(&mut self) -> crate::InternalResult {
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let block = &mut self[block_idx];
debug_assert!(!block.cold);
debug_assert!(!block.warm);
block_idx = block.next;
}
self.mark_warm()?;
let mut cold_stack = self.make_cfg_traversal_stack()?;
block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next = self[block_idx].next;
let block = &self[block_idx];
if block.except_handler {
debug_assert!(!block.warm);
cold_stack.push(block_idx);
self[block_idx].visited = true;
}
block_idx = next;
}
while let Some(block_idx) = cold_stack.pop() {
self[block_idx].cold = true;
let next = self[block_idx].next;
if next != BlockIdx::NULL
&& self[block_idx].bb_has_fallthrough()
&& !self[next].warm
&& !self[next].visited
{
cold_stack.push(next);
self[next].visited = true;
}
let instr_count = self[block_idx].instruction_used;
for i in 0..instr_count {
let instr = self[block_idx].instructions[i];
if instr.is_jump() {
debug_assert_eq!(i, instr_count - 1);
let target = instr.target;
debug_assert!(target != BlockIdx::NULL);
if !self[target].warm && !self[target].visited {
cold_stack.push(target);
self[target].visited = true;
}
}
}
}
Ok(())
}
/// flowgraph.c push_cold_blocks_to_end
fn push_cold_blocks_to_end(&mut self) -> crate::InternalResult {
if self[0].next == BlockIdx::NULL {
return Ok(());
}
self.mark_cold()?;
let mut next_label = get_max_label(self) + 1;
// If a cold block falls through to a warm block, add an explicit jump
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next = self[block_idx].next;
if self[block_idx].cold
&& self[block_idx].bb_has_fallthrough()
&& next != BlockIdx::NULL
&& self[next].warm
{
let explicit_jump = self.blocks_new_block()?;
if !is_label(self[next].cpython_label) {
self[next].cpython_label = InstructionSequenceLabel::from_index(next_label);
next_label += 1;
}
let jump_label = self[next].cpython_label;
debug_assert!(is_label(jump_label));
self[explicit_jump].basicblock_addop(InstructionInfo {
instr: PseudoOpcode::JumpNoInterrupt.into(),
arg: instruction_sequence_label_oparg(jump_label),
target: BlockIdx::NULL,
location: SourceLocation::default(),
end_location: SourceLocation::default(),
except_handler: None,
semantic_location: None,
lineno_override: Some(NO_LOCATION_OVERRIDE),
})?;
self[explicit_jump].cold = true;
self[explicit_jump].next = next;
self[explicit_jump].predecessors = 1;
self[block_idx].next = explicit_jump;
let target = self[explicit_jump].next;
let last = self[explicit_jump]
.basicblock_last_instr_mut()
.expect("missing explicit jump");
last.target = target;
}
block_idx = self[block_idx].next;
}
assert!(!self[0].cold);
let mut cold_blocks: BlockIdx = BlockIdx::NULL;
let mut cold_blocks_tail: BlockIdx = BlockIdx::NULL;
let mut block_idx = BlockIdx(0);
while self[block_idx].next != BlockIdx::NULL {
debug_assert!(!self[block_idx].cold);
while self[block_idx].next != BlockIdx::NULL && !self[self[block_idx].next].cold {
block_idx = self[block_idx].next;
}
if self[block_idx].next == BlockIdx::NULL {
break;
}
debug_assert!(!self[block_idx].cold);
debug_assert!(self[self[block_idx].next].cold);
let mut block_end = self[block_idx].next;
while self[block_end].next != BlockIdx::NULL && self[self[block_end].next].cold {
block_end = self[block_end].next;
}
debug_assert!(self[block_end].cold);
debug_assert!(
self[block_end].next == BlockIdx::NULL || !self[self[block_end].next].cold
);
if cold_blocks == BlockIdx::NULL {
cold_blocks = self[block_idx].next;
} else {
self[cold_blocks_tail].next = self[block_idx].next;
}
cold_blocks_tail = block_end;
self[block_idx].next = self[block_end].next;
self[block_end].next = BlockIdx::NULL;
}
debug_assert!(self[block_idx].next == BlockIdx::NULL);
self[block_idx].next = cold_blocks;
if cold_blocks != BlockIdx::NULL {
self.remove_redundant_nops_and_jumps()?;
}
Ok(())
}
/// flowgraph.c check_cfg
fn check_cfg(&self) -> crate::InternalResult {
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let block = &self[block_idx];
for i in 0..block.instruction_used {
let opcode = block.instructions[i].instr;
debug_assert!(!opcode.is_assembler());
if opcode.is_terminator() && i != block.instruction_used - 1 {
return Err(InternalError::MalformedControlFlowGraph);
}
}
block_idx = block.next;
}
Ok(())
}
/// flowgraph.c jump_thread
fn jump_thread(
&mut self,
block_idx: BlockIdx,
instr_idx: usize,
target: &InstructionInfo,
opcode: AnyInstruction,
) -> crate::InternalResult {
debug_assert!(self[block_idx].instructions[instr_idx].is_jump());
debug_assert!(target.is_jump());
debug_assert_eq!(instr_idx + 1, self[block_idx].instruction_used);
debug_assert!(target.target != BlockIdx::NULL);
if self[block_idx].instructions[instr_idx].target != target.target {
self[block_idx].instructions[instr_idx].set_to_nop();
self.basicblock_add_jump(block_idx, opcode, target.target, target)?;
return Ok(true);
}
Ok(false)
}
/// flowgraph.c basicblock_add_jump
fn basicblock_add_jump(
&mut self,
block_idx: BlockIdx,
instr: AnyInstruction,
target: BlockIdx,
loc_source: &InstructionInfo,
) -> crate::InternalResult {
let last = self[block_idx].basicblock_last_instr();
if last.is_some_and(|l| l.is_jump()) {
return Err(InternalError::MalformedControlFlowGraph);
}
debug_assert!(target != BlockIdx::NULL);
let label = self[target].cpython_label;
debug_assert!(is_label(label));
let arg = instruction_sequence_label_oparg(label);
let block = &mut self[block_idx];
block.basicblock_addop(InstructionInfo {
instr,
arg,
target: BlockIdx::NULL,
location: loc_source.location,
end_location: loc_source.end_location,
except_handler: None,
semantic_location: loc_source.semantic_location,
lineno_override: loc_source.lineno_override,
})?;
let last = block.basicblock_last_instr_mut().expect("missing jump");
debug_assert!(match (last.instr, instr) {
(AnyInstruction::Real(last), AnyInstruction::Real(opcode)) =>
last.as_opcode() == opcode.as_opcode(),
(AnyInstruction::Pseudo(last), AnyInstruction::Pseudo(opcode)) =>
last.as_opcode() == opcode.as_opcode(),
_ => false,
});
last.target = target;
Ok(())
}
/// flowgraph.c convert_pseudo_conditional_jumps
fn convert_pseudo_conditional_jumps(&mut self) -> crate::InternalResult {
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next = self[block_idx].next;
let block = &mut self[block_idx];
let mut i = 0;
while i < block.instruction_used {
let instr = block.instructions[i];
let opcode = instr.instr;
if matches!(
opcode.pseudo_opcode(),
Some(PseudoOpcode::JumpIfFalse | PseudoOpcode::JumpIfTrue)
) {
debug_assert_eq!(i, block.instruction_used - 1);
block.instructions[i].instr =
if matches!(opcode.pseudo_opcode(), Some(PseudoOpcode::JumpIfFalse)) {
Opcode::PopJumpIfFalse
} else {
Opcode::PopJumpIfTrue
}
.into();
let location = instr.location;
let end_location = instr.end_location;
let except_handler = instr.except_handler;
let semantic_location = instr.semantic_location;
let lineno_override = instr.lineno_override;
let copy = InstructionInfo {
instr: Opcode::Copy.into(),
arg: OpArg::new(1),
target: BlockIdx::NULL,
location,
end_location,
except_handler,
semantic_location,
lineno_override,
};
block.basicblock_insert_instruction(i, copy)?;
i += 1;
let to_bool = InstructionInfo {
instr: Opcode::ToBool.into(),
arg: OpArg::new(0),
target: BlockIdx::NULL,
location,
end_location,
except_handler,
semantic_location,
lineno_override,
};
block.basicblock_insert_instruction(i, to_bool)?;
i += 1;
}
i += 1;
}
block_idx = next;
}
Ok(())
}
/// flowgraph.c normalize_jumps_in_block
fn normalize_jumps_in_block(&mut self, block_idx: BlockIdx) -> crate::InternalResult {
let Some(last_ins) = self[block_idx].basicblock_last_instr().copied() else {
return Ok(());
};
if !is_conditional_jump_opcode(last_ins.instr) {
return Ok(());
}
debug_assert!(!last_ins.instr.is_assembler());
debug_assert!(last_ins.target != BlockIdx::NULL);
let is_forward = !self[last_ins.target].visited;
if is_forward {
// Insert NOT_TAKEN after forward conditional jump.
let not_taken = InstructionInfo {
instr: Opcode::NotTaken.into(),
arg: OpArg::new(0),
target: BlockIdx::NULL,
location: last_ins.location,
end_location: last_ins.end_location,
except_handler: None,
semantic_location: last_ins.semantic_location,
lineno_override: last_ins.lineno_override,
};
self[block_idx].basicblock_addop(not_taken)?;
return Ok(());
}
let reversed_opcode = match last_ins.instr.real_opcode() {
Some(Opcode::PopJumpIfNotNone) => Opcode::PopJumpIfNone.into(),
Some(Opcode::PopJumpIfNone) => Opcode::PopJumpIfNotNone.into(),
Some(Opcode::PopJumpIfFalse) => Opcode::PopJumpIfTrue.into(),
Some(Opcode::PopJumpIfTrue) => Opcode::PopJumpIfFalse.into(),
_ => unreachable!("conditional jump has reverse opcode"),
};
// Transform 'conditional jump T' to 'reversed_jump b_next' followed by
// 'jump_backwards T'.
let loc = last_ins.location;
let end_loc = last_ins.end_location;
let target = last_ins.target;
let backwards_jump_idx = self.blocks_new_block()?;
self[backwards_jump_idx].basicblock_addop(InstructionInfo {
instr: Opcode::NotTaken.into(),
arg: OpArg::new(0),
target: BlockIdx::NULL,
location: loc,
end_location: end_loc,
except_handler: None,
semantic_location: last_ins.semantic_location,
lineno_override: last_ins.lineno_override,
})?;
self.basicblock_add_jump(
backwards_jump_idx,
PseudoOpcode::Jump.into(),
target,
&last_ins,
)?;
self[backwards_jump_idx].start_depth = self[target].start_depth;
let old_next = self[block_idx].next;
debug_assert!(old_next != BlockIdx::NULL);
let last_mut = self[block_idx].basicblock_last_instr_mut().unwrap();
last_mut.instr = reversed_opcode;
last_mut.target = old_next;
self[backwards_jump_idx].cold = self[block_idx].cold;
self[backwards_jump_idx].next = old_next;
self[block_idx].next = backwards_jump_idx;
Ok(())
}
/// flowgraph.c basicblock_inline_small_or_no_lineno_blocks
fn basicblock_inline_small_or_no_lineno_blocks(
&mut self,
block_idx: BlockIdx,
) -> crate::InternalResult {
let Some(last) = self[block_idx].basicblock_last_instr().copied() else {
return Ok(false);
};
if !last.instr.is_unconditional_jump() {
return Ok(false);
}
let target = last.target;
debug_assert!(target != BlockIdx::NULL);
let small_exit_block =
self[target].basicblock_exits_scope() && self[target].instruction_used crate::InternalResult {
loop {
let mut changes = false;
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
let next = self[current].next;
let res = self.basicblock_inline_small_or_no_lineno_blocks(current)?;
if res {
changes = true;
}
current = next;
}
if !changes {
return Ok(changes);
}
}
}
/// flowgraph.c basicblock_remove_redundant_nops
fn basicblock_remove_redundant_nops(&mut self, block_idx: BlockIdx) -> usize {
let mut dest = 0;
let mut prev_lineno = -1i32;
let instr_count = self[block_idx].instruction_used;
for src in 0..instr_count {
let instr = self[block_idx].instructions[src];
let lineno = instr.instruction_lineno();
if matches!(instr.instr.real(), Some(Instruction::Nop)) {
if lineno < 0 {
continue;
}
if prev_lineno == lineno {
continue;
}
if src < instr_count - 1 {
let next_lineno = self[block_idx].instructions[src + 1].instruction_lineno();
if next_lineno == lineno {
continue;
}
if next_lineno < 0 {
self[block_idx].instructions[src + 1]
.instr_set_location(instr.instr_location());
continue;
}
} else {
let next = next_nonempty_block(self, self[block_idx].next);
if next != BlockIdx::NULL {
let mut next_loc = no_linetable_location();
let mut next_i = 0;
while next_i < self[next].instruction_used {
let instr = self[next].instructions[next_i];
if matches!(instr.instr.real(), Some(Instruction::Nop))
&& instr.instruction_lineno() < 0
{
next_i += 1;
continue;
}
next_loc = instr.instruction_linetable_location();
break;
}
if lineno == next_loc.line {
continue;
}
}
}
}
if dest != src {
self[block_idx].instructions[dest] = self[block_idx].instructions[src];
}
dest += 1;
prev_lineno = lineno;
}
debug_assert!(dest usize {
let mut changes = 0;
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
let next = self[current].next;
let change = self.basicblock_remove_redundant_nops(current);
changes += change;
current = next;
}
changes
}
/// flowgraph.c no_redundant_nops
#[cfg(debug_assertions)]
fn no_redundant_nops(&mut self) -> bool {
self.remove_redundant_nops() == 0
}
/// flowgraph.c remove_redundant_jumps
fn remove_redundant_jumps(&mut self) -> crate::InternalResult {
let mut changes = 0;
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
let Some(last) = self[current].basicblock_last_instr().copied() else {
current = self[current].next;
continue;
};
debug_assert!(!last.instr.is_assembler());
if last.instr.is_unconditional_jump() {
let jump_target = next_nonempty_block(self, last.target);
if jump_target == BlockIdx::NULL {
return Err(InternalError::MalformedControlFlowGraph);
}
let next = next_nonempty_block(self, self[current].next);
if jump_target == next {
changes += 1;
let last = self[current].basicblock_last_instr_mut().unwrap();
last.set_to_nop();
}
}
current = self[current].next;
}
Ok(changes)
}
/// flowgraph.c no_redundant_jumps
#[cfg(debug_assertions)]
fn no_redundant_jumps(&self) -> bool {
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
let block = &self[current];
if let Some(last) = block.basicblock_last_instr()
&& last.instr.is_unconditional_jump()
{
let next = next_nonempty_block(self, block.next);
let jump_target = next_nonempty_block(self, last.target);
if jump_target == next {
assert!(next != BlockIdx::NULL);
if last.instruction_lineno() == self[next].instructions[0].instruction_lineno()
{
assert_ne!(
last.instruction_lineno(),
self[next].instructions[0].instruction_lineno(),
"redundant jump has same line as fallthrough target"
);
return false;
}
}
}
current = block.next;
}
true
}
fn remove_redundant_nops_and_jumps(&mut self) -> crate::InternalResult {
loop {
// Convergence is guaranteed because the number of redundant jumps and
// nops only decreases.
let removed_nops = self.remove_redundant_nops();
let removed_jumps = self.remove_redundant_jumps()?;
if removed_nops + removed_jumps == 0 {
break;
}
}
Ok(())
}
fn blocks_new_block(&mut self) -> crate::InternalResult {
self.try_reserve(1)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
let block_idx = BlockIdx(
self.len()
.to_u32()
.ok_or(InternalError::MalformedControlFlowGraph)?,
);
self.push(Block::default());
Ok(block_idx)
}
}
impl From for Blocks {
fn from(value: [Block; N]) -> Self {
Self(value.into())
}
}
impl Deref for Blocks {
type Target = [Block];
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl DerefMut for Blocks {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl Index for Blocks {
type Output = Block;
fn index(&self, idx: usize) -> &Self::Output {
&self.0[idx]
}
}
impl IndexMut for Blocks {
fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
&mut self.0[idx]
}
}
impl Index for Blocks {
type Output = Block;
fn index(&self, block_idx: BlockIdx) -> &Self::Output {
&self.0[block_idx.as_usize()]
}
}
impl IndexMut for Blocks {
fn index_mut(&mut self, block_idx: BlockIdx) -> &mut Self::Output {
&mut self.0[block_idx.as_usize()]
}
}
pub(crate) const START_DEPTH_UNSET: i32 = i32::MIN;
const CO_MAXBLOCKS: usize = 21;
/// flowgraph.c struct _PyCfgExceptStack
#[derive(Clone, Debug)]
struct CfgExceptStack {
handlers: [BlockIdx; CO_MAXBLOCKS + 2],
depth: usize,
}
/// flowgraph.c `basicblock **stack`
#[derive(Clone, Debug)]
struct CfgTraversalStack {
stack: Vec,
sp: usize,
}
impl CfgTraversalStack {
fn push(&mut self, block: BlockIdx) {
debug_assert!(self.sp < self.stack.len());
self.stack[self.sp] = block;
self.sp += 1;
}
fn pop(&mut self) -> Option {
if self.sp == 0 {
return None;
}
self.sp -= 1;
Some(self.stack[self.sp])
}
fn capacity(&self) -> usize {
self.stack.len()
}
}
#[derive(Clone, Debug)]
pub(crate) struct InstructionSequenceLabelMap {
block_labels: Vec,
/// Codegen-side shadow of the instruction-sequence label map.
///
/// `_PyInstructionSequence_UseLabel()` can map multiple labels to the same
/// instruction offset before `_PyCfg_FromInstructionSequence()` materializes
/// CFG blocks. The codegen CFG path keeps the same aliasing by resolving
/// those labels to the block that owns the shared offset.
cpython_block_by_label: Vec,
}
fn instruction_sequence_label_map_register_label(
map: &mut InstructionSequenceLabelMap,
label: InstructionSequenceLabel,
) -> crate::InternalResult {
debug_assert!(is_label(label));
let old_size = map.cpython_block_by_label.len();
let new_allocation = c_array_ensure_capacity::(
old_size,
label.idx(),
INITIAL_INSTR_SEQUENCE_LABELS_MAP_SIZE,
)?;
if new_allocation > old_size {
if new_allocation > map.cpython_block_by_label.capacity() {
map.cpython_block_by_label
.try_reserve_exact(new_allocation - map.cpython_block_by_label.capacity())
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
}
map.cpython_block_by_label
.resize(new_allocation, BlockIdx::NULL);
for i in old_size..map.cpython_block_by_label.len() {
map.cpython_block_by_label[i] = BlockIdx::NULL;
}
}
debug_assert!(map.cpython_block_by_label.len() > label.idx());
Ok(())
}
fn instruction_sequence_label_map_ensure_label_for_block(
map: &mut InstructionSequenceLabelMap,
seq: &mut InstructionSequence,
block: BlockIdx,
) -> crate::InternalResult {
debug_assert_ne!(block, BlockIdx::NULL);
let block_label = map.block_labels[block.idx()];
if is_label(block_label) {
return Ok(block_label);
}
let label = instruction_sequence_new_label(seq);
debug_assert_eq!(label.0, seq.next_free_label);
instruction_sequence_label_map_register_label(map, label)?;
map.cpython_block_by_label[label.idx()] = block;
map.block_labels[block.idx()] = label;
Ok(label)
}
fn instruction_sequence_label_map_label_for_block(
map: &InstructionSequenceLabelMap,
block: BlockIdx,
) -> InstructionSequenceLabel {
debug_assert_ne!(block, BlockIdx::NULL);
map.block_labels
.get(block.idx())
.copied()
.unwrap_or(InstructionSequenceLabel::NO_LABEL)
}
fn instruction_sequence_label_map_block_for_label(
map: &InstructionSequenceLabelMap,
label: InstructionSequenceLabel,
) -> Option {
if !is_label(label) {
return None;
}
map.cpython_block_by_label
.get(label.idx())
.copied()
.filter(|&block| block != BlockIdx::NULL)
}
fn instruction_sequence_label_map_resolve_label(
map: &InstructionSequenceLabelMap,
block: BlockIdx,
) -> BlockIdx {
if block == BlockIdx::NULL {
return BlockIdx::NULL;
}
let label = instruction_sequence_label_map_label_for_block(map, block);
if !is_label(label) {
return block;
}
instruction_sequence_label_map_block_for_label(map, label).unwrap_or_else(|| {
debug_assert!(
false,
"CPython instruction-sequence label must map to a codegen CFG block"
);
BlockIdx::NULL
})
}
fn instruction_sequence_label_map_resolve_label_to_block(
map: &InstructionSequenceLabelMap,
label: InstructionSequenceLabel,
) -> BlockIdx {
if !is_label(label) {
return BlockIdx::NULL;
}
instruction_sequence_label_map_block_for_label(map, label).unwrap_or_else(|| {
debug_assert!(
false,
"CPython instruction-sequence label must map to a codegen CFG block"
);
BlockIdx::NULL
})
}
fn instruction_sequence_label_oparg(label: InstructionSequenceLabel) -> OpArg {
debug_assert!(is_label(label));
OpArg::new(label.idx() as u32)
}
fn instruction_sequence_label_map_use_label_at_block(
map: &mut InstructionSequenceLabelMap,
seq: &mut InstructionSequence,
from: BlockIdx,
to: BlockIdx,
) -> crate::InternalResult {
if from == BlockIdx::NULL || from == to {
return Ok(());
}
let from_label = instruction_sequence_label_map_ensure_label_for_block(map, seq, from)?;
debug_assert!(map.cpython_block_by_label.len() > from_label.idx());
let to_block = instruction_sequence_label_map_resolve_label(map, to);
if to_block == BlockIdx::NULL {
debug_assert!(
false,
"CPython label target must map to a codegen CFG block"
);
return Ok(());
}
map.cpython_block_by_label[from_label.idx()] = to_block;
Ok(())
}
fn instruction_sequence_label_map_push_unlabeled_block(
map: &mut InstructionSequenceLabelMap,
) -> crate::InternalResult {
map.block_labels
.try_reserve(1)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
map.block_labels.push(InstructionSequenceLabel::NO_LABEL);
Ok(())
}
fn instruction_sequence_label_map_push_unmapped_label(
map: &mut InstructionSequenceLabelMap,
seq: &mut InstructionSequence,
) -> crate::InternalResult {
let label = instruction_sequence_new_label(seq);
debug_assert_eq!(label.0, seq.next_free_label);
instruction_sequence_label_map_register_label(map, label)?;
let block = BlockIdx(
map.block_labels
.len()
.to_u32()
.ok_or(InternalError::MalformedControlFlowGraph)?,
);
map.cpython_block_by_label[label.idx()] = block;
map.block_labels
.try_reserve(1)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
map.block_labels.push(label);
Ok(())
}
impl InstructionSequenceLabelMap {
pub(crate) fn new() -> Self {
Self {
block_labels: vec![InstructionSequenceLabel::NO_LABEL],
cpython_block_by_label: Vec::new(),
}
}
}
pub struct CodeInfo {
pub flags: CodeFlags,
pub source_path: String,
pub private: Option, // For private name mangling, mostly for class
pub blocks: Blocks,
pub current_block: BlockIdx,
pub(crate) instr_sequence: InstructionSequence,
pub(crate) instr_sequence_label_map: InstructionSequenceLabelMap,
pub(crate) annotations_instr_sequence: Option,
pub metadata: CodeUnitMetadata,
// For class scopes: attributes accessed via self.X
pub static_attributes: Option,
// True if compiling an inlined comprehension
pub in_inlined_comp: bool,
// Block stack for tracking nested control structures
pub fblock: Vec,
// Reference to the symbol table for this scope
pub symbol_table_index: usize,
// compile.c uses PyList_GET_SIZE(u->u_ste->ste_varnames)
// when calling flowgraph.c _PyCfg_OptimizeCodeUnit().
pub nparams: usize,
// PEP 649: Track nesting depth inside conditional blocks (if/for/while/etc.)
// u_in_conditional_block
pub in_conditional_block: u32,
// PEP 649: Next index for conditional annotation tracking
// u_next_conditional_annotation_index
pub next_conditional_annotation_index: u32,
}
impl CodeInfo {
pub(crate) fn addop_to_instr_sequence(
&mut self,
mut info: InstructionInfo,
) -> crate::InternalResult {
if info.instr.has_target() && info.target != BlockIdx::NULL {
let label = instruction_sequence_label_map_ensure_label_for_block(
&mut self.instr_sequence_label_map,
&mut self.instr_sequence,
info.target,
)?;
info.arg = instruction_sequence_label_oparg(label);
info.target = BlockIdx::NULL;
}
instruction_sequence_addop(&mut self.instr_sequence, info)?;
Ok(())
}
pub(crate) fn addop_to_instr_sequence_with_target_label(
&mut self,
mut info: InstructionInfo,
target_label: InstructionSequenceLabel,
) -> crate::InternalResult {
if !info.instr.has_target() {
return Err(InternalError::MalformedControlFlowGraph);
}
info.arg = instruction_sequence_label_oparg(target_label);
info.target = BlockIdx::NULL;
instruction_sequence_addop(&mut self.instr_sequence, info)?;
Ok(())
}
pub(crate) fn addop_to_current_block(
&mut self,
info: InstructionInfo,
) -> crate::InternalResult {
self.blocks[self.current_block].basicblock_addop(info)
}
pub(crate) fn last_current_block_instr_mut(&mut self) -> Option {
self.blocks[self.current_block].basicblock_last_instr_mut()
}
pub(crate) fn set_last_instr_sequence_lineno_override(&mut self, lineno_override: i32) {
if let Some(last) = instruction_sequence_last_info_mut(&mut self.instr_sequence) {
last.lineno_override = Some(lineno_override);
}
}
pub(crate) fn use_instr_sequence_label(
&mut self,
block: BlockIdx,
) -> crate::InternalResult {
let label = instruction_sequence_label_map_ensure_label_for_block(
&mut self.instr_sequence_label_map,
&mut self.instr_sequence,
block,
)?;
instruction_sequence_use_label(&mut self.instr_sequence, label)
}
pub(crate) fn new_instr_sequence_label(&mut self) -> InstructionSequenceLabel {
instruction_sequence_new_label(&mut self.instr_sequence)
}
pub(crate) fn use_raw_instr_sequence_label(
&mut self,
label: InstructionSequenceLabel,
) -> crate::InternalResult {
instruction_sequence_use_label(&mut self.instr_sequence, label)
}
pub(crate) fn mark_cpython_cfg_label(&mut self, block: BlockIdx) -> crate::InternalResult {
let label = instruction_sequence_label_map_ensure_label_for_block(
&mut self.instr_sequence_label_map,
&mut self.instr_sequence,
block,
)?;
self.blocks[block].cpython_label = label;
Ok(())
}
pub(crate) fn resolve_instr_sequence_label(&self, block: BlockIdx) -> BlockIdx {
instruction_sequence_label_map_resolve_label(&self.instr_sequence_label_map, block)
}
pub(crate) fn block_for_instr_sequence_label(
&self,
label: InstructionSequenceLabel,
) -> BlockIdx {
instruction_sequence_label_map_resolve_label_to_block(&self.instr_sequence_label_map, label)
}
pub(crate) fn use_instr_sequence_label_at_block(
&mut self,
from: BlockIdx,
to: BlockIdx,
) -> crate::InternalResult {
instruction_sequence_label_map_use_label_at_block(
&mut self.instr_sequence_label_map,
&mut self.instr_sequence,
from,
to,
)
}
pub(crate) fn instr_sequence_label_for_block(
&mut self,
block: BlockIdx,
) -> crate::InternalResult {
if block == BlockIdx::NULL {
Ok(InstructionSequenceLabel::NO_LABEL)
} else {
instruction_sequence_label_map_ensure_label_for_block(
&mut self.instr_sequence_label_map,
&mut self.instr_sequence,
block,
)
}
}
/// Insert SETUP_CLEANUP just after the initial RETURN_GENERATOR; POP_TOP.
pub(crate) fn insert_start_setup_cleanup(
&mut self,
handler_block: BlockIdx,
) -> crate::InternalResult {
let handler_label = instruction_sequence_label_map_ensure_label_for_block(
&mut self.instr_sequence_label_map,
&mut self.instr_sequence,
handler_block,
)?;
let seq = &self.instr_sequence;
let opcode_at = |i: usize| seq.instrs[i].info.instr.real();
let mut resume = 0;
while !matches!(opcode_at(resume), Some(Instruction::ReturnGenerator)) {
resume += 1;
debug_assert!(resume < seq.instr_used);
}
resume += 1;
debug_assert!(matches!(opcode_at(resume), Some(Instruction::PopTop)));
resume += 1;
debug_assert!(resume < seq.instr_used);
instruction_sequence_insert_instruction(
&mut self.instr_sequence,
resume,
InstructionInfo {
instr: PseudoOpcode::SetupCleanup.into(),
arg: instruction_sequence_label_oparg(handler_label),
target: BlockIdx::NULL,
location: SourceLocation::default(),
end_location: SourceLocation::default(),
except_handler: None,
semantic_location: None,
lineno_override: Some(NO_LOCATION_OVERRIDE),
},
)
}
/// Insert `RESUME`, `LOAD_FAST 0` and the outermost `GET_ITER` (or
/// `GET_AITER`) before RETURN_GENERATOR.
pub(crate) fn insert_genexpr_prefix(
&mut self,
mut iterator: InstructionInfo,
) -> crate::InternalResult {
let mut resume = InstructionInfo::empty();
resume.instr_set_op1(
Opcode::Resume.into(),
OpArg::new(oparg::ResumeLocation::AtGenExprStart.into()),
);
resume.lineno_override = Some(NO_LOCATION_OVERRIDE);
let mut load = iterator;
load.instr_set_op1(Opcode::LoadFast.into(), OpArg::new(0));
iterator.arg = OpArg::new(0);
for (i, info) in [resume, load, iterator].into_iter().enumerate() {
instruction_sequence_insert_instruction(&mut self.instr_sequence, i, info)?;
}
Ok(())
}
pub(crate) fn push_unmapped_instr_sequence_label(&mut self) -> crate::InternalResult {
instruction_sequence_label_map_push_unmapped_label(
&mut self.instr_sequence_label_map,
&mut self.instr_sequence,
)
}
pub(crate) fn push_unlabeled_instr_sequence_block(&mut self) -> crate::InternalResult {
instruction_sequence_label_map_push_unlabeled_block(&mut self.instr_sequence_label_map)
}
fn take_recorded_instr_sequence(&mut self) -> InstructionSequence {
let mut instr_sequence =
core::mem::replace(&mut self.instr_sequence, instruction_sequence_new());
if let Some(mut annotations_instr_sequence) = self.annotations_instr_sequence.take() {
instruction_sequence_apply_label_map(&mut annotations_instr_sequence);
instruction_sequence_set_annotations_code(
&mut instr_sequence,
Some(Box::new(annotations_instr_sequence)),
);
}
instr_sequence
}
fn prepare_cfg_from_codegen(&mut self) -> InstructionSequence {
// compile.c optimize_and_assemble_code_unit passes
// u_instr_sequence directly into flowgraph.c _PyCfg_FromInstructionSequence().
self.take_recorded_instr_sequence()
}
}
fn optimize_code_unit(
metadata: &mut CodeUnitMetadata,
blocks: &mut Blocks,
instr_sequence: InstructionSequence,
nlocals: usize,
nparams: usize,
) -> crate::InternalResult {
// Phase 1: _PyCfg_OptimizeCodeUnit (flowgraph.c)
*blocks = cfg_from_instruction_sequence(instr_sequence)?;
translate_jump_labels_to_targets(blocks)?;
blocks.mark_except_handlers();
label_exception_targets(blocks)?;
optimize_cfg(metadata, blocks, metadata.firstlineno)?;
blocks.remove_unused_consts(&mut metadata.consts)?;
add_checks_for_loads_of_uninitialized_variables(blocks, nlocals, nparams)?;
// Superinstructions are inserted in _PyCfg_OptimizeCodeUnit, before
// later jump normalization / block reordering can create adjacencies
// that never exist at this stage in flowgraph.c.
blocks.insert_superinstructions();
blocks.push_cold_blocks_to_end()?;
// Line numbers are resolved again after cold-block extraction.
blocks.resolve_line_numbers(metadata.firstlineno)?;
Ok(())
}
fn optimize_cfg(
metadata: &mut CodeUnitMetadata,
blocks: &mut Blocks,
firstlineno: OneIndexed,
) -> crate::InternalResult {
// flowgraph.c optimize_cfg
// optimize_cfg() starts with check_cfg() and raises
// SystemError if a jump or scope exit is not the last instruction in
// its block.
blocks.check_cfg()?;
blocks.inline_small_or_no_lineno_blocks()?;
// The instruction-sequence label-map/CFG conversion is not re-run
// after this point. Unreferenced label blocks left by jump inlining
// remain block boundaries and can preserve line-marker NOPs.
blocks.remove_unreachable()?;
// optimize_cfg resolves line numbers before local checks and
// superinstruction insertion, so fusion decisions see propagated
// source locations.
blocks.resolve_line_numbers(firstlineno)?;
// optimize_cfg() runs optimize_load_const() and then
// optimize_basic_block() after line numbers are resolved.
optimize_load_const(metadata, blocks)?;
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next_block = blocks[block_idx].next;
blocks.optimize_basic_block(metadata, block_idx)?;
block_idx = next_block;
}
blocks.remove_redundant_nops_and_pairs();
// optimize_cfg() removes newly-unreachable blocks and
// redundant NOP/jump chains before _PyCfg_OptimizeCodeUnit() prunes
// unused constants.
blocks.remove_unreachable()?;
blocks.remove_redundant_nops_and_jumps()?;
#[cfg(debug_assertions)]
assert!(blocks.no_redundant_jumps());
Ok(())
}
fn optimized_cfg_to_instruction_sequence(
metadata: &CodeUnitMetadata,
flags: CodeFlags,
blocks: &mut Blocks,
) -> crate::InternalResult {
// Phase 2: _PyCfg_OptimizedCfgToInstructionSequence (flowgraph.c)
blocks.convert_pseudo_conditional_jumps()?;
let max_stackdepth = blocks.calculate_stackdepth()?;
debug_assert!(!is_generator(flags) || max_stackdepth != 0);
let nlocalsplus = prepare_localsplus(metadata, blocks)?;
// Pseudo ops are lowered after stackdepth and
// localsplus preparation, before normalize_jumps.
convert_pseudo_ops(blocks)?;
blocks.normalize_jumps()?;
#[cfg(debug_assertions)]
assert!(blocks.no_redundant_jumps());
// optimize_load_fast: after normalize_jumps
blocks.optimize_load_fast()?;
let mut instr_sequence = instruction_sequence_new();
blocks.cfg_to_instruction_sequence(&mut instr_sequence)?;
Ok((max_stackdepth, nlocalsplus, instr_sequence))
}
/// flowgraph.c _PyCompile_OptimizeCfg
pub fn optimize_cfg_for_tests(
seq: InstructionSequence,
consts: Vec,
nlocals: usize,
) -> crate::InternalResult {
seq.check_load_const_indices(consts.len())?;
let mut metadata = CodeUnitMetadata {
name: String::new(),
qualname: None,
consts: ConstantPool::from_ordered(consts),
names: IndexSet::default(),
varnames: IndexSet::default(),
cellvars: IndexSet::default(),
freevars: IndexSet::default(),
fast_hidden: IndexMap::default(),
fast_hidden_final: IndexSet::default(),
argcount: 0,
posonlyargcount: 0,
kwonlyargcount: 0,
firstlineno: OneIndexed::MIN,
};
let mut blocks = Blocks::from([Block::default()]);
optimize_code_unit(&mut metadata, &mut blocks, seq, nlocals, 0)?;
let _ = blocks.calculate_stackdepth()?;
blocks.optimize_load_fast()?;
let mut out = instruction_sequence_new();
blocks.cfg_to_instruction_sequence(&mut out)?;
Ok((out, metadata.consts.into_vec()))
}
/// compile.c _PyCompile_Assemble
pub fn assemble_for_tests(
filename: String,
seq: InstructionSequence,
metadata: CodeUnitMetadata,
debug_ranges: bool,
) -> crate::InternalResult {
let mut blocks = cfg_from_instruction_sequence(seq)?;
translate_jump_labels_to_targets(&mut blocks)?;
blocks.mark_except_handlers();
label_exception_targets(&mut blocks)?;
let flags = CodeFlags::empty();
let (max_stackdepth, nlocalsplus, mut instr_sequence) =
optimized_cfg_to_instruction_sequence(&metadata, flags, &mut blocks)?;
let localsplusinfo = compute_localsplus_info(&metadata, nlocalsplus, flags)?;
let CodeUnitMetadata {
name: obj_name,
qualname,
consts: constants,
names: name_cache,
varnames: varname_cache,
cellvars: _,
freevars: freevar_cache,
fast_hidden: _,
fast_hidden_final: _,
argcount: arg_count,
posonlyargcount: posonlyarg_count,
kwonlyargcount: kwonlyarg_count,
firstlineno: first_line_number,
} = metadata;
let code_arg_count = posonlyarg_count
.checked_add(arg_count)
.ok_or(InternalError::MalformedControlFlowGraph)?;
resolve_unconditional_jumps(&mut instr_sequence);
resolve_jump_offsets(&mut instr_sequence);
let assembled = assemble_emit(
&mut instr_sequence,
first_line_number.get() as i32,
debug_ranges,
)?;
let locations = rustpython_compiler_core::marshal::linetable_to_locations(
&assembled.linetable,
first_line_number.get() as i32,
assembled.instructions.len(),
);
Ok(CodeObject {
flags,
posonlyarg_count,
arg_count: code_arg_count,
kwonlyarg_count,
source_path: filename,
first_line_number: Some(first_line_number),
obj_name: obj_name.clone(),
qualname: qualname.unwrap_or(obj_name),
max_stackdepth: max_stackdepth.max(1),
instructions: CodeUnits::from(assembled.instructions),
locations,
constants: constants.into_iter().collect(),
names: name_cache.into_iter().collect(),
varnames: varname_cache.into_iter().collect(),
cellvars: localsplusinfo.cellvars,
freevars: freevar_cache.into_iter().collect(),
localspluskinds: localsplusinfo.kinds,
linetable: assembled.linetable,
exceptiontable: assembled.exceptiontable,
})
}
impl CodeInfo {
pub fn finalize_code(
mut self,
opts: &crate::compile::CompileOpts,
) -> crate::InternalResult {
let instr_sequence = self.prepare_cfg_from_codegen();
let nlocals = self.metadata.varnames.len();
let nparams = self.nparams;
optimize_code_unit(
&mut self.metadata,
&mut self.blocks,
instr_sequence,
nlocals,
nparams,
)?;
let (max_stackdepth, nlocalsplus, mut instr_sequence) =
optimized_cfg_to_instruction_sequence(&self.metadata, self.flags, &mut self.blocks)?;
let localsplusinfo = compute_localsplus_info(&self.metadata, nlocalsplus, self.flags)?;
let Self {
flags,
source_path,
private: _, // private is only used during compilation
blocks: _,
current_block: _,
instr_sequence: _,
instr_sequence_label_map: _,
annotations_instr_sequence: _,
metadata,
static_attributes: _,
in_inlined_comp: _,
fblock: _,
symbol_table_index: _,
nparams: _,
in_conditional_block: _,
next_conditional_annotation_index: _,
} = self;
let CodeUnitMetadata {
name: obj_name,
qualname,
consts: constants,
names: name_cache,
varnames: varname_cache,
cellvars: _,
freevars: freevar_cache,
fast_hidden: _,
fast_hidden_final: _,
argcount: arg_count,
posonlyargcount: posonlyarg_count,
kwonlyargcount: kwonlyarg_count,
firstlineno: first_line_number,
} = metadata;
let code_arg_count = posonlyarg_count
.checked_add(arg_count)
.ok_or(InternalError::MalformedControlFlowGraph)?;
resolve_unconditional_jumps(&mut instr_sequence);
resolve_jump_offsets(&mut instr_sequence);
let assembled = assemble_emit(
&mut instr_sequence,
first_line_number.get() as i32,
opts.debug_ranges,
)?;
let locations = rustpython_compiler_core::marshal::linetable_to_locations(
&assembled.linetable,
first_line_number.get() as i32,
assembled.instructions.len(),
);
Ok(CodeObject {
flags,
posonlyarg_count,
arg_count: code_arg_count,
kwonlyarg_count,
source_path,
first_line_number: Some(first_line_number),
obj_name: obj_name.clone(),
qualname: qualname.unwrap_or(obj_name),
// Room for one value is always reserved, even where nothing is pushed.
max_stackdepth: max_stackdepth.max(1),
instructions: CodeUnits::from(assembled.instructions),
locations,
constants: constants.into_iter().collect(),
names: name_cache.into_iter().collect(),
varnames: varname_cache.into_iter().collect(),
cellvars: localsplusinfo.cellvars,
freevars: freevar_cache.into_iter().collect(),
localspluskinds: localsplusinfo.kinds,
linetable: assembled.linetable,
exceptiontable: assembled.exceptiontable,
})
}
}
/// flowgraph.c IS_GENERATOR
fn is_generator(flags: CodeFlags) -> bool {
flags.intersects(CodeFlags::GENERATOR | CodeFlags::COROUTINE | CodeFlags::ASYNC_GENERATOR)
}
/// flowgraph.c insert_prefix_instructions
fn insert_prefix_instructions(
metadata: &CodeUnitMetadata,
blocks: &mut Blocks,
cellfixedoffsets: &[i32],
nfreevars: usize,
) -> crate::InternalResult {
debug_assert!(!blocks.is_empty());
let entry = &mut blocks[0];
let ncellvars = metadata.cellvars.len();
let firstlineno = metadata.firstlineno;
debug_assert!(firstlineno.get() > 0);
if ncellvars > 0 {
let nvars = metadata.varnames.len() + ncellvars;
let mut sorted = Vec::new();
vec_try_reserve_exact(&mut sorted, nvars)?;
sorted.resize(nvars, 0i32);
for i in 0..ncellvars {
sorted[cellfixedoffsets[i] as usize] = i as i32 + 1;
}
let mut ncellsused = 0;
let mut i = 0;
while ncellsused < ncellvars {
let oldindex = sorted[i] - 1;
i += 1;
if oldindex == -1 {
continue;
}
entry.basicblock_insert_instruction(
ncellsused,
InstructionInfo {
instr: Opcode::MakeCell.into(),
arg: OpArg::new(oldindex as u32),
target: BlockIdx::NULL,
location: SourceLocation::default(),
end_location: SourceLocation::default(),
except_handler: None,
semantic_location: None,
lineno_override: Some(NO_LOCATION_OVERRIDE),
},
)?;
ncellsused += 1;
}
}
if nfreevars > 0 {
entry.basicblock_insert_instruction(
0,
InstructionInfo {
instr: Opcode::CopyFreeVars.into(),
arg: OpArg::new(nfreevars as u32),
target: BlockIdx::NULL,
location: SourceLocation::default(),
end_location: SourceLocation::default(),
except_handler: None,
semantic_location: None,
lineno_override: Some(NO_LOCATION_OVERRIDE),
},
)?;
}
Ok(())
}
/// flowgraph.c prepare_localsplus
fn prepare_localsplus(
metadata: &CodeUnitMetadata,
blocks: &mut Blocks,
) -> crate::InternalResult {
let nlocals = metadata.varnames.len();
let ncellvars = metadata.cellvars.len();
let nfreevars = metadata.freevars.len();
let int_max = i32::MAX as usize;
debug_assert!(nlocals < int_max);
debug_assert!(ncellvars < int_max);
debug_assert!(nfreevars < int_max);
debug_assert!(int_max - nlocals - ncellvars > 0);
debug_assert!(int_max - nlocals - ncellvars - nfreevars > 0);
let mut nlocalsplus = nlocals + ncellvars + nfreevars;
let mut cellfixedoffsets = build_cellfixedoffsets(metadata)?;
// This must be called before fix_cell_offsets().
insert_prefix_instructions(metadata, blocks, &cellfixedoffsets, nfreevars)?;
let numdropped = fix_cell_offsets(metadata, blocks, &mut cellfixedoffsets);
nlocalsplus -= numdropped;
Ok(nlocalsplus)
}
/// flowgraph.c eval_const_unaryop
fn eval_const_unaryop(
operand: &ConstantData,
op: Instruction,
intrinsic: Option,
) -> Option {
match (operand, op, intrinsic) {
(ConstantData::Integer { value }, Instruction::UnaryNegative, None) => {
Some(ConstantData::Integer { value: -value })
}
(ConstantData::Float { value }, Instruction::UnaryNegative, None) => {
Some(ConstantData::Float { value: -value })
}
(ConstantData::Complex { value }, Instruction::UnaryNegative, None) => {
Some(ConstantData::Complex { value: -value })
}
(ConstantData::Boolean { value }, Instruction::UnaryNegative, None) => {
Some(ConstantData::Integer {
value: BigInt::from(-i32::from(*value)),
})
}
(ConstantData::Integer { value }, Instruction::UnaryInvert, None) => {
Some(ConstantData::Integer { value: !value })
}
(ConstantData::Boolean { .. }, Instruction::UnaryInvert, None) => None,
(_, Instruction::UnaryNot, None) => Some(ConstantData::Boolean {
value: !operand.truthiness(),
}),
(
ConstantData::Integer { value },
Instruction::CallIntrinsic1 { .. },
Some(oparg::IntrinsicFunction1::UnaryPositive),
) => Some(ConstantData::Integer {
value: value.clone(),
}),
(
ConstantData::Float { value },
Instruction::CallIntrinsic1 { .. },
Some(oparg::IntrinsicFunction1::UnaryPositive),
) => Some(ConstantData::Float { value: *value }),
(
ConstantData::Boolean { value },
Instruction::CallIntrinsic1 { .. },
Some(oparg::IntrinsicFunction1::UnaryPositive),
) => Some(ConstantData::Integer {
value: BigInt::from(i32::from(*value)),
}),
(
ConstantData::Complex { value },
Instruction::CallIntrinsic1 { .. },
Some(oparg::IntrinsicFunction1::UnaryPositive),
) => Some(ConstantData::Complex { value: *value }),
_ => None,
}
}
fn load_const_truthiness(
instr: Instruction,
arg: OpArg,
metadata: &CodeUnitMetadata,
) -> Option {
match instr {
Instruction::LoadConst { consti } => {
let constant = &metadata.consts[consti.get(arg).as_usize()];
Some(constant.truthiness())
}
Instruction::LoadSmallInt { i } => Some(i.get(arg) != 0),
Instruction::LoadCommonConstant { idx } => {
use oparg::CommonConstant;
Some(!matches!(
idx.get(arg),
CommonConstant::None | CommonConstant::False | CommonConstant::EmptyStr
))
}
_ => None,
}
}
/// flowgraph.c add_const
fn add_const(
metadata: &mut CodeUnitMetadata,
constant: ConstantData,
) -> crate::InternalResult {
Ok(metadata.consts.try_insert_full(constant)?.0)
}
fn instr_make_load_const(
metadata: &mut CodeUnitMetadata,
instr: &mut InstructionInfo,
constant: ConstantData,
) -> crate::InternalResult {
if instr.maybe_instr_make_load_smallint(&constant)
|| instr.maybe_instr_make_load_common_const(&constant)
{
return Ok(());
}
let const_idx = add_const(metadata, constant)?;
instr.instr_set_op1(Opcode::LoadConst.into(), OpArg::new(const_idx as u32));
Ok(())
}
/// flowgraph.c fold_const_unaryop
fn fold_const_unaryop(
metadata: &mut CodeUnitMetadata,
block: &mut Block,
i: usize,
) -> crate::InternalResult {
let instr = &block.instructions[i];
let (op, intrinsic) = match instr.instr.real() {
Some(Instruction::UnaryNegative) => (Instruction::UnaryNegative, None),
Some(Instruction::UnaryInvert) => (Instruction::UnaryInvert, None),
Some(Instruction::UnaryNot) => (Instruction::UnaryNot, None),
Some(Instruction::CallIntrinsic1 { func })
if matches!(
func.get(instr.arg),
oparg::IntrinsicFunction1::UnaryPositive
) =>
{
(Opcode::CallIntrinsic1.into(), Some(func.get(instr.arg)))
}
_ => return Ok(false),
};
let Some(operand_index) = (if let Some(start) = i.checked_sub(1) {
block.get_const_loading_instrs(start, 1)?
} else {
None
})
.and_then(|indices| indices.into_iter().next()) else {
return Ok(false);
};
let operand = get_const_value(metadata, &block.instructions[operand_index]);
let Some(operand) = operand else {
return Ok(false);
};
let Some(folded_const) = eval_const_unaryop(&operand, op, intrinsic) else {
return Ok(false);
};
block.nop_out(&[operand_index]);
instr_make_load_const(metadata, &mut block.instructions[i], folded_const)?;
Ok(true)
}
/// flowgraph.c fold_const_binop
fn fold_const_binop(
metadata: &mut CodeUnitMetadata,
block: &mut Block,
i: usize,
) -> crate::InternalResult {
use oparg::BinaryOperator as BinOp;
let Some(Opcode::BinaryOp) = block.instructions[i].instr.real_opcode() else {
return Ok(false);
};
let Some(operand_indices) = (if let Some(start) = i.checked_sub(1) {
block.get_const_loading_instrs(start, 2)?
} else {
None
}) else {
return Ok(false);
};
let op_raw = u32::from(block.instructions[i].arg);
let Ok(op) = BinOp::try_from(op_raw) else {
return Ok(false);
};
let left = get_const_value(metadata, &block.instructions[operand_indices[0]]);
let right = get_const_value(metadata, &block.instructions[operand_indices[1]]);
let (Some(left_val), Some(right_val)) = (left, right) else {
return Ok(false);
};
let Some(result_const) = eval_const_binop(&left_val, &right_val, op) else {
return Ok(false);
};
block.nop_out(&operand_indices);
instr_make_load_const(metadata, &mut block.instructions[i], result_const)?;
Ok(true)
}
/// flowgraph.c get_const_value
fn get_const_value(metadata: &CodeUnitMetadata, info: &InstructionInfo) -> Option {
match info.instr.real_opcode() {
Some(Opcode::LoadCommonConstant) => {
use oparg::CommonConstant;
match CommonConstant::try_from(u32::from(info.arg)).ok()? {
CommonConstant::None => Some(ConstantData::None),
CommonConstant::EmptyStr => Some(ConstantData::Str {
value: Wtf8Buf::new(),
}),
CommonConstant::True => Some(ConstantData::Boolean { value: true }),
CommonConstant::False => Some(ConstantData::Boolean { value: false }),
CommonConstant::MinusOne => Some(ConstantData::Integer {
value: BigInt::from(-1),
}),
_ => None,
}
}
Some(Opcode::LoadSmallInt) => {
let v = u32::from(info.arg) as i32;
Some(ConstantData::Integer {
value: BigInt::from(v),
})
}
_ if info.instr.has_const() => {
let idx = u32::from(info.arg) as usize;
metadata.consts.get_index(idx).cloned()
}
_ => None,
}
}
/// flowgraph.c const_folding_check_complexity
fn const_folding_check_complexity(obj: &ConstantData, mut limit: isize) -> Option {
if let ConstantData::Tuple { elements } = obj {
limit -= isize::try_from(elements.len()).ok()?;
if limit < 0 {
return None;
}
for element in elements {
limit = const_folding_check_complexity(element, limit)?;
}
}
Some(limit)
}
fn repeat_wtf8(value: &Wtf8Buf, n: usize) -> Option {
let mut result = Wtf8Buf::new();
result.try_reserve_exact(value.len().checked_mul(n)?).ok()?;
for _ in 0..n {
result.push_wtf8(value);
}
Some(result)
}
fn checked_repeat_count(n: &BigInt, item_size: usize) -> Option {
let n = n.to_isize()?;
if item_size != 0 && (n < 0 || n as usize > MAX_STR_SIZE / item_size) {
return None;
}
Some(n.max(0) as usize)
}
/// flowgraph.c const_folding_safe_multiply
fn const_folding_safe_multiply(left: &ConstantData, right: &ConstantData) -> Option {
match (left, right) {
(ConstantData::Integer { value: l }, ConstantData::Integer { value: r }) => {
if !l.is_zero() && !r.is_zero() && l.bits() + r.bits() > MAX_INT_SIZE {
return None;
}
Some(ConstantData::Integer { value: l * r })
}
(ConstantData::Float { value: l }, ConstantData::Float { value: r }) => {
Some(ConstantData::Float { value: l * r })
}
(ConstantData::Str { value: s }, ConstantData::Integer { value: n }) => {
let n = checked_repeat_count(n, s.code_points().count())?;
Some(ConstantData::Str {
value: repeat_wtf8(s, n)?,
})
}
(ConstantData::Integer { .. }, ConstantData::Str { .. }) => {
const_folding_safe_multiply(right, left)
}
(ConstantData::Bytes { value: b }, ConstantData::Integer { value: n }) => {
let n = checked_repeat_count(n, b.len())?;
let mut value = Vec::new();
value.try_reserve_exact(b.len().checked_mul(n)?).ok()?;
for _ in 0..n {
value.extend_from_slice(b);
}
Some(ConstantData::Bytes { value })
}
(ConstantData::Integer { .. }, ConstantData::Bytes { .. }) => {
const_folding_safe_multiply(right, left)
}
(ConstantData::Tuple { elements }, ConstantData::Integer { value: n }) => {
if elements.is_empty() {
return Some(ConstantData::Tuple {
elements: Vec::new(),
});
}
let n = n.to_usize()?;
if n != 0 {
if n > MAX_COLLECTION_SIZE / elements.len() {
return None;
}
const_folding_check_complexity(
&ConstantData::Tuple {
elements: elements.clone(),
},
MAX_TOTAL_ITEMS / isize::try_from(n).ok()?,
)?;
}
let mut result = Vec::new();
result
.try_reserve_exact(elements.len().checked_mul(n)?)
.ok()?;
for _ in 0..n {
result.extend(elements.iter().cloned());
}
Some(ConstantData::Tuple { elements: result })
}
(ConstantData::Integer { .. }, ConstantData::Tuple { .. }) => {
const_folding_safe_multiply(right, left)
}
_ => None,
}
}
/// flowgraph.c const_folding_safe_power
fn const_folding_safe_power(left: &ConstantData, right: &ConstantData) -> Option {
match (left, right) {
(ConstantData::Integer { value: l }, ConstantData::Integer { value: r }) => {
if r < &BigInt::from(0) {
if l.is_zero() {
return None;
}
let base = l.to_f64()?;
if !base.is_finite() {
return None;
}
let result = if let Some(exp) = r.to_i32() {
base.powi(exp)
} else {
base.powf(r.to_f64()?)
};
if !result.is_finite() {
return None;
}
return Some(ConstantData::Float { value: result });
}
let exp: u64 = r.try_into().ok()?;
let exp_usize = usize::try_from(exp).ok()?;
if !l.is_zero() && exp > 0 && l.bits() > MAX_INT_SIZE / exp {
return None;
}
Some(ConstantData::Integer {
value: num_traits::pow::pow(l.clone(), exp_usize),
})
}
(ConstantData::Float { value: l }, ConstantData::Float { value: r }) => {
let result = l.powf(*r);
result
.is_finite()
.then_some(ConstantData::Float { value: result })
}
_ => None,
}
}
/// flowgraph.c const_folding_safe_lshift
fn const_folding_safe_lshift(left: &ConstantData, right: &ConstantData) -> Option {
let (ConstantData::Integer { value: l }, ConstantData::Integer { value: r }) = (left, right)
else {
return None;
};
let shift: u64 = r.try_into().ok()?;
let shift_usize = usize::try_from(shift).ok()?;
if shift > MAX_INT_SIZE || (!l.is_zero() && l.bits() > MAX_INT_SIZE - shift) {
return None;
}
Some(ConstantData::Integer {
value: l Option {
if matches!(left, ConstantData::Str { .. } | ConstantData::Bytes { .. }) {
return None;
}
match (left, right) {
(ConstantData::Integer { value: l }, ConstantData::Integer { value: r }) => {
if r.is_zero() {
return None;
}
let rem = l.clone() % r.clone();
let value = if !rem.is_zero() && (rem < BigInt::from(0)) != (*r < BigInt::from(0)) {
rem + r
} else {
rem
};
Some(ConstantData::Integer { value })
}
(ConstantData::Float { value: l }, ConstantData::Float { value: r }) => {
let (_, modulo) = float_div_mod(*l, *r)?;
Some(ConstantData::Float { value: modulo })
}
_ => None,
}
}
fn float_div_mod(left: f64, right: f64) -> Option {
if right == 0.0 {
return None;
}
let mut modulo = left % right;
let div = (left - modulo) / right;
let floordiv = if modulo != 0.0 {
let div = if (right < 0.0) != (modulo < 0.0) {
modulo += right;
div - 1.0
} else {
div
};
let mut floordiv = div.floor();
if div - floordiv > 0.5 {
floordiv += 1.0;
}
floordiv
} else {
modulo = 0.0f64.copysign(right);
0.0f64.copysign(left / right)
};
Some((floordiv, modulo))
}
/// flowgraph.c eval_const_binop complex result construction
fn eval_const_complex_const(value: Complex) -> Option {
(value.re.is_finite() && value.im.is_finite()).then_some(ConstantData::Complex { value })
}
/// flowgraph.c eval_const_binop complex operations
fn eval_const_complex_binop(
left: Complex,
right: Complex,
op: oparg::BinaryOperator,
) -> Option {
use oparg::BinaryOperator as BinOp;
let value = match op {
BinOp::Add => left + right,
BinOp::Subtract => {
let re = left.re - right.re;
// Preserve signed-zero behavior for real-zero
// minus zero-complex expressions such as `0 - 0j`.
let im = if left.re == 0.0
&& left.im == 0.0
&& right.re == 0.0
&& right.im == 0.0
&& !right.im.is_sign_negative()
{
-0.0
} else {
left.im - right.im
};
Complex::new(re, im)
}
BinOp::Multiply => left * right,
BinOp::TrueDivide => {
if right == Complex::new(0.0, 0.0) {
return None;
}
left / right
}
BinOp::Power => {
if left == Complex::new(0.0, 0.0) {
if right.im != 0.0 || right.re < 0.0 {
return None;
}
return eval_const_complex_const(if right.re == 0.0 {
Complex::new(1.0, 0.0)
} else {
Complex::new(0.0, 0.0)
});
}
if right.im == 0.0
&& right.re.fract() == 0.0
&& right.re >= f64::from(i32::MIN)
&& right.re return None,
};
eval_const_complex_const(value)
}
/// flowgraph.c eval_const_binop subscript index conversion
fn constant_as_index(value: &ConstantData) -> Option {
match value {
ConstantData::Integer { value } => value.to_i64().or_else(|| {
if value < &BigInt::from(0) {
Some(i64::MIN)
} else {
Some(i64::MAX)
}
}),
ConstantData::Boolean { value } => Some(i64::from(*value)),
_ => None,
}
}
/// flowgraph.c eval_const_binop subscript slice bound conversion
fn slice_bound(value: &ConstantData) -> Option {
match value {
ConstantData::None => Some(None),
_ => constant_as_index(value).map(Some),
}
}
/// flowgraph.c eval_const_binop subscript slice index adjustment
fn adjusted_slice_indices(len: usize, slice: &[ConstantData; 3]) -> Option {
let len = i64::try_from(len).ok()?;
let start = slice_bound(&slice[0])?;
let stop = slice_bound(&slice[1])?;
let step = slice_bound(&slice[2])?.unwrap_or(1);
if step == 0 || step == i64::MIN {
return None;
}
let step_is_negative = step < 0;
let lower = if step_is_negative { -1 } else { 0 };
let upper = if step_is_negative { len - 1 } else { len };
let adjust = |value: Option, default: i64| {
let mut value = value.unwrap_or(default);
if value < 0 {
value = value.saturating_add(len);
if value < 0 {
value = lower;
}
} else if value >= len {
value = upper;
}
value
};
let start = adjust(start, if step_is_negative { upper } else { lower });
let stop = adjust(stop, if step_is_negative { lower } else { upper });
let mut index = i128::from(start);
let stop = i128::from(stop);
let step = i128::from(step);
let slice_len = if step > 0 {
if index < stop {
usize::try_from((stop - index - 1) / step + 1).ok()?
} else {
0
}
} else if index > stop {
usize::try_from((index - stop - 1) / -step + 1).ok()?
} else {
0
};
let mut indices = Vec::new();
indices.try_reserve_exact(slice_len).ok()?;
if step > 0 {
while index < stop {
indices.push(usize::try_from(index).ok()?);
index += step;
}
} else {
while index > stop {
indices.push(usize::try_from(index).ok()?);
index += step;
}
}
Some(indices)
}
/// flowgraph.c eval_const_binop subscript index adjustment
fn adjusted_const_index(len: usize, index: &ConstantData) -> Option {
let len = i64::try_from(len).ok()?;
let index = constant_as_index(index)?;
let index = if index < 0 {
index.saturating_add(len)
} else {
index
};
if index < 0 || index >= len {
return None;
}
usize::try_from(index).ok()
}
/// flowgraph.c eval_const_binop NB_SUBSCR
fn eval_const_subscript(container: &ConstantData, index: &ConstantData) -> Option {
match (container, index) {
(
ConstantData::Str { value },
ConstantData::Integer { .. } | ConstantData::Boolean { .. },
) => {
let string = value.to_string();
if string.contains(char::REPLACEMENT_CHARACTER) {
return None;
}
let mut chars = Vec::new();
chars.try_reserve_exact(string.chars().count()).ok()?;
chars.extend(string.chars());
let index = adjusted_const_index(chars.len(), index)?;
Some(ConstantData::Str {
value: chars[index].to_string().into(),
})
}
(ConstantData::Str { value }, ConstantData::Slice { elements }) => {
let string = value.to_string();
if string.contains(char::REPLACEMENT_CHARACTER) {
return None;
}
let mut chars = Vec::new();
chars.try_reserve_exact(string.chars().count()).ok()?;
chars.extend(string.chars());
let indices = adjusted_slice_indices(chars.len(), elements)?;
let capacity = indices.iter().try_fold(0usize, |capacity, &index| {
capacity.checked_add(chars[index].len_utf8())
})?;
let mut result = String::new();
result.try_reserve_exact(capacity).ok()?;
for index in indices {
result.push(chars[index]);
}
Some(ConstantData::Str {
value: result.into(),
})
}
(
ConstantData::Bytes { value },
ConstantData::Integer { .. } | ConstantData::Boolean { .. },
) => {
let index = adjusted_const_index(value.len(), index)?;
Some(ConstantData::Integer {
value: BigInt::from(value[index]),
})
}
(ConstantData::Bytes { value }, ConstantData::Slice { elements }) => {
let indices = adjusted_slice_indices(value.len(), elements)?;
let mut result = Vec::new();
result.try_reserve_exact(indices.len()).ok()?;
for index in indices {
result.push(value[index]);
}
Some(ConstantData::Bytes { value: result })
}
(
ConstantData::Tuple { elements },
ConstantData::Integer { .. } | ConstantData::Boolean { .. },
) => {
let index = adjusted_const_index(elements.len(), index)?;
Some(elements[index].clone())
}
(ConstantData::Tuple { elements }, ConstantData::Slice { elements: slice }) => {
let indices = adjusted_slice_indices(elements.len(), slice)?;
let mut result = Vec::new();
result.try_reserve_exact(indices.len()).ok()?;
for index in indices {
result.push(elements[index].clone());
}
Some(ConstantData::Tuple { elements: result })
}
_ => None,
}
}
/// flowgraph.c eval_const_binop bool/int coercion
fn constant_as_int(value: &ConstantData) -> Option {
match value {
ConstantData::Boolean { value } => Some((BigInt::from(u8::from(*value)), true)),
ConstantData::Integer { value } => Some((value.clone(), false)),
_ => None,
}
}
/// flowgraph.c eval_const_binop
fn eval_const_binop(
left: &ConstantData,
right: &ConstantData,
op: oparg::BinaryOperator,
) -> Option {
use oparg::BinaryOperator as BinOp;
if matches!(op, BinOp::Subscr) {
return eval_const_subscript(left, right);
}
if let (Some((left_int, left_is_bool)), Some((right_int, right_is_bool))) =
(constant_as_int(left), constant_as_int(right))
&& (left_is_bool || right_is_bool)
{
if left_is_bool && right_is_bool {
match op {
BinOp::And => {
return Some(ConstantData::Boolean {
value: !left_int.is_zero() & !right_int.is_zero(),
});
}
BinOp::Or => {
return Some(ConstantData::Boolean {
value: !left_int.is_zero() | !right_int.is_zero(),
});
}
BinOp::Xor => {
return Some(ConstantData::Boolean {
value: !left_int.is_zero() ^ !right_int.is_zero(),
});
}
_ => {}
}
}
return eval_const_binop(
&ConstantData::Integer { value: left_int },
&ConstantData::Integer { value: right_int },
op,
);
}
match (left, right) {
(ConstantData::Integer { value: l }, ConstantData::Integer { value: r }) => {
let result = match op {
BinOp::Add => l + r,
BinOp::Subtract => l - r,
BinOp::Multiply => {
return const_folding_safe_multiply(left, right);
}
BinOp::TrueDivide => {
if r.is_zero() {
return None;
}
let l_f = l.to_f64()?;
let r_f = r.to_f64()?;
let result = l_f / r_f;
if !result.is_finite() {
return None;
}
return Some(ConstantData::Float { value: result });
}
BinOp::FloorDivide => {
if r.is_zero() {
return None;
}
// Python floor division: round towards negative infinity
let (q, rem) = (l.clone() / r.clone(), l.clone() % r.clone());
if !rem.is_zero() && (rem < BigInt::from(0)) != (*r < BigInt::from(0)) {
q - 1
} else {
q
}
}
BinOp::Remainder => return const_folding_safe_mod(left, right),
BinOp::Power => return const_folding_safe_power(left, right),
BinOp::Lshift => return const_folding_safe_lshift(left, right),
BinOp::Rshift => {
let shift: u32 = r.try_into().ok()?;
l >> (shift as usize)
}
BinOp::And => l & r,
BinOp::Or => l | r,
BinOp::Xor => l ^ r,
_ => return None,
};
Some(ConstantData::Integer { value: result })
}
(ConstantData::Float { value: l }, ConstantData::Float { value: r }) => {
let result = match op {
BinOp::Add => l + r,
BinOp::Subtract => l - r,
BinOp::Multiply => return const_folding_safe_multiply(left, right),
BinOp::TrueDivide => {
if *r == 0.0 {
return None;
}
l / r
}
BinOp::FloorDivide => {
let (floordiv, _) = float_div_mod(*l, *r)?;
floordiv
}
BinOp::Remainder => return const_folding_safe_mod(left, right),
BinOp::Power => return const_folding_safe_power(left, right),
_ => return None,
};
if matches!(op, BinOp::Power) && !result.is_finite() {
return None;
}
Some(ConstantData::Float { value: result })
}
// Int op Float or Float op Int Float
(ConstantData::Integer { value: l }, ConstantData::Float { value: r }) => {
let l_f = l.to_f64()?;
eval_const_binop(
&ConstantData::Float { value: l_f },
&ConstantData::Float { value: *r },
op,
)
}
(ConstantData::Float { value: l }, ConstantData::Integer { value: r }) => {
let r_f = r.to_f64()?;
eval_const_binop(
&ConstantData::Float { value: *l },
&ConstantData::Float { value: r_f },
op,
)
}
(ConstantData::Integer { value: l }, ConstantData::Complex { value: r }) => {
eval_const_complex_binop(Complex::new(l.to_f64()?, 0.0), *r, op)
}
(ConstantData::Complex { value: l }, ConstantData::Integer { value: r }) => {
eval_const_complex_binop(*l, Complex::new(r.to_f64()?, 0.0), op)
}
(ConstantData::Float { value: l }, ConstantData::Complex { value: r }) => {
eval_const_complex_binop(Complex::new(*l, 0.0), *r, op)
}
(ConstantData::Complex { value: l }, ConstantData::Float { value: r }) => {
eval_const_complex_binop(*l, Complex::new(*r, 0.0), op)
}
(ConstantData::Complex { value: l }, ConstantData::Complex { value: r }) => {
eval_const_complex_binop(*l, *r, op)
}
// String concatenation and repetition
(ConstantData::Str { value: l }, ConstantData::Str { value: r })
if matches!(op, BinOp::Add) =>
{
let mut result = Wtf8Buf::new();
result
.try_reserve_exact(l.len().checked_add(r.len())?)
.ok()?;
result.push_wtf8(l);
result.push_wtf8(r);
Some(ConstantData::Str { value: result })
}
(ConstantData::Str { .. }, ConstantData::Integer { .. })
if matches!(op, BinOp::Multiply) =>
{
const_folding_safe_multiply(left, right)
}
(ConstantData::Tuple { elements: l }, ConstantData::Tuple { elements: r })
if matches!(op, BinOp::Add) =>
{
let mut result = Vec::new();
result
.try_reserve_exact(l.len().checked_add(r.len())?)
.ok()?;
result.extend(l.iter().cloned());
result.extend(r.iter().cloned());
Some(ConstantData::Tuple { elements: result })
}
(ConstantData::Tuple { .. }, ConstantData::Integer { .. })
if matches!(op, BinOp::Multiply) =>
{
const_folding_safe_multiply(left, right)
}
(ConstantData::Integer { .. }, ConstantData::Tuple { .. })
if matches!(op, BinOp::Multiply) =>
{
const_folding_safe_multiply(left, right)
}
(ConstantData::Integer { .. }, ConstantData::Str { .. })
if matches!(op, BinOp::Multiply) =>
{
const_folding_safe_multiply(left, right)
}
(ConstantData::Bytes { value: l }, ConstantData::Bytes { value: r })
if matches!(op, BinOp::Add) =>
{
let mut result = Vec::new();
result
.try_reserve_exact(l.len().checked_add(r.len())?)
.ok()?;
result.extend_from_slice(l);
result.extend_from_slice(r);
Some(ConstantData::Bytes { value: result })
}
(ConstantData::Bytes { .. }, ConstantData::Integer { .. })
if matches!(op, BinOp::Multiply) =>
{
const_folding_safe_multiply(left, right)
}
(ConstantData::Integer { .. }, ConstantData::Bytes { .. })
if matches!(op, BinOp::Multiply) =>
{
const_folding_safe_multiply(left, right)
}
_ => None,
}
}
/// flowgraph.c fold_tuple_of_constants
fn fold_tuple_of_constants(
metadata: &mut CodeUnitMetadata,
block: &mut Block,
i: usize,
) -> crate::InternalResult {
let Some(Opcode::BuildTuple) = block.instructions[i].instr.real_opcode() else {
return Ok(false);
};
let tuple_size = u32::from(block.instructions[i].arg) as usize;
if tuple_size > STACK_USE_GUIDELINE {
return Ok(false);
}
let Some(operand_indices) = (if tuple_size == 0 {
Some(Vec::new())
} else if let Some(start) = i.checked_sub(1) {
block.get_const_loading_instrs(start, tuple_size)?
} else {
None
}) else {
return Ok(false);
};
let mut elements = Vec::new();
elements
.try_reserve_exact(tuple_size)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
for &j in &operand_indices {
let Some(element) = get_const_value(metadata, &block.instructions[j]) else {
return Ok(false);
};
elements.push(element);
}
block.nop_out(&operand_indices);
instr_make_load_const(
metadata,
&mut block.instructions[i],
ConstantData::Tuple { elements },
)?;
Ok(true)
}
fn fold_constant_sequence_into_load_const(
metadata: &mut CodeUnitMetadata,
block: &mut Block,
i: usize,
) -> crate::InternalResult {
let (intrinsic, is_set) = match block.instructions[i].instr.real() {
Some(Instruction::CallIntrinsic1 { func })
if func.get(block.instructions[i].arg) == IntrinsicFunction1::ListToTuple =>
{
(true, false)
}
Some(Instruction::ListAppend { .. }) => (false, false),
Some(Instruction::SetAdd { .. }) => (false, true),
_ => return Ok(false),
};
let mut consts_found = 0usize;
let mut expect_append = intrinsic;
let mut pos = i;
while let Some(prev) = pos.checked_sub(1) {
pos = prev;
let instr = &block.instructions[pos];
if matches!(instr.instr.real(), Some(Instruction::Nop)) {
continue;
}
let is_start = if is_set {
matches!(instr.instr.real(), Some(Instruction::BuildSet { .. }))
} else {
matches!(instr.instr.real(), Some(Instruction::BuildList { .. }))
};
if is_start && u32::from(instr.arg) == 0 {
if !expect_append {
return Ok(false);
}
let mut elements = Vec::new();
elements
.try_reserve_exact(consts_found)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
let end = if intrinsic { i } else { i + 1 };
for idx in (pos..end).rev() {
if matches!(block.instructions[idx].instr.real(), Some(Instruction::Nop)) {
continue;
}
if block.instructions[idx].loads_const() {
let Some(value) = get_const_value(metadata, &block.instructions[idx]) else {
return Ok(false);
};
elements.push(value);
}
}
debug_assert_eq!(elements.len(), consts_found);
elements.reverse();
// A valid common constant may have no ConstantData representation.
// Leave the sequence intact when collecting its values rejects it.
for instr in &mut block.instructions[pos..end] {
if !matches!(instr.instr.real(), Some(Instruction::Nop)) {
instr.nop_out_no_location();
}
}
instr_make_load_const(
metadata,
&mut block.instructions[i],
if is_set {
ConstantData::Frozenset { elements }
} else {
ConstantData::Tuple { elements }
},
)?;
return Ok(true);
}
if expect_append {
let is_append = if is_set {
matches!(instr.instr.real(), Some(Instruction::SetAdd { .. }))
} else {
matches!(instr.instr.real(), Some(Instruction::ListAppend { .. }))
};
if !is_append || u32::from(instr.arg) != 1 {
return Ok(false);
}
} else {
if !instr.loads_const() {
return Ok(false);
}
consts_found += 1;
}
expect_append = !expect_append;
}
Ok(false)
}
/// Port of flowgraph.c optimize_lists_and_sets().
fn optimize_lists_and_sets(
metadata: &mut CodeUnitMetadata,
block: &mut Block,
i: usize,
nextop: Option,
) -> crate::InternalResult {
let Some(instr) = block.instructions[i].instr.real() else {
return Ok(false);
};
let is_list = matches!(instr, Instruction::BuildList { .. });
let is_set = matches!(instr, Instruction::BuildSet { .. });
if !is_list && !is_set {
return Ok(false);
}
let contains_or_iter = matches!(
nextop,
Some(Instruction::GetIter { .. } | Instruction::ContainsOp { .. })
);
let seq_size = u32::from(block.instructions[i].arg) as usize;
if seq_size > STACK_USE_GUIDELINE || (seq_size < MIN_CONST_SEQUENCE_SIZE && !contains_or_iter) {
return Ok(false);
}
let Some(operand_indices) = (if seq_size == 0 {
Some(Vec::new())
} else if let Some(start) = i.checked_sub(1) {
block.get_const_loading_instrs(start, seq_size)?
} else {
None
}) else {
if contains_or_iter && is_list {
let arg = block.instructions[i].arg;
block.instructions[i].instr_set_op1(Opcode::BuildTuple.into(), arg);
return Ok(true);
}
return Ok(false);
};
let mut elements = Vec::new();
elements
.try_reserve_exact(seq_size)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
for &j in &operand_indices {
let Some(element) = get_const_value(metadata, &block.instructions[j]) else {
return Ok(false);
};
elements.push(element);
}
let const_data = if is_list {
ConstantData::Tuple { elements }
} else {
ConstantData::Frozenset { elements }
};
let const_idx = add_const(metadata, const_data)?;
if !contains_or_iter {
debug_assert!(i >= 2);
let folded_loc = block.instructions[i].instr_location();
block.nop_out(&operand_indices);
let build_instr = if is_list {
Opcode::BuildList
} else {
Opcode::BuildSet
}
.into();
block.instructions[i - 2].instr_set_op1(build_instr, OpArg::new(0));
block.instructions[i - 2].instr_set_location(folded_loc);
block.instructions[i - 1]
.instr_set_op1(Opcode::LoadConst.into(), OpArg::new(const_idx as u32));
let extend_instr = if is_list {
Opcode::ListExtend
} else {
Opcode::SetUpdate
};
block.instructions[i].instr_set_op1(extend_instr.into(), OpArg::new(1));
return Ok(true);
}
block.nop_out(&operand_indices);
block.instructions[i].instr_set_op1(Opcode::LoadConst.into(), OpArg::new(const_idx as u32));
Ok(true)
}
/// flowgraph.c VISITED
const VISITED: i32 = -1;
/// flowgraph.c SWAPPABLE
fn is_swappable(instr: AnyInstruction) -> bool {
matches!(
instr.into(),
AnyOpcode::Real(Opcode::StoreFast | Opcode::PopTop)
| AnyOpcode::Pseudo(PseudoOpcode::StoreFastMaybeNull)
)
}
/// flowgraph.c basicblock_optimize_load_const
fn basicblock_optimize_load_const(
metadata: &mut CodeUnitMetadata,
block: &mut Block,
) -> crate::InternalResult {
let mut effective_opcode = Instruction::Nop.into();
let mut effective_oparg = OpArg::new(0);
for i in 0..block.instruction_used {
'instruction: {
if matches!(
block.instructions[i].instr.real(),
Some(Instruction::LoadConst { .. })
) && let Some(constant) = get_const_value(metadata, &block.instructions[i])
{
block.instructions[i].maybe_instr_make_load_smallint(&constant);
}
let curr = block.instructions[i];
let curr_arg = curr.arg;
let is_copy_of_load_const = matches!(
(effective_opcode, curr.instr.real()),
(AnyInstruction::Real(Instruction::LoadConst { .. }), Some(Instruction::Copy { i }))
if i.get(curr_arg) == 1
);
if !is_copy_of_load_const {
effective_opcode = curr.instr;
effective_oparg = curr_arg;
}
debug_assert!(!effective_opcode.is_assembler());
let Some(
const_instr @ (Instruction::LoadConst { .. }
| Instruction::LoadSmallInt { .. }
| Instruction::LoadCommonConstant { .. }),
) = effective_opcode.real()
else {
break 'instruction;
};
let const_arg = effective_oparg;
if i + 1 >= block.instruction_used {
break 'instruction;
}
let next = block.instructions[i + 1];
let next_arg = next.arg;
if let Some(is_true) = load_const_truthiness(const_instr, const_arg, metadata) {
let const_jump = match (next.instr.real_opcode(), next.instr.pseudo_opcode()) {
(_, Some(PseudoOpcode::JumpIfTrue)) => Some((true, false)),
(_, Some(PseudoOpcode::JumpIfFalse)) => Some((false, false)),
(Some(Opcode::PopJumpIfTrue), _) => Some((true, true)),
(Some(Opcode::PopJumpIfFalse), _) => Some((false, true)),
_ => None,
};
if let Some((jump_if_true, pops_condition)) = const_jump {
if pops_condition {
block.instructions[i].set_to_nop();
}
if is_true == jump_if_true {
block.instructions[i + 1].instr = PseudoOpcode::Jump.into();
} else {
block.instructions[i + 1].set_to_nop();
}
break 'instruction;
}
}
// The remaining combinations require both instructions to be real.
let Some(next_instr) = next.instr.real() else {
break 'instruction;
};
let is_none = match const_instr {
Instruction::LoadConst { consti } => matches!(
&metadata.consts[consti.get(const_arg).as_usize()],
ConstantData::None
),
Instruction::LoadCommonConstant { idx } => {
idx.get(const_arg) == oparg::CommonConstant::None
}
_ => false,
};
if is_none && let Instruction::IsOp { invert } = next_instr {
let mut jump_idx = i + 2;
if jump_idx >= block.instruction_used {
break 'instruction;
}
if matches!(
block.instructions[jump_idx].instr.real(),
Some(Instruction::ToBool)
) {
block.instructions[jump_idx].set_to_nop();
jump_idx += 1;
if jump_idx >= block.instruction_used {
break 'instruction;
}
}
let Some(jump_instr) = block.instructions[jump_idx].instr.real() else {
break 'instruction;
};
let mut invert = matches!(
invert.get(next_arg),
rustpython_compiler_core::bytecode::Invert::Yes
);
match jump_instr {
Instruction::PopJumpIfFalse { .. } => {
invert = !invert;
}
Instruction::PopJumpIfTrue { .. } => {}
_ => {
break 'instruction;
}
};
block.instructions[i].set_to_nop();
block.instructions[i + 1].set_to_nop();
block.instructions[jump_idx].instr = if invert {
Opcode::PopJumpIfNotNone
} else {
Opcode::PopJumpIfNone
}
.into();
break 'instruction;
}
if matches!(
const_instr,
Instruction::LoadConst { .. }
| Instruction::LoadSmallInt { .. }
| Instruction::LoadCommonConstant { .. }
) && matches!(next_instr, Instruction::ToBool)
&& let Some(value) = load_const_truthiness(const_instr, const_arg, metadata)
{
let const_idx = add_const(metadata, ConstantData::Boolean { value })?;
block.instructions[i].set_to_nop();
block.instructions[i + 1]
.instr_set_op1(Opcode::LoadConst.into(), OpArg::new(const_idx as u32));
break 'instruction;
}
}
if matches!(
block.instructions[i].instr.real_opcode(),
Some(Opcode::LoadConst)
) && let Some(constant) = get_const_value(metadata, &block.instructions[i])
{
block.instructions[i].maybe_instr_make_load_common_const(&constant);
}
}
Ok(())
}
/// flowgraph.c optimize_load_const
fn optimize_load_const(
metadata: &mut CodeUnitMetadata,
blocks: &mut Blocks,
) -> crate::InternalResult {
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next_block = blocks[block_idx].next;
let block = &mut blocks[block_idx];
basicblock_optimize_load_const(metadata, block)?;
block_idx = next_block;
}
Ok(())
}
#[cfg(test)]
impl CodeInfo {
fn debug_block_dump(&self) -> String {
let mut out = String::new();
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
use core::fmt::Write;
let block = &self.blocks[block_idx];
let block_return = if block.basicblock_returns() {
" return"
} else {
""
};
let _ = writeln!(
out,
"block {} next={} cold={} except={} preserve_lasti={} start_depth={}{}",
u32::from(block_idx),
if block.next == BlockIdx::NULL {
String::from("NULL")
} else {
u32::from(block.next).to_string()
},
block.cold,
block.except_handler,
block.preserve_lasti,
if block.start_depth < 0 {
String::from("None")
} else {
block.start_depth.to_string()
},
block_return,
);
for info in &block.instructions[..block.instruction_used] {
let lineno = info.instruction_lineno();
let _ = writeln!(
out,
" [disp={}:{} raw={}:{}-{}:{} override={:?}] {:?} arg={} target={}",
lineno,
info.location.character_offset.get(),
info.location.line.get(),
info.location.character_offset.get(),
info.end_location.line.get(),
info.end_location.character_offset.get(),
info.lineno_override,
info.instr,
u32::from(info.arg),
if info.target == BlockIdx::NULL {
String::from("NULL")
} else {
u32::from(info.target).to_string()
}
);
}
block_idx = block.next;
}
out
}
pub(crate) fn debug_late_cfg_trace(mut self) -> crate::InternalResult {
let mut trace = Vec::new();
trace.push(("initial".to_owned(), self.debug_block_dump()));
let instr_sequence = self.prepare_cfg_from_codegen();
self.blocks = cfg_from_instruction_sequence(instr_sequence)?;
trace.push((
"after_cfg_from_instruction_sequence".to_owned(),
self.debug_block_dump(),
));
translate_jump_labels_to_targets(&mut self.blocks)?;
self.blocks.mark_except_handlers();
label_exception_targets(&mut self.blocks)?;
self.blocks.check_cfg()?;
self.blocks.inline_small_or_no_lineno_blocks()?;
trace.push((
"after_inline_small_or_no_lineno_blocks".to_owned(),
self.debug_block_dump(),
));
self.blocks.remove_unreachable()?;
self.blocks
.resolve_line_numbers(self.metadata.firstlineno)?;
optimize_load_const(&mut self.metadata, &mut self.blocks)?;
trace.push((
"after_optimize_load_const".to_owned(),
self.debug_block_dump(),
));
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next_block = self.blocks[block_idx].next;
self.blocks
.optimize_basic_block(&mut self.metadata, block_idx)?;
block_idx = next_block;
}
trace.push((
"after_optimize_basic_block".to_owned(),
self.debug_block_dump(),
));
self.blocks.remove_redundant_nops_and_pairs();
self.blocks.remove_unreachable()?;
self.blocks.remove_redundant_nops_and_jumps()?;
#[cfg(debug_assertions)]
assert!(self.blocks.no_redundant_jumps());
self.blocks
.remove_unused_consts(&mut self.metadata.consts)?;
trace.push((
"after_optimize_cfg_cleanup".to_owned(),
self.debug_block_dump(),
));
let nlocals = self.metadata.varnames.len();
let nparams = self.nparams;
add_checks_for_loads_of_uninitialized_variables(&mut self.blocks, nlocals, nparams)?;
self.blocks.insert_superinstructions();
self.blocks.push_cold_blocks_to_end()?;
trace.push((
"after_push_cold_before_chain_reorder".to_owned(),
self.debug_block_dump(),
));
self.blocks
.resolve_line_numbers(self.metadata.firstlineno)?;
trace.push((
"after_push_cold_resolve_line_numbers".to_owned(),
self.debug_block_dump(),
));
trace.push((
"after_push_cold_blocks_to_end".to_owned(),
self.debug_block_dump(),
));
self.blocks.convert_pseudo_conditional_jumps()?;
trace.push((
"after_convert_pseudo_conditional_jumps".to_owned(),
self.debug_block_dump(),
));
let _max_stackdepth = self.blocks.calculate_stackdepth()?;
let _nlocalsplus = prepare_localsplus(&self.metadata, &mut self.blocks)?;
convert_pseudo_ops(&mut self.blocks)?;
trace.push((
"after_convert_pseudo_ops".to_owned(),
self.debug_block_dump(),
));
self.blocks.normalize_jumps()?;
#[cfg(debug_assertions)]
assert!(self.blocks.no_redundant_jumps());
trace.push(("after_normalize_jumps".to_owned(), self.debug_block_dump()));
self.blocks.optimize_load_fast()?;
trace.push((
"after_optimize_load_fast".to_owned(),
self.debug_block_dump(),
));
Ok(trace)
}
}
impl InstrDisplayContext for CodeInfo {
type Constant = ConstantData;
fn get_constant(&self, consti: oparg::ConstIdx) -> &ConstantData {
&self.metadata.consts[consti.as_usize()]
}
fn get_name(&self, i: usize) -> &str {
self.metadata.names[i].as_ref()
}
fn get_varname(&self, var_num: oparg::VarNum) -> &str {
self.metadata.varnames[var_num.as_usize()].as_ref()
}
fn get_localsplus_name(&self, var_num: oparg::VarNum) -> &str {
let idx = var_num.as_usize();
let nlocals = self.metadata.varnames.len();
if idx < nlocals {
self.metadata.varnames[idx].as_ref()
} else {
let cell_idx = idx - nlocals;
self.metadata
.cellvars
.get_index(cell_idx)
.unwrap_or_else(|| &self.metadata.freevars[cell_idx - self.metadata.cellvars.len()])
.as_ref()
}
}
}
const NOT_LOCAL: isize = -1;
const DUMMY_INSTR: isize = -1;
/// flowgraph.c LoadFastInstrFlag
#[derive(Clone, Copy, Eq, PartialEq)]
#[repr(u8)]
enum LoadFastInstrFlag {
SupportKilled = 1,
StoredAsLocal = 2,
RefUnconsumed = 4,
}
/// flowgraph.c ref
#[derive(Clone, Copy)]
struct Ref {
instr: isize,
local: isize,
}
/// flowgraph.c ref_stack
struct RefStack {
refs: Vec,
size: usize,
capacity: usize,
}
/// flowgraph.c ref_stack_push
fn ref_stack_push(stack: &mut RefStack, r: Ref) -> crate::InternalResult {
debug_assert_eq!(stack.refs.len(), stack.capacity);
if stack.size == stack.capacity {
let doubled = stack.capacity * 2;
let new_cap = 32.max(doubled);
stack
.refs
.try_reserve_exact(new_cap - stack.capacity)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
stack.refs.resize(new_cap, Ref { instr: 0, local: 0 });
stack.capacity = new_cap;
}
stack.refs[stack.size] = r;
stack.size += 1;
Ok(())
}
/// flowgraph.c ref_stack_pop
fn ref_stack_pop(stack: &mut RefStack) -> Ref {
assert!(stack.size > 0);
stack.size -= 1;
stack.refs[stack.size]
}
/// flowgraph.c ref_stack_swap_top
fn ref_stack_swap_top(stack: &mut RefStack, off: usize) {
assert!(off >= 2 && stack.size >= off);
let top = stack.size - 1;
let other = stack.size - off;
stack.refs.swap(top, other);
}
/// flowgraph.c ref_stack_at
fn ref_stack_at(stack: &RefStack, idx: usize) -> Ref {
assert!(idx < stack.size);
stack.refs[idx]
}
/// flowgraph.c ref_stack_clear
fn ref_stack_clear(stack: &mut RefStack) {
stack.size = 0;
}
/// flowgraph.c optimize_load_fast PUSH_REF
fn push_ref(stack: &mut RefStack, instr: isize, local: isize) -> crate::InternalResult {
ref_stack_push(stack, Ref { instr, local })
}
/// flowgraph.c kill_local
fn kill_local(instr_flags: &mut [u8], refs: &RefStack, local: isize) {
for i in 0..refs.size {
let r = ref_stack_at(refs, i);
if r.local != local {
continue;
}
debug_assert!(r.instr >= 0);
instr_flags[r.instr as usize] |= LoadFastInstrFlag::SupportKilled as u8;
}
}
/// flowgraph.c store_local
fn store_local(instr_flags: &mut [u8], refs: &RefStack, local: isize, r: Ref) {
kill_local(instr_flags, refs, local);
if r.instr != DUMMY_INSTR {
instr_flags[r.instr as usize] |= LoadFastInstrFlag::StoredAsLocal as u8;
}
}
fn local_as_ref_local(local: usize) -> isize {
local as isize
}
/// flowgraph.c load_fast_push_block
fn load_fast_push_block(
worklist: &mut CfgTraversalStack,
blocks: &mut Blocks,
target: BlockIdx,
start_depth: usize,
) {
debug_assert!(target != BlockIdx::NULL);
debug_assert!(blocks[target].start_depth >= 0);
debug_assert_eq!(blocks[target].start_depth as usize, start_depth,);
if !blocks[target].visited {
blocks[target].visited = true;
worklist.push(target);
}
}
fn stackdepth_push(
stack: &mut CfgTraversalStack,
blocks: &mut Blocks,
target: BlockIdx,
depth: i32,
) -> crate::InternalResult {
let block_depth = &mut blocks[target].start_depth;
if !(*block_depth < 0 || *block_depth == depth) {
return Err(InternalError::InconsistentStackDepth);
}
if *block_depth < depth && *block_depth < 100 {
debug_assert!(*block_depth < 0);
*block_depth = depth;
stack.push(target);
}
Ok(())
}
/// flowgraph.c stack_effects
#[derive(Clone, Copy, Eq, PartialEq)]
struct StackEffects {
net: i32,
}
/// flowgraph.c get_stack_effects
fn get_stack_effects(
instr: AnyInstruction,
oparg: OpArg,
jump: i32,
) -> crate::InternalResult {
if instr
.real()
.is_some_and(|op| op.as_opcode().deopt().is_some())
{
return Err(InternalError::InvalidStackEffect);
}
let oparg = u32::from(oparg);
let net = if instr.is_block_push() && jump == 0 {
0
} else if jump != 0 {
instr.stack_effect_jump(oparg)
} else {
instr.stack_effect(oparg)
};
Ok(StackEffects { net })
}
fn vec_try_reserve_exact(vec: &mut Vec, additional: usize) -> crate::InternalResult {
vec.try_reserve_exact(additional)
.map_err(|_| InternalError::MalformedControlFlowGraph)
}
fn vec_try_resize_to_double_capacity(vec: &mut Vec) -> crate::InternalResult {
let capacity = vec.capacity();
debug_assert!(capacity > 0);
let len = capacity
.checked_mul(core::mem::size_of::())
.ok_or(InternalError::MalformedControlFlowGraph)?;
if capacity == 0 || len > usize::MAX / 2 {
return Err(InternalError::MalformedControlFlowGraph);
}
let new_capacity = capacity * 2;
let additional = new_capacity
.checked_sub(vec.len())
.ok_or(InternalError::MalformedControlFlowGraph)?;
vec_try_reserve_exact(vec, additional)
}
/// assemble.c write_location_first_byte
fn write_location_first_byte(linetable: &mut Vec, code: u8, length: usize) {
linetable.extend(write_location_entry_start(code, length));
}
/// pycore_code.h write_location_entry_start
fn write_location_entry_start(code: u8, length: usize) -> [u8; 1] {
debug_assert!(length > 0 && length > 3;
let code = PyCodeLocationInfoKind::Short0 as u8 + column_group as u8;
write_location_first_byte(linetable, code, length);
write_location_byte(
linetable,
((column_low_bits as u8) 0 && length 0 && length = loc.line);
write_location_varint(linetable, (loc.end_line - loc.line) as u32);
write_location_varint(
linetable,
if loc.col < 0 { 0 } else { (loc.col as u32) + 1 },
);
write_location_varint(
linetable,
if loc.end_col < 0 {
0
} else {
(loc.end_col as u32) + 1
},
);
}
/// assemble.c write_location_info_none
fn write_location_info_none(linetable: &mut Vec, length: usize) {
write_location_first_byte(linetable, PyCodeLocationInfoKind::None as u8, length);
}
/// assemble.c write_location_info_no_column
fn write_location_info_no_column(linetable: &mut Vec, length: usize, line_delta: i32) {
write_location_first_byte(linetable, PyCodeLocationInfoKind::NoColumns as u8, length);
write_location_signed_varint(linetable, line_delta);
}
/// assemble.c write_location_info_entry
fn write_location_info_entry(
linetable: &mut Vec,
loc: LineTableLocation,
length: usize,
prev_line: &mut i32,
debug_ranges: bool,
) -> crate::InternalResult {
const THEORETICAL_MAX_ENTRY_SIZE: usize = 25;
if linetable
.len()
.checked_add(THEORETICAL_MAX_ENTRY_SIZE)
.ok_or(InternalError::MalformedControlFlowGraph)?
>= linetable.capacity()
{
debug_assert!(linetable.capacity() > THEORETICAL_MAX_ENTRY_SIZE);
vec_try_resize_to_double_capacity(linetable)?;
}
if loc.line == NO_LOCATION_OVERRIDE {
write_location_info_none(linetable, length);
return Ok(());
}
let line_delta = loc.line - *prev_line;
let column = loc.col;
let end_column = loc.end_col;
if !debug_ranges
|| ((column < 0 || end_column < 0) && (loc.end_line == loc.line || loc.end_line < 0))
{
write_location_info_no_column(linetable, length, line_delta);
*prev_line = loc.line;
return Ok(());
}
if loc.end_line == loc.line {
if line_delta == 0 && column < 80 && end_column - column < 16 && end_column >= column {
write_location_info_short_form(linetable, length, column, end_column);
return Ok(());
}
if (0..3).contains(&line_delta) && column < 128 && end_column < 128 {
write_location_info_oneline_form(linetable, length, line_delta, column, end_column);
*prev_line = loc.line;
return Ok(());
}
}
write_location_info_long_form(linetable, loc, length, line_delta);
*prev_line = loc.line;
Ok(())
}
/// assemble.c assemble_emit_location
fn assemble_emit_location(
linetable: &mut Vec,
loc: LineTableLocation,
mut size: usize,
prev_line: &mut i32,
debug_ranges: bool,
) -> crate::InternalResult {
if size == 0 {
return Ok(());
}
while size > 8 {
write_location_info_entry(linetable, loc, 8, prev_line, debug_ranges)?;
size -= 8;
}
write_location_info_entry(linetable, loc, size, prev_line, debug_ranges)
}
fn no_linetable_location() -> LineTableLocation {
LineTableLocation {
line: NO_LOCATION_OVERRIDE,
end_line: NO_LOCATION_OVERRIDE,
col: NO_LOCATION_OVERRIDE,
end_col: NO_LOCATION_OVERRIDE,
}
}
fn next_linetable_location() -> LineTableLocation {
LineTableLocation {
line: NEXT_LOCATION_OVERRIDE,
end_line: NEXT_LOCATION_OVERRIDE,
col: NEXT_LOCATION_OVERRIDE,
end_col: NEXT_LOCATION_OVERRIDE,
}
}
/// assemble.c assemble_emit_exception_table_item
fn assemble_emit_exception_table_item(table: &mut Vec, value: i32, mut msb: u8) {
debug_assert!((msb | 128) == 128);
debug_assert!((0..(1 = 1 > 24) as u8) | CONTINUATION_BIT | msb);
msb = 0;
}
if value >= 1 > 18) & 0x3f) as u8) | CONTINUATION_BIT | msb);
msb = 0;
}
if value >= 1 > 12) & 0x3f) as u8) | CONTINUATION_BIT | msb);
msb = 0;
}
if value >= 1 > 6) & 0x3f) as u8) | CONTINUATION_BIT | msb);
msb = 0;
}
table.push(((value & 0x3f) as u8) | msb);
}
/// assemble.c assemble_emit_exception_table_entry
fn assemble_emit_exception_table_entry(
table: &mut Vec,
start: i32,
end: i32,
handler_offset: i32,
handler: InstructionSequenceExceptHandlerInfo,
) -> crate::InternalResult {
const MAX_SIZE_OF_ENTRY: usize = 20;
if table
.len()
.checked_add(MAX_SIZE_OF_ENTRY)
.ok_or(InternalError::MalformedControlFlowGraph)?
>= table.capacity()
{
vec_try_resize_to_double_capacity(table)?;
}
let size = end - start;
debug_assert!(end > start);
let target = handler_offset;
let mut depth = handler.start_depth - 1;
if handler.preserve_lasti > 0 {
depth -= 1;
}
debug_assert!(depth >= 0);
let depth_lasti = (depth = 0 {
let handler_offset = instrs[handler.h_label as usize].i_offset;
assemble_emit_exception_table_entry(
&mut table,
start,
ioffset,
handler_offset,
handler,
)?;
}
start = ioffset;
handler = instr.except_handler;
}
ioffset += instr.info.instr_size() as i32;
}
if handler.h_label >= 0 {
let handler_offset = instrs[handler.h_label as usize].i_offset;
assemble_emit_exception_table_entry(&mut table, start, ioffset, handler_offset, handler)?;
}
Ok(table.into_boxed_slice())
}
/// pycore_opcode_utils.h IS_CONDITIONAL_JUMP_OPCODE
fn is_conditional_jump_opcode(instr: AnyInstruction) -> bool {
matches!(
instr.real().map(Into::into),
Some(
Opcode::PopJumpIfFalse
| Opcode::PopJumpIfTrue
| Opcode::PopJumpIfNone
| Opcode::PopJumpIfNotNone
)
)
}
/// flowgraph.c struct _PyCfgBuilder
struct CfgBuilder {
blocks: Blocks,
entry: BlockIdx,
block_list: BlockIdx,
current: BlockIdx,
current_label: InstructionSequenceLabel,
}
/// flowgraph.c cfg_builder_new_block
fn cfg_builder_new_block(g: &mut CfgBuilder) -> crate::InternalResult {
let block = g.blocks.blocks_new_block()?;
g.blocks[block].allocation_next = g.block_list;
g.blocks[block].cpython_label = InstructionSequenceLabel::NO_LABEL;
g.block_list = block;
Ok(block)
}
/// flowgraph.c cfg_builder_use_next_block
fn cfg_builder_use_next_block(g: &mut CfgBuilder, block: BlockIdx) -> BlockIdx {
debug_assert!(block != BlockIdx::NULL);
g.blocks[g.current].next = block;
g.current = block;
block
}
/// flowgraph.c init_cfg_builder
fn init_cfg_builder(g: &mut CfgBuilder) -> crate::InternalResult {
g.block_list = BlockIdx::NULL;
let block = cfg_builder_new_block(g)?;
g.entry = block;
g.current = block;
g.current_label = InstructionSequenceLabel::NO_LABEL;
Ok(())
}
/// flowgraph.c _PyCfgBuilder_New
fn cfg_builder_new() -> crate::InternalResult {
let mut builder = CfgBuilder {
blocks: Blocks::default(),
entry: BlockIdx::NULL,
block_list: BlockIdx::NULL,
current: BlockIdx::NULL,
current_label: InstructionSequenceLabel::NO_LABEL,
};
init_cfg_builder(&mut builder)?;
Ok(builder)
}
/// flowgraph.c cfg_builder_current_block_is_terminated
fn cfg_builder_current_block_is_terminated(g: &mut CfgBuilder) -> bool {
let block = &mut g.blocks[g.current];
let last = block.basicblock_last_instr().copied();
if last.is_some_and(|last| last.instr.is_terminator()) {
return true;
}
if is_label(g.current_label) {
if last.is_some() || is_label(block.cpython_label) {
return true;
}
block.cpython_label = g.current_label;
g.current_label = InstructionSequenceLabel::NO_LABEL;
}
false
}
/// flowgraph.c cfg_builder_maybe_start_new_block
fn cfg_builder_maybe_start_new_block(g: &mut CfgBuilder) -> crate::InternalResult {
if cfg_builder_current_block_is_terminated(g) {
let block = cfg_builder_new_block(g)?;
g.blocks[block].cpython_label = g.current_label;
g.current_label = InstructionSequenceLabel::NO_LABEL;
cfg_builder_use_next_block(g, block);
}
Ok(())
}
/// flowgraph.c _PyCfgBuilder_UseLabel
fn cfg_builder_use_label(
g: &mut CfgBuilder,
label_id: InstructionSequenceLabel,
) -> crate::InternalResult {
g.current_label = label_id;
cfg_builder_maybe_start_new_block(g)
}
/// flowgraph.c _PyCfgBuilder_Addop
fn cfg_builder_addop(g: &mut CfgBuilder, info: InstructionInfo) -> crate::InternalResult {
cfg_builder_maybe_start_new_block(g)?;
g.blocks[g.current].basicblock_addop(info)
}
/// flowgraph.c cfg_builder_check
fn cfg_builder_check(g: &CfgBuilder) -> bool {
debug_assert!(g.entry != BlockIdx::NULL);
debug_assert!(g.blocks[g.entry].instruction_used != 0);
let mut block = g.block_list;
while block != BlockIdx::NULL {
debug_assert!(block.idx() < g.blocks.len());
let block_ref = &g.blocks[block];
let has_instr_array = block_ref.instruction_allocation > 0;
if has_instr_array {
debug_assert!(block_ref.instruction_allocation > 0);
debug_assert_eq!(
block_ref.instructions.len(),
block_ref.instruction_allocation
);
debug_assert!(block_ref.instruction_allocation >= block_ref.instruction_used);
} else {
debug_assert_eq!(block_ref.instruction_used, 0);
debug_assert_eq!(block_ref.instruction_allocation, 0);
}
block = block_ref.allocation_next;
}
true
}
/// flowgraph.c _PyCfgBuilder_CheckSize
fn cfg_builder_check_size(g: &CfgBuilder) -> crate::InternalResult {
debug_assert!(g.entry != BlockIdx::NULL);
debug_assert!(g.block_list != BlockIdx::NULL);
debug_assert!(g.current != BlockIdx::NULL);
let mut nblocks = 0usize;
let mut block = g.block_list;
while block != BlockIdx::NULL {
debug_assert!(block.idx() < g.blocks.len());
nblocks += 1;
block = g.blocks[block].allocation_next;
}
debug_assert_eq!(nblocks, g.blocks.len());
if nblocks > usize::MAX / core::mem::size_of::() {
return Err(InternalError::MalformedControlFlowGraph);
}
Ok(())
}
/// flowgraph.c translate_jump_labels_to_targets
fn translate_jump_labels_to_targets(blocks: &mut Blocks) -> crate::InternalResult {
let max_label = get_max_label(blocks);
let label_count = (max_label + 1) as usize;
if label_count > usize::MAX / core::mem::size_of::() {
return Err(InternalError::MalformedControlFlowGraph);
}
let mut label_to_block = Vec::new();
vec_try_reserve_exact(&mut label_to_block, label_count)?;
label_to_block.resize(label_count, BlockIdx::NULL);
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let block = &blocks[block_idx];
if is_label(block.cpython_label) {
let label_id = block.cpython_label;
debug_assert!(label_id.0 = 0 && lbl crate::InternalResult {
instruction_sequence_apply_label_map(&mut instr_sequence);
let mut builder = cfg_builder_new()?;
for i in 0..instr_sequence.instr_used {
instr_sequence.instrs[i].i_target = 0;
}
for i in 0..instr_sequence.instr_used {
if instr_sequence.instrs[i].info.instr.has_target() {
let target_offset = u32::from(instr_sequence.instrs[i].info.arg) as usize;
debug_assert!(target_offset < instr_sequence.instr_used);
instr_sequence.instrs[target_offset].i_target = 1;
}
}
let InstructionSequence {
instrs,
instr_used,
label_map,
label_map_allocation,
annotations_code,
..
} = instr_sequence;
debug_assert!(label_map.is_none());
debug_assert_eq!(label_map_allocation, 0);
let mut offset = 0i32;
let mut i = 0;
while i < instr_used {
let mut entry = instrs[i];
if matches!(
entry.info.instr.pseudo(),
Some(PseudoInstruction::AnnotationsPlaceholder)
) {
if let Some(annotations_code) = &annotations_code {
debug_assert!(annotations_code.label_map.is_none());
debug_assert_eq!(annotations_code.label_map_allocation, 0);
for ann_entry in annotations_code
.instrs
.iter()
.take(annotations_code.instr_used)
{
debug_assert!(!ann_entry.info.instr.has_target());
let mut info = ann_entry.info;
info.target = BlockIdx::NULL;
cfg_builder_addop(&mut builder, info)?;
}
offset += annotations_code.instr_used as i32 - 1;
} else {
offset -= 1;
}
i += 1;
continue;
}
if entry.i_target != 0 {
let label_id = i as i32 + offset;
let label = InstructionSequenceLabel(label_id);
cfg_builder_use_label(&mut builder, label)?;
}
let opcode = entry.info.instr;
let mut oparg = entry.info.arg;
if opcode.has_target() {
let target_offset = u32::from(oparg) as i32 + offset;
debug_assert!(target_offset >= 0);
oparg = OpArg::new(target_offset as u32);
}
entry.info.instr = opcode;
entry.info.arg = oparg;
entry.info.target = BlockIdx::NULL;
cfg_builder_addop(&mut builder, entry.info)?;
i += 1;
}
cfg_builder_check_size(&builder)?;
debug_assert!(cfg_builder_check(&builder));
Ok(builder.blocks)
}
/// flowgraph.c maybe_push
fn maybe_push(
blocks: &mut Blocks,
worklist: &mut CfgTraversalStack,
block: BlockIdx,
unsafe_mask: u64,
) {
debug_assert!(block != BlockIdx::NULL);
let both = blocks[block].unsafe_locals_mask | unsafe_mask;
if blocks[block].unsafe_locals_mask != both {
blocks[block].unsafe_locals_mask = both;
if !blocks[block].visited {
worklist.push(block);
blocks[block].visited = true;
}
}
}
/// flowgraph.c scan_block_for_locals
fn scan_block_for_locals(
blocks: &mut Blocks,
block_idx: BlockIdx,
worklist: &mut CfgTraversalStack,
) {
let idx = block_idx.idx();
let mut unsafe_mask = blocks[idx].unsafe_locals_mask;
let instr_count = blocks[idx].instruction_used;
for i in 0..instr_count {
let (instr, arg, except_handler) = {
let info = &blocks[idx].instructions[i];
(
info.instr,
info.arg,
info.except_handler.map(|eh| eh.handler_block),
)
};
debug_assert!(!matches!(instr.real(), Some(Instruction::ExtendedArg)));
if let Some(handler_block) = except_handler {
maybe_push(blocks, worklist, handler_block, unsafe_mask);
}
let oparg = u32::from(arg) as usize;
if oparg >= LOCAL_UNSAFE_MASK_BITS {
continue;
}
let bit = 1u64 {
unsafe_mask |= bit;
}
AnyInstruction::Real(Instruction::StoreFast { .. }) => {
unsafe_mask &= !bit;
}
AnyInstruction::Real(Instruction::LoadFastCheck { .. }) => {
// If this doesn't raise, then the local is defined.
unsafe_mask &= !bit;
}
AnyInstruction::Real(Instruction::LoadFast { .. }) => {
if unsafe_mask & bit != 0 {
blocks[idx].instructions[i].instr = Opcode::LoadFastCheck.into();
}
unsafe_mask &= !bit;
}
_ => {}
}
}
let next = blocks[idx].next;
if next != BlockIdx::NULL && blocks[idx].bb_has_fallthrough() {
maybe_push(blocks, worklist, next, unsafe_mask);
}
let last = blocks[idx].basicblock_last_instr().copied();
if let Some(last) = last
&& last.is_jump()
{
let target = last.target;
debug_assert!(target != BlockIdx::NULL);
maybe_push(blocks, worklist, target, unsafe_mask);
}
}
/// flowgraph.c fast_scan_many_locals
fn fast_scan_many_locals(blocks: &mut Blocks, nlocals: usize) -> crate::InternalResult {
debug_assert!(nlocals > LOCAL_UNSAFE_MASK_BITS);
let mut states = Vec::new();
states
.try_reserve_exact(nlocals - LOCAL_UNSAFE_MASK_BITS)
.map_err(|_| InternalError::MalformedControlFlowGraph)?;
states.resize(nlocals - LOCAL_UNSAFE_MASK_BITS, 0usize);
let mut blocknum = 0usize;
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
blocknum += 1;
for i in 0..blocks[current].instruction_used {
let info = &mut blocks[current].instructions[i];
debug_assert!(!matches!(info.instr.real(), Some(Instruction::ExtendedArg)));
let arg = u32::from(info.arg) as usize;
if arg < LOCAL_UNSAFE_MASK_BITS {
continue;
}
debug_assert!(arg >= LOCAL_UNSAFE_MASK_BITS);
match info.instr {
AnyInstruction::Real(
Instruction::DeleteFast { .. } | Instruction::LoadFastAndClear { .. },
)
| AnyInstruction::Pseudo(PseudoInstruction::StoreFastMaybeNull { .. }) => {
debug_assert!(arg < nlocals);
states[arg - LOCAL_UNSAFE_MASK_BITS] = blocknum - 1;
}
AnyInstruction::Real(Instruction::StoreFast { .. }) => {
debug_assert!(arg < nlocals);
states[arg - LOCAL_UNSAFE_MASK_BITS] = blocknum;
}
AnyInstruction::Real(Instruction::LoadFast { .. }) => {
debug_assert!(arg < nlocals);
if states[arg - LOCAL_UNSAFE_MASK_BITS] != blocknum {
info.instr = Opcode::LoadFastCheck.into();
}
states[arg - LOCAL_UNSAFE_MASK_BITS] = blocknum;
}
_ => {}
}
}
current = blocks[current].next;
}
Ok(())
}
/// flowgraph.c add_checks_for_loads_of_uninitialized_variables
fn add_checks_for_loads_of_uninitialized_variables(
blocks: &mut Blocks,
mut nlocals: usize,
nparams: usize,
) -> crate::InternalResult {
if nlocals == 0 {
return Ok(());
}
if nlocals > LOCAL_UNSAFE_MASK_BITS {
fast_scan_many_locals(blocks, nlocals)?;
nlocals = LOCAL_UNSAFE_MASK_BITS;
}
let mut worklist = blocks.make_cfg_traversal_stack()?;
let mut start_mask = 0u64;
for i in nparams..nlocals {
start_mask |= 1u64 BlockIdx {
while idx != BlockIdx::NULL && blocks[idx].instruction_used == 0 {
idx = blocks[idx].next;
}
idx
}
/// flowgraph.c add_checks_for_loads_of_uninitialized_variables uses uint64_t masks.
const LOCAL_UNSAFE_MASK_BITS: usize = 64;
/// flowgraph.c MAX_COPY_SIZE
const MAX_COPY_SIZE: usize = 4;
/// flowgraph.c get_max_label
fn get_max_label(blocks: &Blocks) -> i32 {
let mut lbl = -1;
let mut current = BlockIdx(0);
while current != BlockIdx::NULL {
let cpython_label = blocks[current].cpython_label;
lbl = lbl.max(cpython_label.0);
current = blocks[current].next;
}
lbl
}
/// flowgraph.c make_except_stack
fn make_except_stack() -> CfgExceptStack {
let handlers = [BlockIdx::NULL; CO_MAXBLOCKS + 2];
debug_assert_eq!(handlers[0], BlockIdx::NULL);
CfgExceptStack { handlers, depth: 0 }
}
/// flowgraph.c copy_except_stack
fn copy_except_stack(stack: &CfgExceptStack) -> CfgExceptStack {
debug_assert!(stack.depth Option {
debug_assert!(stack.depth Option {
debug_assert!(setup.is_block_push());
let instr = setup.instr;
let target = setup.target;
debug_assert!(target != BlockIdx::NULL);
if matches!(
instr.pseudo(),
Some(PseudoInstruction::SetupWith { .. } | PseudoInstruction::SetupCleanup { .. })
) {
blocks[target].preserve_lasti = true;
}
debug_assert!(stack.depth 0);
stack.depth -= 1;
debug_assert!(stack.depth crate::InternalResult {
let mut todo = blocks.make_cfg_traversal_stack()?;
todo.push(BlockIdx(0));
blocks[0].visited = true;
blocks[0].except_stack = Some(make_except_stack());
while let Some(block_idx) = todo.pop() {
let bi = block_idx.idx();
debug_assert!(blocks[bi].visited);
let mut stack = Some(
blocks[bi]
.except_stack
.take()
.expect("visited exception block has an except stack"),
);
let mut handler = except_stack_top(stack.as_ref().expect("active exception stack"), blocks);
let mut last_yield_except_depth: i32 = -1;
let mut stack_transferred = false;
let instr_count = blocks[bi].instruction_used;
for i in 0..instr_count {
let info = blocks[bi].instructions[i];
let instr = info.instr;
let target = info.target;
let arg = info.arg;
if info.is_block_push() {
debug_assert!(target != BlockIdx::NULL);
if !blocks[target].visited {
blocks[target].except_stack = Some(copy_except_stack(
stack.as_ref().expect("active exception stack"),
));
todo.push(target);
blocks[target].visited = true;
}
handler = push_except_block(
stack.as_mut().expect("active exception stack"),
info,
blocks,
);
} else if instr.is_pop_block() {
handler = pop_except_block(stack.as_mut().expect("active exception stack"), blocks);
blocks[bi].instructions[i].set_to_nop();
} else if blocks[bi].instructions[i].is_jump() {
blocks[bi].instructions[i].except_handler = handler;
debug_assert_eq!(i, instr_count - 1);
// CPython label_exception_targets(): copy the except stack
// when this block can also fall through, otherwise transfer it
// to the jump target.
debug_assert!(target != BlockIdx::NULL);
if !blocks[target].visited {
if blocks[bi].bb_has_fallthrough() {
blocks[target].except_stack = Some(copy_except_stack(
stack.as_ref().expect("active exception stack"),
));
} else {
blocks[target].except_stack = stack.take();
stack_transferred = true;
todo.push(target);
blocks[target].visited = true;
break;
}
todo.push(target);
blocks[target].visited = true;
}
} else if matches!(instr.real(), Some(Instruction::YieldValue { .. })) {
blocks[bi].instructions[i].except_handler = handler;
last_yield_except_depth =
stack.as_ref().expect("active exception stack").depth as i32;
} else if let Some(Instruction::Resume { context: _ }) = instr.real() {
blocks[bi].instructions[i].except_handler = handler;
let resume_arg = u32::from(arg);
if resume_arg != u32::from(oparg::ResumeLocation::AtFuncStart)
&& resume_arg != u32::from(oparg::ResumeLocation::AtGenExprStart)
{
debug_assert!(last_yield_except_depth >= 0);
if last_yield_except_depth == 1 {
blocks[bi].instructions[i].arg =
OpArg::new(resume_arg | oparg::ResumeContext::DEPTH1_MASK);
}
last_yield_except_depth = -1;
}
} else {
blocks[bi].instructions[i].except_handler = handler;
}
}
let next = blocks[bi].next;
if !stack_transferred && blocks[bi].bb_has_fallthrough() {
debug_assert!(next != BlockIdx::NULL);
if next != BlockIdx::NULL && !blocks[next].visited {
blocks[next].except_stack = stack.take();
todo.push(next);
blocks[next].visited = true;
}
}
}
#[cfg(debug_assertions)]
{
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let block = &blocks[block_idx];
debug_assert!(block.except_stack.is_none());
block_idx = block.next;
}
}
Ok(())
}
/// Convert remaining pseudo ops to real instructions or NOP.
/// flowgraph.c convert_pseudo_ops
pub(crate) fn convert_pseudo_ops(blocks: &mut Blocks) -> crate::InternalResult {
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next = blocks[block_idx].next;
let block = &mut blocks[block_idx];
for i in 0..block.instruction_used {
let info = &mut block.instructions[i];
if info.is_block_push() {
info.set_to_nop();
} else if matches!(
info.instr.pseudo(),
Some(PseudoInstruction::LoadClosure { .. })
) {
debug_assert!(is_pseudo_target(
PseudoOpcode::LoadClosure,
Opcode::LoadFast
));
info.instr = Opcode::LoadFast.into();
} else if matches!(
info.instr.pseudo(),
Some(PseudoInstruction::StoreFastMaybeNull { .. })
) {
debug_assert!(is_pseudo_target(
PseudoOpcode::StoreFastMaybeNull,
Opcode::StoreFast
));
info.instr = Opcode::StoreFast.into();
}
}
block_idx = next;
}
// CPython flowgraph.c::convert_pseudo_ops() finishes by calling
// remove_redundant_nops_and_jumps().
blocks.remove_redundant_nops_and_jumps()
}
/// flowgraph.c build_cellfixedoffsets
pub(crate) fn build_cellfixedoffsets(
metadata: &CodeUnitMetadata,
) -> crate::InternalResult {
let nlocals = metadata.varnames.len();
let ncellvars = metadata.cellvars.len();
let nfreevars = metadata.freevars.len();
let noffsets = ncellvars + nfreevars;
let mut fixed = Vec::new();
vec_try_reserve_exact(&mut fixed, noffsets)?;
fixed.resize(noffsets, 0);
for (i, item) in fixed.iter_mut().enumerate().take(noffsets) {
*item = (nlocals + i) as i32;
}
for (oldindex, cell) in fixed.iter_mut().enumerate().take(ncellvars) {
let varname = metadata
.cellvars
.get_index(oldindex)
.expect("cellvar index is in range");
if let Some(varindex) = metadata.varnames.get_index_of(varname) {
let argoffset = varindex as i32;
*cell = argoffset;
}
}
Ok(fixed)
}
/// flowgraph.c fix_cell_offsets
pub(crate) fn fix_cell_offsets(
metadata: &CodeUnitMetadata,
blocks: &mut Blocks,
cellfixedoffsets: &mut [i32],
) -> usize {
let nlocals = metadata.varnames.len();
let ncellvars = metadata.cellvars.len();
let nfreevars = metadata.freevars.len();
let noffsets = ncellvars + nfreevars;
debug_assert_eq!(cellfixedoffsets.len(), noffsets);
let mut numdropped = 0usize;
for (i, cell) in cellfixedoffsets.iter_mut().enumerate().take(noffsets) {
if *cell == (i + nlocals) as i32 {
*cell -= numdropped as i32;
} else {
numdropped += 1;
}
}
let mut block_idx = BlockIdx(0);
while block_idx != BlockIdx::NULL {
let next = blocks[block_idx].next;
let block = &mut blocks[block_idx];
for i in 0..block.instruction_used {
let inst = &mut block.instructions[i];
debug_assert!(
!matches!(inst.instr.real(), Some(Instruction::ExtendedArg)),
"fix_cell_offsets is called before extended args are generated"
);
let oldoffset = u32::from(inst.arg) as i32;
match inst.instr {
AnyInstruction::Real(
Instruction::MakeCell { .. }
| Instruction::LoadDeref { .. }
| Instruction::StoreDeref { .. }
| Instruction::DeleteDeref { .. }
| Instruction::LoadFromDictOrDeref { .. },
)
| AnyInstruction::Pseudo(PseudoInstruction::LoadClosure { .. }) => {
debug_assert!(oldoffset >= 0);
debug_assert!(oldoffset < noffsets as i32);
let fixed_offset = cellfixedoffsets[oldoffset as usize];
debug_assert!(fixed_offset >= 0);
inst.arg = OpArg::new(fixed_offset as u32);
}
_ => {}
}
}
block_idx = next;
}
numdropped
}
#[cfg(test)]
mod tests {
use super::*;
use rustpython_compiler_core::bytecode::Arg;
fn int_const(value: i32) -> ConstantData {
ConstantData::Integer {
value: BigInt::from(value),
}
}
fn nan_const() -> ConstantData {
ConstantData::Float { value: f64::NAN }
}
#[test]
fn constant_pool_frozenset_key_ignores_order_and_duplicates_like_cpython() {
let mut pool = ConstantPool::default();
let (first, inserted) = pool.insert_full(ConstantData::Frozenset {
elements: vec![int_const(1), int_const(2)],
});
assert_eq!(first, 0);
assert!(inserted);
let (second, inserted) = pool.insert_full(ConstantData::Frozenset {
elements: vec![int_const(2), int_const(1), int_const(1)],
});
assert_eq!(
second, first,
"CPython _PyCode_ConstantKey uses frozenset item keys, not insertion order"
);
assert!(!inserted);
assert!(matches!(
&pool.constants[first],
ConstantData::Frozenset { elements } if elements.len() == 2
));
}
#[test]
fn constant_pool_frozenset_key_preserves_nan_duplicates_like_cpython() {
let mut pool = ConstantPool::default();
let (idx, inserted) = pool.insert_full(ConstantData::Frozenset {
elements: vec![nan_const(), nan_const()],
});
assert_eq!(idx, 0);
assert!(inserted);
assert!(matches!(
&pool.constants[idx],
ConstantData::Frozenset { elements }
if elements.iter().filter(|constant| {
matches!(constant, ConstantData::Float { value } if value.is_nan())
}).count() == 2
));
}
fn test_location(line: u32) -> SourceLocation {
SourceLocation {
line: OneIndexed::new(line as usize).expect("valid line number"),
character_offset: OneIndexed::MIN,
}
}
fn test_instr(instr: Instruction, line: u32) -> InstructionInfo {
InstructionInfo {
instr: instr.into(),
arg: OpArg::new(0),
target: BlockIdx::NULL,
location: test_location(line),
end_location: test_location(line),
except_handler: None,
semantic_location: None,
lineno_override: None,
}
}
fn test_jump(target: BlockIdx, line: u32) -> InstructionInfo {
let mut instr = test_instr(Instruction::Nop, line);
instr.instr = PseudoOpcode::Jump.into();
instr.target = target;
instr
}
fn test_cond_jump(target: BlockIdx, line: u32) -> InstructionInfo {
let mut instr = test_instr(Instruction::Nop, line);
instr.instr = PseudoOpcode::JumpIfFalse.into();
instr.target = target;
instr
}
fn test_true_cond_jump(target: BlockIdx, line: u32) -> InstructionInfo {
let mut instr = test_instr(Instruction::Nop, line);
instr.instr = PseudoOpcode::JumpIfTrue.into();
instr.target = target;
instr
}
fn test_block_push(block: &mut Block, info: InstructionInfo) {
let off = block
.basicblock_next_instr()
.expect("test block instruction slot");
block.instructions[off] = info;
}
fn test_code_info(block: Block) -> CodeInfo {
CodeInfo {
flags: CodeFlags::empty(),
source_path: "source_path".to_owned(),
private: None,
blocks: Blocks::from([block]),
current_block: BlockIdx::new(0),
instr_sequence: instruction_sequence_new(),
instr_sequence_label_map: InstructionSequenceLabelMap::new(),
annotations_instr_sequence: None,
metadata: CodeUnitMetadata {
name: "".to_owned(),
qualname: Some("".to_owned()),
consts: Default::default(),
names: IndexSet::default(),
varnames: IndexSet::default(),
cellvars: IndexSet::default(),
freevars: IndexSet::default(),
fast_hidden: IndexMap::default(),
fast_hidden_final: IndexSet::default(),
argcount: 0,
posonlyargcount: 0,
kwonlyargcount: 0,
firstlineno: OneIndexed::MIN,
},
static_attributes: None,
in_inlined_comp: false,
fblock: Vec::new(),
symbol_table_index: 0,
nparams: 0,
in_conditional_block: 0,
next_conditional_annotation_index: 0,
}
}
#[test]
fn rejected_constant_append_fold_preserves_instructions() {
for (build, append, intrinsic) in [
(Opcode::BuildList, Opcode::ListAppend, false),
(Opcode::BuildSet, Opcode::SetAdd, false),
(Opcode::BuildList, Opcode::ListAppend, true),
] {
let mut block = Block::default();
for (index, (opcode, arg)) in [
(build, 0),
(
Opcode::LoadCommonConstant,
oparg::CommonConstant::BuiltinAny as u32,
),
(append, 1),
(Opcode::LoadSmallInt, 7),
(append, 1),
]
.into_iter()
.enumerate()
{
let mut instr = test_instr(Instruction::Nop, index as u32 + 1);
instr.instr = opcode.into();
instr.arg = OpArg::new(arg);
test_block_push(&mut block, instr);
}
let target = if intrinsic {
let mut instr = test_instr(Instruction::Nop, 6);
instr.instr = Opcode::CallIntrinsic1.into();
instr.arg = OpArg::new(IntrinsicFunction1::ListToTuple as u32);
test_block_push(&mut block, instr);
5
} else {
4
};
let before = block.instructions.clone();
let mut metadata = test_code_info(Block::default()).metadata;
metadata.consts.insert_full(int_const(42));
let consts_before = metadata.consts.clone().into_vec();
// BuiltinAny is a valid common constant but has no ConstantData
// representation. Reject the fold before changing any of its tail.
assert!(
!fold_constant_sequence_into_load_const(&mut metadata, &mut block, target).unwrap()
);
assert_eq!(metadata.consts.clone().into_vec(), consts_before);
assert_eq!(block.instructions.len(), before.len());
for (actual, expected) in block.instructions.iter().zip(&before) {
assert_eq!(actual.instr.real_opcode(), expected.instr.real_opcode());
assert_eq!(u32::from(actual.arg), u32::from(expected.arg));
assert_eq!(actual.target, expected.target);
assert_eq!(actual.location, expected.location);
assert_eq!(actual.end_location, expected.end_location);
assert_eq!(actual.except_handler, expected.except_handler);
assert_eq!(actual.semantic_location, expected.semantic_location);
assert_eq!(actual.lineno_override, expected.lineno_override);
}
}
}
#[test]
fn get_stack_effects_rejects_cpython_deopt_opcodes() {
match get_stack_effects(Instruction::BinaryOpAddInt.into(), OpArg::new(0), 0) {
Err(InternalError::InvalidStackEffect) => {}
Err(err) => panic!("unexpected stack-effect error: {err}"),
Ok(_) => panic!("CPython get_stack_effects rejects specialized deopt opcodes"),
}
}
#[test]
fn instruction_sequence_label_shadow_preserves_cpython_offset_aliases() {
let mut seq = instruction_sequence_new();
let mut labels = InstructionSequenceLabelMap::new();
instruction_sequence_label_map_push_unmapped_label(&mut labels, &mut seq).unwrap();
instruction_sequence_label_map_push_unmapped_label(&mut labels, &mut seq).unwrap();
assert_eq!(
labels.cpython_block_by_label.len(),
INITIAL_INSTR_SEQUENCE_LABELS_MAP_SIZE
);
let first = BlockIdx::new(1);
let second = BlockIdx::new(2);
assert_ne!(
instruction_sequence_label_map_label_for_block(&labels, first),
instruction_sequence_label_map_label_for_block(&labels, second)
);
// CPython `_PyInstructionSequence_UseLabel()` can map consecutive
// labels to the same instruction offset. The codegen CFG shadow must
// resolve the later block label to the block owning that shared offset.
instruction_sequence_label_map_use_label_at_block(&mut labels, &mut seq, second, first)
.unwrap();
assert_eq!(
instruction_sequence_label_map_resolve_label(&labels, first),
first
);
assert_eq!(
instruction_sequence_label_map_resolve_label(&labels, second),
first
);
}
#[test]
fn except_stack_tracks_cpython_depth_and_handler_slots() {
let mut stack = make_except_stack();
assert_eq!(stack.depth, 0);
assert_eq!(stack.handlers.len(), CO_MAXBLOCKS + 2);
assert_eq!(stack.handlers[0], BlockIdx::NULL);
let mut blocks = Blocks::from([Block::default(), Block::default()]);
assert!(except_stack_top(&stack, &blocks).is_none());
let setup = InstructionInfo {
instr: PseudoOpcode::SetupWith.into(),
arg: OpArg::new(0),
target: BlockIdx::new(1),
location: SourceLocation::default(),
end_location: SourceLocation::default(),
except_handler: None,
semantic_location: None,
lineno_override: None,
};
let handler = push_except_block(&mut stack, setup, &mut blocks).unwrap();
assert_eq!(stack.depth, 1);
assert_eq!(stack.handlers[1], BlockIdx::new(1));
assert_eq!(handler.handler_block, BlockIdx::new(1));
assert!(handler.preserve_lasti);
assert!(blocks[1].preserve_lasti);
let copy = copy_except_stack(&stack);
assert_eq!(copy.depth, stack.depth);
assert_eq!(copy.handlers, stack.handlers);
assert!(pop_except_block(&mut stack, &blocks).is_none());
assert_eq!(stack.depth, 0);
}
#[test]
fn ref_stack_tracks_cpython_size_and_allocated_refs() {
let mut stack = RefStack {
refs: Vec::new(),
size: 0,
capacity: 0,
};
ref_stack_push(&mut stack, Ref { instr: 7, local: 3 }).unwrap();
assert_eq!(stack.size, 1);
assert_eq!(stack.capacity, 32);
assert_eq!(stack.refs.len(), 32);
assert_eq!(ref_stack_at(&stack, 0).instr, 7);
assert_eq!(ref_stack_at(&stack, 0).local, 3);
ref_stack_clear(&mut stack);
assert_eq!(stack.size, 0);
assert_eq!(stack.capacity, 32);
assert_eq!(stack.refs.len(), 32);
ref_stack_push(
&mut stack,
Ref {
instr: DUMMY_INSTR,
local: NOT_LOCAL,
},
)
.unwrap();
assert_eq!(stack.size, 1);
assert_eq!(ref_stack_pop(&mut stack).instr, DUMMY_INSTR);
assert_eq!(stack.size, 0);
}
#[test]
fn cfg_traversal_stack_resets_visited_and_allocates_for_blocks() {
let mut blocks = Blocks::from([Block::default(), Block::default()]);
blocks[0].next = BlockIdx::new(1);
blocks[0].visited = true;
blocks[1].visited = true;
let mut stack = blocks.make_cfg_traversal_stack().unwrap();
assert!(!blocks[0].visited);
assert!(!blocks[1].visited);
assert!(stack.capacity() >= 2);
assert_eq!(stack.pop(), None);
stack.push(BlockIdx::new(1));
stack.push(BlockIdx::new(0));
assert_eq!(stack.pop(), Some(BlockIdx::new(0)));
assert_eq!(stack.pop(), Some(BlockIdx::new(1)));
assert_eq!(stack.pop(), None);
}
#[test]
fn instruction_sequence_insert_preserves_cpython_slot_metadata() {
let handler = InstructionSequenceExceptHandlerInfo {
h_label: 7,
start_depth: 3,
preserve_lasti: 1,
};
let mut seq = instruction_sequence_new();
let entry = instruction_sequence_addop(&mut seq, test_instr(Instruction::Nop, 11)).unwrap();
entry.except_handler = handler;
entry.i_target = 1;
entry.i_offset = 42;
instruction_sequence_insert_instruction(&mut seq, 0, test_instr(Instruction::PopTop, 12))
.unwrap();
// CPython `_PyInstructionSequence_InsertInstruction()` shifts the
// backing instruction slots, then overwrites only opcode/oparg/loc.
let inserted = &seq.instrs[0];
assert!(matches!(
inserted.info.instr.real(),
Some(Instruction::PopTop)
));
assert_eq!(inserted.except_handler.h_label, handler.h_label);
assert_eq!(inserted.except_handler.start_depth, handler.start_depth);
assert_eq!(
inserted.except_handler.preserve_lasti,
handler.preserve_lasti
);
assert_eq!(inserted.i_target, 1);
assert_eq!(inserted.i_offset, 42);
}
#[test]
fn instruction_sequence_tracks_cpython_c_array_allocation() {
let mut seq = instruction_sequence_new();
for i in 0..99 {
instruction_sequence_addop(&mut seq, test_instr(Instruction::Nop, 10 + i)).unwrap();
}
assert_eq!(seq.instr_allocation, INITIAL_INSTR_SEQUENCE_SIZE);
assert_eq!(seq.instrs.len(), seq.instr_allocation);
assert_eq!(seq.instr_used, 99);
// CPython calls `_Py_CArray_EnsureCapacity(s_used + 1)`, so the 100th
// instruction expands a 100-slot array to 200 before returning offset 99.
instruction_sequence_addop(&mut seq, test_instr(Instruction::Nop, 109)).unwrap();
assert_eq!(seq.instr_allocation, INITIAL_INSTR_SEQUENCE_SIZE * 2);
assert_eq!(seq.instrs.len(), seq.instr_allocation);
assert_eq!(seq.instr_used, 100);
}
#[test]
fn instruction_sequence_label_map_tracks_cpython_c_array_allocation() {
let mut seq = instruction_sequence_new();
instruction_sequence_use_label(&mut seq, InstructionSequenceLabel::from_index(1)).unwrap();
assert_eq!(
seq.label_map_allocation,
INITIAL_INSTR_SEQUENCE_LABELS_MAP_SIZE
);
assert_eq!(
seq.label_map.as_ref().expect("label map allocated").len(),
INITIAL_INSTR_SEQUENCE_LABELS_MAP_SIZE
);
// CPython passes the label id itself to `_Py_CArray_EnsureCapacity()`.
// Label 10 therefore expands the initial 10-slot map to 20.
instruction_sequence_use_label(&mut seq, InstructionSequenceLabel::from_index(10)).unwrap();
assert_eq!(
seq.label_map_allocation,
INITIAL_INSTR_SEQUENCE_LABELS_MAP_SIZE * 2
);
}
#[test]
fn basicblock_addop_reuses_cpython_spare_except_handler_slot() {
let handler = ExceptHandlerInfo {
handler_block: BlockIdx::new(7),
preserve_lasti: true,
};
let mut block = Block::default();
let mut stale = test_instr(Instruction::Nop, 11);
stale.except_handler = Some(handler);
test_block_push(&mut block, stale);
block.basicblock_clear();
block
.basicblock_addop(test_instr(Instruction::PopTop, 12))
.expect("basicblock_addop succeeds");
// CPython `basicblock_addop()` writes opcode/oparg/target/location into
// the reused `b_instr[b_iused]` slot, but does not clear `i_except`.
assert_eq!(block.instruction_used, 1);
assert_eq!(block.instructions[0].except_handler, Some(handler));
assert_eq!(block.instructions[0].target, BlockIdx::NULL);
}
#[test]
fn basicblock_next_instr_tracks_cpython_c_array_allocation() {
let mut block = Block::default();
for i in 0..15 {
block
.basicblock_addop(test_instr(Instruction::PopTop, 10 + i))
.expect("basicblock_addop succeeds");
}
assert_eq!(block.instruction_allocation, DEFAULT_BLOCK_SIZE);
// CPython calls `_Py_CArray_EnsureCapacity(b_iused + 1)`, so the 16th
// instruction expands a 16-slot array to 32 before returning offset 15.
block
.basicblock_addop(test_instr(Instruction::PopTop, 25))
.expect("basicblock_addop succeeds");
assert_eq!(block.instruction_allocation, DEFAULT_BLOCK_SIZE * 2);
}
#[test]
fn basicblock_insert_instruction_consumes_spare_without_inheriting_except_handler() {
let handler = ExceptHandlerInfo {
handler_block: BlockIdx::new(9),
preserve_lasti: false,
};
let mut block = Block::default();
test_block_push(&mut block, test_instr(Instruction::Nop, 21));
let mut stale = test_instr(Instruction::Nop, 22);
stale.except_handler = Some(handler);
test_block_push(&mut block, stale);
block.instruction_used = 1;
block
.basicblock_insert_instruction(0, test_instr(Instruction::PopTop, 23))
.expect("basicblock_insert_instruction succeeds");
// CPython `basicblock_insert_instruction()` also obtains a slot with
// `basicblock_next_instr()`, then overwrites the inserted position with
// the provided instruction copy, including its `i_except` value.
assert_eq!(block.instruction_used, 2);
assert_eq!(block.instructions[0].except_handler, None);
}
#[test]
fn basicblock_clear_preserves_cpython_spare_slots() {
let handler = ExceptHandlerInfo {
handler_block: BlockIdx::new(3),
preserve_lasti: true,
};
let mut block = Block::default();
let mut stale = test_instr(Instruction::PopTop, 31);
stale.except_handler = Some(handler);
test_block_push(&mut block, stale);
block.basicblock_clear();
block
.basicblock_addop(test_instr(Instruction::Nop, 32))
.expect("basicblock_addop succeeds");
// CPython `remove_unreachable()` sets `b_iused = 0` without clearing the
// backing `b_instr` slot. A later `basicblock_addop()` reuses that slot
// and does not overwrite `i_except`.
assert_eq!(block.instruction_used, 1);
assert_eq!(block.instructions[0].except_handler, Some(handler));
}
#[test]
fn basicblock_clear_reuses_cpython_spare_slots_in_offset_order() {
let mut block = Block::default();
for i in 0..3 {
let mut stale = test_instr(Instruction::Nop, 35 + i);
stale.except_handler = Some(ExceptHandlerInfo {
handler_block: BlockIdx::new(i + 1),
preserve_lasti: false,
});
test_block_push(&mut block, stale);
}
block.basicblock_clear();
for i in 0..3 {
block
.basicblock_addop(test_instr(Instruction::PopTop, 38 + i))
.expect("basicblock_addop succeeds");
}
let handlers = block
.used_instructions()
.iter()
.map(|instr| {
instr
.except_handler
.expect("reused CPython slot")
.handler_block
})
.collect::();
assert_eq!(
handlers,
[BlockIdx::new(1), BlockIdx::new(2), BlockIdx::new(3)]
);
}
#[test]
fn basicblock_append_instructions_overwrites_cpython_spare_slot() {
let handler = ExceptHandlerInfo {
handler_block: BlockIdx::new(5),
preserve_lasti: false,
};
let mut blocks = Blocks::from([Block::default(), Block::default()]);
let mut stale = test_instr(Instruction::Nop, 41);
stale.except_handler = Some(handler);
test_block_push(&mut blocks[0], stale);
blocks[0].basicblock_clear();
test_block_push(&mut blocks[1], test_instr(Instruction::PopTop, 42));
blocks
.basicblock_append_block_instructions(BlockIdx::new(0), BlockIdx::new(1))
.expect("basicblock_append_block_instructions succeeds");
// CPython `basicblock_append_instructions()` obtains a slot with
// `basicblock_next_instr()`, then overwrites it with the copied
// instruction, including `i_except`.
assert_eq!(blocks[0].instruction_used, 1);
assert_eq!(blocks[0].instructions[0].except_handler, None);
}
#[test]
fn instr_set_op0_nop_preserves_cpython_stale_target() {
let mut info = test_jump(BlockIdx::new(1), 50);
info.set_to_nop();
assert_eq!(info.target, BlockIdx::new(1));
let mut blocks = Blocks::from([Block::default(), Block::default()]);
test_block_push(&mut blocks[0], info);
blocks[0].next = BlockIdx::new(1);
let mut instr_sequence = instruction_sequence_new();
blocks
.cfg_to_instruction_sequence(&mut instr_sequence)
.expect("non-target NOP should ignore stale CPython i_target");
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "target_block != BlockIdx::NULL")]
fn cfg_to_instruction_sequence_requires_target_for_target_opcodes() {
let mut block = Block::default();
test_block_push(&mut block, test_jump(BlockIdx::NULL, 51));
let mut blocks = Blocks::from([block]);
let mut instr_sequence = instruction_sequence_new();
let _ = blocks.cfg_to_instruction_sequence(&mut instr_sequence);
}
#[test]
fn static_swaps_respect_cpython_no_location_line_boundary() {
let mut block = Block::default();
let mut swap = test_instr(Opcode::Swap.into(), 60);
swap.arg = OpArg::new(2);
let mut store = test_instr(Opcode::StoreFast.into(), 60);
store.arg = OpArg::new(0);
let mut pop = test_instr(Instruction::PopTop, 60);
pop.lineno_override = Some(NO_LOCATION_OVERRIDE);
for info in [swap, store, pop] {
test_block_push(&mut block, info);
}
block
.apply_static_swaps_block()
.expect("apply_static_swaps_block succeeds");
// CPython `next_swappable_instruction()` compares `i_loc.lineno`
// directly, so a following NO_LOCATION swaperand does not match the
// first swaperand's positive line number.
assert!(matches!(
block.instructions[0].instr.real(),
Some(Instruction::Swap { .. })
));
assert!(matches!(
block.instructions[1].instr.real(),
Some(Instruction::StoreFast { .. })
));
assert!(matches!(
block.instructions[2].instr.real(),
Some(Instruction::PopTop)
));
let mut block = Block::default();
let mut swap = test_instr(Opcode::Swap.into(), 70);
swap.arg = OpArg::new(2);
let mut store = test_instr(Opcode::StoreFast.into(), 70);
store.arg = OpArg::new(0);
store.lineno_override = Some(NO_LOCATION_OVERRIDE);
let pop = test_instr(Instruction::PopTop, 71);
for info in [swap, store, pop] {
test_block_push(&mut block, info);
}
block
.apply_static_swaps_block()
.expect("apply_static_swaps_block succeeds");
// Conversely, when the first swaperand has NO_LOCATION, CPython passes
// `-1` as the line filter and does not enforce a boundary.
assert!(matches!(
block.instructions[0].instr.real_opcode(),
Some(Opcode::Nop)
));
assert!(matches!(
block.instructions[1].instr.real_opcode(),
Some(Opcode::PopTop)
));
assert!(matches!(
block.instructions[2].instr.real_opcode(),
Some(Opcode::StoreFast)
));
}
#[test]
fn optimize_load_const_tracks_cpython_copy_of_load_const() {
let mut block = Block::default();
test_block_push(&mut block, test_instr(Opcode::LoadConst.into(), 80));
let mut copy = test_instr(Opcode::Copy.into(), 80);
copy.arg = OpArg::new(1);
test_block_push(&mut block, copy);
test_block_push(&mut block, test_instr(Instruction::ToBool, 80));
let mut code = test_code_info(block);
let (const_idx, _) = code.metadata.consts.insert_full(ConstantData::Tuple {
elements: vec![ConstantData::Integer {
value: BigInt::from(1),
}],
});
code.blocks[0].instructions[0].arg = OpArg::new(const_idx as u32);
optimize_load_const(&mut code.metadata, &mut code.blocks)
.expect("optimize_load_const succeeds");
// CPython `basicblock_optimize_load_const()` keeps the previous
// LOAD_CONST as the effective opcode for a following `COPY 1`, so the
// COPY is NOPed and TO_BOOL becomes LOAD_COMMON_CONSTANT True.
assert!(matches!(
code.blocks[0].instructions[0].instr.real(),
Some(Instruction::LoadConst { .. })
));
assert!(matches!(
code.blocks[0].instructions[1].instr.real(),
Some(Instruction::Nop)
));
let load_bool = &code.blocks[0].instructions[2];
assert!(matches!(
load_bool.instr.real(),
Some(Instruction::LoadCommonConstant { .. })
));
assert_eq!(
u32::from(load_bool.arg),
u32::from(oparg::CommonConstant::True)
);
}
#[test]
fn optimize_load_const_pseudo_opcode_breaks_effective_load_const() {
let mut block = Block::default();
test_block_push(
&mut block,
test_instr(
Instruction::LoadConst {
consti: Arg::marker(),
},
90,
),
);
test_block_push(&mut block, test_true_cond_jump(BlockIdx::new(0), 90));
let mut copy = test_instr(Instruction::Copy { i: Arg::marker() }, 90);
copy.arg = OpArg::new(1);
test_block_push(&mut block, copy);
test_block_push(&mut block, test_instr(Instruction::ToBool, 90));
let mut code = test_code_info(block);
let (const_idx, _) = code.metadata.consts.insert_full(ConstantData::Tuple {
elements: vec![ConstantData::Integer {
value: BigInt::from(1),
}],
});
code.blocks[0].instructions[0].arg = OpArg::new(const_idx as u32);
optimize_load_const(&mut code.metadata, &mut code.blocks)
.expect("optimize_load_const succeeds");
// `basicblock_optimize_load_const()` assigns the current
// pseudo opcode to its effective opcode slot, so the following COPY 1
// is not treated as a copy of the earlier LOAD_CONST.
assert!(matches!(
code.blocks[0].instructions[1].instr.pseudo(),
Some(PseudoInstruction::Jump { .. })
));
assert!(matches!(
code.blocks[0].instructions[2].instr.real(),
Some(Instruction::Copy { .. })
));
assert!(matches!(
code.blocks[0].instructions[3].instr.real(),
Some(Instruction::ToBool)
));
}
#[test]
fn optimize_load_fast_records_no_input_opcode_ref_at_cpython_instruction_index() {
let mut block = Block::default();
test_block_push(&mut block, test_instr(Opcode::LoadFast.into(), 10));
test_block_push(&mut block, test_instr(Instruction::GetLen, 10));
let mut swap = test_instr(Opcode::Swap.into(), 10);
swap.arg = OpArg::new(2);
test_block_push(&mut block, swap);
test_block_push(&mut block, test_instr(Instruction::PopTop, 10));
let mut code = test_code_info(block);
code.blocks
.optimize_load_fast()
.expect("optimize_load_fast succeeds");
// CPython records GET_LEN's result at instruction index 1. The
// SWAP/POP_TOP consumes the original local reference, so it can borrow.
assert!(matches!(
code.blocks[0].instructions[0].instr.real(),
Some(Instruction::LoadFastBorrow { .. })
));
}
#[test]
fn empty_tuple_repeat_folds_negative_count_like_cpython() {
let folded = const_folding_safe_multiply(
&ConstantData::Tuple {
elements: Vec::new(),
},
&ConstantData::Integer {
value: BigInt::from(-1),
},
)
.expect("CPython skips repeat-count checks for empty tuples");
assert!(matches!(
folded,
ConstantData::Tuple { elements } if elements.is_empty()
));
}
#[test]
fn resolve_line_numbers_duplicates_exit_blocks_like_cpython() {
let exit = BlockIdx::new(2);
let mut blocks = Blocks::from([Block::default(), Block::default(), Block::default()]);
blocks[0].cpython_label = InstructionSequenceLabel::from_index(0);
blocks[1].cpython_label = InstructionSequenceLabel::from_index(1);
blocks[2].cpython_label = InstructionSequenceLabel::from_index(2);
blocks[0].next = BlockIdx::new(1);
test_block_push(&mut blocks[0], test_cond_jump(exit, 10));
blocks[1].next = exit;
test_block_push(&mut blocks[1], test_jump(exit, 20));
test_block_push(&mut blocks[2], test_instr(Instruction::ReturnValue, 30));
blocks[2].instructions[0].lineno_override = Some(NO_LOCATION_OVERRIDE);
blocks
.remove_unreachable()
.expect("remove_unreachable succeeds");
blocks
.resolve_line_numbers(OneIndexed::MIN)
.expect("resolve_line_numbers succeeds");
// CPython `duplicate_exits_without_lineno()` copies a shared exit block
// reached by jumps so each copy can inherit its sole predecessor's line.
let duplicate = blocks[0].instructions[0].target;
assert_ne!(duplicate, exit);
assert_eq!(
blocks[duplicate].cpython_label,
InstructionSequenceLabel::from_index(3)
);
assert_eq!(blocks[duplicate].instructions[0].instruction_lineno(), 10);
assert_eq!(blocks[1].instructions[0].target, exit);
assert_eq!(blocks[exit].instructions[0].instruction_lineno(), 20);
}
#[test]
fn propagate_line_numbers_treats_next_location_like_cpython() {
let mut block = Block::default();
test_block_push(&mut block, test_instr(Instruction::Nop, 10));
test_block_push(&mut block, test_instr(Instruction::PopTop, 20));
block.instructions[1].lineno_override = Some(NEXT_LOCATION_OVERRIDE);
test_block_push(&mut block, test_instr(Instruction::ReturnValue, 30));
block.instructions[2].lineno_override = Some(NO_LOCATION_OVERRIDE);
let mut blocks = Blocks::from([block]);
blocks
.remove_unreachable()
.expect("remove_unreachable succeeds");
blocks.propagate_line_numbers();
// CPython `propagate_line_numbers()` only copies over NO_LOCATION
// (`lineno == NO_LOCATION`). `NEXT_LOCATION` (`lineno == -2`) becomes the
// current previous location and is copied to following NO_LOCATION
// instructions for assemble.c to resolve later.
assert_eq!(
blocks[0].instructions[1].lineno_override,
Some(NEXT_LOCATION_OVERRIDE)
);
assert_eq!(
blocks[0].instructions[2].lineno_override,
Some(NEXT_LOCATION_OVERRIDE)
);
}
#[test]
fn propagate_line_numbers_updates_empty_jump_target_raw_slot_like_cpython() {
let mut blocks = Blocks::from([Block::default(), Block::default(), Block::default()]);
blocks[0].next = BlockIdx::new(2);
test_block_push(&mut blocks[0], test_cond_jump(BlockIdx::new(1), 10));
test_block_push(&mut blocks[1], test_instr(Instruction::Nop, 20));
blocks[1].instructions[0].lineno_override = Some(NO_LOCATION_OVERRIDE);
blocks[1].basicblock_clear();
test_block_push(&mut blocks[2], test_instr(Instruction::ReturnValue, 30));
blocks
.remove_unreachable()
.expect("remove_unreachable succeeds");
blocks.propagate_line_numbers();
// CPython `propagate_line_numbers()` directly reads `target->b_instr[0]`
// for jump targets without checking `b_iused`. If
// `remove_redundant_nops()` emptied the target, that writes the stale
// backing slot rather than an active instruction.
assert_eq!(blocks[1].instructions[0].instruction_lineno(), 10);
}
#[test]
fn basicblock_has_no_lineno_treats_next_location_like_cpython() {
let mut block = Block::default();
test_block_push(&mut block, test_instr(Instruction::Nop, 10));
block.instructions[0].lineno_override = Some(NEXT_LOCATION_OVERRIDE);
// CPython `basicblock_has_no_lineno()` treats every negative lineno as
// no line number, including `NEXT_LOCATION` (`lineno == -2`).
assert!(block.basicblock_has_no_lineno());
test_block_push(&mut block, test_instr(Instruction::PopTop, 11));
assert!(!block.basicblock_has_no_lineno());
}
#[test]
fn jump_threading_rechecks_new_jump_like_cpython() {
let mut blocks = Blocks::from([
Block::default(),
Block::default(),
Block::default(),
Block::default(),
]);
for (i, block) in blocks.iter_mut().enumerate() {
block.cpython_label = InstructionSequenceLabel::from_index(i as i32);
}
blocks[0].next = BlockIdx::new(1);
blocks[1].next = BlockIdx::new(2);
blocks[2].next = BlockIdx::new(3);
test_block_push(&mut blocks[0], test_jump(BlockIdx::new(1), 10));
test_block_push(&mut blocks[1], test_jump(BlockIdx::new(2), 20));
test_block_push(&mut blocks[2], test_jump(BlockIdx::new(3), 30));
test_block_push(&mut blocks[3], test_instr(Instruction::ReturnValue, 40));
let mut metadata = test_code_info(Block::default()).metadata;
blocks
.optimize_basic_block(&mut metadata, BlockIdx::new(0))
.expect("valid jump chain");
// CPython `optimize_basic_block()` continues after `jump_thread()`, so
// the appended jump is immediately checked against the next jump target.
let threaded = blocks[0].basicblock_last_instr().expect("threaded jump");
assert!(matches!(
threaded.instr.pseudo(),
Some(PseudoInstruction::Jump { .. })
));
assert_eq!(threaded.target, BlockIdx::new(3));
assert_eq!(u32::from(threaded.arg), 3);
}
#[test]
fn same_direction_pseudo_conditional_jump_thread_false_keeps_target() {
let mut blocks = Blocks::from([Block::default(), Block::default(), Block::default()]);
for (i, block) in blocks.iter_mut().enumerate() {
block.cpython_label = InstructionSequenceLabel::from_index(i as i32);
}
blocks[0].next = BlockIdx::new(1);
blocks[1].next = BlockIdx::new(2);
test_block_push(&mut blocks[0], test_cond_jump(BlockIdx::new(1), 10));
test_block_push(&mut blocks[1], test_cond_jump(BlockIdx::new(1), 20));
test_block_push(&mut blocks[2], test_instr(Instruction::ReturnValue, 30));
let mut metadata = test_code_info(Block::default()).metadata;
blocks
.optimize_basic_block(&mut metadata, BlockIdx::new(0))
.expect("valid conditional jump chain");
// Only rewrite JUMP_IF_FALSE -> JUMP_IF_TRUE through
// target->b_next. For same-direction jumps, a failed jump_thread()
// leaves the original target unchanged.
assert_eq!(blocks[0].instructions[0].target, BlockIdx::new(1));
assert!(matches!(
blocks[0].instructions[0].instr.pseudo(),
Some(PseudoInstruction::JumpIfFalse { .. })
));
}
#[test]
fn opposite_direction_pseudo_conditional_uses_target_fallthrough() {
let mut blocks = Blocks::from([Block::default(), Block::default(), Block::default()]);
for (i, block) in blocks.iter_mut().enumerate() {
block.cpython_label = InstructionSequenceLabel::from_index(i as i32);
}
blocks[0].next = BlockIdx::new(1);
blocks[1].next = BlockIdx::new(2);
test_block_push(&mut blocks[0], test_cond_jump(BlockIdx::new(1), 10));
test_block_push(&mut blocks[1], test_true_cond_jump(BlockIdx::new(2), 20));
test_block_push(&mut blocks[2], test_instr(Instruction::ReturnValue, 30));
let mut metadata = test_code_info(Block::default()).metadata;
blocks
.optimize_basic_block(&mut metadata, BlockIdx::new(0))
.expect("valid conditional jump chain");
assert_eq!(blocks[0].instructions[0].target, BlockIdx::new(2));
}
}