[Scummvm-cvs-logs] SF.net SVN: scummvm:[50632] tools/branches/gsoc2010-decompiler/decompiler

[pidgeot at users.sourceforge.net]

Revision: 50632
          http://scummvm.svn.sourceforge.net/scummvm/?rev=50632&view=rev
Author:   pidgeot
Date:     2010-07-03 21:07:30 +0000 (Sat, 03 Jul 2010)

Log Message:
-----------
Add detection of break and continue, including tests
Small fix to while loop detection (ingoing edge must not be from do-while)

Modified Paths:
--------------
    tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
    tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h

Modified: tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp	2010-07-03 21:05:51 UTC (rev 50631)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp	2010-07-03 21:07:30 UTC (rev 50632)
@@ -229,13 +229,13 @@
 	VertexRange vr = boost::vertices(_g);
 	for (VertexIterator v = vr.first; v != vr.second; ++v) {
 		Group *gr = GET(*v);
-		// Block ends with conditional jump and has not yet been determined
+		// Undetermined block that ends with conditional jump
 		if (out_degree(*v, _g) == 2 && gr->_type == kNormal) {
 			InEdgeRange ier = boost::in_edges(*v, _g);
 			for (InEdgeIterator e = ier.first; e != ier.second; ++e) {
 				Group *sourceGr = GET(boost::source(*e, _g));
-				// Block has ingoing edge from later in the code
-				if (sourceGr->_start->_address > gr->_start->_address)
+				// Block has ingoing edge from block later in the code that isn't a do-while condition
+				if (sourceGr->_start->_address > gr->_start->_address && sourceGr->_type != kDoWhileCond)
 					gr->_type = kWhileCond;
 			}
 		}
@@ -246,7 +246,7 @@
 	VertexRange vr = boost::vertices(_g);
 	for (VertexIterator v = vr.first; v != vr.second; ++v) {
 		Group *gr = GET(*v);
-		// Block has not yet been determined and ends with conditional jump...
+		// Undetermined block that ends with conditional jump...
 		if (out_degree(*v, _g) == 2 && gr->_type == kNormal) {
 			OutEdgeRange oer = boost::out_edges(*v, _g);
 			for (OutEdgeIterator e = oer.first; e != oer.second; ++e) {
@@ -260,9 +260,44 @@
 }
 
 void ControlFlow::detectBreak() {
+	VertexRange vr = boost::vertices(_g);
+	for (VertexIterator v = vr.first; v != vr.second; ++v) {
+		Group *gr = GET(*v);
+		// Unconditional jump...
+		if ((gr->_end->_type == kJump || gr->_end->_type == kJumpRel) && out_degree(*v, _g) == 1) {
+			OutEdgeIterator oe = boost::out_edges(*v, _g).first;
+			GraphVertex target = boost::target(*oe, _g);
+			Group *targetGr = GET(target);			
+			// ...to somewhere later in the code...
+			if (gr->_start->_address >= targetGr->_start->_address)
+				continue;
+			InEdgeRange ier = boost::in_edges(target, _g);
+			for (InEdgeIterator ie = ier.first; ie != ier.second; ++ie) {
+				Group *sourceGr = GET(boost::source(*ie, _g));
+				// ...to block immediately after a do-while condition, or to jump target of a while condition
+				if ((targetGr->_prev == sourceGr && sourceGr->_type == kDoWhileCond) || sourceGr->_type == kWhileCond) {
+					gr->_type = kBreak;
+				}
+			}
+		}
+	}
 }
 
 void ControlFlow::detectContinue() {
+	VertexRange vr = boost::vertices(_g);
+	for (VertexIterator v = vr.first; v != vr.second; ++v) {
+		Group *gr = GET(*v);
+		// Undetermined block with unconditional jump...
+		if (gr->_type == kNormal && (gr->_end->_type == kJump || gr->_end->_type == kJumpRel) && out_degree(*v, _g) == 1) {
+			OutEdgeIterator oe = boost::out_edges(*v, _g).first;
+			GraphVertex target = boost::target(*oe, _g);
+			Group *targetGr = GET(target);
+			// ...to a while or do-while condition
+			if (targetGr->_type == kWhileCond || targetGr->_type == kDoWhileCond) {
+				gr->_type = kContinue;
+			}
+		}
+	}
 }
 
 void ControlFlow::detectIf() {

Modified: tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h	2010-07-03 21:05:51 UTC (rev 50631)
+++ tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h	2010-07-03 21:07:30 UTC (rev 50632)
@@ -61,6 +61,8 @@
 				TS_ASSERT(false);
 			}
 		}
+		delete c;
+		delete engine;
 	};
 
 	void testBranching() {
@@ -92,6 +94,8 @@
 				TS_ASSERT(false);
 			}
 		}
+		delete c;
+		delete engine;
 	}
 
 	void testGrouping() {
@@ -123,6 +127,8 @@
 				break;
 			}
 		}
+		delete c;
+		delete engine;
 	}
 
 	void testShortCircuitDetection() {
@@ -135,6 +141,8 @@
 		c->createGroups();
 		Graph g = c->getGraph();
 		TS_ASSERT(boost::num_vertices(g) == 3);
+		delete c;
+		delete engine;
 	}
 
 	void testWhileDetection() {
@@ -152,6 +160,8 @@
 			if (gr->_start->_address == 0)
 				TS_ASSERT(gr->_type == kWhileCond);
 		}
+		delete c;
+		delete engine;
 	}
 
 	void testDoWhileDetection() {
@@ -169,5 +179,105 @@
 			if (gr->_start->_address == 3)
 				TS_ASSERT(gr->_type == kDoWhileCond);
 		}
+		delete c;
+		delete engine;
 	}
+
+	void testBreakDetection() {
+		Scumm::v6::Engine *engine = new Scumm::v6::Engine();
+		Disassembler *d = engine->getDisassembler();
+		d->open("decompiler/test/break-while.dmp");
+		std::vector<Instruction> insts = d->disassemble();
+		delete d;
+		ControlFlow *c = new ControlFlow(insts, engine);
+		c->createGroups();
+		Graph g = c->analyze();
+		VertexRange range = boost::vertices(g);
+		for (VertexIterator it = range.first; it != range.second; ++it) {
+			Group *gr = GET(*it);
+			if (gr->_start->_address == 0x14)
+				TS_ASSERT(gr->_type == kBreak);
+		}
+		delete c;
+
+		d = engine->getDisassembler();
+		d->open("decompiler/test/break-do-while.dmp");
+		insts = d->disassemble();
+		delete d;
+		c = new ControlFlow(insts, engine);
+		c->createGroups();
+		g = c->analyze();
+		range = boost::vertices(g);
+		for (VertexIterator it = range.first; it != range.second; ++it) {
+			Group *gr = GET(*it);
+			if (gr->_start->_address == 0xA)
+				TS_ASSERT(gr->_type == kBreak);
+		}
+		delete c;
+
+		d = engine->getDisassembler();
+		d->open("decompiler/test/break-do-while2.dmp");
+		insts = d->disassemble();
+		delete d;
+		c = new ControlFlow(insts, engine);
+		c->createGroups();
+		g = c->analyze();
+		range = boost::vertices(g);
+		for (VertexIterator it = range.first; it != range.second; ++it) {
+			Group *gr = GET(*it);
+			if (gr->_start->_address == 0xD)
+				TS_ASSERT(gr->_type == kBreak);
+		}
+		delete c;
+		delete engine;
+	}
+
+	void testContinueDetection() {
+		Scumm::v6::Engine *engine = new Scumm::v6::Engine();
+		Disassembler *d = engine->getDisassembler();
+		d->open("decompiler/test/continue-while.dmp");
+		std::vector<Instruction> insts = d->disassemble();
+		delete d;
+		ControlFlow *c = new ControlFlow(insts, engine);
+		c->createGroups();
+		Graph g = c->analyze();
+		VertexRange range = boost::vertices(g);
+		for (VertexIterator it = range.first; it != range.second; ++it) {
+			Group *gr = GET(*it);
+			if (gr->_start->_address == 0x14)
+				TS_ASSERT(gr->_type == kContinue);
+		}
+		delete c;
+
+		d = engine->getDisassembler();
+		d->open("decompiler/test/continue-do-while.dmp");
+		insts = d->disassemble();
+		delete d;
+		c = new ControlFlow(insts, engine);
+		c->createGroups();
+		g = c->analyze();
+		range = boost::vertices(g);
+		for (VertexIterator it = range.first; it != range.second; ++it) {
+			Group *gr = GET(*it);
+			if (gr->_start->_address == 0xA)
+				TS_ASSERT(gr->_type == kContinue);
+		}
+		delete c;
+
+		d = engine->getDisassembler();
+		d->open("decompiler/test/continue-do-while2.dmp");
+		insts = d->disassemble();
+		delete d;
+		c = new ControlFlow(insts, engine);
+		c->createGroups();
+		g = c->analyze();
+		range = boost::vertices(g);
+		for (VertexIterator it = range.first; it != range.second; ++it) {
+			Group *gr = GET(*it);
+			if (gr->_start->_address == 0xD)
+				TS_ASSERT(gr->_type == kContinue);
+		}
+		delete c;
+		delete engine;
+	}
 };


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.