ToolSphere

Basic Blocks and Flow Graph

Computer science

Find TAC leaders, basic blocks, control-flow edges, dominators and natural loops, with an SVG graph and source-code examples that update as you type.

Edit one instruction per line; the example is already analyzed.

2 straight-line blocks; 1 natural loop; leaders 1, 3

Input settings — TAC or source

TAC means three-address code: one simple assignment or jump per line.

Results update as you type. TAC accepts labels, scalar operations, indexed loads/stores and conditional jumps. Source mode supports assignments, if/else and while; it does not compile array syntax.

2 basic blocks · 1 natural loop

Copy analysis

Leaders and their rules

A leader is the first instruction of a straight-line block.

BlockFirst instructionLeader rule
B11first instruction
B23target of instruction 12

Control-flow graph

Scroll inside the graph to read all edge labels and blocks.

fallthroughtruefalseB1Instructions 1–2B2Instructions 3–12Exit

Edges are possible control transfers. EXIT is a display endpoint, not another basic block. Unreachable blocks remain visible.

Basic blocks

B1 · reachable

1: prod = 0
2: i = 1

Successors: B2

B2 · reachable

3: t1 = 4 * i
4: t2 = a[t1]
5: t3 = 4 * i
6: t4 = b[t3]
7: t5 = t2 * t4
8: t6 = prod + t5
9: prod = t6
10: t7 = i + 1
11: i = t7
12: if i <= 20 goto L1

Successors: B2; EXIT

Dominators

A dominator lies on every entry-to-block path.

BlockPredecessorsDominators
B1entryB1
B2B1, B2B1, B2

Back edges and natural loops

A natural loop returns to a header that dominates its latch (the block jumping back).

Back edgeHeaderLoop blocks
B2 → B2B2B2

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Basic Blocks and Flow Graph

  1. 1Start with the loaded dot-product program, or choose the identity-matrix or source-loop example.
  2. 2Choose Three-address code or Source snippet, then edit the program in the labelled input.
  3. 3Read each leader rule and inspect the instructions assigned to its block.
  4. 4Follow true, false, jump and fallthrough edges in the graph; check reachability and dominators.
  5. 5Review natural loops only where a reachable edge points back to a dominator, then copy the analysis.

About Basic Blocks and Flow Graph

Find the straight-line regions in a program

This basic-block and flow-graph tool turns a small program into the regions a compiler can analyse together. Start with three-address code, or use the source mode to run assignments, if/else statements and while loops through the site's existing TAC generator. The loaded dot-product example produces results immediately. There is no separate conversion step: changing the input recomputes the analysis, and malformed input produces a readable error instead of leaving an old answer visible.

Each result includes the leaders, the rule that introduced each leader, the block contents, a control-flow graph, predecessor and successor lists, dominator sets and natural loops. The purpose is to make a coursework answer inspectable. The tool does not run your program, optimise it, compile it to a real processor or prove that a branch condition is feasible. Its graph describes possible control transfers in the supplied code.

The leader rules and block boundaries

A basic block is a maximal straight-line instruction sequence. Control enters at its first instruction, and an ordinary branch appears only at its end. The first instruction is a leader. A conditional or unconditional jump target is also a leader, as is the instruction immediately following a jump when that instruction exists. An explicit exit also ends a block; following code is separated even when it is unreachable.

Sort those leader positions in program order. A block starts at a leader and includes every instruction up to, but excluding, the next leader. Source-line numbers and instruction ordinals can differ when the input has blank lines, comments or labels on their own lines. The output numbers actual instructions, so a standalone label does not create a fictitious instruction. A trailing label receives an explicit exit marker so jumps to the end have a destination.

Read and enter the supported TAC syntax

Use one instruction per line. Scalar assignments may copy an operand, negate an operand with minus or perform one arithmetic operation. Indexed array loads and stores are accepted with a simple index operand. Conditional branches use if a < b goto label, with the corresponding comparison operators also supported. Unconditional goto, halt and exit are recognised. Comments begin with a double slash.

Labels can be named, numbered or generated by the existing source translator. A jump to an unlabelled numeric target is interpreted as an instruction ordinal. Duplicate labels and missing jump targets are errors. Array indices in TAC are already-computed offsets: the tool does not infer an element size, a row-major address formula or bounds checks. Source mode is deliberately narrower and does not compile array syntax. For a compound source expression, use Source snippet rather than placing several operations into one TAC instruction.

Worked dot-product and matrix examples

