Subversion Repositories openrisc

/* Loop manipulation code for GNU compiler.

   Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009 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 3, 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 COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "rtl.h"

#include "hard-reg-set.h"

#include "obstack.h"

#include "basic-block.h"

#include "cfgloop.h"

#include "cfglayout.h"

#include "cfghooks.h"

#include "output.h"

#include "tree-flow.h"

static void copy_loops_to (struct loop **, int,

                           struct loop *);

static void loop_redirect_edge (edge, basic_block);

static void remove_bbs (basic_block *, int);

static bool rpe_enum_p (const_basic_block, const void *);

static int find_path (edge, basic_block **);

static void fix_loop_placements (struct loop *, bool *);

static bool fix_bb_placement (basic_block);

static void fix_bb_placements (basic_block, bool *);

static void unloop (struct loop *, bool *);

#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))

/* Checks whether basic block BB is dominated by DATA.  */

static bool

rpe_enum_p (const_basic_block bb, const void *data)

{

  return dominated_by_p (CDI_DOMINATORS, bb, (const_basic_block) data);

}

/* Remove basic blocks BBS.  NBBS is the number of the basic blocks.  */

static void

remove_bbs (basic_block *bbs, int nbbs)

{

  int i;

  for (i = 0; i < nbbs; i++)

    delete_basic_block (bbs[i]);

}

/* Find path -- i.e. the basic blocks dominated by edge E and put them

   into array BBS, that will be allocated large enough to contain them.

   E->dest must have exactly one predecessor for this to work (it is

   easy to achieve and we do not put it here because we do not want to

   alter anything by this function).  The number of basic blocks in the

   path is returned.  */

static int

find_path (edge e, basic_block **bbs)

{

  gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);

  /* Find bbs in the path.  */

  *bbs = XCNEWVEC (basic_block, n_basic_blocks);

  return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,

                             n_basic_blocks, e->dest);

}

/* Fix placement of basic block BB inside loop hierarchy --

   Let L be a loop to that BB belongs.  Then every successor of BB must either

     1) belong to some superloop of loop L, or

     2) be a header of loop K such that K->outer is superloop of L

   Returns true if we had to move BB into other loop to enforce this condition,

   false if the placement of BB was already correct (provided that placements

   of its successors are correct).  */

static bool

fix_bb_placement (basic_block bb)

{

  edge e;

  edge_iterator ei;

  struct loop *loop = current_loops->tree_root, *act;

  FOR_EACH_EDGE (e, ei, bb->succs)

    {

      if (e->dest == EXIT_BLOCK_PTR)

        continue;

      act = e->dest->loop_father;

      if (act->header == e->dest)

        act = loop_outer (act);

      if (flow_loop_nested_p (loop, act))

        loop = act;

    }

  if (loop == bb->loop_father)

    return false;

  remove_bb_from_loops (bb);

  add_bb_to_loop (bb, loop);

  return true;

}

/* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop

   of LOOP to that leads at least one exit edge of LOOP, and set it

   as the immediate superloop of LOOP.  Return true if the immediate superloop

   of LOOP changed.  */

static bool

fix_loop_placement (struct loop *loop)

{

  unsigned i;

  edge e;

  VEC (edge, heap) *exits = get_loop_exit_edges (loop);

  struct loop *father = current_loops->tree_root, *act;

  bool ret = false;

  for (i = 0; VEC_iterate (edge, exits, i, e); i++)

    {

      act = find_common_loop (loop, e->dest->loop_father);

      if (flow_loop_nested_p (father, act))

        father = act;

    }

  if (father != loop_outer (loop))

    {

      for (act = loop_outer (loop); act != father; act = loop_outer (act))

        act->num_nodes -= loop->num_nodes;

      flow_loop_tree_node_remove (loop);

      flow_loop_tree_node_add (father, loop);

      /* The exit edges of LOOP no longer exits its original immediate

         superloops; remove them from the appropriate exit lists.  */

      for (i = 0; VEC_iterate (edge, exits, i, e); i++)

        rescan_loop_exit (e, false, false);

      ret = true;

    }

  VEC_free (edge, heap, exits);

  return ret;

}

/* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.

   enforce condition condition stated in description of fix_bb_placement. We

   start from basic block FROM that had some of its successors removed, so that

   his placement no longer has to be correct, and iteratively fix placement of

   its predecessors that may change if placement of FROM changed.  Also fix

   placement of subloops of FROM->loop_father, that might also be altered due

   to this change; the condition for them is similar, except that instead of

   successors we consider edges coming out of the loops.

   If the changes may invalidate the information about irreducible regions,

   IRRED_INVALIDATED is set to true.  */

static void

fix_bb_placements (basic_block from,

                   bool *irred_invalidated)

{

  sbitmap in_queue;

  basic_block *queue, *qtop, *qbeg, *qend;

  struct loop *base_loop;

  edge e;

  /* We pass through blocks back-reachable from FROM, testing whether some

     of their successors moved to outer loop.  It may be necessary to

     iterate several times, but it is finite, as we stop unless we move

     the basic block up the loop structure.  The whole story is a bit

     more complicated due to presence of subloops, those are moved using

     fix_loop_placement.  */

  base_loop = from->loop_father;

  if (base_loop == current_loops->tree_root)

    return;

  in_queue = sbitmap_alloc (last_basic_block);

  sbitmap_zero (in_queue);

  SET_BIT (in_queue, from->index);

  /* Prevent us from going out of the base_loop.  */

  SET_BIT (in_queue, base_loop->header->index);

  queue = XNEWVEC (basic_block, base_loop->num_nodes + 1);

  qtop = queue + base_loop->num_nodes + 1;

  qbeg = queue;

  qend = queue + 1;

  *qbeg = from;

  while (qbeg != qend)

    {

      edge_iterator ei;

      from = *qbeg;

      qbeg++;

      if (qbeg == qtop)

        qbeg = queue;

      RESET_BIT (in_queue, from->index);

      if (from->loop_father->header == from)

        {

          /* Subloop header, maybe move the loop upward.  */

          if (!fix_loop_placement (from->loop_father))

            continue;

        }

      else

        {

          /* Ordinary basic block.  */

          if (!fix_bb_placement (from))

            continue;

        }

      FOR_EACH_EDGE (e, ei, from->succs)

        {

          if (e->flags & EDGE_IRREDUCIBLE_LOOP)

            *irred_invalidated = true;

        }

      /* Something has changed, insert predecessors into queue.  */

      FOR_EACH_EDGE (e, ei, from->preds)

        {

          basic_block pred = e->src;

          struct loop *nca;

          if (e->flags & EDGE_IRREDUCIBLE_LOOP)

            *irred_invalidated = true;

          if (TEST_BIT (in_queue, pred->index))

            continue;

          /* If it is subloop, then it either was not moved, or

             the path up the loop tree from base_loop do not contain

             it.  */

          nca = find_common_loop (pred->loop_father, base_loop);

          if (pred->loop_father != base_loop

              && (nca == base_loop

                  || nca != pred->loop_father))

            pred = pred->loop_father->header;

          else if (!flow_loop_nested_p (from->loop_father, pred->loop_father))

            {

              /* No point in processing it.  */

              continue;

            }

          if (TEST_BIT (in_queue, pred->index))

            continue;

          /* Schedule the basic block.  */

          *qend = pred;

          qend++;

          if (qend == qtop)

            qend = queue;

          SET_BIT (in_queue, pred->index);

        }

    }

  free (in_queue);

  free (queue);

}

/* Removes path beginning at edge E, i.e. remove basic blocks dominated by E

   and update loop structures and dominators.  Return true if we were able

   to remove the path, false otherwise (and nothing is affected then).  */

bool

remove_path (edge e)

