Loop optimiser upgrade (Was RFC: BB duplication code)

[Michael Hayes]

Jan Hubicka writes:

 > > I'd say strip the loop notes.  You don't really lose any information,
 > > in that correct information can always be obtained from the shape of
 > > the CFG, via flow_loop_nodes_find.
 > Agreed - anyway an loop optimizer is still an barrier for my effort.
 > Until it is converted to use CFG, we can't make flow info survive.

I agree that the loop notes should be weeded out.  The one useful loop
note is the VTOP note that indicates if the loop exit code has been
duplicated.  When this loop exists and we know that the loop body will
be executed at least once if the loop header is entered.  I'm not sure
of an easy means to determine this from the CFG.

 > Converting whole loop optimizer at once can be huge task. Additionally some
 > pieces should be already obsoletted (as code hoisting).

Yes, I agree.  Before I got snowed under with my real job I had a big
hack at converting the old loop optimiser to use the CFG.  The problem
was ensuring that I did not break anything.  I think a better approach
is to write another loop optimiser that can run after the current loop
optimiser and then one day replace it completely.  After the current
loop optimiser has run, I'd say that we should strip the loop notes
completely (or at least regenerate them from the CFG) and rely totally
on the CFG.

 > So I think that in mid term, we can make the BIV/GIV discovery code idedendent
 > on loop notes (it should not be that dificult) and start work on new loop
 > unroller done as separate pass.

Yes, this could be done standalone.  However, it would need loop
invariant discovery code first.  This is one of the reasons I wrote
the dataflow code that Dan Berlin has marvellously souped up for the
new register allocator.  It is also the reason I added routines to
loop.c for sinking and hoisting insns so that I could track the
changes to the dataflow.

What started to stump me was an efficient way to update the dataflow
information incrementally after each loop optimisation.  To mitigate
the dataflow computation needed, I structured the loop optimiser to
optimise all the innermost loops first, then all the next level loops,
and so on.  This way the loops could be optimised independently
without having to always recompute the dataflow information.

I've attached the basic structure of the data flow based loop
optimiser that I was working on.

Michael

-------------- next part --------------
static void 
loop_notes_strip (f)
     rtx f;
{
  rtx insn;

  /* Strip old loop notes.  */
  for (insn = f; insn; insn = NEXT_INSN (insn))
    {
      if (GET_CODE (insn) == NOTE
	  && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG 
	      || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
	      || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END))
	delete_insn (insn);
    }
}


