Compilers

In a function, at most five values are live at the same time. In a simple case where the interference graph imposes no further constraints, how many registers are needed at minimum to hold every value without spilling?

  1. A5
  2. B4
  3. C10
Show answer and explanation

Answer: A. 5

The five simultaneously live values all interfere with one another, forming a complete subgraph of five nodes in the interference graph, so at least five colors are needed. In simple cases such as straight-line code, where live ranges are intervals, the graph can be colored with as many colors as the maximum number of simultaneously live values, so five registers suffice. With four, some value must be spilled to memory somewhere. Ten is more than necessary.

  • A. Correct. Five, the maximum live at once, are needed and suffice here.
  • B. With four, a spill is needed somewhere.
  • C. Ten is more than necessary.
Practice this topic Back to topic

More Compilers questions

  1. If a loop with 100 iterations is unrolled by replicating its body four times, how many counter checks and branches remain? (Assume 100 is divisible by 4.)
  2. What is the usual sequence for producing an executable from a C program?
  3. What is the optimization called that examines short sequences of generated machine code through a small window and replaces wasteful instruction combinations with better ones?
  4. In the code above, which optimization applies after inlining sq, and with what result?
  5. Which describes software pipelining?