dotgnu-pnet-commits
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[dotgnu-pnet-commits] libjit ChangeLog jit/jit-live.c jit/jit-value.c


From: Aleksey Demakov
Subject: [dotgnu-pnet-commits] libjit ChangeLog jit/jit-live.c jit/jit-value.c
Date: Mon, 28 May 2007 02:41:29 +0000

CVSROOT:        /sources/dotgnu-pnet
Module name:    libjit
Changes by:     Aleksey Demakov <avd>   07/05/28 02:41:28

Modified files:
        .              : ChangeLog 
        jit            : jit-live.c jit-value.c 

Log message:
        implement simple-minded copy propagation

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/libjit/ChangeLog?cvsroot=dotgnu-pnet&r1=1.314&r2=1.315
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-live.c?cvsroot=dotgnu-pnet&r1=1.3&r2=1.4
http://cvs.savannah.gnu.org/viewcvs/libjit/jit/jit-value.c?cvsroot=dotgnu-pnet&r1=1.10&r2=1.11

Patches:
Index: ChangeLog
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/ChangeLog,v
retrieving revision 1.314
retrieving revision 1.315
diff -u -b -r1.314 -r1.315
--- ChangeLog   26 May 2007 14:13:22 -0000      1.314
+++ ChangeLog   28 May 2007 02:41:28 -0000      1.315
@@ -1,3 +1,12 @@
+2007-05-28  Aleksey Demakov  <address@hidden>
+
+       * jit/jit-live.c (_jit_function_compute_liveness)
+       (forward_propagation, backward_propagation): add simple copy
+       propagation that works only within basic blocks.
+
+       * jit/jit-value.c (jit_value_ref): do not set the live flag here
+       as this is done in jit-live.c now.
+
 2007-05-26  Klaus Treichel  <address@hidden>
 
        * jit/jit-intrinsic.c: Fix conversion from ulong to nfloat for values

Index: jit/jit-live.c
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-live.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -b -r1.3 -r1.4
--- jit/jit-live.c      20 May 2004 09:53:37 -0000      1.3
+++ jit/jit-live.c      28 May 2007 02:41:28 -0000      1.4
@@ -20,10 +20,14 @@
 
 #include "jit-internal.h"
 
+#define USE_FORWARD_PROPAGATION 1
+#define USE_BACKWARD_PROPAGATION 1
+
 /*
  * Compute liveness information for a basic block.
  */
-static void compute_liveness_for_block(jit_block_t block)
+static void
+compute_liveness_for_block(jit_block_t block)
 {
        jit_insn_iter_t iter;
        jit_insn_t insn;
@@ -157,41 +161,299 @@
                        value2->next_use = 1;
                }
        }
