Более приятный способ сопоставления с образцом окна инструкций по сборке глазка с ржавчиной?
Итак, я пытаюсь реализовать оптимизацию глазка, где я иду отVec<LLStackInstruction> -> Vec<LLStackInstruction>, где возвращаемый список оптимизирован. (LLдля низкого уровня) Наш компилятор смоделирован как абстрактная стековая машина, и для инициализации/назначения мы помещаем RHS в стек, помещаем адрес LHS в стек, а затем извлекаем и STR, но пытаемся свести это к отправке RHS и затем сохраняем по адресу прямо через спецификатор адреса, но я получаю очень уродливое совпадение, например: (и с изменчивостью)
pub fn peephole_optimiser(instrs: Vec<LLStackInstruction>) -> Vec<LLStackInstruction> {
let mut optimized_instructions: Vec<LLStackInstruction> = Vec::new();
let mut iter = instrs.iter().peekable();
while let Some(instruction) = iter.next() {
let window_iter = iter.clone();
let window: Vec<_> = [vec![instruction], window_iter.take(10).collect()].concat();
if let Some(LLStackInstruction::Push(Register::FP)) = window.get(0) {
if let Some(LLStackInstruction::Mov(Condition::None, r1, ArgType::Imm(n))) = window.get(1) {
if let Some(LLStackInstruction::Push(r2)) = window.get(2) {
if let Some(LLStackInstruction::Pop(_)) = window.get(3) {
if let Some(LLStackInstruction::Pop(_)) = window.get(4) {
if let Some(LLStackInstruction::Sub(..)) = window.get(5) {
if let Some(LLStackInstruction::Branch(..)) = window.get(6) {
if let Some(LLStackInstruction::Push(_)) = window.get(7) {
if let Some(LLStackInstruction::Pop(_)) = window.get(8) {
if let Some(LLStackInstruction::Pop(_)) = window.get(9) {
if let Some(LLStackInstruction::Str(..)) = window.get(10) {
if r1 == r2 {
optimized_instructions.push(LLStackInstruction::Pop(Register::R4));
optimized_instructions.push(LLStackInstruction::Str(Register::R4, AddressSpecifier::ImmediateOffset(Register::FP, -n)));
iter.nth(9);
continue;
}
}
}
}
}
}
}
}
}
}
}
}
optimized_instructions.push(instruction.clone());
}
optimized_instructions
}
Как я могу сделать это лучше?
Пример того, что делает эта оптимизация
// Compact init/assign statements
// push {fp}
// mov r1, #88
// push {r1}
// pop {r0}
// pop {r1}
// subs r0, r1, r0
// bvs _overflow_err
// push {r0}
// pop {r3}
// pop {r4}
// str r4, [r3]
// INTO
// pop {r4}
// str r4, [fp, #-88]
Единственное, о чем я мог подумать, это то, что я мог бы выразить это в несколько шагов меньших окон и выполнить несколько проходов оптимизации (или после оптимизации окна перезапустить результат с его начала до тех пор, пока он не изменится).
3 ответа
Вы можете сопоставить свое окно напрямую, а не вложенноеif letзаявления. Rust поддерживает деструктуризацию срезов по шаблону:
match window[..11] {
[
LLStackInstruction::Push(Register::FP),
LLStackInstruction::Push(r2),
LLStackInstruction::Pop(_),
LLStackInstruction::Pop(_),
LLStackInstruction::Sub(..),
LLStackInstruction::Branch(..),
LLStackInstruction::Push(_),
LLStackInstruction::Pop(_),
LLStackInstruction::Pop(_),
LLStackInstruction::Str(..)
] if r1 == r2 => {
optimized_instructions.push(LLStackInstruction::Pop(Register::R4));
optimized_instructions.push(LLStackInstruction::Str(
Register::R4,
AddressSpecifier::ImmediateOffset(Register::FP, -n),
));
iter.nth(9);
continue;
}
_ => {}
}
Как упоминал Джонас, вы можете использовать сопоставление шаблонов срезов для большей эргономики, а ночью вы можете комбинировать его с цепочками let, чтобы избежать вложенных if.
Тогда трудность заключается в том, как совместить работу с окнами с пропуском произвольного количества инструкций в случае успеха.
Простое решение — использовать индексацию вручную:
pub fn peephole_optimiser(instrs: &[LLStackInstruction]) -> Vec<LLStackInstruction> {
const WINDOW_SIZE: usize = 11;
type Instr = LLStackInstruction;
if instrs.len() < WINDOW_SIZE{
optimized.extend_from_slice(instrs);
return optimized;
}
let mut optimized = Vec::new();
let mut index = 0;
while index < instrs.len() - WINDOW_SIZE {
if let [
Instr::Push(Register::FP),
Instr::Mov(Condition::None, r1, ArgType::Imm(_)),
Instr::Push(r2),
Instr::Pop(_),
Instr::Pop(_),
Instr::Sub(..),
Instr::Branch(..),
Instr::Push(..),
Instr::Pop(..),
Instr::Pop(..),
Instr::Str(..)
] = &instrs[index..][..WINDOW_SIZE]
{
if r1 == r2 {
optimized.push(LLStackInstruction::Pop(Register::R4));
optimized.push(LLStackInstruction::Str(<>));
index += WINDOW_SIZE;
continue;
}
}
optimized.push(window[0].clone());
index += 1;
}
optimized
}
но это немного сложнее понять цель, и вы рискуете забыть увеличить индекс перед повторным запуском цикла... что приведет к бесконечному циклу.
sliceимеетwindowsфункции для перебора окон, вforцикл, хотя для этого требуется пропуск вручную:
pub fn peephole_optimiser(instrs: &[LLStackInstruction]) -> Vec<LLStackInstruction> {
const WINDOW_SIZE: usize = 11;
type Instr = LLStackInstruction;
let mut optimized = Vec::new();
if instrs.len() < WINDOW_SIZE {
optimized.extend_from_slice(instrs);
return optimized;
}
let mut skip = 0;
for window in instrs.windows(WINDOW_SIZE) {
if skip > 0 {
skip -= 1;
continue;
}
if let [
Instr::Push(Register::FP),
Instr::Mov(Condition::None, r1, ArgType::Imm(_)),
Instr::Push(r2),
Instr::Pop(_),
Instr::Pop(_),
Instr::Sub(..),
Instr::Branch(..),
Instr::Push(..),
Instr::Pop(..),
Instr::Pop(..),
Instr::Str(..)
] = window
{
if r1 == r2 {
optimized.push(Instr::Pop(Register::R4));
optimized.push(Instr::Str(<>));
skip = 9;
continue;
}
}
optimized.push(window[0].clone());
}
optimized
}
Однако дополнительная переменная не очень хороша.
В конце концов, возможно, комбинацияslice::windowsс несколько более ручным режимом итерации — лучшее, чего мы можем достичь:
- Одна итерационная переменная, а не две разные.
- Без возможности случайно попасть в бесконечный цикл.
Я думаю, что это довольно читабельно, особенно если выделить совпадение в отдельную функцию:
pub fn peephole_optimiser(instrs: &[LLStackInstruction]) -> Vec<LLStackInstruction> {
const WINDOW_SIZE: usize = 11;
type Instr = LLStackInstruction;
fn matches(window: &[Instr]) -> bool {
assert_eq!(WINDOW_SIZE, window.len());
if let [
Instr::Push(Register::FP),
Instr::Mov(Condition::None, r1, ArgType::Imm(_)),
Instr::Push(r2),
Instr::Pop(_),
Instr::Pop(_),
Instr::Sub(..),
Instr::Branch(..),
Instr::Push(..),
Instr::Pop(..),
Instr::Str(..)
] = window
{
r1 == r2
} else {
false
}
}
let mut optimized = Vec::new();
let mut windows = instrs.windows(WINDOW_SIZE);
while let Some(window) = windows.next() {
if matches(window) {
optimized.push(Instr::Pop(Register::R4));
optimized.push(Instr::Str(<>);
windows.nth(WINDOW_SIZE - 2);
continue;
}
optimized.push(window[0].clone());
}
optimized
}
В ночное время есть функция цепочек if-let :
#![feature(let_chains)]
if let a = b && let c = d && e == f { ... }
В стабильной версии вы можете использоватьif_chainящик:
if_chain::if_chain! {
if let a = b;
if let c = d;
if e == f;
then { ... }
}