nsz Git - libfirm/blob - ir/be/grgen/simd/normalize.c

   1 /*******************************************************************************************
   2 * Program:  normalize.c
   3 * Function: Part of the simd optimization. Provides functions to normalize a FIRM
   4 *                       graph in order to increase the number of patterns matched.
   5 * Author:   Andreas Schoesser
   6 * Date:     08.03.2007
   7 *******************************************************************************************/
   8
   9 #include <malloc.h>
  10 #include <assert.h>
  11
  12 #include "simd_presets.h"
  13
  14 #include "pmap.h"
  15 #include "irgwalk.h"
  16 #include "ircons.h"
  17 #include "tv.h"
  18 #include "irgmod.h"
  19 #include "irnode.h"
  20
  21 #include "normalize_t.h"
  22 #include "firm_node_ext.h"
  23
  24
  25
  26 /************************************************************************
  27  * Starts normalization of address calculations for Add and Store
  28  * nodes. Folds Add-chains to one big MultipeAdd node.
  29  ************************************************************************/
  30
  31 struct pmap *normalize_address_calculation(ir_graph *irg, int decomposition_possible)
  32 {
  33         normalize_info_t norm_info;
  34
  35         norm_info.irg = irg;
  36         norm_info.replaced_ptrs = (decomposition_possible)      ? pmap_create() : NULL;
  37
  38         irg_walk_graph(irg, ac_walk_pre, NULL, &norm_info);
  39
  40         return(norm_info.replaced_ptrs);
  41 }
  42
  43
  44
  45 /************************************************************************
  46  * Called for each ir_node, in which the main work for normalization
  47  * is done.
  48  ************************************************************************/
  49
  50 static void ac_walk_pre(ir_node *n, void * env)
  51 {
  52         ir_node *addr, *multAdd;
  53         normalize_info_t *norm_info = (normalize_info_t *) env;
  54         ir_graph *irg = norm_info->irg;
  55         int i, exchanged = 0;
  56
  57         switch(get_irn_opcode(n))
  58         {
  59                 case iro_Load: addr = get_Load_ptr(n); break;
  60                 case iro_Store: addr = get_Store_ptr(n); break;
  61                 case iro_Proj:  if(get_irn_opcode(get_irn_n(n, 0)) == iro_Cmp)
  62                                                         enforce_cmp_gt(n);
  63                                                 return;
  64                 default: return;
  65         }
  66
  67         if(get_irn_opcode(addr) == iro_Add)
  68         {
  69                 // Convert a ADD-chain to a single MultipleAdd node.
  70
  71                 ir_node *add = addr;
  72                 int arity = 0;
  73                 int max_ins = 30;
  74                 ir_node **ins = malloc(max_ins * sizeof(ir_node *));
  75
  76                 if(add_add_preds(add, ins, &max_ins, &arity) == 0)
  77                 {
  78                         // We found no constant, add 0x0
  79                         ins[arity++] = new_Const(mode_Is, new_tarval_from_long(0, mode_Is));
  80                 }
  81                 multAdd = new_ir_node(NULL, irg, get_nodes_block(addr), op_MultipleAdd, get_irn_mode(addr), arity, ins);
  82
  83                 switch(get_irn_opcode(n))
  84                 {
  85                         case iro_Load: set_Load_ptr(n, multAdd); break;
  86                         case iro_Store: set_Store_ptr(n, multAdd); break;
  87                         default: return;
  88                 }
  89
  90                 // exchange(add, multAdd); Exchange wouldn't work here since the original ADD node would be killed.
  91                 if(norm_info->replaced_ptrs != NULL)
  92                         pmap_insert(norm_info->replaced_ptrs, multAdd, add);
  93                 free(ins);
  94         }
  95         else if(get_irn_opcode(addr) != iro_MultipleAdd)
  96         {
  97                 // Insert a new MultipleAdd node.
  98                 ir_node **ins = alloca(2 * sizeof(ir_node *));
  99
 100                 ins[0] = addr;
 101                 ins[1] = new_Const(mode_Is, new_tarval_from_long(0, mode_Is));
 102                 multAdd = new_ir_node(NULL, irg, get_nodes_block(n), op_MultipleAdd, get_irn_mode(addr), 2, ins);
 103                 //exchange(addr, multAdd);
 104                 if(norm_info->replaced_ptrs != NULL)
 105                         pmap_insert(norm_info->replaced_ptrs, multAdd, addr);
 106
 107                 switch(get_irn_opcode(n))
 108                 {
 109                         case iro_Load: set_Load_ptr(n, multAdd); break;
 110                         case iro_Store: set_Store_ptr(n, multAdd); break;
 111                         default: return;
 112                 }
 113         }
 114
 115         /* Order the MultAdd ins to be compared quickly later. Bubble Sort */
 116         do
 117         {
 118                 exchanged = 0;
 119                 for(i = 0; i < get_irn_arity(multAdd) - 1; i++)
 120                 {
 121                         ir_node *n1 = get_irn_n(multAdd, i),
 122                                         *n2 = get_irn_n(multAdd, i + 1);
 123
 124                         // Move the Constant to pos0
 125                         if(is_Const(n2) && !is_Const(n1))
 126                         {
 127                                 set_irn_n(multAdd, i, n2);
 128                                 set_irn_n(multAdd, i + 1, n1);
 129                                 exchanged = 1;
 130                                 continue;
 131                         }
 132
 133                         // Otherwise order by pointer value
 134                         if(n1 > n2 && !is_Const(n1))
 135                         {
 136                                 set_irn_n(multAdd, i, n2);
 137                                 set_irn_n(multAdd, i + 1, n1);
 138                                 exchanged = 1;
 139                         }
 140                 }
 141         } while(exchanged);
 142
 143 }
 144
 145
 146
 147 /************************************************************************
 148  * Recursive function. Collects all adds of an "add chain" and inserts
 149  * all the predecessors of the add chain into one ins array
 150  ************************************************************************/
 151
 152 int add_add_preds(ir_node *add, ir_node **ins, int *max_len, int *num_preds)
 153 {
 154         int i, found_constant = 0;
 155
 156         for(i = 0; i < 2; i++)
 157         {
 158                 ir_node *pred = get_irn_n(add, i);
 159                 switch(get_irn_opcode(pred))
 160                 {
 161                         case iro_Add:   found_constant |= add_add_preds(pred, ins, max_len, num_preds);
 162                                                         break;
 163                         case iro_Const: found_constant |= 1;
 164                                                         /* Fall through */
 165                         default:                assert(*num_preds < *max_len && "Reallocation of temp ins array not implemented yet!");
 166                                                         ins[*num_preds] = pred;
 167                                                         (*num_preds)++;
 168                 }
 169         }
 170
 171         return(found_constant);
 172 }
 173
 174
 175
 176 /*******************************************************
 177  * Decompose the normalization, that is replace all
 178  * introduced MultipleAdds by their original ADD-Chain.
 179  *******************************************************/
 180
 181 void decompose_normalization(struct pmap *replaced_ptrs)
 182 {
 183         pmap_entry *entry;
 184
 185         pmap_foreach(replaced_ptrs, entry)
 186         {
 187                 ir_node *multAdd = (ir_node *) entry->key;
 188                 ir_node *orgAddr = (ir_node *) entry->value;
 189
 190                 //if(get_irn_n_edges(multAdd) > 0)
 191 /*              switch(get_irn_opcode(loadStore))
 192                 {
 193                         case iro_Load: set_Load_ptr(loadStore, orgAddr); break;
 194                         case iro_Store: set_Store_ptr(loadStore, orgAddr); break;
 195                         default: break; //return; //assert(0 && "Wrong opcode!");
 196                 }*/
 197                 exchange(multAdd, orgAddr);
 198 //              edges_node_deleted(multAdd, get_irn_irg(multAdd));
 199         }
 200
 201         pmap_destroy(replaced_ptrs);
 202 }
 203
 204
 205 /************************************************************************
 206  * Returns the original address that was replaced by a multiple add
 207  ************************************************************************/
 208
 209 ir_node *get_org_addr(ir_node *madd, struct pmap *replaced_ptrs)
 210 {
 211         assert(get_irn_opcode(madd) == iro_MultipleAdd);
 212         return(pmap_get(replaced_ptrs, madd));
 213 }
 214
 215
 216
 217 /************************************************************************
 218  * Enforces all compares lt to be gt
 219  ************************************************************************/
 220
 221 void enforce_cmp_gt(ir_node *proj)
 222 {
 223         if(get_Proj_proj(proj) == pn_Cmp_Lt)
 224         {
 225                 pn_Cmp new_pnc = get_inversed_pnc(get_Proj_proj(proj));
 226                 ir_node *tmp, *cmp = get_irn_n(proj, 0);
 227
 228                 tmp = get_Cmp_left(cmp);
 229                 set_Cmp_left(cmp, get_Cmp_right(cmp));
 230                 set_Cmp_right(cmp, tmp);
 231                 set_Proj_proj(proj, new_pnc);
 232         }
 233 }
 234
 235
 236 /************************************************************************/
 237 /*                                                                      */
 238 /************************************************************************/
 239 #if 0
 240 void normalize_direct_jump(ir_node *block)
 241 {
 242         int block_arity = get_irn_arity(block);
 243     int i, j;
 244
 245         if(block_arity > 1)
 246         {
 247                 for(i = 0; i < block_arity; i++)
 248                 {
 249                         ir_node *pred1 = get_irn_n(block, i);
 250                         ir_node *cond;
 251                         if(get_irn_opcode(pred1) == iro_Proj && get_irn_mode(pred1) == mode_X && get_Proj_proj(pred1) == 0 /* False */)
 252                         {
 253                                 cond = get_irn_n(pred1, 0);
 254                                 assert(get_irn_op(cond) == iro_Cond);
 255
 256                                 for(j = 0; i < block_arity; j++)
 257                                 {
 258                                         ir_node *jmp = get_irn_n(block, j);
 259
 260                                         if(j == i)
 261                                                 continue;
 262
 263                                         if(get_irn_opcode(jmp) == iro_Jmp)
 264                                         {
 265                                                 ir_node *jmp_block = get_nodes_block(jmp);
 266                                                 if(get_irn_arity(jmp_block) == 1 && get_irn_n(jmp_block)
 267                                         }
 268
 269                                 }
 270                 }
 271         }
 272 }
 273 #endif