+}
+
+#if USE_FORWARD_PROPAGATION || USE_BACKWARD_PROPAGATION
+static int
+is_copy_opcode(int opcode)
+{
+       switch(opcode)
+       {
+       case JIT_OP_COPY_INT:
+       case JIT_OP_COPY_LONG:
+       case JIT_OP_COPY_FLOAT32:
+       case JIT_OP_COPY_FLOAT64:
+       case JIT_OP_COPY_NFLOAT:
+       /*case JIT_OP_STRUCT:*/
+               return 1;
+       }
+       return 0;
+}
+#endif
+
+#if USE_FORWARD_PROPAGATION
+/*
+ * Perform simple copy propagation within basic block. Replaces instructions
+ * that look like this:
+ *
+ * i) t = x
+ * ...
+ * j) y = op(t)
+ *
+ * with the folowing:
+ *
+ * i) t = x
+ * ...
+ * j) y = op(x)
+ *
+ * If "t" is not used after the instruction "j" then further liveness analysis
+ * may replace the instruction "i" with a noop:
+ *
+ * i) noop
+ * ...
+ * j) y = op(x)
+ *
+ * The propagation stops as soon as either "t" or "x" are changed (used as a
+ * dest in a different instruction).
+ */
+static int
+forward_propagation(jit_block_t block)
+{
+       int optimized;
+       jit_insn_iter_t iter, iter2;
+       jit_insn_t insn, insn2;
+       jit_value_t dest, value;
+       int flags2;
+
+       optimized = 0;
+
+       jit_insn_iter_init(&iter, block);
+       while((insn = jit_insn_iter_next(&iter)) != 0)
+       {
+               if(!is_copy_opcode(insn->opcode))
+               {
+                       continue;
+               }
+
+               dest = insn->dest;
+               if(dest == 0 || dest->is_constant)
+               {
+                       continue;
+               }
+
+               value = insn->value1;
+               if(value == 0)
+               {
+                       continue;
+               }
+
+               /* Copy to itself could be safely discarded */
+               if(dest == value)
+               {
+                       insn->opcode = (short)JIT_OP_NOP;
+                       optimized = 1;
+                       continue;
+               }
+
+               /* Not smart enough to tell when it is safe to optimize copying
+                  to a value used in other basic block. So just give up. */
+               if(!dest->is_temporary)
+               {
+                       continue;
+               }
+
+               iter2 = iter;
+               while((insn2 = jit_insn_iter_next(&iter2)) != 0)
+               {
+                       flags2 = insn2->flags;
+
+                       if((flags2 & JIT_INSN_DEST_OTHER_FLAGS) == 0)
+                       {
+                               if((flags2 & JIT_INSN_DEST_IS_VALUE) == 0)
+                               {
+                                       if(insn2->dest == dest || insn2->dest 
== value)
+                                       {
+                                               break;
+                                       }
+                               }
+                               else if(insn2->dest == dest)
+                               {
+                                       insn2->dest = value;
+                                       optimized = 1;
+                               }
+                       }
+                       if((flags2 & JIT_INSN_VALUE1_OTHER_FLAGS) == 0)
+                       {
+                               if(insn2->value1 == dest)
+                               {
+                                       insn2->value1 = value;
+                                       optimized = 1;
+                               }
+                       }
+                       if((flags2 & JIT_INSN_VALUE2_OTHER_FLAGS) == 0)
+                       {
+                               if(insn2->value2 == dest)
+                               {
+                                       insn2->value2 = value;
+                                       optimized = 1;
+                               }
+                       }
+               }
+       }
+
+       return optimized;
+}
+#endif
+
+#if USE_BACKWARD_PROPAGATION
+/*
+ * Perform simple copy propagation within basic block for the case when a
+ * temporary value is stored to another value. This replaces instructions
+ * that look like this:
+ *
+ * i) t = op(x)
+ * ...
+ * j) y = t
+ *
+ * with the following
+ *
+ * i) y = op(x)
+ * ...
+ * j) noop
+ *
+ * This is only allowed if "t" is used only in the instructions "i" and "j"
+ * and "y" is not used between "i" and "j" (but can be used after "j").
+ */
+static int
+backward_propagation(jit_block_t block)
+{
+       int optimized;
+       jit_insn_iter_t iter, iter2;
+       jit_insn_t insn, insn2;
+       jit_value_t dest, value;
+       int flags2;
+
+       optimized = 0;
 
-       /* Re-scan the block to reset the liveness flags on all non-temporaries
-          because we need them in the original state for the next block */
        jit_insn_iter_init_last(&iter, block);
        while((insn = jit_insn_iter_previous(&iter)) != 0)
        {
-               flags = insn->flags;
-               if((flags & JIT_INSN_DEST_OTHER_FLAGS) == 0)
+               if(!is_copy_opcode(insn->opcode))
                {
+                       continue;
+               }
+
                        dest = insn->dest;
-                       if(dest && !(dest->is_constant) && 
!(dest->is_temporary))
+               if(dest == 0 || dest->is_constant)
                        {
-                               dest->live = 1;
-                               dest->next_use = 0;
+                       continue;
                        }
+
+               value = insn->value1;
+               if(value == 0)
+               {
+                       continue;
                }
-               if((flags & JIT_INSN_VALUE1_OTHER_FLAGS) == 0)
+
+               /* Copy to itself could be safely discarded */
+               if(dest == value)
                {
-                       value1 = insn->value1;
-                       if(value1 && !(value1->is_constant) && 
!(value1->is_temporary))
+                       insn->opcode = (short)JIT_OP_NOP;
+                       optimized = 1;
+                       continue;
+               }
+
+               /* "value" is used afterwards so we cannot eliminate it here */
+               if((insn->flags & (JIT_INSN_VALUE1_LIVE | 
JIT_INSN_VALUE1_NEXT_USE)) != 0)
                        {
-                               value1->live = 1;
-                               value1->next_use = 0;
+                       continue;
                        }
+
+               iter2 = iter;
+               while((insn2 = jit_insn_iter_previous(&iter2)) != 0)
+               {
+                       flags2 = insn2->flags;
+
+                       if((flags2 & JIT_INSN_DEST_OTHER_FLAGS) == 0)
+                       {
+                               if(insn2->dest == dest)
+                               {
+                                       break;
                }
-               if((flags & JIT_INSN_VALUE2_OTHER_FLAGS) == 0)
+                               if(insn2->dest == value)
                {
-                       value2 = insn->value2;
-                       if(value2 && !(value2->is_constant) && 
!(value2->is_temporary))
+                                       if((flags2 & JIT_INSN_DEST_IS_VALUE) == 
0)
                        {
-                               value2->live = 1;
-                               value2->next_use = 0;
+                                               insn->opcode = 
(short)JIT_OP_NOP;
+                                               insn2->dest = dest;
+                                               optimized = 1;
+                                       }
+                                       break;
+                               }
+                       }
+                       if((flags2 & JIT_INSN_VALUE1_OTHER_FLAGS) == 0)
+                       {
+                               if(insn2->value1 == dest || insn2->value1 == 
value)
+                               {
+                                       break;
+                               }
+                       }
+                       if((flags2 & JIT_INSN_VALUE2_OTHER_FLAGS) == 0)
+                       {
+                               if(insn2->value2 == dest || insn2->value1 == 
value)
+                               {
+                                       break;
                        }
                }
        }
+       }
+
+       return optimized;
+}
+#endif
+
+/* Reset value liveness flags. */
+static void
+reset_value_liveness(jit_value_t value)
+{
+       if(value)
+       {
+               if (!value->is_constant && !value->is_temporary)
+               {
+                       value->live = 1;
+               }
+               else
+               {
+                       value->live = 0;
+               }
+               value->next_use = 0;
+       }
+}
+
+/*
+ * Re-scan the block to reset the liveness flags on all non-temporaries
+ * because we need them in the original state for the next block.
+ */
+static void
+reset_liveness_flags(jit_block_t block, int reset_all)
+{
+       jit_insn_iter_t iter;
+       jit_insn_t insn;
+       int flags;
+
+       jit_insn_iter_init(&iter, block);
+       while((insn = jit_insn_iter_next(&iter)) != 0)
+       {
+               flags = insn->flags;
+               if((flags & JIT_INSN_DEST_OTHER_FLAGS) == 0)
+               {
+                       reset_value_liveness(insn->dest);
+               }
+               if((flags & JIT_INSN_VALUE1_OTHER_FLAGS) == 0)
+               {
+                       reset_value_liveness(insn->value1);
+               }
+               if((flags & JIT_INSN_VALUE2_OTHER_FLAGS) == 0)
+               {
+                       reset_value_liveness(insn->value2);
+               }
+               if(reset_all)
+               {
+                       flags &= ~(JIT_INSN_DEST_LIVE | JIT_INSN_DEST_NEXT_USE
+                                  |JIT_INSN_VALUE1_LIVE | 
JIT_INSN_VALUE1_NEXT_USE
+                                  |JIT_INSN_VALUE2_LIVE | 
JIT_INSN_VALUE2_NEXT_USE);
+               }
+       }
 }
 
 void _jit_function_compute_liveness(jit_function_t func)
