线性扫描算法

int example() {
	int a = 1;
	int b = 2;
	int c = a + b;
	int d = 4;
	int e = 5;
	return c + (d + e);
}

example:
	addi sp, sp, -16 # 分配栈空间
	sw 	ra, 0(sp) # 保存返回地址 (RV32)
	sw 	s0, 4(sp) # 保存栈帧指针 (RV32)
	addi s0, sp, 16 # 设置栈帧指针

	li 	a0, 1 # 加载a到寄存器a0
	li 	t0, 2 # 加载b到寄存器t0
	add a0, a0, t0 # 计算c
	li 	t0, 4 # 加载d到寄存器t0
	sw 	a0, -4(s0) # 将c存入内存
	li 	a0, 5 # 加载e到寄存器a0
	add a0, a0, t0 # 计算d+e
	lw 	t0, -4(s0) # 将c从内存中加载到寄存器t0
	add a0, a0, t0 # 计算c+(d+e)

	ret

use std::collections::{HashMap, HashSet, BTreeMap};

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Variable(usize);

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Register(usize);

#[derive(Debug)]
struct LiveInterval {
	var: Variable,
	start: usize,
	end: usize
}

struct LinearScanAllocator {
	free_registers: Vec<Register>,
	active_list: BTreeMap<usize, (Variable, Register)>,
	allocations: HashMap<Variable, Register>,
	spilled: HashSet<Variable>
}

impl LinearScanAllocator {
	fn new(num_regs: usize) -> Self {
		let free_registers = (0..num_regs).map(Register).collect();
		Self {
			free_registers,
			active_list: BTreeMap::new(),
			allocations: HashMap::new(),
			spilled: HashSet::new()
		}
	}

	fn expire_old_intervals(&mut self, curr_point: usize) {
		let expired_ends: Vec<usize> = self
			.active_list.keys()
			.filter(|&&end| end <= curr_point)
			.cloned()
			.collect();

		for end in expired_ends {
			if let Some((_, reg)) = self.active_list.remove(&end) {
				self.free_registers.push(reg);
			}
		}
	}

	fn handle_spill(&mut self, interval: LiveInterval) {
		if let Some(&max_end, &(var, reg)) = self.active_list.iter().next_back() {
			if interval.end > max_end {
				self.spilled.insert(interval.var);
			} else {
				self.active_list.remove(&max_end);
				self.active_list.insert(interval.end, (interval.var, reg));
				self.spilled.insert(var);
				self.allocations.insert(interval.var, reg);
			}
		}
	}

	fn allocate(&mut self, intervals: Vec<LiveInterval>) {
		let mut sorted_intervals = intervals.clone();
		sorted_intervals.sort_by_key(|interval| interval.start);

		for interval in sorted_intervals {
			self.expire_old_intervals(interval.start);

			if self.free_registers.is_empty() {
				self.handle_spill(interval);
			} else {
				let reg = self.free_registers.pop().unwrap();
				self.allocations.insert(interval.var, reg);
				self.active_list.insert(interval.end, (interval.var, reg));
			}
		}
	}

	fn get_allocations(&self) -> &HashMap<Variable, Register> {
		&self.allocations
	}

	fn get_spilled(&self) -> &HashSet<Variable> {
		&self.spilled
	}
}

fn main() {
	let intervals = vec![
		LiveInterval { var: Variable(0), start: 1, end: 4 },
		LiveInterval { var: Variable(1), start: 2, end: 5 },
		LiveInterval { var: Variable(2), start: 3, end: 8 },
		LiveInterval { var: Variable(3), start: 4, end: 6 },
		LiveInterval { var: Variable(4), start: 5, end: 7 },
	];

	let mut allocator = LinearScanAllocator::new(2);
	allocator.allocate(intervals);

	for (var, reg) in allocator.get_allocations() {
		println!("Variable {:?} allocated to Register {:?}", var, reg);
	}
	for var in allocator.get_spilled() {
		println!("Variable {:?} spilled to memory", var);
	}
}