OSDN Git Service

2005-07-25 Andrew Pinski <pinskia@physics.uc.edu>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-reassoc.c
1 /* Reassociation for trees.
2    Copyright (C) 2005 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin <dan@dberlin.org>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "errors.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-dump.h"
35 #include "timevar.h"
36 #include "hashtab.h"
37 #include "tree-iterator.h"
38 #include "tree-pass.h"
39
40 /*  This is a simple global reassociation pass that uses a combination
41     of heuristics and a hashtable to try to expose more operations to
42     CSE.  
43
44     The basic idea behind the heuristic is to rank expressions by
45     depth of the computation tree and loop depth, and try to produce
46     expressions consisting of small rank operations, as they are more
47     likely to reoccur.  In addition, we use a hashtable to try to see
48     if we can transpose an operation into something we have seen
49     before.
50
51     Note that the way the hashtable is structured will sometimes find
52     matches that will not expose additional redundancies, since it is
53     not unwound as we traverse back up one branch of the dominator
54     tree and down another.  However, the cost of improving this is
55     probably not worth the additional benefits it will bring.  */
56
57 /* Statistics */
58 static struct
59 {
60   int reassociated_by_rank;
61   int reassociated_by_match;
62 } reassociate_stats;
63
64
65
66 /* Seen binary operator hashtable.  */
67 static htab_t seen_binops;
68
69 /* Binary operator struct. */
70
71 typedef struct seen_binop_d
72 {
73   tree op1;
74   tree op2;
75 } *seen_binop_t;
76
77 /* Return a SEEN_BINOP_T if we have seen an associative binary
78    operator with OP1 and OP2 in it.  */
79
80 static seen_binop_t
81 find_seen_binop (tree op1, tree op2)
82 {
83   void **slot;
84   struct seen_binop_d sbd;
85   sbd.op1 = op1;
86   sbd.op2 = op2;
87   slot = htab_find_slot (seen_binops, &sbd, NO_INSERT);
88   if (!slot)
89     return NULL;
90   return ((seen_binop_t) *slot);
91 }
92
93 /* Insert a binary operator consisting of OP1 and OP2 into the
94    SEEN_BINOP table.  */
95
96 static void
97 insert_seen_binop (tree op1, tree op2)
98 {
99   void **slot;
100   seen_binop_t new_pair = xmalloc (sizeof (*new_pair));
101   new_pair->op1 = op1;
102   new_pair->op2 = op2;
103   slot = htab_find_slot (seen_binops, new_pair, INSERT);
104   if (*slot != NULL)
105     free (*slot);
106   *slot = new_pair;
107 }
108
109 /* Return the hash value for a seen binop structure pointed to by P.
110    Because all the binops we consider are associative, we just add the
111    hash value for op1 and op2.  */
112
113 static hashval_t
114 seen_binop_hash (const void *p)
115 {
116   const seen_binop_t sb = (seen_binop_t) p;
117   return iterative_hash_expr (sb->op1, 0) + iterative_hash_expr (sb->op2, 0);
118 }
119
120 /* Return true if two seen binop structures pointed to by P1 and P2 are equal.
121    We have to check the operators both ways because we don't know what
122    order they appear in the table.  */
123
124 static int
125 seen_binop_eq (const void *p1, const void *p2)
126 {
127   const seen_binop_t sb1 = (seen_binop_t) p1;
128   const seen_binop_t sb2 = (seen_binop_t) p2;
129   return (sb1->op1 == sb2->op1 && sb1->op2 == sb2->op2)
130     || (sb1->op2 == sb2->op1 && sb1->op1 == sb2->op2);
131 }
132
133 /* Value rank structure.  */
134
135 typedef struct valrank_d
136 {
137   tree e;   
138   unsigned int rank;  
139 } *valrank_t;
140
141 /* Starting rank number for a given basic block, so that we can rank
142    operations using unmovable instructions in that BB based on the bb
143    depth.  */
144 static unsigned int *bb_rank;
145
146 /* Value rank hashtable.  */
147 static htab_t value_rank;
148
149
150 /* Look up the value rank structure for expression E.  */
151
152 static valrank_t
153 find_value_rank (tree e)
154 {
155   void **slot;
156   struct valrank_d vrd;
157   vrd.e = e;
158   slot = htab_find_slot (value_rank, &vrd, NO_INSERT);
159   if (!slot)
160     return NULL;
161   return ((valrank_t) *slot);
162 }
163
164 /* Insert {E,RANK} into the value rank hashtable.  */
165
166 static void
167 insert_value_rank (tree e, unsigned int rank)
168 {
169   void **slot;
170   valrank_t new_pair = xmalloc (sizeof (*new_pair));
171   new_pair->e = e;
172   new_pair->rank = rank;
173   slot = htab_find_slot (value_rank, new_pair, INSERT);
174   gcc_assert (*slot == NULL);
175   *slot = new_pair;
176
177 }
178
179
180 /* Return the hash value for a value rank structure  */
181
182 static hashval_t
183 valrank_hash (const void *p)
184 {
185   const valrank_t vr = (valrank_t) p;
186   return iterative_hash_expr (vr->e, 0);
187 }
188
189 /* Return true if two value rank structures are equal.  */
190
191 static int
192 valrank_eq (const void *p1, const void *p2)
193 {
194   const valrank_t vr1 = (valrank_t) p1;
195   const valrank_t vr2 = (valrank_t) p2;
196   return vr1->e == vr2->e;
197 }
198
199
200 /* Initialize the reassociation pass.  */
201
202 static void
203 init_reassoc (void)
204 {
205   int i;
206   unsigned int rank = 2;
207   
208   tree param;
209   int *bbs = xmalloc ((last_basic_block + 1) * sizeof (int));
210   
211   memset (&reassociate_stats, 0, sizeof (reassociate_stats));
212
213   /* Reverse RPO (Reverse Post Order) will give us something where
214      deeper loops come later.  */
215   flow_reverse_top_sort_order_compute (bbs);
216   bb_rank = xcalloc (last_basic_block + 1, sizeof (unsigned int));
217   value_rank = htab_create (511, valrank_hash,
218                             valrank_eq, free);
219   seen_binops = htab_create (511, seen_binop_hash,
220                              seen_binop_eq, free);
221
222   /* Give each argument a distinct rank.   */
223   for (param = DECL_ARGUMENTS (current_function_decl);
224        param;
225        param = TREE_CHAIN (param))
226     {
227       if (default_def (param) != NULL)
228         {
229           tree def = default_def (param);
230           insert_value_rank (def, ++rank);
231         }
232     }
233   /* Give the chain decl a distinct rank. */
234   if (cfun->static_chain_decl != NULL)
235     {
236       tree def = default_def (cfun->static_chain_decl);
237       if (def != NULL)
238         insert_value_rank (def, ++rank);
239     }
240   
241   /* Set up rank for each BB  */
242   for (i = 0; i < n_basic_blocks; i++)
243     bb_rank[bbs[i]] = ++rank  << 16;
244
245   free (bbs);
246   calculate_dominance_info (CDI_DOMINATORS);
247
248 }
249
250 /* Cleanup after the reassociation pass, and print stats if
251    requested.  */
252
253 static void
254 fini_reassoc (void)
255 {
256
257   if (dump_file && (dump_flags & TDF_STATS))
258     {
259       fprintf (dump_file, "Reassociation stats:\n");
260       fprintf (dump_file, "Reassociated by rank: %d\n", reassociate_stats.reassociated_by_rank);
261       fprintf (dump_file, "Reassociated by match: %d\n", reassociate_stats.reassociated_by_match);
262     }
263   htab_delete (value_rank);
264   htab_delete (seen_binops);
265   free (bb_rank);
266 }
267
268 /* Given an expression E, return the rank of the expression.  */
269
270 static unsigned int
271 get_rank (tree e)
272 {
273   valrank_t vr;
274
275   /* Constants have rank 0.  */  
276   if (is_gimple_min_invariant (e))
277     return 0;
278   
279   /* SSA_NAME's have the rank of the expression they are the result
280      of.
281      For globals and uninitialized values, the rank is 0.
282      For function arguments, use the pre-setup rank.
283      For PHI nodes, stores, asm statements, etc, we use the rank of
284      the BB.
285      For simple operations, the rank is the maximum rank of any of
286      its operands, or the bb_rank, whichever is less.
287      I make no claims that this is optimal, however, it gives good
288      results.  */
289
290   if (TREE_CODE (e) == SSA_NAME)
291     {
292       tree stmt;
293       tree rhs;      
294       unsigned int rank, maxrank;
295       int i;
296       
297       if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
298           && e == default_def (SSA_NAME_VAR (e)))
299         return find_value_rank (e)->rank;
300       
301       stmt = SSA_NAME_DEF_STMT (e);
302       if (bb_for_stmt (stmt) == NULL)
303         return 0;
304       
305       if (TREE_CODE (stmt) != MODIFY_EXPR
306           || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
307         return bb_rank[bb_for_stmt (stmt)->index];
308
309       /* If we already have a rank for this expression, use that.  */
310       vr = find_value_rank (e);
311       if (vr)
312         return vr->rank;
313
314       /* Otherwise, find the maximum rank for the operands, or the bb
315          rank, whichever is less.   */
316       rank = 0;
317       maxrank = bb_rank[bb_for_stmt(stmt)->index];
318       rhs = TREE_OPERAND (stmt, 1);
319       if (TREE_CODE_LENGTH (TREE_CODE (rhs)) == 0)
320         rank = MAX (rank, get_rank (rhs));
321       else 
322         {
323           for (i = 0; 
324                i < TREE_CODE_LENGTH (TREE_CODE (rhs)) 
325                  && TREE_OPERAND (rhs, i)
326                  && rank != maxrank; i++)
327             rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
328         }
329       
330       if (dump_file && (dump_flags & TDF_DETAILS))
331         {
332           fprintf (dump_file, "Rank for ");
333           print_generic_expr (dump_file, e, 0);
334           fprintf (dump_file, " is %d\n", (rank + 1));
335         }
336       
337       /* Note the rank in the hashtable so we don't recompute it.  */
338       insert_value_rank (e, (rank + 1));
339       return (rank + 1);
340     }
341
342   /* Globals, etc,  are rank 0 */
343   return 0;
344 }
345
346
347 /* Decide whether we should transpose RHS and some operand of
348    LHSDEFOP.
349    If yes, then return true and set TAKEOP to the operand number of LHSDEFOP to
350    switch RHS for.
351    Otherwise, return false.  */
352
353 static bool
354 should_transpose (tree rhs ATTRIBUTE_UNUSED, 
355                   unsigned int rhsrank,
356                   tree lhsdefop, unsigned int *takeop)
357 {
358   /* Attempt to expose the low ranked
359      arguments to CSE if we have something like:
360      a = <rank 2> + c (rank 1)
361      b = a (rank 3) + d (rank 1)
362      We want to transform this into:
363      a = c + d
364      b = <rank 2> + <rank 3>
365      
366      The op finding part wouldn't be necessary if
367                          we could swap the operands above and not have
368                          update_stmt change them back on us.
369   */
370   unsigned int lowrankop;
371   unsigned int lowrank;
372   unsigned int highrank;
373   unsigned int highrankop;
374   unsigned int temp;
375   
376   lowrankop = 0;
377   *takeop = 1;
378   lowrank = get_rank (TREE_OPERAND (lhsdefop, 0));
379   temp = get_rank (TREE_OPERAND (lhsdefop, 1));
380   highrank = temp;
381   highrankop = 1;
382   if (temp < lowrank)
383     {
384       lowrankop = 1;
385       highrankop = 0;
386       *takeop = 0;
387       highrank = lowrank;
388       lowrank = temp;
389     }
390   
391   /* If highrank == lowrank, then we had something
392      like:
393      a = <rank 1> + <rank 1> 
394      already, so there is no guarantee that
395      swapping our argument in is going to be
396      better.
397      If we run reassoc twice, we could probably
398      have a flag that switches this behavior on,
399      so that we try once without it, and once with
400      it, so that redundancy elimination sees it
401      both ways.
402   */                  
403   
404   if (lowrank == rhsrank && highrank != lowrank)
405     return true;
406
407   /* Also, see if the LHS's high ranked op should be switched with our
408      RHS simply because it is greater in rank than our current RHS.  */
409   if (TREE_CODE (TREE_OPERAND (lhsdefop, highrankop)) == SSA_NAME)
410     {
411       tree iop = SSA_NAME_DEF_STMT (TREE_OPERAND (lhsdefop, highrankop));
412       if (TREE_CODE (iop) == MODIFY_EXPR)
413         iop = TREE_OPERAND (iop, 1);
414       if (TREE_CODE (iop) == TREE_CODE (lhsdefop))
415         *takeop = 1;
416       if (rhsrank < get_rank (TREE_OPERAND (lhsdefop, *takeop)))
417         return true;
418     }             
419   
420   return false;
421 }
422
423 /* Attempt to reassociate the associative binary operator BEXPR, which
424    is in the statement pointed to by CURRBSI.  Return true if we
425    changed the statement.  */
426
427 static bool
428 reassociate_expr (tree bexpr, block_stmt_iterator *currbsi)
429 {
430   tree lhs = TREE_OPERAND (bexpr, 0);
431   tree rhs = TREE_OPERAND (bexpr, 1);
432   tree lhsdef;
433   tree lhsi;
434   bool changed = false;
435   unsigned int lhsrank = get_rank (lhs);
436   unsigned int rhsrank = get_rank (rhs);
437
438   /* If unsafe math optimizations we can do reassociation for non integal
439      types.  */
440   if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
441        || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
442       && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
443           || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
444           || !flag_unsafe_math_optimizations))
445     return false;
446     
447   /* We want the greater ranked operand to be our "LHS" for simplicity
448      sake.  There is no point in actually modifying the expression, as
449      update_stmt will simply resort the operands anyway. */
450   if (lhsrank < rhsrank)
451     {
452       tree temp;
453       unsigned int temp1;
454       temp = lhs;
455       lhs = rhs;
456       rhs = temp;
457       temp1 = lhsrank;
458       lhsrank = rhsrank;
459       rhsrank = temp1;
460     }
461
462   /* If the high ranked operand is an SSA_NAME, and the binary
463      operator is not something we've already seen somewhere else
464      (i.e., it may be redundant), attempt to reassociate it.
465      
466      We can't reassociate expressions unless the expression we are
467      going to reassociate with is only used in our current expression,
468      or else we may screw up other computations, like so:
469
470      a = b + c
471      e = a + d
472      
473      g = a + f
474      
475      We cannot reassociate and rewrite the "a = ..." , 
476      because that would change the value of the computation of 
477      "g = a + f".  */
478   if (TREE_CODE (lhs) == SSA_NAME && !find_seen_binop (lhs, rhs))
479     {
480       lhsdef = SSA_NAME_DEF_STMT (lhs);
481       if (TREE_CODE (lhsdef) == MODIFY_EXPR)
482         {
483           lhsi = TREE_OPERAND (lhsdef, 1);
484           if (TREE_CODE (lhsi) == TREE_CODE (bexpr))
485             {
486               use_operand_p use;
487               tree usestmt;
488               if (single_imm_use (lhs, &use, &usestmt))
489                 {
490                   unsigned int takeop = 0;
491                   unsigned int otherop = 1;
492                   bool foundmatch = false;
493                   bool foundrank = false;
494
495                   /* If we can easily transpose this into an operation
496                      we've already seen, let's do that.
497                      otherwise, let's try to expose low ranked ops to
498                      CSE.  */
499                   if (find_seen_binop (TREE_OPERAND (lhsi, 1), rhs))
500                     {
501                       takeop = 0;
502                       otherop = 1;
503                       foundmatch = true;
504                     }
505                   else if (find_seen_binop (TREE_OPERAND (lhsi, 0),
506                                             rhs))
507                     {
508                       takeop = 1;
509                       otherop = 0;
510                       foundmatch = true;
511                     }
512                   else if (should_transpose (rhs, rhsrank, lhsi,
513                                              &takeop))
514                     {
515                       foundrank = true;
516                     }             
517                   if (foundmatch || foundrank)
518                     {
519                       block_stmt_iterator lhsbsi = bsi_for_stmt (lhsdef);
520                       if (dump_file && (dump_flags & TDF_DETAILS))
521                         {
522                           fprintf (dump_file, "Reassociating by %s\n",
523                                    foundmatch ? "match" : "rank");
524                           fprintf (dump_file, "Before LHS:");
525                           print_generic_stmt (dump_file, lhsi, 0);
526                           fprintf (dump_file, "Before curr expr:");
527                           print_generic_stmt (dump_file, bexpr, 0);
528                         }
529                       TREE_OPERAND (bexpr, 0) = TREE_OPERAND (lhsi, takeop);
530                       TREE_OPERAND (lhsi, takeop) = rhs;
531                       TREE_OPERAND (bexpr, 1) = TREE_OPERAND (lhsdef, 0);
532                       if (dump_file && (dump_flags & TDF_DETAILS))
533                         {
534                           fprintf (dump_file, "After LHS:");
535                           print_generic_stmt (dump_file, lhsi, 0);
536                           fprintf (dump_file, "After curr expr:");
537                           print_generic_stmt (dump_file, bexpr, 0);
538                         }
539                       bsi_move_before (&lhsbsi, currbsi);
540                       update_stmt (lhsdef);
541                       update_stmt (bsi_stmt (*currbsi));
542                       lhsbsi = bsi_for_stmt (lhsdef);
543                       update_stmt (bsi_stmt (lhsbsi));
544
545                       /* If update_stmt didn't reorder our operands,
546                          we'd like to recurse on the expression we
547                          just reassociated and reassociate it
548                          top-down, exposing further opportunities.
549                          Unfortunately, update_stmt does reorder them,
550                          so we can't do this cheaply.  */
551                       if (!foundmatch)
552                         reassociate_stats.reassociated_by_rank++;
553                       else
554                         reassociate_stats.reassociated_by_match++;
555                       return true;
556                     }
557                 }
558             }
559         }
560     }
561   return changed;
562 }
563
564 /* Reassociate expressions in basic block BB and its dominator as
565    children , return true if any
566    expressions changed.  */
567
568 static bool
569 reassociate_bb (basic_block bb)
570 {
571   bool changed = false;
572   block_stmt_iterator bsi;
573   basic_block son;
574
575   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
576     {
577       tree stmt = bsi_stmt (bsi);
578       
579       if (TREE_CODE (stmt) == MODIFY_EXPR)
580         {
581           tree rhs = TREE_OPERAND (stmt, 1);
582           if (associative_tree_code (TREE_CODE (rhs)))
583             {
584               if (reassociate_expr (rhs, &bsi))
585                 {
586                   changed = true;
587                   update_stmt (stmt);             
588                 }
589               insert_seen_binop (TREE_OPERAND (rhs, 0),
590                                  TREE_OPERAND (rhs, 1));
591             }
592         }
593     }
594   for (son = first_dom_son (CDI_DOMINATORS, bb);
595        son;
596        son = next_dom_son (CDI_DOMINATORS, son))
597     {
598       changed |= reassociate_bb (son);
599     }
600   return changed;  
601 }
602
603         
604 static bool
605 do_reassoc (void)
606 {  
607   bool changed = false;
608   
609   changed = reassociate_bb (ENTRY_BLOCK_PTR);
610
611   return changed;  
612 }
613
614
615 /* Gate and execute functions for Reassociation.  */
616
617 static void
618 execute_reassoc (void)
619 {
620   init_reassoc ();
621   do_reassoc ();
622   fini_reassoc ();
623 }
624
625 struct tree_opt_pass pass_reassoc =
626 {
627   "reassoc",                            /* name */
628   NULL,                         /* gate */
629   execute_reassoc,                              /* execute */
630   NULL,                                 /* sub */
631   NULL,                                 /* next */
632   0,                                    /* static_pass_number */
633   TV_TREE_REASSOC,                              /* tv_id */
634   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
635   0,                                    /* properties_provided */
636   0,                                    /* properties_destroyed */
637   0,                                    /* todo_flags_start */
638   TODO_update_ssa | TODO_dump_func 
639   | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
640   0                                     /* letter */
641 };