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);
}