Instruction selection in Compiler Design - Mini Project: Build & Apply

Understanding Instruction Selection in Compiler Design

📖 Scenario: You are learning how compilers translate high-level code into machine instructions. Instruction selection is a key step where the compiler chooses the best machine instructions to perform operations.Imagine you are designing a simple compiler that converts arithmetic expressions into assembly instructions for a basic processor.

🎯 Goal: Build a step-by-step understanding of instruction selection by creating a mapping from arithmetic operations to machine instructions, setting up a selection rule, applying it to an expression, and finalizing the instruction sequence.

📋 What You'll Learn

Create a dictionary mapping arithmetic operators to machine instructions

Define a variable for the target operation to select instructions for

Use the mapping to select the correct machine instruction for the operation

Complete the instruction sequence by adding a final instruction

💡 Why This Matters

🌍 Real World

Instruction selection is a fundamental step in compilers that translates human-readable code into machine instructions that a processor can execute.

💼 Career

Understanding instruction selection helps software developers and compiler engineers optimize code generation and improve program efficiency.

1

Create the instruction mapping dictionary

Create a dictionary called instruction_map with these exact entries: '+' maps to 'ADD', '-' maps to 'SUB', '*' maps to 'MUL', and '/' maps to 'DIV'.

Compiler Design

# Create the instruction_map dictionary with operator to instruction mappings
# Your code here

Need a hint?

Use curly braces to create a dictionary with keys as operators and values as instruction names.

2

Set the target operation for instruction selection

Create a variable called target_op and set it to the string '*' to represent the multiplication operation.

Compiler Design

instruction_map = {'+': 'ADD', '-': 'SUB', '*': 'MUL', '/': 'DIV'}
# Set the target_op variable to '*' to select multiplication instruction
# Your code here

Need a hint?

Assign the string '*' to the variable target_op.

3

Select the machine instruction for the target operation

Create a variable called selected_instruction and set it to the value from instruction_map using the key target_op.

Compiler Design

instruction_map = {'+': 'ADD', '-': 'SUB', '*': 'MUL', '/': 'DIV'}
target_op = '*'
# Use instruction_map and target_op to get selected_instruction
# Your code here

Need a hint?

Use the dictionary lookup syntax with instruction_map[target_op] to get the instruction.

4

Complete the instruction sequence

Create a list called instruction_sequence containing the selected_instruction followed by the string 'STORE' to represent storing the result.

Compiler Design

instruction_map = {'+': 'ADD', '-': 'SUB', '*': 'MUL', '/': 'DIV'}
target_op = '*'
selected_instruction = instruction_map[target_op]
# Create instruction_sequence list with selected_instruction and 'STORE'
# Your code here

Need a hint?

Create a list with two elements: the selected instruction and the string 'STORE'.