{

  edge ae;

  basic_block *rem_bbs, *bord_bbs, from, bb;

  VEC (basic_block, heap) *dom_bbs;

  int i, nrem, n_bord_bbs;

  sbitmap seen;

  bool irred_invalidated = false;

  if (!can_remove_branch_p (e))

    return false;

  /* Keep track of whether we need to update information about irreducible

     regions.  This is the case if the removed area is a part of the

     irreducible region, or if the set of basic blocks that belong to a loop

     that is inside an irreducible region is changed, or if such a loop is

     removed.  */

  if (e->flags & EDGE_IRREDUCIBLE_LOOP)

    irred_invalidated = true;

  /* We need to check whether basic blocks are dominated by the edge

     e, but we only have basic block dominators.  This is easy to

     fix -- when e->dest has exactly one predecessor, this corresponds

     to blocks dominated by e->dest, if not, split the edge.  */

  if (!single_pred_p (e->dest))

    e = single_pred_edge (split_edge (e));

  /* It may happen that by removing path we remove one or more loops

     we belong to.  In this case first unloop the loops, then proceed

     normally.   We may assume that e->dest is not a header of any loop,

     as it now has exactly one predecessor.  */

  while (loop_outer (e->src->loop_father)

         && dominated_by_p (CDI_DOMINATORS,

                            e->src->loop_father->latch, e->dest))

    unloop (e->src->loop_father, &irred_invalidated);

  /* Identify the path.  */

  nrem = find_path (e, &rem_bbs);

  n_bord_bbs = 0;

  bord_bbs = XCNEWVEC (basic_block, n_basic_blocks);

  seen = sbitmap_alloc (last_basic_block);

  sbitmap_zero (seen);

  /* Find "border" hexes -- i.e. those with predecessor in removed path.  */

  for (i = 0; i < nrem; i++)

    SET_BIT (seen, rem_bbs[i]->index);

  for (i = 0; i < nrem; i++)

    {

      edge_iterator ei;

      bb = rem_bbs[i];

      FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)

        if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))

          {

            SET_BIT (seen, ae->dest->index);

            bord_bbs[n_bord_bbs++] = ae->dest;

            if (ae->flags & EDGE_IRREDUCIBLE_LOOP)

              irred_invalidated = true;

          }

    }

  /* Remove the path.  */

  from = e->src;

  remove_branch (e);

  dom_bbs = NULL;

  /* Cancel loops contained in the path.  */

  for (i = 0; i < nrem; i++)

    if (rem_bbs[i]->loop_father->header == rem_bbs[i])

      cancel_loop_tree (rem_bbs[i]->loop_father);

  remove_bbs (rem_bbs, nrem);

  free (rem_bbs);

  /* Find blocks whose dominators may be affected.  */

  sbitmap_zero (seen);

  for (i = 0; i < n_bord_bbs; i++)

    {

      basic_block ldom;

      bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);

      if (TEST_BIT (seen, bb->index))

        continue;

      SET_BIT (seen, bb->index);

      for (ldom = first_dom_son (CDI_DOMINATORS, bb);

           ldom;

           ldom = next_dom_son (CDI_DOMINATORS, ldom))

        if (!dominated_by_p (CDI_DOMINATORS, from, ldom))

          VEC_safe_push (basic_block, heap, dom_bbs, ldom);

    }

  free (seen);

  /* Recount dominators.  */

  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true);

  VEC_free (basic_block, heap, dom_bbs);

  free (bord_bbs);

  /* Fix placements of basic blocks inside loops and the placement of

     loops in the loop tree.  */

  fix_bb_placements (from, &irred_invalidated);

  fix_loop_placements (from->loop_father, &irred_invalidated);

  if (irred_invalidated

      && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))

    mark_irreducible_loops ();

  return true;

}

/* Creates place for a new LOOP in loops structure.  */

static void

place_new_loop (struct loop *loop)

{

  loop->num = number_of_loops ();

  VEC_safe_push (loop_p, gc, current_loops->larray, loop);

}

/* Given LOOP structure with filled header and latch, find the body of the

   corresponding loop and add it to loops tree.  Insert the LOOP as a son of

   outer.  */

void

add_loop (struct loop *loop, struct loop *outer)

{

  basic_block *bbs;

  int i, n;

  struct loop *subloop;

  edge e;

  edge_iterator ei;

  /* Add it to loop structure.  */

  place_new_loop (loop);

  flow_loop_tree_node_add (outer, loop);

  /* Find its nodes.  */

  bbs = XNEWVEC (basic_block, n_basic_blocks);

  n = get_loop_body_with_size (loop, bbs, n_basic_blocks);

  for (i = 0; i < n; i++)

    {

      if (bbs[i]->loop_father == outer)

        {

          remove_bb_from_loops (bbs[i]);

          add_bb_to_loop (bbs[i], loop);

          continue;

        }

      loop->num_nodes++;

      /* If we find a direct subloop of OUTER, move it to LOOP.  */

      subloop = bbs[i]->loop_father;

      if (loop_outer (subloop) == outer

          && subloop->header == bbs[i])

        {

          flow_loop_tree_node_remove (subloop);

          flow_loop_tree_node_add (loop, subloop);

        }

    }

  /* Update the information about loop exit edges.  */

  for (i = 0; i < n; i++)

    {

      FOR_EACH_EDGE (e, ei, bbs[i]->succs)

        {

          rescan_loop_exit (e, false, false);

        }

    }

  free (bbs);

}

