gcc/tree-ssa-math-opts.c

   1 /* Global, SSA-based optimizations using mathematical identities.
   2    Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 /* Currently, the only mini-pass in this file tries to CSE reciprocal
  22    operations.  These are common in sequences such as this one:
  23
  24         modulus = sqrt(x*x + y*y + z*z);
  25         x = x / modulus;
  26         y = y / modulus;
  27         z = z / modulus;
  28
  29    that can be optimized to
  30
  31         modulus = sqrt(x*x + y*y + z*z);
  32         rmodulus = 1.0 / modulus;
  33         x = x * rmodulus;
  34         y = y * rmodulus;
  35         z = z * rmodulus;
  36
  37    We do this for loop invariant divisors, and with this pass whenever
  38    we notice that a division has the same divisor multiple times.  */
  39
  40 #include "config.h"
  41 #include "system.h"
  42 #include "coretypes.h"
  43 #include "tm.h"
  44 #include "flags.h"
  45 #include "tree.h"
  46 #include "tree-flow.h"
  47 #include "real.h"
  48 #include "timevar.h"
  49 #include "tree-pass.h"
  50
  51 static bool
  52 gate_cse_reciprocals (void)
  53 {
  54   return optimize && !optimize_size && flag_unsafe_math_optimizations;
  55 }
  56
  57 /* Check if DEF's uses include more than one floating-point division,
  58    and if so replace them by multiplications with the reciprocal.  If
  59    PHI is true, insert the reciprocal calculation before BSI, otherwise
  60    insert it after and move BSI to the new statement.
  61
  62    Does not check the type of DEF, nor that DEF is a GIMPLE register.
  63    This is done in the caller for speed, because otherwise this routine
  64    would be called for every definition and phi node.  */
  65 static void
  66 execute_cse_reciprocals_1 (block_stmt_iterator *bsi, tree def, bool phi)
  67 {
  68   use_operand_p use_p;
  69   imm_use_iterator use_iter;
  70   tree t, new_stmt, type;
  71   int count = 0;
  72   bool ok = !flag_trapping_math;
  73
  74   /* Find uses.  */
  75   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
  76     {
  77       tree use_stmt = USE_STMT (use_p);
  78       if (TREE_CODE (use_stmt) == MODIFY_EXPR
  79           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
  80           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
  81         {
  82           ++count;
  83           /* Check if this use post-dominates the insertion point.  */
  84           if (ok || dominated_by_p (CDI_POST_DOMINATORS, bsi->bb,
  85                                     bb_for_stmt (use_stmt)))
  86             ok = true;
  87         }
  88       if (count >= 2 && ok)
  89         break;
  90     }
  91
  92   if (count < 2 || !ok)
  93     return;
  94
  95   /* Make a variable with the replacement and substitute it.  */
  96   type = TREE_TYPE (def);
  97   t = make_rename_temp (type, "reciptmp");
  98   new_stmt = build2 (MODIFY_EXPR, void_type_node, t,
  99                      fold_build2 (RDIV_EXPR, type, build_real (type, dconst1),
 100                                   def));
 101
 102   if (phi)
 103     bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
 104   else
 105     bsi_insert_after (bsi, new_stmt, BSI_NEW_STMT);
 106
 107   FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def)
 108     {
 109       tree use_stmt = USE_STMT (use_p);
 110       if (use_stmt != new_stmt
 111           && TREE_CODE (use_stmt) == MODIFY_EXPR
 112           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
 113           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
 114         {
 115           TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR);
 116           SET_USE (use_p, t);
 117         }
 118     }
 119 }
 120
 121 static void
 122 execute_cse_reciprocals (void)
 123 {
 124   basic_block bb;
 125   tree arg;
 126
 127   if (flag_trapping_math)
 128     calculate_dominance_info (CDI_POST_DOMINATORS);
 129
 130   if (single_succ_p (ENTRY_BLOCK_PTR))
 131     for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
 132       if (default_def (arg))
 133         {
 134           block_stmt_iterator bsi;
 135           bsi = bsi_start (single_succ (ENTRY_BLOCK_PTR));
 136           execute_cse_reciprocals_1 (&bsi, default_def (arg), false);
 137         }
 138
 139   FOR_EACH_BB (bb)
 140     {
 141       block_stmt_iterator bsi;
 142       tree phi, def;
 143       for (bsi = bsi_start (bb);
 144            !bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR;
 145            bsi_next (&bsi))
 146         ;
 147
 148       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 149         {
 150           def = PHI_RESULT (phi);
 151           if (FLOAT_TYPE_P (TREE_TYPE (def))
 152               && is_gimple_reg (def))
 153             execute_cse_reciprocals_1 (&bsi, def, true);
 154         }
 155
 156       for (; !bsi_end_p (bsi); bsi_next (&bsi))
 157         {
 158           tree stmt = bsi_stmt (bsi);
 159           if (TREE_CODE (stmt) == MODIFY_EXPR
 160               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 161               && FLOAT_TYPE_P (TREE_TYPE (def))
 162               && TREE_CODE (def) == SSA_NAME)
 163             execute_cse_reciprocals_1 (&bsi, def, false);
 164         }
 165     }
 166
 167   if (flag_trapping_math)
 168     free_dominance_info (CDI_POST_DOMINATORS);
 169 }
 170
 171 struct tree_opt_pass pass_cse_reciprocals =
 172 {
 173   "recip",                              /* name */
 174   gate_cse_reciprocals,                 /* gate */
 175   execute_cse_reciprocals,              /* execute */
 176   NULL,                                 /* sub */
 177   NULL,                                 /* next */
 178   0,                                    /* static_pass_number */
 179   0,                                    /* tv_id */
 180   PROP_ssa,                             /* properties_required */
 181   0,                                    /* properties_provided */
 182   0,                                    /* properties_destroyed */
 183   0,                                    /* todo_flags_start */
 184   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 185     | TODO_verify_stmts,                /* todo_flags_finish */
 186   0                                     /* letter */
 187 };