Report use of possibly uninitialized variables, fixes bug 508477 and bug

2008-11-14  Jürg Billeter  <j@bitron.ch>

	* vala/Makefile.am:
	* vala/valaassignment.vala:
	* vala/valabasicblock.vala:
	* vala/valabinaryexpression.vala:
	* vala/valacastexpression.vala:
	* vala/valacatchclause.vala:
	* vala/valacodenode.vala:
	* vala/valadeclarationstatement.vala:
	* vala/valaelementaccess.vala:
	* vala/valaexpressionstatement.vala:
	* vala/valaflowanalyzer.vala:
	* vala/valaforeachstatement.vala:
	* vala/valainvocationexpression.vala:
	* vala/valamemberaccess.vala:
	* vala/valaobjectcreationexpression.vala:
	* vala/valaparenthesizedexpression.vala:
	* vala/valaphifunction.vala:
	* vala/valapointerindirection.vala:
	* vala/valareferencetransferexpression.vala:
	* vala/valareturnstatement.vala:
	* vala/valathrowstatement.vala:
	* vala/valaunaryexpression.vala:
	* compiler/valacompiler.vala:

	Report use of possibly uninitialized variables, fixes bug 508477
	and bug 556861

svn path=/trunk/; revision=2018

24 files changed, 630 insertions, 21 deletions

diff --git a/ChangeLog b/ChangeLog
index cb527202d..e7b664446 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,34 @@
 2008-11-14  Jürg Billeter  <j@bitron.ch>
 
+	* vala/Makefile.am:
+	* vala/valaassignment.vala:
+	* vala/valabasicblock.vala:
+	* vala/valabinaryexpression.vala:
+	* vala/valacastexpression.vala:
+	* vala/valacatchclause.vala:
+	* vala/valacodenode.vala:
+	* vala/valadeclarationstatement.vala:
+	* vala/valaelementaccess.vala:
+	* vala/valaexpressionstatement.vala:
+	* vala/valaflowanalyzer.vala:
+	* vala/valaforeachstatement.vala:
+	* vala/valainvocationexpression.vala:
+	* vala/valamemberaccess.vala:
+	* vala/valaobjectcreationexpression.vala:
+	* vala/valaparenthesizedexpression.vala:
+	* vala/valaphifunction.vala:
+	* vala/valapointerindirection.vala:
+	* vala/valareferencetransferexpression.vala:
+	* vala/valareturnstatement.vala:
+	* vala/valathrowstatement.vala:
+	* vala/valaunaryexpression.vala:
+	* compiler/valacompiler.vala:
+
+	Report use of possibly uninitialized variables, fixes bug 508477
+	and bug 556861
+
+2008-11-14  Jürg Billeter  <j@bitron.ch>
+
 	* vala/valagenieparser.vala:
 	* vala/valainterface.vala:
 	* vala/valainterfacewriter.vala:
diff --git a/compiler/valacompiler.vala b/compiler/valacompiler.vala
index 2c8ecbb0a..4983deddb 100644
--- a/compiler/valacompiler.vala
+++ b/compiler/valacompiler.vala
@@ -256,8 +256,8 @@ class Vala.Compiler {
 			return quit ();
 		}
 
