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.

Practice

1. What is the main purpose of instruction selection in a compiler?

easy

A. To convert intermediate code into machine-specific instructions

B. To check the syntax of the source code

C. To optimize memory usage during runtime

D. To link different program modules together

Solution

1. Step 1: Understand the role of instruction selection

   Instruction selection is the process where the compiler converts intermediate code into instructions that a specific machine can execute.

2. Step 2: Differentiate from other compiler phases

   Syntax checking is done earlier, optimization and linking are separate steps, so they are not the main purpose here.

3. Final Answer:

   To convert intermediate code into machine-specific instructions -> Option A

4. Quick Check:

   Instruction selection = convert code to machine instructions [OK]

Hint: Instruction selection = intermediate code to machine code [OK]

Common Mistakes:

• Confusing instruction selection with syntax checking
• Thinking it optimizes memory directly
• Mixing it up with linking process

2. Which of the following is a correct statement about instruction selection syntax in compiler design?

easy

A. Instruction selection ignores the target machine architecture

B. Instruction selection always uses high-level language syntax

C. Instruction selection is performed before lexical analysis

D. Instruction selection maps intermediate code patterns to machine instructions

Solution

1. Step 1: Identify the role of instruction selection syntax

   Instruction selection involves matching patterns in intermediate code to machine instructions, so it maps patterns to instructions.

2. Step 2: Eliminate incorrect options

   It does not use high-level syntax, happens after lexical analysis, and must consider target machine architecture.

3. Final Answer:

   Instruction selection maps intermediate code patterns to machine instructions -> Option D

4. Quick Check:

   Instruction selection = pattern matching to machine code [OK]

Hint: Instruction selection matches code patterns to machine instructions [OK]

Common Mistakes:

• Assuming instruction selection uses high-level language syntax
• Thinking it happens before lexical analysis
• Ignoring machine architecture in selection

3. Given the intermediate code: ADD R1, R2, R3, which machine instruction would instruction selection most likely choose for a processor that supports ADD with two registers and a destination register?

medium

A. LOAD R1, R2; ADD R1, R1, R3

B. ADD R1, R2

C. ADD R1, R2, R3

D. STORE R3, R1

Solution

1. Step 1: Understand the intermediate code format

   The code ADD R1, R2, R3 means add contents of R2 and R3, store in R1.

2. Step 2: Match to machine instruction format

   The processor supports ADD with two source registers and one destination register, so the same instruction fits.

3. Final Answer:

   ADD R1, R2, R3 -> Option C

4. Quick Check:

   Instruction matches intermediate code format [OK]

Hint: Match intermediate code format to machine instruction format [OK]

Common Mistakes:

• Choosing instructions that split operations unnecessarily
• Selecting instructions with wrong operands count
• Confusing LOAD/STORE with ADD

4. Identify the error in this instruction selection rule: if (node.op == 'ADD') then emit('LOAD ' + node.left) + emit('ADD ' + node.right)

medium

A. It ignores the target machine's register allocation

B. It emits two separate instructions instead of one combined ADD

C. It uses incorrect syntax for the emit function

D. It should check for 'SUB' instead of 'ADD'

Solution

1. Step 1: Analyze the rule's emitted instructions

   The rule emits a LOAD for the left operand and then an ADD for the right operand separately.

2. Step 2: Understand instruction selection goal

   Instruction selection should emit a single combined ADD instruction if the machine supports it, not split into LOAD and ADD unnecessarily.

3. Final Answer:

   It emits two separate instructions instead of one combined ADD -> Option B

4. Quick Check:

   Instruction selection should combine operations when possible [OK]

Hint: Look for unnecessary instruction splitting in rules [OK]

Common Mistakes:

• Not combining instructions when machine supports it
• Misusing emit syntax
• Ignoring register allocation issues

5. How can instruction selection be optimized to improve performance on a processor with complex instructions that combine multiple operations?

hard

A. By using pattern matching to select complex instructions that cover multiple intermediate operations

B. By always breaking down complex operations into simple instructions

C. By ignoring the processor's instruction set and using generic instructions

D. By delaying instruction selection until after program execution

Solution

1. Step 1: Understand processor complex instructions

   Some processors have instructions that perform multiple operations at once, which can speed up execution.

2. Step 2: Apply pattern matching for optimization

   Instruction selection can use pattern matching to detect sequences of intermediate code that map to these complex instructions, improving performance.

3. Final Answer:

   By using pattern matching to select complex instructions that cover multiple intermediate operations -> Option A

4. Quick Check:

   Use pattern matching for complex instruction selection [OK]

Hint: Select complex instructions via pattern matching for speed [OK]

Common Mistakes:

• Breaking complex operations unnecessarily
• Ignoring processor instruction set
• Delaying instruction selection beyond compile time