Instruction selection in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the primary goal of instruction selection in a compiler?

Instruction selection is a key phase in compiler design. What is its main purpose?

A To translate intermediate code into machine instructions that efficiently use the target CPU's capabilities

B To optimize the source code by removing redundant variables

C To allocate registers for variables during program execution

D To parse the source code and build an abstract syntax tree

💡 Hint

Think about how the compiler converts a general representation into something the CPU understands.

Instruction selection chooses machine instructions that implement the operations in the intermediate code, aiming for efficient use of the CPU.

📋 Factual

intermediate

Which technique is commonly used for instruction selection?

Among the following, which technique is widely used for instruction selection in modern compilers?

A Garbage collection

B Lexical analysis

C Tree pattern matching

D Syntax-directed translation

💡 Hint

It involves matching parts of the intermediate code tree to machine instructions.

Tree pattern matching is used to map parts of the intermediate representation to machine instructions efficiently.

🔍 Analysis

advanced

What is the output of this instruction selection scenario?

Given an intermediate representation of an addition operation, which machine instruction sequence is the best selection?

Compiler Design

Intermediate code: t1 = a + b
Target CPU supports: ADD R1, R2, R3 (R1 = R2 + R3), MOV R1, a, MOV R2, b

A MOV R1, a; MOV R2, b; ADD R3, R1, R2

B MOV R2, a; MOV R3, b; ADD R1, R2, R3

C ADD R1, a, b

D MOV R1, a; MOV R2, b; ADD R1, R1, R2

💡 Hint

Consider which registers hold the operands and where the result should be stored.

Option D correctly moves operands into registers R1 and R2, then adds them storing the result back in R1, matching the intermediate code.

❓ Comparison

advanced

Compare bottom-up and top-down instruction selection approaches

Which statement correctly contrasts bottom-up and top-down instruction selection methods?

A Top-down always produces more efficient code than bottom-up

B Bottom-up starts from leaves of the intermediate tree and builds up, while top-down starts from the root and breaks down

C Bottom-up requires manual coding of instructions, top-down is fully automatic

D Top-down uses register allocation first, bottom-up does not

💡 Hint

Think about the direction in which the intermediate representation is processed.

Bottom-up instruction selection processes from leaves to root, matching patterns upwards; top-down starts at the root and recursively selects instructions downwards.

❓ Reasoning

expert

Why might instruction selection impact overall program performance?

Consider how instruction selection affects the final machine code. Why does this phase influence the program's speed and size?

A Because selecting fewer or simpler instructions can reduce execution time and memory usage

B Because instruction selection changes the source code logic

C Because it determines the syntax errors in the program

D Because it manages user input and output operations

💡 Hint

Think about how machine instructions relate to CPU cycles and memory.

Efficient instruction selection chooses instructions that execute faster and use less memory, improving program performance.