Utility Graphviz-create.py. It looks at hydrogen.cfg files and creates graphviz (dot) output of var…

tools/graphviz-create.py

+#!/usr/bin/env python
+#
+# Copyright 2012 the V8 project authors. All rights reserved.
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+#     * Redistributions of source code must retain the above copyright
+#       notice, this list of conditions and the following disclaimer.
+#     * Redistributions in binary form must reproduce the above
+#       copyright notice, this list of conditions and the following
+#       disclaimer in the documentation and/or other materials provided
+#       with the distribution.
+#     * Neither the name of Google Inc. nor the names of its
+#       contributors may be used to endorse or promote products derived
+#       from this software without specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+import optparse
+import os
+from os.path import join
+import sys
+import shlex

[Jakob Kummerow, 2012/11/16 17:31:57]

nit: sort imports alphabetically please

[mvstanton, 2013/01/06 11:26:36]

Done.

+import collections
+import tempfile
+import subprocess
+import glob
+
+
+# Parse() returns:
+# a map of compilations (functions)
+#   each compilation has a map of phases, and a name
+#     each phase has a map of blocks, and a name
+#       each block has a map of locals, and a map of statements
+# functions, phases, blocks, statements
+#
+# The first statement of foo, in final phase
+# data["foo"]["Z_Code generation"]["B0"][0]
+#
+# a phase is the typical area of work. Offers
+# phase.visit_statements(visitor) - visit every statement in the phase
+# phase.visit_blocks(visitor)
+#
+# of course,
+# blocks.visit_statements(visitor)
+# blocks.visit_locals(visitor)
+#
+
+
+USAGE="""usage: %prog [OPTION]...
+
+Looks at a hydrogen cfg file and produces graphviz (ie, dot) output.
+Output is directed to stdout for further customization before creating
+a graph. 
+ 
+Examples:
+  # Run on the last function defined in the file, looking at the final 
+  # HIR
+  $ %prog > output.dot
+
+  # Create the graphic too, this time with HIR, all on one line
+  $ %prog --displayHIR | dot -Tpng > out.png
+
+  # Examine a different phase of compilation for the last function
+  # Output to the screen
+  $ %prog --phase="H_Redundant phi elimination" --displayHIR
+
+  # Create an html report of the last function, with all HIR
+  $ %prog --command="report"
+"""
+
+
+def OrderedDictionary():
+  return collections.OrderedDict()
+
+
+def die(inputobj,expected):

[Jakob Kummerow, 2012/11/16 17:31:57]

Looking at what this method does, shouldn't it be called ASSERT_EQ(expected,
actual)? In that case, why not use Python's builtin "assert" statement?

[mvstanton, 2013/01/06 11:26:36]

thx. I changed to use assert. I kept diemsg() as a way to spit out a formatted
message and end process.

+  if inputobj != expected:
+    print "Expected: %s Got: %s" % (inputobj, expected)
+    sys.exit(1)
+
+
+def diemsg(msg):
+  print "Unexpected error: %s" % msg
+  sys.exit(1)
+
+
+class Printer(object):
+  def __init__(self):
+    self.stream = sys.stdout
+
+  def CreateFile(self,filename):

[Jakob Kummerow, 2012/11/16 17:31:57]

Create/close pairs are brittle. The most robust way to work with files in Python
is to use with-blocks (which auto-close the file when they go out of scope),
e.g.:

with open(filename, "w") as f:
  f.write("stuff")

I think I'd remove the Printer class and just pass around opened file objects
that are created in such a with-statement. The code at use sites should be
almost identical.

[mvstanton, 2013/01/06 11:26:36]

Done.