/* Multiply all frequencies in LOOP by NUM/DEN.  */

void

scale_loop_frequencies (struct loop *loop, int num, int den)

{

  basic_block *bbs;

  bbs = get_loop_body (loop);

  scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);

  free (bbs);

}

/* Recompute dominance information for basic blocks outside LOOP.  */

static void

update_dominators_in_loop (struct loop *loop)

{

  VEC (basic_block, heap) *dom_bbs = NULL;

  sbitmap seen;

  basic_block *body;

  unsigned i;

  seen = sbitmap_alloc (last_basic_block);

  sbitmap_zero (seen);

  body = get_loop_body (loop);

  for (i = 0; i < loop->num_nodes; i++)

    SET_BIT (seen, body[i]->index);

  for (i = 0; i < loop->num_nodes; i++)

    {

      basic_block ldom;

      for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);

           ldom;

           ldom = next_dom_son (CDI_DOMINATORS, ldom))

        if (!TEST_BIT (seen, ldom->index))

          {

            SET_BIT (seen, ldom->index);

            VEC_safe_push (basic_block, heap, dom_bbs, ldom);

          }

    }

  iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);

  free (body);

  free (seen);

  VEC_free (basic_block, heap, dom_bbs);

}

/* Creates an if region as shown above. CONDITION is used to create

   the test for the if.

   |

   |     -------------                 -------------

   |     |  pred_bb  |                 |  pred_bb  |

   |     -------------                 -------------

   |           |                             |

   |           |                             | ENTRY_EDGE

   |           | ENTRY_EDGE                  V

   |           |             ====>     -------------

   |           |                       |  cond_bb  |

   |           |                       | CONDITION |

   |           |                       -------------

   |           V                        /         \

   |     -------------         e_false /           \ e_true

   |     |  succ_bb  |                V             V

   |     -------------         -----------       -----------

   |                           | false_bb |      | true_bb |

   |                           -----------       -----------

   |                                   \           /

   |                                    \         /

   |                                     V       V

   |                                   -------------

   |                                   |  join_bb  |

   |                                   -------------

   |                                         | exit_edge (result)

   |                                         V

   |                                    -----------

   |                                    | succ_bb |

   |                                    -----------

   |

 */

edge

create_empty_if_region_on_edge (edge entry_edge, tree condition)

{

  basic_block cond_bb, true_bb, false_bb, join_bb;

  edge e_true, e_false, exit_edge;

  gimple cond_stmt;

  tree simple_cond;

  gimple_stmt_iterator gsi;

  cond_bb = split_edge (entry_edge);

  /* Insert condition in cond_bb.  */

  gsi = gsi_last_bb (cond_bb);

  simple_cond =

    force_gimple_operand_gsi (&gsi, condition, true, NULL,

                              false, GSI_NEW_STMT);

  cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE);

  gsi = gsi_last_bb (cond_bb);

  gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);

  join_bb = split_edge (single_succ_edge (cond_bb));

  e_true = single_succ_edge (cond_bb);

  true_bb = split_edge (e_true);

  e_false = make_edge (cond_bb, join_bb, 0);

  false_bb = split_edge (e_false);

  e_true->flags &= ~EDGE_FALLTHRU;

  e_true->flags |= EDGE_TRUE_VALUE;

  e_false->flags &= ~EDGE_FALLTHRU;

  e_false->flags |= EDGE_FALSE_VALUE;

  set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src);

  set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb);

  set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb);

  set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);

  exit_edge = single_succ_edge (join_bb);

  if (single_pred_p (exit_edge->dest))

    set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb);

  return exit_edge;

}