-		var cfg_builder = new CFGBuilder ();
-		cfg_builder.build_cfg (context);
+		var flow_analyzer = new FlowAnalyzer ();
+		flow_analyzer.analyze (context);
 
 		if (Report.get_errors () > 0) {
 			return quit ();
diff --git a/vala/Makefile.am b/vala/Makefile.am
index 1963e31e9..b53002042 100644
--- a/vala/Makefile.am
+++ b/vala/Makefile.am
@@ -30,7 +30,6 @@ libvalacore_la_VALASOURCES = \
 	valabreakstatement.vala \
 	valacastexpression.vala \
 	valacatchclause.vala \
-	valacfgbuilder.vala \
 	valacharacterliteral.vala \
 	valaclass.vala \
 	valaclasstype.vala \
@@ -64,6 +63,7 @@ libvalacore_la_VALASOURCES = \
 	valaexpressionstatement.vala \
 	valafield.vala \
 	valafieldprototype.vala \
+	valaflowanalyzer.vala \
 	valaforeachstatement.vala \
 	valaformalparameter.vala \
 	valaforstatement.vala \
@@ -99,6 +99,7 @@ libvalacore_la_VALASOURCES = \
 	valaobjecttypesymbol.vala \
 	valaparenthesizedexpression.vala \
 	valaparser.vala \
+	valaphifunction.vala \
 	valapointerindirection.vala \
 	valapointertype.vala \
 	valapostfixexpression.vala \
diff --git a/vala/valaassignment.vala b/vala/valaassignment.vala
index 04af2b659..f45a95e28 100644
--- a/vala/valaassignment.vala
+++ b/vala/valaassignment.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents an assignment expression in the source code.
@@ -376,6 +376,26 @@ public class Vala.Assignment : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		right.get_defined_variables (collection);
+		left.get_defined_variables (collection);
+		var local = left.symbol_reference as LocalVariable;
+		if (local != null) {
+			collection.add (local);
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		var ma = left as MemberAccess;
+		var ea = left as ElementAccess;
+		if (ma != null && ma.inner != null) {
+			ma.inner.get_used_variables (collection);
+		} else if (ea != null) {
+			ea.get_used_variables (collection);
+		}
+		right.get_used_variables (collection);
+	}
 }
 	
 public enum Vala.AssignmentOperator {
diff --git a/vala/valabasicblock.vala b/vala/valabasicblock.vala
index 4dd9792ee..2602f5968 100644
--- a/vala/valabasicblock.vala
+++ b/vala/valabasicblock.vala
@@ -30,9 +30,17 @@ using Gee;
 public class Vala.BasicBlock {
 	private Gee.List<CodeNode> nodes = new ArrayList<CodeNode> ();
 
+	// control flow graph
 	private Gee.List<weak BasicBlock> predecessors = new ArrayList<weak BasicBlock> ();
 	private Gee.List<BasicBlock> successors = new ArrayList<BasicBlock> ();
 
+	// dominator tree
+	public BasicBlock parent { get; private set; }
+	Gee.List<BasicBlock> children = new ArrayList<BasicBlock> ();
+	Set<BasicBlock> df = new HashSet<BasicBlock> ();
+
+	Set<PhiFunction> phi_functions = new HashSet<PhiFunction> ();
+
 	public BasicBlock () {
 	}
 
@@ -46,6 +54,10 @@ public class Vala.BasicBlock {
 		nodes.add (node);
 	}
 
+	public Gee.List<CodeNode> get_nodes () {
+		return nodes;
+	}
+
 	public void connect (BasicBlock target) {
 		if (!successors.contains (target)) {
 			successors.add (target);
@@ -62,4 +74,29 @@ public class Vala.BasicBlock {
 	public Gee.List<weak BasicBlock> get_successors () {
 		return new ReadOnlyList<weak BasicBlock> (successors);
 	}
+
+	public void add_child (BasicBlock block) {
+		children.add (block);
+		block.parent = this;
+	}
+
+	public Gee.List<BasicBlock> get_children () {
+		return children;
+	}
+
+	public void add_dominator_frontier (BasicBlock block) {
+		df.add (block);
+	}
+
+	public Gee.Set<BasicBlock> get_dominator_frontier () {
+		return df;
+	}
+
+	public void add_phi_function (PhiFunction phi) {
+		phi_functions.add (phi);
+	}
+
+	public Gee.Set<PhiFunction> get_phi_functions () {
+		return phi_functions;
+	}
 }
diff --git a/vala/valabinaryexpression.vala b/vala/valabinaryexpression.vala
index a3743c715..200bb711d 100644
--- a/vala/valabinaryexpression.vala
+++ b/vala/valabinaryexpression.vala
@@ -300,6 +300,16 @@ public class Vala.BinaryExpression : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		left.get_defined_variables (collection);
+		right.get_defined_variables (collection);
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		left.get_used_variables (collection);
+		right.get_used_variables (collection);
+	}
 }
 
 public enum Vala.BinaryOperator {
diff --git a/vala/valacastexpression.vala b/vala/valacastexpression.vala
index d94041ca3..4f94832ce 100644
--- a/vala/valacastexpression.vala
+++ b/vala/valacastexpression.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a type cast in the source code.
@@ -123,4 +123,12 @@ public class Vala.CastExpression : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		inner.get_defined_variables (collection);
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		inner.get_used_variables (collection);
+	}
 }
diff --git a/vala/valacatchclause.vala b/vala/valacatchclause.vala
index 0cb7d0189..e1c7e4b92 100644
--- a/vala/valacatchclause.vala
+++ b/vala/valacatchclause.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a catch clause in a try statement in the source code.
@@ -119,4 +119,8 @@ public class Vala.CatchClause : CodeNode {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		collection.add (error_variable);
+	}
 }