+    self.stream = open(filename,"w+t")
+
+  def CloseFile(self):
+    self.stream.close()
+
+  def SetStream(self,newStream):
+    self.stream = newStream
+
+  def Print(self,string):
+    self.stream.write(string)
+
+  def PrintLine(self,string):
+    self.Print(string + "\n")
+
+
+class Block(object):
+  """A compilation block."""
+
+  def __init__(self, name, predecessors, successors):
+    self.name = name
+    self.predecessors = predecessors
+    self.successors = successors
+    self.hir = OrderedDictionary()
+    self.lir = OrderedDictionary()
+    self.locals = OrderedDictionary()
+
+  def GetName(self):
+    return self.name
+
+  def GetPredecessors(self):
+    return self.predecessors
+
+  def GetSuccessors(self):
+    return self.successors
+
+  def AddHIR(self,statement):
+    self.hir[len(self.hir)] = statement

[Jakob Kummerow, 2012/11/16 17:31:57]

self.hir.append(statement)

+
+  def GetHIRs(self):
+    return self.hir.values()
+
+  def AddLIR(self,statement):
+    self.lir[len(self.lir)] = statement
+
+  def GetLIRs(self):
+    return self.lir.values()
+
+  def visit(self,visitor):
+    """Visit every HIR statement in the block."""
+    for h in hir.values():
+      visitor(h)
+
+  def AddLocal(self,name,local):
+    self.locals[name] = local
+
+  def visit_locals(self,visitor):
+    for l in self.locals.values():
+      visitor(l)
+
+  def GetLocals(self):
+    return self.locals.values()
+
+  def __str__(self):
+    return "%s (pred: %d) (succ: %d)" % (
+      self.name,

[Jakob Kummerow, 2012/11/16 17:31:57]

4-space indentation when you break inside ()

[mvstanton, 2013/01/06 11:26:36]

Done.

+      len(self.predecessors),
+      len(self.successors))
+
+
+class Phase(object):
+  """A compilation phase."""
+
+  def __init__(self, name):
+    self.name = name
+    self.blocks = OrderedDictionary()
+
+  def GetName(self):
+    return self.name
+
+  def AddBlock(self,name,block):
+    self.blocks[name] = block
+
+  def GetBlocks(self):
+    return self.blocks.values()
+
+  def GetBlock(self,block):
+    return self.blocks[block]
+
+  def visit_statements(self,visitor):
+    for block in self.blocks:
+      block.visit(visitor)
+
+  def visit_blocks(self,visitor):
+    for block in self.blocks.values():
+      visitor(block)
+
+  def Print(self,printer):
+    printer.Print(self)
+    for block in self.blocks.values():
+      printer.Print(block)
+
+  def __str__(self):
+    return "%s (%d blocks)" % (
+      self.name,
+      len(self.blocks))
+
+      
+class Compilation(object):
+  """A compilation unit."""
+
+  def __init__(self, name, method):
+    self.phases = OrderedDictionary()
+    self.name = name
+    self.method = method
+
+  def AddPhase(self, name, phase):
+    self.phases[name] = phase
+
+  def AllPhases(self):
+    for phase in self.phases.itervalues():
+      yield phase
+
+  def AllPhaseNames(self):
+    return self.phases.keys()
+
+  def GetName(self):
+    return self.name
+
+  def GetPhase(self,phase):
+    return self.phases[phase]
+
+  def GetPreviousPhase(self,phase):
+    # useful for diffs
+    index = self.phases.keys().index(phase)
+    if index == 0:
+      diemsg("No previous phase of " + phase)
+    return self.phases[self.phases.keys()[index - 1]]
+
+  def Print(self,printer):
+    printer.PrintLine('Compilation ' + self.name)
+    for phase in self.AllPhases():
+      phase.Print()
+
+  def __str__(self):
+    return "%s (%d phases)" % (
+      self.name,
+      len(self.phases))
+
+
+def BuildOptions():
+  result = optparse.OptionParser(USAGE)
+  result.add_option("--input",
+                    help="Input file (default hydrogen.cfg)",

[Jakob Kummerow, 2012/11/16 17:31:57]

No need to type the default value twice:

help="Input file (default: %default)"

See http://docs.python.org/2/library/optparse.html#generating-help

[mvstanton, 2013/01/06 11:26:36]

Done.

+                    default="hydrogen.cfg")
+  result.add_option("--command",
+                    help="The command to run: 'diff','report','blocks' (default)",

[Jakob Kummerow, 2012/11/16 17:31:57]

nit: long line

[mvstanton, 2013/01/06 11:26:36]

Done.

+                    default="blocks")
+  result.add_option("--function",
+                    help="The function to analyze (default @last)",
+                    default="@last")
+  result.add_option("--phase",
+      help="The compilation phase to examine (default Z_Code generation)",
+      default="Z_Code generation")
+  result.add_option("--displayHIR",
+                    help="Display HIR in blocks? (default false)",
+                    default=False, action="store_true")
+  result.add_option("--displayLIR",
+                    help="Display LIR in blocks? (default false)",
+                    default=False, action="store_true")
+  result.add_option("-v", "--verbose", help="Verbose output",
+                    default=False, action="store_true")
+  result.add_option("-d", "--debug", help="Debug output",
+                    default=False, action="store_true")
+  return result
+
+
+def ProcessOptions(options):
+  if not options.command in ["blocks","diff","report"]:
+    print "Unknown command %s" % options.command
+    return False
+  return True
+
+
+def parseKeyString(line):
+  tokens = shlex.split(line.strip())
+  return tokens
+
+
+class CFGReader(object):
+  """CFG file reader."""
+
+  def __init__(self, filename):
+    self.file = open(filename, "r")
+    self.savedline = None
+
+  def Dispose(self):
+    self.log.close()
+    self.log_file.close()
+
+  def pushline(self,line):
+    self.savedline = line
+
+  def nextline(self):
+    # we can push one line back
+    if self.savedline:
+      s = self.savedline
+      self.savedline = None
+      return s
+
+    return self.file.readline()
+
+  def Parse(self):
+    """Return a map of compilation units."""
+    compilations = OrderedDictionary()
+    while True:
+      compilation = self.ParseCompilation()
+      if not compilation:
+        break
+      compilations[compilation.name] = compilation
+    return compilations
+
+  def ParseCompilation(self):
+    line = self.nextline()
+    if not line:
+      return None
+    die("begin_compilation",line.strip())
+    pair = parseKeyString(self.nextline())
+    die("name",pair[0])
+    name = pair[1]
+    compilation = Compilation(name,name)
+    # now read into configs
+    while line.strip() != "end_compilation":
+      line = self.nextline()
+      if not line:
+        diemsg("Unexpected end of file")
+
+    while True:
+      phase = self.ParsePhase()
+      if not phase:
+        break
+      compilation.AddPhase(phase.name,phase)
+    return compilation
+
+  def ParseHIRs(self,block):
+    while True:
+      line = self.nextline().strip()
+      if line == "end_HIR":
+        break
+      # we don't need the first number ("0 ") and some symbols at the end
+      line = line[2:]
+      line = line.replace("<|@","")
+      block.AddHIR(line)
+
+  def ParseLIRs(self,block):
+    while True:
+      line = self.nextline().strip()
+      if line == "end_LIR":
+        break
+      # we don't need some symbols at the end
+      line = line.replace("<|@","")
+      block.AddLIR(line)
+    
+  def ParseLocals(self,block):
+    while True:
+      line = self.nextline()
+      line = line.strip()
+      if line == "end_locals":
+        break
+      if len(line) > 0 and (line[0]>='0' and line[0]<='9'):
+        keys = parseKeyString(line)
+        block.AddLocal(keys[1],line)
+
+  def ParseBlock(self):
+    line = self.nextline()
+    if not line:
+      return None
+
+    if line.strip() != "begin_block":
+      self.pushline(line)
+      return None
+
+    die("begin_block",line.strip())
+    pair = parseKeyString(self.nextline())
+    die("name",pair[0])
+    name = pair[1]
+    # read pred and succ
+    while True:
+      line = self.nextline()
+      if line.strip() == "begin_states":
+        break;
+      pair = parseKeyString(line)
+      if pair[0] == "predecessors":
+        pred = pair[1:]
+      elif pair[0] == "successors":
+        succ = pair[1:]
+
+    block = Block(name,pred,succ)
+    # add hrs if found
+    while True:
+      line = self.nextline().strip()
+      if line == "end_block":
+        break;
+      elif line == "begin_locals":
+        self.ParseLocals(block)
+      elif line == "begin_LIR":
+        self.ParseLIRs(block)
+      elif line == "begin_HIR":
+        self.ParseHIRs(block)
+   
+    return block
+
+  def ParsePhase(self):
+    line = self.nextline()
+    if not line:
+      return None
+
+    if line.strip() != "begin_cfg":
+      self.pushline(line)
+      return None
+
+    die("begin_cfg",line.strip())
+    pair = parseKeyString(self.nextline())
+    die("name",pair[0])
+    name = pair[1]
+    phase = Phase(name)
+
+    while True:
+      block = self.ParseBlock()
+      if not block:
+        break
+      phase.AddBlock(block.name,block)
+
+    # just consume blocks
+    # consume the "end_cfg" message
+    die("end_cfg", self.nextline().strip())
+    return phase
+
+
+def DumpCompilations(compilations,printer):
+  printer.Print("len = %d" % len(compilations))
+  for comp in compilations.itervalues():
+    comp.Print(printer)
+
+
+def WriteTempFile(lines):
+  temp = tempfile.NamedTemporaryFile(mode="w+t")
+  for line in lines:
+    temp.write(line)
+    temp.write("\n")
+  temp.seek(0)
+  return temp
+
+
+def diffText(lines1,lines2):
+  """Takes two lists of text lines, creates a diff output of them as an array"""
+
+  try:
+    temp1 = WriteTempFile(lines1)
+    temp2 = WriteTempFile(lines2)
+    outputlines = []
+    cmdline = "diff -u %s %s" % (temp1.name, temp2.name)
+    process = subprocess.Popen(cmdline,
+                               shell=True, 
+                               stdout=subprocess.PIPE, 
+                               stderr=subprocess.STDOUT)
+    pipe = process.stdout
+    try:
+      headerLines = 2
+      lineCount = 0
+      for line in pipe:
+        if lineCount > headerLines:
+          # strip newline
+          outputlines.append(line.strip())
+        lineCount = lineCount + 1
+    except Exception as e:
+      diemsg("error in diff = " + str(e))
+    finally:
+      pipe.close()
+
+  finally:
+    temp1.close()
+    temp2.close()
+
+  return outputlines
+
+
+def Bold(line):
+  return "<b>%s</b>" % line
+
+
+def Color(color,line):
+  return "<font color=\"%s\">%s</font>" % (color,line)
+
+
+def LeftLineBreak():
+  return "<br align=\"left\"/>"
+
+
+def HtmlLikeEscape(line):
+  return line.replace("<","&lt;").replace(">","&gt;")
+
+
+def TableBegin():
+  return "<table border=\"0\" cellborder=\"1\" cellspacing=\"0\">\n"
+
+
+def TableEnd():
+  return "</table>\n"
+
+
+def NameRow(blockName):
+  return "<tr><td>%s</td></tr>\n" % Bold(blockName)
+
+
+def FormatLine(line):
+  tesc = HtmlLikeEscape(line)
+  # Deal with diff output
+  if tesc.startswith("-"):
+    tesc = Color("red",tesc)
+  elif tesc.startswith("+"):
+    tesc = Color("blue",tesc)
+  return "    %s%s\n" % (tesc, LeftLineBreak())
+
+
+def FormatLines(lineList):
+  result = ""
+  if len(lineList) > 0:
+    result += "<tr><td>\n"
+    for l in lineList:
+      result = result + FormatLine(l)
+    result = result + "</td></tr>\n"
+  return result
+
+
+def FormatLabel(blockName,localsList,hirList,lirList):
+  label = TableBegin()
+  label += NameRow(blockName)
+  label += FormatLines(localsList)
+  label += FormatLines(hirList)
+  label += FormatLines(lirList)
+  label += TableEnd()
+  return label
+
+
+def DotBlockVisit(displayHIR,displayLIR,p,block):
+  localsList = []
+  hirList = []
+  lirList = []
+

