From 2f41ff03e2c6d1b16e9d4300315ca1c841e3970e Mon Sep 17 00:00:00 2001 From: Quentin Carbonneaux Date: Sat, 22 Oct 2016 13:32:43 -0400 Subject: fix bug in copy propagation The pass was not doing anything incorrect, but it missed some opportunities to optimize. On a copy heavy example I observed that, in the output of the pass a phi of the following shape remained: %a =w phi @A %c, @B %a Originally the phi for %a was: %a =w phi @A %b, @B %a Since %b was discovered a copy of %c, %a should have been eliminated and replaced with %c. I think the problem is that knowledge on the first argument of the phi %a changes as the algorithm progresses, a more detailed walk- through follows. In the first round of the algoritm, %a is discovered to be a copy of its first argument %b. phi(%b, %a) -> %b In the second round, %a is computed as the phi of %c (since the first argument changed) and %b (the result of the first iteration), in our lattice, the glb of those two is bottom. phi(%c, %b) -> %a (Bottom) Finally, there is a third round in which we compute %a as the phi of %a and %c, which again, gives bottom. phi(%c, %a) -> %a (Bottom) The bug is not tied to a phi of a copy, for example, if the first argument is speculated to be a copy of 0 and then, this knowledge is retracted; we will compute in sequence: phi(0, %a) -> 0 phi(%b, 0) -> %a (Bottom) phi(%b, %a) -> %a (Bottom) The way I fixed this is by ignoring arguments of the phi that were discovered to be copies of the phi node itself. This will make the last rounds above do the correct thing. --- copy.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'copy.c') diff --git a/copy.c b/copy.c index 06a0fb3..965f202 100644 --- a/copy.c +++ b/copy.c @@ -38,7 +38,7 @@ visitphi(Phi *p, Ref *cp, RList **w) r = R; for (a=0; anarg; a++) { r1 = copyof(p->arg[a], cp); - if (req(r1, R)) + if (req(r1, R) || req(r1, p->to)) continue; if (req(r, R) || req(r, r1)) r = r1; -- cgit 1.4.1