from statement import Block class BasicBlock(Block): def __init__(self, statements=[]): Block.__init__(self, statements) self.edges_to = [] self.edges_from = [] self.dominates = [] self.dominated_by = [] def add_edge_to(self, block): if block not in self.edges_to: self.edges_to.append(block) block.edges_from.append(self) def set_dominates(self, block): if block not in self.dominates: self.dominates.append(block) block.dominated_by.append(self) def find_leaders(statements): """Determine the leaders, which are: 1. The first statement. 2. Any statement that is the target of a jump. 3. Any statement that follows directly follows a jump.""" leaders = [0] jump_target_labels = [] # Append statements following jumps and save jump target labels for i, statement in enumerate(statements[1:]): if statement.is_jump(): leaders.append(i + 2) jump_target_labels.append(statement[-1]) # Append jump targets for i, statement in enumerate(statements[1:]): if i + 1 not in leaders \ and statement.is_label() \ and statement.name in jump_target_labels: leaders.append(i + 1) leaders.sort() return leaders def find_basic_blocks(statements): """Divide a statement list into basic blocks. Returns a list of basic blocks, which are also statement lists.""" leaders = find_leaders(statements) blocks = [] for i in range(len(leaders) - 1): blocks.append(BasicBlock(statements[leaders[i]:leaders[i + 1]])) blocks.append(BasicBlock(statements[leaders[-1]:])) return blocks def generate_flow_graph(blocks): """Add flow graph edge administration of an ordered sequence of basic blocks.""" for i, b in enumerate(blocks): last_statement = b[-1] if last_statement.is_jump(): target = last_statement.jump_target() # Compare the target to all leading labels, add an edge if the # label matches the jump target for other in blocks: if other[0].is_label(target): b.add_edge_to(other) # A branch and jump-and-line instruction also creates an edge to # the next block if (last_statement.is_branch() or last_statement.name == 'jal') \ and i < len(blocks) - 1: b.add_edge_to(blocks[i + 1]) elif i < len(blocks) - 1: b.add_edge_to(blocks[i + 1])