Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Calculate register active blocks with tradition liveness analysing algorithm #28

Open
longfangsong opened this issue Dec 17, 2022 · 0 comments
Labels
feature request A request for a certain feature medium This issue is not so easy to fix

Comments

@longfangsong
Copy link
Member

longfangsong commented Dec 17, 2022

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.

@longfangsong longfangsong added feature request A request for a certain feature medium This issue is not so easy to fix labels Dec 17, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature request A request for a certain feature medium This issue is not so easy to fix
Projects
Status: Todo
Development

No branches or pull requests

1 participant