muis/basic_block.py

   1 """
   2 Contains functions and classes regarding basic blocks.
   3
   4 Code released under a free software compatible license. See LICENSE for more
   5 details.
   6 Original author: Nido Media
   7 Code patches by:
   8         ...
   9 """
  10
  11 import aliasdb
  12 import options
  13 import regex_support
  14 import registers
  15
  16 """
  17 basic_block attempts to be a structure for basic blocks. It will inherit all
  18 needed information from the instructions inserted.
  19 """
  20
  21 def print_block_list(blocks):
  22         """
  23         Prints the basic blocks in the basic block structure. Also prints the
  24         auxilary assembly code
  25         """
  26         for item in blocks:
  27                 print item
  28
  29 def test_block(instructions):
  30         """
  31         Create a new basic block with the given instructions. It omits other
  32         variables and is therefor not usefull outside of test functions.
  33         """
  34         block = basic_block("test", instructions,"jump",None,None)
  35         return block
  36
  37 def attach_previous(block_list):
  38         """This function takes a list of basic blocks and finds out which blocks are
  39         followed by the given block"""
  40         for block in block_list:
  41                 for exit in block.exit_points():
  42                         exit.preceding.append(block)
  43
  44 def reset_liveness(block_list):
  45         """ recalculates the liveness of all given basic blocks, taking following
  46         and previous blocks in account."""
  47         for block in block_list:
  48                 block.reset_liveness()
  49         changed = True
  50         while changed == True:
  51                 changed = update_liveness(block_list)
  52
  53 def get_block(block_list, string):
  54         """ takes the string representing a block name and returns a block with that
  55         name from the block_list. Returns None when nothing is found."""
  56         result = None
  57         for block in block_list:
  58                 if block.label == string:
  59                         result = block
  60         return result
  61
  62 def update_liveness(block_list):
  63         """Updates the given block_list and returns wether or not this update has
  64         changed anything. The idea is to keep updating until no changes happen."""
  65         changed = False
  66         for block in block_list:
  67                 # One caveat with this way of writing it down is that it doesn't quite
  68                 # resemble the fact update_dead and update_live actually change the
  69                 # block.
  70                 if block.update_dead(block_list):
  71                         changed = True
  72                 if block.update_live(block_list):
  73                         changed = True
  74         return changed
  75
  76
  77 class basic_block:
  78         def __init__(self, label, instructions, jump, branch, jal, block_list=None):
  79                 """ Creates a new basic block given the input values"""
  80                 self.label = label
  81                 self.instructions = instructions
  82                 self.jump = jump
  83                 self.branch = branch
  84                 self.jal = jal
  85                 self.preceding = []
  86                 self.constant_folding_registers = {}
  87
  88                 # Make sure liveness is correct (on this single block).
  89                 self.reset_liveness()
  90
  91                 # Make sure the block is correct
  92                 self.test_integrity()
  93
  94                 # The block_list is the block list to which this block belongs.
  95                 self.block_list = block_list
  96
  97                 # The label can be used as alias for load instructions
  98                 aliasdb.alias(label)
  99
 100         def update_live(self, block_list):
 101                 """Updates the liveness of this block with respect to following blocks."""
 102                 changed = False
 103                 for follower in self.get_exit_points():
 104                         if follower == "$31":
 105                                 for register in registers.jal_return_live:
 106                                         if register not in self.live:
 107                                                 self.live.append(register)
 108                                                 changed = True
 109                         else:
 110                                 for register in follower.live:
 111                                         if register not in self.live:
 112                                                 self.live.append(register)
 113                                                 changed = True
 114                 return changed
 115
 116         def update_dead(self, block_list):
 117                 """Tries to update its own dead register information according to the
 118                 information in following blocks."""
 119                 changed = False
 120                 # Create the list of potential dead registers
 121                 new_dead = []
 122                 for register in registers.all:
 123                         if register not in self.live:
 124                                 new_dead.append(register)
 125                 # Update the list to remove nondead registers
 126                 for follower in self.get_exit_points():
 127                         if follower == "$31":
 128                                 follower = registers.jal_return()
 129                         for register in new_dead:
 130                                 if register not in follower.dead:
 131                                         new_dead.remove(register)
 132                 # Update the internal list
 133                 for register in new_dead:
 134                         if register not in self.dead:
 135                                 self.dead.append(register)
 136                                 changed = True
 137                 # return wether or not something changed
 138                 return changed
 139
 140         def reset_liveness(self):
 141                 """Resets the live and dead fields in the basic block. Beware that this
 142                 resets the liveness according to this block alone. It does not take into
 143                 account following blocks."""
 144                 live_dict = self.liveness()
 145                 self.live = live_dict['live']
 146                 self.dead = live_dict['dead']
 147
 148         def get_exit_points(self):
 149                 """ Returns a list of exit points (basic blocks that are followed by
 150                 this one. This does not include the Jump And Link exit point if it is
 151                 there."""
 152                 labels = []
 153                 if self.jump:
 154                         labels.append(self.jump)
 155                 if self.branch:
 156                         labels.append(self.get_branch_jumppoint())
 157                 exits = []
 158                 for label in labels:
 159                         if label == "$31":
 160                                 # Special case: $31 is 'return' from JAL
 161                                 exits.append("$31")
 162                         else:
 163                                 exits.append(get_block(self.block_list, label))
 164                 return exits
 165
 166         def get_branch_reads(self):
 167                 """ Returns the registers read by this branch instruction."""
 168                 if not self.branch:
 169                         print sys.stderr, "NO BRANCH, YOU IDIOT!"
 170                         return None
 171                 arguments = self.branch[1].split(",")
 172                 # split off the last argument, as it is the jump point
 173                 registers = arguments[:-1]
 174                 # take out excess whitespace
 175                 for x in xrange(len(registers)):
 176                         registers[x] = registers[x].strip()
 177                 return registers
 178
 179         def get_branch_jumppoint(self):
 180                 """ Returns the name of the location where this branch will jump to."""
 181                 if not self.branch:
 182                         return None
 183
 184                 arguments = self.branch[1]
 185                 match = regex_support.branch_jumppoint_matcher.match(arguments)
 186                 if match == None:
 187                         import sys
 188                         print >> sys.stderr, arguments
 189                         print >> sys.stderr, self.branch[0]
 190                 return match.group('name')
 191
 192         def liveness(self):
 193                 """Returns a dictionary. This dictionary contains a list of 'live'
 194                 registers, which is a list of registers which are being read by this basic block before
 195                 they are being written, and a list of 'dead' registers, which are the the registers
 196                 being written before being read. The validity of the liveness is at the
 197                 beginning of the function. As such, it should not be used within the
 198                 function itself.
 199
 200                 This function takes into account the 'agressive' option invocation. If
 201                 set, it is assumed some registers are dead and some are live if this
 202                 block has a Jump And Link. Otherwise, all registers are assumed to be live.
 203                 """
 204                 dict = { "live": [], "dead": [] }
 205                 if self.instructions:
 206                         for inst in self.instructions:
 207                                 for register in inst.read:
 208                                         if register not in dict["dead"]:
 209                                                 dict["live"].append(register)
 210                                 for register in inst.write:
 211                                         if register not in dict["live"]:
 212                                                 dict["dead"].append(register)
 213
 214                 if self.jal:
 215                         jal_dict = registers.jal_liveness()
 216                         # The following are interchangable, no register from the jal__registers
 217                         # is both dead and alive at the same time.
 218                         for register in jal_dict['dead']:
 219                                 if register not in dict['live']:
 220                                         dict['dead'].append(register)
 221                         for register in jal_dict['live']:
 222                                 if register not in dict['dead']:
 223                                         dict['live'].append(register)
 224
 225                 return dict
 226
 227
 228         def test_integrity(self):
 229                 """
 230                 Tests wether this basic block is okay or if it violates a basic block
 231                 rule. Returns True if the block is valid, will exit with an assert if
 232                 invalid. If the asserts are turned off somehow, it returns false.
 233                 """
 234                 result = True
 235                 if self.jal and self.branch:
 236                         assert False, "JAL and branch cannot be in the same basic block"
 237                         result = False
 238                 if not self.jump:
 239                         if self.jump != "":
 240                                 assert False, "Basic block has no jump instruction"
 241                                 result = False
 242                 if not self.label:
 243                         assert False, "The block has no name. It should have a name"
 244                 return result
 245
 246         def __str__(self):
 247                 """
 248                 Returns a crude string representation of the Basic Block
 249                 """
 250                 result = "Basic_block " + self.label + "\n"
 251                 if self.instructions == None:
 252                         result += "No Instructions\n"
 253                 else:
 254                         result += "Instructions\n"
 255                         for instruction in self.instructions:
 256                                 result += "\t" + instruction.__str__() + "\n"
 257
 258                 if self.jal:
 259                         result += "Jump And Link: " + self.jal + "\n"
 260                 if self.branch:
 261                         result += "Branches: " + self.branch + "\n"
 262                 if self.jump:
 263                         result += "Jumps: " + self.jump + "\n"
 264                 return result
 265
 266 # vim:nocindent:nosmartindent:autoindent:tabstop=4:shiftwidth=4
 267 # vim:textwidth=80:foldmethod=indent:foldlevel=0