Added trace tree visualizer (bug 506714, r=gal).
authorDavid Anderson <danderson@mozilla.com>
Wed, 19 Aug 2009 16:11:59 -0700
changeset 31903 427326d92dfbe6d9cda5004eaade7253ffe13b94
parent 31902 0b47a120e4e11260f76afd618da474f45cbcec6f
child 31904 c7b5f61928098fad9c0dcf520ea01644c81e8a07
push idunknown
push userunknown
push dateunknown
reviewersgal
bugs506714
milestone1.9.3a1pre
Added trace tree visualizer (bug 506714, r=gal).
js/src/jstracer.cpp
js/src/jstracer.h
js/src/tracevis/tree.py
--- a/js/src/jstracer.cpp
+++ b/js/src/jstracer.cpp
@@ -357,16 +357,17 @@ InitJITLogController()
     /* flags for jstracer.cpp */
     if (strstr(tmf, "minimal"))     bits |= LC_TMMinimal;
     if (strstr(tmf, "tracer"))      bits |= LC_TMTracer;
     if (strstr(tmf, "recorder"))    bits |= LC_TMRecorder;
     if (strstr(tmf, "patcher"))     bits |= LC_TMPatcher;
     if (strstr(tmf, "abort"))       bits |= LC_TMAbort;
     if (strstr(tmf, "stats"))       bits |= LC_TMStats;
     if (strstr(tmf, "regexp"))      bits |= LC_TMRegexp;
+    if (strstr(tmf, "treevis"))     bits |= LC_TMTreeVis;
 
     /* flags for nanojit */
     if (strstr(tmf, "liveness"))    bits |= LC_Liveness;
     if (strstr(tmf, "readlir"))     bits |= LC_ReadLIR;
     if (strstr(tmf, "aftersf_sp"))  bits |= LC_AfterSF_SP;
     if (strstr(tmf, "aftersf_rp"))  bits |= LC_AfterSF_RP;
     if (strstr(tmf, "regalloc"))    bits |= LC_RegAlloc;
     if (strstr(tmf, "assembly"))    bits |= LC_Assembly;
@@ -395,16 +396,17 @@ InitJITLogController()
     printf("   minimal      ultra-minimalist output; try this first\n");
     printf("   full         everything (old verbosity)\n");
     printf("   tracer       tracer lifetime (FIXME:better description)\n");
     printf("   recorder     trace recording stuff (FIXME:better description)\n");
     printf("   patcher      patching stuff (FIXME:better description)\n");
     printf("   abort        show trace recording aborts\n");
     printf("   stats        show trace recording stats\n");
     printf("   regexp       show compilation & entry for regexps\n");
+    printf("   treevis      spew that tracevis/tree.py can parse\n");  
     printf("   ------ options for Nanojit ------\n");
     printf("   liveness     show LIR liveness at start of rdr pipeline\n");
     printf("   readlir      show LIR as it enters the reader pipeline\n");
     printf("   aftersf_sp   show LIR after StackFilter(sp)\n");
     printf("   aftersf_rp   show LIR after StackFilter(rp)\n");
     printf("   regalloc     show regalloc details\n");
     printf("   assembly     show final aggregated assembly code\n");
     printf("   nocodeaddrs  don't show code addresses in assembly listings\n");
@@ -1711,16 +1713,17 @@ TraceRecorder::TraceRecorder(JSContext* 
 
 #ifdef JS_JIT_SPEW
     debug_only_print0(LC_TMMinimal, "\n");
     debug_only_printf(LC_TMMinimal, "Recording starting from %s:%u@%u\n",
                       ti->treeFileName, ti->treeLineNumber, ti->treePCOffset);
 
     debug_only_printf(LC_TMTracer, "globalObj=%p, shape=%d\n",
                       (void*)this->globalObj, OBJ_SHAPE(this->globalObj));
+    debug_only_printf(LC_TMTreeVis, "TREEVIS RECORD FRAG=%p ANCHOR=%p\n", fragment, anchor);
 
     /* Set up jitstats so that trace-test.js can determine which architecture
      * we're running on. */
     jitstats.archIsIA32 = 0;
     jitstats.archIsAMD64 = 0;
     jitstats.archIs64BIT = 0;
     jitstats.archIsARM = 0;
     jitstats.archIsSPARC = 0;
@@ -3218,16 +3221,34 @@ public:
     }
 
     JSTraceType* getTypeMap()
     {
         return mTypeMap;
     }
 };
 
