Program Optimization

ProgramOptimization is a kind of ProgramTransformation aimed at improving the time or memory performance of a program. CompilationByTransformation makes heavy use of optimizations implemented as small transformations.

Here is a list of common optimizations. Feel free to add missing ones.

(a) Static optimizations (appropriate to a StaticTranslator)

• CodeCompaction
• CodeGeneration
• CodeMotion^?
• CommonSubexpressionElimination^?
• ConstantFolding^?
• ConstantPropagation^?

• DataCaching^?
• DeadCodeElimination^?
• DeForestation

• FiniteDifferencing^?
• FunctionInlining^?

• InductionVariableAnalysis^?
• InductionVariableElimination^?
• InstructionScheduling^?
• InstructionSelection

• LoopOptimization
  • LoopFusion^?
  • LoopUnrolling^?

• PartialEvaluation (also called ProgramSpecialization)
• ProcedureSplitting

• RecursionRemoval^?
• RegisterAllocation^?

• StrengthReduction^?

• SuperCompilation

• TailCallElimination
• TailRecursionElimination

(b) Dynamic optimizations (appropriate to a DynamicTranslator)

• BasicBlockPositioning
• ProcedurePositioning
• ProgramSpecialization

---

See also the MLRISC project at http://cs1.cs.nyu.edu/leunga/www/MLRISC/Doc/html/, which provides a customizable optimizing back-end written in StandardML^? -- ArieVanDeursen.

---

CategoryTransformation, CategoryOptimization | Contributions by EelcoVisser