Re: Flow analysis and optimization with computed gotos

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi Brad,

On Sat, 2 Dec 2000, Brad Lucier wrote:

> I fear that some of what I wrote last night might be nonsense; it's no
> longer clear to me that the techniques implemented in flow.c work in
> the presence of multiple computed gotos in a rooutine, and that
> techniques appropriate for interprocedural PRE will be needed.  (I
> believe that computed gotos can be handled the same as function
> returns, so perhaps the same analysis techniques will be needed.)

Seems so, yes, but as we don't have any mean for interprocedural PRE we
can't use that. We would need to write it. But the problem we are facing
is more narrow: Normally for PRE to be as effective as possible, it needs
to split critical edges. Abnormal edges can't be split. So there is a
conflict ;-) We need to make PRE less effective, but more correct. In
presence of abnormal critical edges, PRE's effects are similar to
speculative code motion.

In the attachment is a small patch to gcse.c which slightly helps in this
situation (at least in my test case). Can you try it? If the instruction
in question can trap, and the edge in question is abnormal and critical it
doesn't move the insn to the end of the source, but instead to the
beginning of the destination. This can create redundancy again, but is at
least later than now (so it generates less incorrect code ;-)

It still isn't correct though. E.g. if the expression didn't come from the
destination block. The real solution is, that abnormal critical edges
(s->d) kill all expressions from which it's not provable that they don't
trap in block d. So the data collection phase needs adjustment (which
requires too much thinking work right now, given the state of my brain ;)

> E. Morel and C. Renvoise, Interprocedural Elimination of
> Partial Redundancies, in {\it Program Flow Analysis: Theory and
> Applications,} S. S. Muchnick and N. D. Jones, eds., Prentice-Hall,
> Englewood Cliffs, NJ, 1981, pp. 160--188.

I bet this still uses the bidirectional data flow solver (which would
mean, that we wouldn't want to implement this).


Ciao,
Michael.
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.111
diff -u -r1.111 gcse.c
--- gcse.c	2000/11/21 21:00:20	1.111
+++ gcse.c	2000/12/04 00:50:02
@@ -594,6 +594,7 @@
 static void free_pre_mem	PARAMS ((void));
 static void compute_pre_data	PARAMS ((void));
 static int pre_expr_reaches_here_p PARAMS ((int, struct expr *, int));
+static void insert_insn_begin_bb PARAMS ((struct expr *, int));
 static void insert_insn_end_bb	PARAMS ((struct expr *, int, int));
 static void pre_insert_copy_insn PARAMS ((struct expr *, rtx));
 static void pre_insert_copies	PARAMS ((void));
@@ -4284,6 +4285,66 @@
   return pat;
 }
   
+static void
+insert_insn_begin_bb (expr, bb)
+     struct expr *expr;
+     int bb;
+{
+  basic_block b = BASIC_BLOCK (bb);
+  rtx insn = b->head;
+  rtx new_insn;
+  rtx reg = expr->reaching_reg;
+  int regno = REGNO (reg);
+  rtx pat;
+  int i;
+
+  pat = process_insert_insn (expr);
+
+  if (GET_CODE (insn) == CODE_LABEL)
+    insn = NEXT_INSN (insn);
+  if (NOTE_INSN_BASIC_BLOCK_P (insn))
+    insn = NEXT_INSN (insn);
+  if (insn == b->head)
+    new_insn = emit_block_insn_before (pat, insn, b);
+  else
+    new_insn = emit_block_insn_after (pat, insn, b);
+
+  /* Keep block number table up to date.
+     Note, PAT could be a multiple insn sequence, we have to make
+     sure that each insn in the sequence is handled.  */
+  if (GET_CODE (pat) == SEQUENCE)
+    {
+      for (i = 0; i < XVECLEN (pat, 0); i++)
+	{
+	  rtx insn = XVECEXP (pat, 0, i);
+
+	  set_block_num (insn, bb);
+	  if (INSN_P (insn))
+	    add_label_notes (PATTERN (insn), new_insn);
+
+	  note_stores (PATTERN (insn), record_set_info, insn);
+	}
+    }
+  else
+    {
+      add_label_notes (SET_SRC (pat), new_insn);
+      set_block_num (new_insn, bb);
+
+      /* Keep register set table up to date.  */
+      record_one_set (regno, new_insn);
+    }
+
+  gcse_create_count++;
+
+  if (gcse_file)
+    {
+      fprintf (gcse_file, "PRE/HOIST: begin of bb %d, insn %d, ",
+	       bb, INSN_UID (new_insn));
+      fprintf (gcse_file, "copying expression %d to reg %d\n",
+	       expr->bitmap_index, regno);
+    }
+}
+
 /* Add EXPR to the end of basic block BB.
 
    This is used by both the PRE and code hoisting.
@@ -4506,7 +4567,22 @@
 			   now.  */
 
 			if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
-			  insert_insn_end_bb (index_map[j], bb, 0);
+			  {
+			    /* If this is a critical edge, and the inserted
+			       instruction might trap, we can't insert it
+			       at the end of the source block.  Instead we
+			       insert it at the beginning of the destination
+			       block, which might cause redundancy again.
+			       This is better than generating wrong code.  */
+			    if ((eg->flags & EDGE_CRITICAL) == EDGE_CRITICAL
+			        && may_trap_p (index_map[j]->expr))
+			      {
+			        int dbb = eg->dest->index;
+			        insert_insn_begin_bb (index_map[j], dbb);
+			      }
+			    else
+			      insert_insn_end_bb (index_map[j], bb, 0);
+			  }
 			else
 			  {
 			    insn = process_insert_insn (index_map[j]);