Commit graph

1395 commits

Author SHA1 Message Date
Quentin Carbonneaux
6c64119f55 do not freeze r when allocating for r2 2015-04-01 09:30:00 -04:00
Quentin Carbonneaux
3ca7d9849b update TODO with fix commit 2015-03-31 17:59:13 -04:00
Quentin Carbonneaux
bb9c5e7835 tentative fix of messed up spills for phis 2015-03-31 17:58:27 -04:00
Quentin Carbonneaux
f00bc00ed6 add bugs 2015-03-31 16:02:53 -04:00
Quentin Carbonneaux
b330009493 avoid evicting arguments 2015-03-31 16:00:25 -04:00
Quentin Carbonneaux
868667ea27 add move constant to spill 2015-03-31 13:51:00 -04:00
Quentin Carbonneaux
6d6b1ef4b0 better support for constants 2015-03-31 13:23:37 -04:00
Quentin Carbonneaux
c65422a14f refine TODO 2015-03-27 17:22:25 -04:00
Quentin Carbonneaux
92dd898493 add a scratch TODO 2015-03-27 17:13:23 -04:00
Quentin Carbonneaux
288613f0d6 expect reg in brz, might not be true 2015-03-25 16:26:47 -04:00
Quentin Carbonneaux
c07e0bdcef simplify label logic 2015-03-25 16:24:14 -04:00
Quentin Carbonneaux
4379da2447 branch code 2015-03-25 15:58:15 -04:00
Quentin Carbonneaux
5c44aecd0c more codegen 2015-03-25 14:32:52 -04:00
Quentin Carbonneaux
ae76cfb9cd start writing some codegen 2015-03-25 12:23:59 -04:00
Quentin Carbonneaux
99b136d7ba improvements to elf.ml 2015-02-20 20:22:12 -05:00
Quentin Carbonneaux
c0271371c6 fix bugs in movgen 2015-02-20 16:06:24 -05:00
Quentin Carbonneaux
4e307b91e7 start work on movgen 2015-02-20 15:52:17 -05:00
Quentin Carbonneaux
00cec4cf35 cosmetics 2015-02-18 20:00:42 -05:00
Quentin Carbonneaux
cc1f38f501 add spill test 2015-02-18 19:58:12 -05:00
Quentin Carbonneaux
8344a68910 kind of working! 2015-02-18 18:59:40 -05:00
Quentin Carbonneaux
67cf06ca8c wip 2015-02-18 16:44:27 -05:00
Quentin Carbonneaux
cc50060844 wip 2015-02-18 10:18:16 -05:00
Quentin Carbonneaux
622da2b11b add notes
I start to believe that it is possible to simply
reuse the regalloc I wrote.  All the data structures
seem fine.

Here is a list modifications to make for sure:
 - Keep track of the mapping for live in variables
   for each block.
 - Make sure 'loc' (or a new function) returns
   registers for the arguments of base instructions.

Spilling
--------

When we need a register and none are left.  If we
are at the end of a block, simply spill anybody (the
resolving will take care of adding the moves).  If we
are in a block, find somebody to spill and its next
use, if the next use is in the same block, emit reload
code, otherwise, decide to emit the reload at the
end of the cheapest block (this means that we have to
patch some mappings that were already stored).  We let
the resolve handle the insertion of the reload code.

Example:

  +----------------------+
  |                      |
  |                      |
  |   +----+     +----+  |   +----+
 -+-> | b1 | --> | b2 | -+-> | b3 | -->
      +----+     +----+      +----+
        ^                       ^
        Spill x                 First use of x
        (Was in r1)

The cheapest position for reload code is at the
beginning of b3, so we have to modify the mapping
at the end of b1, beginning of b2, and end of b2 to
change it from (x -> r1) to (x -> spill).

Reloading
---------

When a spilled variable is needed in register.  In this
case, we are necessarily inside a block (or at a branch)
because that is the only place we require a variable to
be in register.  Here again we are constrained to insert
the spill code before the next use of the variable, but
more importantly, we must do it before the register
chosen is *in use next*.
2015-02-15 18:43:52 -05:00
Quentin Carbonneaux
83474cd206 finished interval building, untested 2015-02-13 23:05:23 -05:00
Quentin Carbonneaux
b83133cbbe attempt a new linear scan implementation 2015-02-13 22:37:07 -05:00
Quentin Carbonneaux
d621e6654b remove debug code for heaps 2015-02-13 15:41:16 -05:00
Quentin Carbonneaux
778e33848b implement binary heaps in lo3 2015-02-13 15:41:03 -05:00
Quentin Carbonneaux
bbf944c6e7 release also non-register locations 2015-01-22 12:00:55 -05:00
Quentin Carbonneaux
31abfbfa6d add some test programs 2015-01-22 11:55:45 -05:00
Quentin Carbonneaux
08523a2438 implement linear scan ideas in lo2.ml 2015-01-22 11:37:16 -05:00
Quentin Carbonneaux
d051e0c210 start hacking new regalloc 2015-01-14 22:36:53 -05:00
Quentin Carbonneaux
a2c0719131 more types 2015-01-11 12:56:18 -05:00
Quentin Carbonneaux
ec89cc7eb1 type surgery 2015-01-09 13:26:36 -05:00
Quentin Carbonneaux
41b9d07f79 try new presentation in lo2.ml 2015-01-08 22:00:20 -05:00
Quentin Carbonneaux
ea316953bb handle IBrz correctly 2015-01-06 13:17:19 -05:00
Quentin Carbonneaux
c0469ee2f0 first ugly allocator that works 2015-01-06 12:54:44 -05:00
Quentin Carbonneaux
72a74b97ab try to add code for phis 2015-01-05 21:56:49 -05:00
Quentin Carbonneaux
2bbff83d40 quick fix in loc2 for constants 2015-01-05 15:59:22 -05:00
Quentin Carbonneaux
85ffed1369 more work on regalloc, still screwed 2015-01-04 11:37:13 -05:00
Quentin Carbonneaux
5c73d7cdf3 start register allocation 2015-01-01 17:08:09 -05:00
Quentin Carbonneaux
2124e95718 add irreducible cflow example 2014-12-30 15:04:46 -05:00
Quentin Carbonneaux
046532e51d pad text in elf output function 2014-12-21 22:38:24 -05:00
Quentin Carbonneaux
fd1bb8148e start an ELF output module 2014-12-20 19:28:12 -05:00
Quentin Carbonneaux
1cf6ea7bcc allow multiple labels per line 2014-12-20 16:34:54 -05:00
Quentin Carbonneaux
59db3dd956 initial commit 2014-12-19 08:57:56 -05:00