parameters: (self, merge_class=startopen_class)
docstring: Create the program dependency graph.
docstring_summary: Create the program dependency graph.
docstring_tokens: Create the program dependency graph .
function: def dependency_graph(self, merge_class=startopen_class):
          """ Create the program dependency graph. """
          block = self.block
          options = self.options
          open_nodes = set()
          self.open_nodes = open_nodes
          self.input_nodes = []
          colordict = defaultdict(lambda: 'gray', startopen='red', stopopen='red',\
                                  ldi='lightblue', ldm='lightblue', stm='blue',\
                                  mov='yellow', mulm='orange', mulc='orange',\
                                  triple='green', square='green', bit='green',\
                                  asm_input='lightgreen')
  
          G = Compiler.graph.SparseDiGraph(len(block.instructions))
          self.G = G
  
          reg_nodes = {}
          last_def = defaultdict(lambda: -1)
          last_mem_write = []
          last_mem_read = []
          warned_about_mem = []
          last_mem_write_of = defaultdict(list)
          last_mem_read_of = defaultdict(list)
          last_print_str = None
          last = defaultdict(lambda: defaultdict(lambda: None))
          last_open = deque()
  
          depths = [0] * len(block.instructions)
          self.depths = depths
          parallel_open = defaultdict(lambda: 0)
          next_available_depth = {}
          self.sources = []
          self.real_depths = [0] * len(block.instructions)
  
          def add_edge(i, j):
              from_merge = isinstance(block.instructions[i], merge_class)
              to_merge = isinstance(block.instructions[j], merge_class)
              G.add_edge(i, j)
              is_source = G.get_attr(i, 'is_source') and G.get_attr(j, 'is_source') and not from_merge
              G.set_attr(j, 'is_source', is_source)
              for d in (self.depths, self.real_depths):
                  if d[j] < d[i]:
                      d[j] = d[i]
  
          def read(reg, n):
              if last_def[reg] != -1:
                  add_edge(last_def[reg], n)
  
          def write(reg, n):
              last_def[reg] = n
  
          def handle_mem_access(addr, reg_type, last_access_this_kind,
                                last_access_other_kind):
              this = last_access_this_kind[addr,reg_type]
              other = last_access_other_kind[addr,reg_type]
              if this and other:
                  if this[-1] < other[0]:
                      del this[:]
              this.append(n)
              for inst in other:
                  add_edge(inst, n)
  
          def mem_access(n, instr, last_access_this_kind, last_access_other_kind):
              addr = instr.args[1]
              reg_type = instr.args[0].reg_type
              if isinstance(addr, int):
                  for i in range(min(instr.get_size(), 100)):
                      addr_i = addr + i
                      handle_mem_access(addr_i, reg_type, last_access_this_kind,
                                        last_access_other_kind)
                  if not warned_about_mem and (instr.get_size() > 100):
                      print 'WARNING: Order of memory instructions ' \
                          'not preserved due to long vector, errors possible'
                      warned_about_mem.append(True)
              else:
                  handle_mem_access(addr, reg_type, last_access_this_kind,
                                    last_access_other_kind)
              if not warned_about_mem and not isinstance(instr, DirectMemoryInstruction):
                  print 'WARNING: Order of memory instructions ' \
                      'not preserved, errors possible'
                  # hack
                  warned_about_mem.append(True)
  
          def keep_order(instr, n, t, arg_index=None):
              if arg_index is None:
                  player = None
              else:
                  player = instr.args[arg_index]
              if last[t][player] is not None:
                  add_edge(last[t][player], n)
              last[t][player] = n
  
          for n,instr in enumerate(block.instructions):
              outputs,inputs = instr.get_def(), instr.get_used()
  
              G.add_node(n, is_source=True)
  
              # if options.debug:
              #     col = colordict[instr.__class__.__name__]
              #     G.add_node(n, color=col, label=str(instr))
              for reg in inputs:
                  if reg.vector and instr.is_vec():
                      for i in reg.vector:
                          read(i, n)
                  else:
                      read(reg, n)
  
              for reg in outputs:
                  if reg.vector and instr.is_vec():
                      for i in reg.vector:
                          write(i, n)
                  else:
                      write(reg, n)
  
              if isinstance(instr, merge_class):
                  open_nodes.add(n)
                  last_open.append(n)
                  G.add_node(n, merges=[])
                  # the following must happen after adding the edge
                  self.real_depths[n] += 1
                  depth = depths[n] + 1
                  if int(options.max_parallel_open):
                      skipped_depths = set()
                      while parallel_open[depth] >= int(options.max_parallel_open):
                          skipped_depths.add(depth)
                          depth = next_available_depth.get(depth, depth + 1)
                      for d in skipped_depths:
                          next_available_depth[d] = depth
                  parallel_open[depth] += len(instr.args) * instr.get_size()
                  depths[n] = depth
  
              if isinstance(instr, stopopen_class):
                  startopen = last_open.popleft()
                  add_edge(startopen, n)
                  G.set_attr(startopen, 'stop', n)
                  G.set_attr(n, 'start', last_open)
                  G.add_node(n, merges=[])
  
              if isinstance(instr, ReadMemoryInstruction):
                  if options.preserve_mem_order:
                      if last_mem_write and last_mem_read and last_mem_write[-1] > last_mem_read[-1]:
                          last_mem_read[:] = []
                      last_mem_read.append(n)
                      for i in last_mem_write:
                          add_edge(i, n)
                  else:
                      mem_access(n, instr, last_mem_read_of, last_mem_write_of)
              elif isinstance(instr, WriteMemoryInstruction):
                  if options.preserve_mem_order:
                      if last_mem_write and last_mem_read and last_mem_write[-1] < last_mem_read[-1]:
                          last_mem_write[:] = []
                      last_mem_write.append(n)
                      for i in last_mem_read:
                          add_edge(i, n)
                  else:
                      mem_access(n, instr, last_mem_write_of, last_mem_read_of)
              # keep I/O instructions in order
              elif isinstance(instr, IOInstruction):
                  if last_print_str is not None:
                      add_edge(last_print_str, n)
                  last_print_str = n
              elif isinstance(instr, PublicFileIOInstruction):
                  keep_order(instr, n, instr.__class__)
              elif isinstance(instr, RawInputInstruction):
                  keep_order(instr, n, instr.__class__, 0)
                  self.input_nodes.append(n)
                  G.add_node(n, merges=[])
                  player = instr.args[0]
                  if isinstance(instr, stopinput):
                      add_edge(last[startinput_class][player], n)
                  elif isinstance(instr, gstopinput):
                      add_edge(last[gstartinput][player], n)
              elif isinstance(instr, startprivateoutput_class):
                  keep_order(instr, n, startprivateoutput_class, 2)
              elif isinstance(instr, stopprivateoutput_class):
                  keep_order(instr, n, stopprivateoutput_class, 1)
              elif isinstance(instr, prep_class):
                  keep_order(instr, n, instr.args[0])
              elif isinstance(instr, StackInstruction):
                  keep_order(instr, n, StackInstruction)
  
              if not G.pred[n]:
                  self.sources.append(n)
  
              if n % 100000 == 0 and n > 0:
                  print "Processed dependency of %d/%d instructions at" % \
                      (n, len(block.instructions)), time.asctime()
  
          if len(open_nodes) > 1000:
              print "Program has %d %s instructions" % (len(open_nodes), merge_class)
