Branch data Line data Source code
1 : : /* Preamble and helpers for the autogenerated gimple-match.cc file.
2 : : Copyright (C) 2014-2024 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
9 : : version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "backend.h"
24 : : #include "target.h"
25 : : #include "rtl.h"
26 : : #include "tree.h"
27 : : #include "gimple.h"
28 : : #include "ssa.h"
29 : : #include "cgraph.h"
30 : : #include "vec-perm-indices.h"
31 : : #include "fold-const.h"
32 : : #include "fold-const-call.h"
33 : : #include "stor-layout.h"
34 : : #include "gimple-iterator.h"
35 : : #include "gimple-fold.h"
36 : : #include "calls.h"
37 : : #include "tree-dfa.h"
38 : : #include "builtins.h"
39 : : #include "gimple-match.h"
40 : : #include "tree-pass.h"
41 : : #include "internal-fn.h"
42 : : #include "case-cfn-macros.h"
43 : : #include "gimplify.h"
44 : : #include "memmodel.h"
45 : : #include "optabs.h"
46 : : #include "optabs-tree.h"
47 : : #include "tree-eh.h"
48 : : #include "dbgcnt.h"
49 : : #include "tm.h"
50 : : #include "gimple-range.h"
51 : : #include "langhooks.h"
52 : : #include "attribs.h"
53 : : #include "asan.h"
54 : :
55 : : tree do_valueize (tree, tree (*)(tree), bool &);
56 : : tree do_valueize (tree (*)(tree), tree);
57 : :
58 : : /* Helper for the autogenerated code, get at the definition of NAME when
59 : : VALUEIZE allows that. */
60 : :
61 : : inline gimple *
62 : 9308987565 : get_def (tree (*valueize)(tree), tree name)
63 : : {
64 : 9308987565 : if (valueize && ! valueize (name))
65 : : return NULL;
66 : 3934165059 : return SSA_NAME_DEF_STMT (name);
67 : : }
68 : :
69 : : /* Routine to determine if the types T1 and T2 are effectively
70 : : the same for GIMPLE. If T1 or T2 is not a type, the test
71 : : applies to their TREE_TYPE. */
72 : :
73 : : static inline bool
74 : 46473437 : types_match (tree t1, tree t2)
75 : : {
76 : 46473437 : if (!TYPE_P (t1))
77 : 1253617 : t1 = TREE_TYPE (t1);
78 : 46473437 : if (!TYPE_P (t2))
79 : 1848677 : t2 = TREE_TYPE (t2);
80 : :
81 : 46473437 : return types_compatible_p (t1, t2);
82 : : }
83 : :
84 : : /* Routine to determine if the types T1, T2 and T3 are effectively
85 : : the same for GIMPLE. If T1, T2 or T2 is not a type, the test
86 : : applies to their TREE_TYPE. */
87 : :
88 : : static inline bool
89 : 1427 : types_match (tree t1, tree t2, tree t3)
90 : : {
91 : 1427 : return types_match (t1, t2) && types_match (t2, t3);
92 : : }
93 : :
94 : : /* Return if T has a single use. For GIMPLE, we also allow any
95 : : non-SSA_NAME (ie constants) and zero uses to cope with uses
96 : : that aren't linked up yet. */
97 : :
98 : : static bool
99 : : single_use (const_tree) ATTRIBUTE_PURE;
100 : :
101 : : static bool
102 : 9946223 : single_use (const_tree t)
103 : : {
104 : 9946223 : if (TREE_CODE (t) != SSA_NAME)
105 : : return true;
106 : :
107 : : /* Inline return has_zero_uses (t) || has_single_use (t); */
108 : 9946223 : const ssa_use_operand_t *const head = &(SSA_NAME_IMM_USE_NODE (t));
109 : 9946223 : const ssa_use_operand_t *ptr;
110 : 9946223 : bool single = false;
111 : :
112 : 21162360 : for (ptr = head->next; ptr != head; ptr = ptr->next)
113 : 16399695 : if (USE_STMT(ptr) && !is_gimple_debug (USE_STMT (ptr)))
114 : : {
115 : 15116101 : if (single)
116 : : return false;
117 : : single = true;
118 : : }
119 : : return true;
120 : : }
121 : :
122 : : /* Return true if math operations should be canonicalized,
123 : : e.g. sqrt(sqrt(x)) -> pow(x, 0.25). */
124 : :
125 : : static inline bool
126 : 35005 : canonicalize_math_p ()
127 : : {
128 : 35005 : return !cfun || (cfun->curr_properties & PROP_gimple_opt_math) == 0;
129 : : }
130 : :
131 : : /* Return true if math operations that are beneficial only after
132 : : vectorization should be canonicalized. */
133 : :
134 : : static inline bool
135 : 45811 : canonicalize_math_after_vectorization_p ()
136 : : {
137 : 45811 : return !cfun || (cfun->curr_properties & PROP_gimple_lvec) != 0;
138 : : }
139 : :
140 : : /* Return true if we can still perform transformations that may introduce
141 : : vector operations that are not supported by the target. Vector lowering
142 : : normally handles those, but after that pass, it becomes unsafe. */
143 : :
144 : : static inline bool
145 : 4226 : optimize_vectors_before_lowering_p ()
146 : : {
147 : 4226 : return !cfun || (cfun->curr_properties & PROP_gimple_lvec) == 0;
148 : : }
149 : :
150 : : /* Returns true if the expression T has no side effects
151 : : including not trapping. */
152 : : static inline bool
153 : 27 : expr_no_side_effects_p (tree t)
154 : : {
155 : : /* For gimple, there should only be gimple val's here. */
156 : 27 : gcc_assert (is_gimple_val (t));
157 : 27 : return true;
158 : : }
159 : :
160 : : /* Return true if pow(cst, x) should be optimized into exp(log(cst) * x).
161 : : As a workaround for SPEC CPU2017 628.pop2_s, don't do it if arg0
162 : : is an exact integer, arg1 = phi_res +/- cst1 and phi_res = PHI <cst2, ...>
163 : : where cst2 +/- cst1 is an exact integer, because then pow (arg0, arg1)
164 : : will likely be exact, while exp (log (arg0) * arg1) might be not.
165 : : Also don't do it if arg1 is phi_res above and cst2 is an exact integer. */
166 : :
167 : : static bool
168 : 5 : optimize_pow_to_exp (tree arg0, tree arg1)
169 : : {
170 : 5 : gcc_assert (TREE_CODE (arg0) == REAL_CST);
171 : 5 : if (!real_isinteger (TREE_REAL_CST_PTR (arg0), TYPE_MODE (TREE_TYPE (arg0))))
172 : : return true;
173 : :
174 : 5 : if (TREE_CODE (arg1) != SSA_NAME)
175 : : return true;
176 : :
177 : 5 : gimple *def = SSA_NAME_DEF_STMT (arg1);
178 : 5 : gphi *phi = dyn_cast <gphi *> (def);
179 : 5 : tree cst1 = NULL_TREE;
180 : 5 : enum tree_code code = ERROR_MARK;
181 : 5 : if (!phi)
182 : : {
183 : 5 : if (!is_gimple_assign (def))
184 : : return true;
185 : 5 : code = gimple_assign_rhs_code (def);
186 : 5 : switch (code)
187 : : {
188 : 5 : case PLUS_EXPR:
189 : 5 : case MINUS_EXPR:
190 : 5 : break;
191 : : default:
192 : : return true;
193 : : }
194 : 5 : if (TREE_CODE (gimple_assign_rhs1 (def)) != SSA_NAME
195 : 5 : || TREE_CODE (gimple_assign_rhs2 (def)) != REAL_CST)
196 : : return true;
197 : :
198 : 5 : cst1 = gimple_assign_rhs2 (def);
199 : :
200 : 5 : phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def)));
201 : : if (!phi)
202 : : return true;
203 : : }
204 : :
205 : 5 : tree cst2 = NULL_TREE;
206 : 5 : int n = gimple_phi_num_args (phi);
207 : 15 : for (int i = 0; i < n; i++)
208 : : {
209 : 10 : tree arg = PHI_ARG_DEF (phi, i);
210 : 10 : if (TREE_CODE (arg) != REAL_CST)
211 : 5 : continue;
212 : 5 : else if (cst2 == NULL_TREE)
213 : : cst2 = arg;
214 : 0 : else if (!operand_equal_p (cst2, arg, 0))
215 : : return true;
216 : : }
217 : :
218 : 5 : if (cst1 && cst2)
219 : 5 : cst2 = const_binop (code, TREE_TYPE (cst2), cst2, cst1);
220 : 5 : if (cst2
221 : 5 : && TREE_CODE (cst2) == REAL_CST
222 : 10 : && real_isinteger (TREE_REAL_CST_PTR (cst2),
223 : 5 : TYPE_MODE (TREE_TYPE (cst2))))
224 : 5 : return false;
225 : : return true;
226 : : }
227 : :
228 : : /* Return true if a division INNER_DIV / DIVISOR where INNER_DIV
229 : : is another division can be optimized. Don't optimize if INNER_DIV
230 : : is used in a TRUNC_MOD_EXPR with DIVISOR as second operand. */
231 : :
232 : : static bool
233 : 15964 : optimize_successive_divisions_p (tree divisor, tree inner_div)
234 : : {
235 : 28947 : if (!gimple_in_ssa_p (cfun))
236 : : return false;
237 : :
238 : 15964 : imm_use_iterator imm_iter;
239 : 15964 : use_operand_p use_p;
240 : 35553 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, inner_div)
241 : : {
242 : 32572 : gimple *use_stmt = USE_STMT (use_p);
243 : 32572 : if (!is_gimple_assign (use_stmt)
244 : 25910 : || gimple_assign_rhs_code (use_stmt) != TRUNC_MOD_EXPR
245 : 45965 : || !operand_equal_p (gimple_assign_rhs2 (use_stmt), divisor, 0))
246 : 19589 : continue;
247 : : return false;
248 : : }
249 : : return true;
250 : : }
251 : :
252 : : /* Return true if EXPR1 and EXPR2 have the same value, but not necessarily
253 : : same type. The types can differ through nop conversions. */
254 : : #define bitwise_equal_p(expr1, expr2) \
255 : : gimple_bitwise_equal_p (expr1, expr2, valueize)
256 : :
257 : : bool gimple_nop_convert (tree, tree *, tree (*) (tree));
258 : : bool gimple_maybe_truncate (tree, tree *, tree (*) (tree));
259 : :
260 : : /* Helper function for bitwise_equal_p macro. */
261 : :
262 : : static inline bool
263 : 1688790 : gimple_bitwise_equal_p (tree expr1, tree expr2, tree (*valueize) (tree))
264 : : {
265 : 1688790 : if (expr1 == expr2)
266 : : return true;
267 : 1685420 : if (!tree_nop_conversion_p (TREE_TYPE (expr1), TREE_TYPE (expr2)))
268 : : return false;
269 : 1669223 : if (TREE_CODE (expr1) == INTEGER_CST && TREE_CODE (expr2) == INTEGER_CST)
270 : 67 : return wi::to_wide (expr1) == wi::to_wide (expr2);
271 : 1669156 : if (operand_equal_p (expr1, expr2, 0))
272 : : return true;
273 : 1669156 : tree expr3, expr4;
274 : 1669156 : if (!gimple_nop_convert (expr1, &expr3, valueize))
275 : 1660144 : expr3 = expr1;
276 : 1669156 : if (!gimple_nop_convert (expr2, &expr4, valueize))
277 : 1659171 : expr4 = expr2;
278 : 1669156 : if (expr1 != expr3)
279 : : {
280 : 9012 : if (operand_equal_p (expr3, expr2, 0))
281 : : return true;
282 : 8774 : if (expr2 != expr4 && operand_equal_p (expr3, expr4, 0))
283 : : return true;
284 : : }
285 : 1668904 : if (expr2 != expr4 && operand_equal_p (expr1, expr4, 0))
286 : : return true;
287 : 1668334 : if (gimple_maybe_truncate (expr3, &expr3, valueize)
288 : 9413 : && gimple_maybe_truncate (expr4, &expr4, valueize)
289 : 1672536 : && operand_equal_p (expr3, expr4, 0))
290 : : return true;
291 : : return false;
292 : : }
293 : :
294 : : /* Return true if EXPR1 and EXPR2 have the bitwise opposite value,
295 : : but not necessarily same type.
296 : : The types can differ through nop conversions. */
297 : : #define bitwise_inverted_equal_p(expr1, expr2, wascmp) \
298 : : gimple_bitwise_inverted_equal_p (expr1, expr2, wascmp, valueize)
299 : :
300 : :
301 : : bool gimple_bit_not_with_nop (tree, tree *, tree (*) (tree));
302 : : bool gimple_maybe_cmp (tree, tree *, tree (*) (tree));
303 : : bool gimple_bit_xor_cst (tree, tree *, tree (*) (tree));
304 : :
305 : : /* Helper function for bitwise_inverted_equal_p macro. */
306 : :
307 : : static inline bool
308 : 16751577 : gimple_bitwise_inverted_equal_p (tree expr1, tree expr2, bool &wascmp, tree (*valueize) (tree))
309 : : {
310 : 16751577 : wascmp = false;
311 : 16751577 : if (expr1 == expr2)
312 : : return false;
313 : 16725584 : if (!tree_nop_conversion_p (TREE_TYPE (expr1), TREE_TYPE (expr2)))
314 : : return false;
315 : 16725584 : tree cst1 = uniform_integer_cst_p (expr1);
316 : 16725584 : tree cst2 = uniform_integer_cst_p (expr2);
317 : 16725584 : if (cst1 && cst2)
318 : 298616 : return wi::to_wide (cst1) == ~wi::to_wide (cst2);
319 : 16426968 : if (operand_equal_p (expr1, expr2, 0))
320 : : return false;
321 : :
322 : 16426968 : tree xor1[2];
323 : 16426968 : tree xor2[2];
324 : : /* `X ^ CST` and `X ^ ~CST` match for ~. */
325 : 16426968 : if (gimple_bit_xor_cst (expr1, xor1, valueize)
326 : 16426968 : && gimple_bit_xor_cst (expr2, xor2, valueize))
327 : : {
328 : 343 : if (operand_equal_p (xor1[0], xor2[0], 0)
329 : 385 : && (wi::to_wide (uniform_integer_cst_p (xor1[1]))
330 : 385 : == ~wi::to_wide (uniform_integer_cst_p (xor2[1]))))
331 : : return true;
332 : : }
333 : :
334 : 16426967 : tree other;
335 : : /* Try if EXPR1 was defined as ~EXPR2. */
336 : 16426967 : if (gimple_bit_not_with_nop (expr1, &other, valueize))
337 : : {
338 : 278524 : if (gimple_bitwise_equal_p (other, expr2, valueize))
339 : : return true;
340 : : }
341 : : /* Try if EXPR2 was defined as ~EXPR1. */
342 : 16426020 : if (gimple_bit_not_with_nop (expr2, &other, valueize))
343 : : {
344 : 613872 : if (gimple_bitwise_equal_p (other, expr1, valueize))
345 : : return true;
346 : : }
347 : :
348 : : /* If neither are defined by BIT_NOT, try to see if
349 : : both are defined by comparisons and see if they are
350 : : complementary (inversion) of each other. */
351 : 16424415 : tree newexpr1, newexpr2;
352 : 16424415 : if (!gimple_maybe_cmp (expr1, &newexpr1, valueize))
353 : : return false;
354 : 6009041 : if (!gimple_maybe_cmp (expr2, &newexpr2, valueize))
355 : : return false;
356 : :
357 : 5722058 : gimple *d1 = get_def (valueize, newexpr1);
358 : 5722058 : gassign *a1 = dyn_cast <gassign *> (d1);
359 : 5722058 : gimple *d2 = get_def (valueize, newexpr2);
360 : 5722058 : gassign *a2 = dyn_cast <gassign *> (d2);
361 : 5722058 : tree op10 = do_valueize (valueize, gimple_assign_rhs1 (a1));
362 : 5722058 : tree op20 = do_valueize (valueize, gimple_assign_rhs1 (a2));
363 : 5722058 : if (!operand_equal_p (op10, op20))
364 : : return false;
365 : 3346668 : tree op11 = do_valueize (valueize, gimple_assign_rhs2 (a1));
366 : 3346668 : tree op21 = do_valueize (valueize, gimple_assign_rhs2 (a2));
367 : 1673334 : if (!operand_equal_p (op11, op21))
368 : : return false;
369 : 38606 : wascmp = true;
370 : 38606 : tree_code ac1 = gimple_assign_rhs_code (a1);
371 : 38606 : tree_code ac2 = gimple_assign_rhs_code (a2);
372 : : /* Match `^` against `==` but this should only
373 : : happen when the type is a 1bit precision integer. */
374 : 38606 : if (ac1 == BIT_XOR_EXPR)
375 : : {
376 : 1 : tree type = TREE_TYPE (newexpr1);
377 : 1 : gcc_assert (INTEGRAL_TYPE_P (type) && TYPE_PRECISION (type) == 1);
378 : 1 : return ac2 == EQ_EXPR;
379 : : }
380 : 38605 : if (ac2 == BIT_XOR_EXPR)
381 : : {
382 : 0 : tree type = TREE_TYPE (newexpr1);
383 : 0 : gcc_assert (INTEGRAL_TYPE_P (type) && TYPE_PRECISION (type) == 1);
384 : 0 : return ac1 == EQ_EXPR;
385 : : }
386 : 38605 : if (invert_tree_comparison (ac1, HONOR_NANS (op10)) == ac2)
387 : : return true;
388 : : return false;
389 : : }
390 : :
391 : : /*
392 : : * Return the relevant gcond * of the given phi, as well as the true
393 : : * and false TREE args of the phi. Or return nullptr.
394 : : *
395 : : * If matched the gcond *, the output argument TREE true_arg and false_arg
396 : : * will be updated to the relevant args of phi.
397 : : *
398 : : * If failed to match, nullptr gcond * will be returned, as well as the output
399 : : * arguments will be set to NULL_TREE.
400 : : */
401 : :
402 : : static inline gcond *
403 : 16740965 : match_cond_with_binary_phi (gphi *phi, tree *true_arg, tree *false_arg)
404 : : {
405 : 16740965 : *true_arg = *false_arg = NULL_TREE;
406 : :
407 : 16740965 : if (gimple_phi_num_args (phi) != 2)
408 : : return nullptr;
409 : :
410 : 16740965 : basic_block pred_b0 = EDGE_PRED (gimple_bb (phi), 0)->src;
411 : 16740965 : basic_block pred_b1 = EDGE_PRED (gimple_bb (phi), 1)->src;
412 : 16740965 : edge edge_for_pred_0 = nullptr;
413 : :
414 : 16740965 : if (EDGE_COUNT (pred_b0->succs) == 2
415 : 10099535 : && EDGE_COUNT (pred_b1->succs) == 1
416 : 6214265 : && EDGE_COUNT (pred_b1->preds) == 1
417 : 21611025 : && pred_b0 == EDGE_PRED (pred_b1, 0)->src)
418 : : /*
419 : : * +------+
420 : : * | b0: |
421 : : * | def | +-----+
422 : : * | ... | | b1: |
423 : : * | cond |------>| def |
424 : : * +------+ | ... |
425 : : * | +-----+
426 : : * # |
427 : : * | |
428 : : * v |
429 : : * +-----+ |
430 : : * | b2: | |
431 : : * | def |<----------+
432 : : * +-----+
433 : : * #: edge_for_pred_0.
434 : : */
435 : : edge_for_pred_0 = EDGE_PRED (gimple_bb (phi), 0);
436 : 14973240 : else if (EDGE_COUNT (pred_b1->succs) == 2
437 : 6525710 : && EDGE_COUNT (pred_b0->succs) == 1
438 : 2641130 : && EDGE_COUNT (pred_b0->preds) == 1
439 : 16858375 : && pred_b1 == EDGE_PRED (pred_b0, 0)->src)
440 : : /*
441 : : * +------+
442 : : * | b1: |
443 : : * +-----+ | def |
444 : : * | b0: | | ... |
445 : : * | def |<---#---| cond |
446 : : * | ... | +------+
447 : : * +-----+ |
448 : : * | |
449 : : * | |
450 : : * | |
451 : : * v |
452 : : * +-----+ |
453 : : * | b2: | |
454 : : * | def |<----------+
455 : : * +-----+
456 : : * #: edge_for_pred_0.
457 : : */
458 : : edge_for_pred_0 = EDGE_PRED (pred_b0, 0);
459 : 14440475 : else if (EDGE_COUNT (pred_b0->succs) == 1
460 : 6058725 : && EDGE_COUNT (pred_b1->succs) == 1
461 : 3939955 : && EDGE_COUNT (pred_b0->preds) == 1
462 : 2839720 : && EDGE_COUNT (pred_b1->preds) == 1
463 : 2051755 : && EDGE_COUNT (EDGE_PRED (pred_b0, 0)->src->succs) == 2
464 : 16400655 : && EDGE_PRED (pred_b0, 0)->src == EDGE_PRED (pred_b1, 0)->src)
465 : : /* +------+
466 : : * | b0: |
467 : : * | ... | +-----+
468 : : * | cond |------>| b2: |
469 : : * +------+ | ... |
470 : : * | +-----+
471 : : * # |
472 : : * | |
473 : : * v |
474 : : * +-----+ |
475 : : * | b1: | |
476 : : * | ... | |
477 : : * +-----+ |
478 : : * | |
479 : : * | |
480 : : * v |
481 : : * +-----+ |
482 : : * | b3: |<----------+
483 : : * | ... |
484 : : * +-----+
485 : : * #: edge_for_pred_0.
486 : : */
487 : : edge_for_pred_0 = EDGE_PRED (pred_b0, 0);
488 : :
489 : 3414675 : if (!edge_for_pred_0)
490 : : return nullptr;
491 : :
492 : 20162580 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (edge_for_pred_0->src));
493 : :
494 : 3407735 : if (!cond)
495 : : return nullptr;
496 : :
497 : 3407735 : if (edge_for_pred_0->flags & EDGE_TRUE_VALUE)
498 : : {
499 : 1949808 : *true_arg = gimple_phi_arg_def (phi, 0);
500 : 1949808 : *false_arg = gimple_phi_arg_def (phi, 1);
501 : : }
502 : : else /* Aka edge_for_pred_0->flags & EDGE_FALSE_VALUE */
503 : : {
504 : 1457927 : *false_arg = gimple_phi_arg_def (phi, 0);
505 : 1457927 : *true_arg = gimple_phi_arg_def (phi, 1);
506 : : }
507 : :
508 : : return cond;
509 : : }
|