During instruction selection, what core challenge does a compiler face when mapping IR to machine instructions?
ADetermining whether the program terminates
BMany IR instruction sequences can be covered by multiple machine instruction patterns with different execution costs
CConverting floating-point values to integer types
DRemoving unused variables from the symbol table
Instruction selection is fundamentally a pattern-matching and covering problem: a sequence of IR instructions can often be covered by different combinations of machine instructions (e.g., one complex instruction vs. several simpler ones), each with different execution costs. Choosing the minimum-cost cover is NP-hard in general, so compilers use dynamic programming, greedy heuristics, or tree pattern matching to approximate the optimum.
Question 2 True / False
Register allocation is expected to happen before instruction selection because the number of available physical registers constrains which machine instructions can be chosen.
TTrue
FFalse
Answer: False
In most compiler architectures, instruction selection precedes register allocation. Instructions are first selected assuming an unlimited supply of virtual (temporary) registers; register allocation then maps virtual registers to physical ones, inserting spill code to memory when physical registers run out. Some compilers interleave the phases, but the standard pipeline — used by LLVM and GCC — selects instructions first, then allocates registers.
Question 3 Short Answer
What is instruction scheduling, and why is it a distinct concern from instruction selection in modern processors?
Think about your answer, then reveal below.
Model answer: Instruction scheduling reorders instructions — without changing program semantics — to avoid pipeline stalls and exploit instruction-level parallelism. It is separate from instruction selection because selection decides *which* instructions to emit, while scheduling decides *in what order* to emit them. Modern processors execute instructions out of order at runtime, but static compiler scheduling reduces hazards (such as memory load latencies) that hardware reordering cannot always resolve.
The separation reflects distinct optimization goals: instruction selection minimizes the number and cost of operations; instruction scheduling minimizes the wall-clock time those operations take by exploiting processor microarchitecture. Both phases require knowledge of the target machine, but they use different algorithms (covering/matching for selection; list scheduling or software pipelining for scheduling) and can be improved independently.