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 "optabs-tree.h"
45 : : #include "tree-eh.h"
46 : : #include "dbgcnt.h"
47 : : #include "tm.h"
48 : : #include "gimple-range.h"
49 : : #include "langhooks.h"
50 : : #include "attribs.h"
51 : : #include "asan.h"
52 : :
53 : : tree do_valueize (tree, tree (*)(tree), bool &);
54 : : tree do_valueize (tree (*)(tree), tree);
55 : :
56 : : /* Helper for the autogenerated code, get at the definition of NAME when
57 : : VALUEIZE allows that. */
58 : :
59 : : inline gimple *
60 : 9290599523 : get_def (tree (*valueize)(tree), tree name)
61 : : {
62 : 9290599523 : if (valueize && ! valueize (name))
63 : : return NULL;
64 : 3875922876 : return SSA_NAME_DEF_STMT (name);
65 : : }
66 : :
67 : : /* Routine to determine if the types T1 and T2 are effectively
68 : : the same for GIMPLE. If T1 or T2 is not a type, the test
69 : : applies to their TREE_TYPE. */
70 : :
71 : : static inline bool
72 : 44525737 : types_match (tree t1, tree t2)
73 : : {
74 : 44525737 : if (!TYPE_P (t1))
75 : 1234832 : t1 = TREE_TYPE (t1);
76 : 44525737 : if (!TYPE_P (t2))
77 : 1812696 : t2 = TREE_TYPE (t2);
78 : :
79 : 44525737 : return types_compatible_p (t1, t2);
80 : : }
81 : :
82 : : /* Routine to determine if the types T1, T2 and T3 are effectively
83 : : the same for GIMPLE. If T1, T2 or T2 is not a type, the test
84 : : applies to their TREE_TYPE. */
85 : :
86 : : static inline bool
87 : 27423 : types_match (tree t1, tree t2, tree t3)
88 : : {
89 : 27423 : return types_match (t1, t2) && types_match (t2, t3);
90 : : }
91 : :
92 : : /* Return if T has a single use. For GIMPLE, we also allow any
93 : : non-SSA_NAME (ie constants) and zero uses to cope with uses
94 : : that aren't linked up yet. */
95 : :
96 : : static bool
97 : : single_use (const_tree) ATTRIBUTE_PURE;
98 : :
99 : : static bool
100 : 9768806 : single_use (const_tree t)
101 : : {
102 : 9768806 : if (TREE_CODE (t) != SSA_NAME)
103 : : return true;
104 : :
105 : : /* Inline return has_zero_uses (t) || has_single_use (t); */
106 : 9768806 : const ssa_use_operand_t *const head = &(SSA_NAME_IMM_USE_NODE (t));
107 : 9768806 : const ssa_use_operand_t *ptr;
108 : 9768806 : bool single = false;
109 : :
110 : 20818224 : for (ptr = head->next; ptr != head; ptr = ptr->next)
111 : 16154823 : if (USE_STMT(ptr) && !is_gimple_debug (USE_STMT (ptr)))
112 : : {
113 : 14858203 : if (single)
114 : : return false;
115 : : single = true;
116 : : }
117 : : return true;
118 : : }
119 : :
120 : : /* Return true if math operations should be canonicalized,
121 : : e.g. sqrt(sqrt(x)) -> pow(x, 0.25). */
122 : :
123 : : static inline bool
124 : 34504 : canonicalize_math_p ()
125 : : {
126 : 34504 : return !cfun || (cfun->curr_properties & PROP_gimple_opt_math) == 0;
127 : : }
128 : :
129 : : /* Return true if math operations that are beneficial only after
130 : : vectorization should be canonicalized. */
131 : :
132 : : static inline bool
133 : 45307 : canonicalize_math_after_vectorization_p ()
134 : : {
135 : 45307 : return !cfun || (cfun->curr_properties & PROP_gimple_lvec) != 0;
136 : : }
137 : :
138 : : /* Return true if we can still perform transformations that may introduce
139 : : vector operations that are not supported by the target. Vector lowering
140 : : normally handles those, but after that pass, it becomes unsafe. */
141 : :
142 : : static inline bool
143 : 4039 : optimize_vectors_before_lowering_p ()
144 : : {
145 : 4039 : return !cfun || (cfun->curr_properties & PROP_gimple_lvec) == 0;
146 : : }
147 : :
148 : : /* Returns true if the expression T has no side effects
149 : : including not trapping. */
150 : : static inline bool
151 : 27 : expr_no_side_effects_p (tree t)
152 : : {
153 : : /* For gimple, there should only be gimple val's here. */
154 : 27 : gcc_assert (is_gimple_val (t));
155 : 27 : return true;
156 : : }
157 : :
158 : : /* Return true if pow(cst, x) should be optimized into exp(log(cst) * x).
159 : : As a workaround for SPEC CPU2017 628.pop2_s, don't do it if arg0
160 : : is an exact integer, arg1 = phi_res +/- cst1 and phi_res = PHI <cst2, ...>
161 : : where cst2 +/- cst1 is an exact integer, because then pow (arg0, arg1)
162 : : will likely be exact, while exp (log (arg0) * arg1) might be not.
163 : : Also don't do it if arg1 is phi_res above and cst2 is an exact integer. */
164 : :
165 : : static bool
166 : 5 : optimize_pow_to_exp (tree arg0, tree arg1)
167 : : {
168 : 5 : gcc_assert (TREE_CODE (arg0) == REAL_CST);
169 : 5 : if (!real_isinteger (TREE_REAL_CST_PTR (arg0), TYPE_MODE (TREE_TYPE (arg0))))
170 : : return true;
171 : :
172 : 5 : if (TREE_CODE (arg1) != SSA_NAME)
173 : : return true;
174 : :
175 : 5 : gimple *def = SSA_NAME_DEF_STMT (arg1);
176 : 5 : gphi *phi = dyn_cast <gphi *> (def);
177 : 5 : tree cst1 = NULL_TREE;
178 : 5 : enum tree_code code = ERROR_MARK;
179 : 5 : if (!phi)
180 : : {
181 : 5 : if (!is_gimple_assign (def))
182 : : return true;
183 : 5 : code = gimple_assign_rhs_code (def);
184 : 5 : switch (code)
185 : : {
186 : 5 : case PLUS_EXPR:
187 : 5 : case MINUS_EXPR:
188 : 5 : break;
189 : : default:
190 : : return true;
191 : : }
192 : 5 : if (TREE_CODE (gimple_assign_rhs1 (def)) != SSA_NAME
193 : 5 : || TREE_CODE (gimple_assign_rhs2 (def)) != REAL_CST)
194 : : return true;
195 : :
196 : 5 : cst1 = gimple_assign_rhs2 (def);
197 : :
198 : 5 : phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def)));
199 : : if (!phi)
200 : : return true;
201 : : }
202 : :
203 : 5 : tree cst2 = NULL_TREE;
204 : 5 : int n = gimple_phi_num_args (phi);
205 : 15 : for (int i = 0; i < n; i++)
206 : : {
207 : 10 : tree arg = PHI_ARG_DEF (phi, i);
208 : 10 : if (TREE_CODE (arg) != REAL_CST)
209 : 5 : continue;
210 : 5 : else if (cst2 == NULL_TREE)
211 : : cst2 = arg;
212 : 0 : else if (!operand_equal_p (cst2, arg, 0))
213 : : return true;
214 : : }
215 : :
216 : 5 : if (cst1 && cst2)
217 : 5 : cst2 = const_binop (code, TREE_TYPE (cst2), cst2, cst1);
218 : 5 : if (cst2
219 : 5 : && TREE_CODE (cst2) == REAL_CST
220 : 10 : && real_isinteger (TREE_REAL_CST_PTR (cst2),
221 : 5 : TYPE_MODE (TREE_TYPE (cst2))))
222 : 5 : return false;
223 : : return true;
224 : : }
225 : :
226 : : /* Return true if a division INNER_DIV / DIVISOR where INNER_DIV
227 : : is another division can be optimized. Don't optimize if INNER_DIV
228 : : is used in a TRUNC_MOD_EXPR with DIVISOR as second operand. */
229 : :
230 : : static bool
231 : 16067 : optimize_successive_divisions_p (tree divisor, tree inner_div)
232 : : {
233 : 29048 : if (!gimple_in_ssa_p (cfun))
234 : : return false;
235 : :
236 : 16067 : imm_use_iterator imm_iter;
237 : 16067 : use_operand_p use_p;
238 : 36806 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, inner_div)
239 : : {
240 : 33720 : gimple *use_stmt = USE_STMT (use_p);
241 : 33720 : if (!is_gimple_assign (use_stmt)
242 : 26272 : || gimple_assign_rhs_code (use_stmt) != TRUNC_MOD_EXPR
243 : 47111 : || !operand_equal_p (gimple_assign_rhs2 (use_stmt), divisor, 0))
244 : 20739 : continue;
245 : : return false;
246 : : }
247 : : return true;
248 : : }
249 : :
250 : : /* Return true if EXPR1 and EXPR2 have the same value, but not necessarily
251 : : same type. The types can differ through nop conversions. */
252 : : #define bitwise_equal_p(expr1, expr2) \
253 : : gimple_bitwise_equal_p (expr1, expr2, valueize)
254 : :
255 : : bool gimple_nop_convert (tree, tree *, tree (*) (tree));
256 : : bool gimple_maybe_truncate (tree, tree *, tree (*) (tree));
257 : :
258 : : /* Helper function for bitwise_equal_p macro. */
259 : :
260 : : static inline bool
261 : 1577779 : gimple_bitwise_equal_p (tree expr1, tree expr2, tree (*valueize) (tree))
262 : : {
263 : 1577779 : if (expr1 == expr2)
264 : : return true;
265 : 1574431 : if (!tree_nop_conversion_p (TREE_TYPE (expr1), TREE_TYPE (expr2)))
266 : : return false;
267 : 1560365 : if (TREE_CODE (expr1) == INTEGER_CST && TREE_CODE (expr2) == INTEGER_CST)
268 : 67 : return wi::to_wide (expr1) == wi::to_wide (expr2);
269 : 1560298 : if (operand_equal_p (expr1, expr2, 0))
270 : : return true;
271 : 1560298 : tree expr3, expr4;
272 : 1560298 : if (!gimple_nop_convert (expr1, &expr3, valueize))
273 : 1551642 : expr3 = expr1;
274 : 1560298 : if (!gimple_nop_convert (expr2, &expr4, valueize))
275 : 1551084 : expr4 = expr2;
276 : 1560298 : if (expr1 != expr3)
277 : : {
278 : 8656 : if (operand_equal_p (expr3, expr2, 0))
279 : : return true;
280 : 8426 : if (expr2 != expr4 && operand_equal_p (expr3, expr4, 0))
281 : : return true;
282 : : }
283 : 1560054 : if (expr2 != expr4 && operand_equal_p (expr1, expr4, 0))
284 : : return true;
285 : 1559599 : if (gimple_maybe_truncate (expr3, &expr3, valueize)
286 : 8701 : && gimple_maybe_truncate (expr4, &expr4, valueize)
287 : 1563179 : && operand_equal_p (expr3, expr4, 0))
288 : : return true;
289 : : return false;
290 : : }
291 : :
292 : : /* Return true if EXPR1 and EXPR2 have the bitwise opposite value,
293 : : but not necessarily same type.
294 : : The types can differ through nop conversions. */
295 : : #define bitwise_inverted_equal_p(expr1, expr2, wascmp) \
296 : : gimple_bitwise_inverted_equal_p (expr1, expr2, wascmp, valueize)
297 : :
298 : :
299 : : bool gimple_bit_not_with_nop (tree, tree *, tree (*) (tree));
300 : : bool gimple_maybe_cmp (tree, tree *, tree (*) (tree));
301 : : bool gimple_bit_xor_cst (tree, tree *, tree (*) (tree));
302 : :
303 : : /* Helper function for bitwise_inverted_equal_p macro. */
304 : :
305 : : static inline bool
306 : 15827265 : gimple_bitwise_inverted_equal_p (tree expr1, tree expr2, bool &wascmp, tree (*valueize) (tree))
307 : : {
308 : 15827265 : wascmp = false;
309 : 15827265 : if (expr1 == expr2)
310 : : return false;
311 : 15801572 : if (!tree_nop_conversion_p (TREE_TYPE (expr1), TREE_TYPE (expr2)))
312 : : return false;
313 : 15801572 : tree cst1 = uniform_integer_cst_p (expr1);
314 : 15801572 : tree cst2 = uniform_integer_cst_p (expr2);
315 : 15801572 : if (cst1 && cst2)
316 : 292088 : return wi::to_wide (cst1) == ~wi::to_wide (cst2);
317 : 15509484 : if (operand_equal_p (expr1, expr2, 0))
318 : : return false;
319 : :
320 : 15509484 : tree xor1[2];
321 : 15509484 : tree xor2[2];
322 : : /* `X ^ CST` and `X ^ ~CST` match for ~. */
323 : 15509484 : if (gimple_bit_xor_cst (expr1, xor1, valueize)
324 : 15509484 : && gimple_bit_xor_cst (expr2, xor2, valueize))
325 : : {
326 : 343 : if (operand_equal_p (xor1[0], xor2[0], 0)
327 : 385 : && (wi::to_wide (uniform_integer_cst_p (xor1[1]))
328 : 385 : == ~wi::to_wide (uniform_integer_cst_p (xor2[1]))))
329 : : return true;
330 : : }
331 : :
332 : 15509483 : tree other;
333 : : /* Try if EXPR1 was defined as ~EXPR2. */
334 : 15509483 : if (gimple_bit_not_with_nop (expr1, &other, valueize))
335 : : {
336 : 277519 : if (gimple_bitwise_equal_p (other, expr2, valueize))
337 : : return true;
338 : : }
339 : : /* Try if EXPR2 was defined as ~EXPR1. */
340 : 15508537 : if (gimple_bit_not_with_nop (expr2, &other, valueize))
341 : : {
342 : 604867 : if (gimple_bitwise_equal_p (other, expr1, valueize))
343 : : return true;
344 : : }
345 : :
346 : : /* If neither are defined by BIT_NOT, try to see if
347 : : both are defined by comparisons and see if they are
348 : : complementary (inversion) of each other. */
349 : 15506947 : tree newexpr1, newexpr2;
350 : 15506947 : if (!gimple_maybe_cmp (expr1, &newexpr1, valueize))
351 : : return false;
352 : 5417007 : if (!gimple_maybe_cmp (expr2, &newexpr2, valueize))
353 : : return false;
354 : :
355 : 5134621 : gimple *d1 = get_def (valueize, newexpr1);
356 : 5134621 : gassign *a1 = dyn_cast <gassign *> (d1);
357 : 5134621 : gimple *d2 = get_def (valueize, newexpr2);
358 : 5134621 : gassign *a2 = dyn_cast <gassign *> (d2);
359 : 5134621 : tree op10 = do_valueize (valueize, gimple_assign_rhs1 (a1));
360 : 5134621 : tree op20 = do_valueize (valueize, gimple_assign_rhs1 (a2));
361 : 5134621 : if (!operand_equal_p (op10, op20))
362 : : return false;
363 : 3266334 : tree op11 = do_valueize (valueize, gimple_assign_rhs2 (a1));
364 : 3266334 : tree op21 = do_valueize (valueize, gimple_assign_rhs2 (a2));
365 : 1633167 : if (!operand_equal_p (op11, op21))
366 : : return false;
367 : 35533 : wascmp = true;
368 : 35533 : tree_code ac1 = gimple_assign_rhs_code (a1);
369 : 35533 : tree_code ac2 = gimple_assign_rhs_code (a2);
370 : : /* Match `^` against `==` but this should only
371 : : happen when the type is a 1bit precision integer. */
372 : 35533 : if (ac1 == BIT_XOR_EXPR)
373 : : {
374 : 1 : tree type = TREE_TYPE (newexpr1);
375 : 1 : gcc_assert (INTEGRAL_TYPE_P (type) && TYPE_PRECISION (type) == 1);
376 : 1 : return ac2 == EQ_EXPR;
377 : : }
378 : 35532 : if (ac2 == BIT_XOR_EXPR)
379 : : {
380 : 0 : tree type = TREE_TYPE (newexpr1);
381 : 0 : gcc_assert (INTEGRAL_TYPE_P (type) && TYPE_PRECISION (type) == 1);
382 : 0 : return ac1 == EQ_EXPR;
383 : : }
384 : 35532 : if (invert_tree_comparison (ac1, HONOR_NANS (op10)) == ac2)
385 : : return true;
386 : : return false;
387 : : }
388 : :
389 : : /*
390 : : * Return the relevant gcond * of the given phi, as well as the true
391 : : * and false TREE args of the phi. Or return nullptr.
392 : : *
393 : : * If matched the gcond *, the output argument TREE true_arg and false_arg
394 : : * will be updated to the relevant args of phi.
395 : : *
396 : : * If failed to match, nullptr gcond * will be returned, as well as the output
397 : : * arguments will be set to NULL_TREE.
398 : : */
399 : :
400 : : static inline gcond *
401 : 9654197 : match_cond_with_binary_phi (gphi *phi, tree *true_arg, tree *false_arg)
402 : : {
403 : 9654197 : *true_arg = *false_arg = NULL_TREE;
404 : :
405 : 9654197 : if (gimple_phi_num_args (phi) != 2)
406 : : return nullptr;
407 : :
408 : 9654197 : basic_block pred_b0 = EDGE_PRED (gimple_bb (phi), 0)->src;
409 : 9654197 : basic_block pred_b1 = EDGE_PRED (gimple_bb (phi), 1)->src;
410 : 9654197 : edge edge_for_pred_0 = nullptr;
411 : :
412 : 9654197 : if (EDGE_COUNT (pred_b0->succs) == 2
413 : 5880167 : && EDGE_COUNT (pred_b1->succs) == 1
414 : 3657053 : && EDGE_COUNT (pred_b1->preds) == 1
415 : 12532384 : && pred_b0 == EDGE_PRED (pred_b1, 0)->src)
416 : : /*
417 : : * +------+
418 : : * | b0: |
419 : : * | def | +-----+
420 : : * | ... | | b1: |
421 : : * | cond |------>| def |
422 : : * +------+ | ... |
423 : : * | +-----+
424 : : * # |
425 : : * | |
426 : : * v |
427 : : * +-----+ |
428 : : * | b2: | |
429 : : * | def |<----------+
430 : : * +-----+
431 : : * #: edge_for_pred_0.
432 : : */
433 : : edge_for_pred_0 = EDGE_PRED (gimple_bb (phi), 0);
434 : 8590716 : else if (EDGE_COUNT (pred_b1->succs) == 2
435 : 3686832 : && EDGE_COUNT (pred_b0->succs) == 1
436 : 1464006 : && EDGE_COUNT (pred_b0->preds) == 1
437 : 9658083 : && pred_b1 == EDGE_PRED (pred_b0, 0)->src)
438 : : /*
439 : : * +------+
440 : : * | b1: |
441 : : * +-----+ | def |
442 : : * | b0: | | ... |
443 : : * | def |<---#---| cond |
444 : : * | ... | +------+
445 : : * +-----+ |
446 : : * | |
447 : : * | |
448 : : * | |
449 : : * v |
450 : : * +-----+ |
451 : : * | b2: | |
452 : : * | def |<----------+
453 : : * +-----+
454 : : * #: edge_for_pred_0.
455 : : */
456 : : edge_for_pred_0 = EDGE_PRED (pred_b0, 0);
457 : 8286243 : else if (EDGE_COUNT (pred_b0->succs) == 1
458 : 3440331 : && EDGE_COUNT (pred_b1->succs) == 1
459 : 2274753 : && EDGE_COUNT (pred_b0->preds) == 1
460 : 1659357 : && EDGE_COUNT (pred_b1->preds) == 1
461 : 1196592 : && EDGE_COUNT (EDGE_PRED (pred_b0, 0)->src->succs) == 2
462 : 9427455 : && EDGE_PRED (pred_b0, 0)->src == EDGE_PRED (pred_b1, 0)->src)
463 : : /* +------+
464 : : * | b0: |
465 : : * | ... | +-----+
466 : : * | cond |------>| b2: |
467 : : * +------+ | ... |
468 : : * | +-----+
469 : : * # |
470 : : * | |
471 : : * v |
472 : : * +-----+ |
473 : : * | b1: | |
474 : : * | ... | |
475 : : * +-----+ |
476 : : * | |
477 : : * | |
478 : : * v |
479 : : * +-----+ |
480 : : * | b3: |<----------+
481 : : * | ... |
482 : : * +-----+
483 : : * #: edge_for_pred_0.
484 : : */
485 : : edge_for_pred_0 = EDGE_PRED (pred_b0, 0);
486 : :
487 : 2005304 : if (!edge_for_pred_0)
488 : : return nullptr;
489 : :
490 : 11663794 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (edge_for_pred_0->src));
491 : :
492 : 2001011 : if (!cond)
493 : : return nullptr;
494 : :
495 : 2001011 : if (edge_for_pred_0->flags & EDGE_TRUE_VALUE)
496 : : {
497 : 1177755 : *true_arg = gimple_phi_arg_def (phi, 0);
498 : 1177755 : *false_arg = gimple_phi_arg_def (phi, 1);
499 : : }
500 : : else /* Aka edge_for_pred_0->flags & EDGE_FALSE_VALUE */
501 : : {
502 : 823256 : *false_arg = gimple_phi_arg_def (phi, 0);
503 : 823256 : *true_arg = gimple_phi_arg_def (phi, 1);
504 : : }
505 : :
506 : : return cond;
507 : : }
|