|
111
|
1 /* Header file for SSA dominator optimizations.
|
|
|
2 Copyright (C) 2013-2017 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify it under
|
|
|
7 the terms of the GNU General Public License as published by the Free
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
9 version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "function.h"
|
|
|
24 #include "basic-block.h"
|
|
|
25 #include "tree.h"
|
|
|
26 #include "gimple.h"
|
|
|
27 #include "tree-pass.h"
|
|
|
28 #include "tree-pretty-print.h"
|
|
|
29 #include "tree-ssa-scopedtables.h"
|
|
|
30 #include "tree-ssa-threadedge.h"
|
|
|
31 #include "stor-layout.h"
|
|
|
32 #include "fold-const.h"
|
|
|
33 #include "tree-eh.h"
|
|
|
34 #include "internal-fn.h"
|
|
|
35 #include "tree-dfa.h"
|
|
|
36 #include "options.h"
|
|
|
37 #include "params.h"
|
|
|
38
|
|
|
39 static bool hashable_expr_equal_p (const struct hashable_expr *,
|
|
|
40 const struct hashable_expr *);
|
|
|
41
|
|
|
42 /* Initialize local stacks for this optimizer and record equivalences
|
|
|
43 upon entry to BB. Equivalences can come from the edge traversed to
|
|
|
44 reach BB or they may come from PHI nodes at the start of BB. */
|
|
|
45
|
|
|
46 /* Pop items off the unwinding stack, removing each from the hash table
|
|
|
47 until a marker is encountered. */
|
|
|
48
|
|
|
49 void
|
|
|
50 avail_exprs_stack::pop_to_marker ()
|
|
|
51 {
|
|
|
52 /* Remove all the expressions made available in this block. */
|
|
|
53 while (m_stack.length () > 0)
|
|
|
54 {
|
|
|
55 std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop ();
|
|
|
56 expr_hash_elt **slot;
|
|
|
57
|
|
|
58 if (victim.first == NULL)
|
|
|
59 break;
|
|
|
60
|
|
|
61 /* This must precede the actual removal from the hash table,
|
|
|
62 as ELEMENT and the table entry may share a call argument
|
|
|
63 vector which will be freed during removal. */
|
|
|
64 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
65 {
|
|
|
66 fprintf (dump_file, "<<<< ");
|
|
|
67 victim.first->print (dump_file);
|
|
|
68 }
|
|
|
69
|
|
|
70 slot = m_avail_exprs->find_slot (victim.first, NO_INSERT);
|
|
|
71 gcc_assert (slot && *slot == victim.first);
|
|
|
72 if (victim.second != NULL)
|
|
|
73 {
|
|
|
74 delete *slot;
|
|
|
75 *slot = victim.second;
|
|
|
76 }
|
|
|
77 else
|
|
|
78 m_avail_exprs->clear_slot (slot);
|
|
|
79 }
|
|
|
80 }
|
|
|
81
|
|
|
82 /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
|
|
|
83 from the hash table. */
|
|
|
84
|
|
|
85 void
|
|
|
86 avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
|
|
|
87 class expr_hash_elt *elt2,
|
|
|
88 char type)
|
|
|
89 {
|
|
|
90 if (elt1 && dump_file && (dump_flags & TDF_DETAILS))
|
|
|
91 {
|
|
|
92 fprintf (dump_file, "%c>>> ", type);
|
|
|
93 elt1->print (dump_file);
|
|
|
94 }
|
|
|
95
|
|
|
96 m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2));
|
|
|
97 }
|
|
|
98
|
|
|
99 /* Helper for walk_non_aliased_vuses. Determine if we arrived at
|
|
|
100 the desired memory state. */
|
|
|
101
|
|
|
102 static void *
|
|
|
103 vuse_eq (ao_ref *, tree vuse1, unsigned int cnt, void *data)
|
|
|
104 {
|
|
|
105 tree vuse2 = (tree) data;
|
|
|
106 if (vuse1 == vuse2)
|
|
|
107 return data;
|
|
|
108
|
|
|
109 /* This bounds the stmt walks we perform on reference lookups
|
|
|
110 to O(1) instead of O(N) where N is the number of dominating
|
|
|
111 stores leading to a candidate. We re-use the SCCVN param
|
|
|
112 for this as it is basically the same complexity. */
|
|
|
113 if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
|
|
|
114 return (void *)-1;
|
|
|
115
|
|
|
116 return NULL;
|
|
|
117 }
|
|
|
118
|
|
|
119 /* We looked for STMT in the hash table, but did not find it.
|
|
|
120
|
|
|
121 If STMT is an assignment from a binary operator, we may know something
|
|
|
122 about the operands relationship to each other which would allow
|
|
|
123 us to derive a constant value for the RHS of STMT. */
|
|
|
124
|
|
|
125 tree
|
|
|
126 avail_exprs_stack::simplify_binary_operation (gimple *stmt,
|
|
|
127 class expr_hash_elt element)
|
|
|
128 {
|
|
|
129 if (is_gimple_assign (stmt))
|
|
|
130 {
|
|
|
131 struct hashable_expr *expr = element.expr ();
|
|
|
132 if (expr->kind == EXPR_BINARY)
|
|
|
133 {
|
|
|
134 enum tree_code code = expr->ops.binary.op;
|
|
|
135
|
|
|
136 switch (code)
|
|
|
137 {
|
|
|
138 /* For these cases, if we know the operands
|
|
|
139 are equal, then we know the result. */
|
|
|
140 case MIN_EXPR:
|
|
|
141 case MAX_EXPR:
|
|
|
142 case BIT_IOR_EXPR:
|
|
|
143 case BIT_AND_EXPR:
|
|
|
144 case BIT_XOR_EXPR:
|
|
|
145 case MINUS_EXPR:
|
|
|
146 case TRUNC_DIV_EXPR:
|
|
|
147 case CEIL_DIV_EXPR:
|
|
|
148 case FLOOR_DIV_EXPR:
|
|
|
149 case ROUND_DIV_EXPR:
|
|
|
150 case EXACT_DIV_EXPR:
|
|
|
151 case TRUNC_MOD_EXPR:
|
|
|
152 case CEIL_MOD_EXPR:
|
|
|
153 case FLOOR_MOD_EXPR:
|
|
|
154 case ROUND_MOD_EXPR:
|
|
|
155 {
|
|
|
156 /* Build a simple equality expr and query the hash table
|
|
|
157 for it. */
|
|
|
158 struct hashable_expr expr;
|
|
|
159 expr.type = boolean_type_node;
|
|
|
160 expr.kind = EXPR_BINARY;
|
|
|
161 expr.ops.binary.op = EQ_EXPR;
|
|
|
162 expr.ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
|
|
|
163 expr.ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
|
|
|
164 class expr_hash_elt element2 (&expr, NULL_TREE);
|
|
|
165 expr_hash_elt **slot
|
|
|
166 = m_avail_exprs->find_slot (&element2, NO_INSERT);
|
|
|
167 tree result_type = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
168
|
|
|
169 /* If the query was successful and returned a nonzero
|
|
|
170 result, then we know that the operands of the binary
|
|
|
171 expression are the same. In many cases this allows
|
|
|
172 us to compute a constant result of the expression
|
|
|
173 at compile time, even if we do not know the exact
|
|
|
174 values of the operands. */
|
|
|
175 if (slot && *slot && integer_onep ((*slot)->lhs ()))
|
|
|
176 {
|
|
|
177 switch (code)
|
|
|
178 {
|
|
|
179 case MIN_EXPR:
|
|
|
180 case MAX_EXPR:
|
|
|
181 case BIT_IOR_EXPR:
|
|
|
182 case BIT_AND_EXPR:
|
|
|
183 return gimple_assign_rhs1 (stmt);
|
|
|
184
|
|
|
185 case BIT_XOR_EXPR:
|
|
|
186 case MINUS_EXPR:
|
|
|
187 case TRUNC_MOD_EXPR:
|
|
|
188 case CEIL_MOD_EXPR:
|
|
|
189 case FLOOR_MOD_EXPR:
|
|
|
190 case ROUND_MOD_EXPR:
|
|
|
191 return build_zero_cst (result_type);
|
|
|
192
|
|
|
193 case TRUNC_DIV_EXPR:
|
|
|
194 case CEIL_DIV_EXPR:
|
|
|
195 case FLOOR_DIV_EXPR:
|
|
|
196 case ROUND_DIV_EXPR:
|
|
|
197 case EXACT_DIV_EXPR:
|
|
|
198 return build_one_cst (result_type);
|
|
|
199
|
|
|
200 default:
|
|
|
201 gcc_unreachable ();
|
|
|
202 }
|
|
|
203 }
|
|
|
204 break;
|
|
|
205 }
|
|
|
206
|
|
|
207 default:
|
|
|
208 break;
|
|
|
209 }
|
|
|
210 }
|
|
|
211 }
|
|
|
212 return NULL_TREE;
|
|
|
213 }
|
|
|
214
|
|
|
215 /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table.
|
|
|
216 If found, return its LHS. Otherwise insert STMT in the table and
|
|
|
217 return NULL_TREE.
|
|
|
218
|
|
|
219 Also, when an expression is first inserted in the table, it is also
|
|
|
220 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
|
|
|
221 we finish processing this block and its children. */
|
|
|
222
|
|
|
223 tree
|
|
|
224 avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p)
|
|
|
225 {
|
|
|
226 expr_hash_elt **slot;
|
|
|
227 tree lhs;
|
|
|
228
|
|
|
229 /* Get LHS of phi, assignment, or call; else NULL_TREE. */
|
|
|
230 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
231 lhs = gimple_phi_result (stmt);
|
|
|
232 else
|
|
|
233 lhs = gimple_get_lhs (stmt);
|
|
|
234
|
|
|
235 class expr_hash_elt element (stmt, lhs);
|
|
|
236
|
|
|
237 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
238 {
|
|
|
239 fprintf (dump_file, "LKUP ");
|
|
|
240 element.print (dump_file);
|
|
|
241 }
|
|
|
242
|
|
|
243 /* Don't bother remembering constant assignments and copy operations.
|
|
|
244 Constants and copy operations are handled by the constant/copy propagator
|
|
|
245 in optimize_stmt. */
|
|
|
246 if (element.expr()->kind == EXPR_SINGLE
|
|
|
247 && (TREE_CODE (element.expr()->ops.single.rhs) == SSA_NAME
|
|
|
248 || is_gimple_min_invariant (element.expr()->ops.single.rhs)))
|
|
|
249 return NULL_TREE;
|
|
|
250
|
|
|
251 /* Finally try to find the expression in the main expression hash table. */
|
|
|
252 slot = m_avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
|
|
|
253 if (slot == NULL)
|
|
|
254 {
|
|
|
255 return NULL_TREE;
|
|
|
256 }
|
|
|
257 else if (*slot == NULL)
|
|
|
258 {
|
|
|
259 /* If we did not find the expression in the hash table, we may still
|
|
|
260 be able to produce a result for some expressions. */
|
|
|
261 tree retval = avail_exprs_stack::simplify_binary_operation (stmt,
|
|
|
262 element);
|
|
|
263
|
|
|
264 /* We have, in effect, allocated *SLOT for ELEMENT at this point.
|
|
|
265 We must initialize *SLOT to a real entry, even if we found a
|
|
|
266 way to prove ELEMENT was a constant after not finding ELEMENT
|
|
|
267 in the hash table.
|
|
|
268
|
|
|
269 An uninitialized or empty slot is an indication no prior objects
|
|
|
270 entered into the hash table had a hash collection with ELEMENT.
|
|
|
271
|
|
|
272 If we fail to do so and had such entries in the table, they
|
|
|
273 would become unreachable. */
|
|
|
274 class expr_hash_elt *element2 = new expr_hash_elt (element);
|
|
|
275 *slot = element2;
|
|
|
276
|
|
|
277 record_expr (element2, NULL, '2');
|
|
|
278 return retval;
|
|
|
279 }
|
|
|
280
|
|
|
281 /* If we found a redundant memory operation do an alias walk to
|
|
|
282 check if we can re-use it. */
|
|
|
283 if (gimple_vuse (stmt) != (*slot)->vop ())
|
|
|
284 {
|
|
|
285 tree vuse1 = (*slot)->vop ();
|
|
|
286 tree vuse2 = gimple_vuse (stmt);
|
|
|
287 /* If we have a load of a register and a candidate in the
|
|
|
288 hash with vuse1 then try to reach its stmt by walking
|
|
|
289 up the virtual use-def chain using walk_non_aliased_vuses.
|
|
|
290 But don't do this when removing expressions from the hash. */
|
|
|
291 ao_ref ref;
|
|
|
292 if (!(vuse1 && vuse2
|
|
|
293 && gimple_assign_single_p (stmt)
|
|
|
294 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
|
|
|
295 && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)),
|
|
|
296 ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true)
|
|
|
297 && walk_non_aliased_vuses (&ref, vuse2,
|
|
|
298 vuse_eq, NULL, NULL, vuse1) != NULL))
|
|
|
299 {
|
|
|
300 if (insert)
|
|
|
301 {
|
|
|
302 class expr_hash_elt *element2 = new expr_hash_elt (element);
|
|
|
303
|
|
|
304 /* Insert the expr into the hash by replacing the current
|
|
|
305 entry and recording the value to restore in the
|
|
|
306 avail_exprs_stack. */
|
|
|
307 record_expr (element2, *slot, '2');
|
|
|
308 *slot = element2;
|
|
|
309 }
|
|
|
310 return NULL_TREE;
|
|
|
311 }
|
|
|
312 }
|
|
|
313
|
|
|
314 /* Extract the LHS of the assignment so that it can be used as the current
|
|
|
315 definition of another variable. */
|
|
|
316 lhs = (*slot)->lhs ();
|
|
|
317
|
|
|
318 /* Valueize the result. */
|
|
|
319 if (TREE_CODE (lhs) == SSA_NAME)
|
|
|
320 {
|
|
|
321 tree tem = SSA_NAME_VALUE (lhs);
|
|
|
322 if (tem)
|
|
|
323 lhs = tem;
|
|
|
324 }
|
|
|
325
|
|
|
326 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
327 {
|
|
|
328 fprintf (dump_file, "FIND: ");
|
|
|
329 print_generic_expr (dump_file, lhs);
|
|
|
330 fprintf (dump_file, "\n");
|
|
|
331 }
|
|
|
332
|
|
|
333 return lhs;
|
|
|
334 }
|
|
|
335
|
|
|
336 /* Enter condition equivalence P into the hash table.
|
|
|
337
|
|
|
338 This indicates that a conditional expression has a known
|
|
|
339 boolean value. */
|
|
|
340
|
|
|
341 void
|
|
|
342 avail_exprs_stack::record_cond (cond_equivalence *p)
|
|
|
343 {
|
|
|
344 class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value);
|
|
|
345 expr_hash_elt **slot;
|
|
|
346
|
|
|
347 slot = m_avail_exprs->find_slot_with_hash (element, element->hash (), INSERT);
|
|
|
348 if (*slot == NULL)
|
|
|
349 {
|
|
|
350 *slot = element;
|
|
|
351 record_expr (element, NULL, '1');
|
|
|
352 }
|
|
|
353 else
|
|
|
354 delete element;
|
|
|
355 }
|
|
|
356
|
|
|
357 /* Generate a hash value for a pair of expressions. This can be used
|
|
|
358 iteratively by passing a previous result in HSTATE.
|
|
|
359
|
|
|
360 The same hash value is always returned for a given pair of expressions,
|
|
|
361 regardless of the order in which they are presented. This is useful in
|
|
|
362 hashing the operands of commutative functions. */
|
|
|
363
|
|
|
364 namespace inchash
|
|
|
365 {
|
|
|
366
|
|
|
367 static void
|
|
|
368 add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
|
|
|
369 {
|
|
|
370 hash one, two;
|
|
|
371
|
|
|
372 inchash::add_expr (t1, one);
|
|
|
373 inchash::add_expr (t2, two);
|
|
|
374 hstate.add_commutative (one, two);
|
|
|
375 }
|
|
|
376
|
|
|
377 /* Compute a hash value for a hashable_expr value EXPR and a
|
|
|
378 previously accumulated hash value VAL. If two hashable_expr
|
|
|
379 values compare equal with hashable_expr_equal_p, they must
|
|
|
380 hash to the same value, given an identical value of VAL.
|
|
|
381 The logic is intended to follow inchash::add_expr in tree.c. */
|
|
|
382
|
|
|
383 static void
|
|
|
384 add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
|
|
|
385 {
|
|
|
386 switch (expr->kind)
|
|
|
387 {
|
|
|
388 case EXPR_SINGLE:
|
|
|
389 inchash::add_expr (expr->ops.single.rhs, hstate);
|
|
|
390 break;
|
|
|
391
|
|
|
392 case EXPR_UNARY:
|
|
|
393 hstate.add_object (expr->ops.unary.op);
|
|
|
394
|
|
|
395 /* Make sure to include signedness in the hash computation.
|
|
|
396 Don't hash the type, that can lead to having nodes which
|
|
|
397 compare equal according to operand_equal_p, but which
|
|
|
398 have different hash codes. */
|
|
|
399 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
|
|
|
400 || expr->ops.unary.op == NON_LVALUE_EXPR)
|
|
|
401 hstate.add_int (TYPE_UNSIGNED (expr->type));
|
|
|
402
|
|
|
403 inchash::add_expr (expr->ops.unary.opnd, hstate);
|
|
|
404 break;
|
|
|
405
|
|
|
406 case EXPR_BINARY:
|
|
|
407 hstate.add_object (expr->ops.binary.op);
|
|
|
408 if (commutative_tree_code (expr->ops.binary.op))
|
|
|
409 inchash::add_expr_commutative (expr->ops.binary.opnd0,
|
|
|
410 expr->ops.binary.opnd1, hstate);
|
|
|
411 else
|
|
|
412 {
|
|
|
413 inchash::add_expr (expr->ops.binary.opnd0, hstate);
|
|
|
414 inchash::add_expr (expr->ops.binary.opnd1, hstate);
|
|
|
415 }
|
|
|
416 break;
|
|
|
417
|
|
|
418 case EXPR_TERNARY:
|
|
|
419 hstate.add_object (expr->ops.ternary.op);
|
|
|
420 if (commutative_ternary_tree_code (expr->ops.ternary.op))
|
|
|
421 inchash::add_expr_commutative (expr->ops.ternary.opnd0,
|
|
|
422 expr->ops.ternary.opnd1, hstate);
|
|
|
423 else
|
|
|
424 {
|
|
|
425 inchash::add_expr (expr->ops.ternary.opnd0, hstate);
|
|
|
426 inchash::add_expr (expr->ops.ternary.opnd1, hstate);
|
|
|
427 }
|
|
|
428 inchash::add_expr (expr->ops.ternary.opnd2, hstate);
|
|
|
429 break;
|
|
|
430
|
|
|
431 case EXPR_CALL:
|
|
|
432 {
|
|
|
433 size_t i;
|
|
|
434 enum tree_code code = CALL_EXPR;
|
|
|
435 gcall *fn_from;
|
|
|
436
|
|
|
437 hstate.add_object (code);
|
|
|
438 fn_from = expr->ops.call.fn_from;
|
|
|
439 if (gimple_call_internal_p (fn_from))
|
|
|
440 hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
|
|
|
441 else
|
|
|
442 inchash::add_expr (gimple_call_fn (fn_from), hstate);
|
|
|
443 for (i = 0; i < expr->ops.call.nargs; i++)
|
|
|
444 inchash::add_expr (expr->ops.call.args[i], hstate);
|
|
|
445 }
|
|
|
446 break;
|
|
|
447
|
|
|
448 case EXPR_PHI:
|
|
|
449 {
|
|
|
450 size_t i;
|
|
|
451
|
|
|
452 for (i = 0; i < expr->ops.phi.nargs; i++)
|
|
|
453 inchash::add_expr (expr->ops.phi.args[i], hstate);
|
|
|
454 }
|
|
|
455 break;
|
|
|
456
|
|
|
457 default:
|
|
|
458 gcc_unreachable ();
|
|
|
459 }
|
|
|
460 }
|
|
|
461
|
|
|
462 }
|
|
|
463
|
|
|
464 /* Hashing and equality functions. We compute a value number for expressions
|
|
|
465 using the code of the expression and the SSA numbers of its operands. */
|
|
|
466
|
|
|
467 static hashval_t
|
|
|
468 avail_expr_hash (class expr_hash_elt *p)
|
|
|
469 {
|
|
|
470 const struct hashable_expr *expr = p->expr ();
|
|
|
471 inchash::hash hstate;
|
|
|
472
|
|
|
473 if (expr->kind == EXPR_SINGLE)
|
|
|
474 {
|
|
|
475 /* T could potentially be a switch index or a goto dest. */
|
|
|
476 tree t = expr->ops.single.rhs;
|
|
|
477 if (TREE_CODE (t) == MEM_REF || handled_component_p (t))
|
|
|
478 {
|
|
|
479 /* Make equivalent statements of both these kinds hash together.
|
|
|
480 Dealing with both MEM_REF and ARRAY_REF allows us not to care
|
|
|
481 about equivalence with other statements not considered here. */
|
|
|
482 bool reverse;
|
|
|
483 HOST_WIDE_INT offset, size, max_size;
|
|
|
484 tree base = get_ref_base_and_extent (t, &offset, &size, &max_size,
|
|
|
485 &reverse);
|
|
|
486 /* Strictly, we could try to normalize variable-sized accesses too,
|
|
|
487 but here we just deal with the common case. */
|
|
|
488 if (size != -1
|
|
|
489 && size == max_size)
|
|
|
490 {
|
|
|
491 enum tree_code code = MEM_REF;
|
|
|
492 hstate.add_object (code);
|
|
|
493 inchash::add_expr (base, hstate);
|
|
|
494 hstate.add_object (offset);
|
|
|
495 hstate.add_object (size);
|
|
|
496 return hstate.end ();
|
|
|
497 }
|
|
|
498 }
|
|
|
499 }
|
|
|
500
|
|
|
501 inchash::add_hashable_expr (expr, hstate);
|
|
|
502
|
|
|
503 return hstate.end ();
|
|
|
504 }
|
|
|
505
|
|
|
506 /* Compares trees T0 and T1 to see if they are MEM_REF or ARRAY_REFs equivalent
|
|
|
507 to each other. (That is, they return the value of the same bit of memory.)
|
|
|
508
|
|
|
509 Return TRUE if the two are so equivalent; FALSE if not (which could still
|
|
|
510 mean the two are equivalent by other means). */
|
|
|
511
|
|
|
512 static bool
|
|
|
513 equal_mem_array_ref_p (tree t0, tree t1)
|
|
|
514 {
|
|
|
515 if (TREE_CODE (t0) != MEM_REF && ! handled_component_p (t0))
|
|
|
516 return false;
|
|
|
517 if (TREE_CODE (t1) != MEM_REF && ! handled_component_p (t1))
|
|
|
518 return false;
|
|
|
519
|
|
|
520 if (!types_compatible_p (TREE_TYPE (t0), TREE_TYPE (t1)))
|
|
|
521 return false;
|
|
|
522 bool rev0;
|
|
|
523 HOST_WIDE_INT off0, sz0, max0;
|
|
|
524 tree base0 = get_ref_base_and_extent (t0, &off0, &sz0, &max0, &rev0);
|
|
|
525 if (sz0 == -1
|
|
|
526 || sz0 != max0)
|
|
|
527 return false;
|
|
|
528
|
|
|
529 bool rev1;
|
|
|
530 HOST_WIDE_INT off1, sz1, max1;
|
|
|
531 tree base1 = get_ref_base_and_extent (t1, &off1, &sz1, &max1, &rev1);
|
|
|
532 if (sz1 == -1
|
|
|
533 || sz1 != max1)
|
|
|
534 return false;
|
|
|
535
|
|
|
536 if (rev0 != rev1)
|
|
|
537 return false;
|
|
|
538
|
|
|
539 /* Types were compatible, so this is a sanity check. */
|
|
|
540 gcc_assert (sz0 == sz1);
|
|
|
541
|
|
|
542 return (off0 == off1) && operand_equal_p (base0, base1, 0);
|
|
|
543 }
|
|
|
544
|
|
|
545 /* Compare two hashable_expr structures for equivalence. They are
|
|
|
546 considered equivalent when the expressions they denote must
|
|
|
547 necessarily be equal. The logic is intended to follow that of
|
|
|
548 operand_equal_p in fold-const.c */
|
|
|
549
|
|
|
550 static bool
|
|
|
551 hashable_expr_equal_p (const struct hashable_expr *expr0,
|
|
|
552 const struct hashable_expr *expr1)
|
|
|
553 {
|
|
|
554 tree type0 = expr0->type;
|
|
|
555 tree type1 = expr1->type;
|
|
|
556
|
|
|
557 /* If either type is NULL, there is nothing to check. */
|
|
|
558 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
|
|
|
559 return false;
|
|
|
560
|
|
|
561 /* If both types don't have the same signedness, precision, and mode,
|
|
|
562 then we can't consider them equal. */
|
|
|
563 if (type0 != type1
|
|
|
564 && (TREE_CODE (type0) == ERROR_MARK
|
|
|
565 || TREE_CODE (type1) == ERROR_MARK
|
|
|
566 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
|
|
|
567 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
|
|
|
568 || TYPE_MODE (type0) != TYPE_MODE (type1)))
|
|
|
569 return false;
|
|
|
570
|
|
|
571 if (expr0->kind != expr1->kind)
|
|
|
572 return false;
|
|
|
573
|
|
|
574 switch (expr0->kind)
|
|
|
575 {
|
|
|
576 case EXPR_SINGLE:
|
|
|
577 return equal_mem_array_ref_p (expr0->ops.single.rhs,
|
|
|
578 expr1->ops.single.rhs)
|
|
|
579 || operand_equal_p (expr0->ops.single.rhs,
|
|
|
580 expr1->ops.single.rhs, 0);
|
|
|
581 case EXPR_UNARY:
|
|
|
582 if (expr0->ops.unary.op != expr1->ops.unary.op)
|
|
|
583 return false;
|
|
|
584
|
|
|
585 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
|
|
|
586 || expr0->ops.unary.op == NON_LVALUE_EXPR)
|
|
|
587 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
|
|
|
588 return false;
|
|
|
589
|
|
|
590 return operand_equal_p (expr0->ops.unary.opnd,
|
|
|
591 expr1->ops.unary.opnd, 0);
|
|
|
592
|
|
|
593 case EXPR_BINARY:
|
|
|
594 if (expr0->ops.binary.op != expr1->ops.binary.op)
|
|
|
595 return false;
|
|
|
596
|
|
|
597 if (operand_equal_p (expr0->ops.binary.opnd0,
|
|
|
598 expr1->ops.binary.opnd0, 0)
|
|
|
599 && operand_equal_p (expr0->ops.binary.opnd1,
|
|
|
600 expr1->ops.binary.opnd1, 0))
|
|
|
601 return true;
|
|
|
602
|
|
|
603 /* For commutative ops, allow the other order. */
|
|
|
604 return (commutative_tree_code (expr0->ops.binary.op)
|
|
|
605 && operand_equal_p (expr0->ops.binary.opnd0,
|
|
|
606 expr1->ops.binary.opnd1, 0)
|
|
|
607 && operand_equal_p (expr0->ops.binary.opnd1,
|
|
|
608 expr1->ops.binary.opnd0, 0));
|
|
|
609
|
|
|
610 case EXPR_TERNARY:
|
|
|
611 if (expr0->ops.ternary.op != expr1->ops.ternary.op
|
|
|
612 || !operand_equal_p (expr0->ops.ternary.opnd2,
|
|
|
613 expr1->ops.ternary.opnd2, 0))
|
|
|
614 return false;
|
|
|
615
|
|
|
616 /* BIT_INSERT_EXPR has an implict operand as the type precision
|
|
|
617 of op1. Need to check to make sure they are the same. */
|
|
|
618 if (expr0->ops.ternary.op == BIT_INSERT_EXPR
|
|
|
619 && TREE_CODE (expr0->ops.ternary.opnd1) == INTEGER_CST
|
|
|
620 && TREE_CODE (expr1->ops.ternary.opnd1) == INTEGER_CST
|
|
|
621 && TYPE_PRECISION (TREE_TYPE (expr0->ops.ternary.opnd1))
|
|
|
622 != TYPE_PRECISION (TREE_TYPE (expr1->ops.ternary.opnd1)))
|
|
|
623 return false;
|
|
|
624
|
|
|
625 if (operand_equal_p (expr0->ops.ternary.opnd0,
|
|
|
626 expr1->ops.ternary.opnd0, 0)
|
|
|
627 && operand_equal_p (expr0->ops.ternary.opnd1,
|
|
|
628 expr1->ops.ternary.opnd1, 0))
|
|
|
629 return true;
|
|
|
630
|
|
|
631 /* For commutative ops, allow the other order. */
|
|
|
632 return (commutative_ternary_tree_code (expr0->ops.ternary.op)
|
|
|
633 && operand_equal_p (expr0->ops.ternary.opnd0,
|
|
|
634 expr1->ops.ternary.opnd1, 0)
|
|
|
635 && operand_equal_p (expr0->ops.ternary.opnd1,
|
|
|
636 expr1->ops.ternary.opnd0, 0));
|
|
|
637
|
|
|
638 case EXPR_CALL:
|
|
|
639 {
|
|
|
640 size_t i;
|
|
|
641
|
|
|
642 /* If the calls are to different functions, then they
|
|
|
643 clearly cannot be equal. */
|
|
|
644 if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
|
|
|
645 expr1->ops.call.fn_from))
|
|
|
646 return false;
|
|
|
647
|
|
|
648 if (! expr0->ops.call.pure)
|
|
|
649 return false;
|
|
|
650
|
|
|
651 if (expr0->ops.call.nargs != expr1->ops.call.nargs)
|
|
|
652 return false;
|
|
|
653
|
|
|
654 for (i = 0; i < expr0->ops.call.nargs; i++)
|
|
|
655 if (! operand_equal_p (expr0->ops.call.args[i],
|
|
|
656 expr1->ops.call.args[i], 0))
|
|
|
657 return false;
|
|
|
658
|
|
|
659 if (stmt_could_throw_p (expr0->ops.call.fn_from))
|
|
|
660 {
|
|
|
661 int lp0 = lookup_stmt_eh_lp (expr0->ops.call.fn_from);
|
|
|
662 int lp1 = lookup_stmt_eh_lp (expr1->ops.call.fn_from);
|
|
|
663 if ((lp0 > 0 || lp1 > 0) && lp0 != lp1)
|
|
|
664 return false;
|
|
|
665 }
|
|
|
666
|
|
|
667 return true;
|
|
|
668 }
|
|
|
669
|
|
|
670 case EXPR_PHI:
|
|
|
671 {
|
|
|
672 size_t i;
|
|
|
673
|
|
|
674 if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
|
|
|
675 return false;
|
|
|
676
|
|
|
677 for (i = 0; i < expr0->ops.phi.nargs; i++)
|
|
|
678 if (! operand_equal_p (expr0->ops.phi.args[i],
|
|
|
679 expr1->ops.phi.args[i], 0))
|
|
|
680 return false;
|
|
|
681
|
|
|
682 return true;
|
|
|
683 }
|
|
|
684
|
|
|
685 default:
|
|
|
686 gcc_unreachable ();
|
|
|
687 }
|
|
|
688 }
|
|
|
689
|
|
|
690 /* Given a statement STMT, construct a hash table element. */
|
|
|
691
|
|
|
692 expr_hash_elt::expr_hash_elt (gimple *stmt, tree orig_lhs)
|
|
|
693 {
|
|
|
694 enum gimple_code code = gimple_code (stmt);
|
|
|
695 struct hashable_expr *expr = this->expr ();
|
|
|
696
|
|
|
697 if (code == GIMPLE_ASSIGN)
|
|
|
698 {
|
|
|
699 enum tree_code subcode = gimple_assign_rhs_code (stmt);
|
|
|
700
|
|
|
701 switch (get_gimple_rhs_class (subcode))
|
|
|
702 {
|
|
|
703 case GIMPLE_SINGLE_RHS:
|
|
|
704 expr->kind = EXPR_SINGLE;
|
|
|
705 expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
|
|
|
706 expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
|
|
|
707 break;
|
|
|
708 case GIMPLE_UNARY_RHS:
|
|
|
709 expr->kind = EXPR_UNARY;
|
|
|
710 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
711 if (CONVERT_EXPR_CODE_P (subcode))
|
|
|
712 subcode = NOP_EXPR;
|
|
|
713 expr->ops.unary.op = subcode;
|
|
|
714 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
|
|
|
715 break;
|
|
|
716 case GIMPLE_BINARY_RHS:
|
|
|
717 expr->kind = EXPR_BINARY;
|
|
|
718 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
719 expr->ops.binary.op = subcode;
|
|
|
720 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
|
|
|
721 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
|
|
|
722 break;
|
|
|
723 case GIMPLE_TERNARY_RHS:
|
|
|
724 expr->kind = EXPR_TERNARY;
|
|
|
725 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
726 expr->ops.ternary.op = subcode;
|
|
|
727 expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
|
|
|
728 expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
|
|
|
729 expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
|
|
|
730 break;
|
|
|
731 default:
|
|
|
732 gcc_unreachable ();
|
|
|
733 }
|
|
|
734 }
|
|
|
735 else if (code == GIMPLE_COND)
|
|
|
736 {
|
|
|
737 expr->type = boolean_type_node;
|
|
|
738 expr->kind = EXPR_BINARY;
|
|
|
739 expr->ops.binary.op = gimple_cond_code (stmt);
|
|
|
740 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
|
|
|
741 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
|
|
|
742 }
|
|
|
743 else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
|
|
|
744 {
|
|
|
745 size_t nargs = gimple_call_num_args (call_stmt);
|
|
|
746 size_t i;
|
|
|
747
|
|
|
748 gcc_assert (gimple_call_lhs (call_stmt));
|
|
|
749
|
|
|
750 expr->type = TREE_TYPE (gimple_call_lhs (call_stmt));
|
|
|
751 expr->kind = EXPR_CALL;
|
|
|
752 expr->ops.call.fn_from = call_stmt;
|
|
|
753
|
|
|
754 if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE))
|
|
|
755 expr->ops.call.pure = true;
|
|
|
756 else
|
|
|
757 expr->ops.call.pure = false;
|
|
|
758
|
|
|
759 expr->ops.call.nargs = nargs;
|
|
|
760 expr->ops.call.args = XCNEWVEC (tree, nargs);
|
|
|
761 for (i = 0; i < nargs; i++)
|
|
|
762 expr->ops.call.args[i] = gimple_call_arg (call_stmt, i);
|
|
|
763 }
|
|
|
764 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
|
|
|
765 {
|
|
|
766 expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt));
|
|
|
767 expr->kind = EXPR_SINGLE;
|
|
|
768 expr->ops.single.rhs = gimple_switch_index (swtch_stmt);
|
|
|
769 }
|
|
|
770 else if (code == GIMPLE_GOTO)
|
|
|
771 {
|
|
|
772 expr->type = TREE_TYPE (gimple_goto_dest (stmt));
|
|
|
773 expr->kind = EXPR_SINGLE;
|
|
|
774 expr->ops.single.rhs = gimple_goto_dest (stmt);
|
|
|
775 }
|
|
|
776 else if (code == GIMPLE_PHI)
|
|
|
777 {
|
|
|
778 size_t nargs = gimple_phi_num_args (stmt);
|
|
|
779 size_t i;
|
|
|
780
|
|
|
781 expr->type = TREE_TYPE (gimple_phi_result (stmt));
|
|
|
782 expr->kind = EXPR_PHI;
|
|
|
783 expr->ops.phi.nargs = nargs;
|
|
|
784 expr->ops.phi.args = XCNEWVEC (tree, nargs);
|
|
|
785 for (i = 0; i < nargs; i++)
|
|
|
786 expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
|
|
|
787 }
|
|
|
788 else
|
|
|
789 gcc_unreachable ();
|
|
|
790
|
|
|
791 m_lhs = orig_lhs;
|
|
|
792 m_vop = gimple_vuse (stmt);
|
|
|
793 m_hash = avail_expr_hash (this);
|
|
|
794 m_stamp = this;
|
|
|
795 }
|
|
|
796
|
|
|
797 /* Given a hashable_expr expression ORIG and an ORIG_LHS,
|
|
|
798 construct a hash table element. */
|
|
|
799
|
|
|
800 expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs)
|
|
|
801 {
|
|
|
802 m_expr = *orig;
|
|
|
803 m_lhs = orig_lhs;
|
|
|
804 m_vop = NULL_TREE;
|
|
|
805 m_hash = avail_expr_hash (this);
|
|
|
806 m_stamp = this;
|
|
|
807 }
|
|
|
808
|
|
|
809 /* Copy constructor for a hash table element. */
|
|
|
810
|
|
|
811 expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt)
|
|
|
812 {
|
|
|
813 m_expr = old_elt.m_expr;
|
|
|
814 m_lhs = old_elt.m_lhs;
|
|
|
815 m_vop = old_elt.m_vop;
|
|
|
816 m_hash = old_elt.m_hash;
|
|
|
817 m_stamp = this;
|
|
|
818
|
|
|
819 /* Now deep copy the malloc'd space for CALL and PHI args. */
|
|
|
820 if (old_elt.m_expr.kind == EXPR_CALL)
|
|
|
821 {
|
|
|
822 size_t nargs = old_elt.m_expr.ops.call.nargs;
|
|
|
823 size_t i;
|
|
|
824
|
|
|
825 m_expr.ops.call.args = XCNEWVEC (tree, nargs);
|
|
|
826 for (i = 0; i < nargs; i++)
|
|
|
827 m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i];
|
|
|
828 }
|
|
|
829 else if (old_elt.m_expr.kind == EXPR_PHI)
|
|
|
830 {
|
|
|
831 size_t nargs = old_elt.m_expr.ops.phi.nargs;
|
|
|
832 size_t i;
|
|
|
833
|
|
|
834 m_expr.ops.phi.args = XCNEWVEC (tree, nargs);
|
|
|
835 for (i = 0; i < nargs; i++)
|
|
|
836 m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i];
|
|
|
837 }
|
|
|
838 }
|
|
|
839
|
|
|
840 /* Calls and PHIs have a variable number of arguments that are allocated
|
|
|
841 on the heap. Thus we have to have a special dtor to release them. */
|
|
|
842
|
|
|
843 expr_hash_elt::~expr_hash_elt ()
|
|
|
844 {
|
|
|
845 if (m_expr.kind == EXPR_CALL)
|
|
|
846 free (m_expr.ops.call.args);
|
|
|
847 else if (m_expr.kind == EXPR_PHI)
|
|
|
848 free (m_expr.ops.phi.args);
|
|
|
849 }
|
|
|
850
|
|
|
851 /* Print a diagnostic dump of an expression hash table entry. */
|
|
|
852
|
|
|
853 void
|
|
|
854 expr_hash_elt::print (FILE *stream)
|
|
|
855 {
|
|
|
856 fprintf (stream, "STMT ");
|
|
|
857
|
|
|
858 if (m_lhs)
|
|
|
859 {
|
|
|
860 print_generic_expr (stream, m_lhs);
|
|
|
861 fprintf (stream, " = ");
|
|
|
862 }
|
|
|
863
|
|
|
864 switch (m_expr.kind)
|
|
|
865 {
|
|
|
866 case EXPR_SINGLE:
|
|
|
867 print_generic_expr (stream, m_expr.ops.single.rhs);
|
|
|
868 break;
|
|
|
869
|
|
|
870 case EXPR_UNARY:
|
|
|
871 fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op));
|
|
|
872 print_generic_expr (stream, m_expr.ops.unary.opnd);
|
|
|
873 break;
|
|
|
874
|
|
|
875 case EXPR_BINARY:
|
|
|
876 print_generic_expr (stream, m_expr.ops.binary.opnd0);
|
|
|
877 fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op));
|
|
|
878 print_generic_expr (stream, m_expr.ops.binary.opnd1);
|
|
|
879 break;
|
|
|
880
|
|
|
881 case EXPR_TERNARY:
|
|
|
882 fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op));
|
|
|
883 print_generic_expr (stream, m_expr.ops.ternary.opnd0);
|
|
|
884 fputs (", ", stream);
|
|
|
885 print_generic_expr (stream, m_expr.ops.ternary.opnd1);
|
|
|
886 fputs (", ", stream);
|
|
|
887 print_generic_expr (stream, m_expr.ops.ternary.opnd2);
|
|
|
888 fputs (">", stream);
|
|
|
889 break;
|
|
|
890
|
|
|
891 case EXPR_CALL:
|
|
|
892 {
|
|
|
893 size_t i;
|
|
|
894 size_t nargs = m_expr.ops.call.nargs;
|
|
|
895 gcall *fn_from;
|
|
|
896
|
|
|
897 fn_from = m_expr.ops.call.fn_from;
|
|
|
898 if (gimple_call_internal_p (fn_from))
|
|
|
899 fputs (internal_fn_name (gimple_call_internal_fn (fn_from)),
|
|
|
900 stream);
|
|
|
901 else
|
|
|
902 print_generic_expr (stream, gimple_call_fn (fn_from));
|
|
|
903 fprintf (stream, " (");
|
|
|
904 for (i = 0; i < nargs; i++)
|
|
|
905 {
|
|
|
906 print_generic_expr (stream, m_expr.ops.call.args[i]);
|
|
|
907 if (i + 1 < nargs)
|
|
|
908 fprintf (stream, ", ");
|
|
|
909 }
|
|
|
910 fprintf (stream, ")");
|
|
|
911 }
|
|
|
912 break;
|
|
|
913
|
|
|
914 case EXPR_PHI:
|
|
|
915 {
|
|
|
916 size_t i;
|
|
|
917 size_t nargs = m_expr.ops.phi.nargs;
|
|
|
918
|
|
|
919 fprintf (stream, "PHI <");
|
|
|
920 for (i = 0; i < nargs; i++)
|
|
|
921 {
|
|
|
922 print_generic_expr (stream, m_expr.ops.phi.args[i]);
|
|
|
923 if (i + 1 < nargs)
|
|
|
924 fprintf (stream, ", ");
|
|
|
925 }
|
|
|
926 fprintf (stream, ">");
|
|
|
927 }
|
|
|
928 break;
|
|
|
929 }
|
|
|
930
|
|
|
931 if (m_vop)
|
|
|
932 {
|
|
|
933 fprintf (stream, " with ");
|
|
|
934 print_generic_expr (stream, m_vop);
|
|
|
935 }
|
|
|
936
|
|
|
937 fprintf (stream, "\n");
|
|
|
938 }
|
|
|
939
|
|
|
940 /* Pop entries off the stack until we hit the NULL marker.
|
|
|
941 For each entry popped, use the SRC/DEST pair to restore
|
|
|
942 SRC to its prior value. */
|
|
|
943
|
|
|
944 void
|
|
|
945 const_and_copies::pop_to_marker (void)
|
|
|
946 {
|
|
|
947 while (m_stack.length () > 0)
|
|
|
948 {
|
|
|
949 tree prev_value, dest;
|
|
|
950
|
|
|
951 dest = m_stack.pop ();
|
|
|
952
|
|
|
953 /* A NULL value indicates we should stop unwinding, otherwise
|
|
|
954 pop off the next entry as they're recorded in pairs. */
|
|
|
955 if (dest == NULL)
|
|
|
956 break;
|
|
|
957
|
|
|
958 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
959 {
|
|
|
960 fprintf (dump_file, "<<<< COPY ");
|
|
|
961 print_generic_expr (dump_file, dest);
|
|
|
962 fprintf (dump_file, " = ");
|
|
|
963 print_generic_expr (dump_file, SSA_NAME_VALUE (dest));
|
|
|
964 fprintf (dump_file, "\n");
|
|
|
965 }
|
|
|
966
|
|
|
967 prev_value = m_stack.pop ();
|
|
|
968 set_ssa_name_value (dest, prev_value);
|
|
|
969 }
|
|
|
970 }
|
|
|
971
|
|
|
972 /* Record that X has the value Y and that X's previous value is PREV_X.
|
|
|
973
|
|
|
974 This variant does not follow the value chain for Y. */
|
|
|
975
|
|
|
976 void
|
|
|
977 const_and_copies::record_const_or_copy_raw (tree x, tree y, tree prev_x)
|
|
|
978 {
|
|
|
979 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
980 {
|
|
|
981 fprintf (dump_file, "0>>> COPY ");
|
|
|
982 print_generic_expr (dump_file, x);
|
|
|
983 fprintf (dump_file, " = ");
|
|
|
984 print_generic_expr (dump_file, y);
|
|
|
985 fprintf (dump_file, "\n");
|
|
|
986 }
|
|
|
987
|
|
|
988 set_ssa_name_value (x, y);
|
|
|
989 m_stack.reserve (2);
|
|
|
990 m_stack.quick_push (prev_x);
|
|
|
991 m_stack.quick_push (x);
|
|
|
992 }
|
|
|
993
|
|
|
994 /* Record that X has the value Y. */
|
|
|
995
|
|
|
996 void
|
|
|
997 const_and_copies::record_const_or_copy (tree x, tree y)
|
|
|
998 {
|
|
|
999 record_const_or_copy (x, y, SSA_NAME_VALUE (x));
|
|
|
1000 }
|
|
|
1001
|
|
|
1002 /* Record that X has the value Y and that X's previous value is PREV_X.
|
|
|
1003
|
|
|
1004 This variant follow's Y value chain. */
|
|
|
1005
|
|
|
1006 void
|
|
|
1007 const_and_copies::record_const_or_copy (tree x, tree y, tree prev_x)
|
|
|
1008 {
|
|
|
1009 /* Y may be NULL if we are invalidating entries in the table. */
|
|
|
1010 if (y && TREE_CODE (y) == SSA_NAME)
|
|
|
1011 {
|
|
|
1012 tree tmp = SSA_NAME_VALUE (y);
|
|
|
1013 y = tmp ? tmp : y;
|
|
|
1014 }
|
|
|
1015
|
|
|
1016 record_const_or_copy_raw (x, y, prev_x);
|
|
|
1017 }
|
|
|
1018
|
|
|
1019 bool
|
|
|
1020 expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
|
|
|
1021 {
|
|
|
1022 const struct hashable_expr *expr1 = p1->expr ();
|
|
|
1023 const struct expr_hash_elt *stamp1 = p1->stamp ();
|
|
|
1024 const struct hashable_expr *expr2 = p2->expr ();
|
|
|
1025 const struct expr_hash_elt *stamp2 = p2->stamp ();
|
|
|
1026
|
|
|
1027 /* This case should apply only when removing entries from the table. */
|
|
|
1028 if (stamp1 == stamp2)
|
|
|
1029 return true;
|
|
|
1030
|
|
|
1031 if (p1->hash () != p2->hash ())
|
|
|
1032 return false;
|
|
|
1033
|
|
|
1034 /* In case of a collision, both RHS have to be identical and have the
|
|
|
1035 same VUSE operands. */
|
|
|
1036 if (hashable_expr_equal_p (expr1, expr2)
|
|
|
1037 && types_compatible_p (expr1->type, expr2->type))
|
|
|
1038 return true;
|
|
|
1039
|
|
|
1040 return false;
|
|
|
1041 }
|
|
|
1042
|
|
|
1043 /* Given a conditional expression COND as a tree, initialize
|
|
|
1044 a hashable_expr expression EXPR. The conditional must be a
|
|
|
1045 comparison or logical negation. A constant or a variable is
|
|
|
1046 not permitted. */
|
|
|
1047
|
|
|
1048 void
|
|
|
1049 initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
|
|
|
1050 {
|
|
|
1051 expr->type = boolean_type_node;
|
|
|
1052
|
|
|
1053 if (COMPARISON_CLASS_P (cond))
|
|
|
1054 {
|
|
|
1055 expr->kind = EXPR_BINARY;
|
|
|
1056 expr->ops.binary.op = TREE_CODE (cond);
|
|
|
1057 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
|
|
|
1058 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
|
|
|
1059 }
|
|
|
1060 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
|
|
|
1061 {
|
|
|
1062 expr->kind = EXPR_UNARY;
|
|
|
1063 expr->ops.unary.op = TRUTH_NOT_EXPR;
|
|
|
1064 expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
|
|
|
1065 }
|
|
|
1066 else
|
|
|
1067 gcc_unreachable ();
|
|
|
1068 }
|
|
|
1069
|
|
|
1070 /* Build a cond_equivalence record indicating that the comparison
|
|
|
1071 CODE holds between operands OP0 and OP1 and push it to **P. */
|
|
|
1072
|
|
|
1073 static void
|
|
|
1074 build_and_record_new_cond (enum tree_code code,
|
|
|
1075 tree op0, tree op1,
|
|
|
1076 vec<cond_equivalence> *p,
|
|
|
1077 bool val = true)
|
|
|
1078 {
|
|
|
1079 cond_equivalence c;
|
|
|
1080 struct hashable_expr *cond = &c.cond;
|
|
|
1081
|
|
|
1082 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
|
|
|
1083
|
|
|
1084 cond->type = boolean_type_node;
|
|
|
1085 cond->kind = EXPR_BINARY;
|
|
|
1086 cond->ops.binary.op = code;
|
|
|
1087 cond->ops.binary.opnd0 = op0;
|
|
|
1088 cond->ops.binary.opnd1 = op1;
|
|
|
1089
|
|
|
1090 c.value = val ? boolean_true_node : boolean_false_node;
|
|
|
1091 p->safe_push (c);
|
|
|
1092 }
|
|
|
1093
|
|
|
1094 /* Record that COND is true and INVERTED is false into the edge information
|
|
|
1095 structure. Also record that any conditions dominated by COND are true
|
|
|
1096 as well.
|
|
|
1097
|
|
|
1098 For example, if a < b is true, then a <= b must also be true. */
|
|
|
1099
|
|
|
1100 void
|
|
|
1101 record_conditions (vec<cond_equivalence> *p, tree cond, tree inverted)
|
|
|
1102 {
|
|
|
1103 tree op0, op1;
|
|
|
1104 cond_equivalence c;
|
|
|
1105
|
|
|
1106 if (!COMPARISON_CLASS_P (cond))
|
|
|
1107 return;
|
|
|
1108
|
|
|
1109 op0 = TREE_OPERAND (cond, 0);
|
|
|
1110 op1 = TREE_OPERAND (cond, 1);
|
|
|
1111
|
|
|
1112 switch (TREE_CODE (cond))
|
|
|
1113 {
|
|
|
1114 case LT_EXPR:
|
|
|
1115 case GT_EXPR:
|
|
|
1116 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
|
|
|
1117 {
|
|
|
1118 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
|
|
|
1119 build_and_record_new_cond (LTGT_EXPR, op0, op1, p);
|
|
|
1120 }
|
|
|
1121
|
|
|
1122 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
|
|
|
1123 ? LE_EXPR : GE_EXPR),
|
|
|
1124 op0, op1, p);
|
|
|
1125 build_and_record_new_cond (NE_EXPR, op0, op1, p);
|
|
|
1126 build_and_record_new_cond (EQ_EXPR, op0, op1, p, false);
|
|
|
1127 break;
|
|
|
1128
|
|
|
1129 case GE_EXPR:
|
|
|
1130 case LE_EXPR:
|
|
|
1131 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
|
|
|
1132 {
|
|
|
1133 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
|
|
|
1134 }
|
|
|
1135 break;
|
|
|
1136
|
|
|
1137 case EQ_EXPR:
|
|
|
1138 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
|
|
|
1139 {
|
|
|
1140 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
|
|
|
1141 }
|
|
|
1142 build_and_record_new_cond (LE_EXPR, op0, op1, p);
|
|
|
1143 build_and_record_new_cond (GE_EXPR, op0, op1, p);
|
|
|
1144 break;
|
|
|
1145
|
|
|
1146 case UNORDERED_EXPR:
|
|
|
1147 build_and_record_new_cond (NE_EXPR, op0, op1, p);
|
|
|
1148 build_and_record_new_cond (UNLE_EXPR, op0, op1, p);
|
|
|
1149 build_and_record_new_cond (UNGE_EXPR, op0, op1, p);
|
|
|
1150 build_and_record_new_cond (UNEQ_EXPR, op0, op1, p);
|
|
|
1151 build_and_record_new_cond (UNLT_EXPR, op0, op1, p);
|
|
|
1152 build_and_record_new_cond (UNGT_EXPR, op0, op1, p);
|
|
|
1153 break;
|
|
|
1154
|
|
|
1155 case UNLT_EXPR:
|
|
|
1156 case UNGT_EXPR:
|
|
|
1157 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
|
|
|
1158 ? UNLE_EXPR : UNGE_EXPR),
|
|
|
1159 op0, op1, p);
|
|
|
1160 build_and_record_new_cond (NE_EXPR, op0, op1, p);
|
|
|
1161 break;
|
|
|
1162
|
|
|
1163 case UNEQ_EXPR:
|
|
|
1164 build_and_record_new_cond (UNLE_EXPR, op0, op1, p);
|
|
|
1165 build_and_record_new_cond (UNGE_EXPR, op0, op1, p);
|
|
|
1166 break;
|
|
|
1167
|
|
|
1168 case LTGT_EXPR:
|
|
|
1169 build_and_record_new_cond (NE_EXPR, op0, op1, p);
|
|
|
1170 build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
|
|
|
1171 break;
|
|
|
1172
|
|
|
1173 default:
|
|
|
1174 break;
|
|
|
1175 }
|
|
|
1176
|
|
|
1177 /* Now store the original true and false conditions into the first
|
|
|
1178 two slots. */
|
|
|
1179 initialize_expr_from_cond (cond, &c.cond);
|
|
|
1180 c.value = boolean_true_node;
|
|
|
1181 p->safe_push (c);
|
|
|
1182
|
|
|
1183 /* It is possible for INVERTED to be the negation of a comparison,
|
|
|
1184 and not a valid RHS or GIMPLE_COND condition. This happens because
|
|
|
1185 invert_truthvalue may return such an expression when asked to invert
|
|
|
1186 a floating-point comparison. These comparisons are not assumed to
|
|
|
1187 obey the trichotomy law. */
|
|
|
1188 initialize_expr_from_cond (inverted, &c.cond);
|
|
|
1189 c.value = boolean_false_node;
|
|
|
1190 p->safe_push (c);
|
|
|
1191 }
|
