tree-ssa-dom.c (cprop_into_successor_phis): Remove an obsolete comment.
[gcc.git] / gcc / tree-ssa-dom.c
1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "flags.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "ggc.h"
31 #include "basic-block.h"
32 #include "cfgloop.h"
33 #include "output.h"
34 #include "errors.h"
35 #include "expr.h"
36 #include "function.h"
37 #include "diagnostic.h"
38 #include "timevar.h"
39 #include "tree-dump.h"
40 #include "tree-flow.h"
41 #include "domwalk.h"
42 #include "real.h"
43 #include "tree-pass.h"
44 #include "tree-ssa-propagate.h"
45 #include "langhooks.h"
46
47 /* This file implements optimizations on the dominator tree. */
48
49
50 /* Structure for recording edge equivalences as well as any pending
51 edge redirections during the dominator optimizer.
52
53 Computing and storing the edge equivalences instead of creating
54 them on-demand can save significant amounts of time, particularly
55 for pathological cases involving switch statements.
56
57 These structures live for a single iteration of the dominator
58 optimizer in the edge's AUX field. At the end of an iteration we
59 free each of these structures and update the AUX field to point
60 to any requested redirection target (the code for updating the
61 CFG and SSA graph for edge redirection expects redirection edge
62 targets to be in the AUX field for each edge. */
63
64 struct edge_info
65 {
66 /* If this edge creates a simple equivalence, the LHS and RHS of
67 the equivalence will be stored here. */
68 tree lhs;
69 tree rhs;
70
71 /* Traversing an edge may also indicate one or more particular conditions
72 are true or false. The number of recorded conditions can vary, but
73 can be determined by the condition's code. So we have an array
74 and its maximum index rather than use a varray. */
75 tree *cond_equivalences;
76 unsigned int max_cond_equivalences;
77
78 /* If we can thread this edge this field records the new target. */
79 edge redirection_target;
80 };
81
82
83 /* Hash table with expressions made available during the renaming process.
84 When an assignment of the form X_i = EXPR is found, the statement is
85 stored in this table. If the same expression EXPR is later found on the
86 RHS of another statement, it is replaced with X_i (thus performing
87 global redundancy elimination). Similarly as we pass through conditionals
88 we record the conditional itself as having either a true or false value
89 in this table. */
90 static htab_t avail_exprs;
91
92 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
93 expressions it enters into the hash table along with a marker entry
94 (null). When we finish processing the block, we pop off entries and
95 remove the expressions from the global hash table until we hit the
96 marker. */
97 static VEC(tree_on_heap) *avail_exprs_stack;
98
99 /* Stack of trees used to restore the global currdefs to its original
100 state after completing optimization of a block and its dominator children.
101
102 An SSA_NAME indicates that the current definition of the underlying
103 variable should be set to the given SSA_NAME.
104
105 A _DECL node indicates that the underlying variable has no current
106 definition.
107
108 A NULL node is used to mark the last node associated with the
109 current block. */
110 static VEC(tree_on_heap) *block_defs_stack;
111
112 /* Stack of statements we need to rescan during finalization for newly
113 exposed variables.
114
115 Statement rescanning must occur after the current block's available
116 expressions are removed from AVAIL_EXPRS. Else we may change the
117 hash code for an expression and be unable to find/remove it from
118 AVAIL_EXPRS. */
119 static VEC(tree_on_heap) *stmts_to_rescan;
120
121 /* Structure for entries in the expression hash table.
122
123 This requires more memory for the hash table entries, but allows us
124 to avoid creating silly tree nodes and annotations for conditionals,
125 eliminates 2 global hash tables and two block local varrays.
126
127 It also allows us to reduce the number of hash table lookups we
128 have to perform in lookup_avail_expr and finally it allows us to
129 significantly reduce the number of calls into the hashing routine
130 itself. */
131
132 struct expr_hash_elt
133 {
134 /* The value (lhs) of this expression. */
135 tree lhs;
136
137 /* The expression (rhs) we want to record. */
138 tree rhs;
139
140 /* The annotation if this element corresponds to a statement. */
141 stmt_ann_t ann;
142
143 /* The hash value for RHS/ann. */
144 hashval_t hash;
145 };
146
147 /* Stack of dest,src pairs that need to be restored during finalization.
148
149 A NULL entry is used to mark the end of pairs which need to be
150 restored during finalization of this block. */
151 static VEC(tree_on_heap) *const_and_copies_stack;
152
153 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
154 know their exact value. */
155 static bitmap nonzero_vars;
156
157 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
158 when the current block is finalized.
159
160 A NULL entry is used to mark the end of names needing their
161 entry in NONZERO_VARS cleared during finalization of this block. */
162 static VEC(tree_on_heap) *nonzero_vars_stack;
163
164 /* Track whether or not we have changed the control flow graph. */
165 static bool cfg_altered;
166
167 /* Bitmap of blocks that have had EH statements cleaned. We should
168 remove their dead edges eventually. */
169 static bitmap need_eh_cleanup;
170
171 /* Statistics for dominator optimizations. */
172 struct opt_stats_d
173 {
174 long num_stmts;
175 long num_exprs_considered;
176 long num_re;
177 };
178
179 static struct opt_stats_d opt_stats;
180
181 /* Value range propagation record. Each time we encounter a conditional
182 of the form SSA_NAME COND CONST we create a new vrp_element to record
183 how the condition affects the possible values SSA_NAME may have.
184
185 Each record contains the condition tested (COND), and the range of
186 values the variable may legitimately have if COND is true. Note the
187 range of values may be a smaller range than COND specifies if we have
188 recorded other ranges for this variable. Each record also contains the
189 block in which the range was recorded for invalidation purposes.
190
191 Note that the current known range is computed lazily. This allows us
192 to avoid the overhead of computing ranges which are never queried.
193
194 When we encounter a conditional, we look for records which constrain
195 the SSA_NAME used in the condition. In some cases those records allow
196 us to determine the condition's result at compile time. In other cases
197 they may allow us to simplify the condition.
198
199 We also use value ranges to do things like transform signed div/mod
200 operations into unsigned div/mod or to simplify ABS_EXPRs.
201
202 Simple experiments have shown these optimizations to not be all that
203 useful on switch statements (much to my surprise). So switch statement
204 optimizations are not performed.
205
206 Note carefully we do not propagate information through each statement
207 in the block. i.e., if we know variable X has a value defined of
208 [0, 25] and we encounter Y = X + 1, we do not track a value range
209 for Y (which would be [1, 26] if we cared). Similarly we do not
210 constrain values as we encounter narrowing typecasts, etc. */
211
212 struct vrp_element
213 {
214 /* The highest and lowest values the variable in COND may contain when
215 COND is true. Note this may not necessarily be the same values
216 tested by COND if the same variable was used in earlier conditionals.
217
218 Note this is computed lazily and thus can be NULL indicating that
219 the values have not been computed yet. */
220 tree low;
221 tree high;
222
223 /* The actual conditional we recorded. This is needed since we compute
224 ranges lazily. */
225 tree cond;
226
227 /* The basic block where this record was created. We use this to determine
228 when to remove records. */
229 basic_block bb;
230 };
231
232 /* A hash table holding value range records (VRP_ELEMENTs) for a given
233 SSA_NAME. We used to use a varray indexed by SSA_NAME_VERSION, but
234 that gets awful wasteful, particularly since the density objects
235 with useful information is very low. */
236 static htab_t vrp_data;
237
238 /* An entry in the VRP_DATA hash table. We record the variable and a
239 varray of VRP_ELEMENT records associated with that variable. */
240 struct vrp_hash_elt
241 {
242 tree var;
243 varray_type records;
244 };
245
246 /* Array of variables which have their values constrained by operations
247 in this basic block. We use this during finalization to know
248 which variables need their VRP data updated. */
249
250 /* Stack of SSA_NAMEs which had their values constrained by operations
251 in this basic block. During finalization of this block we use this
252 list to determine which variables need their VRP data updated.
253
254 A NULL entry marks the end of the SSA_NAMEs associated with this block. */
255 static VEC(tree_on_heap) *vrp_variables_stack;
256
257 struct eq_expr_value
258 {
259 tree src;
260 tree dst;
261 };
262
263 /* Local functions. */
264 static void optimize_stmt (struct dom_walk_data *,
265 basic_block bb,
266 block_stmt_iterator);
267 static tree lookup_avail_expr (tree, bool);
268 static hashval_t vrp_hash (const void *);
269 static int vrp_eq (const void *, const void *);
270 static hashval_t avail_expr_hash (const void *);
271 static hashval_t real_avail_expr_hash (const void *);
272 static int avail_expr_eq (const void *, const void *);
273 static void htab_statistics (FILE *, htab_t);
274 static void record_cond (tree, tree);
275 static void record_const_or_copy (tree, tree);
276 static void record_equality (tree, tree);
277 static tree update_rhs_and_lookup_avail_expr (tree, tree, bool);
278 static tree simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *,
279 tree, int);
280 static tree simplify_cond_and_lookup_avail_expr (tree, stmt_ann_t, int);
281 static tree simplify_switch_and_lookup_avail_expr (tree, int);
282 static tree find_equivalent_equality_comparison (tree);
283 static void record_range (tree, basic_block);
284 static bool extract_range_from_cond (tree, tree *, tree *, int *);
285 static void record_equivalences_from_phis (basic_block);
286 static void record_equivalences_from_incoming_edge (basic_block);
287 static bool eliminate_redundant_computations (struct dom_walk_data *,
288 tree, stmt_ann_t);
289 static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
290 static void thread_across_edge (struct dom_walk_data *, edge);
291 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
292 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
293 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
294 static void remove_local_expressions_from_table (void);
295 static void restore_vars_to_original_value (void);
296 static void restore_currdefs_to_original_value (void);
297 static void register_definitions_for_stmt (tree);
298 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
299 static void restore_nonzero_vars_to_original_value (void);
300 static inline bool unsafe_associative_fp_binop (tree);
301
302 /* Local version of fold that doesn't introduce cruft. */
303
304 static tree
305 local_fold (tree t)
306 {
307 t = fold (t);
308
309 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
310 may have been added by fold, and "useless" type conversions that might
311 now be apparent due to propagation. */
312 STRIP_USELESS_TYPE_CONVERSION (t);
313
314 return t;
315 }
316
317 /* Allocate an EDGE_INFO for edge E and attach it to E.
318 Return the new EDGE_INFO structure. */
319
320 static struct edge_info *
321 allocate_edge_info (edge e)
322 {
323 struct edge_info *edge_info;
324
325 edge_info = xcalloc (1, sizeof (struct edge_info));
326
327 e->aux = edge_info;
328 return edge_info;
329 }
330
331 /* Free all EDGE_INFO structures associated with edges in the CFG.
332 If a particular edge can be threaded, copy the redirection
333 target from the EDGE_INFO structure into the edge's AUX field
334 as required by code to update the CFG and SSA graph for
335 jump threading. */
336
337 static void
338 free_all_edge_infos (void)
339 {
340 basic_block bb;
341 edge_iterator ei;
342 edge e;
343
344 FOR_EACH_BB (bb)
345 {
346 FOR_EACH_EDGE (e, ei, bb->preds)
347 {
348 struct edge_info *edge_info = e->aux;
349
350 if (edge_info)
351 {
352 e->aux = edge_info->redirection_target;
353 if (edge_info->cond_equivalences)
354 free (edge_info->cond_equivalences);
355 free (edge_info);
356 }
357 }
358 }
359 }
360
361 /* Jump threading, redundancy elimination and const/copy propagation.
362
363 This pass may expose new symbols that need to be renamed into SSA. For
364 every new symbol exposed, its corresponding bit will be set in
365 VARS_TO_RENAME. */
366
367 static void
368 tree_ssa_dominator_optimize (void)
369 {
370 struct dom_walk_data walk_data;
371 unsigned int i;
372 struct loops loops_info;
373
374 memset (&opt_stats, 0, sizeof (opt_stats));
375
376 for (i = 0; i < num_referenced_vars; i++)
377 var_ann (referenced_var (i))->current_def = NULL;
378
379 /* Create our hash tables. */
380 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
381 vrp_data = htab_create (ceil_log2 (num_ssa_names), vrp_hash, vrp_eq, free);
382 avail_exprs_stack = VEC_alloc (tree_on_heap, 20);
383 block_defs_stack = VEC_alloc (tree_on_heap, 20);
384 const_and_copies_stack = VEC_alloc (tree_on_heap, 20);
385 nonzero_vars_stack = VEC_alloc (tree_on_heap, 20);
386 vrp_variables_stack = VEC_alloc (tree_on_heap, 20);
387 stmts_to_rescan = VEC_alloc (tree_on_heap, 20);
388 nonzero_vars = BITMAP_ALLOC (NULL);
389 need_eh_cleanup = BITMAP_ALLOC (NULL);
390
391 /* Setup callbacks for the generic dominator tree walker. */
392 walk_data.walk_stmts_backward = false;
393 walk_data.dom_direction = CDI_DOMINATORS;
394 walk_data.initialize_block_local_data = NULL;
395 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
396 walk_data.before_dom_children_walk_stmts = optimize_stmt;
397 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
398 walk_data.after_dom_children_before_stmts = NULL;
399 walk_data.after_dom_children_walk_stmts = NULL;
400 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
401 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
402 When we attach more stuff we'll need to fill this out with a real
403 structure. */
404 walk_data.global_data = NULL;
405 walk_data.block_local_data_size = 0;
406
407 /* Now initialize the dominator walker. */
408 init_walk_dominator_tree (&walk_data);
409
410 calculate_dominance_info (CDI_DOMINATORS);
411
412 /* We need to know which edges exit loops so that we can
413 aggressively thread through loop headers to an exit
414 edge. */
415 flow_loops_find (&loops_info);
416 mark_loop_exit_edges (&loops_info);
417 flow_loops_free (&loops_info);
418
419 /* Clean up the CFG so that any forwarder blocks created by loop
420 canonicalization are removed. */
421 cleanup_tree_cfg ();
422
423 /* If we prove certain blocks are unreachable, then we want to
424 repeat the dominator optimization process as PHI nodes may
425 have turned into copies which allows better propagation of
426 values. So we repeat until we do not identify any new unreachable
427 blocks. */
428 do
429 {
430 /* Optimize the dominator tree. */
431 cfg_altered = false;
432
433 /* We need accurate information regarding back edges in the CFG
434 for jump threading. */
435 mark_dfs_back_edges ();
436
437 /* Recursively walk the dominator tree optimizing statements. */
438 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
439
440 /* If we exposed any new variables, go ahead and put them into
441 SSA form now, before we handle jump threading. This simplifies
442 interactions between rewriting of _DECL nodes into SSA form
443 and rewriting SSA_NAME nodes into SSA form after block
444 duplication and CFG manipulation. */
445 if (!bitmap_empty_p (vars_to_rename))
446 {
447 rewrite_into_ssa (false);
448 bitmap_clear (vars_to_rename);
449 }
450
451 free_all_edge_infos ();
452
453 /* Thread jumps, creating duplicate blocks as needed. */
454 cfg_altered |= thread_through_all_blocks ();
455
456 /* Removal of statements may make some EH edges dead. Purge
457 such edges from the CFG as needed. */
458 if (!bitmap_empty_p (need_eh_cleanup))
459 {
460 cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
461 bitmap_zero (need_eh_cleanup);
462 }
463
464 if (cfg_altered)
465 free_dominance_info (CDI_DOMINATORS);
466
467 cfg_altered |= cleanup_tree_cfg ();
468
469 if (rediscover_loops_after_threading)
470 {
471 /* Rerun basic loop analysis to discover any newly
472 created loops and update the set of exit edges. */
473 rediscover_loops_after_threading = false;
474 flow_loops_find (&loops_info);
475 mark_loop_exit_edges (&loops_info);
476 flow_loops_free (&loops_info);
477
478 /* Remove any forwarder blocks inserted by loop
479 header canonicalization. */
480 cleanup_tree_cfg ();
481 }
482
483 calculate_dominance_info (CDI_DOMINATORS);
484
485 rewrite_ssa_into_ssa ();
486
487 /* Reinitialize the various tables. */
488 bitmap_clear (nonzero_vars);
489 htab_empty (avail_exprs);
490 htab_empty (vrp_data);
491
492 for (i = 0; i < num_referenced_vars; i++)
493 var_ann (referenced_var (i))->current_def = NULL;
494
495 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
496
497 This must be done before we iterate as we might have a
498 reference to an SSA_NAME which was removed by the call to
499 rewrite_ssa_into_ssa.
500
501 Long term we will be able to let everything in SSA_NAME_VALUE
502 persist. However, for now, we know this is the safe thing to do. */
503 for (i = 0; i < num_ssa_names; i++)
504 {
505 tree name = ssa_name (i);
506 tree value;
507
508 if (!name)
509 continue;
510
511 value = SSA_NAME_VALUE (name);
512 if (value && !is_gimple_min_invariant (value))
513 SSA_NAME_VALUE (name) = NULL;
514 }
515 }
516 while (optimize > 1 && cfg_altered);
517
518 /* Debugging dumps. */
519 if (dump_file && (dump_flags & TDF_STATS))
520 dump_dominator_optimization_stats (dump_file);
521
522 /* We emptied the hash table earlier, now delete it completely. */
523 htab_delete (avail_exprs);
524 htab_delete (vrp_data);
525
526 /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
527 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
528 of the do-while loop above. */
529
530 /* And finalize the dominator walker. */
531 fini_walk_dominator_tree (&walk_data);
532
533 /* Free nonzero_vars. */
534 BITMAP_FREE (nonzero_vars);
535 BITMAP_FREE (need_eh_cleanup);
536
537 VEC_free (tree_on_heap, block_defs_stack);
538 VEC_free (tree_on_heap, avail_exprs_stack);
539 VEC_free (tree_on_heap, const_and_copies_stack);
540 VEC_free (tree_on_heap, nonzero_vars_stack);
541 VEC_free (tree_on_heap, vrp_variables_stack);
542 VEC_free (tree_on_heap, stmts_to_rescan);
543 }
544
545 static bool
546 gate_dominator (void)
547 {
548 return flag_tree_dom != 0;
549 }
550
551 struct tree_opt_pass pass_dominator =
552 {
553 "dom", /* name */
554 gate_dominator, /* gate */
555 tree_ssa_dominator_optimize, /* execute */
556 NULL, /* sub */
557 NULL, /* next */
558 0, /* static_pass_number */
559 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
560 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
561 0, /* properties_provided */
562 0, /* properties_destroyed */
563 0, /* todo_flags_start */
564 TODO_dump_func | TODO_rename_vars
565 | TODO_verify_ssa, /* todo_flags_finish */
566 0 /* letter */
567 };
568
569
570 /* We are exiting BB, see if the target block begins with a conditional
571 jump which has a known value when reached via BB. */
572
573 static void
574 thread_across_edge (struct dom_walk_data *walk_data, edge e)
575 {
576 block_stmt_iterator bsi;
577 tree stmt = NULL;
578 tree phi;
579
580 /* Each PHI creates a temporary equivalence, record them. */
581 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
582 {
583 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
584 tree dst = PHI_RESULT (phi);
585
586 /* If the desired argument is not the same as this PHI's result
587 and it is set by a PHI in this block, then we can not thread
588 through this block. */
589 if (src != dst
590 && TREE_CODE (src) == SSA_NAME
591 && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
592 && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
593 return;
594
595 record_const_or_copy (dst, src);
596 register_new_def (dst, &block_defs_stack);
597 }
598
599 for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
600 {
601 tree lhs, cached_lhs;
602
603 stmt = bsi_stmt (bsi);
604
605 /* Ignore empty statements and labels. */
606 if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
607 continue;
608
609 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
610 value, then stop our search here. Ideally when we stop a
611 search we stop on a COND_EXPR or SWITCH_EXPR. */
612 if (TREE_CODE (stmt) != MODIFY_EXPR
613 || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
614 break;
615
616 /* At this point we have a statement which assigns an RHS to an
617 SSA_VAR on the LHS. We want to prove that the RHS is already
618 available and that its value is held in the current definition
619 of the LHS -- meaning that this assignment is a NOP when
620 reached via edge E. */
621 if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
622 cached_lhs = TREE_OPERAND (stmt, 1);
623 else
624 cached_lhs = lookup_avail_expr (stmt, false);
625
626 lhs = TREE_OPERAND (stmt, 0);
627
628 /* This can happen if we thread around to the start of a loop. */
629 if (lhs == cached_lhs)
630 break;
631
632 /* If we did not find RHS in the hash table, then try again after
633 temporarily const/copy propagating the operands. */
634 if (!cached_lhs)
635 {
636 /* Copy the operands. */
637 stmt_ann_t ann = stmt_ann (stmt);
638 use_optype uses = USE_OPS (ann);
639 vuse_optype vuses = VUSE_OPS (ann);
640 tree *uses_copy = xmalloc (NUM_USES (uses) * sizeof (tree));
641 tree *vuses_copy = xmalloc (NUM_VUSES (vuses) * sizeof (tree));
642 unsigned int i;
643
644 /* Make a copy of the uses into USES_COPY, then cprop into
645 the use operands. */
646 for (i = 0; i < NUM_USES (uses); i++)
647 {
648 tree tmp = NULL;
649
650 uses_copy[i] = USE_OP (uses, i);
651 if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
652 tmp = SSA_NAME_VALUE (USE_OP (uses, i));
653 if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
654 SET_USE_OP (uses, i, tmp);
655 }
656
657 /* Similarly for virtual uses. */
658 for (i = 0; i < NUM_VUSES (vuses); i++)
659 {
660 tree tmp = NULL;
661
662 vuses_copy[i] = VUSE_OP (vuses, i);
663 if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
664 tmp = SSA_NAME_VALUE (VUSE_OP (vuses, i));
665 if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
666 SET_VUSE_OP (vuses, i, tmp);
667 }
668
669 /* Try to lookup the new expression. */
670 cached_lhs = lookup_avail_expr (stmt, false);
671
672 /* Restore the statement's original uses/defs. */
673 for (i = 0; i < NUM_USES (uses); i++)
674 SET_USE_OP (uses, i, uses_copy[i]);
675
676 for (i = 0; i < NUM_VUSES (vuses); i++)
677 SET_VUSE_OP (vuses, i, vuses_copy[i]);
678
679 free (uses_copy);
680 free (vuses_copy);
681
682 /* If we still did not find the expression in the hash table,
683 then we can not ignore this statement. */
684 if (! cached_lhs)
685 break;
686 }
687
688 /* If the expression in the hash table was not assigned to an
689 SSA_NAME, then we can not ignore this statement. */
690 if (TREE_CODE (cached_lhs) != SSA_NAME)
691 break;
692
693 /* If we have different underlying variables, then we can not
694 ignore this statement. */
695 if (SSA_NAME_VAR (cached_lhs) != SSA_NAME_VAR (lhs))
696 break;
697
698 /* If CACHED_LHS does not represent the current value of the underlying
699 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
700 if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
701 break;
702
703 /* If we got here, then we can ignore this statement and continue
704 walking through the statements in the block looking for a threadable
705 COND_EXPR.
706
707 We want to record an equivalence lhs = cache_lhs so that if
708 the result of this statement is used later we can copy propagate
709 suitably. */
710 record_const_or_copy (lhs, cached_lhs);
711 register_new_def (lhs, &block_defs_stack);
712 }
713
714 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
715 arm will be taken. */
716 if (stmt
717 && (TREE_CODE (stmt) == COND_EXPR
718 || TREE_CODE (stmt) == SWITCH_EXPR
719 || TREE_CODE (stmt) == GOTO_EXPR))
720 {
721 tree cond, cached_lhs;
722
723 /* Now temporarily cprop the operands and try to find the resulting
724 expression in the hash tables. */
725 if (TREE_CODE (stmt) == COND_EXPR)
726 cond = COND_EXPR_COND (stmt);
727 else if (TREE_CODE (stmt) == GOTO_EXPR)
728 cond = GOTO_DESTINATION (stmt);
729 else
730 cond = SWITCH_COND (stmt);
731
732 if (COMPARISON_CLASS_P (cond))
733 {
734 tree dummy_cond, op0, op1;
735 enum tree_code cond_code;
736
737 op0 = TREE_OPERAND (cond, 0);
738 op1 = TREE_OPERAND (cond, 1);
739 cond_code = TREE_CODE (cond);
740
741 /* Get the current value of both operands. */
742 if (TREE_CODE (op0) == SSA_NAME)
743 {
744 tree tmp = SSA_NAME_VALUE (op0);
745 if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
746 op0 = tmp;
747 }
748
749 if (TREE_CODE (op1) == SSA_NAME)
750 {
751 tree tmp = SSA_NAME_VALUE (op1);
752 if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
753 op1 = tmp;
754 }
755
756 /* Stuff the operator and operands into our dummy conditional
757 expression, creating the dummy conditional if necessary. */
758 dummy_cond = walk_data->global_data;
759 if (! dummy_cond)
760 {
761 dummy_cond = build (cond_code, boolean_type_node, op0, op1);
762 dummy_cond = build (COND_EXPR, void_type_node,
763 dummy_cond, NULL, NULL);
764 walk_data->global_data = dummy_cond;
765 }
766 else
767 {
768 TREE_SET_CODE (COND_EXPR_COND (dummy_cond), cond_code);
769 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op0;
770 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1) = op1;
771 }
772
773 /* If the conditional folds to an invariant, then we are done,
774 otherwise look it up in the hash tables. */
775 cached_lhs = local_fold (COND_EXPR_COND (dummy_cond));
776 if (! is_gimple_min_invariant (cached_lhs))
777 {
778 cached_lhs = lookup_avail_expr (dummy_cond, false);
779 if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
780 cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
781 NULL,
782 false);
783 }
784 }
785 /* We can have conditionals which just test the state of a
786 variable rather than use a relational operator. These are
787 simpler to handle. */
788 else if (TREE_CODE (cond) == SSA_NAME)
789 {
790 cached_lhs = cond;
791 cached_lhs = SSA_NAME_VALUE (cached_lhs);
792 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
793 cached_lhs = 0;
794 }
795 else
796 cached_lhs = lookup_avail_expr (stmt, false);
797
798 if (cached_lhs)
799 {
800 edge taken_edge = find_taken_edge (e->dest, cached_lhs);
801 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
802
803 if (dest == e->dest)
804 return;
805
806 /* If we have a known destination for the conditional, then
807 we can perform this optimization, which saves at least one
808 conditional jump each time it applies since we get to
809 bypass the conditional at our original destination. */
810 if (dest)
811 {
812 struct edge_info *edge_info;
813
814 update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
815 e->count, taken_edge);
816 if (e->aux)
817 edge_info = e->aux;
818 else
819 edge_info = allocate_edge_info (e);
820 edge_info->redirection_target = taken_edge;
821 bb_ann (e->dest)->incoming_edge_threaded = true;
822 }
823 }
824 }
825 }
826
827
828 /* Initialize local stacks for this optimizer and record equivalences
829 upon entry to BB. Equivalences can come from the edge traversed to
830 reach BB or they may come from PHI nodes at the start of BB. */
831
832 static void
833 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
834 basic_block bb)
835 {
836 if (dump_file && (dump_flags & TDF_DETAILS))
837 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
838
839 /* Push a marker on the stacks of local information so that we know how
840 far to unwind when we finalize this block. */
841 VEC_safe_push (tree_on_heap, avail_exprs_stack, NULL_TREE);
842 VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
843 VEC_safe_push (tree_on_heap, const_and_copies_stack, NULL_TREE);
844 VEC_safe_push (tree_on_heap, nonzero_vars_stack, NULL_TREE);
845 VEC_safe_push (tree_on_heap, vrp_variables_stack, NULL_TREE);
846
847 record_equivalences_from_incoming_edge (bb);
848
849 /* PHI nodes can create equivalences too. */
850 record_equivalences_from_phis (bb);
851 }
852
853 /* Given an expression EXPR (a relational expression or a statement),
854 initialize the hash table element pointed by by ELEMENT. */
855
856 static void
857 initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
858 {
859 /* Hash table elements may be based on conditional expressions or statements.
860
861 For the former case, we have no annotation and we want to hash the
862 conditional expression. In the latter case we have an annotation and
863 we want to record the expression the statement evaluates. */
864 if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
865 {
866 element->ann = NULL;
867 element->rhs = expr;
868 }
869 else if (TREE_CODE (expr) == COND_EXPR)
870 {
871 element->ann = stmt_ann (expr);
872 element->rhs = COND_EXPR_COND (expr);
873 }
874 else if (TREE_CODE (expr) == SWITCH_EXPR)
875 {
876 element->ann = stmt_ann (expr);
877 element->rhs = SWITCH_COND (expr);
878 }
879 else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
880 {
881 element->ann = stmt_ann (expr);
882 element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
883 }
884 else
885 {
886 element->ann = stmt_ann (expr);
887 element->rhs = TREE_OPERAND (expr, 1);
888 }
889
890 element->lhs = lhs;
891 element->hash = avail_expr_hash (element);
892 }
893
894 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
895 LIMIT entries left in LOCALs. */
896
897 static void
898 remove_local_expressions_from_table (void)
899 {
900 /* Remove all the expressions made available in this block. */
901 while (VEC_length (tree_on_heap, avail_exprs_stack) > 0)
902 {
903 struct expr_hash_elt element;
904 tree expr = VEC_pop (tree_on_heap, avail_exprs_stack);
905
906 if (expr == NULL_TREE)
907 break;
908
909 initialize_hash_element (expr, NULL, &element);
910 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
911 }
912 }
913
914 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
915 state, stopping when there are LIMIT entries left in LOCALs. */
916
917 static void
918 restore_nonzero_vars_to_original_value (void)
919 {
920 while (VEC_length (tree_on_heap, nonzero_vars_stack) > 0)
921 {
922 tree name = VEC_pop (tree_on_heap, nonzero_vars_stack);
923
924 if (name == NULL)
925 break;
926
927 bitmap_clear_bit (nonzero_vars, SSA_NAME_VERSION (name));
928 }
929 }
930
931 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
932 CONST_AND_COPIES to its original state, stopping when we hit a
933 NULL marker. */
934
935 static void
936 restore_vars_to_original_value (void)
937 {
938 while (VEC_length (tree_on_heap, const_and_copies_stack) > 0)
939 {
940 tree prev_value, dest;
941
942 dest = VEC_pop (tree_on_heap, const_and_copies_stack);
943
944 if (dest == NULL)
945 break;
946
947 prev_value = VEC_pop (tree_on_heap, const_and_copies_stack);
948 SSA_NAME_VALUE (dest) = prev_value;
949 }
950 }
951
952 /* Similar to restore_vars_to_original_value, except that it restores
953 CURRDEFS to its original value. */
954 static void
955 restore_currdefs_to_original_value (void)
956 {
957 /* Restore CURRDEFS to its original state. */
958 while (VEC_length (tree_on_heap, block_defs_stack) > 0)
959 {
960 tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
961 tree saved_def, var;
962
963 if (tmp == NULL_TREE)
964 break;
965
966 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
967 definition of its underlying variable. If we recorded anything
968 else, it must have been an _DECL node and its current reaching
969 definition must have been NULL. */
970 if (TREE_CODE (tmp) == SSA_NAME)
971 {
972 saved_def = tmp;
973 var = SSA_NAME_VAR (saved_def);
974 }
975 else
976 {
977 saved_def = NULL;
978 var = tmp;
979 }
980
981 var_ann (var)->current_def = saved_def;
982 }
983 }
984
985 /* We have finished processing the dominator children of BB, perform
986 any finalization actions in preparation for leaving this node in
987 the dominator tree. */
988
989 static void
990 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
991 {
992 tree last;
993
994 /* If we are at a leaf node in the dominator tree, see if we can thread
995 the edge from BB through its successor.
996
997 Do this before we remove entries from our equivalence tables. */
998 if (single_succ_p (bb)
999 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
1000 && (get_immediate_dominator (CDI_DOMINATORS, single_succ (bb)) != bb
1001 || phi_nodes (single_succ (bb))))
1002
1003 {
1004 thread_across_edge (walk_data, single_succ_edge (bb));
1005 }
1006 else if ((last = last_stmt (bb))
1007 && TREE_CODE (last) == GOTO_EXPR
1008 && TREE_CODE (TREE_OPERAND (last, 0)) == SSA_NAME)
1009 {
1010 edge_iterator ei;
1011 edge e;
1012
1013 FOR_EACH_EDGE (e, ei, bb->succs)
1014 {
1015 thread_across_edge (walk_data, e);
1016 }
1017 }
1018 else if ((last = last_stmt (bb))
1019 && TREE_CODE (last) == COND_EXPR
1020 && (COMPARISON_CLASS_P (COND_EXPR_COND (last))
1021 || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
1022 && EDGE_COUNT (bb->succs) == 2
1023 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
1024 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
1025 {
1026 edge true_edge, false_edge;
1027
1028 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1029
1030 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
1031 then try to thread through its edge. */
1032 if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb
1033 || phi_nodes (true_edge->dest))
1034 {
1035 struct edge_info *edge_info;
1036 unsigned int i;
1037
1038 /* Push a marker onto the available expression stack so that we
1039 unwind any expressions related to the TRUE arm before processing
1040 the false arm below. */
1041 VEC_safe_push (tree_on_heap, avail_exprs_stack, NULL_TREE);
1042 VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
1043 VEC_safe_push (tree_on_heap, const_and_copies_stack, NULL_TREE);
1044
1045 edge_info = true_edge->aux;
1046
1047 /* If we have info associated with this edge, record it into
1048 our equivalency tables. */
1049 if (edge_info)
1050 {
1051 tree *cond_equivalences = edge_info->cond_equivalences;
1052 tree lhs = edge_info->lhs;
1053 tree rhs = edge_info->rhs;
1054
1055 /* If we have a simple NAME = VALUE equivalency record it.
1056 Until the jump threading selection code improves, only
1057 do this if both the name and value are SSA_NAMEs with
1058 the same underlying variable to avoid missing threading
1059 opportunities. */
1060 if (lhs
1061 && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME
1062 && TREE_CODE (edge_info->rhs) == SSA_NAME
1063 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs))
1064 record_const_or_copy (lhs, rhs);
1065
1066 /* If we have 0 = COND or 1 = COND equivalences, record them
1067 into our expression hash tables. */
1068 if (cond_equivalences)
1069 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
1070 {
1071 tree expr = cond_equivalences[i];
1072 tree value = cond_equivalences[i + 1];
1073
1074 record_cond (expr, value);
1075 }
1076 }
1077
1078 /* Now thread the edge. */
1079 thread_across_edge (walk_data, true_edge);
1080
1081 /* And restore the various tables to their state before
1082 we threaded this edge. */
1083 remove_local_expressions_from_table ();
1084 restore_vars_to_original_value ();
1085 restore_currdefs_to_original_value ();
1086 }
1087
1088 /* Similarly for the ELSE arm. */
1089 if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb
1090 || phi_nodes (false_edge->dest))
1091 {
1092 struct edge_info *edge_info;
1093 unsigned int i;
1094
1095 edge_info = false_edge->aux;
1096
1097 /* If we have info associated with this edge, record it into
1098 our equivalency tables. */
1099 if (edge_info)
1100 {
1101 tree *cond_equivalences = edge_info->cond_equivalences;
1102 tree lhs = edge_info->lhs;
1103 tree rhs = edge_info->rhs;
1104
1105 /* If we have a simple NAME = VALUE equivalency record it.
1106 Until the jump threading selection code improves, only
1107 do this if both the name and value are SSA_NAMEs with
1108 the same underlying variable to avoid missing threading
1109 opportunities. */
1110 if (lhs
1111 && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
1112 record_const_or_copy (lhs, rhs);
1113
1114 /* If we have 0 = COND or 1 = COND equivalences, record them
1115 into our expression hash tables. */
1116 if (cond_equivalences)
1117 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
1118 {
1119 tree expr = cond_equivalences[i];
1120 tree value = cond_equivalences[i + 1];
1121
1122 record_cond (expr, value);
1123 }
1124 }
1125
1126 thread_across_edge (walk_data, false_edge);
1127
1128 /* No need to remove local expressions from our tables
1129 or restore vars to their original value as that will
1130 be done immediately below. */
1131 }
1132 }
1133
1134 remove_local_expressions_from_table ();
1135 restore_nonzero_vars_to_original_value ();
1136 restore_vars_to_original_value ();
1137 restore_currdefs_to_original_value ();
1138
1139 /* Remove VRP records associated with this basic block. They are no
1140 longer valid.
1141
1142 To be efficient, we note which variables have had their values
1143 constrained in this block. So walk over each variable in the
1144 VRP_VARIABLEs array. */
1145 while (VEC_length (tree_on_heap, vrp_variables_stack) > 0)
1146 {
1147 tree var = VEC_pop (tree_on_heap, vrp_variables_stack);
1148 struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
1149 void **slot;
1150
1151 /* Each variable has a stack of value range records. We want to
1152 invalidate those associated with our basic block. So we walk
1153 the array backwards popping off records associated with our
1154 block. Once we hit a record not associated with our block
1155 we are done. */
1156 varray_type var_vrp_records;
1157
1158 if (var == NULL)
1159 break;
1160
1161 vrp_hash_elt.var = var;
1162 vrp_hash_elt.records = NULL;
1163
1164 slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT);
1165
1166 vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
1167 var_vrp_records = vrp_hash_elt_p->records;
1168
1169 while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0)
1170 {
1171 struct vrp_element *element
1172 = (struct vrp_element *)VARRAY_TOP_GENERIC_PTR (var_vrp_records);
1173
1174 if (element->bb != bb)
1175 break;
1176
1177 VARRAY_POP (var_vrp_records);
1178 }
1179 }
1180
1181 /* If we queued any statements to rescan in this block, then
1182 go ahead and rescan them now. */
1183 while (VEC_length (tree_on_heap, stmts_to_rescan) > 0)
1184 {
1185 tree stmt = VEC_last (tree_on_heap, stmts_to_rescan);
1186 basic_block stmt_bb = bb_for_stmt (stmt);
1187
1188 if (stmt_bb != bb)
1189 break;
1190
1191 VEC_pop (tree_on_heap, stmts_to_rescan);
1192 mark_new_vars_to_rename (stmt, vars_to_rename);
1193 }
1194 }
1195
1196 /* PHI nodes can create equivalences too.
1197
1198 Ignoring any alternatives which are the same as the result, if
1199 all the alternatives are equal, then the PHI node creates an
1200 equivalence.
1201
1202 Additionally, if all the PHI alternatives are known to have a nonzero
1203 value, then the result of this PHI is known to have a nonzero value,
1204 even if we do not know its exact value. */
1205
1206 static void
1207 record_equivalences_from_phis (basic_block bb)
1208 {
1209 tree phi;
1210
1211 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1212 {
1213 tree lhs = PHI_RESULT (phi);
1214 tree rhs = NULL;
1215 int i;
1216
1217 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1218 {
1219 tree t = PHI_ARG_DEF (phi, i);
1220
1221 /* Ignore alternatives which are the same as our LHS. Since
1222 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1223 can simply compare pointers. */
1224 if (lhs == t)
1225 continue;
1226
1227 /* If we have not processed an alternative yet, then set
1228 RHS to this alternative. */
1229 if (rhs == NULL)
1230 rhs = t;
1231 /* If we have processed an alternative (stored in RHS), then
1232 see if it is equal to this one. If it isn't, then stop
1233 the search. */
1234 else if (! operand_equal_for_phi_arg_p (rhs, t))
1235 break;
1236 }
1237
1238 /* If we had no interesting alternatives, then all the RHS alternatives
1239 must have been the same as LHS. */
1240 if (!rhs)
1241 rhs = lhs;
1242
1243 /* If we managed to iterate through each PHI alternative without
1244 breaking out of the loop, then we have a PHI which may create
1245 a useful equivalence. We do not need to record unwind data for
1246 this, since this is a true assignment and not an equivalence
1247 inferred from a comparison. All uses of this ssa name are dominated
1248 by this assignment, so unwinding just costs time and space. */
1249 if (i == PHI_NUM_ARGS (phi)
1250 && may_propagate_copy (lhs, rhs))
1251 SSA_NAME_VALUE (lhs) = rhs;
1252
1253 /* Now see if we know anything about the nonzero property for the
1254 result of this PHI. */
1255 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1256 {
1257 if (!PHI_ARG_NONZERO (phi, i))
1258 break;
1259 }
1260
1261 if (i == PHI_NUM_ARGS (phi))
1262 bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
1263
1264 register_new_def (lhs, &block_defs_stack);
1265 }
1266 }
1267
1268 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1269 return that edge. Otherwise return NULL. */
1270 static edge
1271 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1272 {
1273 edge retval = NULL;
1274 edge e;
1275 edge_iterator ei;
1276
1277 FOR_EACH_EDGE (e, ei, bb->preds)
1278 {
1279 /* A loop back edge can be identified by the destination of
1280 the edge dominating the source of the edge. */
1281 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1282 continue;
1283
1284 /* If we have already seen a non-loop edge, then we must have
1285 multiple incoming non-loop edges and thus we return NULL. */
1286 if (retval)
1287 return NULL;
1288
1289 /* This is the first non-loop incoming edge we have found. Record
1290 it. */
1291 retval = e;
1292 }
1293
1294 return retval;
1295 }
1296
1297 /* Record any equivalences created by the incoming edge to BB. If BB
1298 has more than one incoming edge, then no equivalence is created. */
1299
1300 static void
1301 record_equivalences_from_incoming_edge (basic_block bb)
1302 {
1303 edge e;
1304 basic_block parent;
1305 struct edge_info *edge_info;
1306
1307 /* If our parent block ended with a control statement, then we may be
1308 able to record some equivalences based on which outgoing edge from
1309 the parent was followed. */
1310 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1311
1312 e = single_incoming_edge_ignoring_loop_edges (bb);
1313
1314 /* If we had a single incoming edge from our parent block, then enter
1315 any data associated with the edge into our tables. */
1316 if (e && e->src == parent)
1317 {
1318 unsigned int i;
1319
1320 edge_info = e->aux;
1321
1322 if (edge_info)
1323 {
1324 tree lhs = edge_info->lhs;
1325 tree rhs = edge_info->rhs;
1326 tree *cond_equivalences = edge_info->cond_equivalences;
1327
1328 if (lhs)
1329 record_equality (lhs, rhs);
1330
1331 if (cond_equivalences)
1332 {
1333 bool recorded_range = false;
1334 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
1335 {
1336 tree expr = cond_equivalences[i];
1337 tree value = cond_equivalences[i + 1];
1338
1339 record_cond (expr, value);
1340
1341 /* For the first true equivalence, record range
1342 information. We only do this for the first
1343 true equivalence as it should dominate any
1344 later true equivalences. */
1345 if (! recorded_range
1346 && COMPARISON_CLASS_P (expr)
1347 && value == boolean_true_node
1348 && TREE_CONSTANT (TREE_OPERAND (expr, 1)))
1349 {
1350 record_range (expr, bb);
1351 recorded_range = true;
1352 }
1353 }
1354 }
1355 }
1356 }
1357 }
1358
1359 /* Dump SSA statistics on FILE. */
1360
1361 void
1362 dump_dominator_optimization_stats (FILE *file)
1363 {
1364 long n_exprs;
1365
1366 fprintf (file, "Total number of statements: %6ld\n\n",
1367 opt_stats.num_stmts);
1368 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1369 opt_stats.num_exprs_considered);
1370
1371 n_exprs = opt_stats.num_exprs_considered;
1372 if (n_exprs == 0)
1373 n_exprs = 1;
1374
1375 fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1376 opt_stats.num_re, PERCENT (opt_stats.num_re,
1377 n_exprs));
1378
1379 fprintf (file, "\nHash table statistics:\n");
1380
1381 fprintf (file, " avail_exprs: ");
1382 htab_statistics (file, avail_exprs);
1383 }
1384
1385
1386 /* Dump SSA statistics on stderr. */
1387
1388 void
1389 debug_dominator_optimization_stats (void)
1390 {
1391 dump_dominator_optimization_stats (stderr);
1392 }
1393
1394
1395 /* Dump statistics for the hash table HTAB. */
1396
1397 static void
1398 htab_statistics (FILE *file, htab_t htab)
1399 {
1400 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1401 (long) htab_size (htab),
1402 (long) htab_elements (htab),
1403 htab_collisions (htab));
1404 }
1405
1406 /* Record the fact that VAR has a nonzero value, though we may not know
1407 its exact value. Note that if VAR is already known to have a nonzero
1408 value, then we do nothing. */
1409
1410 static void
1411 record_var_is_nonzero (tree var)
1412 {
1413 int indx = SSA_NAME_VERSION (var);
1414
1415 if (bitmap_bit_p (nonzero_vars, indx))
1416 return;
1417
1418 /* Mark it in the global table. */
1419 bitmap_set_bit (nonzero_vars, indx);
1420
1421 /* Record this SSA_NAME so that we can reset the global table
1422 when we leave this block. */
1423 VEC_safe_push (tree_on_heap, nonzero_vars_stack, var);
1424 }
1425
1426 /* Enter a statement into the true/false expression hash table indicating
1427 that the condition COND has the value VALUE. */
1428
1429 static void
1430 record_cond (tree cond, tree value)
1431 {
1432 struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
1433 void **slot;
1434
1435 initialize_hash_element (cond, value, element);
1436
1437 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1438 element->hash, INSERT);
1439 if (*slot == NULL)
1440 {
1441 *slot = (void *) element;
1442 VEC_safe_push (tree_on_heap, avail_exprs_stack, cond);
1443 }
1444 else
1445 free (element);
1446 }
1447
1448 /* Build a new conditional using NEW_CODE, OP0 and OP1 and store
1449 the new conditional into *p, then store a boolean_true_node
1450 into *(p + 1). */
1451
1452 static void
1453 build_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p)
1454 {
1455 *p = build2 (new_code, boolean_type_node, op0, op1);
1456 p++;
1457 *p = boolean_true_node;
1458 }
1459
1460 /* Record that COND is true and INVERTED is false into the edge information
1461 structure. Also record that any conditions dominated by COND are true
1462 as well.
1463
1464 For example, if a < b is true, then a <= b must also be true. */
1465
1466 static void
1467 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
1468 {
1469 tree op0, op1;
1470
1471 if (!COMPARISON_CLASS_P (cond))
1472 return;
1473
1474 op0 = TREE_OPERAND (cond, 0);
1475 op1 = TREE_OPERAND (cond, 1);
1476
1477 switch (TREE_CODE (cond))
1478 {
1479 case LT_EXPR:
1480 case GT_EXPR:
1481 edge_info->max_cond_equivalences = 12;
1482 edge_info->cond_equivalences = xmalloc (12 * sizeof (tree));
1483 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1484 ? LE_EXPR : GE_EXPR),
1485 op0, op1, &edge_info->cond_equivalences[4]);
1486 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1487 &edge_info->cond_equivalences[6]);
1488 build_and_record_new_cond (NE_EXPR, op0, op1,
1489 &edge_info->cond_equivalences[8]);
1490 build_and_record_new_cond (LTGT_EXPR, op0, op1,
1491 &edge_info->cond_equivalences[10]);
1492 break;
1493
1494 case GE_EXPR:
1495 case LE_EXPR:
1496 edge_info->max_cond_equivalences = 6;
1497 edge_info->cond_equivalences = xmalloc (6 * sizeof (tree));
1498 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1499 &edge_info->cond_equivalences[4]);
1500 break;
1501
1502 case EQ_EXPR:
1503 edge_info->max_cond_equivalences = 10;
1504 edge_info->cond_equivalences = xmalloc (10 * sizeof (tree));
1505 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1506 &edge_info->cond_equivalences[4]);
1507 build_and_record_new_cond (LE_EXPR, op0, op1,
1508 &edge_info->cond_equivalences[6]);
1509 build_and_record_new_cond (GE_EXPR, op0, op1,
1510 &edge_info->cond_equivalences[8]);
1511 break;
1512
1513 case UNORDERED_EXPR:
1514 edge_info->max_cond_equivalences = 16;
1515 edge_info->cond_equivalences = xmalloc (16 * sizeof (tree));
1516 build_and_record_new_cond (NE_EXPR, op0, op1,
1517 &edge_info->cond_equivalences[4]);
1518 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1519 &edge_info->cond_equivalences[6]);
1520 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1521 &edge_info->cond_equivalences[8]);
1522 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1523 &edge_info->cond_equivalences[10]);
1524 build_and_record_new_cond (UNLT_EXPR, op0, op1,
1525 &edge_info->cond_equivalences[12]);
1526 build_and_record_new_cond (UNGT_EXPR, op0, op1,
1527 &edge_info->cond_equivalences[14]);
1528 break;
1529
1530 case UNLT_EXPR:
1531 case UNGT_EXPR:
1532 edge_info->max_cond_equivalences = 8;
1533 edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
1534 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1535 ? UNLE_EXPR : UNGE_EXPR),
1536 op0, op1, &edge_info->cond_equivalences[4]);
1537 build_and_record_new_cond (NE_EXPR, op0, op1,
1538 &edge_info->cond_equivalences[6]);
1539 break;
1540
1541 case UNEQ_EXPR:
1542 edge_info->max_cond_equivalences = 8;
1543 edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
1544 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1545 &edge_info->cond_equivalences[4]);
1546 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1547 &edge_info->cond_equivalences[6]);
1548 break;
1549
1550 case LTGT_EXPR:
1551 edge_info->max_cond_equivalences = 8;
1552 edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
1553 build_and_record_new_cond (NE_EXPR, op0, op1,
1554 &edge_info->cond_equivalences[4]);
1555 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1556 &edge_info->cond_equivalences[6]);
1557 break;
1558
1559 default:
1560 edge_info->max_cond_equivalences = 4;
1561 edge_info->cond_equivalences = xmalloc (4 * sizeof (tree));
1562 break;
1563 }
1564
1565 /* Now store the original true and false conditions into the first
1566 two slots. */
1567 edge_info->cond_equivalences[0] = cond;
1568 edge_info->cond_equivalences[1] = boolean_true_node;
1569 edge_info->cond_equivalences[2] = inverted;
1570 edge_info->cond_equivalences[3] = boolean_false_node;
1571 }
1572
1573 /* A helper function for record_const_or_copy and record_equality.
1574 Do the work of recording the value and undo info. */
1575
1576 static void
1577 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1578 {
1579 SSA_NAME_VALUE (x) = y;
1580
1581 VEC_safe_push (tree_on_heap, const_and_copies_stack, prev_x);
1582 VEC_safe_push (tree_on_heap, const_and_copies_stack, x);
1583 }
1584
1585
1586 /* Return the loop depth of the basic block of the defining statement of X.
1587 This number should not be treated as absolutely correct because the loop
1588 information may not be completely up-to-date when dom runs. However, it
1589 will be relatively correct, and as more passes are taught to keep loop info
1590 up to date, the result will become more and more accurate. */
1591
1592 static int
1593 loop_depth_of_name (tree x)
1594 {
1595 tree defstmt;
1596 basic_block defbb;
1597
1598 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1599 if (TREE_CODE (x) != SSA_NAME)
1600 return 0;
1601
1602 /* Otherwise return the loop depth of the defining statement's bb.
1603 Note that there may not actually be a bb for this statement, if the
1604 ssa_name is live on entry. */
1605 defstmt = SSA_NAME_DEF_STMT (x);
1606 defbb = bb_for_stmt (defstmt);
1607 if (!defbb)
1608 return 0;
1609
1610 return defbb->loop_depth;
1611 }
1612
1613
1614 /* Record that X is equal to Y in const_and_copies. Record undo
1615 information in the block-local vector. */
1616
1617 static void
1618 record_const_or_copy (tree x, tree y)
1619 {
1620 tree prev_x = SSA_NAME_VALUE (x);
1621
1622 if (TREE_CODE (y) == SSA_NAME)
1623 {
1624 tree tmp = SSA_NAME_VALUE (y);
1625 if (tmp)
1626 y = tmp;
1627 }
1628
1629 record_const_or_copy_1 (x, y, prev_x);
1630 }
1631
1632 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1633 This constrains the cases in which we may treat this as assignment. */
1634
1635 static void
1636 record_equality (tree x, tree y)
1637 {
1638 tree prev_x = NULL, prev_y = NULL;
1639
1640 if (TREE_CODE (x) == SSA_NAME)
1641 prev_x = SSA_NAME_VALUE (x);
1642 if (TREE_CODE (y) == SSA_NAME)
1643 prev_y = SSA_NAME_VALUE (y);
1644
1645 /* If one of the previous values is invariant, or invariant in more loops
1646 (by depth), then use that.
1647 Otherwise it doesn't matter which value we choose, just so
1648 long as we canonicalize on one value. */
1649 if (TREE_INVARIANT (y))
1650 ;
1651 else if (TREE_INVARIANT (x) || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1652 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1653 else if (prev_x && TREE_INVARIANT (prev_x))
1654 x = y, y = prev_x, prev_x = prev_y;
1655 else if (prev_y && TREE_CODE (prev_y) != VALUE_HANDLE)
1656 y = prev_y;
1657
1658 /* After the swapping, we must have one SSA_NAME. */
1659 if (TREE_CODE (x) != SSA_NAME)
1660 return;
1661
1662 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1663 variable compared against zero. If we're honoring signed zeros,
1664 then we cannot record this value unless we know that the value is
1665 nonzero. */
1666 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1667 && (TREE_CODE (y) != REAL_CST
1668 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1669 return;
1670
1671 record_const_or_copy_1 (x, y, prev_x);
1672 }
1673
1674 /* Return true, if it is ok to do folding of an associative expression.
1675 EXP is the tree for the associative expression. */
1676
1677 static inline bool
1678 unsafe_associative_fp_binop (tree exp)
1679 {
1680 enum tree_code code = TREE_CODE (exp);
1681 return !(!flag_unsafe_math_optimizations
1682 && (code == MULT_EXPR || code == PLUS_EXPR
1683 || code == MINUS_EXPR)
1684 && FLOAT_TYPE_P (TREE_TYPE (exp)));
1685 }
1686
1687 /* Returns true when STMT is a simple iv increment. It detects the
1688 following situation:
1689
1690 i_1 = phi (..., i_2)
1691 i_2 = i_1 +/- ... */
1692
1693 static bool
1694 simple_iv_increment_p (tree stmt)
1695 {
1696 tree lhs, rhs, preinc, phi;
1697 unsigned i;
1698
1699 if (TREE_CODE (stmt) != MODIFY_EXPR)
1700 return false;
1701
1702 lhs = TREE_OPERAND (stmt, 0);
1703 if (TREE_CODE (lhs) != SSA_NAME)
1704 return false;
1705
1706 rhs = TREE_OPERAND (stmt, 1);
1707
1708 if (TREE_CODE (rhs) != PLUS_EXPR
1709 && TREE_CODE (rhs) != MINUS_EXPR)
1710 return false;
1711
1712 preinc = TREE_OPERAND (rhs, 0);
1713 if (TREE_CODE (preinc) != SSA_NAME)
1714 return false;
1715
1716 phi = SSA_NAME_DEF_STMT (preinc);
1717 if (TREE_CODE (phi) != PHI_NODE)
1718 return false;
1719
1720 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1721 if (PHI_ARG_DEF (phi, i) == lhs)
1722 return true;
1723
1724 return false;
1725 }
1726
1727 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1728 hash tables. Try to simplify the RHS using whatever equivalences
1729 we may have recorded.
1730
1731 If we are able to simplify the RHS, then lookup the simplified form in
1732 the hash table and return the result. Otherwise return NULL. */
1733
1734 static tree
1735 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
1736 tree stmt, int insert)
1737 {
1738 tree rhs = TREE_OPERAND (stmt, 1);
1739 enum tree_code rhs_code = TREE_CODE (rhs);
1740 tree result = NULL;
1741
1742 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1743 In which case we can change this statement to be lhs = y.
1744 Which can then be copy propagated.
1745
1746 Similarly for negation. */
1747 if ((rhs_code == BIT_NOT_EXPR || rhs_code == NEGATE_EXPR)
1748 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
1749 {
1750 /* Get the definition statement for our RHS. */
1751 tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
1752
1753 /* See if the RHS_DEF_STMT has the same form as our statement. */
1754 if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR
1755 && TREE_CODE (TREE_OPERAND (rhs_def_stmt, 1)) == rhs_code)
1756 {
1757 tree rhs_def_operand;
1758
1759 rhs_def_operand = TREE_OPERAND (TREE_OPERAND (rhs_def_stmt, 1), 0);
1760
1761 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1762 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1763 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1764 result = update_rhs_and_lookup_avail_expr (stmt,
1765 rhs_def_operand,
1766 insert);
1767 }
1768 }
1769
1770 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1771 If OP is associative, create and fold (y OP C2) OP C1 which
1772 should result in (y OP C3), use that as the RHS for the
1773 assignment. Add minus to this, as we handle it specially below. */
1774 if ((associative_tree_code (rhs_code) || rhs_code == MINUS_EXPR)
1775 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
1776 && is_gimple_min_invariant (TREE_OPERAND (rhs, 1)))
1777 {
1778 tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
1779
1780 /* If the statement defines an induction variable, do not propagate
1781 its value, so that we do not create overlapping life ranges. */
1782 if (simple_iv_increment_p (rhs_def_stmt))
1783 goto dont_fold_assoc;
1784
1785 /* See if the RHS_DEF_STMT has the same form as our statement. */
1786 if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR)
1787 {
1788 tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
1789 enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
1790
1791 if ((rhs_code == rhs_def_code && unsafe_associative_fp_binop (rhs))
1792 || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
1793 || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
1794 {
1795 tree def_stmt_op0 = TREE_OPERAND (rhs_def_rhs, 0);
1796 tree def_stmt_op1 = TREE_OPERAND (rhs_def_rhs, 1);
1797
1798 if (TREE_CODE (def_stmt_op0) == SSA_NAME
1799 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0)
1800 && is_gimple_min_invariant (def_stmt_op1))
1801 {
1802 tree outer_const = TREE_OPERAND (rhs, 1);
1803 tree type = TREE_TYPE (TREE_OPERAND (stmt, 0));
1804 tree t;
1805
1806 /* If we care about correct floating point results, then
1807 don't fold x + c1 - c2. Note that we need to take both
1808 the codes and the signs to figure this out. */
1809 if (FLOAT_TYPE_P (type)
1810 && !flag_unsafe_math_optimizations
1811 && (rhs_def_code == PLUS_EXPR
1812 || rhs_def_code == MINUS_EXPR))
1813 {
1814 bool neg = false;
1815
1816 neg ^= (rhs_code == MINUS_EXPR);
1817 neg ^= (rhs_def_code == MINUS_EXPR);
1818 neg ^= real_isneg (TREE_REAL_CST_PTR (outer_const));
1819 neg ^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1));
1820
1821 if (neg)
1822 goto dont_fold_assoc;
1823 }
1824
1825 /* Ho hum. So fold will only operate on the outermost
1826 thingy that we give it, so we have to build the new
1827 expression in two pieces. This requires that we handle
1828 combinations of plus and minus. */
1829 if (rhs_def_code != rhs_code)
1830 {
1831 if (rhs_def_code == MINUS_EXPR)
1832 t = build (MINUS_EXPR, type, outer_const, def_stmt_op1);
1833 else
1834 t = build (MINUS_EXPR, type, def_stmt_op1, outer_const);
1835 rhs_code = PLUS_EXPR;
1836 }
1837 else if (rhs_def_code == MINUS_EXPR)
1838 t = build (PLUS_EXPR, type, def_stmt_op1, outer_const);
1839 else
1840 t = build (rhs_def_code, type, def_stmt_op1, outer_const);
1841 t = local_fold (t);
1842 t = build (rhs_code, type, def_stmt_op0, t);
1843 t = local_fold (t);
1844
1845 /* If the result is a suitable looking gimple expression,
1846 then use it instead of the original for STMT. */
1847 if (TREE_CODE (t) == SSA_NAME
1848 || (UNARY_CLASS_P (t)
1849 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1850 || ((BINARY_CLASS_P (t) || COMPARISON_CLASS_P (t))
1851 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
1852 && is_gimple_val (TREE_OPERAND (t, 1))))
1853 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1854 }
1855 }
1856 }
1857 dont_fold_assoc:;
1858 }
1859
1860 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1861 and BIT_AND_EXPR respectively if the first operand is greater
1862 than zero and the second operand is an exact power of two. */
1863 if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
1864 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
1865 && integer_pow2p (TREE_OPERAND (rhs, 1)))
1866 {
1867 tree val;
1868 tree op = TREE_OPERAND (rhs, 0);
1869
1870 if (TYPE_UNSIGNED (TREE_TYPE (op)))
1871 {
1872 val = integer_one_node;
1873 }
1874 else
1875 {
1876 tree dummy_cond = walk_data->global_data;
1877
1878 if (! dummy_cond)
1879 {
1880 dummy_cond = build (GT_EXPR, boolean_type_node,
1881 op, integer_zero_node);
1882 dummy_cond = build (COND_EXPR, void_type_node,
1883 dummy_cond, NULL, NULL);
1884 walk_data->global_data = dummy_cond;
1885 }
1886 else
1887 {
1888 TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GT_EXPR);
1889 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
1890 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
1891 = integer_zero_node;
1892 }
1893 val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
1894 }
1895
1896 if (val && integer_onep (val))
1897 {
1898 tree t;
1899 tree op0 = TREE_OPERAND (rhs, 0);
1900 tree op1 = TREE_OPERAND (rhs, 1);
1901
1902 if (rhs_code == TRUNC_DIV_EXPR)
1903 t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
1904 build_int_cst (NULL_TREE, tree_log2 (op1)));
1905 else
1906 t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
1907 local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
1908 op1, integer_one_node)));
1909
1910 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1911 }
1912 }
1913
1914 /* Transform ABS (X) into X or -X as appropriate. */
1915 if (rhs_code == ABS_EXPR
1916 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
1917 {
1918 tree val;
1919 tree op = TREE_OPERAND (rhs, 0);
1920 tree type = TREE_TYPE (op);
1921
1922 if (TYPE_UNSIGNED (type))
1923 {
1924 val = integer_zero_node;
1925 }
1926 else
1927 {
1928 tree dummy_cond = walk_data->global_data;
1929
1930 if (! dummy_cond)
1931 {
1932 dummy_cond = build (LE_EXPR, boolean_type_node,
1933 op, integer_zero_node);
1934 dummy_cond = build (COND_EXPR, void_type_node,
1935 dummy_cond, NULL, NULL);
1936 walk_data->global_data = dummy_cond;
1937 }
1938 else
1939 {
1940 TREE_SET_CODE (COND_EXPR_COND (dummy_cond), LE_EXPR);
1941 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
1942 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
1943 = build_int_cst (type, 0);
1944 }
1945 val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
1946
1947 if (!val)
1948 {
1949 TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GE_EXPR);
1950 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
1951 TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
1952 = build_int_cst (type, 0);
1953
1954 val = simplify_cond_and_lookup_avail_expr (dummy_cond,
1955 NULL, false);
1956
1957 if (val)
1958 {
1959 if (integer_zerop (val))
1960 val = integer_one_node;
1961 else if (integer_onep (val))
1962 val = integer_zero_node;
1963 }
1964 }
1965 }
1966
1967 if (val
1968 && (integer_onep (val) || integer_zerop (val)))
1969 {
1970 tree t;
1971
1972 if (integer_onep (val))
1973 t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
1974 else
1975 t = op;
1976
1977 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1978 }
1979 }
1980
1981 /* Optimize *"foo" into 'f'. This is done here rather than
1982 in fold to avoid problems with stuff like &*"foo". */
1983 if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)
1984 {
1985 tree t = fold_read_from_constant_string (rhs);
1986
1987 if (t)
1988 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1989 }
1990
1991 return result;
1992 }
1993
1994 /* COND is a condition of the form:
1995
1996 x == const or x != const
1997
1998 Look back to x's defining statement and see if x is defined as
1999
2000 x = (type) y;
2001
2002 If const is unchanged if we convert it to type, then we can build
2003 the equivalent expression:
2004
2005
2006 y == const or y != const
2007
2008 Which may allow further optimizations.
2009
2010 Return the equivalent comparison or NULL if no such equivalent comparison
2011 was found. */
2012
2013 static tree
2014 find_equivalent_equality_comparison (tree cond)
2015 {
2016 tree op0 = TREE_OPERAND (cond, 0);
2017 tree op1 = TREE_OPERAND (cond, 1);
2018 tree def_stmt = SSA_NAME_DEF_STMT (op0);
2019
2020 /* OP0 might have been a parameter, so first make sure it
2021 was defined by a MODIFY_EXPR. */
2022 if (def_stmt && TREE_CODE (def_stmt) == MODIFY_EXPR)
2023 {
2024 tree def_rhs = TREE_OPERAND (def_stmt, 1);
2025
2026 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
2027 if ((TREE_CODE (def_rhs) == NOP_EXPR
2028 || TREE_CODE (def_rhs) == CONVERT_EXPR)
2029 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME)
2030 {
2031 tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
2032 tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
2033 tree new;
2034
2035 if (TYPE_PRECISION (def_rhs_inner_type)
2036 > TYPE_PRECISION (TREE_TYPE (def_rhs)))
2037 return NULL;
2038
2039 /* What we want to prove is that if we convert OP1 to
2040 the type of the object inside the NOP_EXPR that the
2041 result is still equivalent to SRC.
2042
2043 If that is true, the build and return new equivalent
2044 condition which uses the source of the typecast and the
2045 new constant (which has only changed its type). */
2046 new = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
2047 new = local_fold (new);
2048 if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
2049 return build (TREE_CODE (cond), TREE_TYPE (cond),
2050 def_rhs_inner, new);
2051 }
2052 }
2053 return NULL;
2054 }
2055
2056 /* STMT is a COND_EXPR for which we could not trivially determine its
2057 result. This routine attempts to find equivalent forms of the
2058 condition which we may be able to optimize better. It also
2059 uses simple value range propagation to optimize conditionals. */
2060
2061 static tree
2062 simplify_cond_and_lookup_avail_expr (tree stmt,
2063 stmt_ann_t ann,
2064 int insert)
2065 {
2066 tree cond = COND_EXPR_COND (stmt);
2067
2068 if (COMPARISON_CLASS_P (cond))
2069 {
2070 tree op0 = TREE_OPERAND (cond, 0);
2071 tree op1 = TREE_OPERAND (cond, 1);
2072
2073 if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1))
2074 {
2075 int limit;
2076 tree low, high, cond_low, cond_high;
2077 int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
2078 varray_type vrp_records;
2079 struct vrp_element *element;
2080 struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
2081 void **slot;
2082
2083 /* First see if we have test of an SSA_NAME against a constant
2084 where the SSA_NAME is defined by an earlier typecast which
2085 is irrelevant when performing tests against the given
2086 constant. */
2087 if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
2088 {
2089 tree new_cond = find_equivalent_equality_comparison (cond);
2090
2091 if (new_cond)
2092 {
2093 /* Update the statement to use the new equivalent
2094 condition. */
2095 COND_EXPR_COND (stmt) = new_cond;
2096
2097 /* If this is not a real stmt, ann will be NULL and we
2098 avoid processing the operands. */
2099 if (ann)
2100 modify_stmt (stmt);
2101
2102 /* Lookup the condition and return its known value if it
2103 exists. */
2104 new_cond = lookup_avail_expr (stmt, insert);
2105 if (new_cond)
2106 return new_cond;
2107
2108 /* The operands have changed, so update op0 and op1. */
2109 op0 = TREE_OPERAND (cond, 0);
2110 op1 = TREE_OPERAND (cond, 1);
2111 }
2112 }
2113
2114 /* Consult the value range records for this variable (if they exist)
2115 to see if we can eliminate or simplify this conditional.
2116
2117 Note two tests are necessary to determine no records exist.
2118 First we have to see if the virtual array exists, if it
2119 exists, then we have to check its active size.
2120
2121 Also note the vast majority of conditionals are not testing
2122 a variable which has had its range constrained by an earlier
2123 conditional. So this filter avoids a lot of unnecessary work. */
2124 vrp_hash_elt.var = op0;
2125 vrp_hash_elt.records = NULL;
2126 slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT);
2127 if (slot == NULL)
2128 return NULL;
2129
2130 vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
2131 vrp_records = vrp_hash_elt_p->records;
2132 if (vrp_records == NULL)
2133 return NULL;
2134
2135 limit = VARRAY_ACTIVE_SIZE (vrp_records);
2136
2137 /* If we have no value range records for this variable, or we are
2138 unable to extract a range for this condition, then there is
2139 nothing to do. */
2140 if (limit == 0
2141 || ! extract_range_from_cond (cond, &cond_high,
2142 &cond_low, &cond_inverted))
2143 return NULL;
2144
2145 /* We really want to avoid unnecessary computations of range
2146 info. So all ranges are computed lazily; this avoids a
2147 lot of unnecessary work. i.e., we record the conditional,
2148 but do not process how it constrains the variable's
2149 potential values until we know that processing the condition
2150 could be helpful.
2151
2152 However, we do not want to have to walk a potentially long
2153 list of ranges, nor do we want to compute a variable's
2154 range more than once for a given path.
2155
2156 Luckily, each time we encounter a conditional that can not
2157 be otherwise optimized we will end up here and we will
2158 compute the necessary range information for the variable
2159 used in this condition.
2160
2161 Thus you can conclude that there will never be more than one
2162 conditional associated with a variable which has not been
2163 processed. So we never need to merge more than one new
2164 conditional into the current range.
2165
2166 These properties also help us avoid unnecessary work. */
2167 element
2168 = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records, limit - 1);
2169
2170 if (element->high && element->low)
2171 {
2172 /* The last element has been processed, so there is no range
2173 merging to do, we can simply use the high/low values
2174 recorded in the last element. */
2175 low = element->low;
2176 high = element->high;
2177 }
2178 else
2179 {
2180 tree tmp_high, tmp_low;
2181 int dummy;
2182
2183 /* The last element has not been processed. Process it now.
2184 record_range should ensure for cond inverted is not set.
2185 This call can only fail if cond is x < min or x > max,
2186 which fold should have optimized into false.
2187 If that doesn't happen, just pretend all values are
2188 in the range. */
2189 if (! extract_range_from_cond (element->cond, &tmp_high,
2190 &tmp_low, &dummy))
2191 gcc_unreachable ();
2192 else
2193 gcc_assert (dummy == 0);
2194
2195 /* If this is the only element, then no merging is necessary,
2196 the high/low values from extract_range_from_cond are all
2197 we need. */
2198 if (limit == 1)
2199 {
2200 low = tmp_low;
2201 high = tmp_high;
2202 }
2203 else
2204 {
2205 /* Get the high/low value from the previous element. */
2206 struct vrp_element *prev
2207 = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records,
2208 limit - 2);
2209 low = prev->low;
2210 high = prev->high;
2211
2212 /* Merge in this element's range with the range from the
2213 previous element.
2214
2215 The low value for the merged range is the maximum of
2216 the previous low value and the low value of this record.
2217
2218 Similarly the high value for the merged range is the
2219 minimum of the previous high value and the high value of
2220 this record. */
2221 low = (tree_int_cst_compare (low, tmp_low) == 1
2222 ? low : tmp_low);
2223 high = (tree_int_cst_compare (high, tmp_high) == -1
2224 ? high : tmp_high);
2225 }
2226
2227 /* And record the computed range. */
2228 element->low = low;
2229 element->high = high;
2230
2231 }
2232
2233 /* After we have constrained this variable's potential values,
2234 we try to determine the result of the given conditional.
2235
2236 To simplify later tests, first determine if the current
2237 low value is the same low value as the conditional.
2238 Similarly for the current high value and the high value
2239 for the conditional. */
2240 lowequal = tree_int_cst_equal (low, cond_low);
2241 highequal = tree_int_cst_equal (high, cond_high);
2242
2243 if (lowequal && highequal)
2244 return (cond_inverted ? boolean_false_node : boolean_true_node);
2245
2246 /* To simplify the overlap/subset tests below we may want
2247 to swap the two ranges so that the larger of the two
2248 ranges occurs "first". */
2249 swapped = 0;
2250 if (tree_int_cst_compare (low, cond_low) == 1
2251 || (lowequal
2252 && tree_int_cst_compare (cond_high, high) == 1))
2253 {
2254 tree temp;
2255
2256 swapped = 1;
2257 temp = low;
2258 low = cond_low;
2259 cond_low = temp;
2260 temp = high;
2261 high = cond_high;
2262 cond_high = temp;
2263 }
2264
2265 /* Now determine if there is no overlap in the ranges
2266 or if the second range is a subset of the first range. */
2267 no_overlap = tree_int_cst_lt (high, cond_low);
2268 subset = tree_int_cst_compare (cond_high, high) != 1;
2269
2270 /* If there was no overlap in the ranges, then this conditional
2271 always has a false value (unless we had to invert this
2272 conditional, in which case it always has a true value). */
2273 if (no_overlap)
2274 return (cond_inverted ? boolean_true_node : boolean_false_node);
2275
2276 /* If the current range is a subset of the condition's range,
2277 then this conditional always has a true value (unless we
2278 had to invert this conditional, in which case it always
2279 has a true value). */
2280 if (subset && swapped)
2281 return (cond_inverted ? boolean_false_node : boolean_true_node);
2282
2283 /* We were unable to determine the result of the conditional.
2284 However, we may be able to simplify the conditional. First
2285 merge the ranges in the same manner as range merging above. */
2286 low = tree_int_cst_compare (low, cond_low) == 1 ? low : cond_low;
2287 high = tree_int_cst_compare (high, cond_high) == -1 ? high : cond_high;
2288
2289 /* If the range has converged to a single point, then turn this
2290 into an equality comparison. */
2291 if (TREE_CODE (cond) != EQ_EXPR
2292 && TREE_CODE (cond) != NE_EXPR
2293 && tree_int_cst_equal (low, high))
2294 {
2295 TREE_SET_CODE (cond, EQ_EXPR);
2296 TREE_OPERAND (cond, 1) = high;
2297 }
2298 }
2299 }
2300 return 0;
2301 }
2302
2303 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2304 result. This routine attempts to find equivalent forms of the
2305 condition which we may be able to optimize better. */
2306
2307 static tree
2308 simplify_switch_and_lookup_avail_expr (tree stmt, int insert)
2309 {
2310 tree cond = SWITCH_COND (stmt);
2311 tree def, to, ti;
2312
2313 /* The optimization that we really care about is removing unnecessary
2314 casts. That will let us do much better in propagating the inferred
2315 constant at the switch target. */
2316 if (TREE_CODE (cond) == SSA_NAME)
2317 {
2318 def = SSA_NAME_DEF_STMT (cond);
2319 if (TREE_CODE (def) == MODIFY_EXPR)
2320 {
2321 def = TREE_OPERAND (def, 1);
2322 if (TREE_CODE (def) == NOP_EXPR)
2323 {
2324 int need_precision;
2325 bool fail;
2326
2327 def = TREE_OPERAND (def, 0);
2328
2329 #ifdef ENABLE_CHECKING
2330 /* ??? Why was Jeff testing this? We are gimple... */
2331 gcc_assert (is_gimple_val (def));
2332 #endif
2333
2334 to = TREE_TYPE (cond);
2335 ti = TREE_TYPE (def);
2336
2337 /* If we have an extension that preserves value, then we
2338 can copy the source value into the switch. */
2339
2340 need_precision = TYPE_PRECISION (ti);
2341 fail = false;
2342 if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
2343 fail = true;
2344 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
2345 need_precision += 1;
2346 if (TYPE_PRECISION (to) < need_precision)
2347 fail = true;
2348
2349 if (!fail)
2350 {
2351 SWITCH_COND (stmt) = def;
2352 modify_stmt (stmt);
2353
2354 return lookup_avail_expr (stmt, insert);
2355 }
2356 }
2357 }
2358 }
2359
2360 return 0;
2361 }
2362
2363
2364 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2365 known value for that SSA_NAME (or NULL if no value is known).
2366
2367 NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
2368 even if we don't know their precise value.
2369
2370 Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
2371 nodes of the successors of BB. */
2372
2373 static void
2374 cprop_into_successor_phis (basic_block bb, bitmap nonzero_vars)
2375 {
2376 edge e;
2377 edge_iterator ei;
2378
2379 FOR_EACH_EDGE (e, ei, bb->succs)
2380 {
2381 tree phi;
2382 int indx;
2383
2384 /* If this is an abnormal edge, then we do not want to copy propagate
2385 into the PHI alternative associated with this edge. */
2386 if (e->flags & EDGE_ABNORMAL)
2387 continue;
2388
2389 phi = phi_nodes (e->dest);
2390 if (! phi)
2391 continue;
2392
2393 indx = e->dest_idx;
2394 for ( ; phi; phi = PHI_CHAIN (phi))
2395 {
2396 tree new;
2397 use_operand_p orig_p;
2398 tree orig;
2399
2400 /* The alternative may be associated with a constant, so verify
2401 it is an SSA_NAME before doing anything with it. */
2402 orig_p = PHI_ARG_DEF_PTR (phi, indx);
2403 orig = USE_FROM_PTR (orig_p);
2404 if (TREE_CODE (orig) != SSA_NAME)
2405 continue;
2406
2407 /* If the alternative is known to have a nonzero value, record
2408 that fact in the PHI node itself for future use. */
2409 if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
2410 PHI_ARG_NONZERO (phi, indx) = true;
2411
2412 /* If we have *ORIG_P in our constant/copy table, then replace
2413 ORIG_P with its value in our constant/copy table. */
2414 new = SSA_NAME_VALUE (orig);
2415 if (new
2416 && (TREE_CODE (new) == SSA_NAME
2417 || is_gimple_min_invariant (new))
2418 && may_propagate_copy (orig, new))
2419 {
2420 propagate_value (orig_p, new);
2421 }
2422 }
2423 }
2424 }
2425
2426 /* We have finished optimizing BB, record any information implied by
2427 taking a specific outgoing edge from BB. */
2428
2429 static void
2430 record_edge_info (basic_block bb)
2431 {
2432 block_stmt_iterator bsi = bsi_last (bb);
2433 struct edge_info *edge_info;
2434
2435 if (! bsi_end_p (bsi))
2436 {
2437 tree stmt = bsi_stmt (bsi);
2438
2439 if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
2440 {
2441 tree cond = SWITCH_COND (stmt);
2442
2443 if (TREE_CODE (cond) == SSA_NAME)
2444 {
2445 tree labels = SWITCH_LABELS (stmt);
2446 int i, n_labels = TREE_VEC_LENGTH (labels);
2447 tree *info = xcalloc (n_basic_blocks, sizeof (tree));
2448 edge e;
2449 edge_iterator ei;
2450
2451 for (i = 0; i < n_labels; i++)
2452 {
2453 tree label = TREE_VEC_ELT (labels, i);
2454 basic_block target_bb = label_to_block (CASE_LABEL (label));
2455
2456 if (CASE_HIGH (label)
2457 || !CASE_LOW (label)
2458 || info[target_bb->index])
2459 info[target_bb->index] = error_mark_node;
2460 else
2461 info[target_bb->index] = label;
2462 }
2463
2464 FOR_EACH_EDGE (e, ei, bb->succs)
2465 {
2466 basic_block target_bb = e->dest;
2467 tree node = info[target_bb->index];
2468
2469 if (node != NULL && node != error_mark_node)
2470 {
2471 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
2472 edge_info = allocate_edge_info (e);
2473 edge_info->lhs = cond;
2474 edge_info->rhs = x;
2475 }
2476 }
2477 free (info);
2478 }
2479 }
2480
2481 /* A COND_EXPR may create equivalences too. */
2482 if (stmt && TREE_CODE (stmt) == COND_EXPR)
2483 {
2484 tree cond = COND_EXPR_COND (stmt);
2485 edge true_edge;
2486 edge false_edge;
2487
2488 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2489
2490 /* If the conditional is a single variable 'X', record 'X = 1'
2491 for the true edge and 'X = 0' on the false edge. */
2492 if (SSA_VAR_P (cond))
2493 {
2494 struct edge_info *edge_info;
2495
2496 edge_info = allocate_edge_info (true_edge);
2497 edge_info->lhs = cond;
2498 edge_info->rhs = constant_boolean_node (1, TREE_TYPE (cond));
2499
2500 edge_info = allocate_edge_info (false_edge);
2501 edge_info->lhs = cond;
2502 edge_info->rhs = constant_boolean_node (0, TREE_TYPE (cond));
2503 }
2504 /* Equality tests may create one or two equivalences. */
2505 else if (COMPARISON_CLASS_P (cond))
2506 {
2507 tree op0 = TREE_OPERAND (cond, 0);
2508 tree op1 = TREE_OPERAND (cond, 1);
2509
2510 /* Special case comparing booleans against a constant as we
2511 know the value of OP0 on both arms of the branch. i.e., we
2512 can record an equivalence for OP0 rather than COND. */
2513 if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
2514 && TREE_CODE (op0) == SSA_NAME
2515 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
2516 && is_gimple_min_invariant (op1))
2517 {
2518 if (TREE_CODE (cond) == EQ_EXPR)
2519 {
2520 edge_info = allocate_edge_info (true_edge);
2521 edge_info->lhs = op0;
2522 edge_info->rhs = (integer_zerop (op1)
2523 ? boolean_false_node
2524 : boolean_true_node);
2525
2526 edge_info = allocate_edge_info (false_edge);
2527 edge_info->lhs = op0;
2528 edge_info->rhs = (integer_zerop (op1)
2529 ? boolean_true_node
2530 : boolean_false_node);
2531 }
2532 else
2533 {
2534 edge_info = allocate_edge_info (true_edge);
2535 edge_info->lhs = op0;
2536 edge_info->rhs = (integer_zerop (op1)
2537 ? boolean_true_node
2538 : boolean_false_node);
2539
2540 edge_info = allocate_edge_info (false_edge);
2541 edge_info->lhs = op0;
2542 edge_info->rhs = (integer_zerop (op1)
2543 ? boolean_false_node
2544 : boolean_true_node);
2545 }
2546 }
2547
2548 else if (is_gimple_min_invariant (op0)
2549 && (TREE_CODE (op1) == SSA_NAME
2550 || is_gimple_min_invariant (op1)))
2551 {
2552 tree inverted = invert_truthvalue (cond);
2553 struct edge_info *edge_info;
2554
2555 edge_info = allocate_edge_info (true_edge);
2556 record_conditions (edge_info, cond, inverted);
2557
2558 if (TREE_CODE (cond) == EQ_EXPR)
2559 {
2560 edge_info->lhs = op1;
2561 edge_info->rhs = op0;
2562 }
2563
2564 edge_info = allocate_edge_info (false_edge);
2565 record_conditions (edge_info, inverted, cond);
2566
2567 if (TREE_CODE (cond) == NE_EXPR)
2568 {
2569 edge_info->lhs = op1;
2570 edge_info->rhs = op0;
2571 }
2572 }
2573
2574 else if (TREE_CODE (op0) == SSA_NAME
2575 && (is_gimple_min_invariant (op1)
2576 || TREE_CODE (op1) == SSA_NAME))
2577 {
2578 tree inverted = invert_truthvalue (cond);
2579 struct edge_info *edge_info;
2580
2581 edge_info = allocate_edge_info (true_edge);
2582 record_conditions (edge_info, cond, inverted);
2583
2584 if (TREE_CODE (cond) == EQ_EXPR)
2585 {
2586 edge_info->lhs = op0;
2587 edge_info->rhs = op1;
2588 }
2589
2590 edge_info = allocate_edge_info (false_edge);
2591 record_conditions (edge_info, inverted, cond);
2592
2593 if (TREE_CODE (cond) == NE_EXPR)
2594 {
2595 edge_info->lhs = op0;
2596 edge_info->rhs = op1;
2597 }
2598 }
2599 }
2600
2601 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
2602 }
2603 }
2604 }
2605
2606 /* Propagate information from BB to its outgoing edges.
2607
2608 This can include equivalency information implied by control statements
2609 at the end of BB and const/copy propagation into PHIs in BB's
2610 successor blocks. */
2611
2612 static void
2613 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2614 basic_block bb)
2615 {
2616
2617 record_edge_info (bb);
2618 cprop_into_successor_phis (bb, nonzero_vars);
2619 }
2620
2621 /* Search for redundant computations in STMT. If any are found, then
2622 replace them with the variable holding the result of the computation.
2623
2624 If safe, record this expression into the available expression hash
2625 table. */
2626
2627 static bool
2628 eliminate_redundant_computations (struct dom_walk_data *walk_data,
2629 tree stmt, stmt_ann_t ann)
2630 {
2631 v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
2632 tree *expr_p, def = NULL_TREE;
2633 bool insert = true;
2634 tree cached_lhs;
2635 bool retval = false;
2636
2637 if (TREE_CODE (stmt) == MODIFY_EXPR)
2638 def = TREE_OPERAND (stmt, 0);
2639
2640 /* Certain expressions on the RHS can be optimized away, but can not
2641 themselves be entered into the hash tables. */
2642 if (ann->makes_aliased_stores
2643 || ! def
2644 || TREE_CODE (def) != SSA_NAME
2645 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
2646 || NUM_V_MAY_DEFS (v_may_defs) != 0
2647 /* Do not record equivalences for increments of ivs. This would create
2648 overlapping live ranges for a very questionable gain. */
2649 || simple_iv_increment_p (stmt))
2650 insert = false;
2651
2652 /* Check if the expression has been computed before. */
2653 cached_lhs = lookup_avail_expr (stmt, insert);
2654
2655 /* If this is an assignment and the RHS was not in the hash table,
2656 then try to simplify the RHS and lookup the new RHS in the
2657 hash table. */
2658 if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)
2659 cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data, stmt, insert);
2660 /* Similarly if this is a COND_EXPR and we did not find its
2661 expression in the hash table, simplify the condition and
2662 try again. */
2663 else if (! cached_lhs && TREE_CODE (stmt) == COND_EXPR)
2664 cached_lhs = simplify_cond_and_lookup_avail_expr (stmt, ann, insert);
2665 /* Similarly for a SWITCH_EXPR. */
2666 else if (!cached_lhs && TREE_CODE (stmt) == SWITCH_EXPR)
2667 cached_lhs = simplify_switch_and_lookup_avail_expr (stmt, insert);
2668
2669 opt_stats.num_exprs_considered++;
2670
2671 /* Get a pointer to the expression we are trying to optimize. */
2672 if (TREE_CODE (stmt) == COND_EXPR)
2673 expr_p = &COND_EXPR_COND (stmt);
2674 else if (TREE_CODE (stmt) == SWITCH_EXPR)
2675 expr_p = &SWITCH_COND (stmt);
2676 else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
2677 expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
2678 else
2679 expr_p = &TREE_OPERAND (stmt, 1);
2680
2681 /* It is safe to ignore types here since we have already done
2682 type checking in the hashing and equality routines. In fact
2683 type checking here merely gets in the way of constant
2684 propagation. Also, make sure that it is safe to propagate
2685 CACHED_LHS into *EXPR_P. */
2686 if (cached_lhs
2687 && (TREE_CODE (cached_lhs) != SSA_NAME
2688 || may_propagate_copy (*expr_p, cached_lhs)))
2689 {
2690 if (dump_file && (dump_flags & TDF_DETAILS))
2691 {
2692 fprintf (dump_file, " Replaced redundant expr '");
2693 print_generic_expr (dump_file, *expr_p, dump_flags);
2694 fprintf (dump_file, "' with '");
2695 print_generic_expr (dump_file, cached_lhs, dump_flags);
2696 fprintf (dump_file, "'\n");
2697 }
2698
2699 opt_stats.num_re++;
2700
2701 #if defined ENABLE_CHECKING
2702 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
2703 || is_gimple_min_invariant (cached_lhs));
2704 #endif
2705
2706 if (TREE_CODE (cached_lhs) == ADDR_EXPR
2707 || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
2708 && is_gimple_min_invariant (cached_lhs)))
2709 retval = true;
2710
2711 propagate_tree_value (expr_p, cached_lhs);
2712 modify_stmt (stmt);
2713 }
2714 return retval;
2715 }
2716
2717 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2718 the available expressions table or the const_and_copies table.
2719 Detect and record those equivalences. */
2720
2721 static void
2722 record_equivalences_from_stmt (tree stmt,
2723 int may_optimize_p,
2724 stmt_ann_t ann)
2725 {
2726 tree lhs = TREE_OPERAND (stmt, 0);
2727 enum tree_code lhs_code = TREE_CODE (lhs);
2728 int i;
2729
2730 if (lhs_code == SSA_NAME)
2731 {
2732 tree rhs = TREE_OPERAND (stmt, 1);
2733
2734 /* Strip away any useless type conversions. */
2735 STRIP_USELESS_TYPE_CONVERSION (rhs);
2736
2737 /* If the RHS of the assignment is a constant or another variable that
2738 may be propagated, register it in the CONST_AND_COPIES table. We
2739 do not need to record unwind data for this, since this is a true
2740 assignment and not an equivalence inferred from a comparison. All
2741 uses of this ssa name are dominated by this assignment, so unwinding
2742 just costs time and space. */
2743 if (may_optimize_p
2744 && (TREE_CODE (rhs) == SSA_NAME
2745 || is_gimple_min_invariant (rhs)))
2746 SSA_NAME_VALUE (lhs) = rhs;
2747
2748 /* alloca never returns zero and the address of a non-weak symbol
2749 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2750 stripped as they do not affect this equivalence. */
2751 while (TREE_CODE (rhs) == NOP_EXPR
2752 || TREE_CODE (rhs) == CONVERT_EXPR)
2753 rhs = TREE_OPERAND (rhs, 0);
2754
2755 if (alloca_call_p (rhs)
2756 || (TREE_CODE (rhs) == ADDR_EXPR
2757 && DECL_P (TREE_OPERAND (rhs, 0))
2758 && ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
2759 record_var_is_nonzero (lhs);
2760
2761 /* IOR of any value with a nonzero value will result in a nonzero
2762 value. Even if we do not know the exact result recording that
2763 the result is nonzero is worth the effort. */
2764 if (TREE_CODE (rhs) == BIT_IOR_EXPR
2765 && integer_nonzerop (TREE_OPERAND (rhs, 1)))
2766 record_var_is_nonzero (lhs);
2767 }
2768
2769 /* Look at both sides for pointer dereferences. If we find one, then
2770 the pointer must be nonnull and we can enter that equivalence into
2771 the hash tables. */
2772 if (flag_delete_null_pointer_checks)
2773 for (i = 0; i < 2; i++)
2774 {
2775 tree t = TREE_OPERAND (stmt, i);
2776
2777 /* Strip away any COMPONENT_REFs. */
2778 while (TREE_CODE (t) == COMPONENT_REF)
2779 t = TREE_OPERAND (t, 0);
2780
2781 /* Now see if this is a pointer dereference. */
2782 if (INDIRECT_REF_P (t))
2783 {
2784 tree op = TREE_OPERAND (t, 0);
2785
2786 /* If the pointer is a SSA variable, then enter new
2787 equivalences into the hash table. */
2788 while (TREE_CODE (op) == SSA_NAME)
2789 {
2790 tree def = SSA_NAME_DEF_STMT (op);
2791
2792 record_var_is_nonzero (op);
2793
2794 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2795 which are known to have a nonzero value. */
2796 if (def
2797 && TREE_CODE (def) == MODIFY_EXPR
2798 && TREE_CODE (TREE_OPERAND (def, 1)) == NOP_EXPR)
2799 op = TREE_OPERAND (TREE_OPERAND (def, 1), 0);
2800 else
2801 break;
2802 }
2803 }
2804 }
2805
2806 /* A memory store, even an aliased store, creates a useful
2807 equivalence. By exchanging the LHS and RHS, creating suitable
2808 vops and recording the result in the available expression table,
2809 we may be able to expose more redundant loads. */
2810 if (!ann->has_volatile_ops
2811 && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
2812 || is_gimple_min_invariant (TREE_OPERAND (stmt, 1)))
2813 && !is_gimple_reg (lhs))
2814 {
2815 tree rhs = TREE_OPERAND (stmt, 1);
2816 tree new;
2817
2818 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2819 is a constant, we need to adjust the constant to fit into the
2820 type of the LHS. If the LHS is a bitfield and the RHS is not
2821 a constant, then we can not record any equivalences for this
2822 statement since we would need to represent the widening or
2823 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2824 and should not be necessary if GCC represented bitfields
2825 properly. */
2826 if (lhs_code == COMPONENT_REF
2827 && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
2828 {
2829 if (TREE_CONSTANT (rhs))
2830 rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs);
2831 else
2832 rhs = NULL;
2833
2834 /* If the value overflowed, then we can not use this equivalence. */
2835 if (rhs && ! is_gimple_min_invariant (rhs))
2836 rhs = NULL;
2837 }
2838
2839 if (rhs)
2840 {
2841 /* Build a new statement with the RHS and LHS exchanged. */
2842 new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
2843
2844 create_ssa_artficial_load_stmt (&(ann->operands), new);
2845
2846 /* Finally enter the statement into the available expression
2847 table. */
2848 lookup_avail_expr (new, true);
2849 }
2850 }
2851 }
2852
2853 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2854 CONST_AND_COPIES. */
2855
2856 static bool
2857 cprop_operand (tree stmt, use_operand_p op_p)
2858 {
2859 bool may_have_exposed_new_symbols = false;
2860 tree val;
2861 tree op = USE_FROM_PTR (op_p);
2862
2863 /* If the operand has a known constant value or it is known to be a
2864 copy of some other variable, use the value or copy stored in
2865 CONST_AND_COPIES. */
2866 val = SSA_NAME_VALUE (op);
2867 if (val && TREE_CODE (val) != VALUE_HANDLE)
2868 {
2869 tree op_type, val_type;
2870
2871 /* Do not change the base variable in the virtual operand
2872 tables. That would make it impossible to reconstruct
2873 the renamed virtual operand if we later modify this
2874 statement. Also only allow the new value to be an SSA_NAME
2875 for propagation into virtual operands. */
2876 if (!is_gimple_reg (op)
2877 && (get_virtual_var (val) != get_virtual_var (op)
2878 || TREE_CODE (val) != SSA_NAME))
2879 return false;
2880
2881 /* Do not replace hard register operands in asm statements. */
2882 if (TREE_CODE (stmt) == ASM_EXPR
2883 && !may_propagate_copy_into_asm (op))
2884 return false;
2885
2886 /* Get the toplevel type of each operand. */
2887 op_type = TREE_TYPE (op);
2888 val_type = TREE_TYPE (val);
2889
2890 /* While both types are pointers, get the type of the object
2891 pointed to. */
2892 while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
2893 {
2894 op_type = TREE_TYPE (op_type);
2895 val_type = TREE_TYPE (val_type);
2896 }
2897
2898 /* Make sure underlying types match before propagating a constant by
2899 converting the constant to the proper type. Note that convert may
2900 return a non-gimple expression, in which case we ignore this
2901 propagation opportunity. */
2902 if (TREE_CODE (val) != SSA_NAME)
2903 {
2904 if (!lang_hooks.types_compatible_p (op_type, val_type))
2905 {
2906 val = fold_convert (TREE_TYPE (op), val);
2907 if (!is_gimple_min_invariant (val))
2908 return false;
2909 }
2910 }
2911
2912 /* Certain operands are not allowed to be copy propagated due
2913 to their interaction with exception handling and some GCC
2914 extensions. */
2915 else if (!may_propagate_copy (op, val))
2916 return false;
2917
2918 /* Do not propagate copies if the propagated value is at a deeper loop
2919 depth than the propagatee. Otherwise, this may move loop variant
2920 variables outside of their loops and prevent coalescing
2921 opportunities. If the value was loop invariant, it will be hoisted
2922 by LICM and exposed for copy propagation. */
2923 if (loop_depth_of_name (val) > loop_depth_of_name (op))
2924 return false;
2925
2926 /* Dump details. */
2927 if (dump_file && (dump_flags & TDF_DETAILS))
2928 {
2929 fprintf (dump_file, " Replaced '");
2930 print_generic_expr (dump_file, op, dump_flags);
2931 fprintf (dump_file, "' with %s '",
2932 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2933 print_generic_expr (dump_file, val, dump_flags);
2934 fprintf (dump_file, "'\n");
2935 }
2936
2937 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2938 that we may have exposed a new symbol for SSA renaming. */
2939 if (TREE_CODE (val) == ADDR_EXPR
2940 || (POINTER_TYPE_P (TREE_TYPE (op))
2941 && is_gimple_min_invariant (val)))
2942 may_have_exposed_new_symbols = true;
2943
2944 propagate_value (op_p, val);
2945
2946 /* And note that we modified this statement. This is now
2947 safe, even if we changed virtual operands since we will
2948 rescan the statement and rewrite its operands again. */
2949 modify_stmt (stmt);
2950 }
2951 return may_have_exposed_new_symbols;
2952 }
2953
2954 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2955 known value for that SSA_NAME (or NULL if no value is known).
2956
2957 Propagate values from CONST_AND_COPIES into the uses, vuses and
2958 v_may_def_ops of STMT. */
2959
2960 static bool
2961 cprop_into_stmt (tree stmt)
2962 {
2963 bool may_have_exposed_new_symbols = false;
2964 use_operand_p op_p;
2965 ssa_op_iter iter;
2966 tree rhs;
2967
2968 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2969 {
2970 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2971 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
2972 }
2973
2974 if (may_have_exposed_new_symbols)
2975 {
2976 rhs = get_rhs (stmt);
2977 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2978 recompute_tree_invarant_for_addr_expr (rhs);
2979 }
2980
2981 return may_have_exposed_new_symbols;
2982 }
2983
2984
2985 /* Optimize the statement pointed by iterator SI.
2986
2987 We try to perform some simplistic global redundancy elimination and
2988 constant propagation:
2989
2990 1- To detect global redundancy, we keep track of expressions that have
2991 been computed in this block and its dominators. If we find that the
2992 same expression is computed more than once, we eliminate repeated
2993 computations by using the target of the first one.
2994
2995 2- Constant values and copy assignments. This is used to do very
2996 simplistic constant and copy propagation. When a constant or copy
2997 assignment is found, we map the value on the RHS of the assignment to
2998 the variable in the LHS in the CONST_AND_COPIES table. */
2999
3000 static void
3001 optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
3002 block_stmt_iterator si)
3003 {
3004 stmt_ann_t ann;
3005 tree stmt;
3006 bool may_optimize_p;
3007 bool may_have_exposed_new_symbols = false;
3008
3009 stmt = bsi_stmt (si);
3010
3011 get_stmt_operands (stmt);
3012 ann = stmt_ann (stmt);
3013 opt_stats.num_stmts++;
3014 may_have_exposed_new_symbols = false;
3015
3016 if (dump_file && (dump_flags & TDF_DETAILS))
3017 {
3018 fprintf (dump_file, "Optimizing statement ");
3019 print_generic_stmt (dump_file, stmt, TDF_SLIM);
3020 }
3021
3022 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
3023 may_have_exposed_new_symbols = cprop_into_stmt (stmt);
3024
3025 /* If the statement has been modified with constant replacements,
3026 fold its RHS before checking for redundant computations. */
3027 if (ann->modified)
3028 {
3029 /* Try to fold the statement making sure that STMT is kept
3030 up to date. */
3031 if (fold_stmt (bsi_stmt_ptr (si)))
3032 {
3033 stmt = bsi_stmt (si);
3034 ann = stmt_ann (stmt);
3035
3036 if (dump_file && (dump_flags & TDF_DETAILS))
3037 {
3038 fprintf (dump_file, " Folded to: ");
3039 print_generic_stmt (dump_file, stmt, TDF_SLIM);
3040 }
3041 }
3042
3043 /* Constant/copy propagation above may change the set of
3044 virtual operands associated with this statement. Folding
3045 may remove the need for some virtual operands.
3046
3047 Indicate we will need to rescan and rewrite the statement. */
3048 may_have_exposed_new_symbols = true;
3049 }
3050
3051 /* Check for redundant computations. Do this optimization only
3052 for assignments that have no volatile ops and conditionals. */
3053 may_optimize_p = (!ann->has_volatile_ops
3054 && ((TREE_CODE (stmt) == RETURN_EXPR
3055 && TREE_OPERAND (stmt, 0)
3056 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR
3057 && ! (TREE_SIDE_EFFECTS
3058 (TREE_OPERAND (TREE_OPERAND (stmt, 0), 1))))
3059 || (TREE_CODE (stmt) == MODIFY_EXPR
3060 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
3061 || TREE_CODE (stmt) == COND_EXPR
3062 || TREE_CODE (stmt) == SWITCH_EXPR));
3063
3064 if (may_optimize_p)
3065 may_have_exposed_new_symbols
3066 |= eliminate_redundant_computations (walk_data, stmt, ann);
3067
3068 /* Record any additional equivalences created by this statement. */
3069 if (TREE_CODE (stmt) == MODIFY_EXPR)
3070 record_equivalences_from_stmt (stmt,
3071 may_optimize_p,
3072 ann);
3073
3074 register_definitions_for_stmt (stmt);
3075
3076 /* If STMT is a COND_EXPR and it was modified, then we may know
3077 where it goes. If that is the case, then mark the CFG as altered.
3078
3079 This will cause us to later call remove_unreachable_blocks and
3080 cleanup_tree_cfg when it is safe to do so. It is not safe to
3081 clean things up here since removal of edges and such can trigger
3082 the removal of PHI nodes, which in turn can release SSA_NAMEs to
3083 the manager.
3084
3085 That's all fine and good, except that once SSA_NAMEs are released
3086 to the manager, we must not call create_ssa_name until all references
3087 to released SSA_NAMEs have been eliminated.
3088
3089 All references to the deleted SSA_NAMEs can not be eliminated until
3090 we remove unreachable blocks.
3091
3092 We can not remove unreachable blocks until after we have completed
3093 any queued jump threading.
3094
3095 We can not complete any queued jump threads until we have taken
3096 appropriate variables out of SSA form. Taking variables out of
3097 SSA form can call create_ssa_name and thus we lose.
3098
3099 Ultimately I suspect we're going to need to change the interface
3100 into the SSA_NAME manager. */
3101
3102 if (ann->modified)
3103 {
3104 tree val = NULL;
3105
3106 if (TREE_CODE (stmt) == COND_EXPR)
3107 val = COND_EXPR_COND (stmt);
3108 else if (TREE_CODE (stmt) == SWITCH_EXPR)
3109 val = SWITCH_COND (stmt);
3110
3111 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
3112 cfg_altered = true;
3113
3114 /* If we simplified a statement in such a way as to be shown that it
3115 cannot trap, update the eh information and the cfg to match. */
3116 if (maybe_clean_eh_stmt (stmt))
3117 {
3118 bitmap_set_bit (need_eh_cleanup, bb->index);
3119 if (dump_file && (dump_flags & TDF_DETAILS))
3120 fprintf (dump_file, " Flagged to clear EH edges.\n");
3121 }
3122 }
3123
3124 if (may_have_exposed_new_symbols)
3125 VEC_safe_push (tree_on_heap, stmts_to_rescan, bsi_stmt (si));
3126 }
3127
3128 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
3129 available expression hashtable, then return the LHS from the hash
3130 table.
3131
3132 If INSERT is true, then we also update the available expression
3133 hash table to account for the changes made to STMT. */
3134
3135 static tree
3136 update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs, bool insert)
3137 {
3138 tree cached_lhs = NULL;
3139
3140 /* Remove the old entry from the hash table. */
3141 if (insert)
3142 {
3143 struct expr_hash_elt element;
3144
3145 initialize_hash_element (stmt, NULL, &element);
3146 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
3147 }
3148
3149 /* Now update the RHS of the assignment. */
3150 TREE_OPERAND (stmt, 1) = new_rhs;
3151
3152 /* Now lookup the updated statement in the hash table. */
3153 cached_lhs = lookup_avail_expr (stmt, insert);
3154
3155 /* We have now called lookup_avail_expr twice with two different
3156 versions of this same statement, once in optimize_stmt, once here.
3157
3158 We know the call in optimize_stmt did not find an existing entry
3159 in the hash table, so a new entry was created. At the same time
3160 this statement was pushed onto the AVAIL_EXPRS_STACK vector.
3161
3162 If this call failed to find an existing entry on the hash table,
3163 then the new version of this statement was entered into the
3164 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
3165 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
3166
3167 If this call succeeded, we still have one copy of this statement
3168 on the BLOCK_AVAIL_EXPRs vector.
3169
3170 For both cases, we need to pop the most recent entry off the
3171 BLOCK_AVAIL_EXPRs vector. For the case where we never found this
3172 statement in the hash tables, that will leave precisely one
3173 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
3174 we found a copy of this statement in the second hash table lookup
3175 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
3176 if (insert)
3177 VEC_pop (tree_on_heap, avail_exprs_stack);
3178
3179 /* And make sure we record the fact that we modified this
3180 statement. */
3181 modify_stmt (stmt);
3182
3183 return cached_lhs;
3184 }
3185
3186 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
3187 found, return its LHS. Otherwise insert STMT in the table and return
3188 NULL_TREE.
3189
3190 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
3191 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
3192 can be removed when we finish processing this block and its children.
3193
3194 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
3195 contains no CALL_EXPR on its RHS and makes no volatile nor
3196 aliased references. */
3197
3198 static tree
3199 lookup_avail_expr (tree stmt, bool insert)
3200 {
3201 void **slot;
3202 tree lhs;
3203 tree temp;
3204 struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
3205
3206 lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
3207
3208 initialize_hash_element (stmt, lhs, element);
3209
3210 /* Don't bother remembering constant assignments and copy operations.
3211 Constants and copy operations are handled by the constant/copy propagator
3212 in optimize_stmt. */
3213 if (TREE_CODE (element->rhs) == SSA_NAME
3214 || is_gimple_min_invariant (element->rhs))
3215 {
3216 free (element);
3217 return NULL_TREE;
3218 }
3219
3220 /* If this is an equality test against zero, see if we have recorded a
3221 nonzero value for the variable in question. */
3222 if ((TREE_CODE (element->rhs) == EQ_EXPR
3223 || TREE_CODE (element->rhs) == NE_EXPR)
3224 && TREE_CODE (TREE_OPERAND (element->rhs, 0)) == SSA_NAME
3225 && integer_zerop (TREE_OPERAND (element->rhs, 1)))
3226 {
3227 int indx = SSA_NAME_VERSION (TREE_OPERAND (element->rhs, 0));
3228
3229 if (bitmap_bit_p (nonzero_vars, indx))
3230 {
3231 tree t = element->rhs;
3232 free (element);
3233
3234 if (TREE_CODE (t) == EQ_EXPR)
3235 return boolean_false_node;
3236 else
3237 return boolean_true_node;
3238 }
3239 }
3240
3241 /* Finally try to find the expression in the main expression hash table. */
3242 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
3243 (insert ? INSERT : NO_INSERT));
3244 if (slot == NULL)
3245 {
3246 free (element);
3247 return NULL_TREE;
3248 }
3249
3250 if (*slot == NULL)
3251 {
3252 *slot = (void *) element;
3253 VEC_safe_push (tree_on_heap, avail_exprs_stack,
3254 stmt ? stmt : element->rhs);
3255 return NULL_TREE;
3256 }
3257
3258 /* Extract the LHS of the assignment so that it can be used as the current
3259 definition of another variable. */
3260 lhs = ((struct expr_hash_elt *)*slot)->lhs;
3261
3262 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
3263 use the value from the const_and_copies table. */
3264 if (TREE_CODE (lhs) == SSA_NAME)
3265 {
3266 temp = SSA_NAME_VALUE (lhs);
3267 if (temp && TREE_CODE (temp) != VALUE_HANDLE)
3268 lhs = temp;
3269 }
3270
3271 free (element);
3272 return lhs;
3273 }
3274
3275 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
3276 range of values that result in the conditional having a true value.
3277
3278 Return true if we are successful in extracting a range from COND and
3279 false if we are unsuccessful. */
3280
3281 static bool
3282 extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
3283 {
3284 tree op1 = TREE_OPERAND (cond, 1);
3285 tree high, low, type;
3286 int inverted;
3287
3288 type = TREE_TYPE (op1);
3289
3290 /* Experiments have shown that it's rarely, if ever useful to
3291 record ranges for enumerations. Presumably this is due to
3292 the fact that they're rarely used directly. They are typically
3293 cast into an integer type and used that way. */
3294 if (TREE_CODE (type) != INTEGER_TYPE
3295 /* We don't know how to deal with types with variable bounds. */
3296 || TREE_CODE (TYPE_MIN_VALUE (type)) != INTEGER_CST
3297 || TREE_CODE (TYPE_MAX_VALUE (type)) != INTEGER_CST)
3298 return 0;
3299
3300 switch (TREE_CODE (cond))
3301 {
3302 case EQ_EXPR:
3303 high = low = op1;
3304 inverted = 0;
3305 break;
3306
3307 case NE_EXPR:
3308 high = low = op1;
3309 inverted = 1;
3310 break;
3311
3312 case GE_EXPR:
3313 low = op1;
3314 high = TYPE_MAX_VALUE (type);
3315 inverted = 0;
3316 break;
3317
3318 case GT_EXPR:
3319 high = TYPE_MAX_VALUE (type);
3320 if (!tree_int_cst_lt (op1, high))
3321 return 0;
3322 low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);
3323 inverted = 0;
3324 break;
3325
3326 case LE_EXPR:
3327 high = op1;
3328 low = TYPE_MIN_VALUE (type);
3329 inverted = 0;
3330 break;
3331
3332 case LT_EXPR:
3333 low = TYPE_MIN_VALUE (type);
3334 if (!tree_int_cst_lt (low, op1))
3335 return 0;
3336 high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);
3337 inverted = 0;
3338 break;
3339
3340 default:
3341 return 0;
3342 }
3343
3344 *hi_p = high;
3345 *lo_p = low;
3346 *inverted_p = inverted;
3347 return 1;
3348 }
3349
3350 /* Record a range created by COND for basic block BB. */
3351
3352 static void
3353 record_range (tree cond, basic_block bb)
3354 {
3355 enum tree_code code = TREE_CODE (cond);
3356
3357 /* We explicitly ignore NE_EXPRs and all the unordered comparisons.
3358 They rarely allow for meaningful range optimizations and significantly
3359 complicate the implementation. */
3360 if ((code == LT_EXPR || code == LE_EXPR || code == GT_EXPR
3361 || code == GE_EXPR || code == EQ_EXPR)
3362 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond, 1))) == INTEGER_TYPE)
3363 {
3364 struct vrp_hash_elt *vrp_hash_elt;
3365 struct vrp_element *element;
3366 varray_type *vrp_records_p;
3367 void **slot;
3368
3369
3370 vrp_hash_elt = xmalloc (sizeof (struct vrp_hash_elt));
3371 vrp_hash_elt->var = TREE_OPERAND (cond, 0);
3372 vrp_hash_elt->records = NULL;
3373 slot = htab_find_slot (vrp_data, vrp_hash_elt, INSERT);
3374
3375 if (*slot == NULL)
3376 *slot = (void *) vrp_hash_elt;
3377 else
3378 free (vrp_hash_elt);
3379
3380 vrp_hash_elt = (struct vrp_hash_elt *) *slot;
3381 vrp_records_p = &vrp_hash_elt->records;
3382
3383 element = ggc_alloc (sizeof (struct vrp_element));
3384 element->low = NULL;
3385 element->high = NULL;
3386 element->cond = cond;
3387 element->bb = bb;
3388
3389 if (*vrp_records_p == NULL)
3390 VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
3391
3392 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
3393 VEC_safe_push (tree_on_heap, vrp_variables_stack, TREE_OPERAND (cond, 0));
3394 }
3395 }
3396
3397 /* Hashing and equality functions for VRP_DATA.
3398
3399 Since this hash table is addressed by SSA_NAMEs, we can hash on
3400 their version number and equality can be determined with a
3401 pointer comparison. */
3402
3403 static hashval_t
3404 vrp_hash (const void *p)
3405 {
3406 tree var = ((struct vrp_hash_elt *)p)->var;
3407
3408 return SSA_NAME_VERSION (var);
3409 }
3410
3411 static int
3412 vrp_eq (const void *p1, const void *p2)
3413 {
3414 tree var1 = ((struct vrp_hash_elt *)p1)->var;
3415 tree var2 = ((struct vrp_hash_elt *)p2)->var;
3416
3417 return var1 == var2;
3418 }
3419
3420 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
3421 MODIFY_EXPR statements. We compute a value number for expressions using
3422 the code of the expression and the SSA numbers of its operands. */
3423
3424 static hashval_t
3425 avail_expr_hash (const void *p)
3426 {
3427 stmt_ann_t ann = ((struct expr_hash_elt *)p)->ann;
3428 tree rhs = ((struct expr_hash_elt *)p)->rhs;
3429 hashval_t val = 0;
3430 size_t i;
3431 vuse_optype vuses;
3432
3433 /* iterative_hash_expr knows how to deal with any expression and
3434 deals with commutative operators as well, so just use it instead
3435 of duplicating such complexities here. */
3436 val = iterative_hash_expr (rhs, val);
3437
3438 /* If the hash table entry is not associated with a statement, then we
3439 can just hash the expression and not worry about virtual operands
3440 and such. */
3441 if (!ann)
3442 return val;
3443
3444 /* Add the SSA version numbers of every vuse operand. This is important
3445 because compound variables like arrays are not renamed in the
3446 operands. Rather, the rename is done on the virtual variable
3447 representing all the elements of the array. */
3448 vuses = VUSE_OPS (ann);
3449 for (i = 0; i < NUM_VUSES (vuses); i++)
3450 val = iterative_hash_expr (VUSE_OP (vuses, i), val);
3451
3452 return val;
3453 }
3454
3455 static hashval_t
3456 real_avail_expr_hash (const void *p)
3457 {
3458 return ((const struct expr_hash_elt *)p)->hash;
3459 }
3460
3461 static int
3462 avail_expr_eq (const void *p1, const void *p2)
3463 {
3464 stmt_ann_t ann1 = ((struct expr_hash_elt *)p1)->ann;
3465 tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
3466 stmt_ann_t ann2 = ((struct expr_hash_elt *)p2)->ann;
3467 tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
3468
3469 /* If they are the same physical expression, return true. */
3470 if (rhs1 == rhs2 && ann1 == ann2)
3471 return true;
3472
3473 /* If their codes are not equal, then quit now. */
3474 if (TREE_CODE (rhs1) != TREE_CODE (rhs2))
3475 return false;
3476
3477 /* In case of a collision, both RHS have to be identical and have the
3478 same VUSE operands. */
3479 if ((TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
3480 || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
3481 && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
3482 {
3483 vuse_optype ops1 = NULL;
3484 vuse_optype ops2 = NULL;
3485 size_t num_ops1 = 0;
3486 size_t num_ops2 = 0;
3487 size_t i;
3488
3489 if (ann1)
3490 {
3491 ops1 = VUSE_OPS (ann1);
3492 num_ops1 = NUM_VUSES (ops1);
3493 }
3494
3495 if (ann2)
3496 {
3497 ops2 = VUSE_OPS (ann2);
3498 num_ops2 = NUM_VUSES (ops2);
3499 }
3500
3501 /* If the number of virtual uses is different, then we consider
3502 them not equal. */
3503 if (num_ops1 != num_ops2)
3504 return false;
3505
3506 for (i = 0; i < num_ops1; i++)
3507 if (VUSE_OP (ops1, i) != VUSE_OP (ops2, i))
3508 return false;
3509
3510 gcc_assert (((struct expr_hash_elt *)p1)->hash
3511 == ((struct expr_hash_elt *)p2)->hash);
3512 return true;
3513 }
3514
3515 return false;
3516 }
3517
3518 /* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
3519 register register all objects set by this statement into BLOCK_DEFS_P
3520 and CURRDEFS. */
3521
3522 static void
3523 register_definitions_for_stmt (tree stmt)
3524 {
3525 tree def;
3526 ssa_op_iter iter;
3527
3528 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
3529 {
3530
3531 /* FIXME: We shouldn't be registering new defs if the variable
3532 doesn't need to be renamed. */
3533 register_new_def (def, &block_defs_stack);
3534 }
3535 }
3536