+#if defined JS_JIT_SPEW
+JS_REQUIRES_STACK static void
+TreevisLogExit(JSContext* cx, VMSideExit* exit)
+{
+    debug_only_printf(LC_TMTreeVis, "TREEVIS ADDEXIT EXIT=%p TYPE=%s FRAG=%p PC=%p FILE=\"%s\""
+                      " LINE=%d OFFS=%d", exit, getExitName(exit->exitType), exit->from,
+                      cx->fp->regs->pc, cx->fp->script->filename,
+                      js_FramePCToLineNumber(cx, cx->fp), FramePCOffset(cx->fp));
+    debug_only_print0(LC_TMTreeVis, " STACK=\"");
+    for (unsigned i = 0; i < exit->numStackSlots; i++)
+        debug_only_printf(LC_TMTreeVis, "%c", typeChar[exit->stackTypeMap()[i]]);
+    debug_only_print0(LC_TMTreeVis, "\" GLOBALS=\"");
+    for (unsigned i = 0; i < exit->numGlobalSlots; i++)
+        debug_only_printf(LC_TMTreeVis, "%c", typeChar[exit->globalTypeMap()[i]]);
+    debug_only_print0(LC_TMTreeVis, "\"\n");
+}
+#endif
+
 JS_REQUIRES_STACK VMSideExit*
 TraceRecorder::snapshot(ExitType exitType)
 {
     JSStackFrame* fp = cx->fp;
     JSFrameRegs* regs = fp->regs;
     jsbytecode* pc = regs->pc;
 
     /*
@@ -3321,16 +3342,19 @@ TraceRecorder::snapshot(ExitType exitTyp
     unsigned nexits = treeInfo->sideExits.length();
     if (exitType == LOOP_EXIT) {
         for (unsigned n = 0; n < nexits; ++n) {
             VMSideExit* e = exits[n];
             if (e->pc == pc && e->imacpc == fp->imacpc &&
                 ngslots == e->numGlobalSlots &&
                 !memcmp(exits[n]->fullTypeMap(), typemap, typemap_size)) {
                 AUDIT(mergedLoopExits);
+#if defined JS_JIT_SPEW
+                TreevisLogExit(cx, e);
+#endif
                 JS_ARENA_RELEASE(&cx->tempPool, mark);
                 return e;
             }
         }
     }
 
     if (sizeof(VMSideExit) + (stackSlots + ngslots) * sizeof(JSTraceType) >
         LirBuffer::MAX_SKIP_PAYLOAD_SZB) {
@@ -3368,16 +3392,20 @@ TraceRecorder::snapshot(ExitType exitTyp
     exit->pc = pc;
     exit->imacpc = fp->imacpc;
     exit->sp_adj = (stackSlots * sizeof(double)) - treeInfo->nativeStackBase;
     exit->rp_adj = exit->calldepth * sizeof(FrameInfo*);
     exit->nativeCalleeWord = 0;
     exit->lookupFlags = js_InferFlags(cx, 0);
     memcpy(exit->fullTypeMap(), typemap, typemap_size);
 
+#if defined JS_JIT_SPEW
+    TreevisLogExit(cx, exit);
+#endif
+
     JS_ARENA_RELEASE(&cx->tempPool, mark);
     return exit;
 }
 
 JS_REQUIRES_STACK LIns*
 TraceRecorder::createGuardRecord(VMSideExit* exit)
 {
     LIns* guardRec = lir->insSkip(sizeof(GuardRecord));
@@ -3442,16 +3470,17 @@ TraceRecorder::copy(VMSideExit* copy)
     /*
      * BIG FAT WARNING: If compilation fails we don't reset the lirbuf, so it's
      * safe to keep references to the side exits here. If we ever start
      * clearing those lirbufs, we have to make sure we purge the side exits
      * that then no longer will be in valid memory.
      */
     if (exit->exitType == LOOP_EXIT)
         treeInfo->sideExits.add(exit);
+    TreevisLogExit(cx, exit);
     return exit;
 }
 
 /*
  * Emit a guard for condition (cond), expecting to evaluate to boolean result
  * (expected) and generate a side exit with type exitType to jump to if the
  * condition does not hold.
  */