diff --git a/vala/valacodenode.vala b/vala/valacodenode.vala
index 920eecfe3..88e21dde4 100644
--- a/vala/valacodenode.vala
+++ b/vala/valacodenode.vala
@@ -177,4 +177,10 @@ public abstract class Vala.CodeNode {
 
 		return str.append (" */").str;
 	}
+
+	public virtual void get_defined_variables (Collection<LocalVariable> collection) {
+	}
+
+	public virtual void get_used_variables (Collection<LocalVariable> collection) {
+	}
 }
diff --git a/vala/valadeclarationstatement.vala b/vala/valadeclarationstatement.vala
index a11449892..0cc28fbd7 100644
--- a/vala/valadeclarationstatement.vala
+++ b/vala/valadeclarationstatement.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a local variable or constant declaration statement in the source code.
@@ -71,4 +71,19 @@ public class Vala.DeclarationStatement : CodeNode, Statement {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		var local = declaration as LocalVariable;
+		if (local != null && local.initializer != null) {
+			local.initializer.get_defined_variables (collection);
+			collection.add (local);
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		var local = declaration as LocalVariable;
+		if (local != null && local.initializer != null) {
+			local.initializer.get_used_variables (collection);
+		}
+	}
 }
diff --git a/vala/valaelementaccess.vala b/vala/valaelementaccess.vala
index 296103b25..c18363c96 100644
--- a/vala/valaelementaccess.vala
+++ b/vala/valaelementaccess.vala
@@ -208,4 +208,18 @@ public class Vala.ElementAccess : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		container.get_defined_variables (collection);
+		foreach (Expression index in indices) {
+			index.get_defined_variables (collection);
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		container.get_used_variables (collection);
+		foreach (Expression index in indices) {
+			index.get_used_variables (collection);
+		}
+	}
 }
diff --git a/vala/valaexpressionstatement.vala b/vala/valaexpressionstatement.vala
index 6dc66df31..1981624a2 100644
--- a/vala/valaexpressionstatement.vala
+++ b/vala/valaexpressionstatement.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * A code statement that evaluates a given expression. The value computed by the
@@ -103,4 +103,12 @@ public class Vala.ExpressionStatement : CodeNode, Statement {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		expression.get_defined_variables (collection);
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		expression.get_used_variables (collection);
+	}
 }
diff --git a/vala/valacfgbuilder.vala b/vala/valaflowanalyzer.vala
index fe65091e7..84026cb75 100644
--- a/vala/valacfgbuilder.vala
+++ b/vala/valaflowanalyzer.vala
@@ -1,4 +1,4 @@
-/* valacfgbuilder.vala
+/* valaflowanalyzer.vala
  *
  * Copyright (C) 2008  Jürg Billeter
  *
@@ -26,7 +26,7 @@ using Gee;
 /**
  * Code visitor building the control flow graph.
  */
