~cnx/roux - Alternative QBE compiler

Age	Commit message (Collapse)	Author
2019-02-26	new copy elimination pass	Quentin Carbonneaux
	The sparse data-flow analysis used for copy elimination before this patch could sometimes diverge. The core reason for this behavior is that the visitphi() function was not monotonic in the following copy-of lattice: top (represented as the temp / \| \ itself) x y z ... \ \| / bot (represented as R) This monotonicity defect could be fixed by reverting 2f41ff03, but then the pass would end up missing some redundant phis. This patch re-implements the pass from scratch using a different approach. The new algorithm should get rid of all redundant copies. On the other hand, it can run slower than the monotonic sparse data-flow analysis because, in the worst case, an instruction in a phi cluster can be visited as many times as there are phis in the input program. Thanks to Michael Forney for reviewing and testing the new pass.
2018-04-26	Fix compiler warnings.	Emil Skoeldberg
	Compiler warned about comparison between signed and unsigned values.
2017-02-27	cosmetic fixes	Quentin Carbonneaux

2017-02-25	do sign/zero extensions removal in copy.c	Quentin Carbonneaux

2016-12-08	use a queue for copy elimination	Quentin Carbonneaux

2016-10-22	fix bug in copy propagation	Quentin Carbonneaux
	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.
2016-04-20	match jumps/ops with il text	Quentin Carbonneaux

2016-04-19	use assert for ssa invariants in fold/copy	Quentin Carbonneaux

2016-04-12	diagnose some undefined uses	Quentin Carbonneaux

2016-03-31	cleanup error handling	Quentin Carbonneaux

2016-03-29	new layout, put LICENSE in root	Quentin Carbonneaux