@@ -208,9 +470,27 @@
                /* Perform peephole optimization on branches to branches */
                _jit_block_peephole_branch(block);
 
+#if USE_FORWARD_PROPAGATION
+               /* Perform forward copy propagation for the block */
+               forward_propagation(block);
+#endif
+
+               /* Reset the liveness flags for the next block */
+               reset_liveness_flags(block, 0);
+
                /* Compute the liveness flags for the block */
                compute_liveness_for_block(block);
 
+#if USE_BACKWARD_PROPAGATION
+               /* Perform backward copy propagation for the block */
+               if(backward_propagation(block))
+               {
+                       /* Reset the liveness flags and compute them again */
+                       reset_liveness_flags(block, 1);
+                       compute_liveness_for_block(block);
+               }
+#endif
+
                /* Move on to the next block in the function */
                block = block->next;
        }

Index: jit/jit-value.c
===================================================================
RCS file: /sources/dotgnu-pnet/libjit/jit/jit-value.c,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -b -r1.10 -r1.11
--- jit/jit-value.c     13 Feb 2006 09:26:18 -0000      1.10
+++ jit/jit-value.c     28 May 2007 02:41:28 -0000      1.11
@@ -627,7 +627,6 @@
                        value->is_temporary = 0;
                        value->is_local = 1;
                        value->is_addressable = 1;
-                       value->live = 1;
 
                        /* Mark the two functions as not leaves because we will 
need
                           them to set up proper frame pointers to allow us to 
access
@@ -640,7 +639,6 @@
                        /* Reference from another block in same function: local 
*/
                        value->is_temporary = 0;
                        value->is_local = 1;
-                       value->live = 1;
                        if(_jit_gen_is_global_candidate(value->type))
                        {
                                value->global_candidate = 1;




reply via email to

[Prev in Thread] Current Thread [Next in Thread]