From ba1be444bde4682156768fe4eb86730ae98b189d Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Tue, 13 Dec 2022 00:12:33 -0800 Subject: [PATCH] working on code --- .../_tests/test_register_allocator.py | 356 +++++++++--------- .../register_allocator.py | 3 +- 2 files changed, 181 insertions(+), 178 deletions(-) diff --git a/src/bigint_presentation_code/_tests/test_register_allocator.py b/src/bigint_presentation_code/_tests/test_register_allocator.py index be76d2d..78046fe 100644 --- a/src/bigint_presentation_code/_tests/test_register_allocator.py +++ b/src/bigint_presentation_code/_tests/test_register_allocator.py @@ -332,12 +332,81 @@ class TestRegisterAllocator(unittest.TestCase): self.assertEqual( repr(reg_assignments), - "{>: " - "Loc(kind=LocKind.GPR, start=14, reg_len=32), " - ">: " - "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " - ">: " + "{" + ">: " + "Loc(kind=LocKind.GPR, start=14, reg_len=1), " + ">: " "Loc(kind=LocKind.GPR, start=14, reg_len=32), " + ">: " + "Loc(kind=LocKind.GPR, start=45, reg_len=32), " + ">: " + "Loc(kind=LocKind.GPR, start=45, reg_len=32), " + ">: " + "Loc(kind=LocKind.GPR, start=45, reg_len=32), " + ">: " + "Loc(kind=LocKind.GPR, start=45, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=46, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=47, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=48, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=49, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=50, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=51, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=52, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=53, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=54, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=55, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=56, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=57, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=58, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=59, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=60, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=61, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=62, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=63, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=64, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=65, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=66, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=67, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=68, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=69, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=70, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=71, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=72, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=73, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=74, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=75, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=76, reg_len=1), " ">: " "Loc(kind=LocKind.GPR, start=14, reg_len=1), " ">: " @@ -402,228 +471,161 @@ class TestRegisterAllocator(unittest.TestCase): "Loc(kind=LocKind.GPR, start=44, reg_len=1), " ">: " "Loc(kind=LocKind.GPR, start=45, reg_len=1), " - ">: " - "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=3, reg_len=1), " + ">: " + "Loc(kind=LocKind.GPR, start=14, reg_len=32), " ">: " - "Loc(kind=LocKind.GPR, start=4, reg_len=1), " + "Loc(kind=LocKind.GPR, start=3, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=5, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=14, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=15, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=16, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=17, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=18, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=19, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=20, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=21, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=22, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=23, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=24, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=25, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=26, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=27, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=28, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=29, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=30, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=31, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=32, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=33, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=34, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=35, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=36, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=37, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=38, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=39, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=40, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=41, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=42, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=43, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=44, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=45, reg_len=1), " + "Loc(kind=LocKind.GPR, start=4, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=6, reg_len=1), " + "Loc(kind=LocKind.GPR, start=5, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=7, reg_len=1), " + "Loc(kind=LocKind.GPR, start=6, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=8, reg_len=1), " + "Loc(kind=LocKind.GPR, start=7, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=9, reg_len=1), " + "Loc(kind=LocKind.GPR, start=8, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=10, reg_len=1), " + "Loc(kind=LocKind.GPR, start=9, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=11, reg_len=1), " + "Loc(kind=LocKind.GPR, start=10, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=12, reg_len=1), " + "Loc(kind=LocKind.GPR, start=11, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=46, reg_len=1), " + "Loc(kind=LocKind.GPR, start=12, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=47, reg_len=1), " + "Loc(kind=LocKind.GPR, start=77, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=48, reg_len=1), " + "Loc(kind=LocKind.GPR, start=78, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=49, reg_len=1), " + "Loc(kind=LocKind.GPR, start=79, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=50, reg_len=1), " + "Loc(kind=LocKind.GPR, start=80, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=51, reg_len=1), " + "Loc(kind=LocKind.GPR, start=81, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=52, reg_len=1), " + "Loc(kind=LocKind.GPR, start=82, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=53, reg_len=1), " + "Loc(kind=LocKind.GPR, start=83, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=54, reg_len=1), " + "Loc(kind=LocKind.GPR, start=84, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=55, reg_len=1), " + "Loc(kind=LocKind.GPR, start=85, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=56, reg_len=1), " + "Loc(kind=LocKind.GPR, start=86, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=57, reg_len=1), " + "Loc(kind=LocKind.GPR, start=87, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=58, reg_len=1), " + "Loc(kind=LocKind.GPR, start=88, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=59, reg_len=1), " + "Loc(kind=LocKind.GPR, start=89, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=60, reg_len=1), " + "Loc(kind=LocKind.GPR, start=90, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=61, reg_len=1), " + "Loc(kind=LocKind.GPR, start=91, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=62, reg_len=1), " + "Loc(kind=LocKind.GPR, start=92, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=63, reg_len=1), " + "Loc(kind=LocKind.GPR, start=93, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=64, reg_len=1), " + "Loc(kind=LocKind.GPR, start=94, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=65, reg_len=1), " + "Loc(kind=LocKind.GPR, start=95, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=66, reg_len=1), " + "Loc(kind=LocKind.GPR, start=96, reg_len=1), " ">: " - "Loc(kind=LocKind.GPR, start=67, reg_len=1), " + "Loc(kind=LocKind.GPR, start=97, reg_len=1), " + ">: " + "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " + ">: " + "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " ">: " "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=14, reg_len=32), " ">: " "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=14, reg_len=32), " ">: " "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " - ">: " - "Loc(kind=LocKind.GPR, start=14, reg_len=32), " ">: " "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1), " ">: " - "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1)}" + "Loc(kind=LocKind.VL_MAXVL, start=0, reg_len=1)" + "}" ) state = GenAsmState(reg_assignments) fn.gen_asm(state) self.assertEqual(state.output, [ 'setvl 0, 0, 32, 0, 1, 1', 'setvl 0, 0, 32, 0, 1, 1', - 'sv.addi *14, 0, 0', + 'sv.addi *45, 0, 0', 'setvl 0, 0, 32, 0, 1, 1', 'setvl 0, 0, 32, 0, 1, 1', 'setvl 0, 0, 32, 0, 1, 1', - 'or 67, 14, 14', - 'or 66, 15, 15', - 'or 65, 16, 16', - 'or 64, 17, 17', - 'or 63, 18, 18', - 'or 62, 19, 19', - 'or 61, 20, 20', - 'or 60, 21, 21', - 'or 59, 22, 22', - 'or 58, 23, 23', - 'or 57, 24, 24', - 'or 56, 25, 25', - 'or 55, 26, 26', - 'or 54, 27, 27', - 'or 53, 28, 28', - 'or 52, 29, 29', - 'or 51, 30, 30', - 'or 50, 31, 31', - 'or 49, 32, 32', - 'or 48, 33, 33', - 'or 47, 34, 34', - 'or 46, 35, 35', - 'or 12, 36, 36', - 'or 11, 37, 37', - 'or 10, 38, 38', - 'or 9, 39, 39', - 'or 8, 40, 40', - 'or 7, 41, 41', - 'or 6, 42, 42', - 'or 5, 43, 43', - 'or 4, 44, 44', - 'or 3, 45, 45', - 'or 14, 3, 3', - 'or 15, 4, 4', - 'or 16, 5, 5', - 'or 17, 6, 6', - 'or 18, 7, 7', - 'or 19, 8, 8', - 'or 20, 9, 9', - 'or 21, 10, 10', - 'or 22, 11, 11', - 'or 23, 12, 12', - 'or 24, 46, 46', - 'or 25, 47, 47', - 'or 26, 48, 48', - 'or 27, 49, 49', - 'or 28, 50, 50', - 'or 29, 51, 51', - 'or 30, 52, 52', - 'or 31, 53, 53', - 'or 32, 54, 54', - 'or 33, 55, 55', - 'or 34, 56, 56', - 'or 35, 57, 57', - 'or 36, 58, 58', - 'or 37, 59, 59', - 'or 38, 60, 60', - 'or 39, 61, 61', - 'or 40, 62, 62', - 'or 41, 63, 63', - 'or 42, 64, 64', - 'or 43, 65, 65', - 'or 44, 66, 66', - 'or 45, 67, 67', + 'or 97, 45, 45', + 'or 96, 46, 46', + 'or 95, 47, 47', + 'or 94, 48, 48', + 'or 93, 49, 49', + 'or 92, 50, 50', + 'or 91, 51, 51', + 'or 90, 52, 52', + 'or 89, 53, 53', + 'or 88, 54, 54', + 'or 87, 55, 55', + 'or 86, 56, 56', + 'or 85, 57, 57', + 'or 84, 58, 58', + 'or 83, 59, 59', + 'or 82, 60, 60', + 'or 81, 61, 61', + 'or 80, 62, 62', + 'or 79, 63, 63', + 'or 78, 64, 64', + 'or 77, 65, 65', + 'or 12, 66, 66', + 'or 11, 67, 67', + 'or 10, 68, 68', + 'or 9, 69, 69', + 'or 8, 70, 70', + 'or 7, 71, 71', + 'or 6, 72, 72', + 'or 5, 73, 73', + 'or 4, 74, 74', + 'or 3, 75, 75', + 'or 14, 76, 76', + 'or 15, 3, 3', + 'or 16, 4, 4', + 'or 17, 5, 5', + 'or 18, 6, 6', + 'or 19, 7, 7', + 'or 20, 8, 8', + 'or 21, 9, 9', + 'or 22, 10, 10', + 'or 23, 11, 11', + 'or 24, 12, 12', + 'or 25, 77, 77', + 'or 26, 78, 78', + 'or 27, 79, 79', + 'or 28, 80, 80', + 'or 29, 81, 81', + 'or 30, 82, 82', + 'or 31, 83, 83', + 'or 32, 84, 84', + 'or 33, 85, 85', + 'or 34, 86, 86', + 'or 35, 87, 87', + 'or 36, 88, 88', + 'or 37, 89, 89', + 'or 38, 90, 90', + 'or 39, 91, 91', + 'or 40, 92, 92', + 'or 41, 93, 93', + 'or 42, 94, 94', + 'or 43, 95, 95', + 'or 44, 96, 96', + 'or 45, 97, 97', 'setvl 0, 0, 32, 0, 1, 1', - 'setvl 0, 0, 32, 0, 1, 1']) + 'setvl 0, 0, 32, 0, 1, 1' + ]) if __name__ == "__main__": diff --git a/src/bigint_presentation_code/register_allocator.py b/src/bigint_presentation_code/register_allocator.py index 76fc966..0539f0a 100644 --- a/src/bigint_presentation_code/register_allocator.py +++ b/src/bigint_presentation_code/register_allocator.py @@ -5,7 +5,7 @@ this uses an algorithm based on: [Retargetable Graph-Coloring Register Allocation for Irregular Architectures](https://user.it.uu.se/~svenolof/wpo/AllocSCOPES2003.20030626b.pdf) """ -from functools import reduce +from functools import lru_cache, reduce from itertools import combinations, count from typing import Callable, Container, Iterable, Iterator, Mapping, TextIO, Tuple @@ -296,6 +296,7 @@ class MergedSSAVal(metaclass=InternedMeta): return lhs, rhs return None + @lru_cache(maxsize=None, typed=True) def copy_merged(self, lhs_loc, rhs, rhs_loc, copy_relation): # type: (Loc | None, MergedSSAVal, Loc | None, _CopyRelation) -> MergedSSAVal cr_lhs, cr_rhs = copy_relation -- 2.30.2