@@ -3571,16 +3600,18 @@ TraceRecorder::compile(JSTraceMonitor* t
 }
 
 static void
 JoinPeers(Assembler* assm, VMSideExit* exit, VMFragment* target)
 {
     exit->target = target;
     assm->patch(exit);
 
+    debug_only_printf(LC_TMTreeVis, "TREEVIS JOIN ANCHOR=%p FRAG=%p\n", exit, target);
+
     if (exit->root() == target)
         return;
 
     target->getTreeInfo()->dependentTrees.addUnique(exit->root());
     exit->root()->getTreeInfo()->linkedTrees.addUnique(target);
 }
 
 /* Results of trying to connect an arbitrary type A with arbitrary type B */
@@ -3893,25 +3924,30 @@ TraceRecorder::closeLoop(SlotMap& slotMa
             exit->target = peer;
             debug_only_printf(LC_TMTracer,
                               "Joining type-unstable trace to target fragment %p.\n",
                               (void*)peer);
             ((TreeInfo*)peer->vmprivate)->dependentTrees.addUnique(fragment->root);
             treeInfo->linkedTrees.addUnique(peer);
         }
     } else {
+        exit->exitType = LOOP_EXIT;
+        debug_only_printf(LC_TMTreeVis, "TREEVIS CHANGEEXIT EXIT=%p TYPE=%s\n", exit,
+                          getExitName(LOOP_EXIT));
         exit->target = fragment->root;
         fragment->lastIns = lir->insGuard(LIR_loop, lir->insImm(1), createGuardRecord(exit));
     }
     compile(traceMonitor);
 
     Assembler *assm = JS_TRACE_MONITOR(cx).assembler;
     if (assm->error() != nanojit::None)
         return false;
 
+    debug_only_printf(LC_TMTreeVis, "TREEVIS CLOSELOOP EXIT=%p PEER=%p\n", exit, peer);
+
     peer = getLoop(traceMonitor, root->ip, root->globalObj, root->globalShape, root->argc);
     JS_ASSERT(peer);
     joinEdgesToEntry(fragmento, peer);
 
     debug_only_stmt(DumpPeerStability(traceMonitor, peer->ip, peer->globalObj,
                                       peer->globalShape, peer->argc);)
 
     debug_only_print0(LC_TMTracer,
@@ -4050,16 +4086,18 @@ TraceRecorder::endLoop(VMSideExit* exit)
     fragment->lastIns =
         lir->insGuard(LIR_x, NULL, createGuardRecord(exit));
     compile(traceMonitor);
 
     Assembler *assm = traceMonitor->assembler;
     if (assm->error() != nanojit::None)
         return;
 
+    debug_only_printf(LC_TMTreeVis, "TREEVIS ENDLOOP EXIT=%p\n", exit);
+
     VMFragment* root = (VMFragment*)fragment->root;
     joinEdgesToEntry(traceMonitor->fragmento, getLoop(traceMonitor,
                                                       root->ip,
                                                       root->globalObj,
                                                       root->globalShape,
                                                       root->argc));
     debug_only_stmt(DumpPeerStability(traceMonitor, root->ip, root->globalObj,
                                       root->globalShape, root->argc);)
@@ -4184,17 +4222,20 @@ TraceRecorder::emitTreeCall(Fragment* in
         lir->insStorei(lirbuf->sp, lirbuf->state, offsetof(InterpState, sp));
         lir->insStorei(lirbuf->rp, lirbuf->state, offsetof(InterpState, rp));
     }
 
     /*
      * Guard that we come out of the inner tree along the same side exit we came out when
      * we called the inner tree at recording time.
      */
-    guard(true, lir->ins2(LIR_eq, ret, INS_CONSTPTR(exit)), NESTED_EXIT);
+    VMSideExit* nested = snapshot(NESTED_EXIT);
+    guard(true, lir->ins2(LIR_eq, ret, INS_CONSTPTR(exit)), nested);
+    debug_only_printf(LC_TMTreeVis, "TREEVIS TREECALL INNER=%p EXIT=%p GUARD=%p\n", inner, nested,
+                      exit);
 
     /* Register us as a dependent tree of the inner tree. */
     ((TreeInfo*)inner->vmprivate)->dependentTrees.addUnique(fragment->root);
     treeInfo->linkedTrees.addUnique(inner);
 }
 
 /* Add a if/if-else control-flow merge point to the list of known merge points. */
 JS_REQUIRES_STACK void