function_tokens: def dependency_graph ( self , merge_class = startopen_class ) : block = self . block options = self . options open_nodes = set ( ) self . open_nodes = open_nodes self . input_nodes = [ ] colordict = defaultdict ( lambda : 'gray' , startopen = 'red' , stopopen = 'red' , ldi = 'lightblue' , ldm = 'lightblue' , stm = 'blue' , mov = 'yellow' , mulm = 'orange' , mulc = 'orange' , triple = 'green' , square = 'green' , bit = 'green' , asm_input = 'lightgreen' ) G = Compiler . graph . SparseDiGraph ( len ( block . instructions ) ) self . G = G reg_nodes = { } last_def = defaultdict ( lambda : - 1 ) last_mem_write = [ ] last_mem_read = [ ] warned_about_mem = [ ] last_mem_write_of = defaultdict ( list ) last_mem_read_of = defaultdict ( list ) last_print_str = None last = defaultdict ( lambda : defaultdict ( lambda : None ) ) last_open = deque ( ) depths = [ 0 ] * len ( block . instructions ) self . depths = depths parallel_open = defaultdict ( lambda : 0 ) next_available_depth = { } self . sources = [ ] self . real_depths = [ 0 ] * len ( block . instructions ) def add_edge ( i , j ) : from_merge = isinstance ( block . instructions [ i ] , merge_class ) to_merge = isinstance ( block . instructions [ j ] , merge_class ) G . add_edge ( i , j ) is_source = G . get_attr ( i , 'is_source' ) and G . get_attr ( j , 'is_source' ) and not from_merge G . set_attr ( j , 'is_source' , is_source ) for d in ( self . depths , self . real_depths ) : if d [ j ] < d [ i ] : d [ j ] = d [ i ] def read ( reg , n ) : if last_def [ reg ] != - 1 : add_edge ( last_def [ reg ] , n ) def write ( reg , n ) : last_def [ reg ] = n def handle_mem_access ( addr , reg_type , last_access_this_kind , last_access_other_kind ) : this = last_access_this_kind [ addr , reg_type ] other = last_access_other_kind [ addr , reg_type ] if this and other : if this [ - 1 ] < other [ 0 ] : del this [ : ] this . append ( n ) for inst in other : add_edge ( inst , n ) def mem_access ( n , instr , last_access_this_kind , last_access_other_kind ) : addr = instr . args [ 1 ] reg_type = instr . args [ 0 ] . reg_type if isinstance ( addr , int ) : for i in range ( min ( instr . get_size ( ) , 100 ) ) : addr_i = addr + i handle_mem_access ( addr_i , reg_type , last_access_this_kind , last_access_other_kind ) if not warned_about_mem and ( instr . get_size ( ) > 100 ) : print 'WARNING: Order of memory instructions ' 'not preserved due to long vector, errors possible' warned_about_mem . append ( True ) else : handle_mem_access ( addr , reg_type , last_access_this_kind , last_access_other_kind ) if not warned_about_mem and not isinstance ( instr , DirectMemoryInstruction ) : print 'WARNING: Order of memory instructions ' 'not preserved, errors possible' # hack warned_about_mem . append ( True ) def keep_order ( instr , n , t , arg_index = None ) : if arg_index is None : player = None else : player = instr . args [ arg_index ] if last [ t ] [ player ] is not None : add_edge ( last [ t ] [ player ] , n ) last [ t ] [ player ] = n for n , instr in enumerate ( block . instructions ) : outputs , inputs = instr . get_def ( ) , instr . get_used ( ) G . add_node ( n , is_source = True ) # if options.debug: #     col = colordict[instr.__class__.__name__] #     G.add_node(n, color=col, label=str(instr)) for reg in inputs : if reg . vector and instr . is_vec ( ) : for i in reg . vector : read ( i , n ) else : read ( reg , n ) for reg in outputs : if reg . vector and instr . is_vec ( ) : for i in reg . vector : write ( i , n ) else : write ( reg , n ) if isinstance ( instr , merge_class ) : open_nodes . add ( n ) last_open . append ( n ) G . add_node ( n , merges = [ ] ) # the following must happen after adding the edge self . real_depths [ n ] += 1 depth = depths [ n ] + 1 if int ( options . max_parallel_open ) : skipped_depths = set ( ) while parallel_open [ depth ] >= int ( options . max_parallel_open ) : skipped_depths . add ( depth ) depth = next_available_depth . get ( depth , depth + 1 ) for d in skipped_depths : next_available_depth [ d ] = depth parallel_open [ depth ] += len ( instr . args ) * instr . get_size ( ) depths [ n ] = depth if isinstance ( instr , stopopen_class ) : startopen = last_open . popleft ( ) add_edge ( startopen , n ) G . set_attr ( startopen , 'stop' , n ) G . set_attr ( n , 'start' , last_open ) G . add_node ( n , merges = [ ] ) if isinstance ( instr , ReadMemoryInstruction ) : if options . preserve_mem_order : if last_mem_write and last_mem_read and last_mem_write [ - 1 ] > last_mem_read [ - 1 ] : last_mem_read [ : ] = [ ] last_mem_read . append ( n ) for i in last_mem_write : add_edge ( i , n ) else : mem_access ( n , instr , last_mem_read_of , last_mem_write_of ) elif isinstance ( instr , WriteMemoryInstruction ) : if options . preserve_mem_order : if last_mem_write and last_mem_read and last_mem_write [ - 1 ] < last_mem_read [ - 1 ] : last_mem_write [ : ] = [ ] last_mem_write . append ( n ) for i in last_mem_read : add_edge ( i , n ) else : mem_access ( n , instr , last_mem_write_of , last_mem_read_of ) # keep I/O instructions in order elif isinstance ( instr , IOInstruction ) : if last_print_str is not None : add_edge ( last_print_str , n ) last_print_str = n elif isinstance ( instr , PublicFileIOInstruction ) : keep_order ( instr , n , instr . __class__ ) elif isinstance ( instr , RawInputInstruction ) : keep_order ( instr , n , instr . __class__ , 0 ) self . input_nodes . append ( n ) G . add_node ( n , merges = [ ] ) player = instr . args [ 0 ] if isinstance ( instr , stopinput ) : add_edge ( last [ startinput_class ] [ player ] , n ) elif isinstance ( instr , gstopinput ) : add_edge ( last [ gstartinput ] [ player ] , n ) elif isinstance ( instr , startprivateoutput_class ) : keep_order ( instr , n , startprivateoutput_class , 2 ) elif isinstance ( instr , stopprivateoutput_class ) : keep_order ( instr , n , stopprivateoutput_class , 1 ) elif isinstance ( instr , prep_class ) : keep_order ( instr , n , instr . args [ 0 ] ) elif isinstance ( instr , StackInstruction ) : keep_order ( instr , n , StackInstruction ) if not G . pred [ n ] : self . sources . append ( n ) if n % 100000 == 0 and n > 0 : print "Processed dependency of %d/%d instructions at" % ( n , len ( block . instructions ) ) , time . asctime ( ) if len ( open_nodes ) > 1000 : print "Program has %d %s instructions" % ( len ( open_nodes ) , merge_class )