GLOSSARY

Basic blocks A portion of the code within a program with certain desirable properties that make it highly amenable to analysis. Basic blocks form the vertices or nodes in a control flow-graph.

Combinatorial Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Combinatorial problems arise in many areas including computer science.

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control flow-graph (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by compilers when optimizing a program.

Dead variable is one that does not carry any information used subsequently.

Degenerate Reach lower order or trivial state.

Flow-graph is a representation, using graph notation, of all paths that might be traversed through a program during its execution.

Hash-coded Some data encoded by a hashing function.

Heuristics A common-sense rule or set of rules intended to increase the probability of solving some problem.

Loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program.

NP-complete The most notable characteristic of NP-complete problems is that no fast solution to them is known. The time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows.

Subsumed Contain or include; consider an instance of something as part of a general rule or principle.

Super-optimizer finds the optimal code sequence for a single, loop-free sequence of instructions. While usual optimizers just improve code a super-optimizer tries to find the optimal sequence.

Tree-pruning refers to removal of large chunks of a tree using certain strategies which decide which portions are not at all useful.