Page MenuHomePhabricator

[StackLifetime] More efficient loop for LivenessType::Must
ClosedPublic

Authored by vitalybuka on Sep 28 2022, 12:16 AM.

Details

Summary

CFG with cycles may requires additional passes of "while (Changed)"
iteration if to propagate data back from latter blocks to earlier blocks,
ordered according to depth_fist.

OR logic, used for ::May, converge to stable state faster then AND logic
use for ::Must.

Though the better solution is to switch to some some form of queue, but
having that this one is good enough, I will consider to do that later.

We can switch ::Must to OR logic if we calculate "may be dead" instead
of direct "must be alive" and then convert values to match existing
interface.

Additionally it fixes correctness in "@cycle" test.

Diff Detail

Event Timeline

vitalybuka created this revision.Sep 28 2022, 12:16 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 28 2022, 12:16 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
vitalybuka requested review of this revision.Sep 28 2022, 12:16 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 28 2022, 12:16 AM
vitalybuka edited the summary of this revision. (Show Details)Sep 28 2022, 12:17 AM
vitalybuka added reviewers: kstoimenov, fmayer.
vitalybuka edited the summary of this revision. (Show Details)Sep 28 2022, 12:40 PM
fmayer added inline comments.Sep 28 2022, 12:56 PM
llvm/lib/Analysis/StackLifetime.cpp
200–201

if you wanted to micro-optimize, you could put the BlockInfo.LiveIn |= BitsIn in this condition, and make the one below an else if.

217–218

these comments are a bit confusing. it says "set by lifetime start" then uses BlockInfo.End.

vitalybuka marked an inline comment as done.Sep 28 2022, 1:35 PM
vitalybuka added inline comments.
llvm/lib/Analysis/StackLifetime.cpp
200–201

I'll keep as-is for simplicity. This apply only to the entry.

217–218

I'll move to the next line in the next snapshot.

kstoimenov accepted this revision.Sep 28 2022, 2:54 PM
This revision is now accepted and ready to land.Sep 28 2022, 2:54 PM
vitalybuka marked an inline comment as done.

comment

another comment

fmayer accepted this revision.Sep 28 2022, 4:14 PM
fmayer added inline comments.
llvm/lib/Analysis/StackLifetime.cpp
222

nit for consistency with above.

This revision was landed with ongoing or failed builds.Sep 28 2022, 4:29 PM
This revision was automatically updated to reflect the committed changes.