[phc-internals] [phc commit] r1753 - branches/dataflow/src/optimize

[codesite-noreply at google.com]

Author: paul.biggar
Date: Mon Oct  6 10:15:44 2008
New Revision: 1753

Modified:
    branches/dataflow/src/optimize/CFG.cpp
    branches/dataflow/src/optimize/SSA.h

Log:
Copy in the HSSA algorithm. This is quite a big one, so a tidy-up will  
occur first.


Modified: branches/dataflow/src/optimize/CFG.cpp
==============================================================================
--- branches/dataflow/src/optimize/CFG.cpp	(original)
+++ branches/dataflow/src/optimize/CFG.cpp	Mon Oct  6 10:15:44 2008
@@ -18,6 +18,7 @@
  #include "Def_use.h"
  #include "process_ast/DOT_unparser.h"
  #include "process_ir/General.h"
+#include "Address_taken.h"

  using namespace boost;
  using namespace std;
@@ -554,6 +555,9 @@

  void CFG::convert_to_ssa_form ()
  {
+	Address_taken* aliasing = new Address_taken ();
+	aliasing->run (this);
+
  	// Calculate dominance frontiers
  	dominance = new Dominance (this);
  	dominance->calculate_forward_dominance ();

Modified: branches/dataflow/src/optimize/SSA.h
==============================================================================
--- branches/dataflow/src/optimize/SSA.h	(original)
+++ branches/dataflow/src/optimize/SSA.h	Mon Oct  6 10:15:44 2008
@@ -7,6 +7,67 @@

  using namespace boost;

+/*
+ * How to convert into HSSA form algorithm 2 from "Effective  
Representation of
+ * Aliases and Indirect Memory Operations in SSA Form", by Chow et al.
+ *
+ * 1) Assign virtual variables to indirect variables in the program
+ *
+ * 2)	Perform alias analysis and insert MEW and CHI for all scalar and  
virtual variables
+ *
+ * 3) Insert PHIs using Cytron algorithm, including CHI as assignments
+ *
+ * 4) Rename all scalar and virtual variables using Cytron algorithm
+ *
+ * 5) Simultaneously:
+ *		a)	Perform DCE, including on PHIs and CHIs, using Cytron algorithm
+ *		b)	Perform steps 1 and 2 of algorithm 1 (Compute Zero Versions), to set
+ *			the HasRealOcc flag for all variable versions. These steps are:
+ *				czv1)	Initialize flag HasRealOcc for each variable version created
+ *						by SSA renaming to false.
+ *				czv2)	Pass over the program. On visiting a real occurrence, set the
+ *						HasRealOcc flag for the variable version to true.
+ *
+ *	6)	Performs steps 3, 4 and 5 of CZV algorithm to set variable versions  
to 0. These steps are:
+ *		czv3)	For each program varaible, create NonZeroPhiList and init to  
empty.
+ *		czv4)	Iterate through all variable versions:
+ *				a)	If HasRealOcc is false, and is defined by CHI, set version to 0
+ *				b) If HasRealOcc is false, and is defined by PHI:
+ *					-	If the version of one of the operands is 0, set version to 0
+ *					-	Else if HasRealOcc flag of all operand is set to true, set
+ *						HasRealOcc to true
+ *					-	Else add version to NonZeroPhiList for the variable
+ *		czv5)	For each program variable, iterate until its NonZeroPhiList no  
longer changes:
+ *				a)	For each version in NonZeroPhiList
+ *					-	If the version of one of the operands in 0, set version to 0
+ *						and remove from NonZeroPhiList
+ *					-	Else if the HasRealOcc flag of all operands is true, set
+ *						HasRealOcc to true and remove from NonZeroPhiList
+ *
+ *	7)	Hash a unique value unmber and create the corresponding hash table  
VAR
+ *		node for each scalar and virtual variable version that are determined  
to
+ *		be live in Step 5a.
+ *
+ *	8) Conduct a pre-order traversal of the dominator tree of the control  
flow
+ *		graph of the program and apply global value numbering to the code in  
each
+ *		basic_block:
+ *		a)	Hash expression trees bottom-up into the hash-table, searching for  
any
+ *			existing matching entry before creating each new value number and
+ *			entry.  At a VAR node, use the node created in step 7 for that
+ *			variable version.
+ *		b)	For two IVAR nodes to match, two conditions must be satisfied:
+ *			1) Their address expressions have the same value number, and
+ *			2) the versions of their virtual variables are either the same, or are
+ *				separated by definitions that do not alias with the IVAR.
+ *		c)	For each assignment statement, including PHI and CHI, represent its
+ *			lhs by making the statement point to the VAR or IVAR for direct and
+ *			indirect assignments respectively. Also make the VAR or IVAR node
+ *			point back to its defining statement.
+ *		d)	Update all PHI, MEW and CHI operands and results to make them refer  
to
+ *			entries in the hash-table.
+ *				
+ */
+
  class Dominance
  {
  	// TODO: friend the calculate_dominace class