gcc/gimple-isel.cc

   1 /* Schedule GIMPLE vector statements.
   2    Copyright (C) 2020-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
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY 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 "rtl.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "tree-pass.h"
  28 #include "ssa.h"
  29 #include "expmed.h"
  30 #include "optabs-tree.h"
  31 #include "tree-eh.h"
  32 #include "gimple-iterator.h"
  33 #include "gimplify-me.h"
  34 #include "gimplify.h"
  35 #include "tree-cfg.h"
  36 #include "bitmap.h"
  37 #include "tree-ssa-dce.h"
  38 #include "memmodel.h"
  39 #include "optabs.h"
  40 #include "gimple-fold.h"
  41 #include "internal-fn.h"
  42
  43 /* Expand all ARRAY_REF(VIEW_CONVERT_EXPR) gimple assignments into calls to
  44    internal function based on vector type of selected expansion.
  45
  46    For vec_set:
  47
  48      VIEW_CONVERT_EXPR<int[4]>(u)[_1] = i_4(D);
  49    =>
  50      _7 = u;
  51      _8 = .VEC_SET (_7, i_4(D), _1);
  52      u = _8;
  53
  54    For vec_extract:
  55
  56       _3 = VIEW_CONVERT_EXPR<intD.1[4]>(vD.2208)[idx_2(D)];
  57    =>
  58       _4 = vD.2208;
  59       _3 = .VEC_EXTRACT (_4, idx_2(D));  */
  60
  61 static bool
  62 gimple_expand_vec_set_extract_expr (struct function *fun,
  63                                     gimple_stmt_iterator *gsi)
  64 {
  65   gcall *new_stmt = NULL;
  66   gassign *ass_stmt = NULL;
  67   bool cfg_changed = false;
  68
  69   /* Only consider code == GIMPLE_ASSIGN.  */
  70   gassign *stmt = dyn_cast<gassign *> (gsi_stmt (*gsi));
  71   if (!stmt)
  72     return false;
  73
  74   bool is_extract = false;
  75
  76   tree lhs = gimple_assign_lhs (stmt);
  77   tree rhs = gimple_assign_rhs1 (stmt);
  78   tree val, ref;
  79   if (TREE_CODE (lhs) == ARRAY_REF)
  80     {
  81       /* Assume it is a vec_set.  */
  82       val = rhs;
  83       ref = lhs;
  84     }
  85   else if (TREE_CODE (rhs) == ARRAY_REF)
  86     {
  87       /* vec_extract.  */
  88       is_extract = true;
  89       val = lhs;
  90       ref = rhs;
  91     }
  92   else
  93     return false;
  94
  95   tree op0 = TREE_OPERAND (ref, 0);
  96   if (TREE_CODE (op0) == VIEW_CONVERT_EXPR && DECL_P (TREE_OPERAND (op0, 0))
  97       && VECTOR_TYPE_P (TREE_TYPE (TREE_OPERAND (op0, 0)))
  98       && TYPE_MODE (TREE_TYPE (ref))
  99            == TYPE_MODE (TREE_TYPE (TREE_TYPE (TREE_OPERAND (op0, 0)))))
 100     {
 101       tree pos = TREE_OPERAND (ref, 1);
 102
 103       tree view_op0 = TREE_OPERAND (op0, 0);
 104       machine_mode outermode = TYPE_MODE (TREE_TYPE (view_op0));
 105       machine_mode extract_mode = TYPE_MODE (TREE_TYPE (ref));
 106
 107       if ((auto_var_in_fn_p (view_op0, fun->decl)
 108            || (VAR_P (view_op0) && DECL_HARD_REGISTER (view_op0)))
 109           && !TREE_ADDRESSABLE (view_op0)
 110           && ((!is_extract && can_vec_set_var_idx_p (outermode))
 111               || (is_extract
 112                   && can_vec_extract_var_idx_p (outermode, extract_mode))))
 113         {
 114           location_t loc = gimple_location (stmt);
 115           tree var_src = make_ssa_name (TREE_TYPE (view_op0));
 116
 117           ass_stmt = gimple_build_assign (var_src, view_op0);
 118           gimple_set_vuse (ass_stmt, gimple_vuse (stmt));
 119           gimple_set_location (ass_stmt, loc);
 120           gsi_insert_before (gsi, ass_stmt, GSI_SAME_STMT);
 121
 122           if (!is_extract)
 123             {
 124               tree var_dst = make_ssa_name (TREE_TYPE (view_op0));
 125
 126               new_stmt = gimple_build_call_internal (IFN_VEC_SET, 3, var_src,
 127                                                      val, pos);
 128
 129               gimple_call_set_lhs (new_stmt, var_dst);
 130               gimple_set_location (new_stmt, loc);
 131               gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 132
 133               ass_stmt = gimple_build_assign (view_op0, var_dst);
 134               gimple_set_location (ass_stmt, loc);
 135               gimple_move_vops (ass_stmt, stmt);
 136               gsi_insert_before (gsi, ass_stmt, GSI_SAME_STMT);
 137
 138               basic_block bb = gimple_bb (stmt);
 139               if (gsi_remove (gsi, true)
 140                   && gimple_purge_dead_eh_edges (bb))
 141                 cfg_changed = true;
 142               *gsi = gsi_for_stmt (ass_stmt);
 143             }
 144           else
 145             {
 146               new_stmt
 147                 = gimple_build_call_internal (IFN_VEC_EXTRACT, 2, var_src, pos);
 148               gimple_call_set_lhs (new_stmt, lhs);
 149
 150               gsi_replace (gsi, new_stmt, true);
 151               cfg_changed = true;
 152             }
 153         }
 154     }
 155
 156   return cfg_changed;
 157 }
 158
 159 /* Expand all VEC_COND_EXPR gimple assignments into calls to internal
 160    function based on type of selected expansion.  */
 161
 162 static gimple *
 163 gimple_expand_vec_cond_expr (struct function *fun, gimple_stmt_iterator *gsi,
 164                              hash_map<tree, unsigned int> *vec_cond_ssa_name_uses)
 165 {
 166   tree lhs, op0a = NULL_TREE, op0b = NULL_TREE;
 167   enum tree_code code;
 168   enum tree_code tcode;
 169   machine_mode cmp_op_mode;
 170   bool unsignedp;
 171   enum insn_code icode;
 172   imm_use_iterator imm_iter;
 173
 174   /* Only consider code == GIMPLE_ASSIGN.  */
 175   gassign *stmt = dyn_cast<gassign *> (gsi_stmt (*gsi));
 176   if (!stmt)
 177     return NULL;
 178
 179   code = gimple_assign_rhs_code (stmt);
 180   if (code != VEC_COND_EXPR)
 181     return NULL;
 182
 183   tree op0 = gimple_assign_rhs1 (stmt);
 184   tree op1 = gimple_assign_rhs2 (stmt);
 185   tree op2 = gimple_assign_rhs3 (stmt);
 186   lhs = gimple_assign_lhs (stmt);
 187   machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
 188
 189   /* Lower mask typed, non-vector mode VEC_COND_EXPRs to bitwise operations.
 190      Those can end up generated by folding and at least for integer mode masks
 191      we cannot expect vcond expanders to exist.  We lower a ? b : c
 192      to (b & a) | (c & ~a).  */
 193   if (VECTOR_BOOLEAN_TYPE_P (TREE_TYPE (lhs))
 194       && !VECTOR_MODE_P (mode))
 195     {
 196       gcc_assert (types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1)));
 197       gimple_seq stmts = NULL;
 198       tree type = TREE_TYPE (lhs);
 199       location_t loc = gimple_location (stmt);
 200       tree tem0 = gimple_build (&stmts, loc, BIT_AND_EXPR, type, op1, op0);
 201       tree tem1 = gimple_build (&stmts, loc, BIT_NOT_EXPR, type, op0);
 202       tree tem2 = gimple_build (&stmts, loc, BIT_AND_EXPR, type, op2, tem1);
 203       tree tem3 = gimple_build (&stmts, loc, BIT_IOR_EXPR, type, tem0, tem2);
 204       gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
 205       return gimple_build_assign (lhs, tem3);
 206     }
 207
 208   bool can_compute_op0 = true;
 209   gcc_assert (!COMPARISON_CLASS_P (op0));
 210   if (TREE_CODE (op0) == SSA_NAME)
 211     {
 212       unsigned int used_vec_cond_exprs = 0;
 213       unsigned int *slot = vec_cond_ssa_name_uses->get (op0);
 214       if (slot)
 215         used_vec_cond_exprs = *slot;
 216       else
 217         {
 218           gimple *use_stmt;
 219           FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, op0)
 220             {
 221               gassign *assign = dyn_cast<gassign *> (use_stmt);
 222               if (assign != NULL
 223                   && gimple_assign_rhs_code (assign) == VEC_COND_EXPR
 224                   && gimple_assign_rhs1 (assign) == op0)
 225                 used_vec_cond_exprs++;
 226             }
 227           vec_cond_ssa_name_uses->put (op0, used_vec_cond_exprs);
 228         }
 229
 230       gassign *def_stmt = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (op0));
 231       if (def_stmt)
 232         {
 233           tcode = gimple_assign_rhs_code (def_stmt);
 234           op0a = gimple_assign_rhs1 (def_stmt);
 235           op0b = gimple_assign_rhs2 (def_stmt);
 236
 237           tree op0_type = TREE_TYPE (op0);
 238           tree op0a_type = TREE_TYPE (op0a);
 239           if (TREE_CODE_CLASS (tcode) == tcc_comparison)
 240             can_compute_op0 = expand_vec_cmp_expr_p (op0a_type, op0_type,
 241                                                      tcode);
 242
 243           if (can_compute_op0
 244               && TYPE_MODE (TREE_TYPE (lhs)) == TYPE_MODE (TREE_TYPE (op0)))
 245             {
 246               /* Assuming c = x CMP y.  */
 247               bool op1_minus_onep = integer_minus_onep (op1);
 248               bool op2_zerop = integer_zerop (op2);
 249               tree vtype = TREE_TYPE (lhs);
 250               machine_mode vmode = TYPE_MODE (vtype);
 251               /* Try to fold r = c ? -1 : 0 to r = c.  */
 252               if (op1_minus_onep && op2_zerop)
 253                 {
 254                   tree conv_op = build1 (VIEW_CONVERT_EXPR, vtype, op0);
 255                   return gimple_build_assign (lhs, conv_op);
 256                 }
 257               /* Try to fold r = c ? -1 : z to r = c | z, or
 258                  r = c ? c : z.  */
 259               if (op1_minus_onep)
 260                 {
 261                   tree conv_op = build1 (VIEW_CONVERT_EXPR, vtype, op0);
 262                   tree new_op1 = make_ssa_name (vtype);
 263                   gassign *new_stmt = gimple_build_assign (new_op1, conv_op);
 264                   gsi_insert_seq_before (gsi, new_stmt, GSI_SAME_STMT);
 265                   if (optab_handler (ior_optab, vmode) != CODE_FOR_nothing)
 266                     /* r = c | z */
 267                     return gimple_build_assign (lhs, BIT_IOR_EXPR, new_op1,
 268                                                 op2);
 269                   /* r = c ? c : z */
 270                   op1 = new_op1;
 271                 }
 272               /* Try to fold r = c ? z : 0 to r = c & z, or
 273                  r = c ? z : c.  */
 274               else if (op2_zerop)
 275                 {
 276                   tree conv_op = build1 (VIEW_CONVERT_EXPR, vtype, op0);
 277                   tree new_op2 = make_ssa_name (vtype);
 278                   gassign *new_stmt = gimple_build_assign (new_op2, conv_op);
 279                   gsi_insert_seq_before (gsi, new_stmt, GSI_SAME_STMT);
 280                   if (optab_handler (and_optab, vmode) != CODE_FOR_nothing)
 281                     /* r = c | z */
 282                     return gimple_build_assign (lhs, BIT_AND_EXPR, new_op2,
 283                                                 op1);
 284                   /* r = c ? z : c */
 285                   op2 = new_op2;
 286                 }
 287               bool op1_zerop = integer_zerop (op1);
 288               bool op2_minus_onep = integer_minus_onep (op2);
 289               /* Try to fold r = c ? 0 : z to r = .BIT_ANDN (z, c).  */
 290               if (op1_zerop
 291                   && (direct_internal_fn_supported_p (IFN_BIT_ANDN, vtype,
 292                                                       OPTIMIZE_FOR_BOTH)))
 293                 {
 294                   tree conv_op = build1 (VIEW_CONVERT_EXPR, vtype, op0);
 295                   tree new_op = make_ssa_name (vtype);
 296                   gassign *new_stmt = gimple_build_assign (new_op, conv_op);
 297                   gsi_insert_seq_before (gsi, new_stmt, GSI_SAME_STMT);
 298                   return gimple_build_call_internal (IFN_BIT_ANDN, 2, op2,
 299                                                      new_op);
 300                 }
 301               /* Try to fold r = c ? z : -1 to r = .BIT_IORN (z, c).  */
 302               else if (op2_minus_onep
 303                        && (direct_internal_fn_supported_p (IFN_BIT_IORN, vtype,
 304                                                            OPTIMIZE_FOR_BOTH)))
 305                 {
 306                   tree conv_op = build1 (VIEW_CONVERT_EXPR, vtype, op0);
 307                   tree new_op = make_ssa_name (vtype);
 308                   gassign *new_stmt = gimple_build_assign (new_op, conv_op);
 309                   gsi_insert_seq_before (gsi, new_stmt, GSI_SAME_STMT);
 310                   return gimple_build_call_internal (IFN_BIT_IORN, 2, op1,
 311                                                      new_op);
 312                 }
 313             }
 314
 315           /* When the compare has EH we do not want to forward it when
 316              it has multiple uses and in general because of the complication
 317              with EH redirection.  */
 318           if (stmt_can_throw_internal (fun, def_stmt))
 319             tcode = TREE_CODE (op0);
 320
 321           /* If we can compute op0 and have multiple uses, keep the SSA
 322              name and use vcond_mask.  */
 323           else if (can_compute_op0
 324                    && used_vec_cond_exprs >= 2
 325                    && (get_vcond_mask_icode (mode, TYPE_MODE (op0_type))
 326                        != CODE_FOR_nothing))
 327             tcode = TREE_CODE (op0);
 328         }
 329       else
 330         tcode = TREE_CODE (op0);
 331     }
 332   else
 333     tcode = TREE_CODE (op0);
 334
 335   if (TREE_CODE_CLASS (tcode) != tcc_comparison)
 336     {
 337       gcc_assert (VECTOR_BOOLEAN_TYPE_P (TREE_TYPE (op0)));
 338       if (get_vcond_mask_icode (mode, TYPE_MODE (TREE_TYPE (op0)))
 339           != CODE_FOR_nothing)
 340         return gimple_build_call_internal (IFN_VCOND_MASK, 3, op0, op1, op2);
 341       /* Fake op0 < 0.  */
 342       else
 343         {
 344           gcc_assert (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (op0)))
 345                       == MODE_VECTOR_INT);
 346           op0a = op0;
 347           op0b = build_zero_cst (TREE_TYPE (op0));
 348           tcode = LT_EXPR;
 349         }
 350     }
 351   cmp_op_mode = TYPE_MODE (TREE_TYPE (op0a));
 352   unsignedp = TYPE_UNSIGNED (TREE_TYPE (op0a));
 353
 354   gcc_assert (known_eq (GET_MODE_NUNITS (mode),
 355                         GET_MODE_NUNITS (cmp_op_mode)));
 356
 357   icode = get_vcond_icode (mode, cmp_op_mode, unsignedp);
 358   /* Some targets do not have vcondeq and only vcond with NE/EQ
 359      but not vcondu, so make sure to also try vcond here as
 360      vcond_icode_p would canonicalize the optab query to.  */
 361   if (icode == CODE_FOR_nothing
 362       && (tcode == NE_EXPR || tcode == EQ_EXPR)
 363       && ((icode = get_vcond_icode (mode, cmp_op_mode, !unsignedp))
 364           != CODE_FOR_nothing))
 365     unsignedp = !unsignedp;
 366   if (icode == CODE_FOR_nothing)
 367     {
 368       if (tcode == LT_EXPR
 369           && op0a == op0)
 370         {
 371           /* A VEC_COND_EXPR condition could be folded from EQ_EXPR/NE_EXPR
 372              into a constant when only get_vcond_eq_icode is supported.
 373              Try changing it to NE_EXPR.  */
 374           tcode = NE_EXPR;
 375         }
 376       if ((tcode == EQ_EXPR || tcode == NE_EXPR)
 377           && direct_internal_fn_supported_p (IFN_VCONDEQ, TREE_TYPE (lhs),
 378                                              TREE_TYPE (op0a),
 379                                              OPTIMIZE_FOR_BOTH))
 380         {
 381           tree tcode_tree = build_int_cst (integer_type_node, tcode);
 382           return gimple_build_call_internal (IFN_VCONDEQ, 5, op0a, op0b, op1,
 383                                              op2, tcode_tree);
 384         }
 385
 386       gcc_assert (VECTOR_BOOLEAN_TYPE_P (TREE_TYPE (op0))
 387                   && can_compute_op0
 388                   && (get_vcond_mask_icode (mode, TYPE_MODE (TREE_TYPE (op0)))
 389                       != CODE_FOR_nothing));
 390       return gimple_build_call_internal (IFN_VCOND_MASK, 3, op0, op1, op2);
 391     }
 392
 393   tree tcode_tree = build_int_cst (integer_type_node, tcode);
 394   return gimple_build_call_internal (unsignedp ? IFN_VCONDU : IFN_VCOND,
 395                                      5, op0a, op0b, op1, op2, tcode_tree);
 396 }
 397
 398 /* Duplicate COND_EXPR condition defs of STMT located in BB when they are
 399    comparisons so RTL expansion with the help of TER
 400    can perform better if conversion.  */
 401 static void
 402 maybe_duplicate_comparison (gassign *stmt, basic_block bb)
 403 {
 404   imm_use_iterator imm_iter;
 405   use_operand_p use_p;
 406   auto_vec<gassign *, 4> cond_exprs;
 407   tree lhs = gimple_assign_lhs (stmt);
 408   unsigned cnt = 0;
 409
 410   /* This is should not be used for -O0 nor it is not useful
 411      when ter is turned off. */
 412   if (!optimize || !flag_tree_ter)
 413     return;
 414
 415   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
 416     {
 417       if (is_gimple_debug (USE_STMT (use_p)))
 418         continue;
 419       cnt++;
 420       /* Add the use statement if it was a cond_expr.  */
 421       if (gimple_bb (USE_STMT (use_p)) == bb
 422           && is_gimple_assign (USE_STMT (use_p))
 423           && gimple_assign_rhs_code (USE_STMT (use_p)) == COND_EXPR
 424           && gimple_assign_rhs1_ptr (USE_STMT (use_p)) == use_p->use)
 425         cond_exprs.safe_push (as_a <gassign *> (USE_STMT (use_p)));
 426     }
 427
 428   /* If the comparison has 0 or 1 uses, no reason to do anything. */
 429   if (cnt <= 1)
 430     return;
 431
 432   /* If we only use the expression inside cond_exprs in that BB, we don't
 433      need to duplicate for one of them so pop the top. */
 434   if (cond_exprs.length () == cnt)
 435     cond_exprs.pop();
 436
 437   while (!cond_exprs.is_empty())
 438     {
 439       auto old_top = cond_exprs.pop();
 440       gassign *copy = as_a <gassign *> (gimple_copy (stmt));
 441       tree new_def = duplicate_ssa_name (lhs, copy);
 442       gimple_assign_set_lhs (copy, new_def);
 443       auto gsi2 = gsi_for_stmt (old_top);
 444       gsi_insert_before (&gsi2, copy, GSI_SAME_STMT);
 445       gimple_assign_set_rhs1 (old_top, new_def);
 446       update_stmt (old_top);
 447     }
 448 }
 449
 450
 451 namespace {
 452
 453 const pass_data pass_data_gimple_isel =
 454 {
 455   GIMPLE_PASS, /* type */
 456   "isel", /* name */
 457   OPTGROUP_VEC, /* optinfo_flags */
 458   TV_NONE, /* tv_id */
 459   PROP_cfg, /* properties_required */
 460   0, /* properties_provided */
 461   0, /* properties_destroyed */
 462   0, /* todo_flags_start */
 463   TODO_update_ssa, /* todo_flags_finish */
 464 };
 465
 466 class pass_gimple_isel : public gimple_opt_pass
 467 {
 468 public:
 469   pass_gimple_isel (gcc::context *ctxt)
 470     : gimple_opt_pass (pass_data_gimple_isel, ctxt)
 471   {}
 472
 473   /* opt_pass methods: */
 474   bool gate (function *) final override
 475     {
 476       return true;
 477     }
 478
 479   unsigned int execute (function *fun) final override;
 480 }; // class pass_gimple_isel
 481
 482
 483 /* Iterate all gimple statements and perform pre RTL expansion
 484    GIMPLE massaging to improve instruction selection.  */
 485
 486 unsigned int
 487 pass_gimple_isel::execute (struct function *fun)
 488 {
 489   gimple_stmt_iterator gsi;
 490   basic_block bb;
 491   hash_map<tree, unsigned int> vec_cond_ssa_name_uses;
 492   auto_bitmap dce_ssa_names;
 493   bool cfg_changed = false;
 494
 495   FOR_EACH_BB_FN (bb, fun)
 496     {
 497       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 498         {
 499           /* Pre-expand VEC_COND_EXPRs to .VCOND* internal function
 500              calls mapping to supported optabs.  */
 501           gimple *g = gimple_expand_vec_cond_expr (fun, &gsi,
 502                                                    &vec_cond_ssa_name_uses);
 503           if (g != NULL)
 504             {
 505               tree lhs = gimple_assign_lhs (gsi_stmt (gsi));
 506               gimple_set_lhs (g, lhs);
 507               gsi_replace (&gsi, g, false);
 508             }
 509
 510           /* Recognize .VEC_SET and .VEC_EXTRACT patterns.  */
 511           cfg_changed |= gimple_expand_vec_set_extract_expr (fun, &gsi);
 512           if (gsi_end_p (gsi))
 513             break;
 514
 515           gassign *stmt = dyn_cast <gassign *> (*gsi);
 516           if (!stmt)
 517             continue;
 518
 519           tree_code code = gimple_assign_rhs_code (stmt);
 520           if (TREE_CODE_CLASS (code) == tcc_comparison)
 521             maybe_duplicate_comparison (stmt, bb);
 522         }
 523     }
 524
 525   for (auto it = vec_cond_ssa_name_uses.begin ();
 526        it != vec_cond_ssa_name_uses.end (); ++it)
 527     bitmap_set_bit (dce_ssa_names, SSA_NAME_VERSION ((*it).first));
 528
 529   simple_dce_from_worklist (dce_ssa_names);
 530
 531   return cfg_changed ? TODO_cleanup_cfg : 0;
 532 }
 533
 534 } // anon namespace
 535
 536 gimple_opt_pass *
 537 make_pass_gimple_isel (gcc::context *ctxt)
 538 {
 539   return new pass_gimple_isel (ctxt);
 540 }
 541