class RegisterAllocator:
   def live_analyze(self):
      # Determine liveness:
      for i in self.Instructions:
         i.live_in = set()
         i.live_out = set()
      for z in range(50):
         # TODO iterate until converge
         for i in self.Instructions:
            lo_mk = i.live_out.difference(i.defs)
            i.live_in = i.uses.union(lo_mk)
            lo = set()
            for s in i.succ:
               lo = lo.union(s.live_in)
            i.live_out = lo
   def registerAllocate(self, ir, regs):
      allVals = []
      # construct interference:
      for i in ir.Instructions:
         for v in i.live_in:
            allVals.append(v)
            for v2 in i.live_in:
               if v != v2:
                  v.interferes.add(v2)
      # assign random registers:
      regs = set(regs)
      for v in allVals:
         takenregs = set([iv.reg for iv in v.interferes])
         r2 = list(regs.difference(takenregs))
         # Pick next available:
         v.reg = r2[0]