automatic generation of peephole superoptimizers

notes.md

Overview

(Paper:Bansal S, Aiken A, Automatic generation of peephole superoptimizers)

Superoptimization

This is the GRAIL. Infinity. The platonic ideal of optimization. Eu-optimization. One true optimization.

What we usually call optimization is nothing but improvement. Superoptimization is the real deal.

It's finding the one true optimal canonical fastest sequence of instructions to accomplish a task.

How could you tell if two instruction sequences are the same?

Q: How could you tell if two code sequences produce the same result? I see the phrase "Boolean tests"?

A: the entire state of the machine is represented as bits. Everything. Stack, memory, registers, stack counters, program counter, everything.

Overview

Paper: 1996 Lipasti S, Wilkinson C, Shen J, Value locality and Load Value Prediction)

Caching Concepts

• Associativity

  N-way associative: each memory piece can only have N places to go in cache fully associative: each memory piece can be anywhere in the cache Tradeoff: more assocative = more search time looking for data, but also less likely to miss.

• Victim Cache

  Extra, slightly slower cache to store most recently evicted item.

Memory Pages