]>
Commit | Line | Data |
---|---|---|
012309e6 | 1 | /* Reassociation for trees. |
c2152239 | 2 | Copyright (C) 2005, 2007, 2008, 2009 Free Software Foundation, Inc. |
012309e6 DB |
3 | Contributed by Daniel Berlin <dan@dberlin.org> |
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 | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
012309e6 DB |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
012309e6 DB |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
012309e6 DB |
25 | #include "ggc.h" |
26 | #include "tree.h" | |
27 | #include "basic-block.h" | |
28 | #include "diagnostic.h" | |
29 | #include "tree-inline.h" | |
30 | #include "tree-flow.h" | |
726a989a | 31 | #include "gimple.h" |
012309e6 DB |
32 | #include "tree-dump.h" |
33 | #include "timevar.h" | |
012309e6 DB |
34 | #include "tree-iterator.h" |
35 | #include "tree-pass.h" | |
0e0ed594 JL |
36 | #include "alloc-pool.h" |
37 | #include "vec.h" | |
38 | #include "langhooks.h" | |
15814ba0 | 39 | #include "pointer-set.h" |
7a9c7d01 | 40 | #include "cfgloop.h" |
2dc0f633 | 41 | #include "flags.h" |
012309e6 | 42 | |
0e0ed594 JL |
43 | /* This is a simple global reassociation pass. It is, in part, based |
44 | on the LLVM pass of the same name (They do some things more/less | |
45 | than we do, in different orders, etc). | |
012309e6 | 46 | |
0e0ed594 | 47 | It consists of five steps: |
012309e6 | 48 | |
0e0ed594 JL |
49 | 1. Breaking up subtract operations into addition + negate, where |
50 | it would promote the reassociation of adds. | |
012309e6 | 51 | |
0e0ed594 JL |
52 | 2. Left linearization of the expression trees, so that (A+B)+(C+D) |
53 | becomes (((A+B)+C)+D), which is easier for us to rewrite later. | |
54 | During linearization, we place the operands of the binary | |
55 | expressions into a vector of operand_entry_t | |
012309e6 | 56 | |
0e0ed594 JL |
57 | 3. Optimization of the operand lists, eliminating things like a + |
58 | -a, a & a, etc. | |
012309e6 | 59 | |
0e0ed594 JL |
60 | 4. Rewrite the expression trees we linearized and optimized so |
61 | they are in proper rank order. | |
012309e6 | 62 | |
0e0ed594 | 63 | 5. Repropagate negates, as nothing else will clean it up ATM. |
012309e6 | 64 | |
0e0ed594 JL |
65 | A bit of theory on #4, since nobody seems to write anything down |
66 | about why it makes sense to do it the way they do it: | |
012309e6 | 67 | |
0e0ed594 JL |
68 | We could do this much nicer theoretically, but don't (for reasons |
69 | explained after how to do it theoretically nice :P). | |
012309e6 | 70 | |
0e0ed594 JL |
71 | In order to promote the most redundancy elimination, you want |
72 | binary expressions whose operands are the same rank (or | |
6416ae7f | 73 | preferably, the same value) exposed to the redundancy eliminator, |
0e0ed594 | 74 | for possible elimination. |
012309e6 | 75 | |
0e0ed594 JL |
76 | So the way to do this if we really cared, is to build the new op |
77 | tree from the leaves to the roots, merging as you go, and putting the | |
78 | new op on the end of the worklist, until you are left with one | |
79 | thing on the worklist. | |
012309e6 | 80 | |
0e0ed594 JL |
81 | IE if you have to rewrite the following set of operands (listed with |
82 | rank in parentheses), with opcode PLUS_EXPR: | |
012309e6 | 83 | |
0e0ed594 | 84 | a (1), b (1), c (1), d (2), e (2) |
012309e6 | 85 | |
012309e6 | 86 | |
0e0ed594 JL |
87 | We start with our merge worklist empty, and the ops list with all of |
88 | those on it. | |
012309e6 | 89 | |
0e0ed594 JL |
90 | You want to first merge all leaves of the same rank, as much as |
91 | possible. | |
92 | ||
93 | So first build a binary op of | |
94 | ||
95 | mergetmp = a + b, and put "mergetmp" on the merge worklist. | |
96 | ||
97 | Because there is no three operand form of PLUS_EXPR, c is not going to | |
98 | be exposed to redundancy elimination as a rank 1 operand. | |
99 | ||
100 | So you might as well throw it on the merge worklist (you could also | |
101 | consider it to now be a rank two operand, and merge it with d and e, | |
102 | but in this case, you then have evicted e from a binary op. So at | |
103 | least in this situation, you can't win.) | |
104 | ||
105 | Then build a binary op of d + e | |
106 | mergetmp2 = d + e | |
107 | ||
108 | and put mergetmp2 on the merge worklist. | |
109 | ||
110 | so merge worklist = {mergetmp, c, mergetmp2} | |
111 | ||
112 | Continue building binary ops of these operations until you have only | |
113 | one operation left on the worklist. | |
114 | ||
115 | So we have | |
116 | ||
117 | build binary op | |
118 | mergetmp3 = mergetmp + c | |
119 | ||
120 | worklist = {mergetmp2, mergetmp3} | |
121 | ||
122 | mergetmp4 = mergetmp2 + mergetmp3 | |
123 | ||
124 | worklist = {mergetmp4} | |
125 | ||
126 | because we have one operation left, we can now just set the original | |
127 | statement equal to the result of that operation. | |
128 | ||
129 | This will at least expose a + b and d + e to redundancy elimination | |
130 | as binary operations. | |
131 | ||
132 | For extra points, you can reuse the old statements to build the | |
133 | mergetmps, since you shouldn't run out. | |
134 | ||
135 | So why don't we do this? | |
136 | ||
137 | Because it's expensive, and rarely will help. Most trees we are | |
138 | reassociating have 3 or less ops. If they have 2 ops, they already | |
139 | will be written into a nice single binary op. If you have 3 ops, a | |
140 | single simple check suffices to tell you whether the first two are of the | |
141 | same rank. If so, you know to order it | |
142 | ||
143 | mergetmp = op1 + op2 | |
144 | newstmt = mergetmp + op3 | |
145 | ||
146 | instead of | |
147 | mergetmp = op2 + op3 | |
148 | newstmt = mergetmp + op1 | |
149 | ||
150 | If all three are of the same rank, you can't expose them all in a | |
151 | single binary operator anyway, so the above is *still* the best you | |
152 | can do. | |
153 | ||
154 | Thus, this is what we do. When we have three ops left, we check to see | |
155 | what order to put them in, and call it a day. As a nod to vector sum | |
1d72ff1a | 156 | reduction, we check if any of the ops are really a phi node that is a |
0e0ed594 JL |
157 | destructive update for the associating op, and keep the destructive |
158 | update together for vector sum reduction recognition. */ | |
012309e6 | 159 | |
012309e6 | 160 | |
0e0ed594 JL |
161 | /* Statistics */ |
162 | static struct | |
163 | { | |
164 | int linearized; | |
165 | int constants_eliminated; | |
166 | int ops_eliminated; | |
167 | int rewritten; | |
168 | } reassociate_stats; | |
012309e6 | 169 | |
0e0ed594 JL |
170 | /* Operator, rank pair. */ |
171 | typedef struct operand_entry | |
012309e6 | 172 | { |
0e0ed594 JL |
173 | unsigned int rank; |
174 | tree op; | |
175 | } *operand_entry_t; | |
176 | ||
177 | static alloc_pool operand_entry_pool; | |
178 | ||
012309e6 DB |
179 | |
180 | /* Starting rank number for a given basic block, so that we can rank | |
181 | operations using unmovable instructions in that BB based on the bb | |
182 | depth. */ | |
15814ba0 | 183 | static long *bb_rank; |
012309e6 | 184 | |
0e0ed594 | 185 | /* Operand->rank hashtable. */ |
15814ba0 | 186 | static struct pointer_map_t *operand_rank; |
012309e6 DB |
187 | |
188 | ||
0e0ed594 | 189 | /* Look up the operand rank structure for expression E. */ |
012309e6 | 190 | |
15814ba0 | 191 | static inline long |
0e0ed594 | 192 | find_operand_rank (tree e) |
012309e6 | 193 | { |
15814ba0 PB |
194 | void **slot = pointer_map_contains (operand_rank, e); |
195 | return slot ? (long) *slot : -1; | |
012309e6 DB |
196 | } |
197 | ||
0e0ed594 | 198 | /* Insert {E,RANK} into the operand rank hashtable. */ |
012309e6 | 199 | |
15814ba0 PB |
200 | static inline void |
201 | insert_operand_rank (tree e, long rank) | |
012309e6 DB |
202 | { |
203 | void **slot; | |
15814ba0 PB |
204 | gcc_assert (rank > 0); |
205 | slot = pointer_map_insert (operand_rank, e); | |
206 | gcc_assert (!*slot); | |
207 | *slot = (void *) rank; | |
012309e6 DB |
208 | } |
209 | ||
012309e6 DB |
210 | /* Given an expression E, return the rank of the expression. */ |
211 | ||
15814ba0 | 212 | static long |
012309e6 DB |
213 | get_rank (tree e) |
214 | { | |
0e0ed594 | 215 | /* Constants have rank 0. */ |
012309e6 DB |
216 | if (is_gimple_min_invariant (e)) |
217 | return 0; | |
0e0ed594 | 218 | |
012309e6 DB |
219 | /* SSA_NAME's have the rank of the expression they are the result |
220 | of. | |
221 | For globals and uninitialized values, the rank is 0. | |
222 | For function arguments, use the pre-setup rank. | |
223 | For PHI nodes, stores, asm statements, etc, we use the rank of | |
224 | the BB. | |
225 | For simple operations, the rank is the maximum rank of any of | |
226 | its operands, or the bb_rank, whichever is less. | |
227 | I make no claims that this is optimal, however, it gives good | |
228 | results. */ | |
229 | ||
230 | if (TREE_CODE (e) == SSA_NAME) | |
231 | { | |
726a989a | 232 | gimple stmt; |
15814ba0 | 233 | long rank, maxrank; |
726a989a | 234 | int i, n; |
0e0ed594 | 235 | |
012309e6 | 236 | if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL |
cfaab3a9 | 237 | && SSA_NAME_IS_DEFAULT_DEF (e)) |
15814ba0 | 238 | return find_operand_rank (e); |
0e0ed594 | 239 | |
012309e6 | 240 | stmt = SSA_NAME_DEF_STMT (e); |
726a989a | 241 | if (gimple_bb (stmt) == NULL) |
012309e6 | 242 | return 0; |
0e0ed594 | 243 | |
726a989a | 244 | if (!is_gimple_assign (stmt) |
5006671f | 245 | || gimple_vdef (stmt)) |
726a989a | 246 | return bb_rank[gimple_bb (stmt)->index]; |
012309e6 DB |
247 | |
248 | /* If we already have a rank for this expression, use that. */ | |
15814ba0 PB |
249 | rank = find_operand_rank (e); |
250 | if (rank != -1) | |
251 | return rank; | |
012309e6 DB |
252 | |
253 | /* Otherwise, find the maximum rank for the operands, or the bb | |
254 | rank, whichever is less. */ | |
255 | rank = 0; | |
726a989a RB |
256 | maxrank = bb_rank[gimple_bb(stmt)->index]; |
257 | if (gimple_assign_single_p (stmt)) | |
258 | { | |
259 | tree rhs = gimple_assign_rhs1 (stmt); | |
260 | n = TREE_OPERAND_LENGTH (rhs); | |
261 | if (n == 0) | |
262 | rank = MAX (rank, get_rank (rhs)); | |
263 | else | |
264 | { | |
265 | for (i = 0; | |
266 | i < n && TREE_OPERAND (rhs, i) && rank != maxrank; i++) | |
267 | rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i))); | |
268 | } | |
269 | } | |
0e0ed594 | 270 | else |
012309e6 | 271 | { |
726a989a RB |
272 | n = gimple_num_ops (stmt); |
273 | for (i = 1; i < n && rank != maxrank; i++) | |
274 | { | |
275 | gcc_assert (gimple_op (stmt, i)); | |
276 | rank = MAX(rank, get_rank (gimple_op (stmt, i))); | |
277 | } | |
012309e6 | 278 | } |
0e0ed594 | 279 | |
012309e6 DB |
280 | if (dump_file && (dump_flags & TDF_DETAILS)) |
281 | { | |
282 | fprintf (dump_file, "Rank for "); | |
283 | print_generic_expr (dump_file, e, 0); | |
15814ba0 | 284 | fprintf (dump_file, " is %ld\n", (rank + 1)); |
012309e6 | 285 | } |
0e0ed594 | 286 | |
012309e6 | 287 | /* Note the rank in the hashtable so we don't recompute it. */ |
0e0ed594 | 288 | insert_operand_rank (e, (rank + 1)); |
012309e6 DB |
289 | return (rank + 1); |
290 | } | |
291 | ||
292 | /* Globals, etc, are rank 0 */ | |
293 | return 0; | |
294 | } | |
295 | ||
0e0ed594 JL |
296 | DEF_VEC_P(operand_entry_t); |
297 | DEF_VEC_ALLOC_P(operand_entry_t, heap); | |
298 | ||
299 | /* We want integer ones to end up last no matter what, since they are | |
300 | the ones we can do the most with. */ | |
301 | #define INTEGER_CONST_TYPE 1 << 3 | |
302 | #define FLOAT_CONST_TYPE 1 << 2 | |
303 | #define OTHER_CONST_TYPE 1 << 1 | |
304 | ||
305 | /* Classify an invariant tree into integer, float, or other, so that | |
306 | we can sort them to be near other constants of the same type. */ | |
307 | static inline int | |
308 | constant_type (tree t) | |
309 | { | |
310 | if (INTEGRAL_TYPE_P (TREE_TYPE (t))) | |
311 | return INTEGER_CONST_TYPE; | |
312 | else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t))) | |
313 | return FLOAT_CONST_TYPE; | |
314 | else | |
315 | return OTHER_CONST_TYPE; | |
316 | } | |
317 | ||
318 | /* qsort comparison function to sort operand entries PA and PB by rank | |
319 | so that the sorted array is ordered by rank in decreasing order. */ | |
320 | static int | |
321 | sort_by_operand_rank (const void *pa, const void *pb) | |
322 | { | |
323 | const operand_entry_t oea = *(const operand_entry_t *)pa; | |
324 | const operand_entry_t oeb = *(const operand_entry_t *)pb; | |
325 | ||
326 | /* It's nicer for optimize_expression if constants that are likely | |
327 | to fold when added/multiplied//whatever are put next to each | |
328 | other. Since all constants have rank 0, order them by type. */ | |
329 | if (oeb->rank == 0 && oea->rank == 0) | |
330 | return constant_type (oeb->op) - constant_type (oea->op); | |
331 | ||
332 | /* Lastly, make sure the versions that are the same go next to each | |
333 | other. We use SSA_NAME_VERSION because it's stable. */ | |
334 | if ((oeb->rank - oea->rank == 0) | |
335 | && TREE_CODE (oea->op) == SSA_NAME | |
336 | && TREE_CODE (oeb->op) == SSA_NAME) | |
337 | return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op); | |
338 | ||
339 | return oeb->rank - oea->rank; | |
340 | } | |
341 | ||
342 | /* Add an operand entry to *OPS for the tree operand OP. */ | |
343 | ||
344 | static void | |
345 | add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op) | |
346 | { | |
c22940cd | 347 | operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool); |
0e0ed594 JL |
348 | |
349 | oe->op = op; | |
350 | oe->rank = get_rank (op); | |
351 | VEC_safe_push (operand_entry_t, heap, *ops, oe); | |
352 | } | |
012309e6 | 353 | |
0e0ed594 | 354 | /* Return true if STMT is reassociable operation containing a binary |
7a9c7d01 | 355 | operation with tree code CODE, and is inside LOOP. */ |
012309e6 DB |
356 | |
357 | static bool | |
726a989a | 358 | is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop) |
0e0ed594 | 359 | { |
726a989a | 360 | basic_block bb = gimple_bb (stmt); |
7a9c7d01 | 361 | |
726a989a | 362 | if (gimple_bb (stmt) == NULL) |
7a9c7d01 ZD |
363 | return false; |
364 | ||
7a9c7d01 ZD |
365 | if (!flow_bb_inside_loop_p (loop, bb)) |
366 | return false; | |
367 | ||
726a989a RB |
368 | if (is_gimple_assign (stmt) |
369 | && gimple_assign_rhs_code (stmt) == code | |
370 | && has_single_use (gimple_assign_lhs (stmt))) | |
012309e6 | 371 | return true; |
726a989a | 372 | |
0e0ed594 JL |
373 | return false; |
374 | } | |
375 | ||
376 | ||
377 | /* Given NAME, if NAME is defined by a unary operation OPCODE, return the | |
378 | operand of the negate operation. Otherwise, return NULL. */ | |
379 | ||
380 | static tree | |
381 | get_unary_op (tree name, enum tree_code opcode) | |
382 | { | |
726a989a | 383 | gimple stmt = SSA_NAME_DEF_STMT (name); |
0e0ed594 | 384 | |
726a989a | 385 | if (!is_gimple_assign (stmt)) |
0e0ed594 JL |
386 | return NULL_TREE; |
387 | ||
726a989a RB |
388 | if (gimple_assign_rhs_code (stmt) == opcode) |
389 | return gimple_assign_rhs1 (stmt); | |
0e0ed594 JL |
390 | return NULL_TREE; |
391 | } | |
392 | ||
393 | /* If CURR and LAST are a pair of ops that OPCODE allows us to | |
394 | eliminate through equivalences, do so, remove them from OPS, and | |
395 | return true. Otherwise, return false. */ | |
396 | ||
397 | static bool | |
398 | eliminate_duplicate_pair (enum tree_code opcode, | |
399 | VEC (operand_entry_t, heap) **ops, | |
400 | bool *all_done, | |
401 | unsigned int i, | |
402 | operand_entry_t curr, | |
403 | operand_entry_t last) | |
404 | { | |
405 | ||
e969dbde AP |
406 | /* If we have two of the same op, and the opcode is & |, min, or max, |
407 | we can eliminate one of them. | |
0e0ed594 JL |
408 | If we have two of the same op, and the opcode is ^, we can |
409 | eliminate both of them. */ | |
012309e6 | 410 | |
0e0ed594 | 411 | if (last && last->op == curr->op) |
012309e6 | 412 | { |
0e0ed594 JL |
413 | switch (opcode) |
414 | { | |
e969dbde AP |
415 | case MAX_EXPR: |
416 | case MIN_EXPR: | |
0e0ed594 JL |
417 | case BIT_IOR_EXPR: |
418 | case BIT_AND_EXPR: | |
419 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
420 | { | |
421 | fprintf (dump_file, "Equivalence: "); | |
422 | print_generic_expr (dump_file, curr->op, 0); | |
e969dbde | 423 | fprintf (dump_file, " [&|minmax] "); |
0e0ed594 JL |
424 | print_generic_expr (dump_file, last->op, 0); |
425 | fprintf (dump_file, " -> "); | |
426 | print_generic_stmt (dump_file, last->op, 0); | |
427 | } | |
428 | ||
429 | VEC_ordered_remove (operand_entry_t, *ops, i); | |
430 | reassociate_stats.ops_eliminated ++; | |
431 | ||
432 | return true; | |
433 | ||
434 | case BIT_XOR_EXPR: | |
435 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
436 | { | |
437 | fprintf (dump_file, "Equivalence: "); | |
438 | print_generic_expr (dump_file, curr->op, 0); | |
439 | fprintf (dump_file, " ^ "); | |
440 | print_generic_expr (dump_file, last->op, 0); | |
441 | fprintf (dump_file, " -> nothing\n"); | |
442 | } | |
443 | ||
444 | reassociate_stats.ops_eliminated += 2; | |
445 | ||
446 | if (VEC_length (operand_entry_t, *ops) == 2) | |
447 | { | |
448 | VEC_free (operand_entry_t, heap, *ops); | |
449 | *ops = NULL; | |
450 | add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op), | |
451 | integer_zero_node)); | |
452 | *all_done = true; | |
453 | } | |
454 | else | |
455 | { | |
456 | VEC_ordered_remove (operand_entry_t, *ops, i-1); | |
457 | VEC_ordered_remove (operand_entry_t, *ops, i-1); | |
458 | } | |
459 | ||
460 | return true; | |
461 | ||
462 | default: | |
463 | break; | |
464 | } | |
465 | } | |
012309e6 DB |
466 | return false; |
467 | } | |
468 | ||
0e0ed594 JL |
469 | /* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression, |
470 | look in OPS for a corresponding positive operation to cancel it | |
471 | out. If we find one, remove the other from OPS, replace | |
472 | OPS[CURRINDEX] with 0, and return true. Otherwise, return | |
473 | false. */ | |
012309e6 DB |
474 | |
475 | static bool | |
0e0ed594 JL |
476 | eliminate_plus_minus_pair (enum tree_code opcode, |
477 | VEC (operand_entry_t, heap) **ops, | |
478 | unsigned int currindex, | |
479 | operand_entry_t curr) | |
480 | { | |
481 | tree negateop; | |
482 | unsigned int i; | |
483 | operand_entry_t oe; | |
484 | ||
485 | if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME) | |
012309e6 | 486 | return false; |
0e0ed594 JL |
487 | |
488 | negateop = get_unary_op (curr->op, NEGATE_EXPR); | |
489 | if (negateop == NULL_TREE) | |
490 | return false; | |
491 | ||
492 | /* Any non-negated version will have a rank that is one less than | |
493 | the current rank. So once we hit those ranks, if we don't find | |
494 | one, we can stop. */ | |
495 | ||
496 | for (i = currindex + 1; | |
497 | VEC_iterate (operand_entry_t, *ops, i, oe) | |
498 | && oe->rank >= curr->rank - 1 ; | |
499 | i++) | |
012309e6 | 500 | { |
0e0ed594 JL |
501 | if (oe->op == negateop) |
502 | { | |
503 | ||
504 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
505 | { | |
506 | fprintf (dump_file, "Equivalence: "); | |
507 | print_generic_expr (dump_file, negateop, 0); | |
508 | fprintf (dump_file, " + -"); | |
509 | print_generic_expr (dump_file, oe->op, 0); | |
510 | fprintf (dump_file, " -> 0\n"); | |
511 | } | |
512 | ||
513 | VEC_ordered_remove (operand_entry_t, *ops, i); | |
514 | add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op), | |
515 | integer_zero_node)); | |
516 | VEC_ordered_remove (operand_entry_t, *ops, currindex); | |
517 | reassociate_stats.ops_eliminated ++; | |
518 | ||
519 | return true; | |
520 | } | |
012309e6 DB |
521 | } |
522 | ||
0e0ed594 JL |
523 | return false; |
524 | } | |
525 | ||
526 | /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a | |
527 | bitwise not expression, look in OPS for a corresponding operand to | |
528 | cancel it out. If we find one, remove the other from OPS, replace | |
529 | OPS[CURRINDEX] with 0, and return true. Otherwise, return | |
530 | false. */ | |
531 | ||
532 | static bool | |
533 | eliminate_not_pairs (enum tree_code opcode, | |
534 | VEC (operand_entry_t, heap) **ops, | |
535 | unsigned int currindex, | |
536 | operand_entry_t curr) | |
537 | { | |
538 | tree notop; | |
539 | unsigned int i; | |
540 | operand_entry_t oe; | |
541 | ||
542 | if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR) | |
543 | || TREE_CODE (curr->op) != SSA_NAME) | |
544 | return false; | |
545 | ||
546 | notop = get_unary_op (curr->op, BIT_NOT_EXPR); | |
547 | if (notop == NULL_TREE) | |
548 | return false; | |
549 | ||
550 | /* Any non-not version will have a rank that is one less than | |
551 | the current rank. So once we hit those ranks, if we don't find | |
552 | one, we can stop. */ | |
553 | ||
554 | for (i = currindex + 1; | |
555 | VEC_iterate (operand_entry_t, *ops, i, oe) | |
556 | && oe->rank >= curr->rank - 1; | |
557 | i++) | |
012309e6 | 558 | { |
0e0ed594 | 559 | if (oe->op == notop) |
012309e6 | 560 | { |
0e0ed594 | 561 | if (dump_file && (dump_flags & TDF_DETAILS)) |
012309e6 | 562 | { |
0e0ed594 JL |
563 | fprintf (dump_file, "Equivalence: "); |
564 | print_generic_expr (dump_file, notop, 0); | |
565 | if (opcode == BIT_AND_EXPR) | |
566 | fprintf (dump_file, " & ~"); | |
567 | else if (opcode == BIT_IOR_EXPR) | |
568 | fprintf (dump_file, " | ~"); | |
569 | print_generic_expr (dump_file, oe->op, 0); | |
570 | if (opcode == BIT_AND_EXPR) | |
571 | fprintf (dump_file, " -> 0\n"); | |
572 | else if (opcode == BIT_IOR_EXPR) | |
573 | fprintf (dump_file, " -> -1\n"); | |
012309e6 | 574 | } |
0e0ed594 JL |
575 | |
576 | if (opcode == BIT_AND_EXPR) | |
577 | oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node); | |
578 | else if (opcode == BIT_IOR_EXPR) | |
579 | oe->op = build_low_bits_mask (TREE_TYPE (oe->op), | |
580 | TYPE_PRECISION (TREE_TYPE (oe->op))); | |
581 | ||
582 | reassociate_stats.ops_eliminated | |
583 | += VEC_length (operand_entry_t, *ops) - 1; | |
584 | VEC_free (operand_entry_t, heap, *ops); | |
585 | *ops = NULL; | |
586 | VEC_safe_push (operand_entry_t, heap, *ops, oe); | |
587 | return true; | |
012309e6 DB |
588 | } |
589 | } | |
0e0ed594 JL |
590 | |
591 | return false; | |
012309e6 DB |
592 | } |
593 | ||
0e0ed594 JL |
594 | /* Use constant value that may be present in OPS to try to eliminate |
595 | operands. Note that this function is only really used when we've | |
596 | eliminated ops for other reasons, or merged constants. Across | |
597 | single statements, fold already does all of this, plus more. There | |
598 | is little point in duplicating logic, so I've only included the | |
599 | identities that I could ever construct testcases to trigger. */ | |
012309e6 | 600 | |
0e0ed594 JL |
601 | static void |
602 | eliminate_using_constants (enum tree_code opcode, | |
603 | VEC(operand_entry_t, heap) **ops) | |
012309e6 | 604 | { |
0e0ed594 | 605 | operand_entry_t oelast = VEC_last (operand_entry_t, *ops); |
2dc0f633 | 606 | tree type = TREE_TYPE (oelast->op); |
012309e6 | 607 | |
2dc0f633 RG |
608 | if (oelast->rank == 0 |
609 | && (INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type))) | |
012309e6 | 610 | { |
0e0ed594 | 611 | switch (opcode) |
012309e6 | 612 | { |
0e0ed594 JL |
613 | case BIT_AND_EXPR: |
614 | if (integer_zerop (oelast->op)) | |
615 | { | |
616 | if (VEC_length (operand_entry_t, *ops) != 1) | |
617 | { | |
618 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
619 | fprintf (dump_file, "Found & 0, removing all other ops\n"); | |
620 | ||
621 | reassociate_stats.ops_eliminated | |
622 | += VEC_length (operand_entry_t, *ops) - 1; | |
623 | ||
624 | VEC_free (operand_entry_t, heap, *ops); | |
625 | *ops = NULL; | |
626 | VEC_safe_push (operand_entry_t, heap, *ops, oelast); | |
627 | return; | |
628 | } | |
629 | } | |
630 | else if (integer_all_onesp (oelast->op)) | |
631 | { | |
632 | if (VEC_length (operand_entry_t, *ops) != 1) | |
633 | { | |
634 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
635 | fprintf (dump_file, "Found & -1, removing\n"); | |
636 | VEC_pop (operand_entry_t, *ops); | |
637 | reassociate_stats.ops_eliminated++; | |
638 | } | |
639 | } | |
640 | break; | |
641 | case BIT_IOR_EXPR: | |
642 | if (integer_all_onesp (oelast->op)) | |
643 | { | |
644 | if (VEC_length (operand_entry_t, *ops) != 1) | |
645 | { | |
646 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
647 | fprintf (dump_file, "Found | -1, removing all other ops\n"); | |
648 | ||
649 | reassociate_stats.ops_eliminated | |
650 | += VEC_length (operand_entry_t, *ops) - 1; | |
651 | ||
652 | VEC_free (operand_entry_t, heap, *ops); | |
653 | *ops = NULL; | |
654 | VEC_safe_push (operand_entry_t, heap, *ops, oelast); | |
655 | return; | |
656 | } | |
657 | } | |
658 | else if (integer_zerop (oelast->op)) | |
659 | { | |
660 | if (VEC_length (operand_entry_t, *ops) != 1) | |
661 | { | |
662 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
663 | fprintf (dump_file, "Found | 0, removing\n"); | |
664 | VEC_pop (operand_entry_t, *ops); | |
665 | reassociate_stats.ops_eliminated++; | |
666 | } | |
667 | } | |
668 | break; | |
669 | case MULT_EXPR: | |
2dc0f633 RG |
670 | if (integer_zerop (oelast->op) |
671 | || (FLOAT_TYPE_P (type) | |
672 | && !HONOR_NANS (TYPE_MODE (type)) | |
673 | && !HONOR_SIGNED_ZEROS (TYPE_MODE (type)) | |
674 | && real_zerop (oelast->op))) | |
0e0ed594 JL |
675 | { |
676 | if (VEC_length (operand_entry_t, *ops) != 1) | |
677 | { | |
678 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
679 | fprintf (dump_file, "Found * 0, removing all other ops\n"); | |
680 | ||
681 | reassociate_stats.ops_eliminated | |
682 | += VEC_length (operand_entry_t, *ops) - 1; | |
683 | VEC_free (operand_entry_t, heap, *ops); | |
684 | *ops = NULL; | |
685 | VEC_safe_push (operand_entry_t, heap, *ops, oelast); | |
686 | return; | |
687 | } | |
688 | } | |
2dc0f633 RG |
689 | else if (integer_onep (oelast->op) |
690 | || (FLOAT_TYPE_P (type) | |
691 | && !HONOR_SNANS (TYPE_MODE (type)) | |
692 | && real_onep (oelast->op))) | |
0e0ed594 JL |
693 | { |
694 | if (VEC_length (operand_entry_t, *ops) != 1) | |
695 | { | |
696 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
697 | fprintf (dump_file, "Found * 1, removing\n"); | |
698 | VEC_pop (operand_entry_t, *ops); | |
699 | reassociate_stats.ops_eliminated++; | |
700 | return; | |
701 | } | |
702 | } | |
703 | break; | |
704 | case BIT_XOR_EXPR: | |
705 | case PLUS_EXPR: | |
706 | case MINUS_EXPR: | |
2dc0f633 RG |
707 | if (integer_zerop (oelast->op) |
708 | || (FLOAT_TYPE_P (type) | |
709 | && (opcode == PLUS_EXPR || opcode == MINUS_EXPR) | |
710 | && fold_real_zero_addition_p (type, oelast->op, | |
711 | opcode == MINUS_EXPR))) | |
012309e6 | 712 | { |
0e0ed594 | 713 | if (VEC_length (operand_entry_t, *ops) != 1) |
012309e6 | 714 | { |
0e0ed594 JL |
715 | if (dump_file && (dump_flags & TDF_DETAILS)) |
716 | fprintf (dump_file, "Found [|^+] 0, removing\n"); | |
717 | VEC_pop (operand_entry_t, *ops); | |
718 | reassociate_stats.ops_eliminated++; | |
719 | return; | |
012309e6 | 720 | } |
012309e6 | 721 | } |
0e0ed594 JL |
722 | break; |
723 | default: | |
724 | break; | |
012309e6 DB |
725 | } |
726 | } | |
012309e6 DB |
727 | } |
728 | ||
25c6036a RG |
729 | |
730 | static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple, | |
731 | bool, bool); | |
732 | ||
733 | /* Structure for tracking and counting operands. */ | |
734 | typedef struct oecount_s { | |
735 | int cnt; | |
736 | enum tree_code oecode; | |
737 | tree op; | |
738 | } oecount; | |
739 | ||
740 | DEF_VEC_O(oecount); | |
741 | DEF_VEC_ALLOC_O(oecount,heap); | |
742 | ||
743 | /* The heap for the oecount hashtable and the sorted list of operands. */ | |
744 | static VEC (oecount, heap) *cvec; | |
745 | ||
746 | /* Hash function for oecount. */ | |
747 | ||
748 | static hashval_t | |
749 | oecount_hash (const void *p) | |
750 | { | |
751 | const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42); | |
752 | return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode; | |
753 | } | |
754 | ||
755 | /* Comparison function for oecount. */ | |
756 | ||
757 | static int | |
758 | oecount_eq (const void *p1, const void *p2) | |
759 | { | |
760 | const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42); | |
761 | const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42); | |
762 | return (c1->oecode == c2->oecode | |
763 | && c1->op == c2->op); | |
764 | } | |
765 | ||
766 | /* Comparison function for qsort sorting oecount elements by count. */ | |
767 | ||
768 | static int | |
769 | oecount_cmp (const void *p1, const void *p2) | |
770 | { | |
771 | const oecount *c1 = (const oecount *)p1; | |
772 | const oecount *c2 = (const oecount *)p2; | |
773 | return c1->cnt - c2->cnt; | |
774 | } | |
775 | ||
776 | /* Walks the linear chain with result *DEF searching for an operation | |
777 | with operand OP and code OPCODE removing that from the chain. *DEF | |
778 | is updated if there is only one operand but no operation left. */ | |
779 | ||
780 | static void | |
781 | zero_one_operation (tree *def, enum tree_code opcode, tree op) | |
782 | { | |
783 | gimple stmt = SSA_NAME_DEF_STMT (*def); | |
784 | ||
785 | do | |
786 | { | |
787 | tree name = gimple_assign_rhs1 (stmt); | |
788 | ||
789 | /* If this is the operation we look for and one of the operands | |
790 | is ours simply propagate the other operand into the stmts | |
791 | single use. */ | |
792 | if (gimple_assign_rhs_code (stmt) == opcode | |
793 | && (name == op | |
794 | || gimple_assign_rhs2 (stmt) == op)) | |
795 | { | |
796 | gimple use_stmt; | |
797 | use_operand_p use; | |
798 | gimple_stmt_iterator gsi; | |
799 | if (name == op) | |
800 | name = gimple_assign_rhs2 (stmt); | |
801 | gcc_assert (has_single_use (gimple_assign_lhs (stmt))); | |
802 | single_imm_use (gimple_assign_lhs (stmt), &use, &use_stmt); | |
803 | if (gimple_assign_lhs (stmt) == *def) | |
804 | *def = name; | |
805 | SET_USE (use, name); | |
806 | if (TREE_CODE (name) != SSA_NAME) | |
807 | update_stmt (use_stmt); | |
808 | gsi = gsi_for_stmt (stmt); | |
809 | gsi_remove (&gsi, true); | |
810 | release_defs (stmt); | |
811 | return; | |
812 | } | |
813 | ||
814 | /* Continue walking the chain. */ | |
815 | gcc_assert (name != op | |
816 | && TREE_CODE (name) == SSA_NAME); | |
817 | stmt = SSA_NAME_DEF_STMT (name); | |
818 | } | |
819 | while (1); | |
820 | } | |
821 | ||
822 | /* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for | |
823 | the result. Places the statement after the definition of either | |
824 | OP1 or OP2. Returns the new statement. */ | |
825 | ||
826 | static gimple | |
827 | build_and_add_sum (tree tmpvar, tree op1, tree op2, enum tree_code opcode) | |
828 | { | |
829 | gimple op1def = NULL, op2def = NULL; | |
830 | gimple_stmt_iterator gsi; | |
831 | tree op; | |
832 | gimple sum; | |
833 | ||
834 | /* Create the addition statement. */ | |
835 | sum = gimple_build_assign_with_ops (opcode, tmpvar, op1, op2); | |
836 | op = make_ssa_name (tmpvar, sum); | |
837 | gimple_assign_set_lhs (sum, op); | |
838 | ||
839 | /* Find an insertion place and insert. */ | |
840 | if (TREE_CODE (op1) == SSA_NAME) | |
841 | op1def = SSA_NAME_DEF_STMT (op1); | |
842 | if (TREE_CODE (op2) == SSA_NAME) | |
843 | op2def = SSA_NAME_DEF_STMT (op2); | |
844 | if ((!op1def || gimple_nop_p (op1def)) | |
845 | && (!op2def || gimple_nop_p (op2def))) | |
846 | { | |
847 | gsi = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR)); | |
848 | gsi_insert_before (&gsi, sum, GSI_NEW_STMT); | |
849 | } | |
850 | else if ((!op1def || gimple_nop_p (op1def)) | |
851 | || (op2def && !gimple_nop_p (op2def) | |
852 | && stmt_dominates_stmt_p (op1def, op2def))) | |
853 | { | |
854 | if (gimple_code (op2def) == GIMPLE_PHI) | |
855 | { | |
856 | gsi = gsi_start_bb (gimple_bb (op2def)); | |
857 | gsi_insert_before (&gsi, sum, GSI_NEW_STMT); | |
858 | } | |
859 | else | |
860 | { | |
e7089ecf RG |
861 | if (!stmt_ends_bb_p (op2def)) |
862 | { | |
863 | gsi = gsi_for_stmt (op2def); | |
864 | gsi_insert_after (&gsi, sum, GSI_NEW_STMT); | |
865 | } | |
866 | else | |
867 | { | |
868 | edge e; | |
869 | edge_iterator ei; | |
870 | ||
871 | FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs) | |
872 | if (e->flags & EDGE_FALLTHRU) | |
873 | gsi_insert_on_edge_immediate (e, sum); | |
874 | } | |
25c6036a RG |
875 | } |
876 | } | |
877 | else | |
878 | { | |
879 | if (gimple_code (op1def) == GIMPLE_PHI) | |
880 | { | |
881 | gsi = gsi_start_bb (gimple_bb (op1def)); | |
882 | gsi_insert_before (&gsi, sum, GSI_NEW_STMT); | |
883 | } | |
884 | else | |
885 | { | |
e7089ecf RG |
886 | if (!stmt_ends_bb_p (op1def)) |
887 | { | |
888 | gsi = gsi_for_stmt (op1def); | |
889 | gsi_insert_after (&gsi, sum, GSI_NEW_STMT); | |
890 | } | |
891 | else | |
892 | { | |
893 | edge e; | |
894 | edge_iterator ei; | |
895 | ||
896 | FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs) | |
897 | if (e->flags & EDGE_FALLTHRU) | |
898 | gsi_insert_on_edge_immediate (e, sum); | |
899 | } | |
25c6036a RG |
900 | } |
901 | } | |
902 | update_stmt (sum); | |
903 | ||
904 | return sum; | |
905 | } | |
906 | ||
907 | /* Perform un-distribution of divisions and multiplications. | |
908 | A * X + B * X is transformed into (A + B) * X and A / X + B / X | |
909 | to (A + B) / X for real X. | |
910 | ||
911 | The algorithm is organized as follows. | |
912 | ||
913 | - First we walk the addition chain *OPS looking for summands that | |
914 | are defined by a multiplication or a real division. This results | |
915 | in the candidates bitmap with relevant indices into *OPS. | |
916 | ||
917 | - Second we build the chains of multiplications or divisions for | |
918 | these candidates, counting the number of occurences of (operand, code) | |
919 | pairs in all of the candidates chains. | |
920 | ||
921 | - Third we sort the (operand, code) pairs by number of occurence and | |
922 | process them starting with the pair with the most uses. | |
923 | ||
924 | * For each such pair we walk the candidates again to build a | |
925 | second candidate bitmap noting all multiplication/division chains | |
926 | that have at least one occurence of (operand, code). | |
927 | ||
928 | * We build an alternate addition chain only covering these | |
929 | candidates with one (operand, code) operation removed from their | |
930 | multiplication/division chain. | |
931 | ||
932 | * The first candidate gets replaced by the alternate addition chain | |
933 | multiplied/divided by the operand. | |
934 | ||
935 | * All candidate chains get disabled for further processing and | |
936 | processing of (operand, code) pairs continues. | |
937 | ||
938 | The alternate addition chains built are re-processed by the main | |
939 | reassociation algorithm which allows optimizing a * x * y + b * y * x | |
940 | to (a + b ) * x * y in one invocation of the reassociation pass. */ | |
941 | ||
942 | static bool | |
943 | undistribute_ops_list (enum tree_code opcode, | |
944 | VEC (operand_entry_t, heap) **ops, struct loop *loop) | |
945 | { | |
946 | unsigned int length = VEC_length (operand_entry_t, *ops); | |
947 | operand_entry_t oe1; | |
948 | unsigned i, j; | |
949 | sbitmap candidates, candidates2; | |
950 | unsigned nr_candidates, nr_candidates2; | |
951 | sbitmap_iterator sbi0; | |
952 | VEC (operand_entry_t, heap) **subops; | |
953 | htab_t ctable; | |
954 | bool changed = false; | |
955 | ||
956 | if (length <= 1 | |
957 | || opcode != PLUS_EXPR) | |
958 | return false; | |
959 | ||
960 | /* Build a list of candidates to process. */ | |
961 | candidates = sbitmap_alloc (length); | |
962 | sbitmap_zero (candidates); | |
963 | nr_candidates = 0; | |
964 | for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe1); ++i) | |
965 | { | |
966 | enum tree_code dcode; | |
967 | gimple oe1def; | |
968 | ||
969 | if (TREE_CODE (oe1->op) != SSA_NAME) | |
970 | continue; | |
971 | oe1def = SSA_NAME_DEF_STMT (oe1->op); | |
972 | if (!is_gimple_assign (oe1def)) | |
973 | continue; | |
974 | dcode = gimple_assign_rhs_code (oe1def); | |
975 | if ((dcode != MULT_EXPR | |
976 | && dcode != RDIV_EXPR) | |
977 | || !is_reassociable_op (oe1def, dcode, loop)) | |
978 | continue; | |
979 | ||
980 | SET_BIT (candidates, i); | |
981 | nr_candidates++; | |
982 | } | |
983 | ||
984 | if (nr_candidates < 2) | |
985 | { | |
986 | sbitmap_free (candidates); | |
987 | return false; | |
988 | } | |
989 | ||
990 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
991 | { | |
992 | fprintf (dump_file, "searching for un-distribute opportunities "); | |
993 | print_generic_expr (dump_file, | |
994 | VEC_index (operand_entry_t, *ops, | |
995 | sbitmap_first_set_bit (candidates))->op, 0); | |
996 | fprintf (dump_file, " %d\n", nr_candidates); | |
997 | } | |
998 | ||
999 | /* Build linearized sub-operand lists and the counting table. */ | |
1000 | cvec = NULL; | |
1001 | ctable = htab_create (15, oecount_hash, oecount_eq, NULL); | |
1002 | subops = XCNEWVEC (VEC (operand_entry_t, heap) *, | |
1003 | VEC_length (operand_entry_t, *ops)); | |
1004 | EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0) | |
1005 | { | |
1006 | gimple oedef; | |
1007 | enum tree_code oecode; | |
1008 | unsigned j; | |
1009 | ||
1010 | oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op); | |
1011 | oecode = gimple_assign_rhs_code (oedef); | |
1012 | linearize_expr_tree (&subops[i], oedef, | |
1013 | associative_tree_code (oecode), false); | |
1014 | ||
1015 | for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j) | |
1016 | { | |
1017 | oecount c; | |
1018 | void **slot; | |
1019 | size_t idx; | |
1020 | c.oecode = oecode; | |
1021 | c.cnt = 1; | |
1022 | c.op = oe1->op; | |
1023 | VEC_safe_push (oecount, heap, cvec, &c); | |
1024 | idx = VEC_length (oecount, cvec) + 41; | |
1025 | slot = htab_find_slot (ctable, (void *)idx, INSERT); | |
1026 | if (!*slot) | |
1027 | { | |
1028 | *slot = (void *)idx; | |
1029 | } | |
1030 | else | |
1031 | { | |
1032 | VEC_pop (oecount, cvec); | |
1033 | VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++; | |
1034 | } | |
1035 | } | |
1036 | } | |
1037 | htab_delete (ctable); | |
1038 | ||
1039 | /* Sort the counting table. */ | |
1040 | qsort (VEC_address (oecount, cvec), VEC_length (oecount, cvec), | |
1041 | sizeof (oecount), oecount_cmp); | |
1042 | ||
1043 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1044 | { | |
1045 | oecount *c; | |
1046 | fprintf (dump_file, "Candidates:\n"); | |
1047 | for (j = 0; VEC_iterate (oecount, cvec, j, c); ++j) | |
1048 | { | |
1049 | fprintf (dump_file, " %u %s: ", c->cnt, | |
1050 | c->oecode == MULT_EXPR | |
1051 | ? "*" : c->oecode == RDIV_EXPR ? "/" : "?"); | |
1052 | print_generic_expr (dump_file, c->op, 0); | |
1053 | fprintf (dump_file, "\n"); | |
1054 | } | |
1055 | } | |
1056 | ||
1057 | /* Process the (operand, code) pairs in order of most occurence. */ | |
1058 | candidates2 = sbitmap_alloc (length); | |
1059 | while (!VEC_empty (oecount, cvec)) | |
1060 | { | |
1061 | oecount *c = VEC_last (oecount, cvec); | |
1062 | if (c->cnt < 2) | |
1063 | break; | |
1064 | ||
1065 | /* Now collect the operands in the outer chain that contain | |
1066 | the common operand in their inner chain. */ | |
1067 | sbitmap_zero (candidates2); | |
1068 | nr_candidates2 = 0; | |
1069 | EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0) | |
1070 | { | |
1071 | gimple oedef; | |
1072 | enum tree_code oecode; | |
1073 | unsigned j; | |
1074 | tree op = VEC_index (operand_entry_t, *ops, i)->op; | |
1075 | ||
1076 | /* If we undistributed in this chain already this may be | |
1077 | a constant. */ | |
1078 | if (TREE_CODE (op) != SSA_NAME) | |
1079 | continue; | |
1080 | ||
1081 | oedef = SSA_NAME_DEF_STMT (op); | |
1082 | oecode = gimple_assign_rhs_code (oedef); | |
1083 | if (oecode != c->oecode) | |
1084 | continue; | |
1085 | ||
1086 | for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j) | |
1087 | { | |
1088 | if (oe1->op == c->op) | |
1089 | { | |
1090 | SET_BIT (candidates2, i); | |
1091 | ++nr_candidates2; | |
1092 | break; | |
1093 | } | |
1094 | } | |
1095 | } | |
1096 | ||
1097 | if (nr_candidates2 >= 2) | |
1098 | { | |
1099 | operand_entry_t oe1, oe2; | |
1100 | tree tmpvar; | |
1101 | gimple prod; | |
1102 | int first = sbitmap_first_set_bit (candidates2); | |
1103 | ||
1104 | /* Build the new addition chain. */ | |
1105 | oe1 = VEC_index (operand_entry_t, *ops, first); | |
1106 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1107 | { | |
1108 | fprintf (dump_file, "Building ("); | |
1109 | print_generic_expr (dump_file, oe1->op, 0); | |
1110 | } | |
1111 | tmpvar = create_tmp_var (TREE_TYPE (oe1->op), NULL); | |
1112 | add_referenced_var (tmpvar); | |
1113 | zero_one_operation (&oe1->op, c->oecode, c->op); | |
1114 | EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0) | |
1115 | { | |
1116 | gimple sum; | |
1117 | oe2 = VEC_index (operand_entry_t, *ops, i); | |
1118 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1119 | { | |
1120 | fprintf (dump_file, " + "); | |
1121 | print_generic_expr (dump_file, oe2->op, 0); | |
1122 | } | |
1123 | zero_one_operation (&oe2->op, c->oecode, c->op); | |
1124 | sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode); | |
1125 | oe2->op = fold_convert (TREE_TYPE (oe2->op), integer_zero_node); | |
1126 | oe2->rank = 0; | |
1127 | oe1->op = gimple_get_lhs (sum); | |
1128 | } | |
1129 | ||
1130 | /* Apply the multiplication/division. */ | |
1131 | prod = build_and_add_sum (tmpvar, oe1->op, c->op, c->oecode); | |
1132 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1133 | { | |
1134 | fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/"); | |
1135 | print_generic_expr (dump_file, c->op, 0); | |
1136 | fprintf (dump_file, "\n"); | |
1137 | } | |
1138 | ||
1139 | /* Record it in the addition chain and disable further | |
1140 | undistribution with this op. */ | |
1141 | oe1->op = gimple_assign_lhs (prod); | |
1142 | oe1->rank = get_rank (oe1->op); | |
1143 | VEC_free (operand_entry_t, heap, subops[first]); | |
1144 | ||
1145 | changed = true; | |
1146 | } | |
1147 | ||
1148 | VEC_pop (oecount, cvec); | |
1149 | } | |
1150 | ||
1151 | for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i) | |
1152 | VEC_free (operand_entry_t, heap, subops[i]); | |
1153 | free (subops); | |
1154 | VEC_free (oecount, heap, cvec); | |
1155 | sbitmap_free (candidates); | |
1156 | sbitmap_free (candidates2); | |
1157 | ||
1158 | return changed; | |
1159 | } | |
1160 | ||
1161 | ||
0e0ed594 JL |
1162 | /* Perform various identities and other optimizations on the list of |
1163 | operand entries, stored in OPS. The tree code for the binary | |
1164 | operation between all the operands is OPCODE. */ | |
012309e6 | 1165 | |
0e0ed594 JL |
1166 | static void |
1167 | optimize_ops_list (enum tree_code opcode, | |
1168 | VEC (operand_entry_t, heap) **ops) | |
1169 | { | |
1170 | unsigned int length = VEC_length (operand_entry_t, *ops); | |
1171 | unsigned int i; | |
1172 | operand_entry_t oe; | |
1173 | operand_entry_t oelast = NULL; | |
1174 | bool iterate = false; | |
012309e6 | 1175 | |
0e0ed594 JL |
1176 | if (length == 1) |
1177 | return; | |
012309e6 | 1178 | |
0e0ed594 | 1179 | oelast = VEC_last (operand_entry_t, *ops); |
012309e6 | 1180 | |
0e0ed594 JL |
1181 | /* If the last two are constants, pop the constants off, merge them |
1182 | and try the next two. */ | |
1183 | if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op)) | |
1184 | { | |
1185 | operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2); | |
1186 | ||
1187 | if (oelm1->rank == 0 | |
1188 | && is_gimple_min_invariant (oelm1->op) | |
f4088621 RG |
1189 | && useless_type_conversion_p (TREE_TYPE (oelm1->op), |
1190 | TREE_TYPE (oelast->op))) | |
0e0ed594 | 1191 | { |
0dd4b47b | 1192 | tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op), |
0e0ed594 JL |
1193 | oelm1->op, oelast->op); |
1194 | ||
0dd4b47b | 1195 | if (folded && is_gimple_min_invariant (folded)) |
0e0ed594 JL |
1196 | { |
1197 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1198 | fprintf (dump_file, "Merging constants\n"); | |
1199 | ||
1200 | VEC_pop (operand_entry_t, *ops); | |
1201 | VEC_pop (operand_entry_t, *ops); | |
1202 | ||
1203 | add_to_ops_vec (ops, folded); | |
1204 | reassociate_stats.constants_eliminated++; | |
1205 | ||
1206 | optimize_ops_list (opcode, ops); | |
1207 | return; | |
1208 | } | |
1209 | } | |
1210 | } | |
1211 | ||
1212 | eliminate_using_constants (opcode, ops); | |
1213 | oelast = NULL; | |
1214 | ||
1215 | for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);) | |
1216 | { | |
1217 | bool done = false; | |
1218 | ||
1219 | if (eliminate_not_pairs (opcode, ops, i, oe)) | |
1220 | return; | |
1221 | if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast) | |
1222 | || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe))) | |
1223 | { | |
1224 | if (done) | |
1225 | return; | |
1226 | iterate = true; | |
1227 | oelast = NULL; | |
1228 | continue; | |
1229 | } | |
1230 | oelast = oe; | |
1231 | i++; | |
1232 | } | |
1233 | ||
1234 | length = VEC_length (operand_entry_t, *ops); | |
1235 | oelast = VEC_last (operand_entry_t, *ops); | |
1236 | ||
1237 | if (iterate) | |
1238 | optimize_ops_list (opcode, ops); | |
1239 | } | |
1240 | ||
1241 | /* Return true if OPERAND is defined by a PHI node which uses the LHS | |
1242 | of STMT in it's operands. This is also known as a "destructive | |
1243 | update" operation. */ | |
1244 | ||
1245 | static bool | |
726a989a | 1246 | is_phi_for_stmt (gimple stmt, tree operand) |
0e0ed594 | 1247 | { |
726a989a RB |
1248 | gimple def_stmt; |
1249 | tree lhs; | |
0e0ed594 JL |
1250 | use_operand_p arg_p; |
1251 | ssa_op_iter i; | |
1252 | ||
1253 | if (TREE_CODE (operand) != SSA_NAME) | |
1254 | return false; | |
1255 | ||
726a989a RB |
1256 | lhs = gimple_assign_lhs (stmt); |
1257 | ||
0e0ed594 | 1258 | def_stmt = SSA_NAME_DEF_STMT (operand); |
726a989a | 1259 | if (gimple_code (def_stmt) != GIMPLE_PHI) |
0e0ed594 JL |
1260 | return false; |
1261 | ||
1262 | FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE) | |
1263 | if (lhs == USE_FROM_PTR (arg_p)) | |
1264 | return true; | |
1265 | return false; | |
1266 | } | |
1267 | ||
ec81df7d JJ |
1268 | /* Remove def stmt of VAR if VAR has zero uses and recurse |
1269 | on rhs1 operand if so. */ | |
1270 | ||
1271 | static void | |
1272 | remove_visited_stmt_chain (tree var) | |
1273 | { | |
1274 | gimple stmt; | |
1275 | gimple_stmt_iterator gsi; | |
1276 | ||
1277 | while (1) | |
1278 | { | |
1279 | if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var)) | |
1280 | return; | |
1281 | stmt = SSA_NAME_DEF_STMT (var); | |
c2152239 JJ |
1282 | if (!is_gimple_assign (stmt) |
1283 | || !gimple_visited_p (stmt)) | |
ec81df7d JJ |
1284 | return; |
1285 | var = gimple_assign_rhs1 (stmt); | |
1286 | gsi = gsi_for_stmt (stmt); | |
1287 | gsi_remove (&gsi, true); | |
1288 | release_defs (stmt); | |
1289 | } | |
1290 | } | |
1291 | ||
0e0ed594 JL |
1292 | /* Recursively rewrite our linearized statements so that the operators |
1293 | match those in OPS[OPINDEX], putting the computation in rank | |
1294 | order. */ | |
1295 | ||
1296 | static void | |
726a989a | 1297 | rewrite_expr_tree (gimple stmt, unsigned int opindex, |
ec81df7d | 1298 | VEC(operand_entry_t, heap) * ops, bool moved) |
0e0ed594 | 1299 | { |
726a989a RB |
1300 | tree rhs1 = gimple_assign_rhs1 (stmt); |
1301 | tree rhs2 = gimple_assign_rhs2 (stmt); | |
0e0ed594 JL |
1302 | operand_entry_t oe; |
1303 | ||
1304 | /* If we have three operands left, then we want to make sure the one | |
1305 | that gets the double binary op are the ones with the same rank. | |
1306 | ||
1307 | The alternative we try is to see if this is a destructive | |
1308 | update style statement, which is like: | |
1309 | b = phi (a, ...) | |
1310 | a = c + b; | |
1311 | In that case, we want to use the destructive update form to | |
1312 | expose the possible vectorizer sum reduction opportunity. | |
1313 | In that case, the third operand will be the phi node. | |
1314 | ||
1315 | We could, of course, try to be better as noted above, and do a | |
1316 | lot of work to try to find these opportunities in >3 operand | |
1317 | cases, but it is unlikely to be worth it. */ | |
1318 | if (opindex + 3 == VEC_length (operand_entry_t, ops)) | |
1319 | { | |
1320 | operand_entry_t oe1, oe2, oe3; | |
1321 | ||
1322 | oe1 = VEC_index (operand_entry_t, ops, opindex); | |
1323 | oe2 = VEC_index (operand_entry_t, ops, opindex + 1); | |
1324 | oe3 = VEC_index (operand_entry_t, ops, opindex + 2); | |
1325 | ||
1326 | if ((oe1->rank == oe2->rank | |
1327 | && oe2->rank != oe3->rank) | |
1328 | || (is_phi_for_stmt (stmt, oe3->op) | |
1329 | && !is_phi_for_stmt (stmt, oe1->op) | |
1330 | && !is_phi_for_stmt (stmt, oe2->op))) | |
1331 | { | |
1332 | struct operand_entry temp = *oe3; | |
1333 | oe3->op = oe1->op; | |
1334 | oe3->rank = oe1->rank; | |
1335 | oe1->op = temp.op; | |
1336 | oe1->rank= temp.rank; | |
1337 | } | |
c4ae80d9 UB |
1338 | else if ((oe1->rank == oe3->rank |
1339 | && oe2->rank != oe3->rank) | |
1340 | || (is_phi_for_stmt (stmt, oe2->op) | |
1341 | && !is_phi_for_stmt (stmt, oe1->op) | |
1342 | && !is_phi_for_stmt (stmt, oe3->op))) | |
1343 | { | |
1344 | struct operand_entry temp = *oe2; | |
1345 | oe2->op = oe1->op; | |
1346 | oe2->rank = oe1->rank; | |
1347 | oe1->op = temp.op; | |
1348 | oe1->rank= temp.rank; | |
1349 | } | |
0e0ed594 JL |
1350 | } |
1351 | ||
1352 | /* The final recursion case for this function is that you have | |
1353 | exactly two operations left. | |
1354 | If we had one exactly one op in the entire list to start with, we | |
1355 | would have never called this function, and the tail recursion | |
1356 | rewrites them one at a time. */ | |
1357 | if (opindex + 2 == VEC_length (operand_entry_t, ops)) | |
1358 | { | |
1359 | operand_entry_t oe1, oe2; | |
1360 | ||
1361 | oe1 = VEC_index (operand_entry_t, ops, opindex); | |
1362 | oe2 = VEC_index (operand_entry_t, ops, opindex + 1); | |
1363 | ||
726a989a | 1364 | if (rhs1 != oe1->op || rhs2 != oe2->op) |
0e0ed594 | 1365 | { |
0e0ed594 JL |
1366 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1367 | { | |
1368 | fprintf (dump_file, "Transforming "); | |
726a989a | 1369 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1370 | } |
1371 | ||
726a989a RB |
1372 | gimple_assign_set_rhs1 (stmt, oe1->op); |
1373 | gimple_assign_set_rhs2 (stmt, oe2->op); | |
0e0ed594 | 1374 | update_stmt (stmt); |
ec81df7d JJ |
1375 | if (rhs1 != oe1->op && rhs1 != oe2->op) |
1376 | remove_visited_stmt_chain (rhs1); | |
0e0ed594 JL |
1377 | |
1378 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1379 | { | |
1380 | fprintf (dump_file, " into "); | |
726a989a | 1381 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1382 | } |
1383 | ||
1384 | } | |
1385 | return; | |
1386 | } | |
1387 | ||
1388 | /* If we hit here, we should have 3 or more ops left. */ | |
1389 | gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops)); | |
1390 | ||
1391 | /* Rewrite the next operator. */ | |
1392 | oe = VEC_index (operand_entry_t, ops, opindex); | |
1393 | ||
726a989a | 1394 | if (oe->op != rhs2) |
0e0ed594 | 1395 | { |
ec81df7d JJ |
1396 | if (!moved) |
1397 | { | |
1398 | gimple_stmt_iterator gsinow, gsirhs1; | |
1399 | gimple stmt1 = stmt, stmt2; | |
1400 | unsigned int count; | |
1401 | ||
1402 | gsinow = gsi_for_stmt (stmt); | |
1403 | count = VEC_length (operand_entry_t, ops) - opindex - 2; | |
1404 | while (count-- != 0) | |
1405 | { | |
1406 | stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1)); | |
1407 | gsirhs1 = gsi_for_stmt (stmt2); | |
b5b8b0ac | 1408 | propagate_defs_into_debug_stmts (stmt2, gimple_bb (stmt), &gsinow); |
ec81df7d JJ |
1409 | gsi_move_before (&gsirhs1, &gsinow); |
1410 | gsi_prev (&gsinow); | |
1411 | stmt1 = stmt2; | |
1412 | } | |
1413 | moved = true; | |
1414 | } | |
0e0ed594 JL |
1415 | |
1416 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1417 | { | |
1418 | fprintf (dump_file, "Transforming "); | |
726a989a | 1419 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1420 | } |
1421 | ||
726a989a | 1422 | gimple_assign_set_rhs2 (stmt, oe->op); |
0e0ed594 JL |
1423 | update_stmt (stmt); |
1424 | ||
1425 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1426 | { | |
1427 | fprintf (dump_file, " into "); | |
726a989a | 1428 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1429 | } |
1430 | } | |
1431 | /* Recurse on the LHS of the binary operator, which is guaranteed to | |
1432 | be the non-leaf side. */ | |
ec81df7d | 1433 | rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops, moved); |
0e0ed594 JL |
1434 | } |
1435 | ||
1436 | /* Transform STMT, which is really (A +B) + (C + D) into the left | |
1437 | linear form, ((A+B)+C)+D. | |
1438 | Recurse on D if necessary. */ | |
1439 | ||
1440 | static void | |
726a989a | 1441 | linearize_expr (gimple stmt) |
0e0ed594 | 1442 | { |
726a989a RB |
1443 | gimple_stmt_iterator gsinow, gsirhs; |
1444 | gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); | |
1445 | gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); | |
1446 | enum tree_code rhscode = gimple_assign_rhs_code (stmt); | |
1447 | gimple newbinrhs = NULL; | |
7a9c7d01 | 1448 | struct loop *loop = loop_containing_stmt (stmt); |
0e0ed594 | 1449 | |
726a989a RB |
1450 | gcc_assert (is_reassociable_op (binlhs, rhscode, loop) |
1451 | && is_reassociable_op (binrhs, rhscode, loop)); | |
1452 | ||
1453 | gsinow = gsi_for_stmt (stmt); | |
1454 | gsirhs = gsi_for_stmt (binrhs); | |
b5b8b0ac | 1455 | propagate_defs_into_debug_stmts (binrhs, gimple_bb (stmt), &gsinow); |
726a989a | 1456 | gsi_move_before (&gsirhs, &gsinow); |
0e0ed594 | 1457 | |
726a989a RB |
1458 | gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs)); |
1459 | gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs)); | |
1460 | gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs)); | |
0e0ed594 | 1461 | |
726a989a RB |
1462 | if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME) |
1463 | newbinrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); | |
0e0ed594 JL |
1464 | |
1465 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1466 | { | |
1467 | fprintf (dump_file, "Linearized: "); | |
726a989a | 1468 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1469 | } |
1470 | ||
1471 | reassociate_stats.linearized++; | |
1472 | update_stmt (binrhs); | |
1473 | update_stmt (binlhs); | |
1474 | update_stmt (stmt); | |
726a989a RB |
1475 | |
1476 | gimple_set_visited (stmt, true); | |
1477 | gimple_set_visited (binlhs, true); | |
1478 | gimple_set_visited (binrhs, true); | |
0e0ed594 JL |
1479 | |
1480 | /* Tail recurse on the new rhs if it still needs reassociation. */ | |
7a9c7d01 | 1481 | if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop)) |
726a989a RB |
1482 | /* ??? This should probably be linearize_expr (newbinrhs) but I don't |
1483 | want to change the algorithm while converting to tuples. */ | |
0e0ed594 | 1484 | linearize_expr (stmt); |
0e0ed594 JL |
1485 | } |
1486 | ||
726a989a | 1487 | /* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return |
0e0ed594 JL |
1488 | it. Otherwise, return NULL. */ |
1489 | ||
726a989a | 1490 | static gimple |
0e0ed594 JL |
1491 | get_single_immediate_use (tree lhs) |
1492 | { | |
1493 | use_operand_p immuse; | |
726a989a | 1494 | gimple immusestmt; |
0e0ed594 JL |
1495 | |
1496 | if (TREE_CODE (lhs) == SSA_NAME | |
726a989a RB |
1497 | && single_imm_use (lhs, &immuse, &immusestmt) |
1498 | && is_gimple_assign (immusestmt)) | |
1499 | return immusestmt; | |
1500 | ||
1501 | return NULL; | |
0e0ed594 | 1502 | } |
0e0ed594 | 1503 | |
726a989a | 1504 | static VEC(tree, heap) *broken_up_subtracts; |
0e0ed594 JL |
1505 | |
1506 | /* Recursively negate the value of TONEGATE, and return the SSA_NAME | |
1507 | representing the negated value. Insertions of any necessary | |
726a989a | 1508 | instructions go before GSI. |
0e0ed594 JL |
1509 | This function is recursive in that, if you hand it "a_5" as the |
1510 | value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will | |
1511 | transform b_3 + b_4 into a_5 = -b_3 + -b_4. */ | |
1512 | ||
1513 | static tree | |
726a989a | 1514 | negate_value (tree tonegate, gimple_stmt_iterator *gsi) |
0e0ed594 | 1515 | { |
726a989a | 1516 | gimple negatedefstmt= NULL; |
0e0ed594 JL |
1517 | tree resultofnegate; |
1518 | ||
0e0ed594 JL |
1519 | /* If we are trying to negate a name, defined by an add, negate the |
1520 | add operands instead. */ | |
726a989a RB |
1521 | if (TREE_CODE (tonegate) == SSA_NAME) |
1522 | negatedefstmt = SSA_NAME_DEF_STMT (tonegate); | |
0e0ed594 | 1523 | if (TREE_CODE (tonegate) == SSA_NAME |
726a989a RB |
1524 | && is_gimple_assign (negatedefstmt) |
1525 | && TREE_CODE (gimple_assign_lhs (negatedefstmt)) == SSA_NAME | |
1526 | && has_single_use (gimple_assign_lhs (negatedefstmt)) | |
1527 | && gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR) | |
0e0ed594 | 1528 | { |
726a989a RB |
1529 | gimple_stmt_iterator gsi; |
1530 | tree rhs1 = gimple_assign_rhs1 (negatedefstmt); | |
1531 | tree rhs2 = gimple_assign_rhs2 (negatedefstmt); | |
1532 | ||
1533 | gsi = gsi_for_stmt (negatedefstmt); | |
1534 | rhs1 = negate_value (rhs1, &gsi); | |
1535 | gimple_assign_set_rhs1 (negatedefstmt, rhs1); | |
1536 | ||
1537 | gsi = gsi_for_stmt (negatedefstmt); | |
1538 | rhs2 = negate_value (rhs2, &gsi); | |
1539 | gimple_assign_set_rhs2 (negatedefstmt, rhs2); | |
1540 | ||
1541 | update_stmt (negatedefstmt); | |
1542 | return gimple_assign_lhs (negatedefstmt); | |
0e0ed594 JL |
1543 | } |
1544 | ||
1545 | tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate); | |
726a989a RB |
1546 | resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true, |
1547 | NULL_TREE, true, GSI_SAME_STMT); | |
0e0ed594 JL |
1548 | VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate); |
1549 | return resultofnegate; | |
0e0ed594 JL |
1550 | } |
1551 | ||
1552 | /* Return true if we should break up the subtract in STMT into an add | |
1553 | with negate. This is true when we the subtract operands are really | |
1554 | adds, or the subtract itself is used in an add expression. In | |
1555 | either case, breaking up the subtract into an add with negate | |
1556 | exposes the adds to reassociation. */ | |
1557 | ||
1558 | static bool | |
726a989a | 1559 | should_break_up_subtract (gimple stmt) |
0e0ed594 | 1560 | { |
726a989a RB |
1561 | tree lhs = gimple_assign_lhs (stmt); |
1562 | tree binlhs = gimple_assign_rhs1 (stmt); | |
1563 | tree binrhs = gimple_assign_rhs2 (stmt); | |
1564 | gimple immusestmt; | |
7a9c7d01 | 1565 | struct loop *loop = loop_containing_stmt (stmt); |
0e0ed594 JL |
1566 | |
1567 | if (TREE_CODE (binlhs) == SSA_NAME | |
7a9c7d01 | 1568 | && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop)) |
0e0ed594 JL |
1569 | return true; |
1570 | ||
1571 | if (TREE_CODE (binrhs) == SSA_NAME | |
7a9c7d01 | 1572 | && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop)) |
0e0ed594 JL |
1573 | return true; |
1574 | ||
1575 | if (TREE_CODE (lhs) == SSA_NAME | |
1576 | && (immusestmt = get_single_immediate_use (lhs)) | |
726a989a | 1577 | && is_gimple_assign (immusestmt) |
25c6036a RG |
1578 | && (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR |
1579 | || gimple_assign_rhs_code (immusestmt) == MULT_EXPR)) | |
0e0ed594 JL |
1580 | return true; |
1581 | return false; | |
0e0ed594 JL |
1582 | } |
1583 | ||
1584 | /* Transform STMT from A - B into A + -B. */ | |
1585 | ||
1586 | static void | |
726a989a | 1587 | break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip) |
0e0ed594 | 1588 | { |
726a989a RB |
1589 | tree rhs1 = gimple_assign_rhs1 (stmt); |
1590 | tree rhs2 = gimple_assign_rhs2 (stmt); | |
0e0ed594 JL |
1591 | |
1592 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1593 | { | |
1594 | fprintf (dump_file, "Breaking up subtract "); | |
726a989a | 1595 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1596 | } |
1597 | ||
726a989a RB |
1598 | rhs2 = negate_value (rhs2, gsip); |
1599 | gimple_assign_set_rhs_with_ops (gsip, PLUS_EXPR, rhs1, rhs2); | |
0e0ed594 JL |
1600 | update_stmt (stmt); |
1601 | } | |
1602 | ||
1603 | /* Recursively linearize a binary expression that is the RHS of STMT. | |
1604 | Place the operands of the expression tree in the vector named OPS. */ | |
1605 | ||
1606 | static void | |
25c6036a RG |
1607 | linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt, |
1608 | bool is_associative, bool set_visited) | |
0e0ed594 | 1609 | { |
726a989a RB |
1610 | tree binlhs = gimple_assign_rhs1 (stmt); |
1611 | tree binrhs = gimple_assign_rhs2 (stmt); | |
1612 | gimple binlhsdef, binrhsdef; | |
0e0ed594 JL |
1613 | bool binlhsisreassoc = false; |
1614 | bool binrhsisreassoc = false; | |
726a989a | 1615 | enum tree_code rhscode = gimple_assign_rhs_code (stmt); |
7a9c7d01 | 1616 | struct loop *loop = loop_containing_stmt (stmt); |
0e0ed594 | 1617 | |
25c6036a RG |
1618 | if (set_visited) |
1619 | gimple_set_visited (stmt, true); | |
0e0ed594 JL |
1620 | |
1621 | if (TREE_CODE (binlhs) == SSA_NAME) | |
1622 | { | |
1623 | binlhsdef = SSA_NAME_DEF_STMT (binlhs); | |
7a9c7d01 | 1624 | binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop); |
0e0ed594 JL |
1625 | } |
1626 | ||
1627 | if (TREE_CODE (binrhs) == SSA_NAME) | |
1628 | { | |
1629 | binrhsdef = SSA_NAME_DEF_STMT (binrhs); | |
7a9c7d01 | 1630 | binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop); |
0e0ed594 JL |
1631 | } |
1632 | ||
1633 | /* If the LHS is not reassociable, but the RHS is, we need to swap | |
1634 | them. If neither is reassociable, there is nothing we can do, so | |
1635 | just put them in the ops vector. If the LHS is reassociable, | |
1636 | linearize it. If both are reassociable, then linearize the RHS | |
1637 | and the LHS. */ | |
1638 | ||
1639 | if (!binlhsisreassoc) | |
1640 | { | |
1641 | tree temp; | |
1642 | ||
25c6036a RG |
1643 | /* If this is not a associative operation like division, give up. */ |
1644 | if (!is_associative) | |
1645 | { | |
1646 | add_to_ops_vec (ops, binrhs); | |
1647 | return; | |
1648 | } | |
1649 | ||
0e0ed594 JL |
1650 | if (!binrhsisreassoc) |
1651 | { | |
1652 | add_to_ops_vec (ops, binrhs); | |
1653 | add_to_ops_vec (ops, binlhs); | |
1654 | return; | |
1655 | } | |
1656 | ||
1657 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1658 | { | |
1659 | fprintf (dump_file, "swapping operands of "); | |
726a989a | 1660 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1661 | } |
1662 | ||
726a989a RB |
1663 | swap_tree_operands (stmt, |
1664 | gimple_assign_rhs1_ptr (stmt), | |
1665 | gimple_assign_rhs2_ptr (stmt)); | |
0e0ed594 JL |
1666 | update_stmt (stmt); |
1667 | ||
1668 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1669 | { | |
1670 | fprintf (dump_file, " is now "); | |
726a989a | 1671 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1672 | } |
1673 | ||
1674 | /* We want to make it so the lhs is always the reassociative op, | |
1675 | so swap. */ | |
1676 | temp = binlhs; | |
1677 | binlhs = binrhs; | |
1678 | binrhs = temp; | |
1679 | } | |
1680 | else if (binrhsisreassoc) | |
1681 | { | |
1682 | linearize_expr (stmt); | |
726a989a RB |
1683 | binlhs = gimple_assign_rhs1 (stmt); |
1684 | binrhs = gimple_assign_rhs2 (stmt); | |
0e0ed594 JL |
1685 | } |
1686 | ||
1687 | gcc_assert (TREE_CODE (binrhs) != SSA_NAME | |
7a9c7d01 ZD |
1688 | || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), |
1689 | rhscode, loop)); | |
25c6036a RG |
1690 | linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs), |
1691 | is_associative, set_visited); | |
0e0ed594 JL |
1692 | add_to_ops_vec (ops, binrhs); |
1693 | } | |
1694 | ||
1695 | /* Repropagate the negates back into subtracts, since no other pass | |
1696 | currently does it. */ | |
1697 | ||
1698 | static void | |
1699 | repropagate_negates (void) | |
1700 | { | |
1701 | unsigned int i = 0; | |
1702 | tree negate; | |
1703 | ||
1704 | for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++) | |
1705 | { | |
726a989a | 1706 | gimple user = get_single_immediate_use (negate); |
0e0ed594 JL |
1707 | |
1708 | /* The negate operand can be either operand of a PLUS_EXPR | |
1709 | (it can be the LHS if the RHS is a constant for example). | |
1710 | ||
1711 | Force the negate operand to the RHS of the PLUS_EXPR, then | |
1712 | transform the PLUS_EXPR into a MINUS_EXPR. */ | |
1713 | if (user | |
726a989a RB |
1714 | && is_gimple_assign (user) |
1715 | && gimple_assign_rhs_code (user) == PLUS_EXPR) | |
0e0ed594 | 1716 | { |
0e0ed594 JL |
1717 | /* If the negated operand appears on the LHS of the |
1718 | PLUS_EXPR, exchange the operands of the PLUS_EXPR | |
1719 | to force the negated operand to the RHS of the PLUS_EXPR. */ | |
726a989a | 1720 | if (gimple_assign_rhs1 (user) == negate) |
0e0ed594 | 1721 | { |
726a989a RB |
1722 | swap_tree_operands (user, |
1723 | gimple_assign_rhs1_ptr (user), | |
1724 | gimple_assign_rhs2_ptr (user)); | |
0e0ed594 JL |
1725 | } |
1726 | ||
1727 | /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace | |
1728 | the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */ | |
726a989a | 1729 | if (gimple_assign_rhs2 (user) == negate) |
0e0ed594 | 1730 | { |
726a989a RB |
1731 | tree rhs1 = gimple_assign_rhs1 (user); |
1732 | tree rhs2 = get_unary_op (negate, NEGATE_EXPR); | |
1733 | gimple_stmt_iterator gsi = gsi_for_stmt (user); | |
1734 | gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2); | |
0e0ed594 JL |
1735 | update_stmt (user); |
1736 | } | |
1737 | } | |
1738 | } | |
1739 | } | |
1740 | ||
1741 | /* Break up subtract operations in block BB. | |
1742 | ||
1743 | We do this top down because we don't know whether the subtract is | |
1744 | part of a possible chain of reassociation except at the top. | |
1745 | ||
1746 | IE given | |
1747 | d = f + g | |
1748 | c = a + e | |
1749 | b = c - d | |
1750 | q = b - r | |
1751 | k = t - q | |
1752 | ||
1753 | we want to break up k = t - q, but we won't until we've transformed q | |
726a989a RB |
1754 | = b - r, which won't be broken up until we transform b = c - d. |
1755 | ||
1756 | En passant, clear the GIMPLE visited flag on every statement. */ | |
0e0ed594 JL |
1757 | |
1758 | static void | |
1759 | break_up_subtract_bb (basic_block bb) | |
1760 | { | |
726a989a | 1761 | gimple_stmt_iterator gsi; |
0e0ed594 JL |
1762 | basic_block son; |
1763 | ||
726a989a | 1764 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
0e0ed594 | 1765 | { |
726a989a RB |
1766 | gimple stmt = gsi_stmt (gsi); |
1767 | gimple_set_visited (stmt, false); | |
0e0ed594 | 1768 | |
726a989a RB |
1769 | /* Look for simple gimple subtract operations. */ |
1770 | if (is_gimple_assign (stmt) | |
1771 | && gimple_assign_rhs_code (stmt) == MINUS_EXPR) | |
0e0ed594 | 1772 | { |
726a989a RB |
1773 | tree lhs = gimple_assign_lhs (stmt); |
1774 | tree rhs1 = gimple_assign_rhs1 (stmt); | |
1775 | tree rhs2 = gimple_assign_rhs2 (stmt); | |
0e0ed594 | 1776 | |
a1a82611 | 1777 | /* If associative-math we can do reassociation for |
325217ed CF |
1778 | non-integral types. Or, we can do reassociation for |
1779 | non-saturating fixed-point types. */ | |
0e0ed594 | 1780 | if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) |
726a989a RB |
1781 | || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) |
1782 | || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2))) | |
1783 | && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs)) | |
1784 | || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1)) | |
1785 | || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2)) | |
a1a82611 | 1786 | || !flag_associative_math) |
726a989a RB |
1787 | && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs)) |
1788 | || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1)) | |
1789 | || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2)))) | |
0e0ed594 JL |
1790 | continue; |
1791 | ||
1792 | /* Check for a subtract used only in an addition. If this | |
1793 | is the case, transform it into add of a negate for better | |
1794 | reassociation. IE transform C = A-B into C = A + -B if C | |
1795 | is only used in an addition. */ | |
726a989a RB |
1796 | if (should_break_up_subtract (stmt)) |
1797 | break_up_subtract (stmt, &gsi); | |
0e0ed594 JL |
1798 | } |
1799 | } | |
1800 | for (son = first_dom_son (CDI_DOMINATORS, bb); | |
1801 | son; | |
1802 | son = next_dom_son (CDI_DOMINATORS, son)) | |
1803 | break_up_subtract_bb (son); | |
1804 | } | |
1805 | ||
1806 | /* Reassociate expressions in basic block BB and its post-dominator as | |
1807 | children. */ | |
1808 | ||
1809 | static void | |
1810 | reassociate_bb (basic_block bb) | |
1811 | { | |
726a989a | 1812 | gimple_stmt_iterator gsi; |
0e0ed594 JL |
1813 | basic_block son; |
1814 | ||
726a989a | 1815 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) |
0e0ed594 | 1816 | { |
726a989a | 1817 | gimple stmt = gsi_stmt (gsi); |
0e0ed594 | 1818 | |
726a989a | 1819 | if (is_gimple_assign (stmt)) |
0e0ed594 | 1820 | { |
726a989a RB |
1821 | tree lhs, rhs1, rhs2; |
1822 | enum tree_code rhs_code = gimple_assign_rhs_code (stmt); | |
0e0ed594 | 1823 | |
726a989a RB |
1824 | /* If this is not a gimple binary expression, there is |
1825 | nothing for us to do with it. */ | |
1826 | if (get_gimple_rhs_class (rhs_code) != GIMPLE_BINARY_RHS) | |
0e0ed594 JL |
1827 | continue; |
1828 | ||
726a989a RB |
1829 | /* If this was part of an already processed statement, |
1830 | we don't need to touch it again. */ | |
1831 | if (gimple_visited_p (stmt)) | |
25c6036a RG |
1832 | { |
1833 | /* This statement might have become dead because of previous | |
1834 | reassociations. */ | |
1835 | if (has_zero_uses (gimple_get_lhs (stmt))) | |
1836 | { | |
1837 | gsi_remove (&gsi, true); | |
1838 | release_defs (stmt); | |
e4658728 RG |
1839 | /* We might end up removing the last stmt above which |
1840 | places the iterator to the end of the sequence. | |
1841 | Reset it to the last stmt in this case which might | |
1842 | be the end of the sequence as well if we removed | |
1843 | the last statement of the sequence. In which case | |
1844 | we need to bail out. */ | |
1845 | if (gsi_end_p (gsi)) | |
1846 | { | |
1847 | gsi = gsi_last_bb (bb); | |
1848 | if (gsi_end_p (gsi)) | |
1849 | break; | |
1850 | } | |
25c6036a RG |
1851 | } |
1852 | continue; | |
1853 | } | |
726a989a RB |
1854 | |
1855 | lhs = gimple_assign_lhs (stmt); | |
1856 | rhs1 = gimple_assign_rhs1 (stmt); | |
1857 | rhs2 = gimple_assign_rhs2 (stmt); | |
1858 | ||
a1a82611 | 1859 | /* If associative-math we can do reassociation for |
325217ed CF |
1860 | non-integral types. Or, we can do reassociation for |
1861 | non-saturating fixed-point types. */ | |
0e0ed594 | 1862 | if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) |
726a989a RB |
1863 | || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) |
1864 | || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2))) | |
1865 | && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs)) | |
1866 | || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1)) | |
1867 | || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2)) | |
a1a82611 | 1868 | || !flag_associative_math) |
726a989a RB |
1869 | && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs)) |
1870 | || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1)) | |
1871 | || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2)))) | |
0e0ed594 JL |
1872 | continue; |
1873 | ||
726a989a | 1874 | if (associative_tree_code (rhs_code)) |
0e0ed594 JL |
1875 | { |
1876 | VEC(operand_entry_t, heap) *ops = NULL; | |
1877 | ||
1878 | /* There may be no immediate uses left by the time we | |
1879 | get here because we may have eliminated them all. */ | |
bfc646bf | 1880 | if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs)) |
0e0ed594 JL |
1881 | continue; |
1882 | ||
726a989a | 1883 | gimple_set_visited (stmt, true); |
25c6036a | 1884 | linearize_expr_tree (&ops, stmt, true, true); |
0e0ed594 JL |
1885 | qsort (VEC_address (operand_entry_t, ops), |
1886 | VEC_length (operand_entry_t, ops), | |
1887 | sizeof (operand_entry_t), | |
1888 | sort_by_operand_rank); | |
726a989a | 1889 | optimize_ops_list (rhs_code, &ops); |
25c6036a RG |
1890 | if (undistribute_ops_list (rhs_code, &ops, |
1891 | loop_containing_stmt (stmt))) | |
1892 | { | |
1893 | qsort (VEC_address (operand_entry_t, ops), | |
1894 | VEC_length (operand_entry_t, ops), | |
1895 | sizeof (operand_entry_t), | |
1896 | sort_by_operand_rank); | |
1897 | optimize_ops_list (rhs_code, &ops); | |
1898 | } | |
0e0ed594 JL |
1899 | |
1900 | if (VEC_length (operand_entry_t, ops) == 1) | |
1901 | { | |
1902 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1903 | { | |
1904 | fprintf (dump_file, "Transforming "); | |
726a989a | 1905 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 | 1906 | } |
ec81df7d JJ |
1907 | |
1908 | rhs1 = gimple_assign_rhs1 (stmt); | |
726a989a RB |
1909 | gimple_assign_set_rhs_from_tree (&gsi, |
1910 | VEC_last (operand_entry_t, | |
1911 | ops)->op); | |
0e0ed594 | 1912 | update_stmt (stmt); |
ec81df7d | 1913 | remove_visited_stmt_chain (rhs1); |
0e0ed594 JL |
1914 | |
1915 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1916 | { | |
1917 | fprintf (dump_file, " into "); | |
726a989a | 1918 | print_gimple_stmt (dump_file, stmt, 0, 0); |
0e0ed594 JL |
1919 | } |
1920 | } | |
1921 | else | |
ec81df7d | 1922 | rewrite_expr_tree (stmt, 0, ops, false); |
0e0ed594 JL |
1923 | |
1924 | VEC_free (operand_entry_t, heap, ops); | |
1925 | } | |
1926 | } | |
1927 | } | |
1928 | for (son = first_dom_son (CDI_POST_DOMINATORS, bb); | |
1929 | son; | |
1930 | son = next_dom_son (CDI_POST_DOMINATORS, son)) | |
1931 | reassociate_bb (son); | |
1932 | } | |
1933 | ||
1934 | void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops); | |
1935 | void debug_ops_vector (VEC (operand_entry_t, heap) *ops); | |
1936 | ||
1937 | /* Dump the operand entry vector OPS to FILE. */ | |
1938 | ||
1939 | void | |
1940 | dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops) | |
1941 | { | |
1942 | operand_entry_t oe; | |
1943 | unsigned int i; | |
1944 | ||
1945 | for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++) | |
1946 | { | |
1947 | fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank); | |
726a989a | 1948 | print_generic_expr (file, oe->op, 0); |
0e0ed594 JL |
1949 | } |
1950 | } | |
1951 | ||
1952 | /* Dump the operand entry vector OPS to STDERR. */ | |
1953 | ||
1954 | void | |
1955 | debug_ops_vector (VEC (operand_entry_t, heap) *ops) | |
1956 | { | |
1957 | dump_ops_vector (stderr, ops); | |
1958 | } | |
1959 | ||
1960 | static void | |
1961 | do_reassoc (void) | |
1962 | { | |
1963 | break_up_subtract_bb (ENTRY_BLOCK_PTR); | |
1964 | reassociate_bb (EXIT_BLOCK_PTR); | |
1965 | } | |
1966 | ||
1967 | /* Initialize the reassociation pass. */ | |
1968 | ||
1969 | static void | |
1970 | init_reassoc (void) | |
1971 | { | |
1972 | int i; | |
15814ba0 | 1973 | long rank = 2; |
0e0ed594 | 1974 | tree param; |
5ed6ace5 | 1975 | int *bbs = XNEWVEC (int, last_basic_block + 1); |
0e0ed594 | 1976 | |
7a9c7d01 ZD |
1977 | /* Find the loops, so that we can prevent moving calculations in |
1978 | them. */ | |
1979 | loop_optimizer_init (AVOID_CFG_MODIFICATIONS); | |
1980 | ||
0e0ed594 JL |
1981 | memset (&reassociate_stats, 0, sizeof (reassociate_stats)); |
1982 | ||
1983 | operand_entry_pool = create_alloc_pool ("operand entry pool", | |
1984 | sizeof (struct operand_entry), 30); | |
1985 | ||
1986 | /* Reverse RPO (Reverse Post Order) will give us something where | |
1987 | deeper loops come later. */ | |
f91a0beb | 1988 | pre_and_rev_post_order_compute (NULL, bbs, false); |
15814ba0 PB |
1989 | bb_rank = XCNEWVEC (long, last_basic_block + 1); |
1990 | operand_rank = pointer_map_create (); | |
0e0ed594 JL |
1991 | |
1992 | /* Give each argument a distinct rank. */ | |
1993 | for (param = DECL_ARGUMENTS (current_function_decl); | |
1994 | param; | |
1995 | param = TREE_CHAIN (param)) | |
1996 | { | |
5cd4ec7f | 1997 | if (gimple_default_def (cfun, param) != NULL) |
0e0ed594 | 1998 | { |
5cd4ec7f | 1999 | tree def = gimple_default_def (cfun, param); |
0e0ed594 JL |
2000 | insert_operand_rank (def, ++rank); |
2001 | } | |
2002 | } | |
2003 | ||
2004 | /* Give the chain decl a distinct rank. */ | |
2005 | if (cfun->static_chain_decl != NULL) | |
2006 | { | |
5cd4ec7f | 2007 | tree def = gimple_default_def (cfun, cfun->static_chain_decl); |
0e0ed594 JL |
2008 | if (def != NULL) |
2009 | insert_operand_rank (def, ++rank); | |
2010 | } | |
2011 | ||
2012 | /* Set up rank for each BB */ | |
24bd1a0b | 2013 | for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++) |
0e0ed594 JL |
2014 | bb_rank[bbs[i]] = ++rank << 16; |
2015 | ||
2016 | free (bbs); | |
0e0ed594 JL |
2017 | calculate_dominance_info (CDI_POST_DOMINATORS); |
2018 | broken_up_subtracts = NULL; | |
2019 | } | |
2020 | ||
2021 | /* Cleanup after the reassociation pass, and print stats if | |
2022 | requested. */ | |
2023 | ||
2024 | static void | |
2025 | fini_reassoc (void) | |
2026 | { | |
01902653 RG |
2027 | statistics_counter_event (cfun, "Linearized", |
2028 | reassociate_stats.linearized); | |
2029 | statistics_counter_event (cfun, "Constants eliminated", | |
2030 | reassociate_stats.constants_eliminated); | |
2031 | statistics_counter_event (cfun, "Ops eliminated", | |
2032 | reassociate_stats.ops_eliminated); | |
2033 | statistics_counter_event (cfun, "Statements rewritten", | |
2034 | reassociate_stats.rewritten); | |
0e0ed594 | 2035 | |
15814ba0 | 2036 | pointer_map_destroy (operand_rank); |
0e0ed594 JL |
2037 | free_alloc_pool (operand_entry_pool); |
2038 | free (bb_rank); | |
2039 | VEC_free (tree, heap, broken_up_subtracts); | |
2040 | free_dominance_info (CDI_POST_DOMINATORS); | |
7a9c7d01 | 2041 | loop_optimizer_finalize (); |
0e0ed594 JL |
2042 | } |
2043 | ||
2044 | /* Gate and execute functions for Reassociation. */ | |
2045 | ||
c2924966 | 2046 | static unsigned int |
0e0ed594 JL |
2047 | execute_reassoc (void) |
2048 | { | |
012309e6 | 2049 | init_reassoc (); |
0e0ed594 | 2050 | |
012309e6 | 2051 | do_reassoc (); |
0e0ed594 JL |
2052 | repropagate_negates (); |
2053 | ||
012309e6 | 2054 | fini_reassoc (); |
c2924966 | 2055 | return 0; |
012309e6 DB |
2056 | } |
2057 | ||
13c59415 UB |
2058 | static bool |
2059 | gate_tree_ssa_reassoc (void) | |
2060 | { | |
2061 | return flag_tree_reassoc != 0; | |
2062 | } | |
2063 | ||
8ddbbcae | 2064 | struct gimple_opt_pass pass_reassoc = |
012309e6 | 2065 | { |
8ddbbcae JH |
2066 | { |
2067 | GIMPLE_PASS, | |
012309e6 | 2068 | "reassoc", /* name */ |
13c59415 UB |
2069 | gate_tree_ssa_reassoc, /* gate */ |
2070 | execute_reassoc, /* execute */ | |
012309e6 DB |
2071 | NULL, /* sub */ |
2072 | NULL, /* next */ | |
2073 | 0, /* static_pass_number */ | |
13c59415 | 2074 | TV_TREE_REASSOC, /* tv_id */ |
4effdf02 | 2075 | PROP_cfg | PROP_ssa, /* properties_required */ |
012309e6 DB |
2076 | 0, /* properties_provided */ |
2077 | 0, /* properties_destroyed */ | |
2078 | 0, /* todo_flags_start */ | |
8ddbbcae JH |
2079 | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ |
2080 | } | |
012309e6 | 2081 | }; |
726a989a | 2082 |