@@ -4486,16 +4527,17 @@ StartRecorder(JSContext* cx, VMSideExit*
     return true;
 }
 
 static void
 TrashTree(JSContext* cx, Fragment* f)
 {
     JS_ASSERT((!f->code()) == (!f->vmprivate));
     JS_ASSERT(f == f->root);
+    debug_only_printf(LC_TMTreeVis, "TREEVIS TRASH FRAG=%p\n", f);
     if (!f->code())
         return;
     AUDIT(treesTrashed);
     debug_only_print0(LC_TMTracer, "Trashing tree info.\n");
     TreeInfo* ti = (TreeInfo*)f->vmprivate;
     f->vmprivate = NULL;
     f->releaseCode(JS_TRACE_MONITOR(cx).codeAlloc);
     Fragment** data = ti->dependentTrees.data();
@@ -4767,16 +4809,27 @@ RecordTree(JSContext* cx, JSTraceMonitor
     ti->nStackTypes = ti->typeMap.length() - globalSlots->length();
 
 #ifdef DEBUG
     AssertTreeIsUnique(tm, (VMFragment*)f, ti);
     ti->treeFileName = cx->fp->script->filename;
     ti->treeLineNumber = js_FramePCToLineNumber(cx, cx->fp);
     ti->treePCOffset = FramePCOffset(cx->fp);
 #endif
+#ifdef JS_JIT_SPEW
+    debug_only_printf(LC_TMTreeVis, "TREEVIS CREATETREE ROOT=%p PC=%p FILE=\"%s\" LINE=%d OFFS=%d",
+                      f, f->ip, ti->treeFileName, ti->treeLineNumber, FramePCOffset(cx->fp));
+    debug_only_print0(LC_TMTreeVis, " STACK=\"");
+    for (unsigned i = 0; i < ti->nStackTypes; i++)
+        debug_only_printf(LC_TMTreeVis, "%c", typeChar[ti->typeMap[i]]);
+    debug_only_print0(LC_TMTreeVis, "\" GLOBALS=\"");
+    for (unsigned i = 0; i < ti->nGlobalTypes(); i++)
+        debug_only_printf(LC_TMTreeVis, "%c", typeChar[ti->typeMap[ti->nStackTypes + i]]);
+    debug_only_print0(LC_TMTreeVis, "\"\n");
+#endif
 
     /* Determine the native frame layout at the entry point. */
     unsigned entryNativeStackSlots = ti->nStackTypes;
     JS_ASSERT(entryNativeStackSlots == NativeStackSlots(cx, 0 /* callDepth */));
     ti->nativeStackBase = (entryNativeStackSlots -
             (cx->fp->regs->sp - StackBase(cx->fp))) * sizeof(double);
     ti->maxNativeStackSlots = entryNativeStackSlots;
     ti->maxCallDepth = 0;
@@ -4916,16 +4969,20 @@ AttemptToExtendTree(JSContext* cx, VMSid
         if (tvso) tvso->r = R_FAIL_EXTEND_MAX_BRANCHES;
 #endif
         return false;
     }
 
     Fragment* c;
     if (!(c = anchor->target)) {
         c = JS_TRACE_MONITOR(cx).fragmento->createBranch(anchor, cx->fp->regs->pc);
+        debug_only_printf(LC_TMTreeVis, "TREEVIS CREATEBRANCH ROOT=%p FRAG=%p PC=%p FILE=\"%s\""
+                          " LINE=%d ANCHOR=%p OFFS=%d\n",
+                          f, c, cx->fp->regs->pc, cx->fp->script->filename,
+                          js_FramePCToLineNumber(cx, cx->fp), anchor, FramePCOffset(cx->fp));
         c->spawnedFrom = anchor;
         c->parent = f;
         anchor->target = c;
         c->root = f;
     }
 
     /*
      * If we are recycling a fragment, it might have a different ip so reset it
--- a/js/src/jstracer.h
+++ b/js/src/jstracer.h
@@ -180,17 +180,18 @@ enum LC_TMBits {
      * above, since Nanojit uses 0 .. 15 itself.
      */
     LC_TMMinimal  = 1<<16,
     LC_TMTracer   = 1<<17,
     LC_TMRecorder = 1<<18,
     LC_TMPatcher  = 1<<19,
     LC_TMAbort    = 1<<20,
     LC_TMStats    = 1<<21,
-    LC_TMRegexp   = 1<<22
+    LC_TMRegexp   = 1<<22,
+    LC_TMTreeVis  = 1<<23
 };
 
 #endif
 
 #ifdef MOZ_NO_VARADIC_MACROS
 
 #define debug_only_stmt(action)            /* */
 static void debug_only_printf(int mask, const char *fmt, ...) {}
new file mode 100644
--- /dev/null
+++ b/js/src/tracevis/tree.py
@@ -0,0 +1,282 @@
+#!/usr/bin/python
+# vim: set ts=2 sw=2 tw=99 noet: 
+import re
+import sys
+import string
+
+class Node:
+	def __init__(self, address):
+		self.address = address
+
+class Fragment:
+	def __init__(self, address, root, pc, file, line, offset):
+		self.address = 'x' + address[2:]
+		if root == None:
+			self.root = self
+		else:
+			self.root = root
+		self.pc = pc
+		self.file = file
+		self.line = line
+		self.exits = []
+		self.marked = False
+		self.offset = offset
+		self.stackTypes = None
+		self.globalTypes = None
+		self.lastExit = None
+		self.nodes = {}
+
+	def addNode(self, exit):
+		node = Node('L' + self.address + 'E' + exit.address)
+		self.nodes[exit.address] = node
+		return node
+
+	def nodeName(self, exit):
+		return self.nodes[exit.address].address
+
+	def type(self):
+		if self == self.root:
+			return 'loop'
+		else:
+			return 'branch'
+
+	def describe(self):
+		if self.stackTypes == None:
+			return '<' + self.type() + '<br/>' + self.line + '@' + self.offset + \
+						 '<br/>' + self.address + '>'
+		else:
+			return '<' + self.type() + '<br/>' + self.line + '@' + self.offset + \
+						 '<br/>' + self.address + ', ' + self.stackTypes + ',' + self.globalTypes + '>'
+
+	def addExit(self, e):
+		e.owner = self
+		self.exits.append(e)
+
+class Exit:
+	def __init__(self, address, type, pc, file, line, offs, _s, _g):
+		self.address = 'x' + address[2:]
+		self.type = type
+		self.pc = pc
+		self.file = file
+		self.line = line
+		self.offset = offs
+		self.stackTypes = _s
+		self.globalTypes = _g
+		self.owner = None
+		self.target = None
+		self.treeGuard = None
+		self.marked = False
+
+	def describe(self):
+		return '<' + self.type + '<br/>' + self.address + ', line ' + self.line + '@' + self.offset + \
+					 '<br/>' + self.stackTypes + ',' + self.globalTypes + '>'
+
+class TraceRecorder:
+	def __init__(self):
+		self.trees = {}
+		self.fragments = {}
+		self.exits = {}
+		self.currentFrag = None
+		self.currentAnchor = None
+		self.edges = []
+		self.treeEdges = []
+
+	def createTree(self, ROOT, PC, FILE, LINE, STACK, GLOBALS, OFFS):
+		f = Fragment(ROOT, None, PC, FILE, LINE, OFFS)
+		f.stackTypes = STACK
+		f.globalTypes = GLOBALS
+		self.trees[ROOT] = f
+		self.fragments[ROOT] = f
+		return f
+
+	def createBranch(self, ROOT, FRAG, PC, FILE, LINE, ANCHOR, OFFS):
+		root = self.trees[ROOT]
+		branch = Fragment(FRAG, root, PC, FILE, LINE, OFFS)
+		self.fragments[FRAG] = branch
+		return branch
+
+	def record(self, FRAG, ANCHOR):
+		self.currentFrag = self.fragments[FRAG]
+		if self.currentFrag.root != self.currentFrag:
+			self.currentAnchor = self.exits[ANCHOR]
+		else:
+			self.currentAnchor = None
+
+	def addExit(self, EXIT, TYPE, FRAG, PC, FILE, LINE, OFFS, STACK, GLOBALS):
+		if EXIT not in self.exits:
+			e = Exit(EXIT, TYPE, PC, FILE, LINE, OFFS, STACK, GLOBALS)
+			e.owner = self.fragments[FRAG]
+			self.exits[EXIT] = e
+		else:
+			e = self.exits[EXIT]
+		self.currentFrag.addExit(e)
+
+	def changeExit(self, EXIT, TYPE):
+		exit = self.exits[EXIT]
+		exit.type = TYPE
+
+	def endLoop(self, EXIT):
+		exit = self.exits[EXIT]
+		if self.currentAnchor != None:
+			self.currentAnchor.target = self.currentFrag
+		self.currentFrag.lastExit = exit
+		self.currentFrag = None
+		self.currentAnchor = None
+
+	def closeLoop(self, EXIT, PEER):
+		exit = self.exits[EXIT]
+		if self.currentAnchor != None:
+			self.currentAnchor.target = self.currentFrag
+		if exit.type != "LOOP" and PEER != "0x0":
+			peer = self.trees[PEER]
+			exit.target = peer
+		self.currentFrag.lastExit = exit
+		self.currentFrag = None
+		self.currentAnchor = None
+
+	def join(self, ANCHOR, FRAG):
+		exit = self.exits[ANCHOR]
+		fragment = self.fragments[FRAG]
+		exit.target = fragment
+
+	def treeCall(self, INNER, EXIT, GUARD):
+		exit = self.exits[EXIT]
+		inner = self.trees[INNER]
+		guard = self.exits[GUARD]
+		exit.target = inner
+		exit.treeGuard = guard
+
+	def trash(self, FRAG):
+		pass
+
+	def readLine(self, line):
+		cmd = re.match(r"TREEVIS ([^ ]+) (.*)$", line)
+		if cmd == None:
+			return
+		cmd = cmd.groups()
+		keys = dict([w.split('=') for w in string.split(cmd[1])])
+		if cmd[0] == "CREATETREE":
+			self.createTree(**keys)
+		elif cmd[0] == "RECORD":
+			self.record(**keys)
+		elif cmd[0] == "ADDEXIT":
+			self.addExit(**keys)
+		elif cmd[0] == "CREATEBRANCH":
+			self.createBranch(**keys)
+		elif cmd[0] == "CLOSELOOP":
+			self.closeLoop(**keys)
+		elif cmd[0] == "CHANGEEXIT":
+			self.changeExit(**keys)
+		elif cmd[0] == "ENDLOOP":
+			self.endLoop(**keys)
+		elif cmd[0] == "JOIN":
+			self.join(**keys)
+		elif cmd[0] == "TRASH":
+			self.trash(**keys)
+		elif cmd[0] == "TREECALL":
+			self.treeCall(**keys)
+		else:
+			raise Exception("unknown command: " + cmd[0])
+
+	def describeTree(self, fragment):
+		return '<' + 'tree call to<br/>' + fragment.line + '@' + fragment.offset + '>'
+
+	def emitExit(self, fragment, exit):
+		if exit.type == "NESTED":
+			print '\t\ttc_' + exit.address + ' [ shape = octagon, label = ' + \
+						self.describeTree(exit.target) + ' ]'
+			self.edges.append(['tc_' + exit.address, exit.target.address])
+		node = fragment.addNode(exit)
+		print '\t\t' + node.address + ' [ label = ' + exit.describe() + ' ]'
+
+	def emitTrace(self, fragment):
+		if fragment.marked == True:
+			raise Exception('fragment already marked')
+		print "\t\t" + fragment.address + " [ label = <start> ] "
+		for e in fragment.exits:
+			if e.target == None and (e != fragment.lastExit and e.type != 'LOOP'):
+				continue
+			self.emitExit(fragment, e)
+		last = fragment.address
+		for e in fragment.exits:
+			if e.target == None and (e != fragment.lastExit and e.type != 'LOOP'):
+				continue
+			if e.type == "NESTED":
+				print '\t\t' + last + ' -> tc_' + e.address
+				print '\t\ttc_' + e.address + ' -> ' + fragment.nodeName(e) + \
+							' [ arrowtail = dot, arrowhead = onormal ] '
+				if e.treeGuard != None:
+					self.treeEdges.append([e, fragment.nodeName(e)])
+			else:
+				print '\t\t' + last + ' -> ' + fragment.nodeName(e)
+				if e.target == None and e.type == 'LOOP':
+					self.edges.append([fragment.nodeName(e), fragment.root.address])
+				elif e.target != None:
+					self.edges.append([fragment.nodeName(e), e.target.address])
+			last = fragment.nodeName(e)
+
+	def emitBranch(self, fragment):
+		if fragment.root == fragment:
+			raise Exception('branches have root!=frag')
+		if fragment.lastExit == None:
+			fragment.marked = True
+			return
+		print '\tsubgraph cluster_' + fragment.address + ' {'
+		print '\t\tlabel = ' + fragment.describe()
+		self.emitTrace(fragment)
+		fragment.marked = True
+		print "\t}"
+		self.emitBranches(fragment)
+
+	def emitBranches(self, fragment):
+		for e in fragment.exits:
+			if not e.target or e.target.marked:
+				continue
+			if e.target == e.target.root:
+				self.emitTree(e.target)
+			else:
+				self.emitBranch(e.target)
+
+	def emitTree(self, fragment):
+		if fragment.root != fragment:
+			raise Exception('trees have root=frag')
+		if fragment.lastExit == None:
+			fragment.marked = True
+			return
+		print '\tsubgraph cluster_' + fragment.address + ' {'
+		print '\t\tlabel = ' + fragment.describe()
+		self.emitTrace(fragment)
+		print "\t}"
+		fragment.marked = True
+		self.emitBranches(fragment)
+
+	def emitGraph(self):
+		print "digraph G {"
+		worklist = [self.trees[fragment] for fragment in self.trees]
+		for fragment in worklist:
+			if fragment.marked:
+				continue
+			self.emitTree(fragment)
+		for edge in self.edges:
+			name = edge[0]
+			address = edge[1]
+			print '\t' + name + ' -> ' + address
+		for edge in self.treeEdges:
+			fromName = edge[0].treeGuard.owner.nodeName(edge[0].treeGuard)
+			toName = edge[1]
+			print '\t' + fromName + ' -> ' + toName + \
+					  ' [ arrowtail = dot ]'
+		print "}"
+
+	def fromFile(self, file):
+		line = file.readline()
+		while line != "":
+			self.readLine(line)
+			line = file.readline()
+
+tr = TraceRecorder()
+f = open(sys.argv[1], "r")
+tr.fromFile(f)
+f.close()
+tr.emitGraph()
+