Basic blocks and flow graphs in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Basic Blocks

Which of the following best describes a basic block in compiler design?

A A group of functions called together in a program

B A set of instructions that can be executed in parallel

C A block of code that contains only conditional branches

D A sequence of instructions with no branches except at the entry and exit points

💡 Hint

Think about a block where control flow enters at the beginning and leaves at the end without interruption.

A basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit.

📋 Factual

intermediate

Flow Graph Components

In a flow graph representing a program's control flow, what do the nodes and edges represent?

A Nodes represent variables; edges represent data dependencies

B Nodes represent basic blocks; edges represent possible control flow between blocks

C Nodes represent instructions; edges represent memory access

D Nodes represent functions; edges represent function calls

💡 Hint

Consider what a flow graph models in terms of program execution paths.

In a flow graph, nodes are basic blocks and edges show possible paths control can take from one block to another.

🔍 Analysis

advanced

Identifying Leaders in Basic Blocks

Given the following sequence of instructions, which instructions are leaders that start a new basic block?

1: a = 5
2: if a > 0 goto 5
3: b = a + 1
4: goto 6
5: b = a - 1
6: print(b)

A Instructions 1, 3, 5, and 6

B Instructions 1, 3, and 5

C Instructions 1, 2, and 6

D Instructions 1, 2, and 5

💡 Hint

Leaders include the first instruction, targets of jumps, and instructions following jumps.

Instruction 1 is the first instruction (always a leader). Instruction 3 immediately follows the conditional jump at instruction 2. Instruction 5 is the target of the jump at instruction 2 and instruction 6 is the target of the jump at instruction 4.

❓ Comparison

advanced

Difference Between Basic Blocks and Flow Graphs

Which statement correctly compares basic blocks and flow graphs?

A Basic blocks represent function calls; flow graphs represent variable dependencies

B Flow graphs are sequences of instructions; basic blocks show possible paths between instructions

C Basic blocks are nodes in a flow graph; flow graphs show control flow between these blocks

D Flow graphs are used only for data flow analysis; basic blocks are used only for syntax checking

💡 Hint

Think about how basic blocks and flow graphs relate to each other structurally.

Basic blocks form the nodes of a flow graph, which illustrates how control moves between these blocks.

❓ Reasoning

expert

Effect of Removing an Edge in a Flow Graph

In a flow graph of a program, what is the most likely effect of removing an edge that represents a conditional jump?

A It may cause some basic blocks to become unreachable, changing the program's behavior

B It will have no effect since edges do not affect execution

C It will convert the flow graph into a tree structure

D It will merge two basic blocks into one larger block

💡 Hint

Consider what happens if a path of execution is removed from the control flow.

Removing an edge that represents a conditional jump can make some blocks unreachable, potentially changing how the program runs.