1/* Reassociation for trees.
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "target.h"
26#include "rtl.h"
27#include "tree.h"
28#include "gimple.h"
29#include "cfghooks.h"
30#include "alloc-pool.h"
31#include "tree-pass.h"
32#include "memmodel.h"
33#include "tm_p.h"
34#include "ssa.h"
35#include "optabs-tree.h"
36#include "gimple-pretty-print.h"
37#include "diagnostic-core.h"
38#include "fold-const.h"
39#include "stor-layout.h"
40#include "cfganal.h"
41#include "gimple-fold.h"
42#include "tree-eh.h"
43#include "gimple-iterator.h"
44#include "gimplify-me.h"
45#include "tree-cfg.h"
46#include "tree-ssa-loop.h"
47#include "flags.h"
48#include "tree-ssa.h"
49#include "langhooks.h"
50#include "cfgloop.h"
51#include "params.h"
52#include "builtins.h"
53#include "gimplify.h"
54#include "case-cfn-macros.h"
55
56/* This is a simple global reassociation pass. It is, in part, based
57 on the LLVM pass of the same name (They do some things more/less
58 than we do, in different orders, etc).
59
60 It consists of five steps:
61
62 1. Breaking up subtract operations into addition + negate, where
63 it would promote the reassociation of adds.
64
65 2. Left linearization of the expression trees, so that (A+B)+(C+D)
66 becomes (((A+B)+C)+D), which is easier for us to rewrite later.
67 During linearization, we place the operands of the binary
68 expressions into a vector of operand_entry_*
69
70 3. Optimization of the operand lists, eliminating things like a +
71 -a, a & a, etc.
72
73 3a. Combine repeated factors with the same occurrence counts
74 into a __builtin_powi call that will later be optimized into
75 an optimal number of multiplies.
76
77 4. Rewrite the expression trees we linearized and optimized so
78 they are in proper rank order.
79
80 5. Repropagate negates, as nothing else will clean it up ATM.
81
82 A bit of theory on #4, since nobody seems to write anything down
83 about why it makes sense to do it the way they do it:
84
85 We could do this much nicer theoretically, but don't (for reasons
86 explained after how to do it theoretically nice :P).
87
88 In order to promote the most redundancy elimination, you want
89 binary expressions whose operands are the same rank (or
90 preferably, the same value) exposed to the redundancy eliminator,
91 for possible elimination.
92
93 So the way to do this if we really cared, is to build the new op
94 tree from the leaves to the roots, merging as you go, and putting the
95 new op on the end of the worklist, until you are left with one
96 thing on the worklist.
97
98 IE if you have to rewrite the following set of operands (listed with
99 rank in parentheses), with opcode PLUS_EXPR:
100
101 a (1), b (1), c (1), d (2), e (2)
102
103
104 We start with our merge worklist empty, and the ops list with all of
105 those on it.
106
107 You want to first merge all leaves of the same rank, as much as
108 possible.
109
110 So first build a binary op of
111
112 mergetmp = a + b, and put "mergetmp" on the merge worklist.
113
114 Because there is no three operand form of PLUS_EXPR, c is not going to
115 be exposed to redundancy elimination as a rank 1 operand.
116
117 So you might as well throw it on the merge worklist (you could also
118 consider it to now be a rank two operand, and merge it with d and e,
119 but in this case, you then have evicted e from a binary op. So at
120 least in this situation, you can't win.)
121
122 Then build a binary op of d + e
123 mergetmp2 = d + e
124
125 and put mergetmp2 on the merge worklist.
126
127 so merge worklist = {mergetmp, c, mergetmp2}
128
129 Continue building binary ops of these operations until you have only
130 one operation left on the worklist.
131
132 So we have
133
134 build binary op
135 mergetmp3 = mergetmp + c
136
137 worklist = {mergetmp2, mergetmp3}
138
139 mergetmp4 = mergetmp2 + mergetmp3
140
141 worklist = {mergetmp4}
142
143 because we have one operation left, we can now just set the original
144 statement equal to the result of that operation.
145
146 This will at least expose a + b and d + e to redundancy elimination
147 as binary operations.
148
149 For extra points, you can reuse the old statements to build the
150 mergetmps, since you shouldn't run out.
151
152 So why don't we do this?
153
154 Because it's expensive, and rarely will help. Most trees we are
155 reassociating have 3 or less ops. If they have 2 ops, they already
156 will be written into a nice single binary op. If you have 3 ops, a
157 single simple check suffices to tell you whether the first two are of the
158 same rank. If so, you know to order it
159
160 mergetmp = op1 + op2
161 newstmt = mergetmp + op3
162
163 instead of
164 mergetmp = op2 + op3
165 newstmt = mergetmp + op1
166
167 If all three are of the same rank, you can't expose them all in a
168 single binary operator anyway, so the above is *still* the best you
169 can do.
170
171 Thus, this is what we do. When we have three ops left, we check to see
172 what order to put them in, and call it a day. As a nod to vector sum
173 reduction, we check if any of the ops are really a phi node that is a
174 destructive update for the associating op, and keep the destructive
175 update together for vector sum reduction recognition. */
176
177/* Enable insertion of __builtin_powi calls during execute_reassoc. See
178 point 3a in the pass header comment. */
179static bool reassoc_insert_powi_p;
180
181/* Statistics */
182static struct
183{
184 int linearized;
185 int constants_eliminated;
186 int ops_eliminated;
187 int rewritten;
188 int pows_encountered;
189 int pows_created;
190} reassociate_stats;
191
192/* Operator, rank pair. */
193struct operand_entry
194{
195 unsigned int rank;
196 unsigned int id;
197 tree op;
198 unsigned int count;
199 gimple *stmt_to_insert;
200};
201
202static object_allocator<operand_entry> operand_entry_pool
203 ("operand entry pool");
204
205/* This is used to assign a unique ID to each struct operand_entry
206 so that qsort results are identical on different hosts. */
207static unsigned int next_operand_entry_id;
208
209/* Starting rank number for a given basic block, so that we can rank
210 operations using unmovable instructions in that BB based on the bb
211 depth. */
212static long *bb_rank;
213
214/* Operand->rank hashtable. */
215static hash_map<tree, long> *operand_rank;
216
217/* Vector of SSA_NAMEs on which after reassociate_bb is done with
218 all basic blocks the CFG should be adjusted - basic blocks
219 split right after that SSA_NAME's definition statement and before
220 the only use, which must be a bit ior. */
221static vec<tree> reassoc_branch_fixups;
222
223/* Forward decls. */
224static long get_rank (tree);
225static bool reassoc_stmt_dominates_stmt_p (gimple *, gimple *);
226
227/* Wrapper around gsi_remove, which adjusts gimple_uid of debug stmts
228 possibly added by gsi_remove. */
229
230bool
231reassoc_remove_stmt (gimple_stmt_iterator *gsi)
232{
233 gimple *stmt = gsi_stmt (*gsi);
234
235 if (!MAY_HAVE_DEBUG_BIND_STMTS || gimple_code (stmt) == GIMPLE_PHI)
236 return gsi_remove (gsi, true);
237
238 gimple_stmt_iterator prev = *gsi;
239 gsi_prev (&prev);
240 unsigned uid = gimple_uid (stmt);
241 basic_block bb = gimple_bb (stmt);
242 bool ret = gsi_remove (gsi, true);
243 if (!gsi_end_p (prev))
244 gsi_next (&prev);
245 else
246 prev = gsi_start_bb (bb);
247 gimple *end_stmt = gsi_stmt (*gsi);
248 while ((stmt = gsi_stmt (prev)) != end_stmt)
249 {
250 gcc_assert (stmt && is_gimple_debug (stmt) && gimple_uid (stmt) == 0);
251 gimple_set_uid (stmt, uid);
252 gsi_next (&prev);
253 }
254 return ret;
255}
256
257/* Bias amount for loop-carried phis. We want this to be larger than
258 the depth of any reassociation tree we can see, but not larger than
259 the rank difference between two blocks. */
260#define PHI_LOOP_BIAS (1 << 15)
261
262/* Rank assigned to a phi statement. If STMT is a loop-carried phi of
263 an innermost loop, and the phi has only a single use which is inside
264 the loop, then the rank is the block rank of the loop latch plus an
265 extra bias for the loop-carried dependence. This causes expressions
266 calculated into an accumulator variable to be independent for each
267 iteration of the loop. If STMT is some other phi, the rank is the
268 block rank of its containing block. */
269static long
270phi_rank (gimple *stmt)
271{
272 basic_block bb = gimple_bb (stmt);
273 struct loop *father = bb->loop_father;
274 tree res;
275 unsigned i;
276 use_operand_p use;
277 gimple *use_stmt;
278
279 /* We only care about real loops (those with a latch). */
280 if (!father->latch)
281 return bb_rank[bb->index];
282
283 /* Interesting phis must be in headers of innermost loops. */
284 if (bb != father->header
285 || father->inner)
286 return bb_rank[bb->index];
287
288 /* Ignore virtual SSA_NAMEs. */
289 res = gimple_phi_result (stmt);
290 if (virtual_operand_p (res))
291 return bb_rank[bb->index];
292
293 /* The phi definition must have a single use, and that use must be
294 within the loop. Otherwise this isn't an accumulator pattern. */
295 if (!single_imm_use (res, &use, &use_stmt)
296 || gimple_bb (use_stmt)->loop_father != father)
297 return bb_rank[bb->index];
298
299 /* Look for phi arguments from within the loop. If found, bias this phi. */
300 for (i = 0; i < gimple_phi_num_args (stmt); i++)
301 {
302 tree arg = gimple_phi_arg_def (stmt, i);
303 if (TREE_CODE (arg) == SSA_NAME
304 && !SSA_NAME_IS_DEFAULT_DEF (arg))
305 {
306 gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
307 if (gimple_bb (def_stmt)->loop_father == father)
308 return bb_rank[father->latch->index] + PHI_LOOP_BIAS;
309 }
310 }
311
312 /* Must be an uninteresting phi. */
313 return bb_rank[bb->index];
314}
315
316/* If EXP is an SSA_NAME defined by a PHI statement that represents a
317 loop-carried dependence of an innermost loop, return TRUE; else
318 return FALSE. */
319static bool
320loop_carried_phi (tree exp)
321{
322 gimple *phi_stmt;
323 long block_rank;
324
325 if (TREE_CODE (exp) != SSA_NAME
326 || SSA_NAME_IS_DEFAULT_DEF (exp))
327 return false;
328
329 phi_stmt = SSA_NAME_DEF_STMT (exp);
330
331 if (gimple_code (SSA_NAME_DEF_STMT (exp)) != GIMPLE_PHI)
332 return false;
333
334 /* Non-loop-carried phis have block rank. Loop-carried phis have
335 an additional bias added in. If this phi doesn't have block rank,
336 it's biased and should not be propagated. */
337 block_rank = bb_rank[gimple_bb (phi_stmt)->index];
338
339 if (phi_rank (phi_stmt) != block_rank)
340 return true;
341
342 return false;
343}
344
345/* Return the maximum of RANK and the rank that should be propagated
346 from expression OP. For most operands, this is just the rank of OP.
347 For loop-carried phis, the value is zero to avoid undoing the bias
348 in favor of the phi. */
349static long
350propagate_rank (long rank, tree op)
351{
352 long op_rank;
353
354 if (loop_carried_phi (op))
355 return rank;
356
357 op_rank = get_rank (op);
358
359 return MAX (rank, op_rank);
360}
361
362/* Look up the operand rank structure for expression E. */
363
364static inline long
365find_operand_rank (tree e)
366{
367 long *slot = operand_rank->get (e);
368 return slot ? *slot : -1;
369}
370
371/* Insert {E,RANK} into the operand rank hashtable. */
372
373static inline void
374insert_operand_rank (tree e, long rank)
375{
376 gcc_assert (rank > 0);
377 gcc_assert (!operand_rank->put (e, rank));
378}
379
380/* Given an expression E, return the rank of the expression. */
381
382static long
383get_rank (tree e)
384{
385 /* SSA_NAME's have the rank of the expression they are the result
386 of.
387 For globals and uninitialized values, the rank is 0.
388 For function arguments, use the pre-setup rank.
389 For PHI nodes, stores, asm statements, etc, we use the rank of
390 the BB.
391 For simple operations, the rank is the maximum rank of any of
392 its operands, or the bb_rank, whichever is less.
393 I make no claims that this is optimal, however, it gives good
394 results. */
395
396 /* We make an exception to the normal ranking system to break
397 dependences of accumulator variables in loops. Suppose we
398 have a simple one-block loop containing:
399
400 x_1 = phi(x_0, x_2)
401 b = a + x_1
402 c = b + d
403 x_2 = c + e
404
405 As shown, each iteration of the calculation into x is fully
406 dependent upon the iteration before it. We would prefer to
407 see this in the form:
408
409 x_1 = phi(x_0, x_2)
410 b = a + d
411 c = b + e
412 x_2 = c + x_1
413
414 If the loop is unrolled, the calculations of b and c from
415 different iterations can be interleaved.
416
417 To obtain this result during reassociation, we bias the rank
418 of the phi definition x_1 upward, when it is recognized as an
419 accumulator pattern. The artificial rank causes it to be
420 added last, providing the desired independence. */
421
422 if (TREE_CODE (e) == SSA_NAME)
423 {
424 ssa_op_iter iter;
425 gimple *stmt;
426 long rank;
427 tree op;
428
429 if (SSA_NAME_IS_DEFAULT_DEF (e))
430 return find_operand_rank (e);
431
432 stmt = SSA_NAME_DEF_STMT (e);
433 if (gimple_code (stmt) == GIMPLE_PHI)
434 return phi_rank (stmt);
435
436 if (!is_gimple_assign (stmt))
437 return bb_rank[gimple_bb (stmt)->index];
438
439 /* If we already have a rank for this expression, use that. */
440 rank = find_operand_rank (e);
441 if (rank != -1)
442 return rank;
443
444 /* Otherwise, find the maximum rank for the operands. As an
445 exception, remove the bias from loop-carried phis when propagating
446 the rank so that dependent operations are not also biased. */
447 /* Simply walk over all SSA uses - this takes advatage of the
448 fact that non-SSA operands are is_gimple_min_invariant and
449 thus have rank 0. */
450 rank = 0;
451 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
452 rank = propagate_rank (rank, op);
453
454 if (dump_file && (dump_flags & TDF_DETAILS))
455 {
456 fprintf (dump_file, "Rank for ");
457 print_generic_expr (dump_file, e);
458 fprintf (dump_file, " is %ld\n", (rank + 1));
459 }
460
461 /* Note the rank in the hashtable so we don't recompute it. */
462 insert_operand_rank (e, (rank + 1));
463 return (rank + 1);
464 }
465
466 /* Constants, globals, etc., are rank 0 */
467 return 0;
468}
469
470
471/* We want integer ones to end up last no matter what, since they are
472 the ones we can do the most with. */
473#define INTEGER_CONST_TYPE 1 << 3
474#define FLOAT_CONST_TYPE 1 << 2
475#define OTHER_CONST_TYPE 1 << 1
476
477/* Classify an invariant tree into integer, float, or other, so that
478 we can sort them to be near other constants of the same type. */
479static inline int
480constant_type (tree t)
481{
482 if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
483 return INTEGER_CONST_TYPE;
484 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
485 return FLOAT_CONST_TYPE;
486 else
487 return OTHER_CONST_TYPE;
488}
489
490/* qsort comparison function to sort operand entries PA and PB by rank
491 so that the sorted array is ordered by rank in decreasing order. */
492static int
493sort_by_operand_rank (const void *pa, const void *pb)
494{
495 const operand_entry *oea = *(const operand_entry *const *)pa;
496 const operand_entry *oeb = *(const operand_entry *const *)pb;
497
498 if (oeb->rank != oea->rank)
499 return oeb->rank > oea->rank ? 1 : -1;
500
501 /* It's nicer for optimize_expression if constants that are likely
502 to fold when added/multiplied/whatever are put next to each
503 other. Since all constants have rank 0, order them by type. */
504 if (oea->rank == 0)
505 {
506 if (constant_type (oeb->op) != constant_type (oea->op))
507 return constant_type (oeb->op) - constant_type (oea->op);
508 else
509 /* To make sorting result stable, we use unique IDs to determine
510 order. */
511 return oeb->id > oea->id ? 1 : -1;
512 }
513
514 if (TREE_CODE (oea->op) != SSA_NAME)
515 {
516 if (TREE_CODE (oeb->op) != SSA_NAME)
517 return oeb->id > oea->id ? 1 : -1;
518 else
519 return 1;
520 }
521 else if (TREE_CODE (oeb->op) != SSA_NAME)
522 return -1;
523
524 /* Lastly, make sure the versions that are the same go next to each
525 other. */
526 if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
527 {
528 /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
529 versions of removed SSA_NAMEs, so if possible, prefer to sort
530 based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
531 See PR60418. */
532 gimple *stmta = SSA_NAME_DEF_STMT (oea->op);
533 gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op);
534 basic_block bba = gimple_bb (stmta);
535 basic_block bbb = gimple_bb (stmtb);
536 if (bbb != bba)
537 {
538 /* One of the SSA_NAMEs can be defined in oeN->stmt_to_insert
539 but the other might not. */
540 if (!bba)
541 return 1;
542 if (!bbb)
543 return -1;
544 /* If neither is, compare bb_rank. */
545 if (bb_rank[bbb->index] != bb_rank[bba->index])
546 return (bb_rank[bbb->index] >> 16) - (bb_rank[bba->index] >> 16);
547 }
548
549 bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
550 bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta);
551 if (da != db)
552 return da ? 1 : -1;
553
554 return SSA_NAME_VERSION (oeb->op) > SSA_NAME_VERSION (oea->op) ? 1 : -1;
555 }
556
557 return oeb->id > oea->id ? 1 : -1;
558}
559
560/* Add an operand entry to *OPS for the tree operand OP. */
561
562static void
563add_to_ops_vec (vec<operand_entry *> *ops, tree op, gimple *stmt_to_insert = NULL)
564{
565 operand_entry *oe = operand_entry_pool.allocate ();
566
567 oe->op = op;
568 oe->rank = get_rank (op);
569 oe->id = next_operand_entry_id++;
570 oe->count = 1;
571 oe->stmt_to_insert = stmt_to_insert;
572 ops->safe_push (oe);
573}
574
575/* Add an operand entry to *OPS for the tree operand OP with repeat
576 count REPEAT. */
577
578static void
579add_repeat_to_ops_vec (vec<operand_entry *> *ops, tree op,
580 HOST_WIDE_INT repeat)
581{
582 operand_entry *oe = operand_entry_pool.allocate ();
583
584 oe->op = op;
585 oe->rank = get_rank (op);
586 oe->id = next_operand_entry_id++;
587 oe->count = repeat;
588 oe->stmt_to_insert = NULL;
589 ops->safe_push (oe);
590
591 reassociate_stats.pows_encountered++;
592}
593
594/* Return true if STMT is reassociable operation containing a binary
595 operation with tree code CODE, and is inside LOOP. */
596
597static bool
598is_reassociable_op (gimple *stmt, enum tree_code code, struct loop *loop)
599{
600 basic_block bb = gimple_bb (stmt);
601
602 if (gimple_bb (stmt) == NULL)
603 return false;
604
605 if (!flow_bb_inside_loop_p (loop, bb))
606 return false;
607
608 if (is_gimple_assign (stmt)
609 && gimple_assign_rhs_code (stmt) == code
610 && has_single_use (gimple_assign_lhs (stmt)))
611 {
612 tree rhs1 = gimple_assign_rhs1 (stmt);
613 tree rhs2 = gimple_assign_rhs1 (stmt);
614 if (TREE_CODE (rhs1) == SSA_NAME
615 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
616 return false;
617 if (rhs2
618 && TREE_CODE (rhs2) == SSA_NAME
619 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs2))
620 return false;
621 return true;
622 }
623
624 return false;
625}
626
627
628/* Return true if STMT is a nop-conversion. */
629
630static bool
631gimple_nop_conversion_p (gimple *stmt)
632{
633 if (gassign *ass = dyn_cast <gassign *> (stmt))
634 {
635 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (ass))
636 && tree_nop_conversion_p (TREE_TYPE (gimple_assign_lhs (ass)),
637 TREE_TYPE (gimple_assign_rhs1 (ass))))
638 return true;
639 }
640 return false;
641}
642
643/* Given NAME, if NAME is defined by a unary operation OPCODE, return the
644 operand of the negate operation. Otherwise, return NULL. */
645
646static tree
647get_unary_op (tree name, enum tree_code opcode)
648{
649 gimple *stmt = SSA_NAME_DEF_STMT (name);
650
651 /* Look through nop conversions (sign changes). */
652 if (gimple_nop_conversion_p (stmt)
653 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
654 stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
655
656 if (!is_gimple_assign (stmt))
657 return NULL_TREE;
658
659 if (gimple_assign_rhs_code (stmt) == opcode)
660 return gimple_assign_rhs1 (stmt);
661 return NULL_TREE;
662}
663
664/* Return true if OP1 and OP2 have the same value if casted to either type. */
665
666static bool
667ops_equal_values_p (tree op1, tree op2)
668{
669 if (op1 == op2)
670 return true;
671
672 tree orig_op1 = op1;
673 if (TREE_CODE (op1) == SSA_NAME)
674 {
675 gimple *stmt = SSA_NAME_DEF_STMT (op1);
676 if (gimple_nop_conversion_p (stmt))
677 {
678 op1 = gimple_assign_rhs1 (stmt);
679 if (op1 == op2)
680 return true;
681 }
682 }
683
684 if (TREE_CODE (op2) == SSA_NAME)
685 {
686 gimple *stmt = SSA_NAME_DEF_STMT (op2);
687 if (gimple_nop_conversion_p (stmt))
688 {
689 op2 = gimple_assign_rhs1 (stmt);
690 if (op1 == op2
691 || orig_op1 == op2)
692 return true;
693 }
694 }
695
696 return false;
697}
698
699
700/* If CURR and LAST are a pair of ops that OPCODE allows us to
701 eliminate through equivalences, do so, remove them from OPS, and
702 return true. Otherwise, return false. */
703
704static bool
705eliminate_duplicate_pair (enum tree_code opcode,
706 vec<operand_entry *> *ops,
707 bool *all_done,
708 unsigned int i,
709 operand_entry *curr,
710 operand_entry *last)
711{
712
713 /* If we have two of the same op, and the opcode is & |, min, or max,
714 we can eliminate one of them.
715 If we have two of the same op, and the opcode is ^, we can
716 eliminate both of them. */
717
718 if (last && last->op == curr->op)
719 {
720 switch (opcode)
721 {
722 case MAX_EXPR:
723 case MIN_EXPR:
724 case BIT_IOR_EXPR:
725 case BIT_AND_EXPR:
726 if (dump_file && (dump_flags & TDF_DETAILS))
727 {
728 fprintf (dump_file, "Equivalence: ");
729 print_generic_expr (dump_file, curr->op);
730 fprintf (dump_file, " [&|minmax] ");
731 print_generic_expr (dump_file, last->op);
732 fprintf (dump_file, " -> ");
733 print_generic_stmt (dump_file, last->op);
734 }
735
736 ops->ordered_remove (i);
737 reassociate_stats.ops_eliminated ++;
738
739 return true;
740
741 case BIT_XOR_EXPR:
742 if (dump_file && (dump_flags & TDF_DETAILS))
743 {
744 fprintf (dump_file, "Equivalence: ");
745 print_generic_expr (dump_file, curr->op);
746 fprintf (dump_file, " ^ ");
747 print_generic_expr (dump_file, last->op);
748 fprintf (dump_file, " -> nothing\n");
749 }
750
751 reassociate_stats.ops_eliminated += 2;
752
753 if (ops->length () == 2)
754 {
755 ops->truncate (0);
756 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (last->op)));
757 *all_done = true;
758 }
759 else
760 {
761 ops->ordered_remove (i-1);
762 ops->ordered_remove (i-1);
763 }
764
765 return true;
766
767 default:
768 break;
769 }
770 }
771 return false;
772}
773
774static vec<tree> plus_negates;
775
776/* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not
777 expression, look in OPS for a corresponding positive operation to cancel
778 it out. If we find one, remove the other from OPS, replace
779 OPS[CURRINDEX] with 0 or -1, respectively, and return true. Otherwise,
780 return false. */
781
782static bool
783eliminate_plus_minus_pair (enum tree_code opcode,
784 vec<operand_entry *> *ops,
785 unsigned int currindex,
786 operand_entry *curr)
787{
788 tree negateop;
789 tree notop;
790 unsigned int i;
791 operand_entry *oe;
792
793 if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
794 return false;
795
796 negateop = get_unary_op (curr->op, NEGATE_EXPR);
797 notop = get_unary_op (curr->op, BIT_NOT_EXPR);
798 if (negateop == NULL_TREE && notop == NULL_TREE)
799 return false;
800
801 /* Any non-negated version will have a rank that is one less than
802 the current rank. So once we hit those ranks, if we don't find
803 one, we can stop. */
804
805 for (i = currindex + 1;
806 ops->iterate (i, &oe)
807 && oe->rank >= curr->rank - 1 ;
808 i++)
809 {
810 if (negateop
811 && ops_equal_values_p (oe->op, negateop))
812 {
813 if (dump_file && (dump_flags & TDF_DETAILS))
814 {
815 fprintf (dump_file, "Equivalence: ");
816 print_generic_expr (dump_file, negateop);
817 fprintf (dump_file, " + -");
818 print_generic_expr (dump_file, oe->op);
819 fprintf (dump_file, " -> 0\n");
820 }
821
822 ops->ordered_remove (i);
823 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (oe->op)));
824 ops->ordered_remove (currindex);
825 reassociate_stats.ops_eliminated ++;
826
827 return true;
828 }
829 else if (notop
830 && ops_equal_values_p (oe->op, notop))
831 {
832 tree op_type = TREE_TYPE (oe->op);
833
834 if (dump_file && (dump_flags & TDF_DETAILS))
835 {
836 fprintf (dump_file, "Equivalence: ");
837 print_generic_expr (dump_file, notop);
838 fprintf (dump_file, " + ~");
839 print_generic_expr (dump_file, oe->op);
840 fprintf (dump_file, " -> -1\n");
841 }
842
843 ops->ordered_remove (i);
844 add_to_ops_vec (ops, build_all_ones_cst (op_type));
845 ops->ordered_remove (currindex);
846 reassociate_stats.ops_eliminated ++;
847
848 return true;
849 }
850 }
851
852 /* If CURR->OP is a negate expr without nop conversion in a plus expr:
853 save it for later inspection in repropagate_negates(). */
854 if (negateop != NULL_TREE
855 && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (curr->op)) == NEGATE_EXPR)
856 plus_negates.safe_push (curr->op);
857
858 return false;
859}
860
861/* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
862 bitwise not expression, look in OPS for a corresponding operand to
863 cancel it out. If we find one, remove the other from OPS, replace
864 OPS[CURRINDEX] with 0, and return true. Otherwise, return
865 false. */
866
867static bool
868eliminate_not_pairs (enum tree_code opcode,
869 vec<operand_entry *> *ops,
870 unsigned int currindex,
871 operand_entry *curr)
872{
873 tree notop;
874 unsigned int i;
875 operand_entry *oe;
876
877 if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
878 || TREE_CODE (curr->op) != SSA_NAME)
879 return false;
880
881 notop = get_unary_op (curr->op, BIT_NOT_EXPR);
882 if (notop == NULL_TREE)
883 return false;
884
885 /* Any non-not version will have a rank that is one less than
886 the current rank. So once we hit those ranks, if we don't find
887 one, we can stop. */
888
889 for (i = currindex + 1;
890 ops->iterate (i, &oe)
891 && oe->rank >= curr->rank - 1;
892 i++)
893 {
894 if (oe->op == notop)
895 {
896 if (dump_file && (dump_flags & TDF_DETAILS))
897 {
898 fprintf (dump_file, "Equivalence: ");
899 print_generic_expr (dump_file, notop);
900 if (opcode == BIT_AND_EXPR)
901 fprintf (dump_file, " & ~");
902 else if (opcode == BIT_IOR_EXPR)
903 fprintf (dump_file, " | ~");
904 print_generic_expr (dump_file, oe->op);
905 if (opcode == BIT_AND_EXPR)
906 fprintf (dump_file, " -> 0\n");
907 else if (opcode == BIT_IOR_EXPR)
908 fprintf (dump_file, " -> -1\n");
909 }
910
911 if (opcode == BIT_AND_EXPR)
912 oe->op = build_zero_cst (TREE_TYPE (oe->op));
913 else if (opcode == BIT_IOR_EXPR)
914 oe->op = build_all_ones_cst (TREE_TYPE (oe->op));
915
916 reassociate_stats.ops_eliminated += ops->length () - 1;
917 ops->truncate (0);
918 ops->quick_push (oe);
919 return true;
920 }
921 }
922
923 return false;
924}
925
926/* Use constant value that may be present in OPS to try to eliminate
927 operands. Note that this function is only really used when we've
928 eliminated ops for other reasons, or merged constants. Across
929 single statements, fold already does all of this, plus more. There
930 is little point in duplicating logic, so I've only included the
931 identities that I could ever construct testcases to trigger. */
932
933static void
934eliminate_using_constants (enum tree_code opcode,
935 vec<operand_entry *> *ops)
936{
937 operand_entry *oelast = ops->last ();
938 tree type = TREE_TYPE (oelast->op);
939
940 if (oelast->rank == 0
941 && (ANY_INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type)))
942 {
943 switch (opcode)
944 {
945 case BIT_AND_EXPR:
946 if (integer_zerop (oelast->op))
947 {
948 if (ops->length () != 1)
949 {
950 if (dump_file && (dump_flags & TDF_DETAILS))
951 fprintf (dump_file, "Found & 0, removing all other ops\n");
952
953 reassociate_stats.ops_eliminated += ops->length () - 1;
954
955 ops->truncate (0);
956 ops->quick_push (oelast);
957 return;
958 }
959 }
960 else if (integer_all_onesp (oelast->op))
961 {
962 if (ops->length () != 1)
963 {
964 if (dump_file && (dump_flags & TDF_DETAILS))
965 fprintf (dump_file, "Found & -1, removing\n");
966 ops->pop ();
967 reassociate_stats.ops_eliminated++;
968 }
969 }
970 break;
971 case BIT_IOR_EXPR:
972 if (integer_all_onesp (oelast->op))
973 {
974 if (ops->length () != 1)
975 {
976 if (dump_file && (dump_flags & TDF_DETAILS))
977 fprintf (dump_file, "Found | -1, removing all other ops\n");
978
979 reassociate_stats.ops_eliminated += ops->length () - 1;
980
981 ops->truncate (0);
982 ops->quick_push (oelast);
983 return;
984 }
985 }
986 else if (integer_zerop (oelast->op))
987 {
988 if (ops->length () != 1)
989 {
990 if (dump_file && (dump_flags & TDF_DETAILS))
991 fprintf (dump_file, "Found | 0, removing\n");
992 ops->pop ();
993 reassociate_stats.ops_eliminated++;
994 }
995 }
996 break;
997 case MULT_EXPR:
998 if (integer_zerop (oelast->op)
999 || (FLOAT_TYPE_P (type)
1000 && !HONOR_NANS (type)
1001 && !HONOR_SIGNED_ZEROS (type)
1002 && real_zerop (oelast->op)))
1003 {
1004 if (ops->length () != 1)
1005 {
1006 if (dump_file && (dump_flags & TDF_DETAILS))
1007 fprintf (dump_file, "Found * 0, removing all other ops\n");
1008
1009 reassociate_stats.ops_eliminated += ops->length () - 1;
1010 ops->truncate (1);
1011 ops->quick_push (oelast);
1012 return;
1013 }
1014 }
1015 else if (integer_onep (oelast->op)
1016 || (FLOAT_TYPE_P (type)
1017 && !HONOR_SNANS (type)
1018 && real_onep (oelast->op)))
1019 {
1020 if (ops->length () != 1)
1021 {
1022 if (dump_file && (dump_flags & TDF_DETAILS))
1023 fprintf (dump_file, "Found * 1, removing\n");
1024 ops->pop ();
1025 reassociate_stats.ops_eliminated++;
1026 return;
1027 }
1028 }
1029 break;
1030 case BIT_XOR_EXPR:
1031 case PLUS_EXPR:
1032 case MINUS_EXPR:
1033 if (integer_zerop (oelast->op)
1034 || (FLOAT_TYPE_P (type)
1035 && (opcode == PLUS_EXPR || opcode == MINUS_EXPR)
1036 && fold_real_zero_addition_p (type, oelast->op,
1037 opcode == MINUS_EXPR)))
1038 {
1039 if (ops->length () != 1)
1040 {
1041 if (dump_file && (dump_flags & TDF_DETAILS))
1042 fprintf (dump_file, "Found [|^+] 0, removing\n");
1043 ops->pop ();
1044 reassociate_stats.ops_eliminated++;
1045 return;
1046 }
1047 }
1048 break;
1049 default:
1050 break;
1051 }
1052 }
1053}
1054
1055
1056static void linearize_expr_tree (vec<operand_entry *> *, gimple *,
1057 bool, bool);
1058
1059/* Structure for tracking and counting operands. */
1060struct oecount {
1061 unsigned int cnt;
1062 unsigned int id;
1063 enum tree_code oecode;
1064 tree op;
1065};
1066
1067
1068/* The heap for the oecount hashtable and the sorted list of operands. */
1069static vec<oecount> cvec;
1070
1071
1072/* Oecount hashtable helpers. */
1073
1074struct oecount_hasher : int_hash <int, 0, 1>
1075{
1076 static inline hashval_t hash (int);
1077 static inline bool equal (int, int);
1078};
1079
1080/* Hash function for oecount. */
1081
1082inline hashval_t
1083oecount_hasher::hash (int p)
1084{
1085 const oecount *c = &cvec[p - 42];
1086 return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
1087}
1088
1089/* Comparison function for oecount. */
1090
1091inline bool
1092oecount_hasher::equal (int p1, int p2)
1093{
1094 const oecount *c1 = &cvec[p1 - 42];
1095 const oecount *c2 = &cvec[p2 - 42];
1096 return c1->oecode == c2->oecode && c1->op == c2->op;
1097}
1098
1099/* Comparison function for qsort sorting oecount elements by count. */
1100
1101static int
1102oecount_cmp (const void *p1, const void *p2)
1103{
1104 const oecount *c1 = (const oecount *)p1;
1105 const oecount *c2 = (const oecount *)p2;
1106 if (c1->cnt != c2->cnt)
1107 return c1->cnt > c2->cnt ? 1 : -1;
1108 else
1109 /* If counts are identical, use unique IDs to stabilize qsort. */
1110 return c1->id > c2->id ? 1 : -1;
1111}
1112
1113/* Return TRUE iff STMT represents a builtin call that raises OP
1114 to some exponent. */
1115
1116static bool
1117stmt_is_power_of_op (gimple *stmt, tree op)
1118{
1119 if (!is_gimple_call (stmt))
1120 return false;
1121
1122 switch (gimple_call_combined_fn (stmt))
1123 {
1124 CASE_CFN_POW:
1125 CASE_CFN_POWI:
1126 return (operand_equal_p (gimple_call_arg (stmt, 0), op, 0));
1127
1128 default:
1129 return false;
1130 }
1131}
1132
1133/* Given STMT which is a __builtin_pow* call, decrement its exponent
1134 in place and return the result. Assumes that stmt_is_power_of_op
1135 was previously called for STMT and returned TRUE. */
1136
1137static HOST_WIDE_INT
1138decrement_power (gimple *stmt)
1139{
1140 REAL_VALUE_TYPE c, cint;
1141 HOST_WIDE_INT power;
1142 tree arg1;
1143
1144 switch (gimple_call_combined_fn (stmt))
1145 {
1146 CASE_CFN_POW:
1147 arg1 = gimple_call_arg (stmt, 1);
1148 c = TREE_REAL_CST (arg1);
1149 power = real_to_integer (&c) - 1;
1150 real_from_integer (&cint, VOIDmode, power, SIGNED);
1151 gimple_call_set_arg (stmt, 1, build_real (TREE_TYPE (arg1), cint));
1152 return power;
1153
1154 CASE_CFN_POWI:
1155 arg1 = gimple_call_arg (stmt, 1);
1156 power = TREE_INT_CST_LOW (arg1) - 1;
1157 gimple_call_set_arg (stmt, 1, build_int_cst (TREE_TYPE (arg1), power));
1158 return power;
1159
1160 default:
1161 gcc_unreachable ();
1162 }
1163}
1164
1165/* Replace SSA defined by STMT and replace all its uses with new
1166 SSA. Also return the new SSA. */
1167
1168static tree
1169make_new_ssa_for_def (gimple *stmt, enum tree_code opcode, tree op)
1170{
1171 gimple *use_stmt;
1172 use_operand_p use;
1173 imm_use_iterator iter;
1174 tree new_lhs, new_debug_lhs = NULL_TREE;
1175 tree lhs = gimple_get_lhs (stmt);
1176
1177 new_lhs = make_ssa_name (TREE_TYPE (lhs));
1178 gimple_set_lhs (stmt, new_lhs);
1179
1180 /* Also need to update GIMPLE_DEBUGs. */
1181 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
1182 {
1183 tree repl = new_lhs;
1184 if (is_gimple_debug (use_stmt))
1185 {
1186 if (new_debug_lhs == NULL_TREE)
1187 {
1188 new_debug_lhs = make_node (DEBUG_EXPR_DECL);
1189 gdebug *def_temp
1190 = gimple_build_debug_bind (new_debug_lhs,
1191 build2 (opcode, TREE_TYPE (lhs),
1192 new_lhs, op),
1193 stmt);
1194 DECL_ARTIFICIAL (new_debug_lhs) = 1;
1195 TREE_TYPE (new_debug_lhs) = TREE_TYPE (lhs);
1196 SET_DECL_MODE (new_debug_lhs, TYPE_MODE (TREE_TYPE (lhs)));
1197 gimple_set_uid (def_temp, gimple_uid (stmt));
1198 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1199 gsi_insert_after (&gsi, def_temp, GSI_SAME_STMT);
1200 }
1201 repl = new_debug_lhs;
1202 }
1203 FOR_EACH_IMM_USE_ON_STMT (use, iter)
1204 SET_USE (use, repl);
1205 update_stmt (use_stmt);
1206 }
1207 return new_lhs;
1208}
1209
1210/* Replace all SSAs defined in STMTS_TO_FIX and replace its
1211 uses with new SSAs. Also do this for the stmt that defines DEF
1212 if *DEF is not OP. */
1213
1214static void
1215make_new_ssa_for_all_defs (tree *def, enum tree_code opcode, tree op,
1216 vec<gimple *> &stmts_to_fix)
1217{
1218 unsigned i;
1219 gimple *stmt;
1220
1221 if (*def != op
1222 && TREE_CODE (*def) == SSA_NAME
1223 && (stmt = SSA_NAME_DEF_STMT (*def))
1224 && gimple_code (stmt) != GIMPLE_NOP)
1225 *def = make_new_ssa_for_def (stmt, opcode, op);
1226
1227 FOR_EACH_VEC_ELT (stmts_to_fix, i, stmt)
1228 make_new_ssa_for_def (stmt, opcode, op);
1229}
1230
1231/* Find the single immediate use of STMT's LHS, and replace it
1232 with OP. Remove STMT. If STMT's LHS is the same as *DEF,
1233 replace *DEF with OP as well. */
1234
1235static void
1236propagate_op_to_single_use (tree op, gimple *stmt, tree *def)
1237{
1238 tree lhs;
1239 gimple *use_stmt;
1240 use_operand_p use;
1241 gimple_stmt_iterator gsi;
1242
1243 if (is_gimple_call (stmt))
1244 lhs = gimple_call_lhs (stmt);
1245 else
1246 lhs = gimple_assign_lhs (stmt);
1247
1248 gcc_assert (has_single_use (lhs));
1249 single_imm_use (lhs, &use, &use_stmt);
1250 if (lhs == *def)
1251 *def = op;
1252 SET_USE (use, op);
1253 if (TREE_CODE (op) != SSA_NAME)
1254 update_stmt (use_stmt);
1255 gsi = gsi_for_stmt (stmt);
1256 unlink_stmt_vdef (stmt);
1257 reassoc_remove_stmt (&gsi);
1258 release_defs (stmt);
1259}
1260
1261/* Walks the linear chain with result *DEF searching for an operation
1262 with operand OP and code OPCODE removing that from the chain. *DEF
1263 is updated if there is only one operand but no operation left. */
1264
1265static void
1266zero_one_operation (tree *def, enum tree_code opcode, tree op)
1267{
1268 tree orig_def = *def;
1269 gimple *stmt = SSA_NAME_DEF_STMT (*def);
1270 /* PR72835 - Record the stmt chain that has to be updated such that
1271 we dont use the same LHS when the values computed are different. */
1272 auto_vec<gimple *, 64> stmts_to_fix;
1273
1274 do
1275 {
1276 tree name;
1277
1278 if (opcode == MULT_EXPR)
1279 {
1280 if (stmt_is_power_of_op (stmt, op))
1281 {
1282 if (decrement_power (stmt) == 1)
1283 {
1284 if (stmts_to_fix.length () > 0)
1285 stmts_to_fix.pop ();
1286 propagate_op_to_single_use (op, stmt, def);
1287 }
1288 break;
1289 }
1290 else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR)
1291 {
1292 if (gimple_assign_rhs1 (stmt) == op)
1293 {
1294 tree cst = build_minus_one_cst (TREE_TYPE (op));
1295 if (stmts_to_fix.length () > 0)
1296 stmts_to_fix.pop ();
1297 propagate_op_to_single_use (cst, stmt, def);
1298 break;
1299 }
1300 else if (integer_minus_onep (op)
1301 || real_minus_onep (op))
1302 {
1303 gimple_assign_set_rhs_code
1304 (stmt, TREE_CODE (gimple_assign_rhs1 (stmt)));
1305 break;
1306 }
1307 }
1308 }
1309
1310 name = gimple_assign_rhs1 (stmt);
1311
1312 /* If this is the operation we look for and one of the operands
1313 is ours simply propagate the other operand into the stmts
1314 single use. */
1315 if (gimple_assign_rhs_code (stmt) == opcode
1316 && (name == op
1317 || gimple_assign_rhs2 (stmt) == op))
1318 {
1319 if (name == op)
1320 name = gimple_assign_rhs2 (stmt);
1321 if (stmts_to_fix.length () > 0)
1322 stmts_to_fix.pop ();
1323 propagate_op_to_single_use (name, stmt, def);
1324 break;
1325 }
1326
1327 /* We might have a multiply of two __builtin_pow* calls, and
1328 the operand might be hiding in the rightmost one. Likewise
1329 this can happen for a negate. */
1330 if (opcode == MULT_EXPR
1331 && gimple_assign_rhs_code (stmt) == opcode
1332 && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1333 && has_single_use (gimple_assign_rhs2 (stmt)))
1334 {
1335 gimple *stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
1336 if (stmt_is_power_of_op (stmt2, op))
1337 {
1338 if (decrement_power (stmt2) == 1)
1339 propagate_op_to_single_use (op, stmt2, def);
1340 else
1341 stmts_to_fix.safe_push (stmt2);
1342 break;
1343 }
1344 else if (is_gimple_assign (stmt2)
1345 && gimple_assign_rhs_code (stmt2) == NEGATE_EXPR)
1346 {
1347 if (gimple_assign_rhs1 (stmt2) == op)
1348 {
1349 tree cst = build_minus_one_cst (TREE_TYPE (op));
1350 propagate_op_to_single_use (cst, stmt2, def);
1351 break;
1352 }
1353 else if (integer_minus_onep (op)
1354 || real_minus_onep (op))
1355 {
1356 stmts_to_fix.safe_push (stmt2);
1357 gimple_assign_set_rhs_code
1358 (stmt2, TREE_CODE (gimple_assign_rhs1 (stmt2)));
1359 break;
1360 }
1361 }
1362 }
1363
1364 /* Continue walking the chain. */
1365 gcc_assert (name != op
1366 && TREE_CODE (name) == SSA_NAME);
1367 stmt = SSA_NAME_DEF_STMT (name);
1368 stmts_to_fix.safe_push (stmt);
1369 }
1370 while (1);
1371
1372 if (stmts_to_fix.length () > 0 || *def == orig_def)
1373 make_new_ssa_for_all_defs (def, opcode, op, stmts_to_fix);
1374}
1375
1376/* Returns true if statement S1 dominates statement S2. Like
1377 stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
1378
1379static bool
1380reassoc_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
1381{
1382 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1383
1384 /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
1385 SSA_NAME. Assume it lives at the beginning of function and
1386 thus dominates everything. */
1387 if (!bb1 || s1 == s2)
1388 return true;
1389
1390 /* If bb2 is NULL, it doesn't dominate any stmt with a bb. */
1391 if (!bb2)
1392 return false;
1393
1394 if (bb1 == bb2)
1395 {
1396 /* PHIs in the same basic block are assumed to be
1397 executed all in parallel, if only one stmt is a PHI,
1398 it dominates the other stmt in the same basic block. */
1399 if (gimple_code (s1) == GIMPLE_PHI)
1400 return true;
1401
1402 if (gimple_code (s2) == GIMPLE_PHI)
1403 return false;
1404
1405 gcc_assert (gimple_uid (s1) && gimple_uid (s2));
1406
1407 if (gimple_uid (s1) < gimple_uid (s2))
1408 return true;
1409
1410 if (gimple_uid (s1) > gimple_uid (s2))
1411 return false;
1412
1413 gimple_stmt_iterator gsi = gsi_for_stmt (s1);
1414 unsigned int uid = gimple_uid (s1);
1415 for (gsi_next (&gsi); !gsi_end_p (gsi); gsi_next (&gsi))
1416 {
1417 gimple *s = gsi_stmt (gsi);
1418 if (gimple_uid (s) != uid)
1419 break;
1420 if (s == s2)
1421 return true;
1422 }
1423
1424 return false;
1425 }
1426
1427 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1428}
1429
1430/* Insert STMT after INSERT_POINT. */
1431
1432static void
1433insert_stmt_after (gimple *stmt, gimple *insert_point)
1434{
1435 gimple_stmt_iterator gsi;
1436 basic_block bb;
1437
1438 if (gimple_code (insert_point) == GIMPLE_PHI)
1439 bb = gimple_bb (insert_point);
1440 else if (!stmt_ends_bb_p (insert_point))
1441 {
1442 gsi = gsi_for_stmt (insert_point);
1443 gimple_set_uid (stmt, gimple_uid (insert_point));
1444 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1445 return;
1446 }
1447 else
1448 /* We assume INSERT_POINT is a SSA_NAME_DEF_STMT of some SSA_NAME,
1449 thus if it must end a basic block, it should be a call that can
1450 throw, or some assignment that can throw. If it throws, the LHS
1451 of it will not be initialized though, so only valid places using
1452 the SSA_NAME should be dominated by the fallthru edge. */
1453 bb = find_fallthru_edge (gimple_bb (insert_point)->succs)->dest;
1454 gsi = gsi_after_labels (bb);
1455 if (gsi_end_p (gsi))
1456 {
1457 gimple_stmt_iterator gsi2 = gsi_last_bb (bb);
1458 gimple_set_uid (stmt,
1459 gsi_end_p (gsi2) ? 1 : gimple_uid (gsi_stmt (gsi2)));
1460 }
1461 else
1462 gimple_set_uid (stmt, gimple_uid (gsi_stmt (gsi)));
1463 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1464}
1465
1466/* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
1467 the result. Places the statement after the definition of either
1468 OP1 or OP2. Returns the new statement. */
1469
1470static gimple *
1471build_and_add_sum (tree type, tree op1, tree op2, enum tree_code opcode)
1472{
1473 gimple *op1def = NULL, *op2def = NULL;
1474 gimple_stmt_iterator gsi;
1475 tree op;
1476 gassign *sum;
1477
1478 /* Create the addition statement. */
1479 op = make_ssa_name (type);
1480 sum = gimple_build_assign (op, opcode, op1, op2);
1481
1482 /* Find an insertion place and insert. */
1483 if (TREE_CODE (op1) == SSA_NAME)
1484 op1def = SSA_NAME_DEF_STMT (op1);
1485 if (TREE_CODE (op2) == SSA_NAME)
1486 op2def = SSA_NAME_DEF_STMT (op2);
1487 if ((!op1def || gimple_nop_p (op1def))
1488 && (!op2def || gimple_nop_p (op2def)))
1489 {
1490 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1491 if (gsi_end_p (gsi))
1492 {
1493 gimple_stmt_iterator gsi2
1494 = gsi_last_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1495 gimple_set_uid (sum,
1496 gsi_end_p (gsi2) ? 1 : gimple_uid (gsi_stmt (gsi2)));
1497 }
1498 else
1499 gimple_set_uid (sum, gimple_uid (gsi_stmt (gsi)));
1500 gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
1501 }
1502 else
1503 {
1504 gimple *insert_point;
1505 if ((!op1def || gimple_nop_p (op1def))
1506 || (op2def && !gimple_nop_p (op2def)
1507 && reassoc_stmt_dominates_stmt_p (op1def, op2def)))
1508 insert_point = op2def;
1509 else
1510 insert_point = op1def;
1511 insert_stmt_after (sum, insert_point);
1512 }
1513 update_stmt (sum);
1514
1515 return sum;
1516}
1517
1518/* Perform un-distribution of divisions and multiplications.
1519 A * X + B * X is transformed into (A + B) * X and A / X + B / X
1520 to (A + B) / X for real X.
1521
1522 The algorithm is organized as follows.
1523
1524 - First we walk the addition chain *OPS looking for summands that
1525 are defined by a multiplication or a real division. This results
1526 in the candidates bitmap with relevant indices into *OPS.
1527
1528 - Second we build the chains of multiplications or divisions for
1529 these candidates, counting the number of occurrences of (operand, code)
1530 pairs in all of the candidates chains.
1531
1532 - Third we sort the (operand, code) pairs by number of occurrence and
1533 process them starting with the pair with the most uses.
1534
1535 * For each such pair we walk the candidates again to build a
1536 second candidate bitmap noting all multiplication/division chains
1537 that have at least one occurrence of (operand, code).
1538
1539 * We build an alternate addition chain only covering these
1540 candidates with one (operand, code) operation removed from their
1541 multiplication/division chain.
1542
1543 * The first candidate gets replaced by the alternate addition chain
1544 multiplied/divided by the operand.
1545
1546 * All candidate chains get disabled for further processing and
1547 processing of (operand, code) pairs continues.
1548
1549 The alternate addition chains built are re-processed by the main
1550 reassociation algorithm which allows optimizing a * x * y + b * y * x
1551 to (a + b ) * x * y in one invocation of the reassociation pass. */
1552
1553static bool
1554undistribute_ops_list (enum tree_code opcode,
1555 vec<operand_entry *> *ops, struct loop *loop)
1556{
1557 unsigned int length = ops->length ();
1558 operand_entry *oe1;
1559 unsigned i, j;
1560 unsigned nr_candidates, nr_candidates2;
1561 sbitmap_iterator sbi0;
1562 vec<operand_entry *> *subops;
1563 bool changed = false;
1564 unsigned int next_oecount_id = 0;
1565
1566 if (length <= 1
1567 || opcode != PLUS_EXPR)
1568 return false;
1569
1570 /* Build a list of candidates to process. */
1571 auto_sbitmap candidates (length);
1572 bitmap_clear (candidates);
1573 nr_candidates = 0;
1574 FOR_EACH_VEC_ELT (*ops, i, oe1)
1575 {
1576 enum tree_code dcode;
1577 gimple *oe1def;
1578
1579 if (TREE_CODE (oe1->op) != SSA_NAME)
1580 continue;
1581 oe1def = SSA_NAME_DEF_STMT (oe1->op);
1582 if (!is_gimple_assign (oe1def))
1583 continue;
1584 dcode = gimple_assign_rhs_code (oe1def);
1585 if ((dcode != MULT_EXPR
1586 && dcode != RDIV_EXPR)
1587 || !is_reassociable_op (oe1def, dcode, loop))
1588 continue;
1589
1590 bitmap_set_bit (candidates, i);
1591 nr_candidates++;
1592 }
1593
1594 if (nr_candidates < 2)
1595 return false;
1596
1597 if (dump_file && (dump_flags & TDF_DETAILS))
1598 {
1599 fprintf (dump_file, "searching for un-distribute opportunities ");
1600 print_generic_expr (dump_file,
1601 (*ops)[bitmap_first_set_bit (candidates)]->op, 0);
1602 fprintf (dump_file, " %d\n", nr_candidates);
1603 }
1604
1605 /* Build linearized sub-operand lists and the counting table. */
1606 cvec.create (0);
1607
1608 hash_table<oecount_hasher> ctable (15);
1609
1610 /* ??? Macro arguments cannot have multi-argument template types in
1611 them. This typedef is needed to workaround that limitation. */
1612 typedef vec<operand_entry *> vec_operand_entry_t_heap;
1613 subops = XCNEWVEC (vec_operand_entry_t_heap, ops->length ());
1614 EXECUTE_IF_SET_IN_BITMAP (candidates, 0, i, sbi0)
1615 {
1616 gimple *oedef;
1617 enum tree_code oecode;
1618 unsigned j;
1619
1620 oedef = SSA_NAME_DEF_STMT ((*ops)[i]->op);
1621 oecode = gimple_assign_rhs_code (oedef);
1622 linearize_expr_tree (&subops[i], oedef,
1623 associative_tree_code (oecode), false);
1624
1625 FOR_EACH_VEC_ELT (subops[i], j, oe1)
1626 {
1627 oecount c;
1628 int *slot;
1629 int idx;
1630 c.oecode = oecode;
1631 c.cnt = 1;
1632 c.id = next_oecount_id++;
1633 c.op = oe1->op;
1634 cvec.safe_push (c);
1635 idx = cvec.length () + 41;
1636 slot = ctable.find_slot (idx, INSERT);
1637 if (!*slot)
1638 {
1639 *slot = idx;
1640 }
1641 else
1642 {
1643 cvec.pop ();
1644 cvec[*slot - 42].cnt++;
1645 }
1646 }
1647 }
1648
1649 /* Sort the counting table. */
1650 cvec.qsort (oecount_cmp);
1651
1652 if (dump_file && (dump_flags & TDF_DETAILS))
1653 {
1654 oecount *c;
1655 fprintf (dump_file, "Candidates:\n");
1656 FOR_EACH_VEC_ELT (cvec, j, c)
1657 {
1658 fprintf (dump_file, " %u %s: ", c->cnt,
1659 c->oecode == MULT_EXPR
1660 ? "*" : c->oecode == RDIV_EXPR ? "/" : "?");
1661 print_generic_expr (dump_file, c->op);
1662 fprintf (dump_file, "\n");
1663 }
1664 }
1665
1666 /* Process the (operand, code) pairs in order of most occurrence. */
1667 auto_sbitmap candidates2 (length);
1668 while (!cvec.is_empty ())
1669 {
1670 oecount *c = &cvec.last ();
1671 if (c->cnt < 2)
1672 break;
1673
1674 /* Now collect the operands in the outer chain that contain
1675 the common operand in their inner chain. */
1676 bitmap_clear (candidates2);
1677 nr_candidates2 = 0;
1678 EXECUTE_IF_SET_IN_BITMAP (candidates, 0, i, sbi0)
1679 {
1680 gimple *oedef;
1681 enum tree_code oecode;
1682 unsigned j;
1683 tree op = (*ops)[i]->op;
1684
1685 /* If we undistributed in this chain already this may be
1686 a constant. */
1687 if (TREE_CODE (op) != SSA_NAME)
1688 continue;
1689
1690 oedef = SSA_NAME_DEF_STMT (op);
1691 oecode = gimple_assign_rhs_code (oedef);
1692 if (oecode != c->oecode)
1693 continue;
1694
1695 FOR_EACH_VEC_ELT (subops[i], j, oe1)
1696 {
1697 if (oe1->op == c->op)
1698 {
1699 bitmap_set_bit (candidates2, i);
1700 ++nr_candidates2;
1701 break;
1702 }
1703 }
1704 }
1705
1706 if (nr_candidates2 >= 2)
1707 {
1708 operand_entry *oe1, *oe2;
1709 gimple *prod;
1710 int first = bitmap_first_set_bit (candidates2);
1711
1712 /* Build the new addition chain. */
1713 oe1 = (*ops)[first];
1714 if (dump_file && (dump_flags & TDF_DETAILS))
1715 {
1716 fprintf (dump_file, "Building (");
1717 print_generic_expr (dump_file, oe1->op);
1718 }
1719 zero_one_operation (&oe1->op, c->oecode, c->op);
1720 EXECUTE_IF_SET_IN_BITMAP (candidates2, first+1, i, sbi0)
1721 {
1722 gimple *sum;
1723 oe2 = (*ops)[i];
1724 if (dump_file && (dump_flags & TDF_DETAILS))
1725 {
1726 fprintf (dump_file, " + ");
1727 print_generic_expr (dump_file, oe2->op);
1728 }
1729 zero_one_operation (&oe2->op, c->oecode, c->op);
1730 sum = build_and_add_sum (TREE_TYPE (oe1->op),
1731 oe1->op, oe2->op, opcode);
1732 oe2->op = build_zero_cst (TREE_TYPE (oe2->op));
1733 oe2->rank = 0;
1734 oe1->op = gimple_get_lhs (sum);
1735 }
1736
1737 /* Apply the multiplication/division. */
1738 prod = build_and_add_sum (TREE_TYPE (oe1->op),
1739 oe1->op, c->op, c->oecode);
1740 if (dump_file && (dump_flags & TDF_DETAILS))
1741 {
1742 fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/");
1743 print_generic_expr (dump_file, c->op);
1744 fprintf (dump_file, "\n");
1745 }
1746
1747 /* Record it in the addition chain and disable further
1748 undistribution with this op. */
1749 oe1->op = gimple_assign_lhs (prod);
1750 oe1->rank = get_rank (oe1->op);
1751 subops[first].release ();
1752
1753 changed = true;
1754 }
1755
1756 cvec.pop ();
1757 }
1758
1759 for (i = 0; i < ops->length (); ++i)
1760 subops[i].release ();
1761 free (subops);
1762 cvec.release ();
1763
1764 return changed;
1765}
1766
1767/* If OPCODE is BIT_IOR_EXPR or BIT_AND_EXPR and CURR is a comparison
1768 expression, examine the other OPS to see if any of them are comparisons
1769 of the same values, which we may be able to combine or eliminate.
1770 For example, we can rewrite (a < b) | (a == b) as (a <= b). */
1771
1772static bool
1773eliminate_redundant_comparison (enum tree_code opcode,
1774 vec<operand_entry *> *ops,
1775 unsigned int currindex,
1776 operand_entry *curr)
1777{
1778 tree op1, op2;
1779 enum tree_code lcode, rcode;
1780 gimple *def1, *def2;
1781 int i;
1782 operand_entry *oe;
1783
1784 if (opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
1785 return false;
1786
1787 /* Check that CURR is a comparison. */
1788 if (TREE_CODE (curr->op) != SSA_NAME)
1789 return false;
1790 def1 = SSA_NAME_DEF_STMT (curr->op);
1791 if (!is_gimple_assign (def1))
1792 return false;
1793 lcode = gimple_assign_rhs_code (def1);
1794 if (TREE_CODE_CLASS (lcode) != tcc_comparison)
1795 return false;
1796 op1 = gimple_assign_rhs1 (def1);
1797 op2 = gimple_assign_rhs2 (def1);
1798
1799 /* Now look for a similar comparison in the remaining OPS. */
1800 for (i = currindex + 1; ops->iterate (i, &oe); i++)
1801 {
1802 tree t;
1803
1804 if (TREE_CODE (oe->op) != SSA_NAME)
1805 continue;
1806 def2 = SSA_NAME_DEF_STMT (oe->op);
1807 if (!is_gimple_assign (def2))
1808 continue;
1809 rcode = gimple_assign_rhs_code (def2);
1810 if (TREE_CODE_CLASS (rcode) != tcc_comparison)
1811 continue;
1812
1813 /* If we got here, we have a match. See if we can combine the
1814 two comparisons. */
1815 if (opcode == BIT_IOR_EXPR)
1816 t = maybe_fold_or_comparisons (lcode, op1, op2,
1817 rcode, gimple_assign_rhs1 (def2),
1818 gimple_assign_rhs2 (def2));
1819 else
1820 t = maybe_fold_and_comparisons (lcode, op1, op2,
1821 rcode, gimple_assign_rhs1 (def2),
1822 gimple_assign_rhs2 (def2));
1823 if (!t)
1824 continue;
1825
1826 /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
1827 always give us a boolean_type_node value back. If the original
1828 BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
1829 we need to convert. */
1830 if (!useless_type_conversion_p (TREE_TYPE (curr->op), TREE_TYPE (t)))
1831 t = fold_convert (TREE_TYPE (curr->op), t);
1832
1833 if (TREE_CODE (t) != INTEGER_CST
1834 && !operand_equal_p (t, curr->op, 0))
1835 {
1836 enum tree_code subcode;
1837 tree newop1, newop2;
1838 if (!COMPARISON_CLASS_P (t))
1839 continue;
1840 extract_ops_from_tree (t, &subcode, &newop1, &newop2);
1841 STRIP_USELESS_TYPE_CONVERSION (newop1);
1842 STRIP_USELESS_TYPE_CONVERSION (newop2);
1843 if (!is_gimple_val (newop1) || !is_gimple_val (newop2))
1844 continue;
1845 }
1846
1847 if (dump_file && (dump_flags & TDF_DETAILS))
1848 {
1849 fprintf (dump_file, "Equivalence: ");
1850 print_generic_expr (dump_file, curr->op);
1851 fprintf (dump_file, " %s ", op_symbol_code (opcode));
1852 print_generic_expr (dump_file, oe->op);
1853 fprintf (dump_file, " -> ");
1854 print_generic_expr (dump_file, t);
1855 fprintf (dump_file, "\n");
1856 }
1857
1858 /* Now we can delete oe, as it has been subsumed by the new combined
1859 expression t. */
1860 ops->ordered_remove (i);
1861 reassociate_stats.ops_eliminated ++;
1862
1863 /* If t is the same as curr->op, we're done. Otherwise we must
1864 replace curr->op with t. Special case is if we got a constant
1865 back, in which case we add it to the end instead of in place of
1866 the current entry. */
1867 if (TREE_CODE (t) == INTEGER_CST)
1868 {
1869 ops->ordered_remove (currindex);
1870 add_to_ops_vec (ops, t);
1871 }
1872 else if (!operand_equal_p (t, curr->op, 0))
1873 {
1874 gimple *sum;
1875 enum tree_code subcode;
1876 tree newop1;
1877 tree newop2;
1878 gcc_assert (COMPARISON_CLASS_P (t));
1879 extract_ops_from_tree (t, &subcode, &newop1, &newop2);
1880 STRIP_USELESS_TYPE_CONVERSION (newop1);
1881 STRIP_USELESS_TYPE_CONVERSION (newop2);
1882 gcc_checking_assert (is_gimple_val (newop1)
1883 && is_gimple_val (newop2));
1884 sum = build_and_add_sum (TREE_TYPE (t), newop1, newop2, subcode);
1885 curr->op = gimple_get_lhs (sum);
1886 }
1887 return true;
1888 }
1889
1890 return false;
1891}
1892
1893
1894/* Transform repeated addition of same values into multiply with
1895 constant. */
1896static bool
1897transform_add_to_multiply (vec<operand_entry *> *ops)
1898{
1899 operand_entry *oe;
1900 tree op = NULL_TREE;
1901 int j;
1902 int i, start = -1, end = 0, count = 0;
1903 auto_vec<std::pair <int, int> > indxs;
1904 bool changed = false;
1905
1906 if (!INTEGRAL_TYPE_P (TREE_TYPE ((*ops)[0]->op))
1907 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE ((*ops)[0]->op))
1908 || !flag_unsafe_math_optimizations))
1909 return false;
1910
1911 /* Look for repeated operands. */
1912 FOR_EACH_VEC_ELT (*ops, i, oe)
1913 {
1914 if (start == -1)
1915 {
1916 count = 1;
1917 op = oe->op;
1918 start = i;
1919 }
1920 else if (operand_equal_p (oe->op, op, 0))
1921 {
1922 count++;
1923 end = i;
1924 }
1925 else
1926 {
1927 if (count > 1)
1928 indxs.safe_push (std::make_pair (start, end));
1929 count = 1;
1930 op = oe->op;
1931 start = i;
1932 }
1933 }
1934
1935 if (count > 1)
1936 indxs.safe_push (std::make_pair (start, end));
1937
1938 for (j = indxs.length () - 1; j >= 0; --j)
1939 {
1940 /* Convert repeated operand addition to multiplication. */
1941 start = indxs[j].first;
1942 end = indxs[j].second;
1943 op = (*ops)[start]->op;
1944 count = end - start + 1;
1945 for (i = end; i >= start; --i)
1946 ops->unordered_remove (i);
1947 tree tmp = make_ssa_name (TREE_TYPE (op));
1948 tree cst = build_int_cst (integer_type_node, count);
1949 gassign *mul_stmt
1950 = gimple_build_assign (tmp, MULT_EXPR,
1951 op, fold_convert (TREE_TYPE (op), cst));
1952 gimple_set_visited (mul_stmt, true);
1953 add_to_ops_vec (ops, tmp, mul_stmt);
1954 changed = true;
1955 }
1956
1957 return changed;
1958}
1959
1960
1961/* Perform various identities and other optimizations on the list of
1962 operand entries, stored in OPS. The tree code for the binary
1963 operation between all the operands is OPCODE. */
1964
1965static void
1966optimize_ops_list (enum tree_code opcode,
1967 vec<operand_entry *> *ops)
1968{
1969 unsigned int length = ops->length ();
1970 unsigned int i;
1971 operand_entry *oe;
1972 operand_entry *oelast = NULL;
1973 bool iterate = false;
1974
1975 if (length == 1)
1976 return;
1977
1978 oelast = ops->last ();
1979
1980 /* If the last two are constants, pop the constants off, merge them
1981 and try the next two. */
1982 if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
1983 {
1984 operand_entry *oelm1 = (*ops)[length - 2];
1985
1986 if (oelm1->rank == 0
1987 && is_gimple_min_invariant (oelm1->op)
1988 && useless_type_conversion_p (TREE_TYPE (oelm1->op),
1989 TREE_TYPE (oelast->op)))
1990 {
1991 tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
1992 oelm1->op, oelast->op);
1993
1994 if (folded && is_gimple_min_invariant (folded))
1995 {
1996 if (dump_file && (dump_flags & TDF_DETAILS))
1997 fprintf (dump_file, "Merging constants\n");
1998
1999 ops->pop ();
2000 ops->pop ();
2001
2002 add_to_ops_vec (ops, folded);
2003 reassociate_stats.constants_eliminated++;
2004
2005 optimize_ops_list (opcode, ops);
2006 return;
2007 }
2008 }
2009 }
2010
2011 eliminate_using_constants (opcode, ops);
2012 oelast = NULL;
2013
2014 for (i = 0; ops->iterate (i, &oe);)
2015 {
2016 bool done = false;
2017
2018 if (eliminate_not_pairs (opcode, ops, i, oe))
2019 return;
2020 if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
2021 || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe))
2022 || (!done && eliminate_redundant_comparison (opcode, ops, i, oe)))
2023 {
2024 if (done)
2025 return;
2026 iterate = true;
2027 oelast = NULL;
2028 continue;
2029 }
2030 oelast = oe;
2031 i++;
2032 }
2033
2034 length = ops->length ();
2035 oelast = ops->last ();
2036
2037 if (iterate)
2038 optimize_ops_list (opcode, ops);
2039}
2040
2041/* The following functions are subroutines to optimize_range_tests and allow
2042 it to try to change a logical combination of comparisons into a range
2043 test.
2044
2045 For example, both
2046 X == 2 || X == 5 || X == 3 || X == 4
2047 and
2048 X >= 2 && X <= 5
2049 are converted to
2050 (unsigned) (X - 2) <= 3
2051
2052 For more information see comments above fold_test_range in fold-const.c,
2053 this implementation is for GIMPLE. */
2054
2055struct range_entry
2056{
2057 tree exp;
2058 tree low;
2059 tree high;
2060 bool in_p;
2061 bool strict_overflow_p;
2062 unsigned int idx, next;
2063};
2064
2065/* This is similar to make_range in fold-const.c, but on top of
2066 GIMPLE instead of trees. If EXP is non-NULL, it should be
2067 an SSA_NAME and STMT argument is ignored, otherwise STMT
2068 argument should be a GIMPLE_COND. */
2069
2070static void
2071init_range_entry (struct range_entry *r, tree exp, gimple *stmt)
2072{
2073 int in_p;
2074 tree low, high;
2075 bool is_bool, strict_overflow_p;
2076
2077 r->exp = NULL_TREE;
2078 r->in_p = false;
2079 r->strict_overflow_p = false;
2080 r->low = NULL_TREE;
2081 r->high = NULL_TREE;
2082 if (exp != NULL_TREE
2083 && (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp))))
2084 return;
2085
2086 /* Start with simply saying "EXP != 0" and then look at the code of EXP
2087 and see if we can refine the range. Some of the cases below may not
2088 happen, but it doesn't seem worth worrying about this. We "continue"
2089 the outer loop when we've changed something; otherwise we "break"
2090 the switch, which will "break" the while. */
2091 low = exp ? build_int_cst (TREE_TYPE (exp), 0) : boolean_false_node;
2092 high = low;
2093 in_p = 0;
2094 strict_overflow_p = false;
2095 is_bool = false;
2096 if (exp == NULL_TREE)
2097 is_bool = true;
2098 else if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
2099 {
2100 if (TYPE_UNSIGNED (TREE_TYPE (exp)))
2101 is_bool = true;
2102 else
2103 return;
2104 }
2105 else if (TREE_CODE (TREE_TYPE (exp)) == BOOLEAN_TYPE)
2106 is_bool = true;
2107
2108 while (1)
2109 {
2110 enum tree_code code;
2111 tree arg0, arg1, exp_type;
2112 tree nexp;
2113 location_t loc;
2114
2115 if (exp != NULL_TREE)
2116 {
2117 if (TREE_CODE (exp) != SSA_NAME
2118 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
2119 break;
2120
2121 stmt = SSA_NAME_DEF_STMT (exp);
2122 if (!is_gimple_assign (stmt))
2123 break;
2124
2125 code = gimple_assign_rhs_code (stmt);
2126 arg0 = gimple_assign_rhs1 (stmt);
2127 arg1 = gimple_assign_rhs2 (stmt);
2128 exp_type = TREE_TYPE (exp);
2129 }
2130 else
2131 {
2132 code = gimple_cond_code (stmt);
2133 arg0 = gimple_cond_lhs (stmt);
2134 arg1 = gimple_cond_rhs (stmt);
2135 exp_type = boolean_type_node;
2136 }
2137
2138 if (TREE_CODE (arg0) != SSA_NAME)
2139 break;
2140 loc = gimple_location (stmt);
2141 switch (code)
2142 {
2143 case BIT_NOT_EXPR:
2144 if (TREE_CODE (TREE_TYPE (exp)) == BOOLEAN_TYPE
2145 /* Ensure the range is either +[-,0], +[0,0],
2146 -[-,0], -[0,0] or +[1,-], +[1,1], -[1,-] or
2147 -[1,1]. If it is e.g. +[-,-] or -[-,-]
2148 or similar expression of unconditional true or
2149 false, it should not be negated. */
2150 && ((high && integer_zerop (high))
2151 || (low && integer_onep (low))))
2152 {
2153 in_p = !in_p;
2154 exp = arg0;
2155 continue;
2156 }
2157 break;
2158 case SSA_NAME:
2159 exp = arg0;
2160 continue;
2161 CASE_CONVERT:
2162 if (is_bool)
2163 goto do_default;
2164 if (TYPE_PRECISION (TREE_TYPE (arg0)) == 1)
2165 {
2166 if (TYPE_UNSIGNED (TREE_TYPE (arg0)))
2167 is_bool = true;
2168 else
2169 return;
2170 }
2171 else if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE)
2172 is_bool = true;
2173 goto do_default;
2174 case EQ_EXPR:
2175 case NE_EXPR:
2176 case LT_EXPR:
2177 case LE_EXPR:
2178 case GE_EXPR:
2179 case GT_EXPR:
2180 is_bool = true;
2181 /* FALLTHRU */
2182 default:
2183 if (!is_bool)
2184 return;
2185 do_default:
2186 nexp = make_range_step (loc, code, arg0, arg1, exp_type,
2187 &low, &high, &in_p,
2188 &strict_overflow_p);
2189 if (nexp != NULL_TREE)
2190 {
2191 exp = nexp;
2192 gcc_assert (TREE_CODE (exp) == SSA_NAME);
2193 continue;
2194 }
2195 break;
2196 }
2197 break;
2198 }
2199 if (is_bool)
2200 {
2201 r->exp = exp;
2202 r->in_p = in_p;
2203 r->low = low;
2204 r->high = high;
2205 r->strict_overflow_p = strict_overflow_p;
2206 }
2207}
2208
2209/* Comparison function for qsort. Sort entries
2210 without SSA_NAME exp first, then with SSA_NAMEs sorted
2211 by increasing SSA_NAME_VERSION, and for the same SSA_NAMEs
2212 by increasing ->low and if ->low is the same, by increasing
2213 ->high. ->low == NULL_TREE means minimum, ->high == NULL_TREE
2214 maximum. */
2215
2216static int
2217range_entry_cmp (const void *a, const void *b)
2218{
2219 const struct range_entry *p = (const struct range_entry *) a;
2220 const struct range_entry *q = (const struct range_entry *) b;
2221
2222 if (p->exp != NULL_TREE && TREE_CODE (p->exp) == SSA_NAME)
2223 {
2224 if (q->exp != NULL_TREE && TREE_CODE (q->exp) == SSA_NAME)
2225 {
2226 /* Group range_entries for the same SSA_NAME together. */
2227 if (SSA_NAME_VERSION (p->exp) < SSA_NAME_VERSION (q->exp))
2228 return -1;
2229 else if (SSA_NAME_VERSION (p->exp) > SSA_NAME_VERSION (q->exp))
2230 return 1;
2231 /* If ->low is different, NULL low goes first, then by
2232 ascending low. */
2233 if (p->low != NULL_TREE)
2234 {
2235 if (q->low != NULL_TREE)
2236 {
2237 tree tem = fold_binary (LT_EXPR, boolean_type_node,
2238 p->low, q->low);
2239 if (tem && integer_onep (tem))
2240 return -1;
2241 tem = fold_binary (GT_EXPR, boolean_type_node,
2242 p->low, q->low);
2243 if (tem && integer_onep (tem))
2244 return 1;
2245 }
2246 else
2247 return 1;
2248 }
2249 else if (q->low != NULL_TREE)
2250 return -1;
2251 /* If ->high is different, NULL high goes last, before that by
2252 ascending high. */
2253 if (p->high != NULL_TREE)
2254 {
2255 if (q->high != NULL_TREE)
2256 {
2257 tree tem = fold_binary (LT_EXPR, boolean_type_node,
2258 p->high, q->high);
2259 if (tem && integer_onep (tem))
2260 return -1;
2261 tem = fold_binary (GT_EXPR, boolean_type_node,
2262 p->high, q->high);
2263 if (tem && integer_onep (tem))
2264 return 1;
2265 }
2266 else
2267 return -1;
2268 }
2269 else if (q->high != NULL_TREE)
2270 return 1;
2271 /* If both ranges are the same, sort below by ascending idx. */
2272 }
2273 else
2274 return 1;
2275 }
2276 else if (q->exp != NULL_TREE && TREE_CODE (q->exp) == SSA_NAME)
2277 return -1;
2278
2279 if (p->idx < q->idx)
2280 return -1;
2281 else
2282 {
2283 gcc_checking_assert (p->idx > q->idx);
2284 return 1;
2285 }
2286}
2287
2288/* Helper function for update_range_test. Force EXPR into an SSA_NAME,
2289 insert needed statements BEFORE or after GSI. */
2290
2291static tree
2292force_into_ssa_name (gimple_stmt_iterator *gsi, tree expr, bool before)
2293{
2294 enum gsi_iterator_update m = before ? GSI_SAME_STMT : GSI_CONTINUE_LINKING;
2295 tree ret = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE, before, m);
2296 if (TREE_CODE (ret) != SSA_NAME)
2297 {
2298 gimple *g = gimple_build_assign (make_ssa_name (TREE_TYPE (ret)), ret);
2299 if (before)
2300 gsi_insert_before (gsi, g, GSI_SAME_STMT);
2301 else
2302 gsi_insert_after (gsi, g, GSI_CONTINUE_LINKING);
2303 ret = gimple_assign_lhs (g);
2304 }
2305 return ret;
2306}
2307
2308/* Helper routine of optimize_range_test.
2309 [EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for
2310 RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges,
2311 OPCODE and OPS are arguments of optimize_range_tests. If OTHERRANGE
2312 is NULL, OTHERRANGEP should not be and then OTHERRANGEP points to
2313 an array of COUNT pointers to other ranges. Return
2314 true if the range merge has been successful.
2315 If OPCODE is ERROR_MARK, this is called from within
2316 maybe_optimize_range_tests and is performing inter-bb range optimization.
2317 In that case, whether an op is BIT_AND_EXPR or BIT_IOR_EXPR is found in
2318 oe->rank. */
2319
2320static bool
2321update_range_test (struct range_entry *range, struct range_entry *otherrange,
2322 struct range_entry **otherrangep,
2323 unsigned int count, enum tree_code opcode,
2324 vec<operand_entry *> *ops, tree exp, gimple_seq seq,
2325 bool in_p, tree low, tree high, bool strict_overflow_p)
2326{
2327 operand_entry *oe = (*ops)[range->idx];
2328 tree op = oe->op;
2329 gimple *stmt = op ? SSA_NAME_DEF_STMT (op)
2330 : last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
2331 location_t loc = gimple_location (stmt);
2332 tree optype = op ? TREE_TYPE (op) : boolean_type_node;
2333 tree tem = build_range_check (loc, optype, unshare_expr (exp),
2334 in_p, low, high);
2335 enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
2336 gimple_stmt_iterator gsi;
2337 unsigned int i, uid;
2338
2339 if (tem == NULL_TREE)
2340 return false;
2341
2342 /* If op is default def SSA_NAME, there is no place to insert the
2343 new comparison. Give up, unless we can use OP itself as the
2344 range test. */
2345 if (op && SSA_NAME_IS_DEFAULT_DEF (op))
2346 {
2347 if (op == range->exp
2348 && ((TYPE_PRECISION (optype) == 1 && TYPE_UNSIGNED (optype))
2349 || TREE_CODE (optype) == BOOLEAN_TYPE)
2350 && (op == tem
2351 || (TREE_CODE (tem) == EQ_EXPR
2352 && TREE_OPERAND (tem, 0) == op
2353 && integer_onep (TREE_OPERAND (tem, 1))))
2354 && opcode != BIT_IOR_EXPR
2355 && (opcode != ERROR_MARK || oe->rank != BIT_IOR_EXPR))
2356 {
2357 stmt = NULL;
2358 tem = op;
2359 }
2360 else
2361 return false;
2362 }
2363
2364 if (strict_overflow_p && issue_strict_overflow_warning (wc))
2365 warning_at (loc, OPT_Wstrict_overflow,
2366 "assuming signed overflow does not occur "
2367 "when simplifying range test");
2368
2369 if (dump_file && (dump_flags & TDF_DETAILS))
2370 {
2371 struct range_entry *r;
2372 fprintf (dump_file, "Optimizing range tests ");
2373 print_generic_expr (dump_file, range->exp);
2374 fprintf (dump_file, " %c[", range->in_p ? '+' : '-');
2375 print_generic_expr (dump_file, range->low);
2376 fprintf (dump_file, ", ");
2377 print_generic_expr (dump_file, range->high);
2378 fprintf (dump_file, "]");
2379 for (i = 0; i < count; i++)
2380 {
2381 if (otherrange)
2382 r = otherrange + i;
2383 else
2384 r = otherrangep[i];
2385 if (r->exp
2386 && r->exp != range->exp
2387 && TREE_CODE (r->exp) == SSA_NAME)
2388 {
2389 fprintf (dump_file, " and ");
2390 print_generic_expr (dump_file, r->exp);
2391 }
2392 else
2393 fprintf (dump_file, " and");
2394 fprintf (dump_file, " %c[", r->in_p ? '+' : '-');
2395 print_generic_expr (dump_file, r->low);
2396 fprintf (dump_file, ", ");
2397 print_generic_expr (dump_file, r->high);
2398 fprintf (dump_file, "]");
2399 }
2400 fprintf (dump_file, "\n into ");
2401 print_generic_expr (dump_file, tem);
2402 fprintf (dump_file, "\n");
2403 }
2404
2405 if (opcode == BIT_IOR_EXPR
2406 || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
2407 tem = invert_truthvalue_loc (loc, tem);
2408
2409 tem = fold_convert_loc (loc, optype, tem);
2410 if (stmt)
2411 {
2412 gsi = gsi_for_stmt (stmt);
2413 uid = gimple_uid (stmt);
2414 }
2415 else
2416 {
2417 gsi = gsi_none ();
2418 uid = 0;
2419 }
2420 if (stmt == NULL)
2421 gcc_checking_assert (tem == op);
2422 /* In rare cases range->exp can be equal to lhs of stmt.
2423 In that case we have to insert after the stmt rather then before
2424 it. If stmt is a PHI, insert it at the start of the basic block. */
2425 else if (op != range->exp)
2426 {
2427 gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
2428 tem = force_into_ssa_name (&gsi, tem, true);
2429 gsi_prev (&gsi);
2430 }
2431 else if (gimple_code (stmt) != GIMPLE_PHI)
2432 {
2433 gsi_insert_seq_after (&gsi, seq, GSI_CONTINUE_LINKING);
2434 tem = force_into_ssa_name (&gsi, tem, false);
2435 }
2436 else
2437 {
2438 gsi = gsi_after_labels (gimple_bb (stmt));
2439 if (!gsi_end_p (gsi))
2440 uid = gimple_uid (gsi_stmt (gsi));
2441 else
2442 {
2443 gsi = gsi_start_bb (gimple_bb (stmt));
2444 uid = 1;
2445 while (!gsi_end_p (gsi))
2446 {
2447 uid = gimple_uid (gsi_stmt (gsi));
2448 gsi_next (&gsi);
2449 }
2450 }
2451 gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
2452 tem = force_into_ssa_name (&gsi, tem, true);
2453 if (gsi_end_p (gsi))
2454 gsi = gsi_last_bb (gimple_bb (stmt));
2455 else
2456 gsi_prev (&gsi);
2457 }
2458 for (; !gsi_end_p (gsi); gsi_prev (&gsi))
2459 if (gimple_uid (gsi_stmt (gsi)))
2460 break;
2461 else
2462 gimple_set_uid (gsi_stmt (gsi), uid);
2463
2464 oe->op = tem;
2465 range->exp = exp;
2466 range->low = low;
2467 range->high = high;
2468 range->in_p = in_p;
2469 range->strict_overflow_p = false;
2470
2471 for (i = 0; i < count; i++)
2472 {
2473 if (otherrange)
2474 range = otherrange + i;
2475 else
2476 range = otherrangep[i];
2477 oe = (*ops)[range->idx];
2478 /* Now change all the other range test immediate uses, so that
2479 those tests will be optimized away. */
2480 if (opcode == ERROR_MARK)
2481 {
2482 if (oe->op)
2483 oe->op = build_int_cst (TREE_TYPE (oe->op),
2484 oe->rank == BIT_IOR_EXPR ? 0 : 1);
2485 else
2486 oe->op = (oe->rank == BIT_IOR_EXPR
2487 ? boolean_false_node : boolean_true_node);
2488 }
2489 else
2490 oe->op = error_mark_node;
2491 range->exp = NULL_TREE;
2492 range->low = NULL_TREE;
2493 range->high = NULL_TREE;
2494 }
2495 return true;
2496}
2497
2498/* Optimize X == CST1 || X == CST2
2499 if popcount (CST1 ^ CST2) == 1 into
2500 (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)).
2501 Similarly for ranges. E.g.
2502 X != 2 && X != 3 && X != 10 && X != 11
2503 will be transformed by the previous optimization into
2504 !((X - 2U) <= 1U || (X - 10U) <= 1U)
2505 and this loop can transform that into
2506 !(((X & ~8) - 2U) <= 1U). */
2507
2508static bool
2509optimize_range_tests_xor (enum tree_code opcode, tree type,
2510 tree lowi, tree lowj, tree highi, tree highj,
2511 vec<operand_entry *> *ops,
2512 struct range_entry *rangei,
2513 struct range_entry *rangej)
2514{
2515 tree lowxor, highxor, tem, exp;
2516 /* Check lowi ^ lowj == highi ^ highj and
2517 popcount (lowi ^ lowj) == 1. */
2518 lowxor = fold_binary (BIT_XOR_EXPR, type, lowi, lowj);
2519 if (lowxor == NULL_TREE || TREE_CODE (lowxor) != INTEGER_CST)
2520 return false;
2521 if (!integer_pow2p (lowxor))
2522 return false;
2523 highxor = fold_binary (BIT_XOR_EXPR, type, highi, highj);
2524 if (!tree_int_cst_equal (lowxor, highxor))
2525 return false;
2526
2527 tem = fold_build1 (BIT_NOT_EXPR, type, lowxor);
2528 exp = fold_build2 (BIT_AND_EXPR, type, rangei->exp, tem);
2529 lowj = fold_build2 (BIT_AND_EXPR, type, lowi, tem);
2530 highj = fold_build2 (BIT_AND_EXPR, type, highi, tem);
2531 if (update_range_test (rangei, rangej, NULL, 1, opcode, ops, exp,
2532 NULL, rangei->in_p, lowj, highj,
2533 rangei->strict_overflow_p
2534 || rangej->strict_overflow_p))
2535 return true;
2536 return false;
2537}
2538
2539/* Optimize X == CST1 || X == CST2
2540 if popcount (CST2 - CST1) == 1 into
2541 ((X - CST1) & ~(CST2 - CST1)) == 0.
2542 Similarly for ranges. E.g.
2543 X == 43 || X == 76 || X == 44 || X == 78 || X == 77 || X == 46
2544 || X == 75 || X == 45
2545 will be transformed by the previous optimization into
2546 (X - 43U) <= 3U || (X - 75U) <= 3U
2547 and this loop can transform that into
2548 ((X - 43U) & ~(75U - 43U)) <= 3U. */
2549static bool
2550optimize_range_tests_diff (enum tree_code opcode, tree type,
2551 tree lowi, tree lowj, tree highi, tree highj,
2552 vec<operand_entry *> *ops,
2553 struct range_entry *rangei,
2554 struct range_entry *rangej)
2555{
2556 tree tem1, tem2, mask;
2557 /* Check highi - lowi == highj - lowj. */
2558 tem1 = fold_binary (MINUS_EXPR, type, highi, lowi);
2559 if (tem1 == NULL_TREE || TREE_CODE (tem1) != INTEGER_CST)
2560 return false;
2561 tem2 = fold_binary (MINUS_EXPR, type, highj, lowj);
2562 if (!tree_int_cst_equal (tem1, tem2))
2563 return false;
2564 /* Check popcount (lowj - lowi) == 1. */
2565 tem1 = fold_binary (MINUS_EXPR, type, lowj, lowi);
2566 if (tem1 == NULL_TREE || TREE_CODE (tem1) != INTEGER_CST)
2567 return false;
2568 if (!integer_pow2p (tem1))
2569 return false;
2570
2571 type = unsigned_type_for (type);
2572 tem1 = fold_convert (type, tem1);
2573 tem2 = fold_convert (type, tem2);
2574 lowi = fold_convert (type, lowi);
2575 mask = fold_build1 (BIT_NOT_EXPR, type, tem1);
2576 tem1 = fold_build2 (MINUS_EXPR, type,
2577 fold_convert (type, rangei->exp), lowi);
2578 tem1 = fold_build2 (BIT_AND_EXPR, type, tem1, mask);
2579 lowj = build_int_cst (type, 0);
2580 if (update_range_test (rangei, rangej, NULL, 1, opcode, ops, tem1,
2581 NULL, rangei->in_p, lowj, tem2,
2582 rangei->strict_overflow_p
2583 || rangej->strict_overflow_p))
2584 return true;
2585 return false;
2586}
2587
2588/* It does some common checks for function optimize_range_tests_xor and
2589 optimize_range_tests_diff.
2590 If OPTIMIZE_XOR is TRUE, it calls optimize_range_tests_xor.
2591 Else it calls optimize_range_tests_diff. */
2592
2593static bool
2594optimize_range_tests_1 (enum tree_code opcode, int first, int length,
2595 bool optimize_xor, vec<operand_entry *> *ops,
2596 struct range_entry *ranges)
2597{
2598 int i, j;
2599 bool any_changes = false;
2600 for (i = first; i < length; i++)
2601 {
2602 tree lowi, highi, lowj, highj, type, tem;
2603
2604 if (ranges[i].exp == NULL_TREE || ranges[i].in_p)
2605 continue;
2606 type = TREE_TYPE (ranges[i].exp);
2607 if (!INTEGRAL_TYPE_P (type))
2608 continue;
2609 lowi = ranges[i].low;
2610 if (lowi == NULL_TREE)
2611 lowi = TYPE_MIN_VALUE (type);
2612 highi = ranges[i].high;
2613 if (highi == NULL_TREE)
2614 continue;
2615 for (j = i + 1; j < length && j < i + 64; j++)
2616 {
2617 bool changes;
2618 if (ranges[i].exp != ranges[j].exp || ranges[j].in_p)
2619 continue;
2620 lowj = ranges[j].low;
2621 if (lowj == NULL_TREE)
2622 continue;
2623 highj = ranges[j].high;
2624 if (highj == NULL_TREE)
2625 highj = TYPE_MAX_VALUE (type);
2626 /* Check lowj > highi. */
2627 tem = fold_binary (GT_EXPR, boolean_type_node,
2628 lowj, highi);
2629 if (tem == NULL_TREE || !integer_onep (tem))
2630 continue;
2631 if (optimize_xor)
2632 changes = optimize_range_tests_xor (opcode, type, lowi, lowj,
2633 highi, highj, ops,
2634 ranges + i, ranges + j);
2635 else
2636 changes = optimize_range_tests_diff (opcode, type, lowi, lowj,
2637 highi, highj, ops,
2638 ranges + i, ranges + j);
2639 if (changes)
2640 {
2641 any_changes = true;
2642 break;
2643 }
2644 }
2645 }
2646 return any_changes;
2647}
2648
2649/* Helper function of optimize_range_tests_to_bit_test. Handle a single
2650 range, EXP, LOW, HIGH, compute bit mask of bits to test and return
2651 EXP on success, NULL otherwise. */
2652
2653static tree
2654extract_bit_test_mask (tree exp, int prec, tree totallow, tree low, tree high,
2655 wide_int *mask, tree *totallowp)
2656{
2657 tree tem = int_const_binop (MINUS_EXPR, high, low);
2658 if (tem == NULL_TREE
2659 || TREE_CODE (tem) != INTEGER_CST
2660 || TREE_OVERFLOW (tem)
2661 || tree_int_cst_sgn (tem) == -1
2662 || compare_tree_int (tem, prec) != -1)
2663 return NULL_TREE;
2664
2665 unsigned HOST_WIDE_INT max = tree_to_uhwi (tem) + 1;
2666 *mask = wi::shifted_mask (0, max, false, prec);
2667 if (TREE_CODE (exp) == BIT_AND_EXPR
2668 && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
2669 {
2670 widest_int msk = wi::to_widest (TREE_OPERAND (exp, 1));
2671 msk = wi::zext (~msk, TYPE_PRECISION (TREE_TYPE (exp)));
2672 if (wi::popcount (msk) == 1
2673 && wi::ltu_p (msk, prec - max))
2674 {
2675 *mask |= wi::shifted_mask (msk.to_uhwi (), max, false, prec);
2676 max += msk.to_uhwi ();
2677 exp = TREE_OPERAND (exp, 0);
2678 if (integer_zerop (low)
2679 && TREE_CODE (exp) == PLUS_EXPR
2680 && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
2681 {
2682 tree ret = TREE_OPERAND (exp, 0);
2683 STRIP_NOPS (ret);
2684 widest_int bias
2685 = wi::neg (wi::sext (wi::to_widest (TREE_OPERAND (exp, 1)),
2686 TYPE_PRECISION (TREE_TYPE (low))));
2687 tree tbias = wide_int_to_tree (TREE_TYPE (ret), bias);
2688 if (totallowp)
2689 {
2690 *totallowp = tbias;
2691 return ret;
2692 }
2693 else if (!tree_int_cst_lt (totallow, tbias))
2694 return NULL_TREE;
2695 bias = wi::to_widest (tbias);
2696 bias -= wi::to_widest (totallow);
2697 if (bias >= 0 && bias < prec - max)
2698 {
2699 *mask = wi::lshift (*mask, bias);
2700 return ret;
2701 }
2702 }
2703 }
2704 }
2705 if (totallowp)
2706 return exp;
2707 if (!tree_int_cst_lt (totallow, low))
2708 return exp;
2709 tem = int_const_binop (MINUS_EXPR, low, totallow);
2710 if (tem == NULL_TREE
2711 || TREE_CODE (tem) != INTEGER_CST
2712 || TREE_OVERFLOW (tem)
2713 || compare_tree_int (tem, prec - max) == 1)
2714 return NULL_TREE;
2715
2716 *mask = wi::lshift (*mask, wi::to_widest (tem));
2717 return exp;
2718}
2719
2720/* Attempt to optimize small range tests using bit test.
2721 E.g.
2722 X != 43 && X != 76 && X != 44 && X != 78 && X != 49
2723 && X != 77 && X != 46 && X != 75 && X != 45 && X != 82
2724 has been by earlier optimizations optimized into:
2725 ((X - 43U) & ~32U) > 3U && X != 49 && X != 82
2726 As all the 43 through 82 range is less than 64 numbers,
2727 for 64-bit word targets optimize that into:
2728 (X - 43U) > 40U && ((1 << (X - 43U)) & 0x8F0000004FULL) == 0 */
2729
2730static bool
2731optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
2732 vec<operand_entry *> *ops,
2733 struct range_entry *ranges)
2734{
2735 int i, j;
2736 bool any_changes = false;
2737 int prec = GET_MODE_BITSIZE (word_mode);
2738 auto_vec<struct range_entry *, 64> candidates;
2739
2740 for (i = first; i < length - 2; i++)
2741 {
2742 tree lowi, highi, lowj, highj, type;
2743
2744 if (ranges[i].exp == NULL_TREE || ranges[i].in_p)
2745 continue;
2746 type = TREE_TYPE (ranges[i].exp);
2747 if (!INTEGRAL_TYPE_P (type))
2748 continue;
2749 lowi = ranges[i].low;
2750 if (lowi == NULL_TREE)
2751 lowi = TYPE_MIN_VALUE (type);
2752 highi = ranges[i].high;
2753 if (highi == NULL_TREE)
2754 continue;
2755 wide_int mask;
2756 tree exp = extract_bit_test_mask (ranges[i].exp, prec, lowi, lowi,
2757 highi, &mask, &lowi);
2758 if (exp == NULL_TREE)
2759 continue;
2760 bool strict_overflow_p = ranges[i].strict_overflow_p;
2761 candidates.truncate (0);
2762 int end = MIN (i + 64, length);
2763 for (j = i + 1; j < end; j++)
2764 {
2765 tree exp2;
2766 if (ranges[j].exp == NULL_TREE || ranges[j].in_p)
2767 continue;
2768 if (ranges[j].exp == exp)
2769 ;
2770 else if (TREE_CODE (ranges[j].exp) == BIT_AND_EXPR)
2771 {
2772 exp2 = TREE_OPERAND (ranges[j].exp, 0);
2773 if (exp2 == exp)
2774 ;
2775 else if (TREE_CODE (exp2) == PLUS_EXPR)
2776 {
2777 exp2 = TREE_OPERAND (exp2, 0);
2778 STRIP_NOPS (exp2);
2779 if (exp2 != exp)
2780 continue;
2781 }
2782 else
2783 continue;
2784 }
2785 else
2786 continue;
2787 lowj = ranges[j].low;
2788 if (lowj == NULL_TREE)
2789 continue;
2790 highj = ranges[j].high;
2791 if (highj == NULL_TREE)
2792 highj = TYPE_MAX_VALUE (type);
2793 wide_int mask2;
2794 exp2 = extract_bit_test_mask (ranges[j].exp, prec, lowi, lowj,
2795 highj, &mask2, NULL);
2796 if (exp2 != exp)
2797 continue;
2798 mask |= mask2;
2799 strict_overflow_p |= ranges[j].strict_overflow_p;
2800 candidates.safe_push (&ranges[j]);
2801 }
2802
2803 /* If we need otherwise 3 or more comparisons, use a bit test. */
2804 if (candidates.length () >= 2)
2805 {
2806 tree high = wide_int_to_tree (TREE_TYPE (lowi),
2807 wi::to_widest (lowi)
2808 + prec - 1 - wi::clz (mask));
2809 operand_entry *oe = (*ops)[ranges[i].idx];
2810 tree op = oe->op;
2811 gimple *stmt = op ? SSA_NAME_DEF_STMT (op)
2812 : last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
2813 location_t loc = gimple_location (stmt);
2814 tree optype = op ? TREE_TYPE (op) : boolean_type_node;
2815
2816 /* See if it isn't cheaper to pretend the minimum value of the
2817 range is 0, if maximum value is small enough.
2818 We can avoid then subtraction of the minimum value, but the
2819 mask constant could be perhaps more expensive. */
2820 if (compare_tree_int (lowi, 0) > 0
2821 && compare_tree_int (high, prec) < 0)
2822 {
2823 int cost_diff;
2824 HOST_WIDE_INT m = tree_to_uhwi (lowi);
2825 rtx reg = gen_raw_REG (word_mode, 10000);
2826 bool speed_p = optimize_bb_for_speed_p (gimple_bb (stmt));
2827 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
2828 GEN_INT (-m)), speed_p);
2829 rtx r = immed_wide_int_const (mask, word_mode);
2830 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
2831 word_mode, speed_p);
2832 r = immed_wide_int_const (wi::lshift (mask, m), word_mode);
2833 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
2834 word_mode, speed_p);
2835 if (cost_diff > 0)
2836 {
2837 mask = wi::lshift (mask, m);
2838 lowi = build_zero_cst (TREE_TYPE (lowi));
2839 }
2840 }
2841
2842 tree tem = build_range_check (loc, optype, unshare_expr (exp),
2843 false, lowi, high);
2844 if (tem == NULL_TREE || is_gimple_val (tem))
2845 continue;
2846 tree etype = unsigned_type_for (TREE_TYPE (exp));
2847 exp = fold_build2_loc (loc, MINUS_EXPR, etype,
2848 fold_convert_loc (loc, etype, exp),
2849 fold_convert_loc (loc, etype, lowi));
2850 exp = fold_convert_loc (loc, integer_type_node, exp);
2851 tree word_type = lang_hooks.types.type_for_mode (word_mode, 1);
2852 exp = fold_build2_loc (loc, LSHIFT_EXPR, word_type,
2853 build_int_cst (word_type, 1), exp);
2854 exp = fold_build2_loc (loc, BIT_AND_EXPR, word_type, exp,
2855 wide_int_to_tree (word_type, mask));
2856 exp = fold_build2_loc (loc, EQ_EXPR, optype, exp,
2857 build_zero_cst (word_type));
2858 if (is_gimple_val (exp))
2859 continue;
2860
2861 /* The shift might have undefined behavior if TEM is true,
2862 but reassociate_bb isn't prepared to have basic blocks
2863 split when it is running. So, temporarily emit a code
2864 with BIT_IOR_EXPR instead of &&, and fix it up in
2865 branch_fixup. */
2866 gimple_seq seq;
2867 tem = force_gimple_operand (tem, &seq, true, NULL_TREE);
2868 gcc_assert (TREE_CODE (tem) == SSA_NAME);
2869 gimple_set_visited (SSA_NAME_DEF_STMT (tem), true);
2870 gimple_seq seq2;
2871 exp = force_gimple_operand (exp, &seq2, true, NULL_TREE);
2872 gimple_seq_add_seq_without_update (&seq, seq2);
2873 gcc_assert (TREE_CODE (exp) == SSA_NAME);
2874 gimple_set_visited (SSA_NAME_DEF_STMT (exp), true);
2875 gimple *g = gimple_build_assign (make_ssa_name (optype),
2876 BIT_IOR_EXPR, tem, exp);
2877 gimple_set_location (g, loc);
2878 gimple_seq_add_stmt_without_update (&seq, g);
2879 exp = gimple_assign_lhs (g);
2880 tree val = build_zero_cst (optype);
2881 if (update_range_test (&ranges[i], NULL, candidates.address (),
2882 candidates.length (), opcode, ops, exp,
2883 seq, false, val, val, strict_overflow_p))
2884 {
2885 any_changes = true;
2886 reassoc_branch_fixups.safe_push (tem);
2887 }
2888 else
2889 gimple_seq_discard (seq);
2890 }
2891 }
2892 return any_changes;
2893}
2894
2895/* Optimize x != 0 && y != 0 && z != 0 into (x | y | z) != 0
2896 and similarly x != -1 && y != -1 && y != -1 into (x & y & z) != -1. */
2897
2898static bool
2899optimize_range_tests_cmp_bitwise (enum tree_code opcode, int first, int length,
2900 vec<operand_entry *> *ops,
2901 struct range_entry *ranges)
2902{
2903 int i;
2904 unsigned int b;
2905 bool any_changes = false;
2906 auto_vec<int, 128> buckets;
2907 auto_vec<int, 32> chains;
2908 auto_vec<struct range_entry *, 32> candidates;
2909
2910 for (i = first; i < length; i++)
2911 {
2912 if (ranges[i].exp == NULL_TREE
2913 || TREE_CODE (ranges[i].exp) != SSA_NAME
2914 || !ranges[i].in_p
2915 || TYPE_PRECISION (TREE_TYPE (ranges[i].exp)) <= 1
2916 || TREE_CODE (TREE_TYPE (ranges[i].exp)) == BOOLEAN_TYPE
2917 || ranges[i].low == NULL_TREE
2918 || ranges[i].low != ranges[i].high)
2919 continue;
2920
2921 bool zero_p = integer_zerop (ranges[i].low);
2922 if (!zero_p && !integer_all_onesp (ranges[i].low))
2923 continue;
2924
2925 b = TYPE_PRECISION (TREE_TYPE (ranges[i].exp)) * 2 + !zero_p;
2926 if (buckets.length () <= b)
2927 buckets.safe_grow_cleared (b + 1);
2928 if (chains.length () <= (unsigned) i)
2929 chains.safe_grow (i + 1);
2930 chains[i] = buckets[b];
2931 buckets[b] = i + 1;
2932 }
2933
2934 FOR_EACH_VEC_ELT (buckets, b, i)
2935 if (i && chains[i - 1])
2936 {
2937 int j, k = i;
2938 for (j = chains[i - 1]; j; j = chains[j - 1])
2939 {
2940 gimple *gk = SSA_NAME_DEF_STMT (ranges[k - 1].exp);
2941 gimple *gj = SSA_NAME_DEF_STMT (ranges[j - 1].exp);
2942 if (reassoc_stmt_dominates_stmt_p (gk, gj))
2943 k = j;
2944 }
2945 tree type1 = TREE_TYPE (ranges[k - 1].exp);
2946 tree type2 = NULL_TREE;
2947 bool strict_overflow_p = false;
2948 candidates.truncate (0);
2949 for (j = i; j; j = chains[j - 1])
2950 {
2951 tree type = TREE_TYPE (ranges[j - 1].exp);
2952 strict_overflow_p |= ranges[j - 1].strict_overflow_p;
2953 if (j == k
2954 || useless_type_conversion_p (type1, type))
2955 ;
2956 else if (type2 == NULL_TREE
2957 || useless_type_conversion_p (type2, type))
2958 {
2959 if (type2 == NULL_TREE)
2960 type2 = type;
2961 candidates.safe_push (&ranges[j - 1]);
2962 }
2963 }
2964 unsigned l = candidates.length ();
2965 for (j = i; j; j = chains[j - 1])
2966 {
2967 tree type = TREE_TYPE (ranges[j - 1].exp);
2968 if (j == k)
2969 continue;
2970 if (useless_type_conversion_p (type1, type))
2971 ;
2972 else if (type2 == NULL_TREE
2973 || useless_type_conversion_p (type2, type))
2974 continue;
2975 candidates.safe_push (&ranges[j - 1]);
2976 }
2977 gimple_seq seq = NULL;
2978 tree op = NULL_TREE;
2979 unsigned int id;
2980 struct range_entry *r;
2981 candidates.safe_push (&ranges[k - 1]);
2982 FOR_EACH_VEC_ELT (candidates, id, r)
2983 {
2984 gimple *g;
2985 if (id == 0)
2986 {
2987 op = r->exp;
2988 continue;
2989 }
2990 if (id == l)
2991 {
2992 g = gimple_build_assign (make_ssa_name (type1), NOP_EXPR, op);
2993 gimple_seq_add_stmt_without_update (&seq, g);
2994 op = gimple_assign_lhs (g);
2995 }
2996 tree type = TREE_TYPE (r->exp);
2997 tree exp = r->exp;
2998 if (id >= l && !useless_type_conversion_p (type1, type))
2999 {
3000 g = gimple_build_assign (make_ssa_name (type1), NOP_EXPR, exp);
3001 gimple_seq_add_stmt_without_update (&seq, g);
3002 exp = gimple_assign_lhs (g);
3003 }
3004 g = gimple_build_assign (make_ssa_name (id >= l ? type1 : type2),
3005 (b & 1) ? BIT_AND_EXPR : BIT_IOR_EXPR,
3006 op, exp);
3007 gimple_seq_add_stmt_without_update (&seq, g);
3008 op = gimple_assign_lhs (g);
3009 }
3010 candidates.pop ();
3011 if (update_range_test (&ranges[k - 1], NULL, candidates.address (),
3012 candidates.length (), opcode, ops, op,
3013 seq, true, ranges[k - 1].low,
3014 ranges[k - 1].low, strict_overflow_p))
3015 any_changes = true;
3016 else
3017 gimple_seq_discard (seq);
3018 }
3019
3020 return any_changes;
3021}
3022
3023/* Attempt to optimize for signed a and b where b is known to be >= 0:
3024 a >= 0 && a < b into (unsigned) a < (unsigned) b
3025 a >= 0 && a <= b into (unsigned) a <= (unsigned) b */
3026
3027static bool
3028optimize_range_tests_var_bound (enum tree_code opcode, int first, int length,
3029 vec<operand_entry *> *ops,
3030 struct range_entry *ranges)
3031{
3032 int i;
3033 bool any_changes = false;
3034 hash_map<tree, int> *map = NULL;
3035
3036 for (i = first; i < length; i++)
3037 {
3038 if (ranges[i].exp == NULL_TREE
3039 || TREE_CODE (ranges[i].exp) != SSA_NAME
3040 || !ranges[i].in_p)
3041 continue;
3042
3043 tree type = TREE_TYPE (ranges[i].exp);
3044 if (!INTEGRAL_TYPE_P (type)
3045 || TYPE_UNSIGNED (type)
3046 || ranges[i].low == NULL_TREE
3047 || !integer_zerop (ranges[i].low)
3048 || ranges[i].high != NULL_TREE)
3049 continue;
3050 /* EXP >= 0 here. */
3051 if (map == NULL)
3052 map = new hash_map <tree, int>;
3053 map->put (ranges[i].exp, i);
3054 }
3055
3056 if (map == NULL)
3057 return false;
3058
3059 for (i = 0; i < length; i++)
3060 {
3061 bool in_p = ranges[i].in_p;
3062 if (ranges[i].low == NULL_TREE
3063 || ranges[i].high == NULL_TREE)
3064 continue;
3065 if (!integer_zerop (ranges[i].low)
3066 || !integer_zerop (ranges[i].high))
3067 {
3068 if (ranges[i].exp
3069 && TYPE_PRECISION (TREE_TYPE (ranges[i].exp)) == 1
3070 && TYPE_UNSIGNED (TREE_TYPE (ranges[i].exp))
3071 && integer_onep (ranges[i].low)
3072 && integer_onep (ranges[i].high))
3073 in_p = !in_p;
3074 else
3075 continue;
3076 }
3077
3078 gimple *stmt;
3079 tree_code ccode;
3080 tree rhs1, rhs2;
3081 if (ranges[i].exp)
3082 {
3083 if (TREE_CODE (ranges[i].exp) != SSA_NAME)
3084 continue;
3085 stmt = SSA_NAME_DEF_STMT (ranges[i].exp);
3086 if (!is_gimple_assign (stmt))
3087 continue;
3088 ccode = gimple_assign_rhs_code (stmt);
3089 rhs1 = gimple_assign_rhs1 (stmt);
3090 rhs2 = gimple_assign_rhs2 (stmt);
3091 }
3092 else
3093 {
3094 operand_entry *oe = (*ops)[ranges[i].idx];
3095 stmt = last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
3096 if (gimple_code (stmt) != GIMPLE_COND)
3097 continue;
3098 ccode = gimple_cond_code (stmt);
3099 rhs1 = gimple_cond_lhs (stmt);
3100 rhs2 = gimple_cond_rhs (stmt);
3101 }
3102
3103 if (TREE_CODE (rhs1) != SSA_NAME
3104 || rhs2 == NULL_TREE
3105 || TREE_CODE (rhs2) != SSA_NAME)
3106 continue;
3107
3108 switch (ccode)
3109 {
3110 case GT_EXPR:
3111 case GE_EXPR:
3112 case LT_EXPR:
3113 case LE_EXPR:
3114 break;
3115 default:
3116 continue;
3117 }
3118 if (in_p)
3119 ccode = invert_tree_comparison (ccode, false);
3120 switch (ccode)
3121 {
3122 case GT_EXPR:
3123 case GE_EXPR:
3124 std::swap (rhs1, rhs2);
3125 ccode = swap_tree_comparison (ccode);
3126 break;
3127 case LT_EXPR:
3128 case LE_EXPR:
3129 break;
3130 default:
3131 gcc_unreachable ();
3132 }
3133
3134 int *idx = map->get (rhs1);
3135 if (idx == NULL)
3136 continue;
3137
3138 wide_int nz = get_nonzero_bits (rhs2);
3139 if (wi::neg_p (nz))
3140 continue;
3141
3142 /* We have EXP < RHS2 or EXP <= RHS2 where EXP >= 0
3143 and RHS2 is known to be RHS2 >= 0. */
3144 tree utype = unsigned_type_for (TREE_TYPE (rhs1));
3145
3146 enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
3147 if ((ranges[*idx].strict_overflow_p
3148 || ranges[i].strict_overflow_p)
3149 && issue_strict_overflow_warning (wc))
3150 warning_at (gimple_location (stmt), OPT_Wstrict_overflow,
3151 "assuming signed overflow does not occur "
3152 "when simplifying range test");
3153
3154 if (dump_file && (dump_flags & TDF_DETAILS))
3155 {
3156 struct range_entry *r = &ranges[*idx];
3157 fprintf (dump_file, "Optimizing range test ");
3158 print_generic_expr (dump_file, r->exp);
3159 fprintf (dump_file, " +[");
3160 print_generic_expr (dump_file, r->low);
3161 fprintf (dump_file, ", ");
3162 print_generic_expr (dump_file, r->high);
3163 fprintf (dump_file, "] and comparison ");
3164 print_generic_expr (dump_file, rhs1);
3165 fprintf (dump_file, " %s ", op_symbol_code (ccode));
3166 print_generic_expr (dump_file, rhs2);
3167 fprintf (dump_file, "\n into (");
3168 print_generic_expr (dump_file, utype);
3169 fprintf (dump_file, ") ");
3170 print_generic_expr (dump_file, rhs1);
3171 fprintf (dump_file, " %s (", op_symbol_code (ccode));
3172 print_generic_expr (dump_file, utype);
3173 fprintf (dump_file, ") ");
3174 print_generic_expr (dump_file, rhs2);
3175 fprintf (dump_file, "\n");
3176 }
3177
3178 operand_entry *oe = (*ops)[ranges[i].idx];
3179 ranges[i].in_p = 0;
3180 if (opcode == BIT_IOR_EXPR
3181 || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
3182 {
3183 ranges[i].in_p = 1;
3184 ccode = invert_tree_comparison (ccode, false);
3185 }
3186
3187 unsigned int uid = gimple_uid (stmt);
3188 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
3189 gimple *g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, rhs1);
3190 gimple_set_uid (g, uid);
3191 rhs1 = gimple_assign_lhs (g);
3192 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3193 g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, rhs2);
3194 gimple_set_uid (g, uid);
3195 rhs2 = gimple_assign_lhs (g);
3196 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3197 if (tree_swap_operands_p (rhs1, rhs2))
3198 {
3199 std::swap (rhs1, rhs2);
3200 ccode = swap_tree_comparison (ccode);
3201 }
3202 if (gimple_code (stmt) == GIMPLE_COND)
3203 {
3204 gcond *c = as_a <gcond *> (stmt);
3205 gimple_cond_set_code (c, ccode);
3206 gimple_cond_set_lhs (c, rhs1);
3207 gimple_cond_set_rhs (c, rhs2);
3208 update_stmt (stmt);
3209 }
3210 else
3211 {
3212 tree ctype = oe->op ? TREE_TYPE (oe->op) : boolean_type_node;
3213 if (!INTEGRAL_TYPE_P (ctype)
3214 || (TREE_CODE (ctype) != BOOLEAN_TYPE
3215 && TYPE_PRECISION (ctype) != 1))
3216 ctype = boolean_type_node;
3217 g = gimple_build_assign (make_ssa_name (ctype), ccode, rhs1, rhs2);
3218 gimple_set_uid (g, uid);
3219 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3220 if (oe->op && ctype != TREE_TYPE (oe->op))
3221 {
3222 g = gimple_build_assign (make_ssa_name (TREE_TYPE (oe->op)),
3223 NOP_EXPR, gimple_assign_lhs (g));
3224 gimple_set_uid (g, uid);
3225 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3226 }
3227 ranges[i].exp = gimple_assign_lhs (g);
3228 oe->op = ranges[i].exp;
3229 ranges[i].low = build_zero_cst (TREE_TYPE (ranges[i].exp));
3230 ranges[i].high = ranges[i].low;
3231 }
3232 ranges[i].strict_overflow_p = false;
3233 oe = (*ops)[ranges[*idx].idx];
3234 /* Now change all the other range test immediate uses, so that
3235 those tests will be optimized away. */
3236 if (opcode == ERROR_MARK)
3237 {
3238 if (oe->op)
3239 oe->op = build_int_cst (TREE_TYPE (oe->op),
3240 oe->rank == BIT_IOR_EXPR ? 0 : 1);
3241 else
3242 oe->op = (oe->rank == BIT_IOR_EXPR
3243 ? boolean_false_node : boolean_true_node);
3244 }
3245 else
3246 oe->op = error_mark_node;
3247 ranges[*idx].exp = NULL_TREE;
3248 ranges[*idx].low = NULL_TREE;
3249 ranges[*idx].high = NULL_TREE;
3250 any_changes = true;
3251 }
3252
3253 delete map;
3254 return any_changes;
3255}
3256
3257/* Optimize range tests, similarly how fold_range_test optimizes
3258 it on trees. The tree code for the binary
3259 operation between all the operands is OPCODE.
3260 If OPCODE is ERROR_MARK, optimize_range_tests is called from within
3261 maybe_optimize_range_tests for inter-bb range optimization.
3262 In that case if oe->op is NULL, oe->id is bb->index whose
3263 GIMPLE_COND is && or ||ed into the test, and oe->rank says
3264 the actual opcode. */
3265
3266static bool
3267optimize_range_tests (enum tree_code opcode,
3268 vec<operand_entry *> *ops)
3269{
3270 unsigned int length = ops->length (), i, j, first;
3271 operand_entry *oe;
3272 struct range_entry *ranges;
3273 bool any_changes = false;
3274
3275 if (length == 1)
3276 return false;
3277
3278 ranges = XNEWVEC (struct range_entry, length);
3279 for (i = 0; i < length; i++)
3280 {
3281 oe = (*ops)[i];
3282 ranges[i].idx = i;
3283 init_range_entry (ranges + i, oe->op,
3284 oe->op
3285 ? NULL
3286 : last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id)));
3287 /* For | invert it now, we will invert it again before emitting
3288 the optimized expression. */
3289 if (opcode == BIT_IOR_EXPR
3290 || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
3291 ranges[i].in_p = !ranges[i].in_p;
3292 }
3293
3294 qsort (ranges, length, sizeof (*ranges), range_entry_cmp);
3295 for (i = 0; i < length; i++)
3296 if (ranges[i].exp != NULL_TREE && TREE_CODE (ranges[i].exp) == SSA_NAME)
3297 break;
3298
3299 /* Try to merge ranges. */
3300 for (first = i; i < length; i++)
3301 {
3302 tree low = ranges[i].low;
3303 tree high = ranges[i].high;
3304 int in_p = ranges[i].in_p;
3305 bool strict_overflow_p = ranges[i].strict_overflow_p;
3306 int update_fail_count = 0;
3307
3308 for (j = i + 1; j < length; j++)
3309 {
3310 if (ranges[i].exp != ranges[j].exp)
3311 break;
3312 if (!merge_ranges (&in_p, &low, &high, in_p, low, high,
3313 ranges[j].in_p, ranges[j].low, ranges[j].high))
3314 break;
3315 strict_overflow_p |= ranges[j].strict_overflow_p;
3316 }
3317
3318 if (j == i + 1)
3319 continue;
3320
3321 if (update_range_test (ranges + i, ranges + i + 1, NULL, j - i - 1,
3322 opcode, ops, ranges[i].exp, NULL, in_p,
3323 low, high, strict_overflow_p))
3324 {
3325 i = j - 1;
3326 any_changes = true;
3327 }
3328 /* Avoid quadratic complexity if all merge_ranges calls would succeed,
3329 while update_range_test would fail. */
3330 else if (update_fail_count == 64)
3331 i = j - 1;
3332 else
3333 ++update_fail_count;
3334 }
3335
3336 any_changes |= optimize_range_tests_1 (opcode, first, length, true,
3337 ops, ranges);
3338
3339 if (BRANCH_COST (optimize_function_for_speed_p (cfun), false) >= 2)
3340 any_changes |= optimize_range_tests_1 (opcode, first, length, false,
3341 ops, ranges);
3342 if (lshift_cheap_p (optimize_function_for_speed_p (cfun)))
3343 any_changes |= optimize_range_tests_to_bit_test (opcode, first, length,
3344 ops, ranges);
3345 any_changes |= optimize_range_tests_cmp_bitwise (opcode, first, length,
3346 ops, ranges);
3347 any_changes |= optimize_range_tests_var_bound (opcode, first, length, ops,
3348 ranges);
3349
3350 if (any_changes && opcode != ERROR_MARK)
3351 {
3352 j = 0;
3353 FOR_EACH_VEC_ELT (*ops, i, oe)
3354 {
3355 if (oe->op == error_mark_node)
3356 continue;
3357 else if (i != j)
3358 (*ops)[j] = oe;
3359 j++;
3360 }
3361 ops->truncate (j);
3362 }
3363
3364 XDELETEVEC (ranges);
3365 return any_changes;
3366}
3367
3368/* A subroutine of optimize_vec_cond_expr to extract and canonicalize
3369 the operands of the VEC_COND_EXPR. Returns ERROR_MARK on failure,
3370 otherwise the comparison code. */
3371
3372static tree_code
3373ovce_extract_ops (tree var, gassign **rets, bool *reti)
3374{
3375 if (TREE_CODE (var) != SSA_NAME)
3376 return ERROR_MARK;
3377
3378 gassign *stmt = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (var));
3379 if (stmt == NULL)
3380 return ERROR_MARK;
3381
3382 /* ??? If we start creating more COND_EXPR, we could perform
3383 this same optimization with them. For now, simplify. */
3384 if (gimple_assign_rhs_code (stmt) != VEC_COND_EXPR)
3385 return ERROR_MARK;
3386
3387 tree cond = gimple_assign_rhs1 (stmt);
3388 tree_code cmp = TREE_CODE (cond);
3389 if (TREE_CODE_CLASS (cmp) != tcc_comparison)
3390 return ERROR_MARK;
3391
3392 /* ??? For now, allow only canonical true and false result vectors.
3393 We could expand this to other constants should the need arise,
3394 but at the moment we don't create them. */
3395 tree t = gimple_assign_rhs2 (stmt);
3396 tree f = gimple_assign_rhs3 (stmt);
3397 bool inv;
3398 if (integer_all_onesp (t))
3399 inv = false;
3400 else if (integer_all_onesp (f))
3401 {
3402 cmp = invert_tree_comparison (cmp, false);
3403 inv = true;
3404 }
3405 else
3406 return ERROR_MARK;
3407 if (!integer_zerop (f))
3408 return ERROR_MARK;
3409
3410 /* Success! */
3411 if (rets)
3412 *rets = stmt;
3413 if (reti)
3414 *reti = inv;
3415 return cmp;
3416}
3417
3418/* Optimize the condition of VEC_COND_EXPRs which have been combined
3419 with OPCODE (either BIT_AND_EXPR or BIT_IOR_EXPR). */
3420
3421static bool
3422optimize_vec_cond_expr (tree_code opcode, vec<operand_entry *> *ops)
3423{
3424 unsigned int length = ops->length (), i, j;
3425 bool any_changes = false;
3426
3427 if (length == 1)
3428 return false;
3429
3430 for (i = 0; i < length; ++i)
3431 {
3432 tree elt0 = (*ops)[i]->op;
3433
3434 gassign *stmt0;
3435 bool invert;
3436 tree_code cmp0 = ovce_extract_ops (elt0, &stmt0, &invert);
3437 if (cmp0 == ERROR_MARK)
3438 continue;
3439
3440 for (j = i + 1; j < length; ++j)
3441 {
3442 tree &elt1 = (*ops)[j]->op;
3443
3444 gassign *stmt1;
3445 tree_code cmp1 = ovce_extract_ops (elt1, &stmt1, NULL);
3446 if (cmp1 == ERROR_MARK)
3447 continue;
3448
3449 tree cond0 = gimple_assign_rhs1 (stmt0);
3450 tree x0 = TREE_OPERAND (cond0, 0);
3451 tree y0 = TREE_OPERAND (cond0, 1);
3452
3453 tree cond1 = gimple_assign_rhs1 (stmt1);
3454 tree x1 = TREE_OPERAND (cond1, 0);
3455 tree y1 = TREE_OPERAND (cond1, 1);
3456
3457 tree comb;
3458 if (opcode == BIT_AND_EXPR)
3459 comb = maybe_fold_and_comparisons (cmp0, x0, y0, cmp1, x1, y1);
3460 else if (opcode == BIT_IOR_EXPR)
3461 comb = maybe_fold_or_comparisons (cmp0, x0, y0, cmp1, x1, y1);
3462 else
3463 gcc_unreachable ();
3464 if (comb == NULL)
3465 continue;
3466
3467 /* Success! */
3468 if (dump_file && (dump_flags & TDF_DETAILS))
3469 {
3470 fprintf (dump_file, "Transforming ");
3471 print_generic_expr (dump_file, cond0);
3472 fprintf (dump_file, " %c ", opcode == BIT_AND_EXPR ? '&' : '|');
3473 print_generic_expr (dump_file, cond1);
3474 fprintf (dump_file, " into ");
3475 print_generic_expr (dump_file, comb);
3476 fputc ('\n', dump_file);
3477 }
3478
3479 gimple_assign_set_rhs1 (stmt0, comb);
3480 if (invert)
3481 std::swap (*gimple_assign_rhs2_ptr (stmt0),
3482 *gimple_assign_rhs3_ptr (stmt0));
3483 update_stmt (stmt0);
3484
3485 elt1 = error_mark_node;
3486 any_changes = true;
3487 }
3488 }
3489
3490 if (any_changes)
3491 {
3492 operand_entry *oe;
3493 j = 0;
3494 FOR_EACH_VEC_ELT (*ops, i, oe)
3495 {
3496 if (oe->op == error_mark_node)
3497 continue;
3498 else if (i != j)
3499 (*ops)[j] = oe;
3500 j++;
3501 }
3502 ops->truncate (j);
3503 }
3504
3505 return any_changes;
3506}
3507
3508/* Return true if STMT is a cast like:
3509 <bb N>:
3510 ...
3511 _123 = (int) _234;
3512
3513 <bb M>:
3514 # _345 = PHI <_123(N), 1(...), 1(...)>
3515 where _234 has bool type, _123 has single use and
3516 bb N has a single successor M. This is commonly used in
3517 the last block of a range test.
3518
3519 Also Return true if STMT is tcc_compare like:
3520 <bb N>:
3521 ...
3522 _234 = a_2(D) == 2;
3523
3524 <bb M>:
3525 # _345 = PHI <_234(N), 1(...), 1(...)>
3526 _346 = (int) _345;
3527 where _234 has booltype, single use and
3528 bb N has a single successor M. This is commonly used in
3529 the last block of a range test. */
3530
3531static bool
3532final_range_test_p (gimple *stmt)
3533{
3534 basic_block bb, rhs_bb, lhs_bb;
3535 edge e;
3536 tree lhs, rhs;
3537 use_operand_p use_p;
3538 gimple *use_stmt;
3539
3540 if (!gimple_assign_cast_p (stmt)
3541 && (!is_gimple_assign (stmt)
3542 || (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
3543 != tcc_comparison)))
3544 return false;
3545 bb = gimple_bb (stmt);
3546 if (!single_succ_p (bb))
3547 return false;
3548 e = single_succ_edge (bb);
3549 if (e->flags & EDGE_COMPLEX)
3550 return false;
3551
3552 lhs = gimple_assign_lhs (stmt);
3553 rhs = gimple_assign_rhs1 (stmt);
3554 if (gimple_assign_cast_p (stmt)
3555 && (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3556 || TREE_CODE (rhs) != SSA_NAME
3557 || TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE))
3558 return false;
3559
3560 if (!gimple_assign_cast_p (stmt)
3561 && (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE))
3562 return false;
3563
3564 /* Test whether lhs is consumed only by a PHI in the only successor bb. */
3565 if (!single_imm_use (lhs, &use_p, &use_stmt))
3566 return false;
3567
3568 if (gimple_code (use_stmt) != GIMPLE_PHI
3569 || gimple_bb (use_stmt) != e->dest)
3570 return false;
3571
3572 /* And that the rhs is defined in the same loop. */
3573 if (gimple_assign_cast_p (stmt))
3574 {
3575 if (TREE_CODE (rhs) != SSA_NAME
3576 || !(rhs_bb = gimple_bb (SSA_NAME_DEF_STMT (rhs)))
3577 || !flow_bb_inside_loop_p (loop_containing_stmt (stmt), rhs_bb))
3578 return false;
3579 }
3580 else
3581 {
3582 if (TREE_CODE (lhs) != SSA_NAME
3583 || !(lhs_bb = gimple_bb (SSA_NAME_DEF_STMT (lhs)))
3584 || !flow_bb_inside_loop_p (loop_containing_stmt (stmt), lhs_bb))
3585 return false;
3586 }
3587
3588 return true;
3589}
3590
3591/* Return true if BB is suitable basic block for inter-bb range test
3592 optimization. If BACKWARD is true, BB should be the only predecessor
3593 of TEST_BB, and *OTHER_BB is either NULL and filled by the routine,
3594 or compared with to find a common basic block to which all conditions
3595 branch to if true resp. false. If BACKWARD is false, TEST_BB should
3596 be the only predecessor of BB. */
3597
3598static bool
3599suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb,
3600 bool backward)
3601{
3602 edge_iterator ei, ei2;
3603 edge e, e2;
3604 gimple *stmt;
3605 gphi_iterator gsi;
3606 bool other_edge_seen = false;
3607 bool is_cond;
3608
3609 if (test_bb == bb)
3610 return false;
3611 /* Check last stmt first. */
3612 stmt = last_stmt (bb);
3613 if (stmt == NULL
3614 || (gimple_code (stmt) != GIMPLE_COND
3615 && (backward || !final_range_test_p (stmt)))
3616 || gimple_visited_p (stmt)
3617 || stmt_could_throw_p (stmt)
3618 || *other_bb == bb)
3619 return false;
3620 is_cond = gimple_code (stmt) == GIMPLE_COND;
3621 if (is_cond)
3622 {
3623 /* If last stmt is GIMPLE_COND, verify that one of the succ edges
3624 goes to the next bb (if BACKWARD, it is TEST_BB), and the other
3625 to *OTHER_BB (if not set yet, try to find it out). */
3626 if (EDGE_COUNT (bb->succs) != 2)
3627 return false;
3628 FOR_EACH_EDGE (e, ei, bb->succs)
3629 {
3630 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3631 return false;
3632 if (e->dest == test_bb)
3633 {
3634 if (backward)
3635 continue;
3636 else
3637 return false;
3638 }
3639 if (e->dest == bb)
3640 return false;
3641 if (*other_bb == NULL)
3642 {
3643 FOR_EACH_EDGE (e2, ei2, test_bb->succs)
3644 if (!(e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3645 return false;
3646 else if (e->dest == e2->dest)
3647 *other_bb = e->dest;
3648 if (*other_bb == NULL)
3649 return false;
3650 }
3651 if (e->dest == *other_bb)
3652 other_edge_seen = true;
3653 else if (backward)
3654 return false;
3655 }
3656 if (*other_bb == NULL || !other_edge_seen)
3657 return false;
3658 }
3659 else if (single_succ (bb) != *other_bb)
3660 return false;
3661
3662 /* Now check all PHIs of *OTHER_BB. */
3663 e = find_edge (bb, *other_bb);
3664 e2 = find_edge (test_bb, *other_bb);
3665 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3666 {
3667 gphi *phi = gsi.phi ();
3668 /* If both BB and TEST_BB end with GIMPLE_COND, all PHI arguments
3669 corresponding to BB and TEST_BB predecessor must be the same. */
3670 if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx),
3671 gimple_phi_arg_def (phi, e2->dest_idx), 0))
3672 {
3673 /* Otherwise, if one of the blocks doesn't end with GIMPLE_COND,
3674 one of the PHIs should have the lhs of the last stmt in
3675 that block as PHI arg and that PHI should have 0 or 1
3676 corresponding to it in all other range test basic blocks
3677 considered. */
3678 if (!is_cond)
3679 {
3680 if (gimple_phi_arg_def (phi, e->dest_idx)
3681 == gimple_assign_lhs (stmt)
3682 && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx))
3683 || integer_onep (gimple_phi_arg_def (phi,
3684 e2->dest_idx))))
3685 continue;
3686 }
3687 else
3688 {
3689 gimple *test_last = last_stmt (test_bb);
3690 if (gimple_code (test_last) != GIMPLE_COND
3691 && gimple_phi_arg_def (phi, e2->dest_idx)
3692 == gimple_assign_lhs (test_last)
3693 && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
3694 || integer_onep (gimple_phi_arg_def (phi, e->dest_idx))))
3695 continue;
3696 }
3697
3698 return false;
3699 }
3700 }
3701 return true;
3702}
3703
3704/* Return true if BB doesn't have side-effects that would disallow
3705 range test optimization, all SSA_NAMEs set in the bb are consumed
3706 in the bb and there are no PHIs. */
3707
3708static bool
3709no_side_effect_bb (basic_block bb)
3710{
3711 gimple_stmt_iterator gsi;
3712 gimple *last;
3713
3714 if (!gimple_seq_empty_p (phi_nodes (bb)))
3715 return false;
3716 last = last_stmt (bb);
3717 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3718 {
3719 gimple *stmt = gsi_stmt (gsi);
3720 tree lhs;
3721 imm_use_iterator imm_iter;
3722 use_operand_p use_p;
3723
3724 if (is_gimple_debug (stmt))
3725 continue;
3726 if (gimple_has_side_effects (stmt))
3727 return false;
3728 if (stmt == last)
3729 return true;
3730 if (!is_gimple_assign (stmt))
3731 return false;
3732 lhs = gimple_assign_lhs (stmt);
3733 if (TREE_CODE (lhs) != SSA_NAME)
3734 return false;
3735 if (gimple_assign_rhs_could_trap_p (stmt))
3736 return false;
3737 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
3738 {
3739 gimple *use_stmt = USE_STMT (use_p);
3740 if (is_gimple_debug (use_stmt))
3741 continue;
3742 if (gimple_bb (use_stmt) != bb)
3743 return false;
3744 }
3745 }
3746 return false;
3747}
3748
3749/* If VAR is set by CODE (BIT_{AND,IOR}_EXPR) which is reassociable,
3750 return true and fill in *OPS recursively. */
3751
3752static bool
3753get_ops (tree var, enum tree_code code, vec<operand_entry *> *ops,
3754 struct loop *loop)
3755{
3756 gimple *stmt = SSA_NAME_DEF_STMT (var);
3757 tree rhs[2];
3758 int i;
3759
3760 if (!is_reassociable_op (stmt, code, loop))
3761 return false;
3762
3763 rhs[0] = gimple_assign_rhs1 (stmt);
3764 rhs[1] = gimple_assign_rhs2 (stmt);
3765 gimple_set_visited (stmt, true);
3766 for (i = 0; i < 2; i++)
3767 if (TREE_CODE (rhs[i]) == SSA_NAME
3768 && !get_ops (rhs[i], code, ops, loop)
3769 && has_single_use (rhs[i]))
3770 {
3771 operand_entry *oe = operand_entry_pool.allocate ();
3772
3773 oe->op = rhs[i];
3774 oe->rank = code;
3775 oe->id = 0;
3776 oe->count = 1;
3777 oe->stmt_to_insert = NULL;
3778 ops->safe_push (oe);
3779 }
3780 return true;
3781}
3782
3783/* Find the ops that were added by get_ops starting from VAR, see if
3784 they were changed during update_range_test and if yes, create new
3785 stmts. */
3786
3787static tree
3788update_ops (tree var, enum tree_code code, vec<operand_entry *> ops,
3789 unsigned int *pidx, struct loop *loop)
3790{
3791 gimple *stmt = SSA_NAME_DEF_STMT (var);
3792 tree rhs[4];
3793 int i;
3794
3795 if (!is_reassociable_op (stmt, code, loop))
3796 return NULL;
3797
3798 rhs[0] = gimple_assign_rhs1 (stmt);
3799 rhs[1] = gimple_assign_rhs2 (stmt);
3800 rhs[2] = rhs[0];
3801 rhs[3] = rhs[1];
3802 for (i = 0; i < 2; i++)
3803 if (TREE_CODE (rhs[i]) == SSA_NAME)
3804 {
3805 rhs[2 + i] = update_ops (rhs[i], code, ops, pidx, loop);
3806 if (rhs[2 + i] == NULL_TREE)
3807 {
3808 if (has_single_use (rhs[i]))
3809 rhs[2 + i] = ops[(*pidx)++]->op;
3810 else
3811 rhs[2 + i] = rhs[i];
3812 }
3813 }
3814 if ((rhs[2] != rhs[0] || rhs[3] != rhs[1])
3815 && (rhs[2] != rhs[1] || rhs[3] != rhs[0]))
3816 {
3817 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
3818 var = make_ssa_name (TREE_TYPE (var));
3819 gassign *g = gimple_build_assign (var, gimple_assign_rhs_code (stmt),
3820 rhs[2], rhs[3]);
3821 gimple_set_uid (g, gimple_uid (stmt));
3822 gimple_set_visited (g, true);
3823 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3824 }
3825 return var;
3826}
3827
3828/* Structure to track the initial value passed to get_ops and
3829 the range in the ops vector for each basic block. */
3830
3831struct inter_bb_range_test_entry
3832{
3833 tree op;
3834 unsigned int first_idx, last_idx;
3835};
3836
3837/* Inter-bb range test optimization.
3838
3839 Returns TRUE if a gimple conditional is optimized to a true/false,
3840 otherwise return FALSE.
3841
3842 This indicates to the caller that it should run a CFG cleanup pass
3843 once reassociation is completed. */
3844
3845static bool
3846maybe_optimize_range_tests (gimple *stmt)
3847{
3848 basic_block first_bb = gimple_bb (stmt);
3849 basic_block last_bb = first_bb;
3850 basic_block other_bb = NULL;
3851 basic_block bb;
3852 edge_iterator ei;
3853 edge e;
3854 auto_vec<operand_entry *> ops;
3855 auto_vec<inter_bb_range_test_entry> bbinfo;
3856 bool any_changes = false;
3857 bool cfg_cleanup_needed = false;
3858
3859 /* Consider only basic blocks that end with GIMPLE_COND or
3860 a cast statement satisfying final_range_test_p. All
3861 but the last bb in the first_bb .. last_bb range
3862 should end with GIMPLE_COND. */
3863 if (gimple_code (stmt) == GIMPLE_COND)
3864 {
3865 if (EDGE_COUNT (first_bb->succs) != 2)
3866 return cfg_cleanup_needed;
3867 }
3868 else if (final_range_test_p (stmt))
3869 other_bb = single_succ (first_bb);
3870 else
3871 return cfg_cleanup_needed;
3872
3873 if (stmt_could_throw_p (stmt))
3874 return cfg_cleanup_needed;
3875
3876 /* As relative ordering of post-dominator sons isn't fixed,
3877 maybe_optimize_range_tests can be called first on any
3878 bb in the range we want to optimize. So, start searching
3879 backwards, if first_bb can be set to a predecessor. */
3880 while (single_pred_p (first_bb))
3881 {
3882 basic_block pred_bb = single_pred (first_bb);
3883 if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, true))
3884 break;
3885 if (!no_side_effect_bb (first_bb))
3886 break;
3887 first_bb = pred_bb;
3888 }
3889 /* If first_bb is last_bb, other_bb hasn't been computed yet.
3890 Before starting forward search in last_bb successors, find
3891 out the other_bb. */
3892 if (first_bb == last_bb)
3893 {
3894 other_bb = NULL;
3895 /* As non-GIMPLE_COND last stmt always terminates the range,
3896 if forward search didn't discover anything, just give up. */
3897 if (gimple_code (stmt) != GIMPLE_COND)
3898 return cfg_cleanup_needed;
3899 /* Look at both successors. Either it ends with a GIMPLE_COND
3900 and satisfies suitable_cond_bb, or ends with a cast and
3901 other_bb is that cast's successor. */
3902 FOR_EACH_EDGE (e, ei, first_bb->succs)
3903 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
3904 || e->dest == first_bb)
3905 return cfg_cleanup_needed;
3906 else if (single_pred_p (e->dest))
3907 {
3908 stmt = last_stmt (e->dest);
3909 if (stmt
3910 && gimple_code (stmt) == GIMPLE_COND
3911 && EDGE_COUNT (e->dest->succs) == 2)
3912 {
3913 if (suitable_cond_bb (first_bb, e->dest, &other_bb, true))
3914 break;
3915 else
3916 other_bb = NULL;
3917 }
3918 else if (stmt
3919 && final_range_test_p (stmt)
3920 && find_edge (first_bb, single_succ (e->dest)))
3921 {
3922 other_bb = single_succ (e->dest);
3923 if (other_bb == first_bb)
3924 other_bb = NULL;
3925 }
3926 }
3927 if (other_bb == NULL)
3928 return cfg_cleanup_needed;
3929 }
3930 /* Now do the forward search, moving last_bb to successor bbs
3931 that aren't other_bb. */
3932 while (EDGE_COUNT (last_bb->succs) == 2)
3933 {
3934 FOR_EACH_EDGE (e, ei, last_bb->succs)
3935 if (e->dest != other_bb)
3936 break;
3937 if (e == NULL)
3938 break;
3939 if (!single_pred_p (e->dest))
3940 break;
3941 if (!suitable_cond_bb (e->dest, last_bb, &other_bb, false))
3942 break;
3943 if (!no_side_effect_bb (e->dest))
3944 break;
3945 last_bb = e->dest;
3946 }
3947 if (first_bb == last_bb)
3948 return cfg_cleanup_needed;
3949 /* Here basic blocks first_bb through last_bb's predecessor
3950 end with GIMPLE_COND, all of them have one of the edges to
3951 other_bb and another to another block in the range,
3952 all blocks except first_bb don't have side-effects and
3953 last_bb ends with either GIMPLE_COND, or cast satisfying
3954 final_range_test_p. */
3955 for (bb = last_bb; ; bb = single_pred (bb))
3956 {
3957 enum tree_code code;
3958 tree lhs, rhs;
3959 inter_bb_range_test_entry bb_ent;
3960
3961 bb_ent.op = NULL_TREE;
3962 bb_ent.first_idx = ops.length ();
3963 bb_ent.last_idx = bb_ent.first_idx;
3964 e = find_edge (bb, other_bb);
3965 stmt = last_stmt (bb);
3966 gimple_set_visited (stmt, true);
3967 if (gimple_code (stmt) != GIMPLE_COND)
3968 {
3969 use_operand_p use_p;
3970 gimple *phi;
3971 edge e2;
3972 unsigned int d;
3973
3974 lhs = gimple_assign_lhs (stmt);
3975 rhs = gimple_assign_rhs1 (stmt);
3976 gcc_assert (bb == last_bb);
3977
3978 /* stmt is
3979 _123 = (int) _234;
3980 OR
3981 _234 = a_2(D) == 2;
3982
3983 followed by:
3984 <bb M>:
3985 # _345 = PHI <_123(N), 1(...), 1(...)>
3986
3987 or 0 instead of 1. If it is 0, the _234
3988 range test is anded together with all the
3989 other range tests, if it is 1, it is ored with
3990 them. */
3991 single_imm_use (lhs, &use_p, &phi);
3992 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3993 e2 = find_edge (first_bb, other_bb);
3994 d = e2->dest_idx;
3995 gcc_assert (gimple_phi_arg_def (phi, e->dest_idx) == lhs);
3996 if (integer_zerop (gimple_phi_arg_def (phi, d)))
3997 code = BIT_AND_EXPR;
3998 else
3999 {
4000 gcc_checking_assert (integer_onep (gimple_phi_arg_def (phi, d)));
4001 code = BIT_IOR_EXPR;
4002 }
4003
4004 /* If _234 SSA_NAME_DEF_STMT is
4005 _234 = _567 | _789;
4006 (or &, corresponding to 1/0 in the phi arguments,
4007 push into ops the individual range test arguments
4008 of the bitwise or resp. and, recursively. */
4009 if (TREE_CODE (rhs) == SSA_NAME
4010 && (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
4011 != tcc_comparison)
4012 && !get_ops (rhs, code, &ops,
4013 loop_containing_stmt (stmt))
4014 && has_single_use (rhs))
4015 {
4016 /* Otherwise, push the _234 range test itself. */
4017 operand_entry *oe = operand_entry_pool.allocate ();
4018
4019 oe->op = rhs;
4020 oe->rank = code;
4021 oe->id = 0;
4022 oe->count = 1;
4023 oe->stmt_to_insert = NULL;
4024 ops.safe_push (oe);
4025 bb_ent.last_idx++;
4026 bb_ent.op = rhs;
4027 }
4028 else if (is_gimple_assign (stmt)
4029 && (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
4030 == tcc_comparison)
4031 && !get_ops (lhs, code, &ops,
4032 loop_containing_stmt (stmt))
4033 && has_single_use (lhs))
4034 {
4035 operand_entry *oe = operand_entry_pool.allocate ();
4036 oe->op = lhs;
4037 oe->rank = code;
4038 oe->id = 0;
4039 oe->count = 1;
4040 ops.safe_push (oe);
4041 bb_ent.last_idx++;
4042 bb_ent.op = lhs;
4043 }
4044 else
4045 {
4046 bb_ent.last_idx = ops.length ();
4047 bb_ent.op = rhs;
4048 }
4049 bbinfo.safe_push (bb_ent);
4050 continue;
4051 }
4052 /* Otherwise stmt is GIMPLE_COND. */
4053 code = gimple_cond_code (stmt);
4054 lhs = gimple_cond_lhs (stmt);
4055 rhs = gimple_cond_rhs (stmt);
4056 if (TREE_CODE (lhs) == SSA_NAME
4057 && INTEGRAL_TYPE_P (TREE_TYPE</