/* create_empty_loop_on_edge

   |

   |    - pred_bb -                   ------ pred_bb ------

   |   |           |                 | iv0 = initial_value |

   |    -----|-----                   ---------|-----------

   |         |                       ______    | entry_edge

   |         | entry_edge           /      |   |

   |         |             ====>   |      -V---V- loop_header -------------

   |         V                     |     | iv_before = phi (iv0, iv_after) |

   |    - succ_bb -                |      ---|-----------------------------

   |   |           |               |         |

   |    -----------                |      ---V--- loop_body ---------------

   |                               |     | iv_after = iv_before + stride   |

   |                               |     | if (iv_before < upper_bound)    |

   |                               |      ---|--------------\--------------

   |                               |         |               \ exit_e

   |                               |         V                \

   |                               |       - loop_latch -      V- succ_bb -

   |                               |      |              |     |           |

   |                               |       /-------------       -----------

   |                                \ ___ /

   Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME

   that is used before the increment of IV. IV_BEFORE should be used for

   adding code to the body that uses the IV.  OUTER is the outer loop in

   which the new loop should be inserted.

   Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and

   inserted on the loop entry edge.  This implies that this function

   should be used only when the UPPER_BOUND expression is a loop

   invariant.  */

struct loop *

create_empty_loop_on_edge (edge entry_edge,

                           tree initial_value,

                           tree stride, tree upper_bound,

                           tree iv,

                           tree *iv_before,

                           tree *iv_after,

                           struct loop *outer)

{

  basic_block loop_header, loop_latch, succ_bb, pred_bb;

  struct loop *loop;

  gimple_stmt_iterator gsi;

  gimple_seq stmts;

  gimple cond_expr;

  tree exit_test;

  edge exit_e;

  int prob;

  gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);

  /* Create header, latch and wire up the loop.  */

  pred_bb = entry_edge->src;

  loop_header = split_edge (entry_edge);

  loop_latch = split_edge (single_succ_edge (loop_header));

  succ_bb = single_succ (loop_latch);

  make_edge (loop_header, succ_bb, 0);

  redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header);

  /* Set immediate dominator information.  */

  set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb);

  set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header);

  set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header);

  /* Initialize a loop structure and put it in a loop hierarchy.  */

  loop = alloc_loop ();

  loop->header = loop_header;

  loop->latch = loop_latch;

  add_loop (loop, outer);

  /* TODO: Fix frequencies and counts.  */

  prob = REG_BR_PROB_BASE / 2;

  scale_loop_frequencies (loop, REG_BR_PROB_BASE - prob, REG_BR_PROB_BASE);

  /* Update dominators.  */

  update_dominators_in_loop (loop);

  /* Modify edge flags.  */

  exit_e = single_exit (loop);

  exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;

  single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;

  /* Construct IV code in loop.  */

  initial_value = force_gimple_operand (initial_value, &stmts, true, iv);

  if (stmts)

    {

      gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);

      gsi_commit_edge_inserts ();

    }

  upper_bound = force_gimple_operand (upper_bound, &stmts, true, NULL);

  if (stmts)

    {

      gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);

      gsi_commit_edge_inserts ();

    }

  gsi = gsi_last_bb (loop_header);

  create_iv (initial_value, stride, iv, loop, &gsi, false,

             iv_before, iv_after);

  /* Insert loop exit condition.  */

  cond_expr = gimple_build_cond

    (LT_EXPR, *iv_before, upper_bound, NULL_TREE, NULL_TREE);

  exit_test = gimple_cond_lhs (cond_expr);

  exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,

                                        false, GSI_NEW_STMT);

  gimple_cond_set_lhs (cond_expr, exit_test);

  gsi = gsi_last_bb (exit_e->src);

  gsi_insert_after (&gsi, cond_expr, GSI_NEW_STMT);

  split_block_after_labels (loop_header);

  return loop;

}

/* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting

   latch to header and update loop tree and dominators

   accordingly. Everything between them plus LATCH_EDGE destination must

   be dominated by HEADER_EDGE destination, and back-reachable from

   LATCH_EDGE source.  HEADER_EDGE is redirected to basic block SWITCH_BB,

   FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and

   TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.

   Returns the newly created loop.  Frequencies and counts in the new loop

   are scaled by FALSE_SCALE and in the old one by TRUE_SCALE.  */

struct loop *

loopify (edge latch_edge, edge header_edge,

         basic_block switch_bb, edge true_edge, edge false_edge,