home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / ae / AE / ae-loop.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-02-28  |  15.8 KB  |  661 lines
  1. /* AE program profiling system.
  2.    Code to find loops in a control-flow graph.
  3.    Copyright (C) 1989, 1990 by James R. Larus (larus@cs.wisc.edu)
  4.  
  5.    AE and AEC are free software; you can redistribute it and/or modify it
  6.    under the terms of the GNU General Public License as published by the
  7.    Free Software Foundation; either version 1, or (at your option) any
  8.    later version.
  9.  
  10.    AE and AEC are distributed in the hope that it will be useful, but
  11.    WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.    General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with GNU CC; see the file COPYING.  If not, write to James R.
  17.    Larus, Computer Sciences Department, University of Wisconsin--Madison,
  18.    1210 West Dayton Street, Madison, WI 53706, USA or to the Free
  19.    Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21.  
  22. /* $Header: /var/home/larus/AE/AE/RCS/ae-loop.c,v 2.2 90/02/14 09:19:47 larus Exp Locker: larus $ */
  23.  
  24.  
  25. #include "config.h"
  26. #include "rtl.h"
  27. #include "basic-block.h"
  28. #include "ae.h"
  29.  
  30.  
  31. /* Find the arcs in the control flow graph that entry, exit, and
  32.    iterate loops.  We find loops by computing the control-flow
  33.    dominators, then finding edges whose destination dominates their
  34.    source (loop back edges in reducible flow graphs).  From the back
  35.    edges and the loop header, we can compute the entire loop body and
  36.    record the appropriate set of edges. */
  37.  
  38.  
  39. int block_succ_p ();
  40. void compress_semid ();
  41. int condjump_p ();
  42. int dominate_p ();
  43. void dfs_number ();
  44. void dfs_number_sub ();
  45. int eval_semid ();
  46. void find_dominators ();
  47. void find_loops ();
  48. int find_loop_back_edge ();
  49. void find_natural_loop ();
  50. int head_to_block_number ();
  51. rtx jump_target ();
  52. void link_semid ();
  53. void mark_insn ();
  54. int multiway_jump_p ();
  55. void record_exit_edge ();
  56. void record_exit_edge1 ();
  57. int simplejump_p ();
  58.  
  59.  
  60. void bzero ();
  61. void free ();
  62. char *malloc ();
  63.  
  64.  
  65. /* Information on instructions in function. */
  66.  
  67. extern aux_insn_info *insn_info;
  68.  
  69.  
  70. /* Index of a basic block */
  71.  
  72. typedef unsigned short bb_index;
  73.  
  74.  
  75.  
  76. /* Used to assign unique numbers to loops within a function. */
  77.  
  78. static int loop_no = 0;
  79.  
  80.  
  81. /* Represent a set of basic blocks as a bit vector  */
  82.  
  83. #define SET_BBSET_BIT(BBS, BN)                    \
  84.   BBS [(BN) / REGSET_ELT_BITS] |= 1 << ((BN) % REGSET_ELT_BITS)
  85.  
  86.  
  87. #define GET_BBSET_BIT(BBS, BN)                    \
  88.   BBS [(BN) / REGSET_ELT_BITS] & (1 << ((BN) % REGSET_ELT_BITS))
  89.  
  90.  
  91. #define FOREACH_SET_BIT(BBS, LIMIT, N, BODY)            \
  92.   {                                \
  93.     register int _i_, _j_, _c_;                    \
  94.     for (_i_ = 0, _c_ = LIMIT;                    \
  95.      _i_ < (LIMIT + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS;    \
  96.      _i_ ++, _c_ -= REGSET_ELT_BITS)            \
  97.       {                                \
  98.     register int _l_ = (_c_ < REGSET_ELT_BITS ? _c_ : REGSET_ELT_BITS);\
  99.     register int _w_ = BBS [_i_];                \
  100.     if (_w_ != 0)                        \
  101.       for (_j_ = 0; _j_ < _l_; _j_ ++)            \
  102.         {                            \
  103.           int N = (_i_ * REGSET_ELT_BITS) + _j_;        \
  104.           if (_w_ & (1 << _j_))                \
  105.         BODY;                        \
  106.         }}}
  107.  
  108.  
  109. /* Entry N contains the number of the block that is the immediate dominator
  110.    of basic block N. */
  111.  
  112. static bb_index *dom;
  113.  
  114.  
  115. /* Entry N is bit vector where bit M is 1 if block M is predecessor
  116.    of block N in control flow graph */
  117.  
  118. static regset *pred;
  119.  
  120.  
  121. /* Find the loops in the function that begins with INSNS.  Record the
  122.    entry, exit, and backedge arcs in INSN_INFO. */
  123.  
  124. void
  125. analyze_loops (insns)
  126.      rtx insns;
  127. {
  128.   loop_no = 0;
  129.   find_dominators ();
  130.   find_loops ();
  131.   free (dom);
  132.   free (pred);
  133. }
  134.  
  135.  
  136. /* Below is a direct implementation of the fast dominator algorithm
  137.    from: T. Lengauer and R. E. Tarjan, "A Fast Algorithm for Finding
  138.    Dominators in a Flowgraph," TOPLAS, v. 1, n. 1, July 1979, pp 121-141.
  139.    See this paper for detailed comments. */
  140.  
  141.  
  142. /* Return non-zero if block X dominates block Y and 0 otherwise. */
  143.  
  144. static int
  145. dominate_p (x, y)
  146.      register int x, y;
  147. {
  148.   if (x == y)
  149.     return 1;
  150.   else if (dom [y] == 0)
  151.     return 0;
  152.   else if (dom [y] == x)
  153.     return 1;
  154.   else
  155.     return dominate_p (x, dom [y]);
  156. }
  157.  
  158.  
  159. /* Entry N is parent of block N in depth-first spanning tree. */
  160.  
  161. static bb_index *parent;
  162.  
  163.  
  164. /* Entry N is number of semidominator of block N */
  165.  
  166. static bb_index *semi;
  167.  
  168.  
  169. /* Entry N is bit vector of blocks whose semidominator is N */
  170.  
  171. static regset *bucket;
  172.  
  173.  
  174. /* Entry N is the number of the block whose DF number is N. */
  175.  
  176. static bb_index *vertex;
  177.  
  178.  
  179. /* Used in LINK/EVAL data structure */
  180. static bb_index *ancestor;
  181. static bb_index *label;
  182. static bb_index *size;
  183. static bb_index *child;
  184.  
  185.  
  186. static bb_index n;
  187.  
  188. /* Find the dominators in the control graph using the Lengauer/Tarjan
  189.    algorithm.  Leave each element of the array DOM with the immediate
  190.    dominator of each block and each element of the array PRED with a bit
  191.    vector of the control-flow predecessors of a block. */
  192.  
  193. static void
  194. find_dominators ()
  195. {
  196.   register regset tem;
  197.   register int n_blocks = n_basic_blocks + 1; /* Number blocks from 1 */
  198.   int bbset_size = (n_blocks + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS;
  199.   int bbset_bytes = bbset_size * sizeof (int);
  200.   register int i, v;
  201.  
  202.   if (n_basic_blocks > (1 << (sizeof (bb_index) * 8)))
  203.     error ("Too many basic blocks for find_dominator");
  204.  
  205.   /* This algorithm wants to see block numbers from 1..n, so that it can
  206.      use array element 0 for its purposes.  */
  207.   dom = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  208.   bzero (dom, n_blocks * sizeof (bb_index));
  209.  
  210.   pred = (regset *) malloc (n_basic_blocks * sizeof (regset));
  211.   tem = (regset) malloc (n_basic_blocks * bbset_bytes);
  212.   bzero (tem, n_basic_blocks * bbset_bytes);
  213.   init_regset_vector (pred, tem, n_basic_blocks, bbset_bytes);
  214.  
  215.   parent = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  216.   bzero (parent, n_blocks * sizeof (bb_index));
  217.  
  218.   semi = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  219.   bzero (semi, n_blocks * sizeof (bb_index));
  220.  
  221.   bucket = (regset *) malloc (n_blocks * sizeof (regset));
  222.   tem = (regset) malloc (n_blocks * bbset_bytes);
  223.   bzero (tem, n_blocks * bbset_bytes);
  224.   init_regset_vector (bucket, tem, n_blocks, bbset_bytes);
  225.  
  226.   vertex = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  227.   bzero (vertex, n_blocks * sizeof (bb_index));
  228.  
  229.   ancestor = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  230.   bzero (ancestor, n_blocks * sizeof (bb_index));
  231.  
  232.   label = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  233.   for (i = 0; i < n_blocks; i ++) label [i] = i;
  234.  
  235.   size = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  236.   for (i = 0; i < n_blocks; i ++) size [i] = 1;
  237.  
  238.   size [0] = label [0] = semi [0] = 0;
  239.  
  240.   child = (bb_index *) malloc (n_blocks * sizeof (bb_index));
  241.   bzero (child, n_blocks * sizeof (bb_index));
  242.  
  243.   if (n_basic_blocks == 0) return;
  244.  
  245.   /* Step 1 */
  246.   n = 0;
  247.   dfs_number (0);
  248.  
  249.   for (i = n_blocks - 1; i != 1; i --)
  250.     {
  251.       register w = vertex [i];
  252.  
  253.       /* Step 2 */
  254.       for (v = 1; v < n_blocks; v ++)
  255.     {
  256.       if (w > 0 && GET_BBSET_BIT (pred [w - 1], v - 1))
  257.         {
  258.           register int u = eval_semid (v);
  259.  
  260.           if (semi [u] < semi [w])
  261.         semi [w] = semi [u];
  262.         }
  263.     }
  264.       SET_BBSET_BIT (bucket [vertex [semi [w]]], w);
  265.       link_semid (parent [w], w);
  266.  
  267.       /* Step 3 */
  268.       for (v = 1; v < n_blocks; v ++)
  269.     {
  270.       int pw = parent [w];
  271.  
  272.       if (GET_BBSET_BIT (bucket [pw], v))
  273.         {
  274.           int u;
  275.  
  276.           bucket [pw] [v / REGSET_ELT_BITS]
  277.         &= ~(1 << (v % REGSET_ELT_BITS));
  278.           u = eval_semid (v);
  279.           if (semi [u] < semi[v])
  280.         dom [v] = u;
  281.           else
  282.         dom [v] = pw;
  283.         }
  284.     }
  285.     }
  286.  
  287.   /* Step 4 */
  288.   for (i = 2; i < n_blocks; i ++)
  289.     {
  290.       register int w = vertex [i];
  291.  
  292.       if (dom [w] != vertex [semi [w]])
  293.     dom [w] = dom [dom [w]];
  294.     }
  295.  
  296.   /* Convert back to real block numbers */
  297.   for (i = 0; i < n_basic_blocks; i ++)
  298.     if (dom [i + 1] == 0)
  299.       dom [i] = dom [i + 1];
  300.     else
  301.       dom [i] = dom [i + 1] - 1;
  302.   dom [0] = 0;
  303.  
  304.   free (parent);
  305.   free (semi);
  306.   free (bucket);
  307.   free (ancestor);
  308.   free (label);
  309.   free (size);
  310.   free (child);
  311. }
  312.  
  313.  
  314. /* Assign depth-first numbers to blocks and set up some data structures. */
  315.  
  316. static void
  317. dfs_number (v_r)
  318.      register int v_r;        /* Real block number */
  319. {
  320.   register rtx x = basic_block_end [v_r];
  321.  
  322.   semi [v_r + 1] = (n += 1);
  323.   vertex [n] = v_r + 1;
  324.   if (GET_CODE (x) == JUMP_INSN && simplejump_p (x))
  325.     dfs_number_sub (v_r, head_to_block_number (jump_target (x)));
  326.   else if (GET_CODE (x) == JUMP_INSN && condjump_p (x))
  327.     {
  328.       dfs_number_sub (v_r, head_to_block_number (jump_target (x)));
  329.       dfs_number_sub (v_r, v_r + 1);
  330.     }
  331.   else if (multiway_jump_p (x))
  332.     {
  333.       rtx body =  PATTERN (x);
  334.       register int vlen, i;
  335.  
  336.       vlen = XVECLEN (body, 0);
  337.       for (i = 0; i < vlen; i++)
  338.     dfs_number_sub (v_r,
  339.             head_to_block_number (XEXP (XVECEXP (body, 0, i), 0)));
  340.     }
  341.   else
  342.     dfs_number_sub (v_r, v_r + 1);
  343. }
  344.  
  345.  
  346. static void
  347. dfs_number_sub (v_r, w_r)
  348.      register int v_r, w_r;        /* Real block numbers */
  349. {
  350.   if (w_r == n_basic_blocks) return;
  351.   if (semi [w_r + 1] == 0)
  352.     {
  353.       parent [w_r + 1] = v_r + 1;
  354.       dfs_number (w_r);
  355.     }
  356.   SET_BBSET_BIT (pred [w_r], v_r);
  357. }
  358.  
  359.  
  360. /* The "fast" link/eval routines from the paper. */
  361.  
  362. static int
  363. eval_semid (v)
  364.      register int v;
  365. {
  366.   if (ancestor [v] == 0)
  367.     return v;
  368.   else
  369.     {
  370.       compress_semid (v);
  371.       return label[v];
  372.     }
  373. #ifdef FAST
  374.   if (ancestor [v] == 0)
  375.     return label [v];
  376.   else
  377.     {
  378.       compress_semid (v);
  379.       if (semi [label [ancestor [v]]] > semi [label [v]])
  380.     return label [v];
  381.       else
  382.     return label [ancestor [v]];
  383.     }
  384. #endif
  385. }
  386.  
  387.  
  388. static void
  389. compress_semid (v)
  390.      register int v;
  391. {
  392.   if (ancestor [ancestor [v]] != 0)
  393.     {
  394.       compress_semid (ancestor [v]);
  395.       if (semi [label [ancestor [v]]] < semi [label [v]])
  396.     label [v] = label [ancestor [v]];
  397.       ancestor [v] = ancestor [ancestor [v]];
  398.     }
  399. }
  400.  
  401.  
  402. static void
  403. link_semid (v, w)
  404.      register int v, w;
  405. {
  406.   register int s = w;
  407.  
  408.   ancestor [w] = v;
  409.  
  410. #ifdef FAST
  411.   while (semi [label [w]] < semi [label [child [s]]])
  412.     {
  413.       if (size [s] + size [child [child [s]]] > 2 * size [child [s]])
  414.     {
  415.       parent [child [s]] = s;
  416.       child [s] = child [child [s]];
  417.     }
  418.       else
  419.     {
  420.       size [child [s]] = size [s];
  421.       s = parent [s] = child [s];
  422.     }
  423.     }
  424.  
  425.   label [s] = label [w];
  426.   size [v] = size [v] + size [w];
  427.   if (size [v] < 2 * size [w])
  428.     {
  429.       int t = s;
  430.       s = child [v];
  431.      child [v] = t;
  432.     }
  433.   while (s != 0)
  434.     {
  435.       parent [s] = v;
  436.       s = child [s];
  437.     }
  438. #endif
  439. }
  440.  
  441.  
  442. /* Find all loops in the function and record which edges in the
  443.    control flow graph enter, exit, and iterate them. */
  444.  
  445. static void
  446.   find_loops ()
  447. {
  448.   register int i, h;
  449.   bb_index *stack;
  450.  
  451.   stack = (bb_index *) malloc (n_basic_blocks * sizeof (bb_index));
  452.   for (i = 0; i < n_basic_blocks; i ++)
  453.     {
  454.       if ((h = find_loop_back_edge (i)) != -1)
  455.     /* Check if we've already found another backedge of this loop */
  456.     if (!insn_marked_p (basic_block_head[h], LOOP_HEAD_FLAG))
  457.       {
  458.         mark_insn (basic_block_head [h], LOOP_HEAD_FLAG);
  459.         find_natural_loop (stack, i, h);
  460.       }
  461.     }
  462.   free (stack);
  463. }
  464.  
  465.  
  466. /* Return the number of block that is the target of a loop back edge
  467.    from block I (i.e., the number of the loop header's block). If none
  468.    exists, return -1; */
  469.  
  470. static int
  471. find_loop_back_edge (i)
  472.      register int i;
  473. {
  474.   register rtx x = basic_block_end [i];
  475.   register int t;
  476.  
  477.   if (GET_CODE (x) == JUMP_INSN && simplejump_p (x))
  478.     t = head_to_block_number (jump_target (x));
  479.   else if (GET_CODE (x) == JUMP_INSN && condjump_p (x))
  480.     {
  481.       t = head_to_block_number (jump_target (x));
  482.       if (dominate_p (t, i))
  483.     return t;
  484.       t = i + 1;        /* Check fall-thru */
  485.     }
  486.   else if (multiway_jump_p (x))
  487.     {
  488.       rtx body =  PATTERN (x);
  489.       register int vlen, j;
  490.  
  491.       vlen = XVECLEN (body, 0);
  492.       for (j = 0; j < vlen; j ++)
  493.     {
  494.       t = head_to_block_number (XEXP (XVECEXP (body, 0, j), 0));
  495.       if (dominate_p (t, i))
  496.         return t;
  497.     }
  498.       return -1;
  499.     }
  500.   else
  501.     t = i + 1;            /* Check fall-thru */
  502.  
  503.   /* Fall-thru check */
  504.   if (t < n_basic_blocks && dominate_p (t, i))
  505.     return t;
  506.   else
  507.     return -1;
  508. }
  509.  
  510.  
  511. /* Find the natural loop in the control flow graph (see, Aho, Sethi,
  512.    Ullman, p 604) corresponding to the backedge from block N to H.  For
  513.    each loop, record relevant edges. */
  514.  
  515. static void
  516. find_natural_loop (stack, n, h)
  517. bb_index *stack;
  518. register int n, h;
  519. {
  520.   register int stack_top = 0;
  521.   static int mark = 0;
  522.   register int i;
  523.  
  524.   /* Record loop backedge */
  525.   insn_info [INSN_UID (basic_block_end [n])].back_edge
  526.     = cons (cons (h, loop_no), insn_info [n]. back_edge);
  527.  
  528.   mark ++;
  529.   insn_info [INSN_UID (basic_block_head [h])].mark = mark;
  530.   insn_info [INSN_UID (basic_block_head [n])].mark = mark;
  531.   if (h != n)
  532.     stack [stack_top ++] = n;
  533.  
  534.   while (stack_top != 0)
  535.     {
  536.       int m = stack [-- stack_top];
  537.  
  538.       FOREACH_SET_BIT (pred [m], n_basic_blocks, i,
  539.                {
  540.              if (insn_info [INSN_UID (basic_block_head [i])].mark
  541.                  != mark)
  542.                {
  543.                  insn_info [INSN_UID (basic_block_head [i])].mark
  544.                    = mark;
  545.                  stack [stack_top ++] = i;
  546.                }});
  547.  
  548.       /* Record loop backedge */
  549.       if (block_succ_p (m, h))
  550.     insn_info [INSN_UID (basic_block_end [m])].back_edge
  551.       = cons (cons (h, loop_no), insn_info [m]. back_edge);
  552.     }
  553.  
  554.   for (i = 0; i < n_basic_blocks; i ++)
  555.     {
  556.       /* Find edges entering the loop (at its head) */
  557.       if (GET_BBSET_BIT (pred [h], i)
  558.       && insn_info [INSN_UID (basic_block_head [i])].mark != mark)
  559.     insn_info [INSN_UID (basic_block_end [i])].entry_edge
  560.       = cons (cons (h, loop_no),
  561.           insn_info [INSN_UID (basic_block_end [i])].entry_edge);
  562.  
  563.       /* Find edges exiting the loop (from any block in the loop) */
  564.       if (insn_info [INSN_UID (basic_block_head [i])].mark == mark)
  565.     {
  566.       register rtx x = basic_block_end [i];
  567.  
  568.       if (GET_CODE (x) == JUMP_INSN && simplejump_p (x))
  569.         record_exit_edge (x, jump_target (x), loop_no, mark);
  570.       else if (GET_CODE (x) == JUMP_INSN && condjump_p (x))
  571.         {
  572.           record_exit_edge (x, jump_target (x), loop_no, mark);
  573.           record_exit_edge1 (x, i + 1, loop_no, mark);
  574.         }
  575.       else if (multiway_jump_p (x))
  576.         {
  577.           rtx body =  PATTERN (x);
  578.           register int vlen, i;
  579.  
  580.           vlen = XVECLEN (body, 0);
  581.           for (i = 0; i < vlen; i++)
  582.         record_exit_edge (x, XEXP (XVECEXP (body, 0, i), 0), loop_no,
  583.                   mark);
  584.         }
  585.       else
  586.         record_exit_edge1 (x, i + 1, loop_no, mark);
  587.     }
  588.     }
  589.  
  590.   loop_no += 1;
  591. }
  592.  
  593. /* Return non-zero if block N is a successor of block M.  Return 0
  594.    otherwise. */
  595.  
  596. static int
  597. block_succ_p (m, n)
  598.      register int m, n;
  599. {
  600.   register rtx x = basic_block_end [m];
  601.   register rtx y = basic_block_head [n];
  602.  
  603.   if (GET_CODE (x) == JUMP_INSN && simplejump_p (x))
  604.     return (y == jump_target (x));
  605.   else if (GET_CODE (x) == JUMP_INSN && condjump_p (x))
  606.     {
  607.       if (y == jump_target (x)) return 1;
  608.       return m + 1 == n;    /* Fall-thru? */
  609.     }
  610.   else if (multiway_jump_p (x))
  611.     {
  612.       rtx body =  PATTERN (x);
  613.       register int vlen, i;
  614.  
  615.       vlen = XVECLEN (body, 0);
  616.       for (i = 0; i < vlen; i++)
  617.     if (y == (XEXP (XVECEXP (body, 0, i), 0)))
  618.       return 1;
  619.  
  620.       return 0;
  621.     }
  622.   else
  623.     return m + 1 == n;
  624. }
  625.  
  626.  
  627. /* Record that edge from block X to block Y is an exit edge of loop LOOP_NO,
  628.    assumming that Y is not marked with MARK. */
  629.  
  630. static void
  631. record_exit_edge (x, y, loop_no, mark)
  632.      rtx x, y;
  633.      int loop_no;
  634.      int mark;
  635. {
  636.   if (y != NULL && insn_info [INSN_UID (y)].mark != mark)
  637.     /* Target of edge is not in loop */
  638.     insn_info [INSN_UID (x)].exit_edge
  639.       = cons (cons (head_to_block_number (y), loop_no),
  640.           insn_info [INSN_UID (x)].exit_edge);
  641. }
  642.  
  643.  
  644. /* Record the same information, except that block Y is now the block
  645.    with BLOCK_NO. */
  646.  
  647. static void
  648. record_exit_edge1 (x, block_no, loop_no, mark)
  649.      rtx x;
  650.      int block_no;
  651.      int loop_no;
  652.      int mark;
  653. {
  654.   if (block_no == n_basic_blocks /* Implicit last block */
  655.       || insn_info [INSN_UID (basic_block_head [block_no])].mark != mark)
  656.     /* Target of edge is not in loop */
  657.     insn_info [INSN_UID (x)].exit_edge
  658.       = cons (cons (block_no, loop_no),
  659.           insn_info [INSN_UID (x)].exit_edge);
  660. }
  661.