Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-phiopt.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
3 Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "flags.h"
29 #include "tm_p.h"
30 #include "basic-block.h"
31 #include "timevar.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-pass.h"
35 #include "tree-dump.h"
36 #include "langhooks.h"
37 #include "pointer-set.h"
38 #include "domwalk.h"
39
40 static unsigned int tree_ssa_phiopt (void);
41 static unsigned int tree_ssa_phiopt_worker (bool);
42 static bool conditional_replacement (basic_block, basic_block,
43 edge, edge, gimple, tree, tree);
44 static bool value_replacement (basic_block, basic_block,
45 edge, edge, gimple, tree, tree);
46 static bool minmax_replacement (basic_block, basic_block,
47 edge, edge, gimple, tree, tree);
48 static bool abs_replacement (basic_block, basic_block,
49 edge, edge, gimple, tree, tree);
50 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
51 struct pointer_set_t *);
52 static struct pointer_set_t * get_non_trapping (void);
53 static void replace_phi_edge_with_variable (basic_block, edge, gimple, tree);
54
55 /* This pass tries to replaces an if-then-else block with an
56 assignment. We have four kinds of transformations. Some of these
57 transformations are also performed by the ifcvt RTL optimizer.
58
59 Conditional Replacement
60 -----------------------
61
62 This transformation, implemented in conditional_replacement,
63 replaces
64
65 bb0:
66 if (cond) goto bb2; else goto bb1;
67 bb1:
68 bb2:
69 x = PHI <0 (bb1), 1 (bb0), ...>;
70
71 with
72
73 bb0:
74 x' = cond;
75 goto bb2;
76 bb2:
77 x = PHI <x' (bb0), ...>;
78
79 We remove bb1 as it becomes unreachable. This occurs often due to
80 gimplification of conditionals.
81
82 Value Replacement
83 -----------------
84
85 This transformation, implemented in value_replacement, replaces
86
87 bb0:
88 if (a != b) goto bb2; else goto bb1;
89 bb1:
90 bb2:
91 x = PHI <a (bb1), b (bb0), ...>;
92
93 with
94
95 bb0:
96 bb2:
97 x = PHI <b (bb0), ...>;
98
99 This opportunity can sometimes occur as a result of other
100 optimizations.
101
102 ABS Replacement
103 ---------------
104
105 This transformation, implemented in abs_replacement, replaces
106
107 bb0:
108 if (a >= 0) goto bb2; else goto bb1;
109 bb1:
110 x = -a;
111 bb2:
112 x = PHI <x (bb1), a (bb0), ...>;
113
114 with
115
116 bb0:
117 x' = ABS_EXPR< a >;
118 bb2:
119 x = PHI <x' (bb0), ...>;
120
121 MIN/MAX Replacement
122 -------------------
123
124 This transformation, minmax_replacement replaces
125
126 bb0:
127 if (a <= b) goto bb2; else goto bb1;
128 bb1:
129 bb2:
130 x = PHI <b (bb1), a (bb0), ...>;
131
132 with
133
134 bb0:
135 x' = MIN_EXPR (a, b)
136 bb2:
137 x = PHI <x' (bb0), ...>;
138
139 A similar transformation is done for MAX_EXPR. */
140
141 static unsigned int
142 tree_ssa_phiopt (void)
143 {
144 return tree_ssa_phiopt_worker (false);
145 }
146
147 /* This pass tries to transform conditional stores into unconditional
148 ones, enabling further simplifications with the simpler then and else
149 blocks. In particular it replaces this:
150
151 bb0:
152 if (cond) goto bb2; else goto bb1;
153 bb1:
154 *p = RHS
155 bb2:
156
157 with
158
159 bb0:
160 if (cond) goto bb1; else goto bb2;
161 bb1:
162 condtmp' = *p;
163 bb2:
164 condtmp = PHI <RHS, condtmp'>
165 *p = condtmp
166
167 This transformation can only be done under several constraints,
168 documented below. */
169
170 static unsigned int
171 tree_ssa_cs_elim (void)
172 {
173 return tree_ssa_phiopt_worker (true);
174 }
175
176 /* For conditional store replacement we need a temporary to
177 put the old contents of the memory in. */
178 static tree condstoretemp;
179
180 /* The core routine of conditional store replacement and normal
181 phi optimizations. Both share much of the infrastructure in how
182 to match applicable basic block patterns. DO_STORE_ELIM is true
183 when we want to do conditional store replacement, false otherwise. */
184 static unsigned int
185 tree_ssa_phiopt_worker (bool do_store_elim)
186 {
187 basic_block bb;
188 basic_block *bb_order;
189 unsigned n, i;
190 bool cfgchanged = false;
191 struct pointer_set_t *nontrap = 0;
192
193 if (do_store_elim)
194 {
195 condstoretemp = NULL_TREE;
196 /* Calculate the set of non-trapping memory accesses. */
197 nontrap = get_non_trapping ();
198 }
199
200 /* Search every basic block for COND_EXPR we may be able to optimize.
201
202 We walk the blocks in order that guarantees that a block with
203 a single predecessor is processed before the predecessor.
204 This ensures that we collapse inner ifs before visiting the
205 outer ones, and also that we do not try to visit a removed
206 block. */
207 bb_order = blocks_in_phiopt_order ();
208 n = n_basic_blocks - NUM_FIXED_BLOCKS;
209
210 for (i = 0; i < n; i++)
211 {
212 gimple cond_stmt, phi;
213 basic_block bb1, bb2;
214 edge e1, e2;
215 tree arg0, arg1;
216
217 bb = bb_order[i];
218
219 cond_stmt = last_stmt (bb);
220 /* Check to see if the last statement is a GIMPLE_COND. */
221 if (!cond_stmt
222 || gimple_code (cond_stmt) != GIMPLE_COND)
223 continue;
224
225 e1 = EDGE_SUCC (bb, 0);
226 bb1 = e1->dest;
227 e2 = EDGE_SUCC (bb, 1);
228 bb2 = e2->dest;
229
230 /* We cannot do the optimization on abnormal edges. */
231 if ((e1->flags & EDGE_ABNORMAL) != 0
232 || (e2->flags & EDGE_ABNORMAL) != 0)
233 continue;
234
235 /* If either bb1's succ or bb2 or bb2's succ is non NULL. */
236 if (EDGE_COUNT (bb1->succs) == 0
237 || bb2 == NULL
238 || EDGE_COUNT (bb2->succs) == 0)
239 continue;
240
241 /* Find the bb which is the fall through to the other. */
242 if (EDGE_SUCC (bb1, 0)->dest == bb2)
243 ;
244 else if (EDGE_SUCC (bb2, 0)->dest == bb1)
245 {
246 basic_block bb_tmp = bb1;
247 edge e_tmp = e1;
248 bb1 = bb2;
249 bb2 = bb_tmp;
250 e1 = e2;
251 e2 = e_tmp;
252 }
253 else
254 continue;
255
256 e1 = EDGE_SUCC (bb1, 0);
257
258 /* Make sure that bb1 is just a fall through. */
259 if (!single_succ_p (bb1)
260 || (e1->flags & EDGE_FALLTHRU) == 0)
261 continue;
262
263 /* Also make sure that bb1 only have one predecessor and that it
264 is bb. */
265 if (!single_pred_p (bb1)
266 || single_pred (bb1) != bb)
267 continue;
268
269 if (do_store_elim)
270 {
271 /* bb1 is the middle block, bb2 the join block, bb the split block,
272 e1 the fallthrough edge from bb1 to bb2. We can't do the
273 optimization if the join block has more than two predecessors. */
274 if (EDGE_COUNT (bb2->preds) > 2)
275 continue;
276 if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
277 cfgchanged = true;
278 }
279 else
280 {
281 gimple_seq phis = phi_nodes (bb2);
282
283 /* Check to make sure that there is only one PHI node.
284 TODO: we could do it with more than one iff the other PHI nodes
285 have the same elements for these two edges. */
286 if (! gimple_seq_singleton_p (phis))
287 continue;
288
289 phi = gsi_stmt (gsi_start (phis));
290 arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
291 arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
292
293 /* Something is wrong if we cannot find the arguments in the PHI
294 node. */
295 gcc_assert (arg0 != NULL && arg1 != NULL);
296
297 /* Do the replacement of conditional if it can be done. */
298 if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
299 cfgchanged = true;
300 else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
301 cfgchanged = true;
302 else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
303 cfgchanged = true;
304 else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
305 cfgchanged = true;
306 }
307 }
308
309 free (bb_order);
310
311 if (do_store_elim)
312 pointer_set_destroy (nontrap);
313 /* If the CFG has changed, we should cleanup the CFG. */
314 if (cfgchanged && do_store_elim)
315 {
316 /* In cond-store replacement we have added some loads on edges
317 and new VOPS (as we moved the store, and created a load). */
318 gsi_commit_edge_inserts ();
319 return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
320 }
321 else if (cfgchanged)
322 return TODO_cleanup_cfg;
323 return 0;
324 }
325
326 /* Returns the list of basic blocks in the function in an order that guarantees
327 that if a block X has just a single predecessor Y, then Y is after X in the
328 ordering. */
329
330 basic_block *
331 blocks_in_phiopt_order (void)
332 {
333 basic_block x, y;
334 basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
335 unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
336 unsigned np, i;
337 sbitmap visited = sbitmap_alloc (last_basic_block);
338
339 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
340 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
341
342 sbitmap_zero (visited);
343
344 MARK_VISITED (ENTRY_BLOCK_PTR);
345 FOR_EACH_BB (x)
346 {
347 if (VISITED_P (x))
348 continue;
349
350 /* Walk the predecessors of x as long as they have precisely one
351 predecessor and add them to the list, so that they get stored
352 after x. */
353 for (y = x, np = 1;
354 single_pred_p (y) && !VISITED_P (single_pred (y));
355 y = single_pred (y))
356 np++;
357 for (y = x, i = n - np;
358 single_pred_p (y) && !VISITED_P (single_pred (y));
359 y = single_pred (y), i++)
360 {
361 order[i] = y;
362 MARK_VISITED (y);
363 }
364 order[i] = y;
365 MARK_VISITED (y);
366
367 gcc_assert (i == n - 1);
368 n -= np;
369 }
370
371 sbitmap_free (visited);
372 gcc_assert (n == 0);
373 return order;
374
375 #undef MARK_VISITED
376 #undef VISITED_P
377 }
378
379
380 /* Return TRUE if block BB has no executable statements, otherwise return
381 FALSE. */
382
383 bool
384 empty_block_p (basic_block bb)
385 {
386 /* BB must have no executable statements. */
387 return gsi_end_p (gsi_after_labels (bb));
388 }
389
390 /* Replace PHI node element whose edge is E in block BB with variable NEW.
391 Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
392 is known to have two edges, one of which must reach BB). */
393
394 static void
395 replace_phi_edge_with_variable (basic_block cond_block,
396 edge e, gimple phi, tree new_tree)
397 {
398 basic_block bb = gimple_bb (phi);
399 basic_block block_to_remove;
400 gimple_stmt_iterator gsi;
401
402 /* Change the PHI argument to new. */
403 SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
404
405 /* Remove the empty basic block. */
406 if (EDGE_SUCC (cond_block, 0)->dest == bb)
407 {
408 EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
409 EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
410 EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
411 EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
412
413 block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
414 }
415 else
416 {
417 EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
418 EDGE_SUCC (cond_block, 1)->flags
419 &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
420 EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
421 EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
422
423 block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
424 }
425 delete_basic_block (block_to_remove);
426
427 /* Eliminate the COND_EXPR at the end of COND_BLOCK. */
428 gsi = gsi_last_bb (cond_block);
429 gsi_remove (&gsi, true);
430
431 if (dump_file && (dump_flags & TDF_DETAILS))
432 fprintf (dump_file,
433 "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
434 cond_block->index,
435 bb->index);
436 }
437
438 /* The function conditional_replacement does the main work of doing the
439 conditional replacement. Return true if the replacement is done.
440 Otherwise return false.
441 BB is the basic block where the replacement is going to be done on. ARG0
442 is argument 0 from PHI. Likewise for ARG1. */
443
444 static bool
445 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
446 edge e0, edge e1, gimple phi,
447 tree arg0, tree arg1)
448 {
449 tree result;
450 gimple stmt, new_stmt;
451 tree cond;
452 gimple_stmt_iterator gsi;
453 edge true_edge, false_edge;
454 tree new_var, new_var2;
455
456 /* FIXME: Gimplification of complex type is too hard for now. */
457 if (TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
458 || TREE_CODE (TREE_TYPE (arg1)) == COMPLEX_TYPE)
459 return false;
460
461 /* The PHI arguments have the constants 0 and 1, then convert
462 it to the conditional. */
463 if ((integer_zerop (arg0) && integer_onep (arg1))
464 || (integer_zerop (arg1) && integer_onep (arg0)))
465 ;
466 else
467 return false;
468
469 if (!empty_block_p (middle_bb))
470 return false;
471
472 /* At this point we know we have a GIMPLE_COND with two successors.
473 One successor is BB, the other successor is an empty block which
474 falls through into BB.
475
476 There is a single PHI node at the join point (BB) and its arguments
477 are constants (0, 1).
478
479 So, given the condition COND, and the two PHI arguments, we can
480 rewrite this PHI into non-branching code:
481
482 dest = (COND) or dest = COND'
483
484 We use the condition as-is if the argument associated with the
485 true edge has the value one or the argument associated with the
486 false edge as the value zero. Note that those conditions are not
487 the same since only one of the outgoing edges from the GIMPLE_COND
488 will directly reach BB and thus be associated with an argument. */
489
490 stmt = last_stmt (cond_bb);
491 result = PHI_RESULT (phi);
492
493 /* To handle special cases like floating point comparison, it is easier and
494 less error-prone to build a tree and gimplify it on the fly though it is
495 less efficient. */
496 cond = fold_build2 (gimple_cond_code (stmt), boolean_type_node,
497 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
498
499 /* We need to know which is the true edge and which is the false
500 edge so that we know when to invert the condition below. */
501 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
502 if ((e0 == true_edge && integer_zerop (arg0))
503 || (e0 == false_edge && integer_onep (arg0))
504 || (e1 == true_edge && integer_zerop (arg1))
505 || (e1 == false_edge && integer_onep (arg1)))
506 cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
507
508 /* Insert our new statements at the end of conditional block before the
509 COND_STMT. */
510 gsi = gsi_for_stmt (stmt);
511 new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
512 GSI_SAME_STMT);
513
514 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
515 {
516 new_var2 = create_tmp_var (TREE_TYPE (result), NULL);
517 add_referenced_var (new_var2);
518 new_stmt = gimple_build_assign_with_ops (CONVERT_EXPR, new_var2,
519 new_var, NULL);
520 new_var2 = make_ssa_name (new_var2, new_stmt);
521 gimple_assign_set_lhs (new_stmt, new_var2);
522 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
523 new_var = new_var2;
524 }
525
526 replace_phi_edge_with_variable (cond_bb, e1, phi, new_var);
527
528 /* Note that we optimized this PHI. */
529 return true;
530 }
531
532 /* The function value_replacement does the main work of doing the value
533 replacement. Return true if the replacement is done. Otherwise return
534 false.
535 BB is the basic block where the replacement is going to be done on. ARG0
536 is argument 0 from the PHI. Likewise for ARG1. */
537
538 static bool
539 value_replacement (basic_block cond_bb, basic_block middle_bb,
540 edge e0, edge e1, gimple phi,
541 tree arg0, tree arg1)
542 {
543 gimple cond;
544 edge true_edge, false_edge;
545 enum tree_code code;
546
547 /* If the type says honor signed zeros we cannot do this
548 optimization. */
549 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
550 return false;
551
552 if (!empty_block_p (middle_bb))
553 return false;
554
555 cond = last_stmt (cond_bb);
556 code = gimple_cond_code (cond);
557
558 /* This transformation is only valid for equality comparisons. */
559 if (code != NE_EXPR && code != EQ_EXPR)
560 return false;
561
562 /* We need to know which is the true edge and which is the false
563 edge so that we know if have abs or negative abs. */
564 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
565
566 /* At this point we know we have a COND_EXPR with two successors.
567 One successor is BB, the other successor is an empty block which
568 falls through into BB.
569
570 The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
571
572 There is a single PHI node at the join point (BB) with two arguments.
573
574 We now need to verify that the two arguments in the PHI node match
575 the two arguments to the equality comparison. */
576
577 if ((operand_equal_for_phi_arg_p (arg0, gimple_cond_lhs (cond))
578 && operand_equal_for_phi_arg_p (arg1, gimple_cond_rhs (cond)))
579 || (operand_equal_for_phi_arg_p (arg1, gimple_cond_lhs (cond))
580 && operand_equal_for_phi_arg_p (arg0, gimple_cond_rhs (cond))))
581 {
582 edge e;
583 tree arg;
584
585 /* For NE_EXPR, we want to build an assignment result = arg where
586 arg is the PHI argument associated with the true edge. For
587 EQ_EXPR we want the PHI argument associated with the false edge. */
588 e = (code == NE_EXPR ? true_edge : false_edge);
589
590 /* Unfortunately, E may not reach BB (it may instead have gone to
591 OTHER_BLOCK). If that is the case, then we want the single outgoing
592 edge from OTHER_BLOCK which reaches BB and represents the desired
593 path from COND_BLOCK. */
594 if (e->dest == middle_bb)
595 e = single_succ_edge (e->dest);
596
597 /* Now we know the incoming edge to BB that has the argument for the
598 RHS of our new assignment statement. */
599 if (e0 == e)
600 arg = arg0;
601 else
602 arg = arg1;
603
604 replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
605
606 /* Note that we optimized this PHI. */
607 return true;
608 }
609 return false;
610 }
611
612 /* The function minmax_replacement does the main work of doing the minmax
613 replacement. Return true if the replacement is done. Otherwise return
614 false.
615 BB is the basic block where the replacement is going to be done on. ARG0
616 is argument 0 from the PHI. Likewise for ARG1. */
617
618 static bool
619 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
620 edge e0, edge e1, gimple phi,
621 tree arg0, tree arg1)
622 {
623 tree result, type;
624 gimple cond, new_stmt;
625 edge true_edge, false_edge;
626 enum tree_code cmp, minmax, ass_code;
627 tree smaller, larger, arg_true, arg_false;
628 gimple_stmt_iterator gsi, gsi_from;
629
630 type = TREE_TYPE (PHI_RESULT (phi));
631
632 /* The optimization may be unsafe due to NaNs. */
633 if (HONOR_NANS (TYPE_MODE (type)))
634 return false;
635
636 cond = last_stmt (cond_bb);
637 cmp = gimple_cond_code (cond);
638 result = PHI_RESULT (phi);
639
640 /* This transformation is only valid for order comparisons. Record which
641 operand is smaller/larger if the result of the comparison is true. */
642 if (cmp == LT_EXPR || cmp == LE_EXPR)
643 {
644 smaller = gimple_cond_lhs (cond);
645 larger = gimple_cond_rhs (cond);
646 }
647 else if (cmp == GT_EXPR || cmp == GE_EXPR)
648 {
649 smaller = gimple_cond_rhs (cond);
650 larger = gimple_cond_lhs (cond);
651 }
652 else
653 return false;
654
655 /* We need to know which is the true edge and which is the false
656 edge so that we know if have abs or negative abs. */
657 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
658
659 /* Forward the edges over the middle basic block. */
660 if (true_edge->dest == middle_bb)
661 true_edge = EDGE_SUCC (true_edge->dest, 0);
662 if (false_edge->dest == middle_bb)
663 false_edge = EDGE_SUCC (false_edge->dest, 0);
664
665 if (true_edge == e0)
666 {
667 gcc_assert (false_edge == e1);
668 arg_true = arg0;
669 arg_false = arg1;
670 }
671 else
672 {
673 gcc_assert (false_edge == e0);
674 gcc_assert (true_edge == e1);
675 arg_true = arg1;
676 arg_false = arg0;
677 }
678
679 if (empty_block_p (middle_bb))
680 {
681 if (operand_equal_for_phi_arg_p (arg_true, smaller)
682 && operand_equal_for_phi_arg_p (arg_false, larger))
683 {
684 /* Case
685
686 if (smaller < larger)
687 rslt = smaller;
688 else
689 rslt = larger; */
690 minmax = MIN_EXPR;
691 }
692 else if (operand_equal_for_phi_arg_p (arg_false, smaller)
693 && operand_equal_for_phi_arg_p (arg_true, larger))
694 minmax = MAX_EXPR;
695 else
696 return false;
697 }
698 else
699 {
700 /* Recognize the following case, assuming d <= u:
701
702 if (a <= u)
703 b = MAX (a, d);
704 x = PHI <b, u>
705
706 This is equivalent to
707
708 b = MAX (a, d);
709 x = MIN (b, u); */
710
711 gimple assign = last_and_only_stmt (middle_bb);
712 tree lhs, op0, op1, bound;
713
714 if (!assign
715 || gimple_code (assign) != GIMPLE_ASSIGN)
716 return false;
717
718 lhs = gimple_assign_lhs (assign);
719 ass_code = gimple_assign_rhs_code (assign);
720 if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
721 return false;
722 op0 = gimple_assign_rhs1 (assign);
723 op1 = gimple_assign_rhs2 (assign);
724
725 if (true_edge->src == middle_bb)
726 {
727 /* We got here if the condition is true, i.e., SMALLER < LARGER. */
728 if (!operand_equal_for_phi_arg_p (lhs, arg_true))
729 return false;
730
731 if (operand_equal_for_phi_arg_p (arg_false, larger))
732 {
733 /* Case
734
735 if (smaller < larger)
736 {
737 r' = MAX_EXPR (smaller, bound)
738 }
739 r = PHI <r', larger> --> to be turned to MIN_EXPR. */
740 if (ass_code != MAX_EXPR)
741 return false;
742
743 minmax = MIN_EXPR;
744 if (operand_equal_for_phi_arg_p (op0, smaller))
745 bound = op1;
746 else if (operand_equal_for_phi_arg_p (op1, smaller))
747 bound = op0;
748 else
749 return false;
750
751 /* We need BOUND <= LARGER. */
752 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
753 bound, larger)))
754 return false;
755 }
756 else if (operand_equal_for_phi_arg_p (arg_false, smaller))
757 {
758 /* Case
759
760 if (smaller < larger)
761 {
762 r' = MIN_EXPR (larger, bound)
763 }
764 r = PHI <r', smaller> --> to be turned to MAX_EXPR. */
765 if (ass_code != MIN_EXPR)
766 return false;
767
768 minmax = MAX_EXPR;
769 if (operand_equal_for_phi_arg_p (op0, larger))
770 bound = op1;
771 else if (operand_equal_for_phi_arg_p (op1, larger))
772 bound = op0;
773 else
774 return false;
775
776 /* We need BOUND >= SMALLER. */
777 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
778 bound, smaller)))
779 return false;
780 }
781 else
782 return false;
783 }
784 else
785 {
786 /* We got here if the condition is false, i.e., SMALLER > LARGER. */
787 if (!operand_equal_for_phi_arg_p (lhs, arg_false))
788 return false;
789
790 if (operand_equal_for_phi_arg_p (arg_true, larger))
791 {
792 /* Case
793
794 if (smaller > larger)
795 {
796 r' = MIN_EXPR (smaller, bound)
797 }
798 r = PHI <r', larger> --> to be turned to MAX_EXPR. */
799 if (ass_code != MIN_EXPR)
800 return false;
801
802 minmax = MAX_EXPR;
803 if (operand_equal_for_phi_arg_p (op0, smaller))
804 bound = op1;
805 else if (operand_equal_for_phi_arg_p (op1, smaller))
806 bound = op0;
807 else
808 return false;
809
810 /* We need BOUND >= LARGER. */
811 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
812 bound, larger)))
813 return false;
814 }
815 else if (operand_equal_for_phi_arg_p (arg_true, smaller))
816 {
817 /* Case
818
819 if (smaller > larger)
820 {
821 r' = MAX_EXPR (larger, bound)
822 }
823 r = PHI <r', smaller> --> to be turned to MIN_EXPR. */
824 if (ass_code != MAX_EXPR)
825 return false;
826
827 minmax = MIN_EXPR;
828 if (operand_equal_for_phi_arg_p (op0, larger))
829 bound = op1;
830 else if (operand_equal_for_phi_arg_p (op1, larger))
831 bound = op0;
832 else
833 return false;
834
835 /* We need BOUND <= SMALLER. */
836 if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
837 bound, smaller)))
838 return false;
839 }
840 else
841 return false;
842 }
843
844 /* Move the statement from the middle block. */
845 gsi = gsi_last_bb (cond_bb);
846 gsi_from = gsi_last_bb (middle_bb);
847 gsi_move_before (&gsi_from, &gsi);
848 }
849
850 /* Emit the statement to compute min/max. */
851 result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
852 new_stmt = gimple_build_assign_with_ops (minmax, result, arg0, arg1);
853 gsi = gsi_last_bb (cond_bb);
854 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
855
856 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
857 return true;
858 }
859
860 /* The function absolute_replacement does the main work of doing the absolute
861 replacement. Return true if the replacement is done. Otherwise return
862 false.
863 bb is the basic block where the replacement is going to be done on. arg0
864 is argument 0 from the phi. Likewise for arg1. */
865
866 static bool
867 abs_replacement (basic_block cond_bb, basic_block middle_bb,
868 edge e0 ATTRIBUTE_UNUSED, edge e1,
869 gimple phi, tree arg0, tree arg1)
870 {
871 tree result;
872 gimple new_stmt, cond;
873 gimple_stmt_iterator gsi;
874 edge true_edge, false_edge;
875 gimple assign;
876 edge e;
877 tree rhs, lhs;
878 bool negate;
879 enum tree_code cond_code;
880
881 /* If the type says honor signed zeros we cannot do this
882 optimization. */
883 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
884 return false;
885
886 /* OTHER_BLOCK must have only one executable statement which must have the
887 form arg0 = -arg1 or arg1 = -arg0. */
888
889 assign = last_and_only_stmt (middle_bb);
890 /* If we did not find the proper negation assignment, then we can not
891 optimize. */
892 if (assign == NULL)
893 return false;
894
895 /* If we got here, then we have found the only executable statement
896 in OTHER_BLOCK. If it is anything other than arg = -arg1 or
897 arg1 = -arg0, then we can not optimize. */
898 if (gimple_code (assign) != GIMPLE_ASSIGN)
899 return false;
900
901 lhs = gimple_assign_lhs (assign);
902
903 if (gimple_assign_rhs_code (assign) != NEGATE_EXPR)
904 return false;
905
906 rhs = gimple_assign_rhs1 (assign);
907
908 /* The assignment has to be arg0 = -arg1 or arg1 = -arg0. */
909 if (!(lhs == arg0 && rhs == arg1)
910 && !(lhs == arg1 && rhs == arg0))
911 return false;
912
913 cond = last_stmt (cond_bb);
914 result = PHI_RESULT (phi);
915
916 /* Only relationals comparing arg[01] against zero are interesting. */
917 cond_code = gimple_cond_code (cond);
918 if (cond_code != GT_EXPR && cond_code != GE_EXPR
919 && cond_code != LT_EXPR && cond_code != LE_EXPR)
920 return false;
921
922 /* Make sure the conditional is arg[01] OP y. */
923 if (gimple_cond_lhs (cond) != rhs)
924 return false;
925
926 if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond)))
927 ? real_zerop (gimple_cond_rhs (cond))
928 : integer_zerop (gimple_cond_rhs (cond)))
929 ;
930 else
931 return false;
932
933 /* We need to know which is the true edge and which is the false
934 edge so that we know if have abs or negative abs. */
935 extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
936
937 /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
938 will need to negate the result. Similarly for LT_EXPR/LE_EXPR if
939 the false edge goes to OTHER_BLOCK. */
940 if (cond_code == GT_EXPR || cond_code == GE_EXPR)
941 e = true_edge;
942 else
943 e = false_edge;
944
945 if (e->dest == middle_bb)
946 negate = true;
947 else
948 negate = false;
949
950 result = duplicate_ssa_name (result, NULL);
951
952 if (negate)
953 {
954 tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
955 add_referenced_var (tmp);
956 lhs = make_ssa_name (tmp, NULL);
957 }
958 else
959 lhs = result;
960
961 /* Build the modify expression with abs expression. */
962 new_stmt = gimple_build_assign_with_ops (ABS_EXPR, lhs, rhs, NULL);
963
964 gsi = gsi_last_bb (cond_bb);
965 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
966
967 if (negate)
968 {
969 /* Get the right GSI. We want to insert after the recently
970 added ABS_EXPR statement (which we know is the first statement
971 in the block. */
972 new_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, result, lhs, NULL);
973
974 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
975 }
976
977 replace_phi_edge_with_variable (cond_bb, e1, phi, result);
978
979 /* Note that we optimized this PHI. */
980 return true;
981 }
982
983 /* Auxiliary functions to determine the set of memory accesses which
984 can't trap because they are preceded by accesses to the same memory
985 portion. We do that for INDIRECT_REFs, so we only need to track
986 the SSA_NAME of the pointer indirectly referenced. The algorithm
987 simply is a walk over all instructions in dominator order. When
988 we see an INDIRECT_REF we determine if we've already seen a same
989 ref anywhere up to the root of the dominator tree. If we do the
990 current access can't trap. If we don't see any dominating access
991 the current access might trap, but might also make later accesses
992 non-trapping, so we remember it. We need to be careful with loads
993 or stores, for instance a load might not trap, while a store would,
994 so if we see a dominating read access this doesn't mean that a later
995 write access would not trap. Hence we also need to differentiate the
996 type of access(es) seen.
997
998 ??? We currently are very conservative and assume that a load might
999 trap even if a store doesn't (write-only memory). This probably is
1000 overly conservative. */
1001
1002 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF
1003 through it was seen, which would constitute a no-trap region for
1004 same accesses. */
1005 struct name_to_bb
1006 {
1007 tree ssa_name;
1008 basic_block bb;
1009 unsigned store : 1;
1010 };
1011
1012 /* The hash table for remembering what we've seen. */
1013 static htab_t seen_ssa_names;
1014
1015 /* The set of INDIRECT_REFs which can't trap. */
1016 static struct pointer_set_t *nontrap_set;
1017
1018 /* The hash function, based on the pointer to the pointer SSA_NAME. */
1019 static hashval_t
1020 name_to_bb_hash (const void *p)
1021 {
1022 const_tree n = ((const struct name_to_bb *)p)->ssa_name;
1023 return htab_hash_pointer (n) ^ ((const struct name_to_bb *)p)->store;
1024 }
1025
1026 /* The equality function of *P1 and *P2. SSA_NAMEs are shared, so
1027 it's enough to simply compare them for equality. */
1028 static int
1029 name_to_bb_eq (const void *p1, const void *p2)
1030 {
1031 const struct name_to_bb *n1 = (const struct name_to_bb *)p1;
1032 const struct name_to_bb *n2 = (const struct name_to_bb *)p2;
1033
1034 return n1->ssa_name == n2->ssa_name && n1->store == n2->store;
1035 }
1036
1037 /* We see the expression EXP in basic block BB. If it's an interesting
1038 expression (an INDIRECT_REF through an SSA_NAME) possibly insert the
1039 expression into the set NONTRAP or the hash table of seen expressions.
1040 STORE is true if this expression is on the LHS, otherwise it's on
1041 the RHS. */
1042 static void
1043 add_or_mark_expr (basic_block bb, tree exp,
1044 struct pointer_set_t *nontrap, bool store)
1045 {
1046 if (INDIRECT_REF_P (exp)
1047 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME)
1048 {
1049 tree name = TREE_OPERAND (exp, 0);
1050 struct name_to_bb map;
1051 void **slot;
1052 struct name_to_bb *n2bb;
1053 basic_block found_bb = 0;
1054
1055 /* Try to find the last seen INDIRECT_REF through the same
1056 SSA_NAME, which can trap. */
1057 map.ssa_name = name;
1058 map.bb = 0;
1059 map.store = store;
1060 slot = htab_find_slot (seen_ssa_names, &map, INSERT);
1061 n2bb = (struct name_to_bb *) *slot;
1062 if (n2bb)
1063 found_bb = n2bb->bb;
1064
1065 /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP
1066 (it's in a basic block on the path from us to the dominator root)
1067 then we can't trap. */
1068 if (found_bb && found_bb->aux == (void *)1)
1069 {
1070 pointer_set_insert (nontrap, exp);
1071 }
1072 else
1073 {
1074 /* EXP might trap, so insert it into the hash table. */
1075 if (n2bb)
1076 {
1077 n2bb->bb = bb;
1078 }
1079 else
1080 {
1081 n2bb = XNEW (struct name_to_bb);
1082 n2bb->ssa_name = name;
1083 n2bb->bb = bb;
1084 n2bb->store = store;
1085 *slot = n2bb;
1086 }
1087 }
1088 }
1089 }
1090
1091 /* Called by walk_dominator_tree, when entering the block BB. */
1092 static void
1093 nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1094 {
1095 gimple_stmt_iterator gsi;
1096 /* Mark this BB as being on the path to dominator root. */
1097 bb->aux = (void*)1;
1098
1099 /* And walk the statements in order. */
1100 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1101 {
1102 gimple stmt = gsi_stmt (gsi);
1103
1104 if (is_gimple_assign (stmt))
1105 {
1106 add_or_mark_expr (bb, gimple_assign_lhs (stmt), nontrap_set, true);
1107 add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), nontrap_set, false);
1108 if (get_gimple_rhs_num_ops (gimple_assign_rhs_code (stmt)) > 1)
1109 add_or_mark_expr (bb, gimple_assign_rhs2 (stmt), nontrap_set,
1110 false);
1111 }
1112 }
1113 }
1114
1115 /* Called by walk_dominator_tree, when basic block BB is exited. */
1116 static void
1117 nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1118 {
1119 /* This BB isn't on the path to dominator root anymore. */
1120 bb->aux = NULL;
1121 }
1122
1123 /* This is the entry point of gathering non trapping memory accesses.
1124 It will do a dominator walk over the whole function, and it will
1125 make use of the bb->aux pointers. It returns a set of trees
1126 (the INDIRECT_REFs itself) which can't trap. */
1127 static struct pointer_set_t *
1128 get_non_trapping (void)
1129 {
1130 struct pointer_set_t *nontrap;
1131 struct dom_walk_data walk_data;
1132
1133 nontrap = pointer_set_create ();
1134 seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq,
1135 free);
1136 /* We're going to do a dominator walk, so ensure that we have
1137 dominance information. */
1138 calculate_dominance_info (CDI_DOMINATORS);
1139
1140 /* Setup callbacks for the generic dominator tree walker. */
1141 nontrap_set = nontrap;
1142 walk_data.walk_stmts_backward = false;
1143 walk_data.dom_direction = CDI_DOMINATORS;
1144 walk_data.initialize_block_local_data = NULL;
1145 walk_data.before_dom_children_before_stmts = nt_init_block;
1146 walk_data.before_dom_children_walk_stmts = NULL;
1147 walk_data.before_dom_children_after_stmts = NULL;
1148 walk_data.after_dom_children_before_stmts = NULL;
1149 walk_data.after_dom_children_walk_stmts = NULL;
1150 walk_data.after_dom_children_after_stmts = nt_fini_block;
1151 walk_data.global_data = NULL;
1152 walk_data.block_local_data_size = 0;
1153 walk_data.interesting_blocks = NULL;
1154
1155 init_walk_dominator_tree (&walk_data);
1156 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1157 fini_walk_dominator_tree (&walk_data);
1158 htab_delete (seen_ssa_names);
1159
1160 return nontrap;
1161 }
1162
1163 /* Do the main work of conditional store replacement. We already know
1164 that the recognized pattern looks like so:
1165
1166 split:
1167 if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1168 MIDDLE_BB:
1169 something
1170 fallthrough (edge E0)
1171 JOIN_BB:
1172 some more
1173
1174 We check that MIDDLE_BB contains only one store, that that store
1175 doesn't trap (not via NOTRAP, but via checking if an access to the same
1176 memory location dominates us) and that the store has a "simple" RHS. */
1177
1178 static bool
1179 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1180 edge e0, edge e1, struct pointer_set_t *nontrap)
1181 {
1182 gimple assign = last_and_only_stmt (middle_bb);
1183 tree lhs, rhs, name;
1184 gimple newphi, new_stmt;
1185 gimple_stmt_iterator gsi;
1186 enum tree_code code;
1187
1188 /* Check if middle_bb contains of only one store. */
1189 if (!assign
1190 || gimple_code (assign) != GIMPLE_ASSIGN)
1191 return false;
1192
1193 lhs = gimple_assign_lhs (assign);
1194 rhs = gimple_assign_rhs1 (assign);
1195 if (!INDIRECT_REF_P (lhs))
1196 return false;
1197
1198 /* RHS is either a single SSA_NAME or a constant. */
1199 code = gimple_assign_rhs_code (assign);
1200 if (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
1201 || (code != SSA_NAME && !is_gimple_min_invariant (rhs)))
1202 return false;
1203 /* Prove that we can move the store down. We could also check
1204 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1205 whose value is not available readily, which we want to avoid. */
1206 if (!pointer_set_contains (nontrap, lhs))
1207 return false;
1208
1209 /* Now we've checked the constraints, so do the transformation:
1210 1) Remove the single store. */
1211 mark_symbols_for_renaming (assign);
1212 gsi = gsi_for_stmt (assign);
1213 gsi_remove (&gsi, true);
1214
1215 /* 2) Create a temporary where we can store the old content
1216 of the memory touched by the store, if we need to. */
1217 if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1218 {
1219 condstoretemp = create_tmp_var (TREE_TYPE (lhs), "cstore");
1220 get_var_ann (condstoretemp);
1221 if (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE
1222 || TREE_CODE (TREE_TYPE (lhs)) == VECTOR_TYPE)
1223 DECL_GIMPLE_REG_P (condstoretemp) = 1;
1224 }
1225 add_referenced_var (condstoretemp);
1226
1227 /* 3) Insert a load from the memory of the store to the temporary
1228 on the edge which did not contain the store. */
1229 lhs = unshare_expr (lhs);
1230 new_stmt = gimple_build_assign (condstoretemp, lhs);
1231 name = make_ssa_name (condstoretemp, new_stmt);
1232 gimple_assign_set_lhs (new_stmt, name);
1233 mark_symbols_for_renaming (new_stmt);
1234 gsi_insert_on_edge (e1, new_stmt);
1235
1236 /* 4) Create a PHI node at the join block, with one argument
1237 holding the old RHS, and the other holding the temporary
1238 where we stored the old memory contents. */
1239 newphi = create_phi_node (condstoretemp, join_bb);
1240 add_phi_arg (newphi, rhs, e0);
1241 add_phi_arg (newphi, name, e1);
1242
1243 lhs = unshare_expr (lhs);
1244 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1245 mark_symbols_for_renaming (new_stmt);
1246
1247 /* 5) Insert that PHI node. */
1248 gsi = gsi_after_labels (join_bb);
1249 if (gsi_end_p (gsi))
1250 {
1251 gsi = gsi_last_bb (join_bb);
1252 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1253 }
1254 else
1255 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1256
1257 return true;
1258 }
1259
1260 /* Always do these optimizations if we have SSA
1261 trees to work on. */
1262 static bool
1263 gate_phiopt (void)
1264 {
1265 return 1;
1266 }
1267
1268 struct gimple_opt_pass pass_phiopt =
1269 {
1270 {
1271 GIMPLE_PASS,
1272 "phiopt", /* name */
1273 gate_phiopt, /* gate */
1274 tree_ssa_phiopt, /* execute */
1275 NULL, /* sub */
1276 NULL, /* next */
1277 0, /* static_pass_number */
1278 TV_TREE_PHIOPT, /* tv_id */
1279 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1280 0, /* properties_provided */
1281 0, /* properties_destroyed */
1282 0, /* todo_flags_start */
1283 TODO_dump_func
1284 | TODO_ggc_collect
1285 | TODO_verify_ssa
1286 | TODO_verify_flow
1287 | TODO_verify_stmts /* todo_flags_finish */
1288 }
1289 };
1290
1291 static bool
1292 gate_cselim (void)
1293 {
1294 return flag_tree_cselim;
1295 }
1296
1297 struct gimple_opt_pass pass_cselim =
1298 {
1299 {
1300 GIMPLE_PASS,
1301 "cselim", /* name */
1302 gate_cselim, /* gate */
1303 tree_ssa_cs_elim, /* execute */
1304 NULL, /* sub */
1305 NULL, /* next */
1306 0, /* static_pass_number */
1307 TV_TREE_PHIOPT, /* tv_id */
1308 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1309 0, /* properties_provided */
1310 0, /* properties_destroyed */
1311 0, /* todo_flags_start */
1312 TODO_dump_func
1313 | TODO_ggc_collect
1314 | TODO_verify_ssa
1315 | TODO_verify_flow
1316 | TODO_verify_stmts /* todo_flags_finish */
1317 }
1318 };