Added wholeprog phase sources

6 files changed, 1894 insertions, 0 deletions

diff --git a/sources/scala/tools/scalac/MyCompilerPhases.scala b/sources/scala/tools/scalac/MyCompilerPhases.scala
new file mode 100644
index 0000000000..43431a80ef
--- /dev/null
+++ b/sources/scala/tools/scalac/MyCompilerPhases.scala
@@ -0,0 +1,117 @@
+/*     ____ ____  ____ ____  ______                                     *\
+**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
+**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2002, LAMP/EPFL              **
+** /_____/\____/\___/\____/____/                                        **
+\*                                                                      */
+
+/*
+**       The Global analysis phase.
+**
+**  We add a new phase in the compiler, WholeProgPhase.
+**
+** [iuli]   3.03.2004                                                   */
+
+// import scalac.{CompilerPhases => scalac_CompilerPhases}
+
+import scala.tools.scalac.{CompilerPhases => old_CompilerPhases}
+import scalac.{Global => scalac_Global}
+import scalac.transformer.{ICodePhase => scalac_ICodePhase}
+import scalac.PhaseDescriptor;
+import scalac.{Unit => scalac_Unit}
+import scalac.atree._;
+import scala.tools.scalac.wholeprog._;
+//import scalac.ast._;
+import scalac.util.Name;
+
+package scala.tools.scalac {
+
+/**
+ * We add our phase to the compiler phases. To do this, we derive
+ * from the current CompilerPhases class and insert our phase after
+ * the tail call phase.
+ *
+ */
+class MyCompilerPhases extends old_CompilerPhases {
+
+  var WHOLEPROG: PhaseDescriptor = new PhaseDescriptor(
+    "wholeprog",
+    "analyze class hierarchy",
+    "Find final classes, unused code and monomorphic call-sites",
+    WHOLEPROG_PHASE);
+
+
+  insertAfter(WHOLEPROG, TAILCALL);
+
+  protected def WHOLEPROG_PHASE: Class =
+    Class.forName("scala.tools.scalac.WholeProgPhase$class");
+}
+
+/**
+ * This phase analyzes the whole program and tries to derive some
+ * useful facts about it: which classes can be marked final, what
+ * methods, fields are never used, and monomorphic call-sites.
+ *
+ * TODO: Maybe the parent should be something other than ICodePhase!!
+ */
+class WholeProgPhase(global: scalac_Global, descriptor: PhaseDescriptor)
+    extends scalac_ICodePhase (global, descriptor) {
+
+
+  // ##################################################
+  // Public methods
+
+  /* Apply the global analysis phase to the given units */
+  override def apply(units: Array[scalac_Unit]): unit = {
+
+    if (!global.args.XdotFile.value.equals("$")) {
+      val dotFilePrinter = new PrintDotFile(units);
+      dotFilePrinter.makeDotFile(global.args.XdotFile.value);
+    }
+
+    if (!global.args.XrootClass.value.equals("$")) {
+
+      var builder: ApplicationBuilder = new ApplicationBuilder(global);
+      builder.buildApplication(global.args.XrootClass.value, units);
+    }
+
+    if (!global.args.XdotFile.value.equals("$")) {
+      val dotFilePrinter = new PrintDotFile(units);
+      dotFilePrinter.makeDotFile(global.args.XdotFile.value + "2");
+    }
+  }
+
+  /** visit each method of a class
+    * and log Apply cases           */
+  def visitClass(cl: AClass): unit = {
+    val methods = cl.methods();
+
+    var i: int = 0;
+    while (i < methods.length) {
+      visitCode (methods(i).code());
+      i = i + 1;
+    }
+  }
+
+  /** try to find call-sites and print them out */
+  def visitCode(code: ACode): unit = {
+
+    code match {
+      case ACode$Apply(AFunction$Method(obj, method, style),_,_) => {
+	visitCode(obj);
+	global.log("   Apply method: " + obj.toString() + "/" + method + " style: " + style);
+      }
+
+      case ACode$Apply(_, _, _) => global.log("   Apply something: " + code);
+
+      case ACode$Block(_, stats, _) => {
+	stats.foreach( (stat: ACode) => { visitCode(stat) } );
+      }
+
+      case ACode$Drop(value, _) => visitCode(value);
+
+      case _ => ();
+    }
+  }
+}
+
+}
diff --git a/sources/scala/tools/scalac/wholeprog/ApplicationBuilder.scala b/sources/scala/tools/scalac/wholeprog/ApplicationBuilder.scala
new file mode 100644
index 0000000000..39a6bb8868
--- /dev/null
+++ b/sources/scala/tools/scalac/wholeprog/ApplicationBuilder.scala
@@ -0,0 +1,524 @@
+
+import scalac.{Global => scalac_Global}
+import scalac.{Unit => scalac_Unit}
+import scalac.atree._;
+import scalac.symtab._;
+import scalac.util.Name;
+import scalac.util._;
+import scala.collection.mutable._;
+import scalac.ast._;
+
+package scala.tools.scalac.wholeprog {
+
+/**
+ * This class builds the set of classes included in the Application (whole
+ * program), starting with a root class, given from the outside (usually
+ * the user).
+ *
+ */
+class ApplicationBuilder(globall: scalac_Global) {
+
+  private val global = globall;
+  var rootClassName: Name = Name.fromString("");
+  //var map: SymbolMap = null;
+
+  // algorithm data
+  var worklist: Set[Symbol] = new HashSet[Symbol];
+  var app: Set[Symbol]      = new HashSet[Symbol];
+
+  val chGraph = new ClassHierarchy(global);
+
+  def finalClasses(app: Set[Symbol], units: Array[scalac_Unit]): Unit = {
+    val m = new MonomorphicCallSites(global, app);
+    m.buildClassHierarchy;
+
+    m.hierarchy.visitDFS( (n) => {
+      if (m.hierarchy.inEdges(n.id).length == 0) {
+//	Console.println("Final class: " + n.info.name.toString());
+	n.info.flags = n.info.flags | Modifiers.FINAL;
+      }
+    });
+
+//     val transf: GenTransformer = new GenTransformer(global);
+
+//     units.foreach( (u) => {
+//       u.body.foreach( (b) => transf.transform(b) );
+//     });
+
+    m.monomorphicCallsites;
+  }
+
+
+  /** find the whole application that is referenced by the root class  */
+  def buildApplication(root: String, units: Array[scalac_Unit]): unit = {
+    rootClassName = Name.fromString(root);
+
+    var rootClass: Symbol = null;
+    try {
+      rootClass = global.definitions.getModule(root).moduleClass();
+    } catch {
+      case _ => global.error(root + " is not the name of an object");
+    }
+
+    if (rootClass == Symbol.NONE)
+      global.error(root + " is not an object");
+
+    // build the map from Symbol's to AST nodes
+    buildCodeMap(units);
+//    Console.println(SymbolMap);
+
+    worklist += rootClass;
+
+    while (!worklist.isEmpty)
+      visitClass(worklist.toList.head);
+
+    dumpApplication;
+
+    // now we call from here the final-classes analysis,
+    // but we should really move it to a more sensible place, like a
+    // whole-program anlysis controller, or "plan", the same way the
+    // compiler phases are structured
+    finalClasses(app, units);
+  }
+  // where
+    def buildCodeMap(units: Array[scalac_Unit]): Unit = {
+      //val map = new SymbolMap();
+
+      def mapTree(t: Tree): unit = {
+	t match {
+	  case Tree$PackageDef(pack, impl) => {
+	    mapTree(pack);
+	    mapTree(impl);
+	  }
+
+	  case Tree$ClassDef(mods, name, tparams, vparams, tpe, impl) => {
+	    SymbolMap.addSymbol(t.symbol(), t);
+	    mapTree(impl);
+	  }
+
+	  case Tree$Template(parents, body) => {
+	    body.foreach( (b) => mapTree(b) );
+	  }
+
+	  case _ => ;
+	};
+      }
+
+      units.foreach( (u: scalac_Unit) =>
+	u.body.foreach( (b) => mapTree(b) ));
+    }
+
+    def dumpApplication: Unit = {
+      val outputFile = new java.io.File(global.args.XappFile.value);
+      val writer: java.io.Writer = new java.io.FileWriter(outputFile);
+
+      app.foreach( (s: Symbol) => {
+	writer.write(s.name.toString() + "\n");
+      });
+      // if we don't flush, nothing gets written?!!
+      writer.flush();
+    }
+
+  def visitClass(clsSym: Symbol): unit = {
+    if (clsSym.isExternal())
+      visitExternalClass(clsSym);
+    else
+      visitInternalClass(clsSym);
+  }
+
+  def visitExternalClass(clsSym: Symbol): unit = {
+    assert(clsSym.isClass(), "Not a class symbol? " + clsSym);
+
+    app += clsSym;
+    worklist -= clsSym;
+
+    // parents
+    addTypesToWorklist(List.fromArray(clsSym.parents(), 0, clsSym.parents().length));
+
+    updateClassHierarchy(clsSym);
+
+    // members
+    clsSym.members().elements().foreach( (s: Symbol) => {
+      if (s.isClass())
+	visitClass(s);
+      else if (s.isValue() || s.isVariable()) {
+	// a field
+      } else if (s.isMethod()) {
+	// a method
+      }
+    });
+  }
+
+  /**
+   * Visit a class declaration.. Walk all its methods and add to the Application set
+   * all classes referenced by a method call, instantiation or assignment. We have to
+   * have a source represenation of this class (it is not Java code/or external class).
+   *
+   * What we include for each class:
+   *   - superclasses
+   *   - field types (actually their classes)
+   *   - return and argument types for methods (actually their classes)
+   *   - receiver type for method calls (actually its class)
+   *   - receiver and field type for foreign field accesses (same obs as before)
+   */
+  def visitInternalClass(clsSym: Symbol): unit = {
+    var cls: Tree = null;
+
+    app += clsSym;
+    worklist -= clsSym;
+
+    SymbolMap.getDefinition(clsSym) match {
+      case Some(c) => cls = c;
+      case None => {
+	Console.println("Could not find symbol " + clsSym + " in code map");
+	return;
+      }
+    }
+
+    val parents = clsSym.parents();
+
+    updateClassHierarchy(clsSym);
+
+    // superclasses
+    addTypesToWorklist(List.fromArray[Type](parents, 0, parents.length));
+
+    addReferences(cls);
+  }
+  // where
+    def updateClassHierarchy(cls: Symbol): Unit = {
+      val parents = cls.parents();
+      var i = 1;
+      val subclass: Node = chGraph.getNode(cls);
+
+      def typeToSymbol(t: Type): Symbol = {
+	t match {
+	  case Type$TypeRef(_, s, _) => s;
+	  case _ => { global.error("Cannot handle base type " + t + " for " + cls ); null }
+	}
+      }
+
+
+      if (parents.length > 0) {
+	chGraph.addBaseClass(subclass, chGraph.getNode(typeToSymbol(parents(0))));
+        while (i < parents.length) {
+	  chGraph.addMixin(subclass, chGraph.getNode(typeToSymbol(parents(i))));
+	  i = i + 1;
+	}
+      }
+    }
+
+
+    /**
+     * Walk the tree and add to the worklist any class symbol that is
+     * referenced from this tree.
+     */
+    def addReferences(t: Tree): unit = {
+      t match {
+	case Tree$ClassDef(mods, name, tparams, vparams, tpe, impl) => {
+	  tparams.foreach( (tpar) => addReferences(tpar) );
+	  vparams.foreach( (varray) => varray.foreach( (v) => addReferences(v) ) );
+
+	  addReferences(tpe);
+	  addReferences(impl);
+	}
+
+	case Tree$PackageDef(packaged, impl) => {
+	  addReferences(packaged);
+	  addReferences(impl);
+	}
+
+	case Tree$ModuleDef(mods, name, tpe, impl) => {
+	  addReferences(tpe);
+	  addReferences(impl);
+	}
+
+	case Tree$ValDef(mods, name, tpe, rhs) => {
+	  assert(t.hasSymbol());
+
+	  val s = t.symbol().getType();
+	  addTypesToWorklist(s :: Nil);
+
+	  addReferences(tpe);
+	  addReferences(rhs);
+	}
+
+	case Tree$PatDef(mods, pat, rhs) => {
+	  assert(t.hasSymbol());
+
+	  val s = t.symbol().getType();
+	  addTypesToWorklist(s :: Nil);
+
+	  addReferences(pat);
+	  addReferences(rhs);
+	}
+
+	case Tree$DefDef(mods, name, tparams, vparams, tpe, impl) => {
+	  assert(t.hasSymbol());
+
+	  val s = t.symbol().getType();
+	  addTypesToWorklist(s :: Nil);
+
+	  tparams.foreach( (tpar) => addReferences(tpar) );
+	  vparams.foreach( (varray) => varray.foreach( (v) => addReferences(v) ) );
+
+	  addReferences(tpe);
+	  addReferences(impl);
+	}
+
+	case Tree$AbsTypeDef(mods, name, rhs, lobound) => {
+	  addReferences(rhs);
+	  addReferences(lobound);
+	  if (t.hasSymbol())
+	    addTypesToWorklist(t.symbol().getType() :: Nil);
+	}
+
+	case Tree$AliasTypeDef(mods, name, tparams, rhs) => {
+	  tparams.foreach( (tt) => addReferences(tt) );
+	  addReferences(rhs);
+	}
+
+	case Tree$Import(expr, selectors) => ;
+
+	case Tree$CaseDef(pat, guard, body) => {
+	  addReferences(pat);
+	  addReferences(guard);
+	  addReferences(body);
+	}
+
+	case Tree$Template(parents, body) => {
+	  body.foreach( (b) => addReferences(b) );
+	}
+
+	case Tree$LabelDef(name, params, rhs) => {
+	  params.foreach( (p) => addReferences(p) );
+	  addReferences(rhs);
+	}
+
+	case Tree$Block(stats, expr) => {
+	  stats.foreach( (stat) => addReferences(stat) );
+	  addReferences(expr);
+	}
+
+	case Tree$Sequence(trees) => {
+	  trees.foreach( (t) => addReferences(t) );
+	}
+
+	case Tree$Function(vparams, body) => {
+	  vparams.foreach( (vpar) => addReferences(vpar) );
+	  addReferences(body);
+	}
+
+	case Tree$Assign(lhs, rhs) => {
+	  addReferences(lhs);
+	  addReferences(rhs);
+	}
+
+	case Tree$If(cond, thenp, elsep) => {
+	  addReferences(cond);
+	  addReferences(thenp);
+	  addReferences(elsep);
+	}
+
+	case Tree$Switch(test, tags, bodies, otherwise) => {
+	  addReferences(test);
+	  bodies.foreach( (b) => addReferences(b) );
+	  addReferences(otherwise);
+	}
+
+	case Tree$Return(expr) => addReferences(expr);
+
+	case Tree$Throw(expr) => addReferences(expr);
+
+	// the only place where new references can be added
+	case Tree$New(template) => {
+	  addReferences(template);
+
+//	  Console.println("<new> template with type! " + template.getType());
+	  addTypesToWorklist(template.getType() :: Nil);
+	}
+
+	case Tree$Typed(expr, tpe) => {
+	  addReferences(expr);
+	  addReferences(tpe);
+	}
+
+	case Tree$TypeApply(fun, args) => {
+	  addReferences(fun);
+	  args.foreach( (a) => addReferences(a) );
+	}
+
+	case Tree$Apply(fun, args) => {
+	  addReferences(fun);
+	  addTypesToWorklist(fun.getType() :: Nil);
+
+	  args.foreach( (a) => addReferences(a) );
+	}
+
+	case Tree$Super(qualifier, mixin) => ;
+
+	case Tree$This(qualifier) => ;
+
+	case Tree$Select(qualifier, selector) => {
+	  addTypesToWorklist(qualifier.getType() :: Nil);
+
+	  addReferences(qualifier);
+	}
+
+	case Tree$Ident(name) => ;
+
+	case Tree$Literal(value) => ;
+
+	case Tree$TypeTerm() => {
+	  addTypesToWorklist(t.getType() :: Nil);
+	}
+
+	case Tree$SingletonType(ref) => {
+	  addReferences(ref);
+	}
+
+	case Tree$SelectFromType(qualifier, selector) => addReferences(qualifier);
+
+	case Tree$FunType(argTypes, restpe) => {
+	  argTypes.foreach( (a) => addReferences(a) );
+	  addReferences(restpe);
+	}
+
+	case Tree$CompoundType(parents, refinements) => {
+	  parents.foreach( (p) => addReferences(p) );
+	  refinements.foreach( (r) => addReferences(r) );
+	}
+
+	case Tree$AppliedType(tpe, args) => {
+	  addReferences(tpe);
+	  args.foreach( (a) => addReferences(a) );
+	}
+
+	case Tree$Try(block, catcher, finalizer) => {
+	  addReferences(block);
+	  addReferences(catcher);
+	  addReferences(finalizer);
+	}
+
+	case _ => ;
+      }
+    }
+
+    def addReferencesList(trees: List[Tree]) = {
+      trees.foreach( (t) => addReferences(t));
+    }
+
+    def typeToSymbol(t: Type): Symbol = {
+      t match {
+	case Type$TypeRef(_, s, _) => if (s.isAbstractType()) typeToSymbol(t.bound()) else s;
+	case Type$SingleType(pre, sym) => typeToSymbol(sym.getType());
+	case Type$ThisType(sym) => sym;
+	case Type$PolyType(tparams, result) => typeToSymbol(result); // attention!
+	case Type$ConstantType(base, value) => typeToSymbol(base);
+	case Type$MethodType(vparams, result) => typeToSymbol(result);
+	case Type$CompoundType(_, _) => t.symbol();
+	case _ => { global.error("Cannot handle base type " + t); null }
+      }
+    }
+
+  def addTypesToWorklist(types: List[Type]): unit = {
+    types.foreach( (t) => addSymbolToWorklist(typeToSymbol(t)) );
+  }
+
+/*
+   // where
+      def addTypesToWorklist2(types: List[Type]): unit = {
+	// types have to be TypeRef really, actually class types so that we
+	// can identify the corresponding class and add it to our processing list
+	types.foreach( (t: Type) => {
+	  t.match {
+	    case Type$TypeRef(pre, s, args) => {
+	      addTypesToWorklist(List.fromArray[Type](args, 0, args.length));
+	      addSymbolToWorklist(s);
+	    }
+
+	    case Type$CompoundType(parts, members) => Console.println("CompoundType " + t);
+
+	    case Type$ThisType(sym) => Console.println("ThisType " + t);
+
+	    case Type$SingleType(pre, sym) => Console.println("SingleType " + t);
+
+	    case Type$ConstantType(base, value) => Console.println("ConstantType " + t);
+
+	    case Type$MethodType(vparams, result) => {
+	      val xs = List.fromArray[Symbol](vparams, 0, vparams.length);
+	      addTypesToWorklist(xs map { (s) => s.getType() });
+	      addTypesToWorklist(result :: Nil);
+	    }
+
+	    case Type$PolyType(tparams, result) => {
+	      val xs = List.fromArray[Symbol](tparams, 0, tparams.length);
+	      addTypesToWorklist(xs map { (s) => s.getType() });
+	      addTypesToWorklist(result :: Nil);
+	    }
+
+	    case Type$OverloadedType(alts, alttypes) => Console.println("OverloadedType " + t);
+
+	    case Type$LazyType() => Console.println("LazyType " + t);
+
+	    case Type$TypeVar(origin, constr) => Console.println("TypeVar " + t);
+
+	    case Type$UnboxedType(tag) => Console.println("UnboxedType " + t);
+
+	    case Type$UnboxedArrayType(elempt) => Console.println("UnboxedArrayType " + t);
+
+	    case _ => Console.println("[worklist] Could not handle type " + t.toString());
+	  }
+	});
+      }
+*/
+      /** the specified symbol has to be a class symbol. It adds its corresponding
+        *  Class symbol to the worklist if the necessary conditions are met          */
+      def addSymbolToWorklist(sym: Symbol): Unit = {
+	if (sym != null && sym.isClass())
+	  if (!app.contains(sym) && !worklist.contains(sym)) {
+	    global.log("Adding type " + sym + " to worklist");
+	    worklist += sym;
+	  }
+      }
+}
+
+/**
+ * A map from Symbol values to AClass values. It is used by the ApplicationBuilder
+ * in order to resolve class name symbols (to find their definition)
+ */
+object SymbolMap {
+  private var map: Map[Symbol, Tree] = new HashMap[Symbol, Tree]();
+
+  def addSymbol(s: Symbol, definition: Tree): unit =
+    map.update(s, definition);
+
+  /** Return the atree for the class definition of this symbol, if
+    * there is one, or None otherwise                              */
+  def getDefinition(s: Symbol): Option[Tree] = {
+    map.get(s);
+  }
+
+  def getDefinition1(s: Symbol): Tree = {
+    getDefinition(s) match {
+      case Some(t) => t;
+      case _ => null;
+    }
+  }
+
+  def elements = map.elements;
+
+  override def toString(): String = {
+    var str: String = "";
+
+    elements.foreach( (tuple: Tuple2[Symbol, Tree]) => {
+      str = str.concat(SymbolPrinter.fullName(tuple._1));
+      str = str.concat(" -> ");
+      //str = str.concat(tuple._2.toString());
+      str = str.concat("\n");
+    });
+    str;
+  }
+}
+
+} // package scala.tools.scalac.globalanalysis
+
diff --git a/sources/scala/tools/scalac/wholeprog/Inline.scala b/sources/scala/tools/scalac/wholeprog/Inline.scala
new file mode 100644
index 0000000000..b21617d069
--- /dev/null
+++ b/sources/scala/tools/scalac/wholeprog/Inline.scala
@@ -0,0 +1,230 @@
+/*     ____ ____  ____ ____  ______                                     *\
+**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
+**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2004, LAMP/EPFL              **
+** /_____/\____/\___/\____/____/                                        **
+\*                                                                      */
+
+/*
+**       Inline methods in monomoprhic callsites
+**
+** [iuli]   12.05.2004                                                  */
+
+import scalac.{Global => scalac_Global}
+import scalac.{Unit => scalac_Unit}
+import scalac.symtab._;
+import scalac.util._;
+import scala.collection.mutable._;
+import scalac.ast._;
+import scala.tools.scalac.wholeprog.graph.{Node => GNode};
+import scala.tools.scalac.wholeprog.graph._;
+import scala.tools.util._;
+
+package scala.tools.scalac.wholeprog {
+
+/** Perform inlining of the sites passed as parameter */
+class InlineMethods(sites: List[Tuple3[GNode[Symbol, MethodNode], GNode[Symbol, MethodNode], CallSite]],
+		    global: scalac_Global)
+  extends Transformer(global) {
+    var inlines: int = 0;
+    var inlinedThis: Symbol = null;
+
+
+  override def transform(tree: Tree): Tree = {
+    tree match {
+      case Tree$Apply(fun, args) => {
+	val s = sites.find( tuple => tree == tuple._3.t);
+	s match {
+	  case Some(Tuple3(cl, ce, s)) => expand(tree, cl, ce)
+	  case _ => super.transform(tree);
+	}
+      }
+
+      case _ => super.transform(tree);
+    }
+  }
+
+  def expand(tree: Tree, caller: GNode[Symbol, MethodNode], callee: GNode[Symbol, MethodNode]): Tree = {
+    val expr: Tree = null;
+    val Tree$DefDef(_, name, _, vparams, _, rhs) = callee.info.code;
+    val subst = new HashMap[Symbol, Symbol];
+
+    def createLocals(tree: Tree, calleeDef: Tree): Array[Tree] = {
+      val Tree$Apply(fun, args) = tree;
+      val Tree$DefDef(_, name, _, vparams, _, rhs) = calleeDef;
+
+      val res: Array[Tree] = new Array[Tree](args.length + 1); // make room for $this
+      assert(args.length == vparams(0).length,
+	     "Call site has different nr. of arguments than def " + fun.symbol());
+
+      res(0) = makeThisDef(fun);
+      var i: int = 1;
+      while (i < res.length) {
+	// duplicate the formal parameter of the method and create a symbol for this def
+	val arg = vparams(0)(i-1).duplicate().asInstanceOf[Tree$ValDef];
+	val sym = caller.info.method.newVariable(fun.pos, 0, Name.fromString("$" + i));
+
+	// set the type of the parameter to the type of the *actual* argument
+//	sym.setType(args(i-1).getType());
+	// or the formals?
+	sym.setType(arg.tpe.getType());
+
+//	Console.println("Type: actual " + sym.getType() + " : formal "
+//			+ arg);
+
+	arg.tpe.setType(sym.getType());
+	// add the mapping to the substitution table of symbols
+	subst += arg.symbol() -> sym;
+
+	// set the initial value to the actual parameter
+	arg.rhs = args(i - 1).duplicate();
+	arg.setSymbol(sym);
+	arg.rhs.setType(sym.getType());
+
+	res(i) = arg;
+	i = i + 1;
+      }
+
+      res
+    }
+
+    def makeThisDef(fun: Tree): Tree = {
+      val Tree$Select(qualifier, selector) = fun;
+
+//      val tpe = make.TypeTerm(fun.pos);
+      val sym = caller.info.method.newVariable(fun.pos, 0, Name.fromString("inthis"));
+//      sym.setType(qualifier.getType().singleDeref()); // it was .singleDeref() but unneded?
+      sym.setType(callee.info.classz.getType());
+      Logger.log("[inthis] Set type to " + sym.getType());
+
+//      val t = make.ValDef(fun.pos, 0, Name.fromString("inthis"), tpe, qualifier.duplicate());
+      val t = gen.ValDef(sym, qualifier.duplicate());
+
+//      tpe.setType(qualifier.getType().deconst());
+//      t.setSymbol(sym);
+      inlinedThis = sym;
+
+      t
+    }
+
+    val locals = createLocals(tree, callee.info.code);
+    val updater = new UpdateAccesses(subst, caller.info.method);
+    val newRhs = updater.transform(rhs.duplicate());
+
+    Logger.log("[inline] expand reached");
+
+    if (updater.touchedPrivate)
+      tree
+    else {
+      Logger.log("Inlining at " +
+		 caller.info.classz.name + "." +
+		 caller.info.method.name + " [" + Position.toString(tree.pos) + "] with " +
+		 callee.info.classz.name + "." +
+		 callee.info.method.name);
+      inlines = inlines + 1;
+
+      gen.mkBlock(locals, newRhs);
+    }
+  }
+
+  /** Update accesses to symbols that have been replaced according to the map */
+  class UpdateAccesses(subst: HashMap[Symbol, Symbol], hostMethod: Symbol)
+    extends GenTransformer(global) {
+
+    var touchedPrivate: boolean = false;
+
+    override def transform(tree: Tree): Tree = {
+      tree match {
+	case Tree$This(qualifier) => {
+	  assert(inlinedThis != null, "<this> is null for " + tree);
+	  gen.Ident(tree.pos, inlinedThis);
+	}
+
+	// create a new symbol for the new declaration in this method
+ 	case Tree$ValDef(mods, name, tpe, rhs) => {
+	  val newSym = hostMethod.newVariable(tree.pos, mods, name);
+
+	  newSym.setType(tpe.getType());
+	  subst += tree.symbol() -> newSym;
+
+	  tree.setSymbol(newSym);
+
+          gen.ValDef(newSym, transform(rhs));
+	}
+
+	case Tree$Super(_, _) => {
+	  Logger.log("[inline] Touched super.");
+	  touchedPrivate = true; // not private, but still we cannot inline this function
+	  super.transform(tree);
+	}
+
+	case Tree$Return(_) => {
+	  Logger.log("[inline] Touched return.");
+	  touchedPrivate = true; // not private, but still we cannot inline this function
+	  super.transform(tree);
+	}
+
+	case Tree$LabelDef(name, params, rhs) => {
+	  val newSym = hostMethod.newLabel(tree.pos, name);
+
+ 	  newSym.setInfo(tree.symbol().info());
+	  subst += tree.symbol() -> newSym;
+
+          gen.LabelDef(newSym, super.transform(params), transform(rhs));
+	}
+
+ 	case Tree$PatDef(mods, pat, rhs) => {
+	  Console.println("new pattern definition in inlined class");
+	  tree
+	}
+
+ 	case Tree$DefDef(_, _, _, _, _, _) => {
+	  assert(false, "We should be after lambda lift, so no inner function allowed");
+	  tree;
+	}
+
+	case _ =>  super.transform(tree);
+
+      }
+
+    }
+
+    override def getSymbolFor(tree: Tree): Symbol = {
+      if (tree.symbol().isPrivate()) {
+	touchedPrivate = true;
+	Logger.log("[inline] touched private symbol " +
+		   SymbolPrinter.fullName(tree.symbol()));
+      }
+
+      if (subst.contains(tree.symbol())) {
+	Logger.log("[inline] Substituted " + tree.symbol() + " with " + subst(tree.symbol()));
+	subst(tree.symbol());
+      }
+      else
+	super.getSymbolFor(tree);
+	//tree.symbol();
+    }
+
+  }
+}
+
+object Logger {
+  var file: java.io.Writer = null;
+
+  def setFile(name: String): Unit = {
+    file = new java.io.FileWriter(name);
+  }
+
+  def log(s: String): Unit = {
+    file.write(s + "\n");
+  }
+
+  def log(s1: String, s2: String): Unit = {
+    file.write(s1 + " " + "\n");
+  }
+
+  def flush: unit = {
+    file.flush();
+  }
+}
+
+} // package scala.tools.scalac.wholeprog
diff --git a/sources/scala/tools/scalac/wholeprog/MonomorphicCS.scala b/sources/scala/tools/scalac/wholeprog/MonomorphicCS.scala
new file mode 100644
index 0000000000..d4b40c884b
--- /dev/null
+++ b/sources/scala/tools/scalac/wholeprog/MonomorphicCS.scala
@@ -0,0 +1,405 @@
+/*     ____ ____  ____ ____  ______                                     *\
+**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
+**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2004, LAMP/EPFL              **
+** /_____/\____/\___/\____/____/                                        **
+\*                                                                      */
+
+/*
+**       The Whole Program analysis phase.
+**
+**       Identify monomorphic call sites in classes (where the receiver
+**       can always be statically determined).
+**
+** [iuli]   2.05.2004                                                   */
+
+import scalac.{Global => scalac_Global}
+import scalac.{Unit => scalac_Unit}
+import scalac.symtab._;
+import scalac.util._;
+import scala.collection.mutable._;
+import scalac.ast._;
+import scala.tools.scalac.wholeprog.graph.{Node => GNode};
+import scala.tools.scalac.wholeprog.graph._;
+
+package scala.tools.scalac.wholeprog {
+
+class MonomorphicCallSites(globall: scalac_Global, application: Set[Symbol]) {
+  type CallGraph = Graph[Symbol, MethodNode, CallEdge];
+  type CallGraphNode = GNode[Symbol, MethodNode];
+  type CallGraphEdge = Edge[Symbol, CallEdge];
+
+  private val global = globall;
+  val hierarchy = new Graph[Symbol, Symbol, String];
+  val callGraph = new CallGraph;
+
+  var instantiatedClasses = new HashSet[Symbol];
+
+  var inlinable: List[Tuple3[CallGraphNode, CallGraphNode, CallSite]] = Nil;
+
+
+  /** create the class inheritance hierarchy */
+  def buildClassHierarchy: Unit = {
+    application.foreach( (sym) => {
+      hierarchy.addNode(new GNode(sym, sym));
+    });
+
+    application.foreach( (sym) => {
+      val parents = sym.parents();
+
+      // the first "parent" is always the superclass? seems to be like that
+      val superclass = if (parents.length > 0) parents(0) else null;
+
+      parents.foreach( (p) => {
+	val e = new Edge[Symbol, String](sym, typeToSymbol(p));
+
+	e.info = if (p == superclass) "extends" else  "with";
+	hierarchy.addEdge(e);
+      });
+    });
+
+    if (!global.args.XdotFile.value.equals("$")) {
+      val file: java.io.Writer = new java.io.FileWriter("ch.dot");
+      file.write(hierarchy.toDotString);
+      file.flush();
+    }
+  }
+
+
+  def typeToSymbol(t: Type): Symbol = {
+    t match {
+      case Type$TypeRef(_, s, _) => if (s.isAbstractType()) typeToSymbol(t.bound()) else s;
+      case Type$SingleType(pre, sym) => typeToSymbol(sym.getType());
+      case Type$ThisType(sym) => sym;
+      case Type$PolyType(tparams, result) => typeToSymbol(result); // attention!
+      case Type$ConstantType(base, value) => typeToSymbol(base);
+      case Type$MethodType(vparams, result) => typeToSymbol(result);
+      case Type$CompoundType(_, _) => t.symbol();
+      case _ => { global.error("* Cannot handle base type " + t); null }
+    }
+  }
+
+  /** Identify and print monomoprhic callsites */
+  def monomorphicCallsites: Unit = {
+    val cg = callGraph;
+    var nr: int = 0;
+    var views: Int = 0;
+    var closures: Int = 0;
+
+    def logStatistics(e: CallGraphEdge): Unit = {
+      if (SymbolPrinter.fullName(cg.getNode(e.to).info.classz).startsWith("scala.Function"))
+	closures = closures + 1;
+      if (cg.getNode(e.to).info.method.name.toString().equals("view"))
+	views = views + 1;
+    }
+
+    def inlineCallSite(e: CallGraphEdge): Unit = {
+      val caller = cg.getNode(e.from);
+      val callee = cg.getNode(e.to);
+
+      if (canInline(caller, callee))
+	inlinable = new Tuple3(caller, callee, e.info.site) :: inlinable;
+    }
+
+    def canInline(caller: CallGraphNode, callee: CallGraphNode): boolean =
+      !callee.info.method.isInitializer() &&
+      caller.info.code != null &&
+      callee.info.code != null &&
+      !callee.info.method.isDeferred() &&
+      application.contains(caller.info.classz) &&
+      application.contains(callee.info.classz);
+
+    Logger.setFile("inlining.log");
+
+    Console.println("[start build callgraph]");
+    buildCallGraph;
+    Console.println("[end build callgraph]");
+
+    if (global.args.Xrta.value) {
+      // perform additional pruning
+      Console.println("[start RTA]");
+      rapidTypeAnalysis(instantiatedClasses);
+      Console.println("[end RTA]");
+    }
+
+    if (!global.args.XdotFile.value.equals("$"))
+      dumpCallGraph;
+
+    Console.println("[start Monomorphic call site identification]");
+    cg.nodes.foreach( (id, n) => {
+      n.info.callSites.foreach( (site) => {
+	val mcs = cg.getOutEdges(id).filter( e => e.info.site == site );
+
+	if (mcs.length == 1) {
+	  inlineCallSite(mcs.head);
+//	  Console.println("Monomorphic call-site: " + mcs.head.from + " " + mcs.head.to);
+	  logStatistics(mcs.head);
+	  nr = nr + 1;
+	}
+      });
+    });
+    Console.println("[end Monomorphic call site identification]");
+
+    Console.println("We identified " + nr + " monomorphic call-sites. ("
+		    + inlinable.length + " inlinable).");
+    Console.println("[closures = " + closures + ", views = " + views + "]");
+
+    if (global.args.Xinline.value) {
+      Console.println("[start inlining]");
+
+      doInline(inlinable);
+      Console.println("[end inlining]");
+    }
+  }
+
+  /** Perform a (buggy) form of rapid type analysis, as described in Sundaresan 99
+      The idea is that the call graph can be signifficanly pruned if all edges that go
+      into a method of a class that was never instantiated in the program are removed.
+
+      The assumption is that all "new" statements are known, and there is no other way to
+      instantiate classes. While the first one may be true for whole-program analysis
+      (and the -separate:no flag for scalac), the second might not hold: object classes
+      (singletons) are created "magically", and no "new" statement is parsed.
+  */
+  def rapidTypeAnalysis(instances: Set[Symbol]): Unit = {
+
+    /** instantiated classes include singleton classes */
+    def isInstatiated(s: Symbol): boolean =
+      instances.contains(s) ||
+      s.getType().isSubType(global.definitions.ANYVAL_TYPE()) ||
+      s.isModuleClass();
+
+    Console.println("Printing instantiated classes");
+    Logger.log("[RTA] Instantiated classes: ");
+    instantiatedClasses.foreach( s => Logger.log("[RTA] " + SymbolPrinter.fullName(s)));
+
+//     callGraph.visitDFS( (n: CallGraphNode) => {
+//       if (n.info.classz != null &&
+// 	  !isInstatiated(n.info.classz)) {
+// 	callGraph.removeEdges(callGraph.getInEdges(n.id));
+// 	Logger.log("[RTA] Removed inedges for " + SymbolPrinter.fullName(n.id));
+//       }
+//     });
+
+    Console.println("[Visiting call graph]");
+    callGraph.nodes.foreach( (id, n) => {
+      n.info.callSites.foreach( (site) => {
+	val targets = callGraph.getOutEdges(id).filter( e => e.info.site == site );
+
+	if (targets.length > 1) {
+	  // test for instantiation
+	  targets.foreach( (t) => if ( !isInstatiated(callGraph.getNode(t.to).info.classz) ) {
+	    callGraph.removeEdge(t);
+	    Logger.log("[RTA] Removed edge to " + SymbolPrinter.fullName(t.to));
+	  });
+	}
+      });
+    });
+  }
+
+  /** perform inlines */
+  def doInline(sites: List[Tuple3[CallGraphNode, CallGraphNode, CallSite]]): Unit = {
+    val transformer: Transformer = new InlineMethods(sites, global);
+
+    global.units.foreach( (u) => {
+      u.body = transformer.transform(u.body);
+    });
+
+    Console.println("We inlined " + transformer.asInstanceOf[InlineMethods].inlines + " callsites");
+    Logger.flush;
+  }
+
+  def buildCallGraph: Unit = {
+    createNodes(callGraph);
+    createEdges(callGraph);
+
+    // print call graph size
+    var nodes = 0;
+    var edges = 0;
+    var callsites = 0;
+
+    callGraph.nodes.foreach( (id, n) => {
+      nodes = nodes + 1;
+      callsites = callsites + n.info.callSites.length;
+      edges = edges + callGraph.getOutEdges(id).length;
+    });
+
+    Console.println("Call graph: " + nodes + " nodes, " +
+		    edges + " edges, [" /* + callGraph.edges.length */ + "]" +
+		    callsites + " callsites.");
+  }
+
+  def dumpCallGraph: Unit = {
+    val file: java.io.Writer = new java.io.FileWriter("callGraph.dot");
+    file.write(callGraph.toDotString);
+    file.flush();
+  }
+
+  def createNodes(cg: CallGraph): Unit = {
+    val trav: Traverser = new MethodNodeCreator(cg);
+
+    global.units.foreach( (u) => trav.traverse(u.body) );
+  }
+
+  def createEdges(cg: CallGraph): Unit = {
+    val trav: Traverser = new CallGraphEdgeTraverser(cg);
+
+    global.units.foreach( (u) => trav.traverse(u.body) );
+  }
+
+  /** Walk the nodes in the AST tree and creates nodes in the callgraph
+      corresponding to each method  */
+  class MethodNodeCreator(cg: CallGraph) extends Traverser {
+
+    override def traverse(tree: Tree): Unit = {
+      tree match {
+	case Tree$DefDef(_, name, _, _, _, _) => {
+	  val methSym = tree.symbol();
+
+	  cg.addNode(new CallGraphNode(methSym, new MethodNode(methSym, methSym.enclClass(), tree)));
+	}
+
+	case _ => ;
+      }
+
+      super.traverse(tree);
+    }
+  }
+
+
+  /** Walk all source code and create the call graph edges. */
+  class CallGraphEdgeTraverser(cg: CallGraph) extends Traverser {
+    var enclMethod: Symbol = null;
+
+    override def traverse(tree: Tree): Unit = {
+      var oldMethod: Symbol = enclMethod;
+
+      tree match {
+	case Tree$DefDef(_, name, _, _, _, _) => {
+	  oldMethod  = enclMethod;
+	  enclMethod = tree.symbol();
+
+	  super.traverse(tree);
+	}
+
+	case Tree$Create(qualifier, targs) => {
+//	  Console.println("Create: " + tree.symbol());
+	  assert(tree.symbol().isClass());
+	  instantiatedClasses += tree.symbol();
+
+	  traverse(qualifier);
+	}
+
+	case Tree$Apply(fun, args) => {
+
+	  if (enclMethod != null) {
+	    val targetMeth = fun.symbol();
+	    //assert(targetMeth != null, "Null target method for " + tree);
+	    if (targetMeth != null)
+	      createEdges(targetMeth, tree);
+//	    else
+//	      Console.println("Null symbol: " + tree);
+// 	    fun match {
+// 	      case Tree$Select(qualifier, selector) => {
+// 		val target = typeToSymbol(qualifier.getType());
+
+// 		if (target != null)
+// 		  createEdges(target, qualifier, selector, tree);
+// 	      }
+// 	      case _ => ;
+// 	    } /* else
+// 	      Console.println("No f***ing enclosing method - " + fun); */
+	  }
+
+	  traverse(fun);
+	  args.foreach( a => traverse(a));
+	};
+
+	case _ => super.traverse(tree);
+      }
+
+      enclMethod = oldMethod;
+    }
+
+    /** Add edges between the callsite and all possible targets. Possible
+      * targets are methods in the target class (or "nearest" superclass)
+      * or subclasses that override the specific method   */
+    def createEdges(targetMeth: Symbol, t: Tree): Unit = {
+      val site: CallSite = new CallSite(t);
+
+      def createEdgesForSubclasses(cls: Symbol): Unit = {
+	// walk all subclasses
+	hierarchy.getInEdges(cls).foreach( (e) => {
+	  val c = hierarchy.nodes(e.from).info;
+	  val it = c.members().iterator(true);
+
+	  while (it.hasNext()) {
+	    val m = it.next();
+	    if (m.overrides(targetMeth)) {
+	      if (cg.getNode(m) == null)
+		cg.addNode(new CallGraphNode(m, new MethodNode(m, c, null)));
+
+	      cg.addEdge(enclMethod, m).info = new CallEdge(t, site);
+	    }
+	  }
+
+//	  else Console.println("Found a subclass that is not a subtype: " +
+//			       SymbolPrinter.fullName(c) + "[" + c.getType() + "] not <: " +
+//			       targetCls + "[" + refType + "]");
+
+	  createEdgesForSubclasses(c);
+	});
+
+      }
+
+      // add callsite to node
+      if (cg.getNode(enclMethod) == null)
+	cg.addNode(new CallGraphNode(enclMethod, new MethodNode(enclMethod, enclMethod.enclClass(), null)));
+
+      cg.getNode(enclMethod).info.callSites = site :: cg.getNode(enclMethod).info.callSites;
+
+      if (targetMeth != Symbol.NONE) {
+	if (cg.getNode(targetMeth) == null)
+	  cg.addNode(new CallGraphNode(targetMeth, new MethodNode(targetMeth, targetMeth.enclClass(), null)));
+
+	cg.addEdge(enclMethod, targetMeth).info = new CallEdge(t, site);
+      }
+
+      createEdgesForSubclasses(targetMeth.enclClass());
+    }
+  }
+
+//  def makeNodeId(meth: Symbol): String = SymbolPrinter.fullName(meth);
+}
+
+/** Class that maintains information about nodes in the callgraph */
+case class MethodNode(method: Symbol, classz: Symbol, code: Tree) {
+  var callSites: List[CallSite] = Nil;
+
+  override def toString(): String = SymbolPrinter.fullName(method);
+}
+
+case class CallSite(t: Tree) {
+}
+
+class CallEdge(code: Tree, s: CallSite) {
+  val site = s;
+  override def toString() = "\"" + s.hashCode() + "\"";
+}
+
+
+object SymbolPrinter {
+  def fullName(s: Symbol): String = {
+
+    def fullName2(post: String, s: Symbol): String =
+      if (s.owner().isRoot())
+	s.name.toString() + "." + post
+      else
+	fullName2(s.name.toString() + "." + post, s.owner());
+
+    fullName2(s.name.toString(), s.owner())
+  }
+
+}
+
+
+} // package wholeprog
diff --git a/sources/scala/tools/scalac/wholeprog/PrintDotFile.scala b/sources/scala/tools/scalac/wholeprog/PrintDotFile.scala
new file mode 100644
index 0000000000..706274d52f
--- /dev/null
+++ b/sources/scala/tools/scalac/wholeprog/PrintDotFile.scala
@@ -0,0 +1,429 @@
+import scalac.{Unit => scalac_Unit}
+import scalac.ast._;
+import scalac.util.Name;
+
+package scala.tools.scalac.wholeprog {
+
+/**
+ * Print the AST into a dot file, which can be used by
+ * the graphviz "dot" tool to build a graph image. Useful for
+ * understanding the Abstract Syntax Tree.
+ */
+class PrintDotFile(_units: Array[scalac_Unit]) {
+  private val units = _units;
+  private var writer: java.io.Writer = null;
+
+  def makeDotFile(output: String): unit = {
+      val outputFile = new java.io.File(output);
+      writer = new java.io.FileWriter(outputFile);
+
+      writer.write("digraph tree {\nnode [style=filled, color=cadetblue2];\n");
+
+      units.foreach( (u:scalac_Unit) =>
+	u.body.foreach ( (t: Tree) => walk(t, null) ) );
+
+      writer.write("}\n");
+      writer.close();
+  }
+
+
+  def makeDotFile(output: String, tree: Tree): unit = {
+      writer = new java.io.FileWriter(output);
+
+      writer.write("digraph tree {\nnode [style=filled, color=cadetblue2];\n");
+
+      walk(tree, null);
+
+      writer.write("}\n");
+      writer.close();
+  }
+
+    def printNode(t: Object, label: String): unit = {
+      writer.write(t.hashCode().toString() + " [label = \"" + label + "\"];\n");
+    }
+
+
+    def printEdge(t1: Object, t2: Object, label: String): unit = {
+      if (t1 != null)
+	writer.write(t1.hashCode().toString() + " -> " + t2.hashCode().toString() +
+		     "[label= \"" + label + "\"];\n");
+    }
+
+    def printEdge(t1: Object, t2: Object): unit = printEdge(t1, t2, "");
+
+  def walk(t: Tree, parent: Tree, l: String): unit = {
+    t match {
+
+//      case Tree$Empty => {
+//	printNode(t, "Empty");
+//	printEdge(parent, t);
+//      }
+
+      case Tree$DocDef(comment, definition) => {
+	printNode(t, "DocDef");
+	printEdge(parent, t);
+
+	walk(definition, t);
+      }
+
+      case Tree$ClassDef(mods, name, tparams, vparams, tpe, template) => {
+	printNode(t, "ClassDef: " + name.toString());
+	printEdge(parent, t);
+
+	tparams.foreach( (p: Tree) => {
+	  walk(p, t);
+	});
+
+	vparams.foreach( (arr) => {
+	  (p: Tree) =>  walk(p, t);
+	});
+
+	walk(tpe, t);
+
+	walk(template, t);
+      }
+
+      case Tree$PackageDef(packaged, impl) => {
+	printNode(t, "PackageDef");
+	printEdge(parent, t);
+
+	walk(packaged, t);
+	walk(impl, t);
+      }
+
+      case Tree$ModuleDef(_, name, tpe, impl) => {
+	printNode(t, "ModuleDef: " + name.toString());
+	printEdge(parent, t);
+
+	walk(tpe, t);
+	walk(impl, t);
+      }
+
+      case Tree$ValDef(_, name, tpe, rhs) => {
+	printNode(t, "ValDef: " + name.toString());
+	printEdge(parent, t);
+
+	walk(tpe, t);
+	walk(rhs, t);
+      }
+
+      case Tree$PatDef(_, pat, rhs) => {
+	printNode(t, "PatDef");
+	printEdge(parent, t);
+
+	walk(pat, t);
+	walk(rhs, t);
+      }
+
+      case Tree$DefDef(_, name, tparams, vparams, tpe, rhs) => {
+	printNode(t, "DefDef: " + name.toString());
+	printEdge(parent, t);
+
+	tparams.foreach( (tt) =>  walk(tt, t) );
+
+	vparams.foreach( (at) => at.foreach( (tt) => walk(tt, t) ) );
+	walk(tpe, t);
+	walk(rhs, t);
+      }
+
+      case Tree$AbsTypeDef(_, name, rhs, lobound) => {
+	printNode(t, "AbsTypeDef: " + name.toString());
+	printEdge(parent, t);
+
+	walk(rhs, t);
+	walk(lobound, t);
+      }
+
+      case Tree$AliasTypeDef(_, name, tparams, rhs) => {
+	printNode(t, "AliasTypeDef: " + name.toString());
+	printEdge(parent, t);
+
+	tparams.foreach( (tt) => walk(tt, t) );
+	walk(rhs, t);
+      }
+
+      case Tree$Import(expr, selectors) => {
+	printNode(t, "Import");
+	printEdge(parent, t);
+
+	walk(expr, t);
+	selectors.foreach( (n: Name) => {
+	  printNode(n, "Name: " + n);
+	  printEdge(t, n);
+	});
+      }
+
+      case Tree$CaseDef(pat, guard, body) => {
+	printNode(t, "CaseDef");
+	printEdge(parent, t);
+
+	walk(pat, t);
+	walk(guard, t);
+	walk(body, t);
+      }
+
+      case Tree$Template(parents, body) => {
+	printNode(t, "Template");
+	printEdge(parent, t);
+
+	parents.foreach( (tt) => {
+	  walk(tt, t, "parent");
+	});
+
+	body.foreach( (tt) => {
+	  walk(tt, t, "body");
+	});
+      }
+
+      case Tree$LabelDef(name, params, rhs) => {
+	printNode(t, "LabelDef: " + name.toString());
+	printEdge(parent, t);
+
+	params.foreach( (tt) => walk(tt, t) );
+	walk(rhs, t);
+      }
+
+      case Tree$Block(stats, expr) => {
+	printNode(t, "Block");
+	printEdge(parent, t);
+
+	stats.foreach( (tt) => walk(tt, t) );
+	walk(expr, t);
+      }
+
+      case Tree$Sequence(trees) => {
+	printNode(t, "Sequence");
+	printEdge(parent, t);
+
+	trees.foreach( (tt) => walk(tt, t) );
+      }
+
+      case Tree$Alternative(trees) => {
+	printNode(t, "Alternative");
+	printEdge(parent, t);
+
+	trees.foreach( (tt) => walk(tt, t) );
+      }
+
+      case Tree$Bind(name, rhs) => {
+	printNode(t, "Bind: " + name.toString());
+	printEdge(parent, t);
+
+	walk(rhs, t);
+      }
+
+      case Tree$Visitor(cases) => {
+	printNode(t, "Visitor");
+	printEdge(parent, t);
+
+	cases.foreach( (tt) => walk(tt, t) );
+      }
+
+      case Tree$Function(vparams, body) => {
+	printNode(t, "Function");
+	printEdge(parent, t);
+
+	vparams.foreach( (tt) => walk(tt, t) );
+	walk(body, t);
+      }
+
+      case Tree$Assign(lhs, rhs) => {
+	printNode(t, "Assign");
+	printEdge(parent, t);
+
+	walk(lhs, t);
+	walk(rhs, t);
+      }
+
+      case Tree$If(cond, thenp, elsep) => {
+	printNode(t, "If");
+	printEdge(parent, t);
+
+	walk(cond, t);
+	walk(thenp, t);
+	walk(elsep, t);
+      }
+
+      // we ignore the "tags" array...
+      case Tree$Switch(test, _, bodies, otherwise) => {
+	printNode(t, "Switch");
+	printEdge(parent, t);
+
+	walk(test, t);
+	bodies.foreach( (tt) => walk(tt, t) );
+	walk(otherwise, t);
+      }
+
+      case Tree$Return(expr) => {
+	printNode(t, "Return");
+	printEdge(parent, t);
+
+	walk(expr, t);
+      }
+
+      case Tree$Throw(expr) => {
+	printNode(t, "Throw");
+	printEdge(parent, t);
+
+	walk(expr, t);
+      }
+
+      case Tree$New(template) => {
+	printNode(t, "New");
+	printEdge(parent, t);
+
+	walk(template, t);
+      }
+
+      case Tree$Create(qualifier, targs) => {
+	printNode(t, "Create");
+	printEdge(parent, t);
+
+	walk(qualifier, t);
+	targs.foreach( (a) => walk(a, t) );
+      }
+
+      case Tree$Typed(expr, tpe) => {
+	printNode(t, "Typed");
+	printEdge(parent, t);
+
+	walk(expr, t);
+	walk(tpe, t);
+      }
+
+      case Tree$TypeApply(fun, args) => {
+	printNode(t, "TypeApply");
+	printEdge(parent, t, l);
+
+	walk(fun, t);
+
+	args.foreach( (tt) => walk(tt, t) );
+      }
+
+      case Tree$Apply(fun, args) => {
+	printNode(t, "Apply");
+	printEdge(parent, t, l);
+
+	walk(fun, t, "fun");
+
+	args.foreach( (tt) => walk(tt, t, "arg") );
+      }
+
+      case Tree$Super(qualifier, mixin) => {
+	printNode(t, "Super");
+	printEdge(parent, t);
+
+	printNode(qualifier, "Qualifier: " + qualifier.toString());
+	printNode(mixin, "Mixin: " + mixin.toString());
+
+	printEdge(t, qualifier);
+	printEdge(t, mixin);
+      }
+
+      case Tree$This(qualifier) => {
+	printNode(t, "This");
+	printEdge(parent, t);
+
+	printNode(qualifier, "Qualifier: " + qualifier);
+	printEdge(t, qualifier);
+      }
+
+      case Tree$Select(qualifier, selector) => {
+	printNode(t, "Select");
+	printEdge(parent, t, l);
+
+//	printNode(qualifier, "Qualifier: " + qualifier.toString());
+//	printEdge(t, qualifier);
+//	printNode(qualifier, "Qualifier");
+//	Console.println("--qualifier: " + qualifier + " : " + selector);
+	walk(qualifier, t);
+
+	printNode(selector, "Selector: " + selector.toString());
+	printEdge(t, selector);
+      }
+
+      case Tree$Ident(name) => {
+	printNode(t, "Ident");
+	printEdge(parent, t);
+
+	printNode(name, "Name: " + name);
+	printEdge(t, name);
+      }
+
+      case Tree$Literal(value) => {
+	printNode(t, "Literal");
+	printEdge(parent, t);
+
+	printNode(value, "Value: " + value);
+	printEdge(t, value);
+      }
+
+      case Tree$TypeTerm() => {
+	printNode(t, "TypeTerm: " + t.getType());
+	printEdge(parent, t);
+      }
+
+      case Tree$SingletonType(ref) => {
+	printNode(t, "SingletonType");
+	printEdge(parent, t);
+
+	walk(ref, t);
+      }
+
+      case Tree$SelectFromType(qual, selector) => {
+	printNode(t, "SelectFromType");
+	printEdge(parent, t);
+
+	walk(qual, t);
+	printNode(selector, "Selector: " + selector);
+	printEdge(t, selector);
+      }
+
+      case Tree$FunType(argtypes, restpe) => {
+	printNode(t, "FunType");
+	printEdge(parent, t);
+
+	argtypes.foreach( (tt) => walk(tt, t) );
+	walk(restpe, t);
+      }
+
+      case Tree$CompoundType(parents, refinements) => {
+	printNode(t, "CompoundType");
+	printEdge(parent, t);
+
+	parents.foreach( (tt) => walk(tt, t) );
+	refinements.foreach( (tt) => walk(tt, t) );
+      }
+
+      case Tree$AppliedType(tpe, args) => {
+	printNode(t, "AppliedType");
+	printEdge(parent, t);
+
+	walk(tpe, t);
+	args.foreach( (tt) => walk(tt, t) );
+      }
+
+      case Tree$Try(block, catcher, finalizer) => {
+	printNode(t, "Try");
+	printEdge(parent, t);
+
+	walk(block, t);
+	walk(catcher, t);
+	walk(finalizer, t);
+      }
+
+      case _ => {
+//	Console.println(t.toString());
+//	assert(false, t.toString());
+//	printNode(t.symbol().name.toString(), "Unknown");
+//	if (parent != null)
+//	  printEdge(parent.symbol().name.toString(), t.symbol().name.toString());
+      }
+    }
+  }
+
+  def walk(t: Tree, parent: Tree): unit = walk(t, parent, "");
+
+} // class PrintDotFile
+
+} // package scala.tools.scalac.wholeprog
diff --git a/sources/scala/tools/scalac/wholeprog/graph/Graph.scala b/sources/scala/tools/scalac/wholeprog/graph/Graph.scala
new file mode 100644
index 0000000000..59c6f3ffdb
--- /dev/null
+++ b/sources/scala/tools/scalac/wholeprog/graph/Graph.scala
@@ -0,0 +1,189 @@
+/*     ____ ____  ____ ____  ______                                     *\
+**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
+**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2002, LAMP/EPFL              **
+** /_____/\____/\___/\____/____/                                        **
+\*                                                                      */
+
+// $Id$
+
+import scala.collection.mutable._;
+
+package scala.tools.scalac.wholeprog.graph {
+
+
+/** Defualt implementation for Node objects, which can have any
+  * identifier */
+class Node[id_t, info_t](i: id_t, nn: info_t) {
+  var info: info_t = nn;
+  val id: id_t = i;
+
+  override def toString(): String = "\"" + id.hashCode() +
+    "\"[ label = \"" + info + "\" ]";
+}
+
+/** Default implementation for edges. It takes two parameters, the
+  * start and the end identifiers for the nodes it connects  */
+class Edge[id_t, info_t](start: id_t, end: id_t) {
+  val from = start;
+  val to = end;
+  var info: info_t = _;
+
+  override def toString(): String =  "\"" + start.hashCode() + "\" -> " + "\""
+      + end.hashCode() + "\"[ label = \"" + info + "\" ]";
+}
+
+
+class InvalidEdgeException(from: String, to: String) extends java.lang.Exception {
+  override def toString(): String = "Edge [" + from + " -> " + to +
+      "] references non existent nodes";
+}
+
+
+/** The Graph class, parameterized with the node and edge types
+  * The id_t is the type of the identifier of nodes. This is used
+  * when retrieving nodes from the graph. The node_t is the type of
+    nodes, which have to subtype the Node trait. edge_t is the type
+    of edges, which again is a subtype of Edge.   */
+
+class Graph[id_t, node_info_t, edge_info_t] {
+  type node_t = Node[id_t, node_info_t];
+  type edge_t = Edge[id_t, edge_info_t];
+
+  var nodes: HashMap[id_t, node_t] = new HashMap[id_t, node_t];
+  var edges: List[edge_t] = Nil;
+
+  val inEdges: HashMap[id_t, List[edge_t]] = new HashMap[id_t, List[edge_t]];
+  val outEdges: HashMap[id_t, List[edge_t]] = new HashMap[id_t, List[edge_t]];
+
+
+  def addNode(n: node_t): Unit = {
+    nodes += n.id -> n;
+    inEdges += n.id -> Nil;
+    outEdges += n.id -> Nil;
+  }
+
+  def addEdge(from: id_t, to: id_t): edge_t = addEdge(new Edge(from, to));
+
+  def addEdge(e: edge_t): edge_t = {
+    if ((nodes contains e.from) && (nodes contains e.to)) {
+      edges = e :: edges;
+      addEdgeToIncidenceMap(outEdges, e, getNode(e.from));
+      addEdgeToIncidenceMap(inEdges, e, getNode(e.to));
+    } //else
+//      throw new InvalidEdgeException(e.start, e.end);
+    e
+  }
+
+  def removeEdge(e: edge_t): edge_t = {
+    edges = edges.remove( ee => e == ee );
+    outEdges += e.from -> getOutEdges(e.from).remove( ee => e == ee);
+    inEdges  += e.to -> getInEdges(e.to).remove(ee => e == ee);
+
+    e
+  }
+
+  def removeEdges(es: List[edge_t]): Unit = es match {
+    case Nil => ();
+    case e :: ee => { removeEdge(e); removeEdges(ee) }
+  }
+
+  def addEdgeToIncidenceMap(map: HashMap[id_t, List[edge_t]], e: edge_t, n: node_t): Unit = {
+    map.get(n.id) match {
+      case Some(l) => map += n.id -> (e :: l);
+      case None    => map += n.id -> (e :: Nil);
+    }
+  }
+
+  def getOutEdges(node: id_t): List[edge_t] = outEdges.get(node) match {
+    case Some(l) => l;
+    case None    => Nil;
+  }
+
+  def getInEdges(node: id_t): List[edge_t] = inEdges.get(node) match {
+    case Some(l) => l;
+    case None    => Nil;
+  }
+
+  def visitDFS(f: (node_t) => Unit): Unit = {
+    val visited = new HashSet[node_t];
+    var i = nodeIterator;
+
+    while (i.hasNext) {
+      visitDFS(i.next, f, visited);
+    }
+  }
+
+  private def visitDFS(currentNode: node_t, f: (node_t) => Unit, visited: Set[node_t]): Unit = {
+    if (!visited.contains(currentNode)) {
+      visited += currentNode;
+      f(currentNode);
+
+      getOutEdges(currentNode.id) foreach { (e) => {
+	visitDFS(getNode(e.to), f, visited);
+      }}
+    }
+  }
+
+  def getNode(id: id_t): node_t = nodes.get(id) match {
+    case Some(n) => n;
+    case None    => null;
+  }
+
+  def getRootNodes: Iterator[node_t] = {
+    for (val elem <- nodes.elements; getInEdges(elem._2.id) == Nil)
+	yield elem._2;
+  }
+
+  /** Remove all nodes with degree 0. Return the graph. */
+  def prune: Graph[id_t, node_info_t, edge_info_t] = {
+    nodes.filter( (id, n) => inEdges(id) != Nil || outEdges(id) != Nil );
+
+    this
+  }
+
+  /* graph visualization  */
+
+  override def toString(): String = {
+    var s = "";
+
+    edges.foreach( (e) => s = s + e + "\n" );
+    s
+  }
+
+  def toDotString: String = {
+    var str = "digraph grph {\n";
+
+    val it = nodeIterator;
+    while (it.hasNext) {
+      val node = it.next;
+      str = str + node + "\n";// + " [label = \"" + node.id + "\"];\n";
+    }
+
+    // edges
+    edges.foreach( (e) => str = str + e + "\n" );
+    str + "}\n";
+  }
+
+  def nodeIterator: GraphIterator = new GraphIterator();
+
+  /** Iterator for graph nodes */
+  class GraphIterator extends Iterator[node_t] {
+    val elem = nodes.elements;
+
+    override def hasNext: Boolean = elem.hasNext;
+    override def next: node_t = elem.next._2;
+  }
+
+
+  def consistencyCheck: Unit = {
+    edges.foreach( (e) => {
+      if ( !(getOutEdges(e.from) contains e) )
+	Console.println("Edge " + e + " not found in out edges of " + e.from);
+
+      if ( !(getInEdges(e.to) contains e) )
+	Console.println("Edge " + e + " not found in in edges of " + e.to);
+    });
+  }
+}
+
+} // graph package