7ad1fbe42e0423b686308fcbe691042b3f4cb3aa
[libfirm] / ir / opt / ldstopt.c
1 /*
2  * Project:     libFIRM
3  * File name:   ir/opt/ldstopt.c
4  * Purpose:     load store optimizations
5  * Author:
6  * Created:
7  * CVS-ID:      $Id$
8  * Copyright:   (c) 1998-2004 Universit\81ät Karlsruhe
9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
10  */
11 # include "irnode_t.h"
12 # include "irgraph_t.h"
13 # include "irmode_t.h"
14 # include "iropt_t.h"
15 # include "ircons_t.h"
16 # include "irgmod.h"
17 # include "irgwalk.h"
18 # include "irvrfy.h"
19 # include "tv_t.h"
20 # include "dbginfo_t.h"
21 # include "iropt_dbg.h"
22 # include "irflag_t.h"
23 # include "array.h"
24 # include "firmstat.h"
25
26 #undef IMAX
27 #define IMAX(a,b)       ((a) > (b) ? (a) : (b))
28
29 #define MAX_PROJ        IMAX(pn_Load_max, pn_Store_max)
30
31 /**
32  * walker environment
33  */
34 typedef struct _walk_env_t {
35   struct obstack obst;          /**< list of all stores */
36   int changes;
37 } walk_env_t;
38
39 /**
40  * flags for Load/Store
41  */
42 enum ldst_flags_t {
43   LDST_VISITED = 1              /**< if set, this Load/Store is already visited */
44 };
45
46 /**
47  * a Load/Store info
48  */
49 typedef struct _ldst_info_t {
50   ir_node  *projs[MAX_PROJ];    /**< list of Proj's of this node */
51   ir_node  *exc_block;          /**< the exception block if available */
52   int      exc_idx;             /**< predecessor index in the exception block */
53   unsigned flags;               /**< flags */
54 } ldst_info_t;
55
56 /**
57  * flags for control flow
58  */
59 enum block_flags_t {
60   BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
61   BLOCK_HAS_EXC  = 2       /**< Block has exceptionl control flow */
62 };
63
64 /**
65  * a Block info
66  */
67 typedef struct _block_info_t {
68   unsigned flags;               /**< flags for the block */
69 } block_info_t;
70
71 /**
72  * walker, clears all links first
73  */
74 static void init_links(ir_node *n, void *env)
75 {
76   set_irn_link(n, NULL);
77 }
78
79 /**
80  * get the Load/Store info of a node
81  */
82 static ldst_info_t *get_ldst_info(ir_node *node, walk_env_t *env)
83 {
84   ldst_info_t *info = get_irn_link(node);
85
86   if (! info) {
87     info = obstack_alloc(&env->obst, sizeof(*info));
88
89     memset(info, 0, sizeof(*info));
90
91     set_irn_link(node, info);
92   }
93   return info;
94 }
95
96 /**
97  * get the Block info of a node
98  */
99 static block_info_t *get_block_info(ir_node *node, walk_env_t *env)
100 {
101   block_info_t *info = get_irn_link(node);
102
103   if (! info) {
104     info = obstack_alloc(&env->obst, sizeof(*info));
105
106     memset(info, 0, sizeof(*info));
107
108     set_irn_link(node, info);
109   }
110   return info;
111 }
112
113 /**
114  * update the projection info for a Load/Store
115  */
116 static int update_projs(ldst_info_t *info, ir_node *proj)
117 {
118   long nr = get_Proj_proj(proj);
119
120   assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");
121
122   if (info->projs[nr]) {
123     /* there is already one, do CSE */
124     exchange(proj, info->projs[nr]);
125     return 1;
126   }
127   else {
128     info->projs[nr] = proj;
129     return 0;
130   }
131 }
132
133 /**
134  * update the exception block info for a Load/Store
135  */
136 static int update_exc(ldst_info_t *info, ir_node *block, int pos)
137 {
138   assert(info->exc_block == NULL && "more than one exception block found");
139
140   info->exc_block = block;
141   info->exc_idx   = pos;
142   return 0;
143 }
144
145 #define get_irn_out_n(node)     (unsigned)get_irn_link(node)
146 #define set_irn_out_n(node, n)  set_irn_link(adr, (void *)(n))
147
148 /**
149  * walker, collects all Load/Store/Proj nodes
150  *
151  * walks form Start -> End
152  */
153 static void collect_nodes(ir_node *node, void *env)
154 {
155   ir_op       *op = get_irn_op(node);
156   ir_node     *pred;
157   ldst_info_t *ldst_info;
158   walk_env_t  *wenv = env;
159
160   if (op == op_Proj) {
161     ir_node *adr;
162     ir_op *op;
163
164     pred = get_Proj_pred(node);
165     op   = get_irn_op(pred);
166
167     if (op == op_Load) {
168       ldst_info = get_ldst_info(pred, wenv);
169
170       wenv->changes |= update_projs(ldst_info, node);
171
172       if ((ldst_info->flags & LDST_VISITED) == 0) {
173         adr = get_Load_ptr(pred);
174         set_irn_out_n(adr, get_irn_out_n(adr) + 1);
175
176         ldst_info->flags |= LDST_VISITED;
177       }
178     }
179     else if (op == op_Store) {
180       ldst_info = get_ldst_info(pred, wenv);
181
182       wenv->changes |= update_projs(ldst_info, node);
183
184       if ((ldst_info->flags & LDST_VISITED) == 0) {
185         adr = get_Store_ptr(pred);
186         set_irn_out_n(adr, get_irn_out_n(adr) + 1);
187
188         ldst_info->flags |= LDST_VISITED;
189       }
190     }
191   }
192   else if (op == op_Block) { /* check, if it's an exception block */
193     int i, n;
194
195     for (i = 0, n = get_Block_n_cfgpreds(node); i < n; ++i) {
196       ir_node      *pred_block;
197       block_info_t *bl_info;
198
199       pred = skip_Proj(get_Block_cfgpred(node, i));
200
201       /* ignore Bad predecessors, they will be removed later */
202       if (is_Bad(pred))
203         continue;
204
205       pred_block = get_nodes_block(pred);
206       bl_info    = get_block_info(pred_block, wenv);
207
208       if (is_fragile_op(pred))
209         bl_info->flags |= BLOCK_HAS_EXC;
210       else if (is_forking_op(pred))
211         bl_info->flags |= BLOCK_HAS_COND;
212
213       if (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store) {
214         ldst_info = get_ldst_info(pred, wenv);
215
216         wenv->changes |= update_exc(ldst_info, node, i);
217       }
218     }
219   }
220 }
221
222 /**
223  * optimize a Load
224  */
225 static int optimize_load(ir_node *load)
226 {
227   ldst_info_t *info = get_irn_link(load);
228   ir_mode *load_mode = get_Load_mode(load);
229   ir_node *pred, *mem, *ptr;
230   int res = 0;
231
232   /* the address of the load to be optimized */
233   ptr = get_Load_ptr(load);
234
235   /*
236    * Check if we can remove the exception form a Load:
237    * this can be done, if the address is from an Sel(Alloc) and
238    * the Sel type is a subtype of the alloc type.
239    *
240    * This optimizes some often used OO constructs,
241    * like x = new O; x->t;
242    */
243   if (info->projs[pn_Load_X_except]) {
244     if (get_irn_op(ptr) == op_Sel) {
245       ir_node *mem = get_Sel_mem(ptr);
246
247       if (get_irn_op(mem) == op_Alloc) {
248         /* ok, check the types */
249         entity *ent  = get_Sel_entity(ptr);
250         type *s_type = get_entity_type(ent);
251         type *a_type = get_Alloc_type(mem);
252
253         if (is_subclass_of(s_type, a_type)) {
254           /* ok, condition met: there can't be an exception because
255            * alloc guarantees that enough memory was allocated */
256
257           exchange(info->projs[pn_Load_X_except], new_Bad());
258           info->projs[pn_Load_X_except] = NULL;
259         }
260       }
261     }
262     else if (get_irn_op(ptr) == op_Alloc) {
263       /* simple case: a direct load after an Alloc. Firm Alloc throw
264        * an exception in case of out-of-memory. So, there is no way for an
265        * exception in this load.
266        * This code is constructed by the "exception lowering" in the Jack compiler.
267        */
268        exchange(info->projs[pn_Load_X_except], new_Bad());
269        info->projs[pn_Load_X_except] = NULL;
270     }
271   }
272
273   /* do NOT touch volatile loads for now */
274   if (get_Load_volatility(load) == volatility_is_volatile)
275     return 0;
276
277   if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
278     /* a Load which value is neither used nor exception checked, remove it */
279     mem  = get_Load_mem(load);
280     exchange(info->projs[pn_Load_M], mem);
281
282     return 1;
283   }
284
285   /* the mem of the Load. Must still be returned after optimization */
286   mem  = get_Load_mem(load);
287
288   if ((get_irn_opcode(ptr) == iro_SymConst) && (get_SymConst_kind(ptr) == symconst_addr_ent)) {
289     entity *ent = get_SymConst_entity(ptr);
290
291     assert(mode_is_reference(get_irn_mode(ptr)));
292
293     if ((allocation_static == get_entity_allocation(ent)) &&
294         (visibility_external_allocated != get_entity_visibility(ent))) {
295       /* a static allocation that is not external: there should be NO exception
296        * when loading. */
297
298       /* no exception, clear the info field as it might be checked later again */
299       if (info->projs[pn_Load_X_except]) {
300         exchange(info->projs[pn_Load_X_except], new_Bad());
301         info->projs[pn_Load_X_except] = NULL;
302       }
303
304       if (variability_constant == get_entity_variability(ent)
305           && is_atomic_entity(ent)) {   /* Might not be atomic after
306                                          lowering of Sels.  In this
307                                          case we could also load, but
308                                          it's more complicated. */
309         /* more simpler case: we load the content of a constant value:
310          * replace it by the constant itself
311          */
312
313         /* no memory */
314         if (info->projs[pn_Load_M])
315           exchange(info->projs[pn_Load_M], mem);
316
317         /* no result :-) */
318         if (info->projs[pn_Load_res])
319           exchange(info->projs[pn_Load_res], copy_const_value(get_atomic_ent_value(ent)));
320
321         return 1;
322       }
323
324       /* we changed the irg, but try further */
325       res = 1;
326     }
327   }
328
329   /* Check, if the address of this load is used more than once.
330    * If not, this load cannot be removed in any case. */
331   if (get_irn_out_n(ptr) <= 1)
332     return 0;
333
334   /* follow the memory chain as long as there are only Loads */
335   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
336
337     /*
338      * BEWARE: one might think that checking the modes is useless, because
339      * if the pointers are identical, they refer to the same object.
340      * This is only true in strong typed languages, not is C were the following
341      * is possible a = *(type1 *)p; b = *(type2 *)p ...
342      */
343
344     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
345         get_irn_mode(get_Store_value(pred)) == load_mode) {
346       ldst_info_t *pred_info = get_irn_link(pred);
347
348       /*
349        * a Load immediately after a Store -- a read after write.
350        * We may remove the Load, if both Load & Store does not have an exception handler
351        * OR they are in the same block. In the latter case the Load cannot
352        * throw an exception when the previous Store was quiet.
353        *
354        * Why we need to check for Store Exc? If the Store cannot be executed (ROM)
355        * the exception handler might simply jump into the load block :-(
356        * We could make it a little bit better if we would know that the exception
357        * handler of the Store jumps directly to the end...
358        */
359       if ((!pred_info->projs[pn_Store_X_except] && !info->projs[pn_Load_X_except]) ||
360           get_nodes_block(load) == get_nodes_block(pred)) {
361         DBG_OPT_RAW(pred, load);
362         exchange( info->projs[pn_Load_res], get_Store_value(pred) );
363
364         if (info->projs[pn_Load_M])
365           exchange(info->projs[pn_Load_M], mem);
366
367         /* no exception */
368         if (info->projs[pn_Load_X_except])
369           exchange( info->projs[pn_Load_X_except], new_Bad());
370         return 1;
371       }
372     }
373     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
374              get_Load_mode(pred) == load_mode) {
375       /*
376        * a Load after a Load -- a read after read.
377        * We may remove the second Load, if it does not have an exception handler
378        * OR they are in the same block. In the later case the Load cannot
379        * throw an exception when the previous Load was quiet.
380        *
381        * Here, there is no need to check if the previos Load has an exception hander because
382        * they would have exact the same exception...
383        */
384       if (! info->projs[pn_Load_X_except] || get_nodes_block(load) == get_nodes_block(pred)) {
385         ldst_info_t *pred_info = get_irn_link(pred);
386
387         DBG_OPT_RAR(pred, load);
388
389         if (pred_info->projs[pn_Load_res]) {
390           /* we need a data proj from the previous load for this optimization */
391           exchange( info->projs[pn_Load_res], pred_info->projs[pn_Load_res] );
392           if (info->projs[pn_Load_M])
393             exchange(info->projs[pn_Load_M], mem);
394         }
395         else {
396           if (info->projs[pn_Load_res]) {
397             set_Proj_pred(info->projs[pn_Load_res], pred);
398             set_nodes_block(info->projs[pn_Load_res], get_nodes_block(pred));
399           }
400           if (info->projs[pn_Load_M]) {
401             /* Actually, this if should not be necessary.  Construct the Loads
402                properly!!! */
403             exchange(info->projs[pn_Load_M], mem);
404           }
405         }
406
407         /* no exception */
408         if (info->projs[pn_Load_X_except])
409           exchange(info->projs[pn_Load_X_except], new_Bad());
410
411         return 1;
412       }
413     }
414
415     /* follow only Load chains */
416     if (get_irn_op(pred) != op_Load)
417       break;
418    }
419   return res;
420 }
421
422 /**
423  * optimize a Store
424  */
425 static int optimize_store(ir_node *store)
426 {
427   ldst_info_t *info = get_irn_link(store);
428   ir_node *pred, *mem, *ptr, *value, *block;
429   ir_mode *mode;
430   int res = 0;
431
432   if (get_Store_volatility(store) == volatility_is_volatile)
433     return 0;
434
435   /*
436    * BEWARE: one might think that checking the modes is useless, because
437    * if the pointers are identical, they refer to the same object.
438    * This is only true in strong typed languages, not is C were the following
439    * is possible *(type1 *)p = a; *(type2 *)p = b ...
440    */
441
442   ptr   = get_Store_ptr(store);
443
444   /* Check, if the address of this load is used more than once.
445    * If not, this load cannot be removed in any case. */
446   if (get_irn_out_n(ptr) <= 1)
447     return 0;
448
449   block = get_nodes_block(store);
450   mem   = get_Store_mem(store);
451   value = get_Store_value(store);
452   mode  = get_irn_mode(value);
453
454   /* follow the memory chain as long as there are only Loads */
455   for (pred = skip_Proj(mem); ; pred = skip_Proj(get_Load_mem(pred))) {
456     ldst_info_t *pred_info = get_irn_link(pred);
457
458     if (get_irn_op(pred) == op_Store && get_Store_ptr(pred) == ptr &&
459         get_nodes_block(pred) == block && get_irn_mode(get_Store_value(pred)) == mode) {
460       /*
461        * a Store after a Store in the same block -- a write after write.
462        * We may remove the first Store, if it does not have an exception handler.
463        *
464        * TODO: What, if both have the same exception handler ???
465        */
466       if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) {
467         DBG_OPT_WAW(pred, store);
468         exchange( pred_info->projs[pn_Store_M], get_Store_mem(pred) );
469         return 1;
470       }
471     }
472     else if (get_irn_op(pred) == op_Load && get_Load_ptr(pred) == ptr &&
473              value == pred_info->projs[pn_Load_res]) {
474       /*
475        * a Store of a value after a Load -- a write after read.
476        * We may remove the second Store, if it does not have an exception handler.
477        */
478       if (! info->projs[pn_Store_X_except]) {
479         DBG_OPT_WAR(pred, store);
480         exchange( info->projs[pn_Store_M], mem );
481         return 1;
482       }
483     }
484
485     /* follow only Load chains */
486     if (get_irn_op(pred) != op_Load)
487       break;
488   }
489   return res;
490 }
491
492 /**
493  * walker, optimizes Phi after Stores:
494  * Does the following optimization:
495  *
496  *   val1   val2   val3          val1  val2  val3
497  *    |      |      |               \    |    /
498  *   Str    Str    Str               \   |   /
499  *      \    |    /                     Phi
500  *       \   |   /                       |
501  *        \  |  /                       Str
502  *          Phi
503  *
504  * This removes the number of stores and allows for predicated execution.
505  * Moves Stores back to the end of a function which may be bad
506  *
507  * Is only allowed if the predecessor blocks have only one successor.
508  */
509 static int optimize_phi(ir_node *phi, void *env)
510 {
511   walk_env_t *wenv = env;
512   int i, n;
513   ir_node *store, *ptr, *block, *phiM, *phiD, *exc, *projM;
514   ir_mode *mode;
515   ir_node **inM, **inD;
516   int *idx;
517   dbg_info *db = NULL;
518   ldst_info_t *info;
519   block_info_t *bl_info;
520
521   /* Must be a memory Phi */
522   if (get_irn_mode(phi) != mode_M)
523     return 0;
524
525   n = get_Phi_n_preds(phi);
526   if (n <= 0)
527     return 0;
528
529   store = skip_Proj(get_Phi_pred(phi, 0));
530   if (get_irn_op(store) != op_Store)
531     return 0;
532
533   /* abort on bad blocks */
534   if (is_Bad(get_nodes_block(store)))
535     return 0;
536
537   /* check if the block has only one output */
538   bl_info = get_irn_link(get_nodes_block(store));
539   if (bl_info->flags)
540     return 0;
541
542   /* this is the address of the store */
543   ptr  = get_Store_ptr(store);
544   mode = get_irn_mode(get_Store_value(store));
545   info = get_irn_link(store);
546   exc  = info->exc_block;
547
548   for (i = 1; i < n; ++i) {
549     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
550
551     if (get_irn_op(pred) != op_Store)
552       return 0;
553
554     if (mode != get_irn_mode(get_Store_value(pred)) || ptr != get_Store_ptr(pred))
555       return 0;
556
557     info = get_irn_link(pred);
558
559     /* check, if all stores have the same exception flow */
560     if (exc != info->exc_block)
561       return 0;
562
563     /* abort on bad blocks */
564     if (is_Bad(get_nodes_block(store)))
565       return 0;
566
567     /* check if the block has only one output */
568     bl_info = get_irn_link(get_nodes_block(store));
569     if (bl_info->flags)
570       return 0;
571   }
572
573   /*
574    * ok, when we are here, we found all predecessors of a Phi that
575    * are Stores to the same address. That means whatever we do before
576    * we enter the block of the Phi, we do a Store.
577    * So, we can move the store to the current block:
578    *
579    *   val1    val2    val3          val1  val2  val3
580    *    |       |       |               \    |    /
581    * | Str | | Str | | Str |             \   |   /
582    *      \     |     /                     Phi
583    *       \    |    /                       |
584    *        \   |   /                       Str
585    *           Phi
586    *
587    * Is only allowed if the predecessor blocks have only one successor.
588    */
589
590   /* first step: collect all inputs */
591   NEW_ARR_A(ir_node *, inM, n);
592   NEW_ARR_A(ir_node *, inD, n);
593   NEW_ARR_A(int, idx, n);
594
595   for (i = 0; i < n; ++i) {
596     ir_node *pred = skip_Proj(get_Phi_pred(phi, i));
597     info = get_irn_link(pred);
598
599     inM[i] = get_Store_mem(pred);
600     inD[i] = get_Store_value(pred);
601     idx[i] = info->exc_idx;
602   }
603   block = get_nodes_block(phi);
604
605   /* second step: create a new memory Phi */
606   phiM = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inM, mode_M);
607
608   /* third step: create a new data Phi */
609   phiD = new_rd_Phi(get_irn_dbg_info(phi), current_ir_graph, block, n, inD, mode);
610
611   /* fourth step: create the Store */
612   store = new_rd_Store(db, current_ir_graph, block, phiM, ptr, phiD);
613   projM = new_rd_Proj(NULL, current_ir_graph, block, store, mode_M, pn_Store_M);
614
615   info = get_ldst_info(store, wenv);
616   info->projs[pn_Store_M] = projM;
617
618   /* fifths step: repair exception flow */
619   if (exc) {
620     ir_node *projX = new_rd_Proj(NULL, current_ir_graph, block, store, mode_X, pn_Store_X_except);
621
622     info->projs[pn_Store_X_except] = projX;
623     info->exc_block                = exc;
624     info->exc_idx                  = idx[0];
625
626     for (i = 0; i < n; ++i) {
627       set_Block_cfgpred(exc, idx[i], projX);
628     }
629
630     if (n > 1) {
631       /* the exception block should be optimized as some inputs are identical now */
632     }
633   }
634
635   /* sixt step: replace old Phi */
636   exchange(phi, projM);
637
638   return 1;
639 }
640
641 /**
642  * walker, collects all Load/Store/Proj nodes
643  */
644 static void do_load_store_optimize(ir_node *n, void *env)
645 {
646   walk_env_t *wenv = env;
647
648   switch (get_irn_opcode(n)) {
649
650   case iro_Load:
651     wenv->changes |= optimize_load(n);
652     break;
653
654   case iro_Store:
655     wenv->changes |= optimize_store(n);
656     break;
657
658   case iro_Phi:
659     wenv->changes |= optimize_phi(n, env);
660
661   default:
662     ;
663   }
664 }
665
666 /*
667  * do the load store optimization
668  */
669 void optimize_load_store(ir_graph *irg)
670 {
671   walk_env_t env;
672
673   assert(get_irg_phase_state(irg) != phase_building);
674
675   if (!get_opt_redundant_LoadStore())
676     return;
677
678   obstack_init(&env.obst);
679   env.changes = 0;
680
681   /* init the links, then collect Loads/Stores/Proj's in lists */
682   irg_walk_graph(irg, init_links, collect_nodes, &env);
683
684   /* now we have collected enough information, optimize */
685   irg_walk_graph(irg, NULL, do_load_store_optimize, &env);
686
687   obstack_free(&env.obst, NULL);
688
689   /* Handle graph state */
690   if (env.changes) {
691     if (get_irg_outs_state(current_ir_graph) == outs_consistent)
692       set_irg_outs_inconsistent(current_ir_graph);
693
694     /* is this really needed: Yes, as exception block may get bad but this might be tested */
695     if (get_irg_dom_state(current_ir_graph) == dom_consistent)
696       set_irg_dom_inconsistent(current_ir_graph);
697   }
698 }