Back Edges and Reducibility A back edge is an edge a >b whose head b dominates its tail a. For any flow graph,every back edge is retreating,but not every retreating edge is a back edge. A flow graph is said to be reducible if all its retreating edges in any depth-first spanning tree are also back edges. A flow graph is said to be reducible if all its retreating edges in any depth-first spanning tree are also back edges. CS308 Compiler TheoryBack Edges and Reducibility • A back edge is an edge a Æb whose head b dominates its tail a. • For any flow graph, every back edge is retreating, but not every retreating edge is a back edge. • A flow graph is said to be reducible if all its retreatin g edges in any depth-first spanning tree are also back edges. • A flow graph is said to be reducible if all its retreating edges in any depth -first spanning tree are also back edges first spanning tree are also back edges. CS308 Compiler Theory 9