From 811de8d46881118ca25dc4f7bf735bf5f9eb8e4d Mon Sep 17 00:00:00 2001
From: Jacob Lifshay <programmerjake@gmail.com>
Date: Mon, 10 Oct 2022 20:52:31 -0700
Subject: [PATCH] working on code

---
 src/bigint_presentation_code/toom_cook.py | 90 ++++++++++++++++-------
 1 file changed, 65 insertions(+), 25 deletions(-)

diff --git a/src/bigint_presentation_code/toom_cook.py b/src/bigint_presentation_code/toom_cook.py
index 6a389c1..dd9061b 100644
--- a/src/bigint_presentation_code/toom_cook.py
+++ b/src/bigint_presentation_code/toom_cook.py
@@ -1,5 +1,4 @@
 from abc import ABCMeta, abstractmethod
-import builtins
 from collections import defaultdict
 from enum import Enum, unique
 from typing import AbstractSet, Iterable, Mapping, TYPE_CHECKING
@@ -72,6 +71,10 @@ class GlobalMem(Enum, PhysLoc):
     GlobalMem = "GlobalMem"
 
 
+ALLOCATABLE_REGS = frozenset((set(GPR) - set(SPECIAL_GPRS))
+                             | set(XERBit) | set(GlobalMem))
+
+
 @plain_data()
 @final
 class StackSlot(GPROrStackLoc):
@@ -380,7 +383,7 @@ class OpCopy(Op):
         return {"dest": self.dest}
 
     def __init__(self, src):
-        # type: (VecArg | SSAVal) -> None
+        # type: (SSAGPRVal) -> None
         self.dest = src.like(op=self, arg_name="dest")
         self.src = src
 
@@ -391,27 +394,9 @@ class OpCopy(Op):
             raise ValueError(f"{val} must be an operand of {self}")
         if val.get_phys_loc(value_assignments) is not None:
             raise ValueError(f"{val} already assigned a physical location")
-        conflicting_regs = set()  # type: set[GPR]
-        if val in self.output_ssa_vals() and isinstance(self.dest, VecArg):
-            # OpCopy is the only op that can write to physical locations in
-            # any order, it handles figuring out the right instruction sequence
-            dest_locs = {}  # type: dict[GPROrStackLoc, SSAVal]
-            for val in self.dest.regs:
-                loc = val.get_phys_loc(value_assignments)
-                if loc is None:
-                    continue
-                if loc in dest_locs:
-                    raise ValueError(
-                        f"duplicate destination location not allowed: "
-                        f"{val} is assigned to {loc} which is also "
-                        f"written by {dest_locs[loc]}")
-                dest_locs[loc] = val
-                if isinstance(loc, GPR):
-                    conflicting_regs.add(loc)
         if not isinstance(val, SSAGPRVal):
             raise ValueError("invalid operand type")
-        return val.possible_reg_assignments(value_assignments,
-                                            conflicting_regs)
+        return val.possible_reg_assignments(value_assignments)
 
 
 def range_overlaps(range1, range2):
@@ -912,6 +897,9 @@ class EqualitySet(AbstractSet[SSAVal]):
     def __len__(self):
         return len(self.__items)
 
+    def __hash__(self):
+        return super()._hash()
+
 
 @final
 class EqualitySets(Mapping[SSAVal, EqualitySet]):
@@ -970,6 +958,57 @@ class LiveIntervals(Mapping[EqualitySet, LiveInterval]):
         return iter(self.__live_intervals)
 
 
+@final
+class IGNode:
+    """ interference graph node """
+    __slots__ = "equality_set", "edges"
+
+    def __init__(self, equality_set, edges=()):
+        # type: (EqualitySet, Iterable[IGNode]) -> None
+        self.equality_set = equality_set
+        self.edges = set(edges)
+
+    def add_edge(self, other):
+        # type: (IGNode) -> None
+        self.edges.add(other)
+        other.edges.add(self)
+
+    def __eq__(self, other):
+        # type: (object) -> bool
+        if isinstance(other, IGNode):
+            return self.equality_set == other.equality_set
+        return NotImplemented
+
+    def __hash__(self):
+        return self.equality_set.__hash__()
+
+    def __repr__(self, nodes=None):
+        # type: (None | dict[IGNode, int]) -> str
+        if nodes is None:
+            nodes = {}
+        if self in nodes:
+            return f"<IGNode #{nodes[self]}>"
+        nodes[self] = len(nodes)
+        edges = "{" + ", ".join(i.__repr__(nodes) for i in self.edges) + "}"
+        return (f"IGNode(#{nodes[self]}, "
+                f"equality_set={self.equality_set}, "
+                f"edges={edges})")
+
+
+@final
+class InterferenceGraph(Mapping[EqualitySet, IGNode]):
+    def __init__(self, equality_sets):
+        # type: (Iterable[EqualitySet]) -> None
+        self.__nodes = {i: IGNode(i) for i in equality_sets}
+
+    def __getitem__(self, key):
+        # type: (EqualitySet) -> IGNode
+        return self.__nodes[key]
+
+    def __iter__(self):
+        return iter(self.__nodes)
+
+
 @plain_data()
 class AllocationFailed:
     __slots__ = "op_idx", "arg", "live_intervals"
@@ -984,10 +1023,11 @@ class AllocationFailed:
 def try_allocate_registers_without_spilling(ops):
     # type: (list[Op]) -> dict[SSAVal, PhysLoc] | AllocationFailed
     live_intervals = LiveIntervals(ops)
-    free_regs = set()  # type: set[GPR | XERBit]
-    free_regs.update(GPR)
-    free_regs.difference_update(SPECIAL_GPRS)
-    free_regs.update(XERBit)
+
+    def is_constrained(node):
+        # type: (EqualitySet) -> bool
+        raise NotImplementedError
+
     raise NotImplementedError
 
 
-- 
2.30.2