Skip to content

Calculate register active blocks with tradition liveness analysing algorithm #28

Description

@longfangsong

Is your feature request related to a problem? Please describe.
Currently, we calculate all_simple_paths from def block to every use block and union them all to find all blocks that a register can be active.

However, traditionally, the liveness analysing algorithm is something like this:

in[exit] = {};
for bb in basic_blocks {
  in[bb] = {};
}
let mut changed = true;
while changed {
  changed = false;
  for bb in basic_blocks {
    out[bb] = bb.succ().map(|s| in[s]).fold(Set::union);
    in[bb] = use[bb] union (out[bb] - def[bb])
  }
}

Which performance is in theory better than calculating all_simple_paths.

However, phi nodes need to be handled in a special way if we want to use this algorithm.

%a = phi [bb1, %0], [bb2, %1] 

It seems it "uses" %0 and %1, but to make the algorithm correct, we should "pretend" %0 is killed by the end of bb1 and %1 is killed by the end of bb2, and they are not in use of this bb.

Describe the solution you'd like
Implement this algorithm and do some benchmarks to make sure we do make a performance improvement.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    feature requestA request for a certain featuremediumThis issue is not so easy to fix

    Type

    No type

    Projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions