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

[brixxie at users.sourceforge.net]

Revision: 28074
          http://scummvm.svn.sourceforge.net/scummvm/?rev=28074&view=rev
Author:   brixxie
Date:     2007-07-14 10:29:58 -0700 (Sat, 14 Jul 2007)

Log Message:
-----------
Added algorithm to find graph intervals

Modified Paths:
--------------
    tools/branches/gsoc2007-decompiler/antipasto.scm
    tools/branches/gsoc2007-decompiler/cfgg.scm

Property Changed:
----------------
    tools/branches/gsoc2007-decompiler/


Property changes on: tools/branches/gsoc2007-decompiler
___________________________________________________________________
Name: svk:merge
   - 489ca303-0d3d-4dc1-a57d-017c7912a06a:/local/gsoc2007-decompiler:39
   + 489ca303-0d3d-4dc1-a57d-017c7912a06a:/local/gsoc2007-decompiler:42

Modified: tools/branches/gsoc2007-decompiler/antipasto.scm
===================================================================
--- tools/branches/gsoc2007-decompiler/antipasto.scm	2007-07-14 15:12:22 UTC (rev 28073)
+++ tools/branches/gsoc2007-decompiler/antipasto.scm	2007-07-14 17:29:58 UTC (rev 28074)
@@ -2,7 +2,7 @@
 
 ;;; Antipasto - Scumm Script Disassembler Prototype (version 5 scripts)
 ;;; Copyright (C) 2007 Andreas Scholta
-;;; Time-stamp: <2007-07-08 20:34:50 brx>
+;;; Time-stamp: <2007-07-10 20:27:13 brx>
 
 ;;; This program is free software; you can redistribute it and/or
 ;;; modify it under the terms of the GNU General Public License
@@ -820,11 +820,17 @@
         (printf "[~A] (~X) "
                 (caar decoded)
                 (cadar decoded))
-        (write (cddar decoded))
-        (newline)
+        (pretty-print (cddar decoded))
         (print-decoded (cdr decoded))))
-    (for-each (cut printf "~S\n" <>)
-              (generate-control-flow-graph decoded)))
+    (receive (basic-blocks intervals)
+        (generate-control-flow-graph decoded)
+      (printf "Basic Blocks:\n")
+      (pretty-print basic-blocks)
+      (newline)
+      (printf "Intervals:\n")
+      (for-each (compose (hole newline)
+                         (cut pretty-print <>))
+                intervals)))
   (close-input-port current-script-port)
   (set! current-script-port #f)
   (set! current-script-file #f)

Modified: tools/branches/gsoc2007-decompiler/cfgg.scm
===================================================================
--- tools/branches/gsoc2007-decompiler/cfgg.scm	2007-07-14 15:12:22 UTC (rev 28073)
+++ tools/branches/gsoc2007-decompiler/cfgg.scm	2007-07-14 17:29:58 UTC (rev 28074)
@@ -2,7 +2,7 @@
 
 ;;; Antipasto - Scumm Script Disassembler Prototype
 ;;; Copyright (C) 2007 Andreas Scholta
-;;; Time-stamp: <2007-07-09 01:31:43 brx>
+;;; Time-stamp: <2007-07-10 20:25:19 brx>
 
 ;;; This program is free software; you can redistribute it and/or
 ;;; modify it under the terms of the GNU General Public License
@@ -143,11 +143,46 @@
             (correct-trivial-blocks! (cdr trivial-blocks)
                                      fixed-blocks)))))
 
+(define (find-interval interval basic-blocks)
+  (let ((new-interval-nodes (partition (lambda (block)
+                                         (and (not (memq block interval))
+                                              (every (cut memq <> interval)
+                                                     (basic-block-preds block))))
+                                       basic-blocks)))
+    (if (null? new-interval-nodes)
+        interval
+        (find-interval (append interval
+                               new-interval-nodes)
+                       basic-blocks))))
+
+(define (generate-intervals unprocessed-headers headers basic-blocks)
+  (if (null? unprocessed-headers)
+      '()
+      (let* ((new-interval (find-interval (list (car unprocessed-headers))
+                                          basic-blocks))
+             (new-headers (partition (lambda (block)
+                                       (and (not (memq block headers))
+                                            (not (memq block new-interval))
+                                            (any (cut memq <> new-interval)
+                                                 (basic-block-preds block))))
+                                     basic-blocks)))
+        (cons new-interval
+              (generate-intervals (append (cdr unprocessed-headers)
+                                          new-headers)
+                                  (append headers
+                                          new-headers)
+                                  basic-blocks)))))
+
 (define (generate-control-flow-graph disassembly)
-  (let ((trivial-blocks
-         (generate-trivial-blocks
-          (remove-opcodes-from-disassembly disassembly) '() #f)))
-    (correct-trivial-blocks! trivial-blocks trivial-blocks)))
+  (let* ((trivial-blocks
+          (generate-trivial-blocks
+           (remove-opcodes-from-disassembly disassembly) '() #f))
+         (basic-blocks (correct-trivial-blocks! trivial-blocks
+                                                trivial-blocks)))
+    (values basic-blocks
+            (generate-intervals (list (car basic-blocks))
+                                (list (car basic-blocks))
+                                basic-blocks))))
 
 ;; (test-run "/home/brx/code/gsoc2007-decompiler/M1.scummV5/81.cu_bar_2.0092")
 ;; (test-run "/home/brx/code/gsoc2007-decompiler/M2.scummV5/entry-4.dmp")


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