Compilers

What does liveness analysis, done in preparation for register allocation, determine?

  1. AThe line number where each variable is declared in the program
  2. BThe maximum and minimum values of each variable
  3. CAt each point, whether a value may still be used later
Show answer and explanation

Answer: C. At each point, whether a value may still be used later

Liveness analysis traverses the control-flow graph to determine, at each point in the program, whether a value may be read later (whether it is live). Live values must be kept in registers, while registers holding dead values can be reused. Values live at the same time cannot share a register, so the interference graph is built from this result. It does not find declaration positions or value ranges.

  • A. It examines possible future use, not declaration position.
  • B. It is distinct from value-range analysis.
  • C. Correct. It determines at each point whether a value is still needed.
Practice this topic Back to topic

More Compilers questions

  1. 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?
  2. 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.)
  3. What is the usual sequence for producing an executable from a C program?
  4. 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?
  5. In the code above, which optimization applies after inlining sq, and with what result?