[Mono-bugs] [Bug 61641][Wis] Changed - Bad register allocation with `if' statements

[bugzilla-daemon@bugzilla.ximian.com]

Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.

Changed by bmaurer@users.sf.net.

http://bugzilla.ximian.com/show_bug.cgi?id=61641

--- shadow/61641	2004-07-15 17:09:45.000000000 -0400
+++ shadow/61641.tmp.20801	2004-07-15 18:20:16.000000000 -0400
@@ -554,6 +554,36 @@
 ------- Additional Comments From bmaurer@users.sf.net  2004-07-15 17:09 -------
 In the paper "Linear Scan Register Allocation" (Poletto and Sarkar),
 the suggested order for arranging the BBs is "depth first ordering"
 which is "the reverse of the order in which nodes are last visited in
 a preorder traversal of the flow graph" The paper references Aho et
 al's "Compilers: Principles Techniques and Tools"
+
+------- Additional Comments From bmaurer@users.sf.net  2004-07-15 18:20 -------
+I took a look at the Aho book, it seems that the DFN calculation uses
+their method for getting the depth first order. However, the method
+they use does not seem to give the same results as the "reverse of the
+order in which the nodes are last visited in preorder"
+
+if you have the tree
+           a
+          / \
+         b   c
+          \ /
+           d
+           |
+           e
+
+the method given in Aho (and used by the jit) orders the nodes
+
+a b d e c
+
+If we do the pre-order visit of the tree, we visit the nodes in the order:
+
+a b d e c d e
+_ _     _ _ _
+
+the reverse of the order in which they were last visited is:
+
+a b c d e
+
+I think the second arrangement would give better allocation.