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

[codesite-noreply at google.com]

Author: paul.biggar
Date: Thu Jul 24 09:50:40 2008
New Revision: 1468

Modified:
   branches/dataflow/src/optimize/Basic_block.cpp
   branches/dataflow/src/optimize/CFG.cpp
   branches/dataflow/src/optimize/Live_variable_analysis.cpp
   branches/dataflow/src/optimize/Set.cpp
   branches/dataflow/src/optimize/Set.h

Log:
Added set operations. Since the C++ algorithms don't offer an in-place 
version, I removed them, implementing only the out-of-place versions.


Modified: branches/dataflow/src/optimize/Basic_block.cpp
==============================================================================
--- branches/dataflow/src/optimize/Basic_block.cpp	(original)
+++ branches/dataflow/src/optimize/Basic_block.cpp	Thu Jul 24 09:50:40 2008
@@ -70,4 +70,8 @@
 	// TODO make sure iteration count is taken into account
 	iteration_count = 0;
 	solution_changed = true;
+	defs = new Set;
+	uses = new Set;
+	live_in = new Set;
+	live_out = new Set;
 }

Modified: branches/dataflow/src/optimize/CFG.cpp
==============================================================================
--- branches/dataflow/src/optimize/CFG.cpp	(original)
+++ branches/dataflow/src/optimize/CFG.cpp	Thu Jul 24 09:50:40 2008
@@ -143,8 +143,10 @@
 {
 	list<Basic_block*>* result = new list<Basic_block*>;

-	assert (0);
-	// TODO
+	foreach (edge_t e, in_edges (bb->vertex, bs))
+	{
+		result->push_back (vb[source (e, bs)]);
+	}

 	return result;
 }
@@ -152,8 +154,6 @@
 list<Basic_block*>*
 CFG::get_successors (Basic_block* bb)
 {
-	this->consistency_check();
-
 	list<Basic_block*>* result = new list<Basic_block*>;

 	foreach (edge_t e, out_edges (bb->vertex, bs))
@@ -167,6 +167,8 @@
 list<Basic_block*>*
 CFG::get_all_bbs ()
 {
+	this->consistency_check();
+
 	list<Basic_block*>* result = new list<Basic_block*>;

 	foreach (vertex_t v, vertices(bs))

Modified: branches/dataflow/src/optimize/Live_variable_analysis.cpp
==============================================================================
--- branches/dataflow/src/optimize/Live_variable_analysis.cpp	(original)
+++ branches/dataflow/src/optimize/Live_variable_analysis.cpp	Thu Jul 
24 09:50:40 2008
@@ -46,7 +46,7 @@
 Live_variable_analysis::transfer_in (Basic_block* bb, list<Basic_block*>*)
 {
 	// IN = (OUT / DEFS) U USES
-	bb->live_in = bb->live_out->oop_union (bb->defs)->ip_union (bb->live_out);
+	bb->live_in = bb->live_out->set_union (bb->defs)->set_union (bb->live_out);
 }

 void
@@ -56,12 +56,12 @@
 	bb->live_out = new Set;
 	BOOST_FOREACH (Basic_block* succ, *succs)
 	{
-		bb->live_out->ip_union (succ->live_in);
+		bb->live_out = bb->live_out->set_union (succ->live_in);
 	}
 }

-#define USE(VAR) bb->uses->add (VAR->value);
-#define DEF(VAR) bb->defs->add (VAR->value);
+#define USE(VAR) bb->uses->insert (VAR->value);
+#define DEF(VAR) bb->defs->insert (VAR->value);

 void use_expr (Basic_block* bb, Expr* in)
 {

Modified: branches/dataflow/src/optimize/Set.cpp
==============================================================================
--- branches/dataflow/src/optimize/Set.cpp	(original)
+++ branches/dataflow/src/optimize/Set.cpp	Thu Jul 24 09:50:40 2008
@@ -1,51 +1,56 @@
-#include "Set.h"
+#include <algorithm>
+#include <iterator>
 #include "assert.h"

+#include "Set.h"
+
 Set::Set()
 {
 }

 // Out-of-place operations return new sets
 Set*
-Set::oop_union (Set* other)
+Set::set_union (Set* other)
 {
-	assert (0);
-}
+	Set* result = new Set;

-Set*
-Set::oop_intersection (Set* other)
-{
-	assert (0);
-}
+	std::set_union (
+		bs.begin (), bs.end(),
+		other->bs.begin (), other->bs.end (),
+		insert_iterator<set<string> > (result->bs, result->bs.begin ()));

-Set*
-Set::oop_difference (Set* other)
-{
-	assert (0);
-}
-	
-// In-place operations
-Set*
-Set::ip_union (Set* other)
-{
-	assert (0);
+	return result;
 }

 Set*
-Set::ip_intersection (Set* other)
+Set::set_intersection (Set* other)
 {
-	assert (0);
+	Set* result = new Set;
+
+	std::set_intersection (
+		bs.begin (), bs.end(),
+		other->bs.begin (), other->bs.end (),
+		insert_iterator<set<string> > (result->bs, result->bs.begin ()));
+
+	return result;
 }

 Set*
-Set::ip_difference (Set* other)
+Set::set_difference (Set* other)
 {
-	assert (0);
+	Set* result = new Set;
+
+	std::set_difference (
+		bs.begin (), bs.end(),
+		other->bs.begin (), other->bs.end (),
+		insert_iterator<set<string> > (result->bs, result->bs.begin ()));
+
+	return result;
 }

 void
-Set::add (String* string)
+Set::insert (String* string)
 {
-	assert (0);
+	bs.insert (*string);
 }


Modified: branches/dataflow/src/optimize/Set.h
==============================================================================
--- branches/dataflow/src/optimize/Set.h	(original)
+++ branches/dataflow/src/optimize/Set.h	Thu Jul 24 09:50:40 2008
@@ -14,18 +14,16 @@
 	Set();

 public:
-	// Out-of-place operations return new sets
-	Set* oop_union (Set* other);
-	Set* oop_intersection (Set* other);
-	Set* oop_difference (Set* other);
+	// Out-of-place operations return new sets. We only consider out-of-place
+	// versions since the STL includes only out-of-place versions. In-place
+	// versions can be created in a lot of cases, however, possibly with lower
+	// complexity.
+	Set* set_union (Set* other);
+	Set* set_intersection (Set* other);
+	Set* set_difference (Set* other);
 	
-	// In-place operations
-	Set* ip_union (Set* other);
-	Set* ip_intersection (Set* other);
-	Set* ip_difference (Set* other);
-
 public:
-	void add (String* string);
+	void insert (String* string);
 };