NOTICE: The Processors Wiki will End-of-Life in December of 2020. It is recommended to download any files or other content you may need that are hosted on processors.wiki.ti.com. The site is now set to read only.

Compiler heuristic

From Texas Instruments Wiki
Jump to: navigation, search

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