"""Defines control flow graph IR data structures.""" # Let's just agree to disagree on map vs list comprehensions, pylint. # pylint: disable=I0011,W0141 class SharedCounter(object): """Defines a shared counter.""" def __init__(self): self.index = 0 def next_value(self): """Gets the next value for this counter.""" result = self.index self.index += 1 return result class BasicBlock(object): """Represents a basic block.""" def __init__(self, counter): self.parameters = [] self.definitions = [] self.counter = counter self.index = counter.next_value() self.flow = UnreachableFlow() def append_parameter(self, parameter): """Appends a parameter to this basic block.""" result = self.create_definition(parameter) self.parameters.append(result) return result def prepend_definition(self, value): """Defines the given value in this basic block.""" result = self.create_definition(value) self.definitions.insert(0, result) return result def append_definition(self, value): """Defines the given value in this basic block.""" result = self.create_definition(value) self.definitions.append(result) return result def create_definition(self, value=None): """Creates a definition, but does not assign it to this block yet.""" if isinstance(value, Definition): return value else: assert isinstance(value, Value) or value is None return Definition(self.counter.next_value(), value) def remove_definition(self, definition): """Removes the given definition from this basic block.""" return self.definitions.remove(definition) def __str__(self): prefix = '!%d(%s):' % (self.index, ', '.join(map(str, self.parameters))) return '\n'.join( [prefix] + [' ' * 4 + str(item) for item in self.definitions + [self.flow]]) class Definition(object): """Maps a value to a variable.""" def __init__(self, index, value): self.index = index self.value = value if value is not None: assert isinstance(value, Value) def redefine(self, new_value): """Tweaks this definition to take on the given new value.""" self.value = new_value if new_value is not None: assert isinstance(new_value, Value) def ref_str(self): """Gets a string that represents a reference to this definition.""" return '$%d' % self.index def __str__(self): return '$%d = %s' % (self.index, str(self.value)) class Instruction(object): """Represents an instruction.""" def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" raise NotImplementedError() def get_all_dependencies(self): """Gets all definitions and instructions on which this instruction depends, along with any dependencies of dependencies.""" results = list(self.get_dependencies()) for item in results: results.extend(item.get_all_dependencies()) return results class Branch(Instruction): """Represents a branch from one basic block to another.""" def __init__(self, block, arguments=None): self.block = block assert isinstance(block, BasicBlock) if arguments is None: arguments = [] self.arguments = arguments assert all([isinstance(arg, Definition) for arg in arguments]) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return self.arguments def __str__(self): return '!%d(%s)' % (self.block.index, ', '.join([arg.ref_str() for arg in self.arguments])) class FlowInstruction(Instruction): """Represents a control flow instruction which terminates a basic block.""" def branches(self): """Gets a list of basic blocks targeted by this flow instruction.""" raise NotImplementedError() class JumpFlow(FlowInstruction): """Represents a control flow instruction which jumps directly to a basic block.""" def __init__(self, branch): FlowInstruction.__init__(self) self.branch = branch assert isinstance(branch, Branch) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return self.branches() def branches(self): """Gets a list of basic blocks targeted by this flow instruction.""" return [self.branch] def __str__(self): return 'jump %s' % self.branch class SelectFlow(FlowInstruction): """Represents a control flow instruction which jumps to one of two basic blocks depending on whether a condition is truthy or not.""" def __init__(self, condition, if_branch, else_branch): FlowInstruction.__init__(self) self.condition = condition assert isinstance(condition, Definition) self.if_branch = if_branch assert isinstance(if_branch, Branch) self.else_branch = else_branch assert isinstance(else_branch, Branch) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [self.condition] + self.branches() def branches(self): """Gets a list of basic blocks targeted by this flow instruction.""" return [self.if_branch, self.else_branch] def __str__(self): return 'select %s, %s, %s' % (self.condition.ref_str(), self.if_branch, self.else_branch) class ReturnFlow(FlowInstruction): """Represents a control flow instruction which terminates the execution of the current function and returns a value.""" def __init__(self, value): FlowInstruction.__init__(self) self.value = value assert isinstance(value, Definition) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [self.value] def branches(self): """Gets a list of basic blocks targeted by this flow instruction.""" return [] def __str__(self): return 'return %s' % self.value.ref_str() class UnreachableFlow(FlowInstruction): """Represents a control flow instruction which is unreachable.""" def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def branches(self): """Gets a list of basic blocks targeted by this flow instruction.""" return [] def __str__(self): return 'unreachable' class Value(Instruction): """A value: an instruction that produces some result.""" def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" raise NotImplementedError() def has_value(self): """Tells if this value produces a result that is not None.""" return True def has_side_effects(self): """Tells if this instruction has side-effects.""" return False class BlockParameter(Value): """A basic block parameter.""" def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def __str__(self): return 'block-parameter' class FunctionParameter(Value): """A function parameter.""" def __init__(self, name): Value.__init__(self) self.name = name def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def __str__(self): return 'func-parameter %s' % self.name class Literal(Value): """A literal value.""" def __init__(self, literal): Value.__init__(self) self.literal = literal def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def has_value(self): """Tells if this value produces a result that is not None.""" return self.literal is not None def __str__(self): return 'literal %r' % self.literal class JitFunctionCall(Value): """A value that is the result of a function call.""" def __init__(self, target, argument_list): Value.__init__(self) assert isinstance(target, Definition) self.target = target assert all([isinstance(val, Definition) for _, val in argument_list]) self.argument_list = argument_list def has_side_effects(self): """Tells if this instruction has side-effects.""" return True def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [self.target] + [val for _, val in self.argument_list] def __str__(self): return 'call %s(%s)' % ( self.target.ref_str(), ', '.join(['%s=%s' % (key, val.ref_str()) for key, val in self.argument_list])) class AllocateRootNode(Value): """A value that produces a new root node. Typically used in function prologs.""" def __init__(self): Value.__init__(self) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def __str__(self): return 'alloc-root-node' class DeallocateRootNode(Value): """A value that deallocates a root node. Typically used in function epilogs.""" def __init__(self, root_node): Value.__init__(self) assert isinstance(root_node, Definition) self.root_node = root_node def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def __str__(self): return 'free-root-node %s' % self.root_node.ref_str() class DeclareLocal(Value): """A value that declares a local variable.""" def __init__(self, variable, root_node): Value.__init__(self) self.variable = variable self.root_node = root_node def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def has_value(self): """Tells if this value produces a result that is not None.""" return False def has_side_effects(self): """Tells if this instruction has side-effects.""" return True def __str__(self): return 'declare-local %s, %s' % (self.variable, self.root_node.ref_str()) class DeclareGlobal(Value): """A value that declares a global variable.""" def __init__(self, variable): Value.__init__(self) self.variable = variable def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def has_value(self): """Tells if this value produces a result that is not None.""" return False def has_side_effects(self): """Tells if this instruction has side-effects.""" return True def __str__(self): return 'declare-global %s' % self.variable.name class CheckLocalExists(Value): """A value that checks if a local value has been defined (yet).""" def __init__(self, variable): Value.__init__(self) self.variable = variable def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def __str__(self): return 'check-local-exists %s' % self.variable class ResolveLocal(Value): """A value that resolves a local as a pointer.""" def __init__(self, variable): Value.__init__(self) self.variable = variable def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def __str__(self): return 'resolve-local %s' % self.variable class ResolveGlobal(Value): """A value that resolves a global as a pointer.""" def __init__(self, variable): Value.__init__(self) self.variable = variable def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def __str__(self): return 'resolve-global %s' % self.variable.name class LoadPointer(Value): """A value that loads the value assigned to a pointer.""" def __init__(self, pointer): Value.__init__(self) self.pointer = pointer assert isinstance(pointer, Definition) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [self.pointer] def __str__(self): return 'load %s' % self.pointer.ref_str() class StoreAtPointer(Value): """A value that assigns a value to a pointer.""" def __init__(self, pointer, value): Value.__init__(self) self.pointer = pointer assert isinstance(pointer, Definition) self.value = value assert isinstance(value, Definition) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [self.pointer, self.value] def has_value(self): """Tells if this value produces a result that is not None.""" return False def has_side_effects(self): """Tells if this instruction has side-effects.""" return True def __str__(self): return 'store %s, %s' % (self.pointer.ref_str(), self.value.ref_str()) class Input(Value): """A value that pops a node from the input queue.""" def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [] def has_side_effects(self): """Tells if this instruction has side-effects.""" return True def __str__(self): return 'input' class Output(Value): """A value that pushes a node onto the output queue.""" def __init__(self, value): Value.__init__(self) self.value = value assert isinstance(value, Definition) def get_dependencies(self): """Gets all definitions and instructions on which this instruction depends.""" return [self.value] def has_value(self): """Tells if this value produces a result that is not None.""" return False def has_side_effects(self): """Tells if this instruction has side-effects.""" return True def __str__(self): return 'output %s' % self.value.ref_str() def create_jump(block, arguments=None): """Creates a jump to the given block with the given argument list.""" return JumpFlow(Branch(block, arguments))