OSDN Git Service

PR tree-optimization/22442
[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   /* I don't want to get into the business of floating point
439      reassociation.  */
440   if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
441       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
442     return false;
443     
444   /* We want the greater ranked operand to be our "LHS" for simplicity
445      sake.  There is no point in actually modifying the expression, as
446      update_stmt will simply resort the operands anyway. */
447   if (lhsrank < rhsrank)
448     {
449       tree temp;
450       unsigned int temp1;
451       temp = lhs;
452       lhs = rhs;
453       rhs = temp;
454       temp1 = lhsrank;
455       lhsrank = rhsrank;
456       rhsrank = temp1;
457     }
458
459   /* If the high ranked operand is an SSA_NAME, and the binary
460      operator is not something we've already seen somewhere else
461      (i.e., it may be redundant), attempt to reassociate it.
462      
463      We can't reassociate expressions unless the expression we are
464      going to reassociate with is only used in our current expression,
465      or else we may screw up other computations, like so:
466
467      a = b + c
468      e = a + d
469      
470      g = a + f
471      
472      We cannot reassociate and rewrite the "a = ..." , 
473      because that would change the value of the computation of 
474      "g = a + f".  */
475   if (TREE_CODE (lhs) == SSA_NAME && !find_seen_binop (lhs, rhs))
476     {
477       lhsdef = SSA_NAME_DEF_STMT (lhs);
478       if (TREE_CODE (lhsdef) == MODIFY_EXPR)
479         {
480           lhsi = TREE_OPERAND (lhsdef, 1);
481           if (TREE_CODE (lhsi) == TREE_CODE (bexpr))
482             {
483               use_operand_p use;
484               tree usestmt;
485               if (single_imm_use (lhs, &use, &usestmt))
486                 {
487                   unsigned int takeop = 0;
488                   unsigned int otherop = 1;
489                   bool foundmatch = false;
490                   bool foundrank = false;
491
492                   /* If we can easily transpose this into an operation
493                      we've already seen, let's do that.
494                      otherwise, let's try to expose low ranked ops to
495                      CSE.  */
496                   if (find_seen_binop (TREE_OPERAND (lhsi, 1), rhs))
497                     {
498                       takeop = 0;
499                       otherop = 1;
500                       foundmatch = true;
501                     }
502                   else if (find_seen_binop (TREE_OPERAND (lhsi, 0),
503                                             rhs))
504                     {
505                       takeop = 1;
506                       otherop = 0;
507                       foundmatch = true;
508                     }
509                   else if (should_transpose (rhs, rhsrank, lhsi,
510                                              &takeop))
511                     {
512                       foundrank = true;
513                     }             
514                   if (foundmatch || foundrank)
515                     {
516                       block_stmt_iterator lhsbsi = bsi_for_stmt (lhsdef);
517                       if (dump_file && (dump_flags & TDF_DETAILS))
518                         {
519                           fprintf (dump_file, "Reassociating by %s\n",
520                                    foundmatch ? "match" : "rank");
521                           fprintf (dump_file, "Before LHS:");
522                           print_generic_stmt (dump_file, lhsi, 0);
523                           fprintf (dump_file, "Before curr expr:");
524                           print_generic_stmt (dump_file, bexpr, 0);
525                         }
526                       TREE_OPERAND (bexpr, 0) = TREE_OPERAND (lhsi, takeop);
527                       TREE_OPERAND (lhsi, takeop) = rhs;
528                       TREE_OPERAND (bexpr, 1) = TREE_OPERAND (lhsdef, 0);
529                       if (dump_file && (dump_flags & TDF_DETAILS))
530                         {
531                           fprintf (dump_file, "After LHS:");
532                           print_generic_stmt (dump_file, lhsi, 0);
533                           fprintf (dump_file, "After curr expr:");
534                           print_generic_stmt (dump_file, bexpr, 0);
535                         }
536                       bsi_move_before (&lhsbsi, currbsi);
537                       update_stmt (lhsdef);
538                       update_stmt (bsi_stmt (*currbsi));
539                       lhsbsi = bsi_for_stmt (lhsdef);
540                       update_stmt (bsi_stmt (lhsbsi));
541
542                       /* If update_stmt didn't reorder our operands,
543                          we'd like to recurse on the expression we
544                          just reassociated and reassociate it
545                          top-down, exposing further opportunities.
546                          Unfortunately, update_stmt does reorder them,
547                          so we can't do this cheaply.  */
548                       if (!foundmatch)
549                         reassociate_stats.reassociated_by_rank++;
550                       else
551                         reassociate_stats.reassociated_by_match++;
552                       return true;
553                     }
554                 }
555             }
556         }
557     }
558   return changed;
559 }
560
561 /* Reassociate expressions in basic block BB and its dominator as
562    children , return true if any
563    expressions changed.  */
564
565 static bool
566 reassociate_bb (basic_block bb)
567 {
568   bool changed = false;
569   block_stmt_iterator bsi;
570   basic_block son;
571
572   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
573     {
574       tree stmt = bsi_stmt (bsi);
575       
576       if (TREE_CODE (stmt) == MODIFY_EXPR)
577         {
578           tree rhs = TREE_OPERAND (stmt, 1);
579           if (associative_tree_code (TREE_CODE (rhs)))
580             {
581               if (reassociate_expr (rhs, &bsi))
582                 {
583                   changed = true;
584                   update_stmt (stmt);             
585                 }
586               insert_seen_binop (TREE_OPERAND (rhs, 0),
587                                  TREE_OPERAND (rhs, 1));
588             }
589         }
590     }
591   for (son = first_dom_son (CDI_DOMINATORS, bb);
592        son;
593        son = next_dom_son (CDI_DOMINATORS, son))
594     {
595       changed |= reassociate_bb (son);
596     }
597   return changed;  
598 }
599
600         
601 static bool
602 do_reassoc (void)
603 {  
604   bool changed = false;
605   
606   changed = reassociate_bb (ENTRY_BLOCK_PTR);
607
608   return changed;  
609 }
610
611
612 /* Gate and execute functions for Reassociation.  */
613
614 static void
615 execute_reassoc (void)
616 {
617   init_reassoc ();
618   do_reassoc ();
619   fini_reassoc ();
620 }
621
622 struct tree_opt_pass pass_reassoc =
623 {
624   "reassoc",                            /* name */
625   NULL,                         /* gate */
626   execute_reassoc,                              /* execute */
627   NULL,                                 /* sub */
628   NULL,                                 /* next */
629   0,                                    /* static_pass_number */
630   TV_TREE_REASSOC,                              /* tv_id */
631   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
632   0,                                    /* properties_provided */
633   0,                                    /* properties_destroyed */
634   0,                                    /* todo_flags_start */
635   TODO_update_ssa | TODO_dump_func 
636   | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
637   0                                     /* letter */
638 };