The author presents new definitions for weak and strong regions in a control-flow graph and presents nearly-linear-time algorithms for computing these regions. Computing strong regions is important in code scheduling, permitting movement of instructions across basic blocks (in the absence of data dependence problems) to vertices in the same strong region. Strong regions can also permit more efficient placement of profiling code, since only one counter is needed for each strong region.

The author presents the definitions and algorithms clearly enough to understand and apply. His illustrations help immensely in understanding the paper. Following each algorithm, he proves its correctness. The paper’s length is appropriate for the material. The author includes 12 carefully selected references, which should aid researchers in this area. Overall, the paper presents practical algorithms while covering all the pertinent theory gracefully.