OSDN Git Service

PR 23164
[pf3gnuchains/gcc-fork.git] / gcc / tree-cfgcleanup.c
1 /* CFG cleanup for trees.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "errors.h"
32 #include "flags.h"
33 #include "function.h"
34 #include "expr.h"
35 #include "ggc.h"
36 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-flow.h"
39 #include "timevar.h"
40 #include "tree-dump.h"
41 #include "tree-pass.h"
42 #include "toplev.h"
43 #include "except.h"
44 #include "cfgloop.h"
45 #include "cfglayout.h"
46 #include "hashtab.h"
47 #include "tree-ssa-propagate.h"
48
49 /* Remove any fallthru edge from EV.  Return true if an edge was removed.  */
50
51 static bool
52 remove_fallthru_edge (VEC(edge,gc) *ev)
53 {
54   edge_iterator ei;
55   edge e;
56
57   FOR_EACH_EDGE (e, ei, ev)
58     if ((e->flags & EDGE_FALLTHRU) != 0)
59       {
60         remove_edge (e);
61         return true;
62       }
63   return false;
64 }
65
66 /* Disconnect an unreachable block in the control expression starting
67    at block BB.  */
68
69 static bool
70 cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
71 {
72   edge taken_edge;
73   bool retval = false;
74   tree expr = bsi_stmt (bsi), val;
75
76   if (!single_succ_p (bb))
77     {
78       edge e;
79       edge_iterator ei;
80
81       switch (TREE_CODE (expr))
82         {
83         case COND_EXPR:
84           val = COND_EXPR_COND (expr);
85           break;
86
87         case SWITCH_EXPR:
88           val = SWITCH_COND (expr);
89           if (TREE_CODE (val) != INTEGER_CST)
90             return false;
91           break;
92
93         default:
94           gcc_unreachable ();
95         }
96
97       taken_edge = find_taken_edge (bb, val);
98       if (!taken_edge)
99         return false;
100
101       /* Remove all the edges except the one that is always executed.  */
102       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
103         {
104           if (e != taken_edge)
105             {
106               taken_edge->probability += e->probability;
107               taken_edge->count += e->count;
108               remove_edge (e);
109               retval = true;
110             }
111           else
112             ei_next (&ei);
113         }
114       if (taken_edge->probability > REG_BR_PROB_BASE)
115         taken_edge->probability = REG_BR_PROB_BASE;
116     }
117   else
118     taken_edge = single_succ_edge (bb);
119
120   bsi_remove (&bsi);
121   taken_edge->flags = EDGE_FALLTHRU;
122
123   /* We removed some paths from the cfg.  */
124   free_dominance_info (CDI_DOMINATORS);
125
126   return retval;
127 }
128
129 /* A list of all the noreturn calls passed to modify_stmt.
130    cleanup_control_flow uses it to detect cases where a mid-block
131    indirect call has been turned into a noreturn call.  When this
132    happens, all the instructions after the call are no longer
133    reachable and must be deleted as dead.  */
134
135 VEC(tree,gc) *modified_noreturn_calls;
136
137 /* Try to remove superfluous control structures.  */
138
139 static bool
140 cleanup_control_flow (void)
141 {
142   basic_block bb;
143   block_stmt_iterator bsi;
144   bool retval = false;
145   tree stmt;
146
147   /* Detect cases where a mid-block call is now known not to return.  */
148   while (VEC_length (tree, modified_noreturn_calls))
149     {
150       stmt = VEC_pop (tree, modified_noreturn_calls);
151       bb = bb_for_stmt (stmt);
152       if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt))
153         split_block (bb, stmt);
154     }
155
156   FOR_EACH_BB (bb)
157     {
158       bsi = bsi_last (bb);
159
160       if (bsi_end_p (bsi))
161         continue;
162
163       stmt = bsi_stmt (bsi);
164       if (TREE_CODE (stmt) == COND_EXPR
165           || TREE_CODE (stmt) == SWITCH_EXPR)
166         retval |= cleanup_control_expr_graph (bb, bsi);
167
168       /* If we had a computed goto which has a compile-time determinable
169          destination, then we can eliminate the goto.  */
170       if (TREE_CODE (stmt) == GOTO_EXPR
171           && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR
172           && TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0)) == LABEL_DECL)
173         {
174           edge e;
175           tree label;
176           edge_iterator ei;
177           basic_block target_block;
178           bool removed_edge = false;
179
180           /* First look at all the outgoing edges.  Delete any outgoing
181              edges which do not go to the right block.  For the one
182              edge which goes to the right block, fix up its flags.  */
183           label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0);
184           target_block = label_to_block (label);
185           for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
186             {
187               if (e->dest != target_block)
188                 {
189                   removed_edge = true;
190                   remove_edge (e);
191                 }
192               else
193                 {
194                   /* Turn off the EDGE_ABNORMAL flag.  */
195                   e->flags &= ~EDGE_ABNORMAL;
196
197                   /* And set EDGE_FALLTHRU.  */
198                   e->flags |= EDGE_FALLTHRU;
199                   ei_next (&ei);
200                 }
201             }
202
203           /* If we removed one or more edges, then we will need to fix the
204              dominators.  It may be possible to incrementally update them.  */
205           if (removed_edge)
206             free_dominance_info (CDI_DOMINATORS);
207
208           /* Remove the GOTO_EXPR as it is not needed.  The CFG has all the
209              relevant information we need.  */
210           bsi_remove (&bsi);
211           retval = true;
212         }
213
214       /* Check for indirect calls that have been turned into
215          noreturn calls.  */
216       if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs))
217         {
218           free_dominance_info (CDI_DOMINATORS);
219           retval = true;
220         }
221     }
222   return retval;
223 }
224
225 /* Return true if basic block BB does nothing except pass control
226    flow to another block and that we can safely insert a label at
227    the start of the successor block.
228
229    As a precondition, we require that BB be not equal to
230    ENTRY_BLOCK_PTR.  */
231
232 static bool
233 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
234 {
235   block_stmt_iterator bsi;
236
237   /* BB must have a single outgoing edge.  */
238   if (single_succ_p (bb) != 1
239       /* If PHI_WANTED is false, BB must not have any PHI nodes.
240          Otherwise, BB must have PHI nodes.  */
241       || (phi_nodes (bb) != NULL_TREE) != phi_wanted
242       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
243       || single_succ (bb) == EXIT_BLOCK_PTR
244       /* Nor should this be an infinite loop.  */
245       || single_succ (bb) == bb
246       /* BB may not have an abnormal outgoing edge.  */
247       || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
248     return false;
249
250 #if ENABLE_CHECKING
251   gcc_assert (bb != ENTRY_BLOCK_PTR);
252 #endif
253
254   /* Now walk through the statements backward.  We can ignore labels,
255      anything else means this is not a forwarder block.  */
256   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
257     {
258       tree stmt = bsi_stmt (bsi);
259
260       switch (TREE_CODE (stmt))
261         {
262         case LABEL_EXPR:
263           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
264             return false;
265           break;
266
267         default:
268           return false;
269         }
270     }
271
272   if (find_edge (ENTRY_BLOCK_PTR, bb))
273     return false;
274
275   if (current_loops)
276     {
277       basic_block dest;
278       /* Protect loop latches, headers and preheaders.  */
279       if (bb->loop_father->header == bb)
280         return false;
281       dest = EDGE_SUCC (bb, 0)->dest;
282
283       if (dest->loop_father->header == dest)
284         return false;
285     }
286
287   return true;
288 }
289
290 /* Return true if BB has at least one abnormal incoming edge.  */
291
292 static inline bool
293 has_abnormal_incoming_edge_p (basic_block bb)
294 {
295   edge e;
296   edge_iterator ei;
297
298   FOR_EACH_EDGE (e, ei, bb->preds)
299     if (e->flags & EDGE_ABNORMAL)
300       return true;
301
302   return false;
303 }
304
305 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
306    those alternatives are equal in each of the PHI nodes, then return
307    true, else return false.  */
308
309 static bool
310 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
311 {
312   int n1 = e1->dest_idx;
313   int n2 = e2->dest_idx;
314   tree phi;
315
316   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
317     {
318       tree val1 = PHI_ARG_DEF (phi, n1);
319       tree val2 = PHI_ARG_DEF (phi, n2);
320
321       gcc_assert (val1 != NULL_TREE);
322       gcc_assert (val2 != NULL_TREE);
323
324       if (!operand_equal_for_phi_arg_p (val1, val2))
325         return false;
326     }
327
328   return true;
329 }
330
331 /* Removes forwarder block BB.  Returns false if this failed.  If a new
332    forwarder block is created due to redirection of edges, it is
333    stored to worklist.  */
334
335 static bool
336 remove_forwarder_block (basic_block bb, basic_block **worklist)
337 {
338   edge succ = single_succ_edge (bb), e, s;
339   basic_block dest = succ->dest;
340   tree label;
341   tree phi;
342   edge_iterator ei;
343   block_stmt_iterator bsi, bsi_to;
344   bool seen_abnormal_edge = false;
345
346   /* We check for infinite loops already in tree_forwarder_block_p.
347      However it may happen that the infinite loop is created
348      afterwards due to removal of forwarders.  */
349   if (dest == bb)
350     return false;
351
352   /* If the destination block consists of a nonlocal label, do not merge
353      it.  */
354   label = first_stmt (dest);
355   if (label
356       && TREE_CODE (label) == LABEL_EXPR
357       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
358     return false;
359
360   /* If there is an abnormal edge to basic block BB, but not into
361      dest, problems might occur during removal of the phi node at out
362      of ssa due to overlapping live ranges of registers.
363
364      If there is an abnormal edge in DEST, the problems would occur
365      anyway since cleanup_dead_labels would then merge the labels for
366      two different eh regions, and rest of exception handling code
367      does not like it.
368
369      So if there is an abnormal edge to BB, proceed only if there is
370      no abnormal edge to DEST and there are no phi nodes in DEST.  */
371   if (has_abnormal_incoming_edge_p (bb))
372     {
373       seen_abnormal_edge = true;
374
375       if (has_abnormal_incoming_edge_p (dest)
376           || phi_nodes (dest) != NULL_TREE)
377         return false;
378     }
379
380   /* If there are phi nodes in DEST, and some of the blocks that are
381      predecessors of BB are also predecessors of DEST, check that the
382      phi node arguments match.  */
383   if (phi_nodes (dest))
384     {
385       FOR_EACH_EDGE (e, ei, bb->preds)
386         {
387           s = find_edge (e->src, dest);
388           if (!s)
389             continue;
390
391           if (!phi_alternatives_equal (dest, succ, s))
392             return false;
393         }
394     }
395
396   /* Redirect the edges.  */
397   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
398     {
399       if (e->flags & EDGE_ABNORMAL)
400         {
401           /* If there is an abnormal edge, redirect it anyway, and
402              move the labels to the new block to make it legal.  */
403           s = redirect_edge_succ_nodup (e, dest);
404         }
405       else
406         s = redirect_edge_and_branch (e, dest);
407
408       if (s == e)
409         {
410           /* Create arguments for the phi nodes, since the edge was not
411              here before.  */
412           for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
413             add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
414         }
415       else
416         {
417           /* The source basic block might become a forwarder.  We know
418              that it was not a forwarder before, since it used to have
419              at least two outgoing edges, so we may just add it to
420              worklist.  */
421           if (tree_forwarder_block_p (s->src, false))
422             *(*worklist)++ = s->src;
423         }
424     }
425
426   if (seen_abnormal_edge)
427     {
428       /* Move the labels to the new block, so that the redirection of
429          the abnormal edges works.  */
430
431       bsi_to = bsi_start (dest);
432       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
433         {
434           label = bsi_stmt (bsi);
435           gcc_assert (TREE_CODE (label) == LABEL_EXPR);
436           bsi_remove (&bsi);
437           bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
438         }
439     }
440
441   /* Update the dominators.  */
442   if (dom_info_available_p (CDI_DOMINATORS))
443     {
444       basic_block dom, dombb, domdest;
445
446       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
447       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
448       if (domdest == bb)
449         {
450           /* Shortcut to avoid calling (relatively expensive)
451              nearest_common_dominator unless necessary.  */
452           dom = dombb;
453         }
454       else
455         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
456
457       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
458     }
459
460   /* And kill the forwarder block.  */
461   delete_basic_block (bb);
462
463   return true;
464 }
465
466 /* Removes forwarder blocks.  */
467
468 static bool
469 cleanup_forwarder_blocks (void)
470 {
471   basic_block bb;
472   bool changed = false;
473   basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
474   basic_block *current = worklist;
475
476   FOR_EACH_BB (bb)
477     {
478       if (tree_forwarder_block_p (bb, false))
479         *current++ = bb;
480     }
481
482   while (current != worklist)
483     {
484       bb = *--current;
485       changed |= remove_forwarder_block (bb, &current);
486     }
487
488   free (worklist);
489   return changed;
490 }
491
492 /* Do one round of CFG cleanup.  */
493
494 static bool
495 cleanup_tree_cfg_1 (void)
496 {
497   bool retval;
498
499   retval = cleanup_control_flow ();
500   retval |= delete_unreachable_blocks ();
501
502   /* Forwarder blocks can carry line number information which is
503      useful when debugging, so we only clean them up when
504      optimizing.  */
505
506   if (optimize > 0)
507     {
508       /* cleanup_forwarder_blocks can redirect edges out of
509          SWITCH_EXPRs, which can get expensive.  So we want to enable
510          recording of edge to CASE_LABEL_EXPR mappings around the call
511          to cleanup_forwarder_blocks.  */
512       start_recording_case_labels ();
513       retval |= cleanup_forwarder_blocks ();
514       end_recording_case_labels ();
515     }
516
517   /* Merging the blocks may create new opportunities for folding
518      conditional branches (due to the elimination of single-valued PHI
519      nodes).  */
520   retval |= merge_seq_blocks ();
521
522   return retval;
523 }
524
525
526 /* Remove unreachable blocks and other miscellaneous clean up work.  */
527
528 bool
529 cleanup_tree_cfg (void)
530 {
531   bool retval;
532
533   timevar_push (TV_TREE_CLEANUP_CFG);
534
535   do
536     retval = cleanup_tree_cfg_1 ();
537   while (retval);
538
539   compact_blocks ();
540
541 #ifdef ENABLE_CHECKING
542   verify_flow_info ();
543 #endif
544
545   timevar_pop (TV_TREE_CLEANUP_CFG);
546
547   return retval;
548 }
549
550 /* Cleanup cfg and repair loop structures.  */
551
552 void
553 cleanup_tree_cfg_loop (void)
554 {
555   bitmap changed_bbs = BITMAP_ALLOC (NULL);
556
557   cleanup_tree_cfg ();
558
559   fix_loop_structure (current_loops, changed_bbs);
560   calculate_dominance_info (CDI_DOMINATORS);
561
562   /* This usually does nothing.  But sometimes parts of cfg that originally
563      were inside a loop get out of it due to edge removal (since they
564      become unreachable by back edges from latch).  */
565   rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
566
567   BITMAP_FREE (changed_bbs);
568
569 #ifdef ENABLE_CHECKING
570   verify_loop_structure (current_loops);
571 #endif
572 }
573
574 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
575
576 static void
577 remove_forwarder_block_with_phi (basic_block bb)
578 {
579   edge succ = single_succ_edge (bb);
580   basic_block dest = succ->dest;
581   tree label;
582   basic_block dombb, domdest, dom;
583
584   /* We check for infinite loops already in tree_forwarder_block_p.
585      However it may happen that the infinite loop is created
586      afterwards due to removal of forwarders.  */
587   if (dest == bb)
588     return;
589
590   /* If the destination block consists of a nonlocal label, do not
591      merge it.  */
592   label = first_stmt (dest);
593   if (label
594       && TREE_CODE (label) == LABEL_EXPR
595       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
596     return;
597
598   /* Redirect each incoming edge to BB to DEST.  */
599   while (EDGE_COUNT (bb->preds) > 0)
600     {
601       edge e = EDGE_PRED (bb, 0), s;
602       tree phi;
603
604       s = find_edge (e->src, dest);
605       if (s)
606         {
607           /* We already have an edge S from E->src to DEST.  If S and
608              E->dest's sole successor edge have the same PHI arguments
609              at DEST, redirect S to DEST.  */
610           if (phi_alternatives_equal (dest, s, succ))
611             {
612               e = redirect_edge_and_branch (e, dest);
613               PENDING_STMT (e) = NULL_TREE;
614               continue;
615             }
616
617           /* PHI arguments are different.  Create a forwarder block by
618              splitting E so that we can merge PHI arguments on E to
619              DEST.  */
620           e = single_succ_edge (split_edge (e));
621         }
622
623       s = redirect_edge_and_branch (e, dest);
624
625       /* redirect_edge_and_branch must not create a new edge.  */
626       gcc_assert (s == e);
627
628       /* Add to the PHI nodes at DEST each PHI argument removed at the
629          destination of E.  */
630       for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
631         {
632           tree def = PHI_ARG_DEF (phi, succ->dest_idx);
633
634           if (TREE_CODE (def) == SSA_NAME)
635             {
636               tree var;
637
638               /* If DEF is one of the results of PHI nodes removed during
639                  redirection, replace it with the PHI argument that used
640                  to be on E.  */
641               for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
642                 {
643                   tree old_arg = TREE_PURPOSE (var);
644                   tree new_arg = TREE_VALUE (var);
645
646                   if (def == old_arg)
647                     {
648                       def = new_arg;
649                       break;
650                     }
651                 }
652             }
653
654           add_phi_arg (phi, def, s);
655         }
656
657       PENDING_STMT (e) = NULL;
658     }
659
660   /* Update the dominators.  */
661   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
662   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
663   if (domdest == bb)
664     {
665       /* Shortcut to avoid calling (relatively expensive)
666          nearest_common_dominator unless necessary.  */
667       dom = dombb;
668     }
669   else
670     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
671
672   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
673
674   /* Remove BB since all of BB's incoming edges have been redirected
675      to DEST.  */
676   delete_basic_block (bb);
677 }
678
679 /* This pass merges PHI nodes if one feeds into another.  For example,
680    suppose we have the following:
681
682   goto <bb 9> (<L9>);
683
684 <L8>:;
685   tem_17 = foo ();
686
687   # tem_6 = PHI <tem_17(8), tem_23(7)>;
688 <L9>:;
689
690   # tem_3 = PHI <tem_6(9), tem_2(5)>;
691 <L10>:;
692
693   Then we merge the first PHI node into the second one like so:
694
695   goto <bb 9> (<L10>);
696
697 <L8>:;
698   tem_17 = foo ();
699
700   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
701 <L10>:;
702 */
703
704 static void
705 merge_phi_nodes (void)
706 {
707   basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
708   basic_block *current = worklist;
709   basic_block bb;
710
711   calculate_dominance_info (CDI_DOMINATORS);
712
713   /* Find all PHI nodes that we may be able to merge.  */
714   FOR_EACH_BB (bb)
715     {
716       basic_block dest;
717
718       /* Look for a forwarder block with PHI nodes.  */
719       if (!tree_forwarder_block_p (bb, true))
720         continue;
721
722       dest = single_succ (bb);
723
724       /* We have to feed into another basic block with PHI
725          nodes.  */
726       if (!phi_nodes (dest)
727           /* We don't want to deal with a basic block with
728              abnormal edges.  */
729           || has_abnormal_incoming_edge_p (bb))
730         continue;
731
732       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
733         {
734           /* If BB does not dominate DEST, then the PHI nodes at
735              DEST must be the only users of the results of the PHI
736              nodes at BB.  */
737           *current++ = bb;
738         }
739     }
740
741   /* Now let's drain WORKLIST.  */
742   while (current != worklist)
743     {
744       bb = *--current;
745       remove_forwarder_block_with_phi (bb);
746     }
747
748   free (worklist);
749 }
750
751 static bool
752 gate_merge_phi (void)
753 {
754   return 1;
755 }
756
757 struct tree_opt_pass pass_merge_phi = {
758   "mergephi",                   /* name */
759   gate_merge_phi,               /* gate */
760   merge_phi_nodes,              /* execute */
761   NULL,                         /* sub */
762   NULL,                         /* next */
763   0,                            /* static_pass_number */
764   TV_TREE_MERGE_PHI,            /* tv_id */
765   PROP_cfg | PROP_ssa,          /* properties_required */
766   0,                            /* properties_provided */
767   0,                            /* properties_destroyed */
768   0,                            /* todo_flags_start */
769   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
770   | TODO_verify_ssa,
771   0                             /* letter */
772 };