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
 126   if (flag_trapping_math)
 127     calculate_dominance_info (CDI_POST_DOMINATORS);
 128
 129   FOR_EACH_BB (bb)
 130     {
 131       block_stmt_iterator bsi;
 132       tree phi, def;
 133       for (bsi = bsi_start (bb);
 134            !bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR;
 135            bsi_next (&bsi))
 136         ;
 137
 138       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 139         {
 140           def = PHI_RESULT (phi);
 141           if (FLOAT_TYPE_P (TREE_TYPE (def))
 142               && is_gimple_reg (def))
 143             execute_cse_reciprocals_1 (&bsi, def, true);
 144         }
 145
 146       for (; !bsi_end_p (bsi); bsi_next (&bsi))
 147         {
 148           tree stmt = bsi_stmt (bsi);
 149           if (TREE_CODE (stmt) == MODIFY_EXPR
 150               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 151               && FLOAT_TYPE_P (TREE_TYPE (def))
 152               && is_gimple_reg (def))
 153             execute_cse_reciprocals_1 (&bsi, def, false);
 154         }
 155     }
 156
 157   if (flag_trapping_math)
 158     free_dominance_info (CDI_POST_DOMINATORS);
 159 }
 160
 161 struct tree_opt_pass pass_cse_reciprocals =
 162 {
 163   "recip",                              /* name */
 164   gate_cse_reciprocals,                 /* gate */
 165   execute_cse_reciprocals,              /* execute */
 166   NULL,                                 /* sub */
 167   NULL,                                 /* next */
 168   0,                                    /* static_pass_number */
 169   0,                                    /* tv_id */
 170   PROP_ssa,                             /* properties_required */
 171   0,                                    /* properties_provided */
 172   0,                                    /* properties_destroyed */
 173   0,                                    /* todo_flags_start */
 174   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 175     | TODO_verify_stmts,                /* todo_flags_finish */
 176   0                                     /* letter */
 177 };