Compilers

Learn how compilers work with multiple-choice questions: lexing and parsing, SSA-form intermediate representations, optimizations such as constant folding and loop unrolling, and register allocation.

—Your accuracy
0 / 50Questions answered
Practice this topicAll questions in this topic, in random order Weak questionsRetry only the questions you last got wrong

Compilers: key points

A compiler translates programs written by people into machine code a CPU can execute. It passes through lexical analysis, which splits source code into tokens; parsing, which builds a tree according to the grammar; and semantic analysis, which checks types and names, before converting the program to an intermediate representation (IR).

On the IR it applies optimizations such as constant folding, common subexpression elimination, inlining, loop unrolling and vectorization, then generates code suited to the CPU through register allocation and instruction scheduling. Understanding these optimizations shows how to write fast code and how to get the most out of the hardware.

All Compilers questions (50)

  1. What is the role of lexical analysis in a compiler?
  2. What is done during syntax analysis (parsing) in a compiler?
  3. Which is the best example of an error found during semantic analysis?
  4. Which describes an abstract syntax tree (AST)?
  5. What is the main advantage of using an intermediate representation (IR), independent of both source language and CPU, inside a compiler?
  6. Which describes a basic block?
  7. In a control-flow graph, what do the nodes and edges represent?
  8. Which is a characteristic of an IR in SSA form?
  9. Converting the code above to SSA form inserts an expression like "x3 = φ(x1, x2)" after the if statement. What does the φ function do?
  10. Which is an example of constant folding by a compiler?
  11. After repeatedly applying constant propagation and constant folding to the code above, what does it finally become?
  12. Which describes applying common subexpression elimination to the code above?
  13. What does dead-code elimination remove?
  14. Which pair gives the advantage and drawback of function inlining?
  15. What is the main effect of loop unrolling?
  16. In the loop above, which computation is a candidate for loop-invariant code motion (hoisting out of the loop)? (Assume x and y are not modified in the loop.)
  17. In the loop above, which transformation applies strength reduction to the index computation i * 4?
  18. Why is the loop above hard to vectorize with SIMD instructions?
  19. In the function above, why can the compiler not simply hoist the load of *b out of the loop?
  20. In register allocation by coloring an interference graph, what do the nodes and edges represent?
  21. What happens to generated code when register allocation causes a "spill"?
  22. What is the main purpose of instruction scheduling in a compiler?
  23. What is the effect of applying tail-call optimization to the final recursive call in the function above?
  24. Which correctly distinguishes a compiler from an interpreter?
  25. Which describes a runtime that uses JIT compilation?
  26. Which describes the basic structure of LLVM?
  27. When is the no-optimization setting of a compiler (such as -O0) commonly used?
  28. Which describes profile-guided optimization (PGO)?
  29. Which optimization does link-time optimization (LTO) make possible?
  30. In C, signed integer overflow is undefined behavior. Under this rule, which code might an optimizing compiler generate for the function above?
  31. Which program error can be detected at compile time?
  32. What is the main benefit of compile-time type checking in a statically typed language?
  33. What is commonly used to express the rules for recognizing tokens in lexical analysis?
  34. Which kind of grammar is used to describe most programming languages and underlies parsing?
  35. What does the abstract syntax tree for the expression 2 + 3 * 4 look like?
  36. Which describes three-address code, a kind of intermediate representation?
  37. What does liveness analysis, done in preparation for register allocation, determine?
  38. 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?
  39. 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.)
  40. What is the usual sequence for producing an executable from a C program?
  41. 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?
  42. In the code above, which optimization applies after inlining sq, and with what result?
  43. Which describes software pipelining?
  44. Why does a compiler with strict settings not reorder the floating-point sum (a + b) + c into a + (b + c) on its own?
  45. Which kind of instruction does a compiler's automatic vectorization use?
  46. What basic condition must compiler optimizations respect?
  47. Which describes instruction selection, one stage of code generation?
  48. Which describes a cross compiler?
  49. When debugging a program compiled with optimization, some variables may show as "unavailable." What is the main reason?
  50. After thoroughly applying constant propagation, constant folding and dead-code elimination to the function above, what does it return and what code remains?

Other topics in Computer systems