Page MenuHomePhabricator

profi - a flow-based profile inference algorithm: Part II (out of 3)
ClosedPublic

Authored by spupyrev on Sep 16 2021, 11:17 AM.

Details

Summary

This is a continuation of D109860.

Traditional flow-based algorithms cannot guarantee that the resulting edge
frequencies correspond to a *connected* flow in the control-flow graph. For
example, for an instance in the attached figure, a flow-based (or any other)
inference algorithm may produce an output in which the hot loop is disconnected
from the entry block (refer to the rightmost graph in the figure). Furthermore,
creating a connected minimum-cost maximum flow is a computationally NP-hard
problem. Hence, we apply a post-processing adjustments to the computed flow
by connecting all isolated flow components ("islands").

This feature helps to keep all blocks with sample counts connected and results
in significant performance wins for some binaries.

Diff Detail

Event Timeline

spupyrev created this revision.Sep 16 2021, 11:17 AM
spupyrev requested review of this revision.Sep 16 2021, 11:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 16 2021, 11:17 AM
spupyrev retitled this revision from profi - a flow-based profile inference algorithm: Part II to profi - a flow-based profile inference algorithm: Part II (out of 3).Sep 16 2021, 11:26 AM
spupyrev edited the summary of this revision. (Show Details)
spupyrev added reviewers: wenlei, hoy, wlei, davidxl, wmi, xur.
hoy accepted this revision.Mon, Nov 22, 2:33 PM

LGTM. As with the other profi patches, this patch has been reviewed internally before.

This revision is now accepted and ready to land.Mon, Nov 22, 2:33 PM
spupyrev updated this revision to Diff 391361.Thu, Dec 2, 9:39 AM

-rebase 2

This revision was automatically updated to reflect the committed changes.