1 /* Optimization of PHI nodes by converting them into straightline code.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3    Free Software Foundation, 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 "flags.h"
28 #include "tm_p.h"
29 #include "basic-block.h"
30 #include "timevar.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
33 #include "tree-dump.h"
34 #include "langhooks.h"
35 #include "pointer-set.h"
36 #include "domwalk.h"
37 #include "cfgloop.h"
38 #include "tree-data-ref.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 bool cond_if_else_store_replacement (basic_block, basic_block, basic_block);
53 static struct pointer_set_t * get_non_trapping (void);
54 static void replace_phi_edge_with_variable (basic_block, edge, gimple, tree);
55 
56 /* This pass tries to replaces an if-then-else block with an
57    assignment.  We have four kinds of transformations.  Some of these
58    transformations are also performed by the ifcvt RTL optimizer.
59 
60    Conditional Replacement
61    -----------------------
62 
63    This transformation, implemented in conditional_replacement,
64    replaces
65 
66      bb0:
67       if (cond) goto bb2; else goto bb1;
68      bb1:
69      bb2:
70       x = PHI <0 (bb1), 1 (bb0), ...>;
71 
72    with
73 
74      bb0:
75       x' = cond;
76       goto bb2;
77      bb2:
78       x = PHI <x' (bb0), ...>;
79 
80    We remove bb1 as it becomes unreachable.  This occurs often due to
81    gimplification of conditionals.
82 
83    Value Replacement
84    -----------------
85 
86    This transformation, implemented in value_replacement, replaces
87 
88      bb0:
89        if (a != b) goto bb2; else goto bb1;
90      bb1:
91      bb2:
92        x = PHI <a (bb1), b (bb0), ...>;
93 
94    with
95 
96      bb0:
97      bb2:
98        x = PHI <b (bb0), ...>;
99 
100    This opportunity can sometimes occur as a result of other
101    optimizations.
102 
103    ABS Replacement
104    ---------------
105 
106    This transformation, implemented in abs_replacement, replaces
107 
108      bb0:
109        if (a >= 0) goto bb2; else goto bb1;
110      bb1:
111        x = -a;
112      bb2:
113        x = PHI <x (bb1), a (bb0), ...>;
114 
115    with
116 
117      bb0:
118        x' = ABS_EXPR< a >;
119      bb2:
120        x = PHI <x' (bb0), ...>;
121 
122    MIN/MAX Replacement
123    -------------------
124 
125    This transformation, minmax_replacement replaces
126 
127      bb0:
128        if (a <= b) goto bb2; else goto bb1;
129      bb1:
130      bb2:
131        x = PHI <b (bb1), a (bb0), ...>;
132 
133    with
134 
135      bb0:
136        x' = MIN_EXPR (a, b)
137      bb2:
138        x = PHI <x' (bb0), ...>;
139 
140    A similar transformation is done for MAX_EXPR.  */
141 
142 static unsigned int
143 tree_ssa_phiopt (void)
144 {
145   return tree_ssa_phiopt_worker (false);
146 }
147 
148 /* This pass tries to transform conditional stores into unconditional
149    ones, enabling further simplifications with the simpler then and else
150    blocks.  In particular it replaces this:
151 
152      bb0:
153        if (cond) goto bb2; else goto bb1;
154      bb1:
155        *p = RHS;
156      bb2:
157 
158    with
159 
160      bb0:
161        if (cond) goto bb1; else goto bb2;
162      bb1:
163        condtmp' = *p;
164      bb2:
165        condtmp = PHI <RHS, condtmp'>
166        *p = condtmp;
167 
168    This transformation can only be done under several constraints,
169    documented below.  It also replaces:
170 
171      bb0:
172        if (cond) goto bb2; else goto bb1;
173      bb1:
174        *p = RHS1;
175        goto bb3;
176      bb2:
177        *p = RHS2;
178      bb3:
179 
180    with
181 
182      bb0:
183        if (cond) goto bb3; else goto bb1;
184      bb1:
185      bb3:
186        condtmp = PHI <RHS1, RHS2>
187        *p = condtmp;  */
188 
189 static unsigned int
190 tree_ssa_cs_elim (void)
191 {
192   return tree_ssa_phiopt_worker (true);
193 }
194 
195 /* For conditional store replacement we need a temporary to
196    put the old contents of the memory in.  */
197 static tree condstoretemp;
198 
199 /* The core routine of conditional store replacement and normal
200    phi optimizations.  Both share much of the infrastructure in how
201    to match applicable basic block patterns.  DO_STORE_ELIM is true
202    when we want to do conditional store replacement, false otherwise.  */
203 static unsigned int
204 tree_ssa_phiopt_worker (bool do_store_elim)
205 {
206   basic_block bb;
207   basic_block *bb_order;
208   unsigned n, i;
209   bool cfgchanged = false;
210   struct pointer_set_t *nontrap = 0;
211 
212   if (do_store_elim)
213     {
214       condstoretemp = NULL_TREE;
215       /* Calculate the set of non-trapping memory accesses.  */
216       nontrap = get_non_trapping ();
217     }
218 
219   /* Search every basic block for COND_EXPR we may be able to optimize.
220 
221      We walk the blocks in order that guarantees that a block with
222      a single predecessor is processed before the predecessor.
223      This ensures that we collapse inner ifs before visiting the
224      outer ones, and also that we do not try to visit a removed
225      block.  */
226   bb_order = blocks_in_phiopt_order ();
227   n = n_basic_blocks - NUM_FIXED_BLOCKS;
228 
229   for (i = 0; i < n; i++)
230     {
231       gimple cond_stmt, phi;
232       basic_block bb1, bb2;
233       edge e1, e2;
234       tree arg0, arg1;
235 
236       bb = bb_order[i];
237 
238       cond_stmt = last_stmt (bb);
239       /* Check to see if the last statement is a GIMPLE_COND.  */
240       if (!cond_stmt
241           || gimple_code (cond_stmt) != GIMPLE_COND)
242         continue;
243 
244       e1 = EDGE_SUCC (bb, 0);
245       bb1 = e1->dest;
246       e2 = EDGE_SUCC (bb, 1);
247       bb2 = e2->dest;
248 
249       /* We cannot do the optimization on abnormal edges.  */
250       if ((e1->flags & EDGE_ABNORMAL) != 0
251           || (e2->flags & EDGE_ABNORMAL) != 0)
252        continue;
253 
254       /* If either bb1's succ or bb2 or bb2's succ is non NULL.  */
255       if (EDGE_COUNT (bb1->succs) == 0
256           || bb2 == NULL
257 	  || EDGE_COUNT (bb2->succs) == 0)
258         continue;
259 
260       /* Find the bb which is the fall through to the other.  */
261       if (EDGE_SUCC (bb1, 0)->dest == bb2)
262         ;
263       else if (EDGE_SUCC (bb2, 0)->dest == bb1)
264         {
265 	  basic_block bb_tmp = bb1;
266 	  edge e_tmp = e1;
267 	  bb1 = bb2;
268 	  bb2 = bb_tmp;
269 	  e1 = e2;
270 	  e2 = e_tmp;
271 	}
272       else if (do_store_elim
273 	       && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
274 	{
275 	  basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
276 
277 	  if (!single_succ_p (bb1)
278 	      || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0
279 	      || !single_succ_p (bb2)
280 	      || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0
281 	      || EDGE_COUNT (bb3->preds) != 2)
282 	    continue;
283 	  if (cond_if_else_store_replacement (bb1, bb2, bb3))
284 	    cfgchanged = true;
285 	  continue;
286 	}
287       else
288 	continue;
289 
290       e1 = EDGE_SUCC (bb1, 0);
291 
292       /* Make sure that bb1 is just a fall through.  */
293       if (!single_succ_p (bb1)
294 	  || (e1->flags & EDGE_FALLTHRU) == 0)
295         continue;
296 
297       /* Also make sure that bb1 only have one predecessor and that it
298 	 is bb.  */
299       if (!single_pred_p (bb1)
300           || single_pred (bb1) != bb)
301 	continue;
302 
303       if (do_store_elim)
304 	{
305 	  /* bb1 is the middle block, bb2 the join block, bb the split block,
306 	     e1 the fallthrough edge from bb1 to bb2.  We can't do the
307 	     optimization if the join block has more than two predecessors.  */
308 	  if (EDGE_COUNT (bb2->preds) > 2)
309 	    continue;
310 	  if (cond_store_replacement (bb1, bb2, e1, e2, nontrap))
311 	    cfgchanged = true;
312 	}
313       else
314 	{
315 	  gimple_seq phis = phi_nodes (bb2);
316 	  gimple_stmt_iterator gsi;
317 
318 	  /* Check to make sure that there is only one non-virtual PHI node.
319 	     TODO: we could do it with more than one iff the other PHI nodes
320 	     have the same elements for these two edges.  */
321 	  phi = NULL;
322 	  for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
323 	    {
324 	      if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
325 		continue;
326 	      if (phi)
327 		{
328 		  phi = NULL;
329 		  break;
330 		}
331 	      phi = gsi_stmt (gsi);
332 	    }
333 	  if (!phi)
334 	    continue;
335 
336 	  arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
337 	  arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
338 
339 	  /* Something is wrong if we cannot find the arguments in the PHI
340 	     node.  */
341 	  gcc_assert (arg0 != NULL && arg1 != NULL);
342 
343 	  /* Do the replacement of conditional if it can be done.  */
344 	  if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
345 	    cfgchanged = true;
346 	  else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
347 	    cfgchanged = true;
348 	  else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
349 	    cfgchanged = true;
350 	  else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
351 	    cfgchanged = true;
352 	}
353     }
354 
355   free (bb_order);
356 
357   if (do_store_elim)
358     pointer_set_destroy (nontrap);
359   /* If the CFG has changed, we should cleanup the CFG.  */
360   if (cfgchanged && do_store_elim)
361     {
362       /* In cond-store replacement we have added some loads on edges
363          and new VOPS (as we moved the store, and created a load).  */
364       gsi_commit_edge_inserts ();
365       return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
366     }
367   else if (cfgchanged)
368     return TODO_cleanup_cfg;
369   return 0;
370 }
371 
372 /* Returns the list of basic blocks in the function in an order that guarantees
373    that if a block X has just a single predecessor Y, then Y is after X in the
374    ordering.  */
375 
376 basic_block *
377 blocks_in_phiopt_order (void)
378 {
379   basic_block x, y;
380   basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
381   unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
382   unsigned np, i;
383   sbitmap visited = sbitmap_alloc (last_basic_block);
384 
385 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
386 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
387 
388   sbitmap_zero (visited);
389 
390   MARK_VISITED (ENTRY_BLOCK_PTR);
391   FOR_EACH_BB (x)
392     {
393       if (VISITED_P (x))
394 	continue;
395 
396       /* Walk the predecessors of x as long as they have precisely one
397 	 predecessor and add them to the list, so that they get stored
398 	 after x.  */
399       for (y = x, np = 1;
400 	   single_pred_p (y) && !VISITED_P (single_pred (y));
401 	   y = single_pred (y))
402 	np++;
403       for (y = x, i = n - np;
404 	   single_pred_p (y) && !VISITED_P (single_pred (y));
405 	   y = single_pred (y), i++)
406 	{
407 	  order[i] = y;
408 	  MARK_VISITED (y);
409 	}
410       order[i] = y;
411       MARK_VISITED (y);
412 
413       gcc_assert (i == n - 1);
414       n -= np;
415     }
416 
417   sbitmap_free (visited);
418   gcc_assert (n == 0);
419   return order;
420 
421 #undef MARK_VISITED
422 #undef VISITED_P
423 }
424 
425 
426 /* Return TRUE if block BB has no executable statements, otherwise return
427    FALSE.  */
428 
429 bool
430 empty_block_p (basic_block bb)
431 {
432   /* BB must have no executable statements.  */
433   gimple_stmt_iterator gsi = gsi_after_labels (bb);
434   if (gsi_end_p (gsi))
435     return true;
436   if (is_gimple_debug (gsi_stmt (gsi)))
437     gsi_next_nondebug (&gsi);
438   return gsi_end_p (gsi);
439 }
440 
441 /* Replace PHI node element whose edge is E in block BB with variable NEW.
442    Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
443    is known to have two edges, one of which must reach BB).  */
444 
445 static void
446 replace_phi_edge_with_variable (basic_block cond_block,
447 				edge e, gimple phi, tree new_tree)
448 {
449   basic_block bb = gimple_bb (phi);
450   basic_block block_to_remove;
451   gimple_stmt_iterator gsi;
452 
453   /* Change the PHI argument to new.  */
454   SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
455 
456   /* Remove the empty basic block.  */
457   if (EDGE_SUCC (cond_block, 0)->dest == bb)
458     {
459       EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
460       EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
461       EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
462       EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
463 
464       block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
465     }
466   else
467     {
468       EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
469       EDGE_SUCC (cond_block, 1)->flags
470 	&= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
471       EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
472       EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
473 
474       block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
475     }
476   delete_basic_block (block_to_remove);
477 
478   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
479   gsi = gsi_last_bb (cond_block);
480   gsi_remove (&gsi, true);
481 
482   if (dump_file && (dump_flags & TDF_DETAILS))
483     fprintf (dump_file,
484 	      "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
485 	      cond_block->index,
486 	      bb->index);
487 }
488 
489 /*  The function conditional_replacement does the main work of doing the
490     conditional replacement.  Return true if the replacement is done.
491     Otherwise return false.
492     BB is the basic block where the replacement is going to be done on.  ARG0
493     is argument 0 from PHI.  Likewise for ARG1.  */
494 
495 static bool
496 conditional_replacement (basic_block cond_bb, basic_block middle_bb,
497 			 edge e0, edge e1, gimple phi,
498 			 tree arg0, tree arg1)
499 {
500   tree result;
501   gimple stmt, new_stmt;
502   tree cond;
503   gimple_stmt_iterator gsi;
504   edge true_edge, false_edge;
505   tree new_var, new_var2;
506 
507   /* FIXME: Gimplification of complex type is too hard for now.  */
508   if (TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
509       || TREE_CODE (TREE_TYPE (arg1)) == COMPLEX_TYPE)
510     return false;
511 
512   /* The PHI arguments have the constants 0 and 1, then convert
513      it to the conditional.  */
514   if ((integer_zerop (arg0) && integer_onep (arg1))
515       || (integer_zerop (arg1) && integer_onep (arg0)))
516     ;
517   else
518     return false;
519 
520   if (!empty_block_p (middle_bb))
521     return false;
522 
523   /* At this point we know we have a GIMPLE_COND with two successors.
524      One successor is BB, the other successor is an empty block which
525      falls through into BB.
526 
527      There is a single PHI node at the join point (BB) and its arguments
528      are constants (0, 1).
529 
530      So, given the condition COND, and the two PHI arguments, we can
531      rewrite this PHI into non-branching code:
532 
533        dest = (COND) or dest = COND'
534 
535      We use the condition as-is if the argument associated with the
536      true edge has the value one or the argument associated with the
537      false edge as the value zero.  Note that those conditions are not
538      the same since only one of the outgoing edges from the GIMPLE_COND
539      will directly reach BB and thus be associated with an argument.  */
540 
541   stmt = last_stmt (cond_bb);
542   result = PHI_RESULT (phi);
543 
544   /* To handle special cases like floating point comparison, it is easier and
545      less error-prone to build a tree and gimplify it on the fly though it is
546      less efficient.  */
547   cond = fold_build2_loc (gimple_location (stmt),
548 			  gimple_cond_code (stmt), boolean_type_node,
549 			  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
550 
551   /* We need to know which is the true edge and which is the false
552      edge so that we know when to invert the condition below.  */
553   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
554   if ((e0 == true_edge && integer_zerop (arg0))
555       || (e0 == false_edge && integer_onep (arg0))
556       || (e1 == true_edge && integer_zerop (arg1))
557       || (e1 == false_edge && integer_onep (arg1)))
558     cond = fold_build1_loc (gimple_location (stmt),
559 			    TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
560 
561   /* Insert our new statements at the end of conditional block before the
562      COND_STMT.  */
563   gsi = gsi_for_stmt (stmt);
564   new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
565 				      GSI_SAME_STMT);
566 
567   if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
568     {
569       source_location locus_0, locus_1;
570 
571       new_var2 = create_tmp_var (TREE_TYPE (result), NULL);
572       add_referenced_var (new_var2);
573       new_stmt = gimple_build_assign_with_ops (CONVERT_EXPR, new_var2,
574 					       new_var, NULL);
575       new_var2 = make_ssa_name (new_var2, new_stmt);
576       gimple_assign_set_lhs (new_stmt, new_var2);
577       gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
578       new_var = new_var2;
579 
580       /* Set the locus to the first argument, unless is doesn't have one.  */
581       locus_0 = gimple_phi_arg_location (phi, 0);
582       locus_1 = gimple_phi_arg_location (phi, 1);
583       if (locus_0 == UNKNOWN_LOCATION)
584         locus_0 = locus_1;
585       gimple_set_location (new_stmt, locus_0);
586     }
587 
588   replace_phi_edge_with_variable (cond_bb, e1, phi, new_var);
589 
590   /* Note that we optimized this PHI.  */
591   return true;
592 }
593 
594 /* Update *ARG which is defined in STMT so that it contains the
595    computed value if that seems profitable.  Return true if the
596    statement is made dead by that rewriting.  */
597 
598 static bool
599 jump_function_from_stmt (tree *arg, gimple stmt)
600 {
601   enum tree_code code = gimple_assign_rhs_code (stmt);
602   if (code == ADDR_EXPR)
603     {
604       /* For arg = &p->i transform it to p, if possible.  */
605       tree rhs1 = gimple_assign_rhs1 (stmt);
606       HOST_WIDE_INT offset;
607       tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
608 						&offset);
609       if (tem
610 	  && TREE_CODE (tem) == MEM_REF
611 	  && double_int_zero_p
612 	       (double_int_add (mem_ref_offset (tem),
613 				shwi_to_double_int (offset))))
614 	{
615 	  *arg = TREE_OPERAND (tem, 0);
616 	  return true;
617 	}
618     }
619   /* TODO: Much like IPA-CP jump-functions we want to handle constant
620      additions symbolically here, and we'd need to update the comparison
621      code that compares the arg + cst tuples in our caller.  For now the
622      code above exactly handles the VEC_BASE pattern from vec.h.  */
623   return false;
624 }
625 
626 /*  The function value_replacement does the main work of doing the value
627     replacement.  Return true if the replacement is done.  Otherwise return
628     false.
629     BB is the basic block where the replacement is going to be done on.  ARG0
630     is argument 0 from the PHI.  Likewise for ARG1.  */
631 
632 static bool
633 value_replacement (basic_block cond_bb, basic_block middle_bb,
634 		   edge e0, edge e1, gimple phi,
635 		   tree arg0, tree arg1)
636 {
637   gimple_stmt_iterator gsi;
638   gimple cond;
639   edge true_edge, false_edge;
640   enum tree_code code;
641 
642   /* If the type says honor signed zeros we cannot do this
643      optimization.  */
644   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
645     return false;
646 
647   /* Allow a single statement in MIDDLE_BB that defines one of the PHI
648      arguments.  */
649   gsi = gsi_after_labels (middle_bb);
650   if (!gsi_end_p (gsi))
651     {
652       if (is_gimple_debug (gsi_stmt (gsi)))
653 	gsi_next_nondebug (&gsi);
654       if (!gsi_end_p (gsi))
655 	{
656 	  gimple stmt = gsi_stmt (gsi);
657 	  tree lhs;
658 	  gsi_next_nondebug (&gsi);
659 	  if (!gsi_end_p (gsi))
660 	    return false;
661 	  if (!is_gimple_assign (stmt))
662 	    return false;
663 	  /* Now try to adjust arg0 or arg1 according to the computation
664 	     in the single statement.  */
665 	  lhs = gimple_assign_lhs (stmt);
666 	  if (!((lhs == arg0
667 		 && jump_function_from_stmt (&arg0, stmt))
668 		|| (lhs == arg1
669 		    && jump_function_from_stmt (&arg1, stmt))))
670 	    return false;
671 	}
672     }
673 
674   cond = last_stmt (cond_bb);
675   code = gimple_cond_code (cond);
676 
677   /* This transformation is only valid for equality comparisons.  */
678   if (code != NE_EXPR && code != EQ_EXPR)
679     return false;
680 
681   /* We need to know which is the true edge and which is the false
682       edge so that we know if have abs or negative abs.  */
683   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
684 
685   /* At this point we know we have a COND_EXPR with two successors.
686      One successor is BB, the other successor is an empty block which
687      falls through into BB.
688 
689      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
690 
691      There is a single PHI node at the join point (BB) with two arguments.
692 
693      We now need to verify that the two arguments in the PHI node match
694      the two arguments to the equality comparison.  */
695 
696   if ((operand_equal_for_phi_arg_p (arg0, gimple_cond_lhs (cond))
697        && operand_equal_for_phi_arg_p (arg1, gimple_cond_rhs (cond)))
698       || (operand_equal_for_phi_arg_p (arg1, gimple_cond_lhs (cond))
699 	  && operand_equal_for_phi_arg_p (arg0, gimple_cond_rhs (cond))))
700     {
701       edge e;
702       tree arg;
703 
704       /* For NE_EXPR, we want to build an assignment result = arg where
705 	 arg is the PHI argument associated with the true edge.  For
706 	 EQ_EXPR we want the PHI argument associated with the false edge.  */
707       e = (code == NE_EXPR ? true_edge : false_edge);
708 
709       /* Unfortunately, E may not reach BB (it may instead have gone to
710 	 OTHER_BLOCK).  If that is the case, then we want the single outgoing
711 	 edge from OTHER_BLOCK which reaches BB and represents the desired
712 	 path from COND_BLOCK.  */
713       if (e->dest == middle_bb)
714 	e = single_succ_edge (e->dest);
715 
716       /* Now we know the incoming edge to BB that has the argument for the
717 	 RHS of our new assignment statement.  */
718       if (e0 == e)
719 	arg = arg0;
720       else
721 	arg = arg1;
722 
723       replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
724 
725       /* Note that we optimized this PHI.  */
726       return true;
727     }
728   return false;
729 }
730 
731 /*  The function minmax_replacement does the main work of doing the minmax
732     replacement.  Return true if the replacement is done.  Otherwise return
733     false.
734     BB is the basic block where the replacement is going to be done on.  ARG0
735     is argument 0 from the PHI.  Likewise for ARG1.  */
736 
737 static bool
738 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
739 		    edge e0, edge e1, gimple phi,
740 		    tree arg0, tree arg1)
741 {
742   tree result, type;
743   gimple cond, new_stmt;
744   edge true_edge, false_edge;
745   enum tree_code cmp, minmax, ass_code;
746   tree smaller, larger, arg_true, arg_false;
747   gimple_stmt_iterator gsi, gsi_from;
748 
749   type = TREE_TYPE (PHI_RESULT (phi));
750 
751   /* The optimization may be unsafe due to NaNs.  */
752   if (HONOR_NANS (TYPE_MODE (type)))
753     return false;
754 
755   cond = last_stmt (cond_bb);
756   cmp = gimple_cond_code (cond);
757 
758   /* This transformation is only valid for order comparisons.  Record which
759      operand is smaller/larger if the result of the comparison is true.  */
760   if (cmp == LT_EXPR || cmp == LE_EXPR)
761     {
762       smaller = gimple_cond_lhs (cond);
763       larger = gimple_cond_rhs (cond);
764     }
765   else if (cmp == GT_EXPR || cmp == GE_EXPR)
766     {
767       smaller = gimple_cond_rhs (cond);
768       larger = gimple_cond_lhs (cond);
769     }
770   else
771     return false;
772 
773   /* We need to know which is the true edge and which is the false
774       edge so that we know if have abs or negative abs.  */
775   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
776 
777   /* Forward the edges over the middle basic block.  */
778   if (true_edge->dest == middle_bb)
779     true_edge = EDGE_SUCC (true_edge->dest, 0);
780   if (false_edge->dest == middle_bb)
781     false_edge = EDGE_SUCC (false_edge->dest, 0);
782 
783   if (true_edge == e0)
784     {
785       gcc_assert (false_edge == e1);
786       arg_true = arg0;
787       arg_false = arg1;
788     }
789   else
790     {
791       gcc_assert (false_edge == e0);
792       gcc_assert (true_edge == e1);
793       arg_true = arg1;
794       arg_false = arg0;
795     }
796 
797   if (empty_block_p (middle_bb))
798     {
799       if (operand_equal_for_phi_arg_p (arg_true, smaller)
800 	  && operand_equal_for_phi_arg_p (arg_false, larger))
801 	{
802 	  /* Case
803 
804 	     if (smaller < larger)
805 	     rslt = smaller;
806 	     else
807 	     rslt = larger;  */
808 	  minmax = MIN_EXPR;
809 	}
810       else if (operand_equal_for_phi_arg_p (arg_false, smaller)
811 	       && operand_equal_for_phi_arg_p (arg_true, larger))
812 	minmax = MAX_EXPR;
813       else
814 	return false;
815     }
816   else
817     {
818       /* Recognize the following case, assuming d <= u:
819 
820 	 if (a <= u)
821 	   b = MAX (a, d);
822 	 x = PHI <b, u>
823 
824 	 This is equivalent to
825 
826 	 b = MAX (a, d);
827 	 x = MIN (b, u);  */
828 
829       gimple assign = last_and_only_stmt (middle_bb);
830       tree lhs, op0, op1, bound;
831 
832       if (!assign
833 	  || gimple_code (assign) != GIMPLE_ASSIGN)
834 	return false;
835 
836       lhs = gimple_assign_lhs (assign);
837       ass_code = gimple_assign_rhs_code (assign);
838       if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
839 	return false;
840       op0 = gimple_assign_rhs1 (assign);
841       op1 = gimple_assign_rhs2 (assign);
842 
843       if (true_edge->src == middle_bb)
844 	{
845 	  /* We got here if the condition is true, i.e., SMALLER < LARGER.  */
846 	  if (!operand_equal_for_phi_arg_p (lhs, arg_true))
847 	    return false;
848 
849 	  if (operand_equal_for_phi_arg_p (arg_false, larger))
850 	    {
851 	      /* Case
852 
853 		 if (smaller < larger)
854 		   {
855 		     r' = MAX_EXPR (smaller, bound)
856 		   }
857 		 r = PHI <r', larger>  --> to be turned to MIN_EXPR.  */
858 	      if (ass_code != MAX_EXPR)
859 		return false;
860 
861 	      minmax = MIN_EXPR;
862 	      if (operand_equal_for_phi_arg_p (op0, smaller))
863 		bound = op1;
864 	      else if (operand_equal_for_phi_arg_p (op1, smaller))
865 		bound = op0;
866 	      else
867 		return false;
868 
869 	      /* We need BOUND <= LARGER.  */
870 	      if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
871 						  bound, larger)))
872 		return false;
873 	    }
874 	  else if (operand_equal_for_phi_arg_p (arg_false, smaller))
875 	    {
876 	      /* Case
877 
878 		 if (smaller < larger)
879 		   {
880 		     r' = MIN_EXPR (larger, bound)
881 		   }
882 		 r = PHI <r', smaller>  --> to be turned to MAX_EXPR.  */
883 	      if (ass_code != MIN_EXPR)
884 		return false;
885 
886 	      minmax = MAX_EXPR;
887 	      if (operand_equal_for_phi_arg_p (op0, larger))
888 		bound = op1;
889 	      else if (operand_equal_for_phi_arg_p (op1, larger))
890 		bound = op0;
891 	      else
892 		return false;
893 
894 	      /* We need BOUND >= SMALLER.  */
895 	      if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
896 						  bound, smaller)))
897 		return false;
898 	    }
899 	  else
900 	    return false;
901 	}
902       else
903 	{
904 	  /* We got here if the condition is false, i.e., SMALLER > LARGER.  */
905 	  if (!operand_equal_for_phi_arg_p (lhs, arg_false))
906 	    return false;
907 
908 	  if (operand_equal_for_phi_arg_p (arg_true, larger))
909 	    {
910 	      /* Case
911 
912 		 if (smaller > larger)
913 		   {
914 		     r' = MIN_EXPR (smaller, bound)
915 		   }
916 		 r = PHI <r', larger>  --> to be turned to MAX_EXPR.  */
917 	      if (ass_code != MIN_EXPR)
918 		return false;
919 
920 	      minmax = MAX_EXPR;
921 	      if (operand_equal_for_phi_arg_p (op0, smaller))
922 		bound = op1;
923 	      else if (operand_equal_for_phi_arg_p (op1, smaller))
924 		bound = op0;
925 	      else
926 		return false;
927 
928 	      /* We need BOUND >= LARGER.  */
929 	      if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
930 						  bound, larger)))
931 		return false;
932 	    }
933 	  else if (operand_equal_for_phi_arg_p (arg_true, smaller))
934 	    {
935 	      /* Case
936 
937 		 if (smaller > larger)
938 		   {
939 		     r' = MAX_EXPR (larger, bound)
940 		   }
941 		 r = PHI <r', smaller>  --> to be turned to MIN_EXPR.  */
942 	      if (ass_code != MAX_EXPR)
943 		return false;
944 
945 	      minmax = MIN_EXPR;
946 	      if (operand_equal_for_phi_arg_p (op0, larger))
947 		bound = op1;
948 	      else if (operand_equal_for_phi_arg_p (op1, larger))
949 		bound = op0;
950 	      else
951 		return false;
952 
953 	      /* We need BOUND <= SMALLER.  */
954 	      if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
955 						  bound, smaller)))
956 		return false;
957 	    }
958 	  else
959 	    return false;
960 	}
961 
962       /* Move the statement from the middle block.  */
963       gsi = gsi_last_bb (cond_bb);
964       gsi_from = gsi_last_nondebug_bb (middle_bb);
965       gsi_move_before (&gsi_from, &gsi);
966     }
967 
968   /* Emit the statement to compute min/max.  */
969   result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
970   new_stmt = gimple_build_assign_with_ops (minmax, result, arg0, arg1);
971   gsi = gsi_last_bb (cond_bb);
972   gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
973 
974   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
975   return true;
976 }
977 
978 /*  The function absolute_replacement does the main work of doing the absolute
979     replacement.  Return true if the replacement is done.  Otherwise return
980     false.
981     bb is the basic block where the replacement is going to be done on.  arg0
982     is argument 0 from the phi.  Likewise for arg1.  */
983 
984 static bool
985 abs_replacement (basic_block cond_bb, basic_block middle_bb,
986 		 edge e0 ATTRIBUTE_UNUSED, edge e1,
987 		 gimple phi, tree arg0, tree arg1)
988 {
989   tree result;
990   gimple new_stmt, cond;
991   gimple_stmt_iterator gsi;
992   edge true_edge, false_edge;
993   gimple assign;
994   edge e;
995   tree rhs, lhs;
996   bool negate;
997   enum tree_code cond_code;
998 
999   /* If the type says honor signed zeros we cannot do this
1000      optimization.  */
1001   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
1002     return false;
1003 
1004   /* OTHER_BLOCK must have only one executable statement which must have the
1005      form arg0 = -arg1 or arg1 = -arg0.  */
1006 
1007   assign = last_and_only_stmt (middle_bb);
1008   /* If we did not find the proper negation assignment, then we can not
1009      optimize.  */
1010   if (assign == NULL)
1011     return false;
1012 
1013   /* If we got here, then we have found the only executable statement
1014      in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
1015      arg1 = -arg0, then we can not optimize.  */
1016   if (gimple_code (assign) != GIMPLE_ASSIGN)
1017     return false;
1018 
1019   lhs = gimple_assign_lhs (assign);
1020 
1021   if (gimple_assign_rhs_code (assign) != NEGATE_EXPR)
1022     return false;
1023 
1024   rhs = gimple_assign_rhs1 (assign);
1025 
1026   /* The assignment has to be arg0 = -arg1 or arg1 = -arg0.  */
1027   if (!(lhs == arg0 && rhs == arg1)
1028       && !(lhs == arg1 && rhs == arg0))
1029     return false;
1030 
1031   cond = last_stmt (cond_bb);
1032   result = PHI_RESULT (phi);
1033 
1034   /* Only relationals comparing arg[01] against zero are interesting.  */
1035   cond_code = gimple_cond_code (cond);
1036   if (cond_code != GT_EXPR && cond_code != GE_EXPR
1037       && cond_code != LT_EXPR && cond_code != LE_EXPR)
1038     return false;
1039 
1040   /* Make sure the conditional is arg[01] OP y.  */
1041   if (gimple_cond_lhs (cond) != rhs)
1042     return false;
1043 
1044   if (FLOAT_TYPE_P (TREE_TYPE (gimple_cond_rhs (cond)))
1045 	       ? real_zerop (gimple_cond_rhs (cond))
1046 	       : integer_zerop (gimple_cond_rhs (cond)))
1047     ;
1048   else
1049     return false;
1050 
1051   /* We need to know which is the true edge and which is the false
1052      edge so that we know if have abs or negative abs.  */
1053   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
1054 
1055   /* For GT_EXPR/GE_EXPR, if the true edge goes to OTHER_BLOCK, then we
1056      will need to negate the result.  Similarly for LT_EXPR/LE_EXPR if
1057      the false edge goes to OTHER_BLOCK.  */
1058   if (cond_code == GT_EXPR || cond_code == GE_EXPR)
1059     e = true_edge;
1060   else
1061     e = false_edge;
1062 
1063   if (e->dest == middle_bb)
1064     negate = true;
1065   else
1066     negate = false;
1067 
1068   result = duplicate_ssa_name (result, NULL);
1069 
1070   if (negate)
1071     {
1072       tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
1073       add_referenced_var (tmp);
1074       lhs = make_ssa_name (tmp, NULL);
1075     }
1076   else
1077     lhs = result;
1078 
1079   /* Build the modify expression with abs expression.  */
1080   new_stmt = gimple_build_assign_with_ops (ABS_EXPR, lhs, rhs, NULL);
1081 
1082   gsi = gsi_last_bb (cond_bb);
1083   gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1084 
1085   if (negate)
1086     {
1087       /* Get the right GSI.  We want to insert after the recently
1088 	 added ABS_EXPR statement (which we know is the first statement
1089 	 in the block.  */
1090       new_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, result, lhs, NULL);
1091 
1092       gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1093     }
1094 
1095   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
1096 
1097   /* Note that we optimized this PHI.  */
1098   return true;
1099 }
1100 
1101 /* Auxiliary functions to determine the set of memory accesses which
1102    can't trap because they are preceded by accesses to the same memory
1103    portion.  We do that for MEM_REFs, so we only need to track
1104    the SSA_NAME of the pointer indirectly referenced.  The algorithm
1105    simply is a walk over all instructions in dominator order.  When
1106    we see an MEM_REF we determine if we've already seen a same
1107    ref anywhere up to the root of the dominator tree.  If we do the
1108    current access can't trap.  If we don't see any dominating access
1109    the current access might trap, but might also make later accesses
1110    non-trapping, so we remember it.  We need to be careful with loads
1111    or stores, for instance a load might not trap, while a store would,
1112    so if we see a dominating read access this doesn't mean that a later
1113    write access would not trap.  Hence we also need to differentiate the
1114    type of access(es) seen.
1115 
1116    ??? We currently are very conservative and assume that a load might
1117    trap even if a store doesn't (write-only memory).  This probably is
1118    overly conservative.  */
1119 
1120 /* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF
1121    through it was seen, which would constitute a no-trap region for
1122    same accesses.  */
1123 struct name_to_bb
1124 {
1125   unsigned int ssa_name_ver;
1126   bool store;
1127   HOST_WIDE_INT offset, size;
1128   basic_block bb;
1129 };
1130 
1131 /* The hash table for remembering what we've seen.  */
1132 static htab_t seen_ssa_names;
1133 
1134 /* The set of MEM_REFs which can't trap.  */
1135 static struct pointer_set_t *nontrap_set;
1136 
1137 /* The hash function.  */
1138 static hashval_t
1139 name_to_bb_hash (const void *p)
1140 {
1141   const struct name_to_bb *n = (const struct name_to_bb *) p;
1142   return n->ssa_name_ver ^ (((hashval_t) n->store) << 31)
1143          ^ (n->offset << 6) ^ (n->size << 3);
1144 }
1145 
1146 /* The equality function of *P1 and *P2.  */
1147 static int
1148 name_to_bb_eq (const void *p1, const void *p2)
1149 {
1150   const struct name_to_bb *n1 = (const struct name_to_bb *)p1;
1151   const struct name_to_bb *n2 = (const struct name_to_bb *)p2;
1152 
1153   return n1->ssa_name_ver == n2->ssa_name_ver
1154          && n1->store == n2->store
1155          && n1->offset == n2->offset
1156          && n1->size == n2->size;
1157 }
1158 
1159 /* We see the expression EXP in basic block BB.  If it's an interesting
1160    expression (an MEM_REF through an SSA_NAME) possibly insert the
1161    expression into the set NONTRAP or the hash table of seen expressions.
1162    STORE is true if this expression is on the LHS, otherwise it's on
1163    the RHS.  */
1164 static void
1165 add_or_mark_expr (basic_block bb, tree exp,
1166 		  struct pointer_set_t *nontrap, bool store)
1167 {
1168   HOST_WIDE_INT size;
1169 
1170   if (TREE_CODE (exp) == MEM_REF
1171       && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME
1172       && host_integerp (TREE_OPERAND (exp, 1), 0)
1173       && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
1174     {
1175       tree name = TREE_OPERAND (exp, 0);
1176       struct name_to_bb map;
1177       void **slot;
1178       struct name_to_bb *n2bb;
1179       basic_block found_bb = 0;
1180 
1181       /* Try to find the last seen MEM_REF through the same
1182          SSA_NAME, which can trap.  */
1183       map.ssa_name_ver = SSA_NAME_VERSION (name);
1184       map.bb = 0;
1185       map.store = store;
1186       map.offset = tree_low_cst (TREE_OPERAND (exp, 1), 0);
1187       map.size = size;
1188 
1189       slot = htab_find_slot (seen_ssa_names, &map, INSERT);
1190       n2bb = (struct name_to_bb *) *slot;
1191       if (n2bb)
1192         found_bb = n2bb->bb;
1193 
1194       /* If we've found a trapping MEM_REF, _and_ it dominates EXP
1195          (it's in a basic block on the path from us to the dominator root)
1196 	 then we can't trap.  */
1197       if (found_bb && found_bb->aux == (void *)1)
1198 	{
1199 	  pointer_set_insert (nontrap, exp);
1200 	}
1201       else
1202         {
1203 	  /* EXP might trap, so insert it into the hash table.  */
1204 	  if (n2bb)
1205 	    {
1206 	      n2bb->bb = bb;
1207 	    }
1208 	  else
1209 	    {
1210 	      n2bb = XNEW (struct name_to_bb);
1211 	      n2bb->ssa_name_ver = SSA_NAME_VERSION (name);
1212 	      n2bb->bb = bb;
1213 	      n2bb->store = store;
1214 	      n2bb->offset = map.offset;
1215 	      n2bb->size = size;
1216 	      *slot = n2bb;
1217 	    }
1218 	}
1219     }
1220 }
1221 
1222 /* Called by walk_dominator_tree, when entering the block BB.  */
1223 static void
1224 nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1225 {
1226   gimple_stmt_iterator gsi;
1227   /* Mark this BB as being on the path to dominator root.  */
1228   bb->aux = (void*)1;
1229 
1230   /* And walk the statements in order.  */
1231   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1232     {
1233       gimple stmt = gsi_stmt (gsi);
1234 
1235       if (gimple_assign_single_p (stmt))
1236 	{
1237 	  add_or_mark_expr (bb, gimple_assign_lhs (stmt), nontrap_set, true);
1238 	  add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), nontrap_set, false);
1239 	}
1240     }
1241 }
1242 
1243 /* Called by walk_dominator_tree, when basic block BB is exited.  */
1244 static void
1245 nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
1246 {
1247   /* This BB isn't on the path to dominator root anymore.  */
1248   bb->aux = NULL;
1249 }
1250 
1251 /* This is the entry point of gathering non trapping memory accesses.
1252    It will do a dominator walk over the whole function, and it will
1253    make use of the bb->aux pointers.  It returns a set of trees
1254    (the MEM_REFs itself) which can't trap.  */
1255 static struct pointer_set_t *
1256 get_non_trapping (void)
1257 {
1258   struct pointer_set_t *nontrap;
1259   struct dom_walk_data walk_data;
1260 
1261   nontrap = pointer_set_create ();
1262   seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq,
1263 				free);
1264   /* We're going to do a dominator walk, so ensure that we have
1265      dominance information.  */
1266   calculate_dominance_info (CDI_DOMINATORS);
1267 
1268   /* Setup callbacks for the generic dominator tree walker.  */
1269   nontrap_set = nontrap;
1270   walk_data.dom_direction = CDI_DOMINATORS;
1271   walk_data.initialize_block_local_data = NULL;
1272   walk_data.before_dom_children = nt_init_block;
1273   walk_data.after_dom_children = nt_fini_block;
1274   walk_data.global_data = NULL;
1275   walk_data.block_local_data_size = 0;
1276 
1277   init_walk_dominator_tree (&walk_data);
1278   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1279   fini_walk_dominator_tree (&walk_data);
1280   htab_delete (seen_ssa_names);
1281 
1282   return nontrap;
1283 }
1284 
1285 /* Do the main work of conditional store replacement.  We already know
1286    that the recognized pattern looks like so:
1287 
1288    split:
1289      if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
1290    MIDDLE_BB:
1291      something
1292      fallthrough (edge E0)
1293    JOIN_BB:
1294      some more
1295 
1296    We check that MIDDLE_BB contains only one store, that that store
1297    doesn't trap (not via NOTRAP, but via checking if an access to the same
1298    memory location dominates us) and that the store has a "simple" RHS.  */
1299 
1300 static bool
1301 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
1302 			edge e0, edge e1, struct pointer_set_t *nontrap)
1303 {
1304   gimple assign = last_and_only_stmt (middle_bb);
1305   tree lhs, rhs, name;
1306   gimple newphi, new_stmt;
1307   gimple_stmt_iterator gsi;
1308   source_location locus;
1309 
1310   /* Check if middle_bb contains of only one store.  */
1311   if (!assign
1312       || !gimple_assign_single_p (assign))
1313     return false;
1314 
1315   locus = gimple_location (assign);
1316   lhs = gimple_assign_lhs (assign);
1317   rhs = gimple_assign_rhs1 (assign);
1318   if (TREE_CODE (lhs) != MEM_REF
1319       || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME
1320       || !is_gimple_reg_type (TREE_TYPE (lhs)))
1321     return false;
1322 
1323   /* Prove that we can move the store down.  We could also check
1324      TREE_THIS_NOTRAP here, but in that case we also could move stores,
1325      whose value is not available readily, which we want to avoid.  */
1326   if (!pointer_set_contains (nontrap, lhs))
1327     return false;
1328 
1329   /* Now we've checked the constraints, so do the transformation:
1330      1) Remove the single store.  */
1331   gsi = gsi_for_stmt (assign);
1332   unlink_stmt_vdef (assign);
1333   gsi_remove (&gsi, true);
1334   release_defs (assign);
1335 
1336   /* 2) Create a temporary where we can store the old content
1337         of the memory touched by the store, if we need to.  */
1338   if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1339     condstoretemp = create_tmp_reg (TREE_TYPE (lhs), "cstore");
1340   add_referenced_var (condstoretemp);
1341 
1342   /* 3) Insert a load from the memory of the store to the temporary
1343         on the edge which did not contain the store.  */
1344   lhs = unshare_expr (lhs);
1345   new_stmt = gimple_build_assign (condstoretemp, lhs);
1346   name = make_ssa_name (condstoretemp, new_stmt);
1347   gimple_assign_set_lhs (new_stmt, name);
1348   gimple_set_location (new_stmt, locus);
1349   gsi_insert_on_edge (e1, new_stmt);
1350 
1351   /* 4) Create a PHI node at the join block, with one argument
1352         holding the old RHS, and the other holding the temporary
1353         where we stored the old memory contents.  */
1354   newphi = create_phi_node (condstoretemp, join_bb);
1355   add_phi_arg (newphi, rhs, e0, locus);
1356   add_phi_arg (newphi, name, e1, locus);
1357 
1358   lhs = unshare_expr (lhs);
1359   new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1360 
1361   /* 5) Insert that PHI node.  */
1362   gsi = gsi_after_labels (join_bb);
1363   if (gsi_end_p (gsi))
1364     {
1365       gsi = gsi_last_bb (join_bb);
1366       gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1367     }
1368   else
1369     gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1370 
1371   return true;
1372 }
1373 
1374 /* Do the main work of conditional store replacement.  */
1375 
1376 static bool
1377 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
1378 				  basic_block join_bb, gimple then_assign,
1379 				  gimple else_assign)
1380 {
1381   tree lhs_base, lhs, then_rhs, else_rhs;
1382   source_location then_locus, else_locus;
1383   gimple_stmt_iterator gsi;
1384   gimple newphi, new_stmt;
1385 
1386   if (then_assign == NULL
1387       || !gimple_assign_single_p (then_assign)
1388       || gimple_clobber_p (then_assign)
1389       || else_assign == NULL
1390       || !gimple_assign_single_p (else_assign)
1391       || gimple_clobber_p (else_assign))
1392     return false;
1393 
1394   lhs = gimple_assign_lhs (then_assign);
1395   if (!is_gimple_reg_type (TREE_TYPE (lhs))
1396       || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
1397     return false;
1398 
1399   lhs_base = get_base_address (lhs);
1400   if (lhs_base == NULL_TREE
1401       || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
1402     return false;
1403 
1404   then_rhs = gimple_assign_rhs1 (then_assign);
1405   else_rhs = gimple_assign_rhs1 (else_assign);
1406   then_locus = gimple_location (then_assign);
1407   else_locus = gimple_location (else_assign);
1408 
1409   /* Now we've checked the constraints, so do the transformation:
1410      1) Remove the stores.  */
1411   gsi = gsi_for_stmt (then_assign);
1412   unlink_stmt_vdef (then_assign);
1413   gsi_remove (&gsi, true);
1414   release_defs (then_assign);
1415 
1416   gsi = gsi_for_stmt (else_assign);
1417   unlink_stmt_vdef (else_assign);
1418   gsi_remove (&gsi, true);
1419   release_defs (else_assign);
1420 
1421   /* 2) Create a temporary where we can store the old content
1422 	of the memory touched by the store, if we need to.  */
1423   if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1424     condstoretemp = create_tmp_reg (TREE_TYPE (lhs), "cstore");
1425   add_referenced_var (condstoretemp);
1426 
1427   /* 3) Create a PHI node at the join block, with one argument
1428 	holding the old RHS, and the other holding the temporary
1429 	where we stored the old memory contents.  */
1430   newphi = create_phi_node (condstoretemp, join_bb);
1431   add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
1432   add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
1433 
1434   new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1435 
1436   /* 4) Insert that PHI node.  */
1437   gsi = gsi_after_labels (join_bb);
1438   if (gsi_end_p (gsi))
1439     {
1440       gsi = gsi_last_bb (join_bb);
1441       gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1442     }
1443   else
1444     gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1445 
1446   return true;
1447 }
1448 
1449 /* Conditional store replacement.  We already know
1450    that the recognized pattern looks like so:
1451 
1452    split:
1453      if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
1454    THEN_BB:
1455      ...
1456      X = Y;
1457      ...
1458      goto JOIN_BB;
1459    ELSE_BB:
1460      ...
1461      X = Z;
1462      ...
1463      fallthrough (edge E0)
1464    JOIN_BB:
1465      some more
1466 
1467    We check that it is safe to sink the store to JOIN_BB by verifying that
1468    there are no read-after-write or write-after-write dependencies in
1469    THEN_BB and ELSE_BB.  */
1470 
1471 static bool
1472 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
1473                                 basic_block join_bb)
1474 {
1475   gimple then_assign = last_and_only_stmt (then_bb);
1476   gimple else_assign = last_and_only_stmt (else_bb);
1477   VEC (data_reference_p, heap) *then_datarefs, *else_datarefs;
1478   VEC (ddr_p, heap) *then_ddrs, *else_ddrs;
1479   gimple then_store, else_store;
1480   bool found, ok = false, res;
1481   struct data_dependence_relation *ddr;
1482   data_reference_p then_dr, else_dr;
1483   int i, j;
1484   tree then_lhs, else_lhs;
1485   VEC (gimple, heap) *then_stores, *else_stores;
1486   basic_block blocks[3];
1487 
1488   if (MAX_STORES_TO_SINK == 0)
1489     return false;
1490 
1491   /* Handle the case with single statement in THEN_BB and ELSE_BB.  */
1492   if (then_assign && else_assign)
1493     return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
1494                                              then_assign, else_assign);
1495 
1496   /* Find data references.  */
1497   then_datarefs = VEC_alloc (data_reference_p, heap, 1);
1498   else_datarefs = VEC_alloc (data_reference_p, heap, 1);
1499   if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
1500         == chrec_dont_know)
1501       || !VEC_length (data_reference_p, then_datarefs)
1502       || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
1503         == chrec_dont_know)
1504       || !VEC_length (data_reference_p, else_datarefs))
1505     {
1506       free_data_refs (then_datarefs);
1507       free_data_refs (else_datarefs);
1508       return false;
1509     }
1510 
1511   /* Find pairs of stores with equal LHS.  */
1512   then_stores = VEC_alloc (gimple, heap, 1);
1513   else_stores = VEC_alloc (gimple, heap, 1);
1514   FOR_EACH_VEC_ELT (data_reference_p, then_datarefs, i, then_dr)
1515     {
1516       if (DR_IS_READ (then_dr))
1517         continue;
1518 
1519       then_store = DR_STMT (then_dr);
1520       then_lhs = gimple_get_lhs (then_store);
1521       found = false;
1522 
1523       FOR_EACH_VEC_ELT (data_reference_p, else_datarefs, j, else_dr)
1524         {
1525           if (DR_IS_READ (else_dr))
1526             continue;
1527 
1528           else_store = DR_STMT (else_dr);
1529           else_lhs = gimple_get_lhs (else_store);
1530 
1531           if (operand_equal_p (then_lhs, else_lhs, 0))
1532             {
1533               found = true;
1534               break;
1535             }
1536         }
1537 
1538       if (!found)
1539         continue;
1540 
1541       VEC_safe_push (gimple, heap, then_stores, then_store);
1542       VEC_safe_push (gimple, heap, else_stores, else_store);
1543     }
1544 
1545   /* No pairs of stores found.  */
1546   if (!VEC_length (gimple, then_stores)
1547       || VEC_length (gimple, then_stores) > (unsigned) MAX_STORES_TO_SINK)
1548     {
1549       free_data_refs (then_datarefs);
1550       free_data_refs (else_datarefs);
1551       VEC_free (gimple, heap, then_stores);
1552       VEC_free (gimple, heap, else_stores);
1553       return false;
1554     }
1555 
1556   /* Compute and check data dependencies in both basic blocks.  */
1557   then_ddrs = VEC_alloc (ddr_p, heap, 1);
1558   else_ddrs = VEC_alloc (ddr_p, heap, 1);
1559   if (!compute_all_dependences (then_datarefs, &then_ddrs, NULL, false)
1560       || !compute_all_dependences (else_datarefs, &else_ddrs, NULL, false))
1561     {
1562       free_dependence_relations (then_ddrs);
1563       free_dependence_relations (else_ddrs);
1564       free_data_refs (then_datarefs);
1565       free_data_refs (else_datarefs);
1566       VEC_free (gimple, heap, then_stores);
1567       VEC_free (gimple, heap, else_stores);
1568       return false;
1569     }
1570   blocks[0] = then_bb;
1571   blocks[1] = else_bb;
1572   blocks[2] = join_bb;
1573   renumber_gimple_stmt_uids_in_blocks (blocks, 3);
1574 
1575   /* Check that there are no read-after-write or write-after-write dependencies
1576      in THEN_BB.  */
1577   FOR_EACH_VEC_ELT (ddr_p, then_ddrs, i, ddr)
1578     {
1579       struct data_reference *dra = DDR_A (ddr);
1580       struct data_reference *drb = DDR_B (ddr);
1581 
1582       if (DDR_ARE_DEPENDENT (ddr) != chrec_known
1583           && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
1584                && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
1585               || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
1586                   && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
1587               || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
1588         {
1589           free_dependence_relations (then_ddrs);
1590           free_dependence_relations (else_ddrs);
1591 	  free_data_refs (then_datarefs);
1592 	  free_data_refs (else_datarefs);
1593           VEC_free (gimple, heap, then_stores);
1594           VEC_free (gimple, heap, else_stores);
1595           return false;
1596         }
1597     }
1598 
1599   /* Check that there are no read-after-write or write-after-write dependencies
1600      in ELSE_BB.  */
1601   FOR_EACH_VEC_ELT (ddr_p, else_ddrs, i, ddr)
1602     {
1603       struct data_reference *dra = DDR_A (ddr);
1604       struct data_reference *drb = DDR_B (ddr);
1605 
1606       if (DDR_ARE_DEPENDENT (ddr) != chrec_known
1607           && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
1608                && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
1609               || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
1610                   && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
1611               || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
1612         {
1613           free_dependence_relations (then_ddrs);
1614           free_dependence_relations (else_ddrs);
1615 	  free_data_refs (then_datarefs);
1616 	  free_data_refs (else_datarefs);
1617           VEC_free (gimple, heap, then_stores);
1618           VEC_free (gimple, heap, else_stores);
1619           return false;
1620         }
1621     }
1622 
1623   /* Sink stores with same LHS.  */
1624   FOR_EACH_VEC_ELT (gimple, then_stores, i, then_store)
1625     {
1626       else_store = VEC_index (gimple, else_stores, i);
1627       res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
1628                                               then_store, else_store);
1629       ok = ok || res;
1630     }
1631 
1632   free_dependence_relations (then_ddrs);
1633   free_dependence_relations (else_ddrs);
1634   free_data_refs (then_datarefs);
1635   free_data_refs (else_datarefs);
1636   VEC_free (gimple, heap, then_stores);
1637   VEC_free (gimple, heap, else_stores);
1638 
1639   return ok;
1640 }
1641 
1642 /* Always do these optimizations if we have SSA
1643    trees to work on.  */
1644 static bool
1645 gate_phiopt (void)
1646 {
1647   return 1;
1648 }
1649 
1650 struct gimple_opt_pass pass_phiopt =
1651 {
1652  {
1653   GIMPLE_PASS,
1654   "phiopt",				/* name */
1655   gate_phiopt,				/* gate */
1656   tree_ssa_phiopt,			/* execute */
1657   NULL,					/* sub */
1658   NULL,					/* next */
1659   0,					/* static_pass_number */
1660   TV_TREE_PHIOPT,			/* tv_id */
1661   PROP_cfg | PROP_ssa,			/* properties_required */
1662   0,					/* properties_provided */
1663   0,					/* properties_destroyed */
1664   0,					/* todo_flags_start */
1665   TODO_ggc_collect
1666     | TODO_verify_ssa
1667     | TODO_verify_flow
1668     | TODO_verify_stmts	 		/* todo_flags_finish */
1669  }
1670 };
1671 
1672 static bool
1673 gate_cselim (void)
1674 {
1675   return flag_tree_cselim;
1676 }
1677 
1678 struct gimple_opt_pass pass_cselim =
1679 {
1680  {
1681   GIMPLE_PASS,
1682   "cselim",				/* name */
1683   gate_cselim,				/* gate */
1684   tree_ssa_cs_elim,			/* execute */
1685   NULL,					/* sub */
1686   NULL,					/* next */
1687   0,					/* static_pass_number */
1688   TV_TREE_PHIOPT,			/* tv_id */
1689   PROP_cfg | PROP_ssa,			/* properties_required */
1690   0,					/* properties_provided */
1691   0,					/* properties_destroyed */
1692   0,					/* todo_flags_start */
1693   TODO_ggc_collect
1694     | TODO_verify_ssa
1695     | TODO_verify_flow
1696     | TODO_verify_stmts	 		/* todo_flags_finish */
1697  }
1698 };
1699