Instruction selection in Compiler Design - Step-by-Step Execution

Concept Flow - Instruction selection

Start: Intermediate Code

↓

Analyze Operations

↓

Match Patterns to Machine Instructions

↓

Select Best Instructions

↓

Generate Machine Code

↓

End

Instruction selection converts intermediate code into machine instructions by matching code patterns and choosing the best instructions step-by-step.

Execution Sample

Compiler Design

Intermediate code: a = b + c
Match pattern: ADD instruction
Select instruction: ADD R1, R2, R3
Generate machine code: ADD R1, R2, R3

This example shows how a simple addition in intermediate code is matched to an ADD machine instruction and then generated.

Analysis Table

Step	Action	Input	Pattern Matched	Instruction Selected	Output
1	Receive intermediate code	a = b + c	None	None	Intermediate code ready
2	Analyze operation	a = b + c	Addition operation	None	Operation identified as addition
3	Match pattern	Addition operation	ADD instruction pattern	ADD	Pattern matched to ADD
4	Select instruction	ADD pattern	ADD instruction pattern	ADD R1, R2, R3	Instruction selected
5	Generate machine code	ADD R1, R2, R3	ADD instruction pattern	ADD R1, R2, R3	Machine code generated
6	End	Machine code generated	None	None	Instruction selection complete

💡 All intermediate operations matched and converted to machine instructions

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
Intermediate Code	a = b + c	a = b + c	a = b + c	a = b + c	a = b + c
Operation Type	None	Addition	Addition	Addition	Addition
Matched Pattern	None	None	ADD instruction pattern	ADD instruction pattern	ADD instruction pattern
Selected Instruction	None	None	None	ADD R1, R2, R3	ADD R1, R2, R3
Machine Code	None	None	None	None	ADD R1, R2, R3

Key Insights - 3 Insights

Why do we need to match patterns before selecting instructions?

Matching patterns identifies which machine instructions can perform the intermediate operations, as shown in step 3 of the execution table.

What happens if no pattern matches the intermediate code?

Instruction selection cannot proceed, and the compiler may report an error or use fallback instructions; this is why step 3 is crucial.

Is the selected instruction always the first matched pattern?

No, the compiler selects the best instruction based on cost or efficiency, as shown in step 4 where selection happens after matching.

Visual Quiz - 3 Questions

Look at the execution table, what is the matched pattern at step 3?

A ADD instruction pattern

B SUB instruction pattern

C MUL instruction pattern

D No pattern matched

💡 Hint

Check the 'Pattern Matched' column at step 3 in the execution table.

At which step is the machine code generated?

A Step 4

B Step 5

C Step 2

D Step 6

💡 Hint

Look at the 'Output' column for when machine code appears in the execution table.

If the intermediate code was 'a = b - c', how would the 'Matched Pattern' change at step 3?

A It would match ADD instruction pattern

B No pattern would match

C It would match SUB instruction pattern

D It would match MUL instruction pattern

💡 Hint

Think about how the operation type affects pattern matching in the execution table.

Concept Snapshot

Instruction selection converts intermediate code into machine instructions.
It analyzes operations, matches code patterns to instructions,
selects the best instructions, and generates machine code.
This step is key in turning compiler output into executable code.

Full Transcript

Instruction selection is a compiler step that takes intermediate code and turns it into machine instructions. The process starts by analyzing the operations in the intermediate code. Then, it matches these operations to known machine instruction patterns. After matching, the compiler selects the best instructions based on criteria like efficiency. Finally, it generates the machine code that the processor can execute. For example, an addition operation in intermediate code is matched to an ADD instruction and then converted into machine code. This process ensures that high-level code is correctly and efficiently translated into instructions the computer understands.

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