gcc/loop-init.c

/* Loop optimizer initialization routines.
   Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING.  If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "cfglayout.h"

static void fixup_loop_exit_succesor (basic_block, basic_block);

/* Initialize loop optimizer.  */

struct loops *
loop_optimizer_init (FILE *dumpfile)
{
  struct loops *loops = xcalloc (1, sizeof (struct loops));
  edge e;

  /* Initialize structures for layout changes.  */
  cfg_layout_initialize (0);

  /* Avoid annoying special cases of edges going to exit
     block.  */
  for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
    if ((e->flags & EDGE_FALLTHRU) && e->src->succ->succ_next)
      split_edge (e);

  /* Find the loops.  */

  if (flow_loops_find (loops, LOOP_TREE) <= 1)
    {
      basic_block bb;

      /* No loops.  */
      flow_loops_free (loops);
      free_dominance_info (CDI_DOMINATORS);
      free (loops);

      /* Make chain.  */
      FOR_EACH_BB (bb)
	if (bb->next_bb != EXIT_BLOCK_PTR)
	  bb->rbi->next = bb->next_bb;
	  cfg_layout_finalize ();
      return NULL;
    }

  /* Not going to update these.  */
  free (loops->cfg.rc_order);
  loops->cfg.rc_order = NULL;
  free (loops->cfg.dfs_order);
  loops->cfg.dfs_order = NULL;

  /* Create pre-headers.  */
  create_preheaders (loops, CP_SIMPLE_PREHEADERS);

  /* Force all latches to have only single successor.  */
  force_single_succ_latches (loops);

  /* Mark irreducible loops.  */
  mark_irreducible_loops (loops);

  /* Dump loops.  */
  flow_loops_dump (loops, dumpfile, NULL, 1);

#ifdef ENABLE_CHECKING
  verify_dominators (CDI_DOMINATORS);
  verify_loop_structure (loops);
#endif

  return loops;
}

/* The first basic block is moved after the second in the reorder chain.  */
static void
fixup_loop_exit_succesor (basic_block exit_succ, basic_block latch)
{
  basic_block bb = exit_succ;
  basic_block bb1 = latch;

  if (!(bb && bb->rbi->next))
    return;

  if (!bb1)
    return;
 

  if (bb && bb->rbi->next)
    {
      basic_block c = ENTRY_BLOCK_PTR->next_bb;

      while (c->rbi->next != bb)
	c = c->rbi->next;

      c->rbi->next = bb->rbi->next;
    }

  if(bb1->rbi->next == NULL)
    {
      bb1->rbi->next=bb;
      bb->rbi->next=NULL;
    }
  else
    
    {
      basic_block tmp;

      tmp = bb1->rbi->next;
      bb1->rbi->next = bb;
      bb->rbi->next = tmp;
    }
}

/* Finalize loop optimizer.  */
void
loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
{
  basic_block bb;
  unsigned int i;

  /* Finalize layout changes.  */
  /* Make chain.  */
  FOR_EACH_BB (bb)
    if (bb->next_bb != EXIT_BLOCK_PTR)
      bb->rbi->next = bb->next_bb;

  /* Another dump.  */
  flow_loops_dump (loops, dumpfile, NULL, 1);

  /* For loops ending with a branch and count instruction, move the basic 
     block found before the unrolling on the fallthru path of this branch,
     after the unrolled code.  This will allow branch simplification.  */
  for (i = 1; i < loops->num; i++)
    {
      struct loop *loop = loops->parray[i];
      struct loop_desc *desc;
      basic_block loop_real_latch, bb, bb_exit;
      edge e;

      if (loop == NULL)
	continue;
      if (!loop->simple)
        continue;
      if (!loop->has_desc)
	continue;

      if (loop->lpt_decision.decision != LPT_UNROLL_RUNTIME)
	continue;

      desc = &loop->desc;
      if (desc == NULL)
        continue;
      if (loop->latch->pred == NULL)
        continue;

      loop_real_latch = loop->latch->pred->src;
 

      if (desc->postincr)
	continue; 
      if (!is_bct_cond (BB_END (loop_real_latch)))
	 continue;

      for (e = loop_real_latch->succ; e ; e = e->succ_next)
	if (e->flags & EDGE_FALLTHRU)
          break;

      if (e == NULL)
	continue;

      bb_exit = e->dest;
     
      bb = NULL;

      /* Leave the case of the bb_exit falling through to exit to 
         fixed_fallthru_exit_predecessor */
      for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
         if (e->flags & EDGE_FALLTHRU)
        bb = e->src;
  
      if (bb_exit == bb)
	continue;
      
      fixup_loop_exit_succesor (bb_exit, loop->latch);
    }

  /* Clean up.  */
  flow_loops_free (loops);
  free_dominance_info (CDI_DOMINATORS);
  free (loops);

  /* Finalize changes.  */
  cfg_layout_finalize ();

  /* Checking.  */
#ifdef ENABLE_CHECKING
  verify_flow_info ();
#endif
}