static void 
loop_note_stats_dump (f, stream)
     rtx f;
     FILE *stream;
{
  struct {
    int loops;
    int vtops;
    int conts;
  } loop_stats;

 
  /* Log old loop note stats.  */
  loop_stats.loops = 0;
  loop_stats.conts = 0;
  loop_stats.vtops = 0;
  
  for (insn = f; insn; insn = NEXT_INSN (insn))
    {
      if (GET_CODE (insn) == NOTE
	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
	loop_stats.loops++;
      else if (GET_CODE (insn) == NOTE
	       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
	loop_stats.conts++;
      else if (GET_CODE (insn) == NOTE
	       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
	loop_stats.vtops++;
    }
  
  if (stream)
    fprintf (stream, 
	     "\n;; Loop stats: %d loops, %d conts, %d vtops\n",
	     loop_stats.loops, loop_stats.conts, loop_stats.vtops);
}  


/* Split an edge to create a new basic block and insert a
   NOTE_INSN_DELETED as a placeholder.  */

static void
loop_edge_split (e)
     edge e;
{
  rtx seq;

  start_sequence ();
  emit_note (NULL_PTR, NOTE_INSN_DELETED);
  seq = gen_sequence ();
  end_sequence ();
  
  /* If we don't need to split the edge then we still want to add a
     dummy note placeholder to the end of the block so that we can
     insert insns before it without having to update bb->end all the
     time.  */

  insert_insn_on_edge (seq, e);
}


static void
loop_pre_header_create (e)
     edge e;
{
  basic_block bb = e->src;

  /* We know that this edge is the only forward edge into
     the loop header.  */

  /* If the source of the edge has a single successor then the source
     is the pre_header and we do not have to split any edges.  */
  if (bb->succ->succ_next == NULL
      && bb != ENTRY_BLOCK_PTR)
    {
      /* insert_insn_on_edge cannot handle a block with a single
	 successor and with a single jump_insn at the end.  Note that
	 we know that the jump must be unconditional since the block
	 has a single successor.  We can use this jump insn to hoist
	 insns before.  */
      if (GET_CODE (bb->end) == JUMP_INSN)
	return;

      /* We need a dummy insn at the end of the block to insert the
	 insn before.  loop_edge_split will do this for us although no
	 actual edges get split.  */
    }
  
  loop_edge_split (e);
}


static void
loop_landing_pad_create (e)
     edge e;
{
  loop_edge_split (e);
}



/* Set the invalid flag for each loop we cannot process.  */

static void
loops_validate (loops)
     struct loops *loops;
{
  int i;
  
  for (i = 0; i < loops->num; i++)
    {
      int j;
      struct loop *loop = &loops->array[i];
      
      /* Invalidate natural loops with multiple forward edges into the
	 loop header or with shared headers for now.  These should be
	 transformed to have a single entry edge to simplify hoisting
	 or we could insert hoisted insns onto all entry edges.  
	 Also invalidate loops with abnormal entry or exit edges
	 since we cannot split these edges.  */
      if (loop->num_entries != 1 || loop->shared
	  || (loop->entry_edges[0]->flags & EDGE_ABNORMAL) != 0)
	{
	  loop->invalid = 1;
	  continue;
	}
      
      for (j = 0; j < loop->num_exits; j++)
	if ((loop->exit_edges[j]->flags & EDGE_ABNORMAL) != 0)
	  loop->invalid = 1;
    }
}


/* Entry point of this file.  Perform loop optimization
   on the current function.  F is the first insn of the function
   and DUMPFILE is a stream for output of a trace of actions taken
   (or 0 if none should be output).  */

void
loop_optimize (f, dumpfile, flags)
     /* f is the first instruction of a chain of insns for one function.  */
     rtx f;
     FILE *dumpfile;
     int flags;
{
  register rtx insn;
  register int i;
  struct loops loops_data;
  struct loops *loops = &loops_data;
  struct loop_info *loops_info;
  struct loop **loops_order;
  int loop_level;
  int n_basic_blocks_orig;

  loop_dump_stream = dumpfile;

  init_recog_no_volatile ();

  max_reg_before_loop = max_reg_num ();

  loop_note_stats_dump (f, loop_dump_stream);

  loop_notes_strip (f);

  /* Build CFG.  */
  find_basic_blocks (f, max_reg_before_loop, loop_dump_stream);
  cleanup_cfg (f);

  /* Find natural loops within the CFG.  Only build the loop tree
     and find the loop entry and exit edges.  */
  flow_loops_find (loops, LOOP_ALL);

  if (! loops->num)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream, 
		 ";; Loop stats: 0 natural loops, %d marked loops\n",
		 loop_stats.loops);
      flow_loops_free (loops);
      return;
    }

  loops_validate (loops);
   
  loops_bbs_find (loops);

  /* Create pre-header and landing-pad nodes to hoist and sink insns
     into.  Use dummy note as a placeholder so that we can insert
     insns before it.  */
  for (i = loops->num - 1; i >= 0; i--)
    {
      int j;
      struct loop *loop = &loops->array[i];

      if (loop->invalid)
	continue;
      
      loop_pre_header_create (loop->entry_edges[0]);
      
      for (j = 0; j < loop->num_exits; j++)
	if ((loop->exit_edges[j]->flags & EDGE_FAKE) == 0)
	  loop_landing_pad_create (loop->exit_edges[j]);

      /* Try inverting the loop; i.e., converting a while loop
	 into a repeat loop.  */
      loop_invert (loop);
    }

  n_basic_blocks_orig = n_basic_blocks;

  commit_edge_insertions ();

  /* Add fake edges to the exit block for calls that may exit.
     This will introduce new basic blocks and new loop exits.
     We do not need landing pads for these new exits since
     they will never get executed.  */
  loop_call_edges_add (loops);

  if (n_basic_blocks != n_basic_blocks_orig)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream, 
		 "\n;; Loop %d basic blocks created\n",
		 n_basic_blocks - n_basic_blocks_orig);

      /* Update the loop data.  This is only necessary if new basic
         blocks were created.  */
      flow_loops_update (loops, LOOP_ALL);

      loops_validate (loops);
    }

  /* Allocate and initialize auxiliary loop information.  */
  loops_info = xcalloc (loops->num, sizeof (struct loop_info));
  for (i = 0; i < loops->num; i++)
    loops->array[i].aux = loops_info + i;

  /* Now find all register lifetimes.  */
  reg_scan (f, max_reg_before_loop, 1);

  /* Initialise dataflow information.  */
  df = df_init ();

  /* Copy pointer to dominator data.  */
  df->dom = loops->cfg.dom;

  /* This must occur after reg_scan so that registers created by gcse
     will have entries in the register tables.

     We could have added a call to reg_scan after gcse_main in toplev.c,
     but moving this call to init_alias_analysis is more efficient.  */
  init_alias_analysis ();

  /* Link loops in terms of the loop level.  */
  loops_order = xcalloc (loops->levels + 1, sizeof (*loops_order));
  for (i = loops->num - 1; i >= 0; i--)
    {
      struct loop *loop = &loops->array[i];
      loop->next = loops_order[loop->level];
      loops_order[loop->level] = loop;
    }

  /* Now optimize the loops with all the innermost loops first (level
     1), followed by all the level 2 loops, etc.  Note that at each
     level the loops are independent and thus the transformations on a
     loop should not screw up the dataflow information for other loops
     at the same level.  */

  for (loop_level = 1; loop_level <= loops->levels; loop_level++)
    {
      struct loop *loop;

      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "\n;; Processing loops at level %d.\n",
		 loop_level);

      /* Create data flow information.  */
      if (df_analyse (df, 0, DF_LOOP))
	df_dump (df, DF_LOOP_DUMP, loop_dump_stream);

      /* Loop optimizations should only affect the dataflow
	 information for the blocks within the loop and for the loop
	 pre-header and landing-pad blocks.  Newly created uses should
	 not be exposed above the loop pre-header unless an
	 optimization has gone wrong.  Thus the existing bits within
	 the IN bitmaps for reaching uses should not change.
	 Similarly, newly created defs within the loop should not be
	 used after the end of the loop landing-pads.  Thus there is
	 no need to propagate dataflow information before the loop
	 pre-header or after the loop landing-pads.  */
      
      /* Scan loops looking for valid ones to optimize.  */
      for (loop = loops_order[loop_level]; loop && !loop->invalid; 
	   loop = loop->next)
	{
	  struct loop_info *loop_info = LOOP_INFO (loop);
	  
	  if (loop->invalid)
	    continue;
	  
	  /* Set up variables describing this loop.  */
	  loop_scan (loop);

	  /* Give up on this loop if it has a setjmp.  */
	  if (loop_info->has_setjmp)
	    {
	      if (loop_dump_stream)
		fprintf (loop_dump_stream,
			 "\n;; Loop%d ignored due to setjmp.\n",
			 loop->num);
	      loop->invalid = 1;
	      continue;
	    }
	}
      
      /* Perform loop invariant code motion.  */
      for (loop = loops_order[loop_level]; loop && !loop->invalid; 
	   loop = loop->next)
	{
	  struct loop_regs *regs = LOOP_REGS (loop);

	  if (loop_dump_stream)
	    fprintf (loop_dump_stream,
		     "\n;; Loop%d invariant code motion.\n",
			 loop->num);

	  loop_invariants_move (loop, flags);
	}

      /* Update data flow information.  */
      if (df_analyse (df, (sbitmap)-1, DF_LOOP))
	df_dump (df, DF_LOOP_DUMP, loop_dump_stream);

      /* Perform shadowing of loop mems.  */
      for (loop = loops_order[loop_level]; loop && !loop->invalid; 
	   loop = loop->next)
	{
	  if (loop_dump_stream)
	    fprintf (loop_dump_stream,
		     "\n;; Loop%d mem loading.\n",
			 loop->num);
	  loop_mems_load (loop);
	}

      /* Update data flow information for blocks that were
	 modified.  */
      if (df_analyse (df, (sbitmap)-1, DF_LOOP))
	df_dump (df, DF_LOOP_DUMP, loop_dump_stream);

      /* Find induction variables.  */
      for (loop = loops_order[loop_level]; loop && !loop->invalid; 
	   loop = loop->next)
	{
	}

      /* Invert loop.  */
      for (loop = loops_order[loop_level]; loop && !loop->invalid; 
	   loop = loop->next)
	{
	}
	  
      /* Update data flow information for blocks that were
	 modified.  */
      if (df_analyse (df, (sbitmap)-1, DF_LOOP))
	df_dump (df, DF_LOOP_DUMP, loop_dump_stream);

      /* Unroll loop.  */
      for (loop = loops_order[loop_level]; loop && !loop->invalid; 
	   loop = loop->next)
	{
	}

      /* Update data flow information for blocks that were
	 modified.  */
      if (df_analyse (df, (sbitmap)-1, DF_LOOP))
	df_dump (df, DF_LOOP_DUMP, loop_dump_stream);

      /* Induction variable strength reduction.  */
      for (loop = loops_order[loop_level]; loop && !loop->invalid; 
	   loop = loop->next)
	{
	}
    }

  /* If there were lexical blocks inside the loop, they have been
     replicated.  We will now have more than one NOTE_INSN_BLOCK_BEG
     and NOTE_INSN_BLOCK_END for each such block.  We must duplicate
     the BLOCKs as well.  */
  if (write_symbols != NO_DEBUG)
    reorder_blocks ();

  end_alias_analysis ();

  if (loop_dump_stream)
    flow_loops_dump (loops, loop_dump_stream, loop_dump_aux, 1);

  /* Clean up.  */
  df_finish (df);
  free (loops_order);
  free (loops_info);
  flow_loops_free (loops);
}