Data-dependent control flow reduction

摘要

A transformation of software control flow to reduce the number of successor blocks in the control flow as well as the number of flow control elements. The control flow after transformation has more streamline code and less data-dependent control flow, which yields better runtime performance, and at the same time maintain functionally equivalent. Software control flow is improved by, for each data-dependent flow control element in the control flow graph, finding value narrowing points that would be sufficient that the exit control flow selected by that flow control element would be deterministic. The control flow is modified such that the control flow leads (without passing through the flow control element) from that found value narrowing point to the identified control flow that would be selected given the found value narrowing point. This method may be repeated proceeding from one flow control element to the next.

主权项

1. A computer program product comprising one or more computer-readable hardware storage media having thereon computer-executable instructions that are structured such that, when executed by one or more processors of a computing system, cause the computing system to perform a method for improving a control flow of a software program, the method comprising:
an act of traversing a control flow graph corresponding to the control flow of the software program; as a result of the act of traversing, an act of detecting a flow control element that specifies a plurality of exit control flows that might be taken at runtime depending on a value of a parameter at runtime; in response to the act of detecting, an act of attempting to find a value narrowing point in the control flow graph prior to the flow control element such that the value narrowing point narrows the value of the parameter sufficiently that an exit control flow that would be selected by the flow control element is deterministic; if a value narrowing point is found in the act of attempting to find a value narrowing point, an act of identifying, from the plurality of exit control flows, the exit control flow that would be taken given the found value narrowing point; and an act of modifying the control flow such that control flow graph from the found value narrowing point leads to the identified exit control flow without traversing the flow control element.