[Jakob Kummerow, 2012/11/16 17:31:57]

nit: one empty line is enough

[mvstanton, 2013/01/06 11:26:36]

Done.

+  
+  if displayHIR or displayLIR:
+    localsList = block.GetLocals()
+    if displayHIR:
+      hirList = block.GetHIRs()
+    if displayLIR:
+      lirList = block.GetLIRs()
+
+  label = FormatLabel(block.GetName(),localsList,hirList,lirList)
+  # extra newline for readability
+  label = "\n" + label
+  p.PrintLine("  block%s [shape=plaintext,label=<%s>];" 
+              % (block.GetName(), label))
+  for succ in block.GetSuccessors():
+    p.PrintLine("  block%s -> block%s;" % (block.GetName(), succ))
+
+
+def DotBlocks(functionName,phase,displayHIR,displayLIR,p):
+  """Diagram the blocks in the given function."""
+  p.PrintLine("digraph Blocks_%s {" % functionName)
+  p.PrintLine("  ratio = 1.0;")
+  phase.visit_blocks(lambda b: DotBlockVisit(displayHIR,displayLIR,p,b))
+  p.PrintLine("}")
+
+
+def DotDiffVisit(diffs,p,block):
+  label = FormatLabel(block.GetName(),[],diffs[block.GetName()],[])
+  p.PrintLine("  block%s [shape=plaintext,label=<%s>];" 
+              % (block.GetName(), label))
+  for succ in block.GetSuccessors():
+    p.PrintLine("  block%s -> block%s;" % (block.GetName(), succ))
+
+
+def DotDiff(functionName, phasePrev, phase, changedBlocksOnly, p):
+  """Run a diff block by block between two phases in the given function."""
+  p.PrintLine("// comparing phase %s with next phase %s" % (phasePrev.GetName(), 

[Jakob Kummerow, 2012/11/16 17:31:57]

nit: trailing whitespace

+                                                            phase.GetName()))
+  p.PrintLine("digraph Diff_%s {" % functionName)
+  p.PrintLine("  ratio = 1.0;")
+  # need to run diff -u phasePrev phase
+  # on the HIR output
+  # I think the # of blocks should be the same
+  diffResults = {} 
+  blocks = phasePrev.GetBlocks()
+  for blockPrev in blocks:
+    block = phase.GetBlock(blockPrev.GetName())
+    diffResults[blockPrev.GetName()] = diffText(blockPrev.GetHIRs(),
+                                                block.GetHIRs())
+
+  phasePrev.visit_blocks(lambda b: DotDiffVisit(diffResults,p,b))
+  p.PrintLine("}")
+
+
+reportText = """<html>

[Jakob Kummerow, 2012/11/16 17:31:57]

Why are these (constant) variables when Bold() etc. above were functions?

[mvstanton, 2013/01/06 11:26:36]

Good point. I got rid of the Bold() function, but I'd like to just keep this
html template as a big string for simplicity. The little functions to add
color/bold/etc., are for use when a function builds html from smaller elements.
This "reportText" variable might eventually go into another file, will things
like tooltips to explain the meaning of hydrogen instructions or things like
that.

+<title>Report on %s</title>
+<body>
+<h2>Block structure</h2>
+<a href=blocks.svg><img width=800 src=blocks.svg></a>
+<h2>All HIR</h2>
+<a href=hirblocks.svg><img width=800 src=hirblocks.svg></a>
+<h2>All LIR</h2>
+<a href=lirblocks.svg><img width=800 src=lirblocks.svg></a>
+<h2>Diffs</h2>
+%s
+</body>
+</html>"""
+
+
+diffsTemplate = """<h2>%s</h2>
+<a href=%s><img width=800 src=%s></a>"""
+
+
+def AsFilename(phaseName,ext):
+  phaseName = phaseName.replace(" ","_")
+  phaseName += ext
+  return phaseName
+
+
+def DotReport(function):
+  """Make a report on the function."""
+  escapedFunctionName = function.GetName().replace(".","_")
+  dirname = "report_%s" % escapedFunctionName
+  if not os.path.exists(dirname):
+    os.mkdir(dirname)