The dot-product example has 2 blocks. Its leaders are instructions 1 and 3. The initial assignments stay together, and the loop body begins at the branch target. The last conditional jump either returns to that body or leaves the program.

Block Instruction range Dominators
B1 1–2 B1
B2 3–12 B1, B2

The identity-matrix example uses the textbook-style nested initialisation loops followed by the diagonal assignment loop. It has 6 blocks, with leaders at 1, 2, 3, 10, 12, 13. These positions come from running the library on the displayed TAC, including its explicit array-offset calculations.

Block Instruction range
B1 1–1
B2 2–2
B3 3–9
B4 10–11
B5 12–12
B6 13–17

The matrix analysis reports 3 natural loops: B3 → B3 over B3; B4 → B2 over B2, B3, B4; B6 → B6 over B6. Load the example to inspect the corresponding edges and compare the inner loop with its enclosing loop.

Interpret graph edges and reachability

A true edge follows a conditional branch's target. A false edge proceeds to the following block. An unconditional jump has only its target as a successor, while an ordinary assignment or array operation falls through to the next block. EXIT is drawn as a display endpoint, not counted as another basic block. Edges describe syntactic possibilities; the analyser does not remove a branch because a constant comparison happens to be false.

Unreachable blocks remain in the block listing and graph so you can see code after a jump or exit. Their dominators are not reported as though they were reachable from the entry. This matters when a disconnected cycle exists: its backward-looking edges should not be mistaken for loops reached by the program. A graph layout is a visual arrangement; an arrow's direction on the screen is not itself a dominance test.

Dominators and natural loops

For reachable blocks, a block dominates another when every entry-to-that-block path passes through it. The entry starts with itself as its dominator set. Other reachable blocks begin with the full reachable set; repeated predecessor intersection computes the fixed point. In set notation, Dom(B) = {B} ∪ intersection of Dom(P) over reachable predecessors P. This is an intersection, not a union of every block that could appear earlier.

A reachable edge from a latch to a header is a back edge for this analysis when the header dominates the latch. Its natural loop contains that header and latch plus the relevant predecessor closure, stopping at the header. A self-loop contains its own block without pulling in the entry predecessor. An irreducible cycle with multiple entries need not have a dominating header, so not every graph cycle appears in the natural-loop table. Multiple latches can produce separate rows sharing a header.

Check an exam answer and continue the workflow

Compare instruction ranges before comparing diagram shapes. Check that every jump target starts a block, every branch ends its block, and an unconditional jump has no accidental fallthrough edge. Then verify reachability before working with dominators. A correct-looking loop arrow does not establish the natural-loop property unless its target dominates its source.

Use the three-address code generator to explore expression translation, and the LR parser for the parsing stage that precedes it. The compiler lab groups the related coursework tools. Copy analysis saves the current blocks, leader reasons, successors, dominators and loop rows as text; it does not export an executable program or retain earlier inputs.

Frequently asked questions

How do I find basic block leaders?

Mark the first instruction, every jump target and the instruction after each jump when it exists. The tool lists the rule beside each resulting block so you can inspect the partition.

What is the difference between a basic block and a flow graph?

A basic block is one straight-line instruction region. A flow graph connects those regions with possible control-transfer edges.

Can I paste source code instead of TAC?

Yes, select Source snippet for the supported assignment, if/else and while syntax. That mode uses the existing TAC generator; it does not compile a complete C program or array syntax.

Are labels counted as instructions?

Standalone labels attach to the following instruction rather than consuming an ordinal. A trailing label gets an explicit exit marker so it can be a jump destination.

Does every label start a basic block?

A label used as a jump target does. An unused label alone does not force another block under the leader rules used here.

What does a dominator mean?

A block dominates a reachable block if every path from entry to that block passes through it. The result is computed by intersecting predecessor dominator sets until they stop changing.

Is every backward jump a natural loop?

No. The target must dominate the source, and the edge must be reachable from entry. Other cycles can exist without a single dominating header.

Why is unreachable code still shown?

It helps you inspect the input rather than silently deleting instructions. Its dominator entry is marked uncomputed, and disconnected cycles are excluded from natural-loop detection.

Does the tool evaluate conditional branches?

No. Both syntactic outcomes of a conditional branch are included when they have destinations. It does not prove feasibility, run array operations or perform constant propagation.

Can I copy the analysis?

Yes. Copy analysis saves the current block contents, leader rules, successor lists, dominators and natural-loop rows as text. Nothing is uploaded or stored as a shared program.

Have a suggestion for Basic Blocks and Flow Graph?Share your feedback ↗