-public class Vala.CFGBuilder : CodeVisitor {
+public class Vala.FlowAnalyzer : CodeVisitor {
 	private class JumpTarget {
 		public bool is_break_target { get; set; }
 		public bool is_continue_target { get; set; }
@@ -74,7 +74,11 @@ public class Vala.CFGBuilder : CodeVisitor {
 	private bool unreachable_reported;
 	private Gee.List<JumpTarget> jump_stack = new ArrayList<JumpTarget> ();
 
-	public CFGBuilder () {
+	Map<Symbol, Gee.List<LocalVariable>> var_map;
+	Set<LocalVariable> used_vars;
+	Map<LocalVariable, PhiFunction> phi_functions;
+
+	public FlowAnalyzer () {
 	}
 
 	/**
@@ -82,7 +86,7 @@ public class Vala.CFGBuilder : CodeVisitor {
 	 *
 	 * @param context a code context
 	 */
-	public void build_cfg (CodeContext context) {
+	public void analyze (CodeContext context) {
 		this.context = context;
 
 		/* we're only interested in non-pkg source files */
@@ -159,6 +163,308 @@ public class Vala.CFGBuilder : CodeVisitor {
 
 			current_block.connect (m.exit_block);
 		}
+
+		build_dominator_tree (m);
+		build_dominator_frontier (m);
+		insert_phi_functions (m);
+		check_variables (m);
+	}
+
+	Gee.List<BasicBlock> get_depth_first_list (Method m) {
+		var list = new ArrayList<BasicBlock> ();
+		depth_first_traverse (m.entry_block, list);
+		return list;
+	}
+
+	void depth_first_traverse (BasicBlock current, Gee.List<BasicBlock> list) {
+		if (current in list) {
+			return;
+		}
+		list.add (current);
+		foreach (BasicBlock succ in current.get_successors ()) {
+			depth_first_traverse (succ, list);
+		}
+	}
+
+	void build_dominator_tree (Method m) {
+		// set dom(n) = {E,1,2...,N,X} forall n
+		var dom = new HashMap<BasicBlock, Set<BasicBlock>> ();
+		var block_list = get_depth_first_list (m);
+		foreach (BasicBlock block in block_list) {
+			var block_set = new HashSet<BasicBlock> ();
+			foreach (BasicBlock b in block_list) {
+				block_set.add (b);
+			}
+			dom.set (block, block_set);
+		}
+
+		// set dom(E) = {E}
+		var entry_dom_set = new HashSet<BasicBlock> ();
+		entry_dom_set.add (m.entry_block);
+		dom.set (m.entry_block, entry_dom_set);
+
+		bool changes = true;
+		while (changes) {
+			changes = false;
+			foreach (BasicBlock block in block_list) {
+				// intersect dom(pred) forall pred: pred = predecessor(s)
+				var dom_set = new HashSet<BasicBlock> ();
+				bool first = true;
+				foreach (BasicBlock pred in block.get_predecessors ()) {
+					var pred_dom_set = dom.get (pred);
+					if (first) {
+						foreach (BasicBlock dom_block in pred_dom_set) {
+							dom_set.add (dom_block);
+						}
+						first = false;
+					} else {
+						var remove_queue = new ArrayList<BasicBlock> ();
+						foreach (BasicBlock dom_block in dom_set) {
+							if (!(dom_block in pred_dom_set)) {
+								remove_queue.add (dom_block);
+							}
+						}
+						foreach (BasicBlock dom_block in remove_queue) {
+							dom_set.remove (dom_block);
+						}
+					}
+				}
+				// unite with s
+				dom_set.add (block);
+
+				// check for changes
+				if (dom.get (block).size != dom_set.size) {
+					changes = true;
+				} else {
+					foreach (BasicBlock dom_block in dom.get (block)) {
+						if (!(dom_block in dom_set)) {
+							changes = true;
+						}
+					}
+				}
+				// update set in map
+				dom.set (block, dom_set);
+			}
+		}
+
+		// build tree
+		foreach (BasicBlock block in block_list) {
+			if (block == m.entry_block) {
+				continue;
+			}
+
+			BasicBlock immediate_dominator = null;
+			foreach (BasicBlock dominator in dom.get (block)) {
+				if (dominator == block) {
+					continue;
+				}
+
+				if (immediate_dominator == null) {
+					immediate_dominator = dominator;
+				} else {
+					// if immediate_dominator dominates dominator,
+					// update immediate_dominator
+					if (immediate_dominator in dom.get (dominator)) {
+						immediate_dominator = dominator;
+					}
+				}
+			}
+
+			immediate_dominator.add_child (block);
+		}
+	}
+
+	void build_dominator_frontier (Method m) {
+		var block_list = get_depth_first_list (m);
+		for (int i = block_list.size - 1; i >= 0; i--) {
+			var block = block_list[i];
+
+			foreach (BasicBlock succ in block.get_successors ()) {
+				// if idom(succ) != block
+				if (succ.parent != block) {
+					block.add_dominator_frontier (succ);
+				}
+			}
+
+			foreach (BasicBlock child in block.get_children ()) {
+				foreach (BasicBlock child_frontier in child.get_dominator_frontier ()) {
+					// if idom(child_frontier) != block
+					if (child_frontier.parent != block) {
+						block.add_dominator_frontier (child_frontier);
+					}
+				}
+			}
+		}
+	}
+
+	Map<LocalVariable, Set<BasicBlock>> get_assignment_map (Method m) {
+		var map = new HashMap<LocalVariable, Set<BasicBlock>> ();
+		foreach (BasicBlock block in get_depth_first_list (m)) {
+			var defined_variables = new ArrayList<LocalVariable> ();
+			foreach (CodeNode node in block.get_nodes ()) {
+				node.get_defined_variables (defined_variables);
+			}
+
+			foreach (LocalVariable local in defined_variables) {
+				var block_set = map.get (local);
+				if (block_set == null) {
+					block_set = new HashSet<BasicBlock> ();
+					map.set (local, block_set);
+				}
+				block_set.add (block);
+			}
+		}
+		return map;
+	}
+
+	void insert_phi_functions (Method m) {
+		var assign = get_assignment_map (m);
+
+		int counter = 0;
+		var work_list = new ArrayList<BasicBlock> ();
+
+		var added = new HashMap<BasicBlock, int> ();
+		var phi = new HashMap<BasicBlock, int> ();
+		foreach (BasicBlock block in get_depth_first_list (m)) {
+			added.set (block, 0);
+			phi.set (block, 0);
+		}
+
+		foreach (LocalVariable local in assign.get_keys ()) {
+			counter++;
+			foreach (BasicBlock block in assign.get (local)) {
+				work_list.add (block);
+				added.set (block, counter);
+			}
+			while (work_list.size > 0) {
+				BasicBlock block = work_list.get (0);
+				work_list.remove_at (0);
+				foreach (BasicBlock frontier in block.get_dominator_frontier ()) {
+					int blockPhi = phi.get (frontier);
+					if (blockPhi < counter) {
+						frontier.add_phi_function (new PhiFunction (local, frontier.get_predecessors ().size));
+						phi.set (frontier, counter);
+						int block_added = added.get (frontier);
+						if (block_added < counter) {
+							added.set (frontier, counter);
+							work_list.add (frontier);
+						}
+					}
+				}
+			}
+		}
+	}
+
+	void check_variables (Method m) {
+		var_map = new HashMap<Symbol, Gee.List<LocalVariable>>();
+		used_vars = new HashSet<LocalVariable> ();
+		phi_functions = new HashMap<LocalVariable, PhiFunction> ();
+
+		check_block_variables (m, m.entry_block);
+
+		// check for variables used before initialization
+		var used_vars_queue = new ArrayList<LocalVariable> ();
+		foreach (LocalVariable local in used_vars) {
+			used_vars_queue.add (local);
+		}
+		while (used_vars_queue.size > 0) {
+			LocalVariable used_var = used_vars_queue[0];
+			used_vars_queue.remove_at (0);
+
+			PhiFunction phi = phi_functions.get (used_var);
+			if (phi != null) {
+				foreach (LocalVariable local in phi.operands) {
+					if (local == null) {
+						Report.error (used_var.source_reference, "use of possibly unassigned local variable `%s'".printf (used_var.name));
+						continue;
+					}
+					if (!(local in used_vars)) {
+						local.source_reference = used_var.source_reference;
+						used_vars.add (local);
+						used_vars_queue.add (local);
+					}
+				}
+			}
+		}
+	}
+
+	void check_block_variables (Method m, BasicBlock block) {
+		foreach (PhiFunction phi in block.get_phi_functions ()) {
+			LocalVariable versioned_var = process_assignment (m, var_map, phi.original_variable);
+
+			phi_functions.set (versioned_var, phi);
+		}
+
+		foreach (CodeNode node in block.get_nodes ()) {
+			var used_variables = new ArrayList<LocalVariable> ();
+			node.get_used_variables (used_variables);
+			
+			foreach (LocalVariable var_symbol in used_variables) {
+				var variable_stack = var_map.get (var_symbol);
+				if (variable_stack == null || variable_stack.size == 0) {
+					Report.error (node.source_reference, "use of possibly unassigned local variable `%s'".printf (var_symbol.name));
+					continue;
+				}
+				var versioned_local = variable_stack.get (variable_stack.size - 1);
+				if (!(versioned_local in used_vars)) {
+					versioned_local.source_reference = node.source_reference;
+				}
+				used_vars.add (versioned_local);
+			}
+
+			var defined_variables = new ArrayList<LocalVariable> ();
+			node.get_defined_variables (defined_variables);
+
+			foreach (LocalVariable local in defined_variables) {
+				process_assignment (m, var_map, local);
+			}
+		}
+
+		foreach (BasicBlock succ in block.get_successors ()) {
+			int j = 0;
+			foreach (BasicBlock pred in succ.get_predecessors ()) {
+				if (pred == block) {
+					break;
+				}
+				j++;
+			}
+
+			foreach (PhiFunction phi in succ.get_phi_functions ()) {
+				var variable_stack = var_map.get (phi.original_variable);
+				if (variable_stack != null && variable_stack.size > 0) {
+					phi.operands.set (j, variable_stack.get (variable_stack.size - 1));
+				}
+			}
+		}
+
+		foreach (BasicBlock child in block.get_children ()) {
+			check_block_variables (m, child);
+		}
+
+		foreach (PhiFunction phi in block.get_phi_functions ()) {
+			var variable_stack = var_map.get (phi.original_variable);
+			variable_stack.remove_at (variable_stack.size - 1);
+		}
+		foreach (CodeNode node in block.get_nodes ()) {
+			var defined_variables = new ArrayList<LocalVariable> ();
+			node.get_defined_variables (defined_variables);
+
+			foreach (LocalVariable local in defined_variables) {
+				var variable_stack = var_map.get (local);
+				variable_stack.remove_at (variable_stack.size - 1);
+			}
+		}
+	}
+
+	LocalVariable process_assignment (Method m, Map<Symbol, Gee.List<LocalVariable>> var_map, LocalVariable var_symbol) {
+		var variable_stack = var_map.get (var_symbol);
+		if (variable_stack == null) {
+			variable_stack = new ArrayList<LocalVariable> ();
+			var_map.set (var_symbol, variable_stack);
+		}
+		LocalVariable versioned_var = new LocalVariable (var_symbol.variable_type, var_symbol.name, null, var_symbol.source_reference);
+		variable_stack.add (versioned_var);
+		return versioned_var;
 	}
 
 	public override void visit_property (Property prop) {
@@ -311,9 +617,13 @@ public class Vala.CFGBuilder : CodeVisitor {
 			}
 		}
 
+		if (!has_default_label) {
+			condition_block.connect (after_switch_block);
+		}
+
 		// after switch
 		// reachable?
-		if (!has_default_label || after_switch_block.get_predecessors ().size > 0) {
+		if (after_switch_block.get_predecessors ().size > 0) {
 			current_block = after_switch_block;
 		} else {
 			current_block = null;
@@ -476,6 +786,7 @@ public class Vala.CFGBuilder : CodeVisitor {
 		var last_block = current_block;
 		last_block.connect (loop_block);
 		current_block = loop_block;
+		current_block.add_node (stmt);
 		stmt.body.accept (this);
 		if (current_block != null) {
 			current_block.connect (loop_block);
@@ -695,6 +1006,7 @@ public class Vala.CFGBuilder : CodeVisitor {
 				Report.warning (jump_target.catch_clause.source_reference, "unreachable catch clause detected");
 			} else {
 				current_block = jump_target.basic_block;
+				current_block.add_node (jump_target.catch_clause);
 				jump_target.catch_clause.body.accept (this);
 				if (current_block != null) {
 					if (finally_block != null) {
diff --git a/vala/valaforeachstatement.vala b/vala/valaforeachstatement.vala
index 949445bfd..efd2480f2 100644
--- a/vala/valaforeachstatement.vala
+++ b/vala/valaforeachstatement.vala
@@ -1,6 +1,6 @@
 /* valaforeachstatement.vala
  *
- * Copyright (C) 2006-2007  Jürg Billeter
+ * Copyright (C) 2006-2008  Jürg Billeter
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a foreach statement in the source code. Foreach statements iterate
@@ -247,4 +247,8 @@ public class Vala.ForeachStatement : Block {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		collection.add (element_variable);
+	}
 }
diff --git a/vala/valainvocationexpression.vala b/vala/valainvocationexpression.vala
index 834ea46c0..3a2de5c9a 100644
--- a/vala/valainvocationexpression.vala
+++ b/vala/valainvocationexpression.vala
@@ -420,4 +420,20 @@ public class Vala.InvocationExpression : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		call.get_defined_variables (collection);
+
+		foreach (Expression arg in argument_list) {
+			arg.get_defined_variables (collection);
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		call.get_used_variables (collection);
+
+		foreach (Expression arg in argument_list) {
+			arg.get_used_variables (collection);
+		}
+	}
 }
diff --git a/vala/valamemberaccess.vala b/vala/valamemberaccess.vala
index 6ced16f4c..01d6f13bf 100644
--- a/vala/valamemberaccess.vala
+++ b/vala/valamemberaccess.vala
@@ -535,4 +535,20 @@ public class Vala.MemberAccess : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		if (inner != null) {
+			inner.get_defined_variables (collection);
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		if (inner != null) {
+			inner.get_used_variables (collection);
+		}
+		var local = symbol_reference as LocalVariable;
+		if (local != null) {
+			collection.add (local);
+		}
+	}
 }
diff --git a/vala/valaobjectcreationexpression.vala b/vala/valaobjectcreationexpression.vala
index 0e42c1098..9fc43fd10 100644
--- a/vala/valaobjectcreationexpression.vala
+++ b/vala/valaobjectcreationexpression.vala
@@ -360,4 +360,16 @@ public class Vala.ObjectCreationExpression : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		foreach (Expression arg in argument_list) {
+			arg.get_defined_variables (collection);
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		foreach (Expression arg in argument_list) {
+			arg.get_used_variables (collection);
+		}
+	}
 }
diff --git a/vala/valaparenthesizedexpression.vala b/vala/valaparenthesizedexpression.vala
index e6d0a2ebd..2a29d9332 100644
--- a/vala/valaparenthesizedexpression.vala
+++ b/vala/valaparenthesizedexpression.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a parenthesized expression in the source code.
@@ -104,4 +104,12 @@ public class Vala.ParenthesizedExpression : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		inner.get_defined_variables (collection);
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		inner.get_used_variables (collection);
+	}
 }
diff --git a/vala/valaphifunction.vala b/vala/valaphifunction.vala
new file mode 100644
index 000000000..b95cc9fe6
--- /dev/null
+++ b/vala/valaphifunction.vala
@@ -0,0 +1,37 @@
+/* valaphifunction.vala
+ *
+ * Copyright (C) 2008  Jürg Billeter
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
+ *
+ * Author:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using Gee;
+
+public class Vala.PhiFunction {
+	public LocalVariable original_variable { get; private set; }
+
+	public Gee.List<LocalVariable?> operands { get; private set; }
+
+	public PhiFunction (LocalVariable variable, int num_of_ops) {
+		this.original_variable = variable;
+		this.operands = new ArrayList<LocalVariable?> ();
+		for (int i = 0; i < num_of_ops; i++) {
+			this.operands.add ((LocalVariable) null);
+		}
+	}
+}
diff --git a/vala/valapointerindirection.vala b/vala/valapointerindirection.vala
index 01a27fa94..84f1b6e6f 100644
--- a/vala/valapointerindirection.vala
+++ b/vala/valapointerindirection.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a pointer indirection in the source code, e.g. `*pointer'.
@@ -101,4 +101,12 @@ public class Vala.PointerIndirection : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		inner.get_defined_variables (collection);
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		inner.get_used_variables (collection);
+	}
 }
diff --git a/vala/valareferencetransferexpression.vala b/vala/valareferencetransferexpression.vala
index e30815ae2..dcf2e5369 100644
--- a/vala/valareferencetransferexpression.vala
+++ b/vala/valareferencetransferexpression.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a reference transfer expression in the source code, e.g. `#foo'.
@@ -107,4 +107,12 @@ public class Vala.ReferenceTransferExpression : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		inner.get_defined_variables (collection);
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		inner.get_used_variables (collection);
+	}
 }
diff --git a/vala/valareturnstatement.vala b/vala/valareturnstatement.vala
index acea14291..c9c99ea8a 100644
--- a/vala/valareturnstatement.vala
+++ b/vala/valareturnstatement.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a return statement in the source code.
@@ -141,4 +141,16 @@ public class Vala.ReturnStatement : CodeNode, Statement {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		if (return_expression != null) {
+			return_expression.get_defined_variables (collection);
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		if (return_expression != null) {
+			return_expression.get_used_variables (collection);
+		}
+	}
 }
diff --git a/vala/valathrowstatement.vala b/vala/valathrowstatement.vala
index 3f27778db..3732b1135 100644
--- a/vala/valathrowstatement.vala
+++ b/vala/valathrowstatement.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents a throw statement in the source code.
@@ -94,4 +94,12 @@ public class Vala.ThrowStatement : CodeNode, Statement {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		error_expression.get_defined_variables (collection);
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		error_expression.get_used_variables (collection);
+	}
 }
diff --git a/vala/valaunaryexpression.vala b/vala/valaunaryexpression.vala
index 3ddd34678..9f478d8e9 100644
--- a/vala/valaunaryexpression.vala
+++ b/vala/valaunaryexpression.vala
@@ -20,7 +20,7 @@
  * 	Jürg Billeter <j@bitron.ch>
  */
 
-using GLib;
+using Gee;
 
 /**
  * Represents an expression with one operand in the source code.
@@ -225,6 +225,22 @@ public class Vala.UnaryExpression : Expression {
 
 		return !error;
 	}
+
+	public override void get_defined_variables (Collection<LocalVariable> collection) {
+		inner.get_defined_variables (collection);
+		if (operator == UnaryOperator.OUT || operator == UnaryOperator.REF) {
+			var local = inner.symbol_reference as LocalVariable;
+			if (local != null) {
+				collection.add (local);
+			}
+		}
+	}
+
+	public override void get_used_variables (Collection<LocalVariable> collection) {
+		if (operator != UnaryOperator.OUT) {
+			inner.get_used_variables (collection);
+		}
+	}
 }
 
 public enum Vala.UnaryOperator {