[Jakob Kummerow, 2012/11/16 17:31:57]

You probably want os.makedirs() here, which can also deal with subdirectories.

[mvstanton, 2013/01/06 11:26:36]

Done.

+
+  p = Printer()
+  htmlfilename = dirname + "/index.html"
+  print "Writing %s..." % htmlfilename
+  p.CreateFile(htmlfilename)
+  diffs = ""
+  phases = function.AllPhaseNames()
+  for ph in phases[1:]:
+    phfilename = AsFilename(ph,".svg")
+    diffs += diffsTemplate % (ph,phfilename,phfilename)
+  htmlText = reportText % (escapedFunctionName,diffs)
+  p.PrintLine(htmlText)
+  p.CloseFile()
+
+  # Write all dot files
+  # get last phase
+  phase = function.GetPhase(phases[-1])
+  p.CreateFile(dirname + "/blocks.dot")
+  DotBlocks(escapedFunctionName,phase,False,False,p)
+  p.CloseFile()
+
+  p.CreateFile(dirname + "/hirblocks.dot")
+  DotBlocks(escapedFunctionName,phase,True,False,p)
+  p.CloseFile()
+
+  p.CreateFile(dirname + "/lirblocks.dot")
+  DotBlocks(escapedFunctionName,phase,False,True,p)
+  p.CloseFile()
+  
+  print "Computing diffs..."
+
+  for ph in phases[1:]:
+    phase = function.GetPhase(ph)
+    phasePrev = function.GetPreviousPhase(ph)
+    p.CreateFile(dirname + "/" + AsFilename(ph,".dot"))
+    DotDiff(escapedFunctionName, phasePrev, phase, True, p)
+    p.CloseFile()
+
+  # Compile the dot files
+  cmdline = "dot -Tsvg %s > %s" 
+  # diff -u %s %s" % (temp1.name, temp2.name)
+  files = glob.glob(dirname + "/*.dot")
+  for f in files:
+    print "compiling " + f
+    process = subprocess.Popen(cmdline % (f,f.replace(".dot",".svg")),
+                               shell=True)
+    process.wait()
+  print "done"                          
+
+
+def Main():
+  p = Printer()
+
+  parser = BuildOptions()
+  (options, args) = parser.parse_args()
+  if not ProcessOptions(options):
+    parser.print_help()
+    return 1
+
+  exit_code = 0

