Compiler heuristic

Compilers use many different algorithms to generate assembly code from the source language (C/C++/Java/etc). In many cases, these algorithms are "heuristics".

In computer science, a heuristic is an algorithm that solves a particular problem, but may not give an optimal solution in all cases. In some cases, a heuristic is used because a given problem cannot be solved optimally in every case in a reasonable amount of time (or space). Some problems that a compiler must address belong to a class of problems known as "NP problems", which are computationally difficult to solve. In other cases, a heuristic is used because the compiler does not or cannot have enough information to make the best decision.

Compiler writers attempt to create heuristics that solve the given problems well in most cases, and in a reasonable amount of time or space, and/or with limited information.

Examples

Examples of compiler heuristics include:

• Inlining decisions
• Unrolling decisions
• Packed-data (SIMD) optimization decisions
• Instruction selection
• Register allocation
• Instruction scheduling
• Software pipelining

External Links

• Heuristic algorithm - Wikipedia's discussion of heuristics
• Compiler Optimization - Wikipedia's discussion of compiler optimizations