[Jakob Kummerow, 2012/11/16 17:31:57]

Did you mean to overwrite this when some error occurs? I don't see any further
assignments.

[mvstanton, 2013/01/06 11:26:36]

Done.

+
+  # Open input file and parse compilations, phases, blocks
+  reader = CFGReader(options.input)
+  compilations = reader.Parse()
+
+  if options.debug:
+    DumpCompilations(compilations, p)
+
+  function = options.function
+  if function == "@last":
+    function = compilations.keys()[-1]
+  elif function == "@first":
+    function = compilations.keys()[0]
+  if options.verbose:
+    print "// dump function %s" % function
+
+  phase = options.phase
+
+  # find the method
+  if not function in compilations:
+    diemsg("function " + function + " not found in input file")
+
+  function = compilations[function]
+  # find the phase
+  phase = function.GetPhase(phase)
+
+  # now what we do depends on the command
+
+  escapedFunctionName = function.GetName().replace(".","_")
+  if options.command == "blocks":
+    DotBlocks(escapedFunctionName, phase, options.displayHIR, 
+              options.displayLIR, p)
+  elif options.command == "diff":
+    # take the phase and the preceding phase.
+    phasePrev = function.GetPreviousPhase(phase.GetName())
+    DotDiff(escapedFunctionName, phasePrev, phase, True, p)
+  elif options.command == "report":
+    DotReport(function)
+  return exit_code
+
+
+if __name__ == "__main__":
+  sys.exit(Main())