X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbelive_t.h;h=06ea057f70b7d0cb4594f3dd68e7d8891689d5ec;hb=0ada12ba1e11d8ff2e39e3183eb43c4783df2d91;hp=f8085115125326a078ede07160ad94423524f502;hpb=9b24fe0ec0f4412c790ee4a7c6fc022fd28064a1;p=libfirm diff --git a/ir/be/belive_t.h b/ir/be/belive_t.h index f80851151..06ea057f7 100644 --- a/ir/be/belive_t.h +++ b/ir/be/belive_t.h @@ -1,131 +1,135 @@ -/** - * Internal headers for liveness analysis. - * @author Sebastian Hack - * @date 6.12.2004 +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifndef _BELIVE_T_H -#define _BELIVE_T_H - -#include "config.h" - -#include "irgraph_t.h" +/** + * @file + * @brief Internal headers for liveness analysis. + * @author Sebastian Hack + * @date 06.12.2004 + */ +#ifndef FIRM_BE_BELIVE_T_H +#define FIRM_BE_BELIVE_T_H +#include +#include "irnodehashmap.h" +#include "irhooks.h" +#include "irlivechk.h" #include "belive.h" -#include "pset.h" -#include "set.h" -#include "list.h" -#include "hashptr.h" - -typedef enum _live_state_t { - live_state_in = 1, - live_state_end = 2, - live_state_out = 6, - live_state_block = 8, -} live_state_t; - -typedef struct _irn_live_t { - const ir_node *block; - const ir_node *irn; - unsigned state; - struct _irn_live_t *next; -} irn_live_t; - -typedef struct _irg_live_info_t { - set *live; -} irg_live_info_t; - -extern size_t live_irg_data_offset; - -#define get_irg_live_info(irg) (get_irg_data(irg, irg_live_info_t, live_irg_data_offset)) - -#define HASH_PTR_PAIR(x,y) (HASH_PTR(x) + 37 * HASH_PTR(y)) - -static INLINE irn_live_t *_get_or_set_live(const ir_node *block, const ir_node *irn, int state) +#include "bearch.h" + +#define be_is_live_in(lv, bl, irn) _be_is_live_xxx(lv, bl, irn, be_lv_state_in) +#define be_is_live_end(lv, bl, irn) _be_is_live_xxx(lv, bl, irn, be_lv_state_end) +#define be_is_live_out(lv, bl, irn) _be_is_live_xxx(lv, bl, irn, be_lv_state_out) + +struct be_lv_t { + ir_nodehashmap_t map; + struct obstack obst; + bool sets_valid; + ir_graph *irg; + lv_chk_t *lvc; +}; + +typedef struct be_lv_info_node_t be_lv_info_node_t; +struct be_lv_info_node_t { + ir_node *node; + unsigned flags; +}; + +struct be_lv_info_head_t { + unsigned n_members; + unsigned n_size; +}; + +union be_lv_info_t { + struct be_lv_info_head_t head; + struct be_lv_info_node_t node; +}; + +be_lv_info_node_t *be_lv_get(const be_lv_t *li, const ir_node *block, + const ir_node *irn); + +static inline unsigned _be_is_live_xxx(const be_lv_t *li, const ir_node *block, + const ir_node *irn, unsigned flags) { - irg_live_info_t *live_info = get_irg_live_info(get_irn_irg(block)); - irn_live_t *live, templ; - - templ.block = block; - templ.irn = irn; - templ.state = -1; - templ.next = NULL; - - live = set_insert(live_info->live, &templ, sizeof(templ), HASH_PTR_PAIR(block, irn)); - if(live->state == -1) { - - if(!is_Block(irn)) { - irn_live_t *bl_live = _get_or_set_live(block, block, live_state_block); - live->next = bl_live->next; - bl_live->next = live; - } - - live->state = state; - } + unsigned res; - live->state |= state; + if (li->sets_valid) { + be_lv_info_node_t *info = be_lv_get(li, block, irn); + res = info != NULL ? (info->flags & flags) != 0 : 0; + } else { + res = (lv_chk_bl_xxx(li->lvc, block, irn) & flags) != 0; + } - return live; + return res; } -static INLINE int _is_live_in(const ir_node *block, const ir_node *irn) +typedef struct lv_iterator_t { - return (_get_or_set_live(block, irn, 0)->state & live_state_in) != 0; -} - -static INLINE int _is_live_out(const ir_node *block, const ir_node *irn) -{ - return (_get_or_set_live(block, irn, 0)->state & live_state_out) != 0; -} + be_lv_info_t *info; + size_t i; +} lv_iterator_t; -static INLINE int _is_live_end(const ir_node *block, const ir_node *irn) +static inline lv_iterator_t be_lv_iteration_begin(const be_lv_t *lv, + const ir_node *block) { - return (_get_or_set_live(block, irn, 0)->state & live_state_end) != 0; + lv_iterator_t res; + res.info = ir_nodehashmap_get(be_lv_info_t, &lv->map, block); + res.i = res.info != NULL ? res.info[0].head.n_members : 0; + return res; } -#define live_foreach(block, live_info) \ - for(live_info = _get_or_set_live(block, block, 0)->next; live_info; live_info = live_info->next) - -static INLINE void _put_live(const ir_node *block, int state, pset *s) +static inline ir_node *be_lv_iteration_next(lv_iterator_t *iterator, be_lv_state_t flags) { - irn_live_t *live; - - live_foreach(block, live) { - if(live->state & state) - pset_insert_ptr(s, live->irn); - } + while (iterator->i != 0) { + const be_lv_info_t *info = iterator->info + iterator->i--; + if (info->node.flags & flags) + return info->node.node; + } + return NULL; } -static INLINE pset *_put_live_in(const ir_node *block, pset *s) +static inline ir_node *be_lv_iteration_cls_next(lv_iterator_t *iterator, be_lv_state_t flags, const arch_register_class_t *cls) { - _put_live(block, live_state_in, s); - return s; + while (iterator->i != 0) { + const be_lv_info_t *info = iterator->info + iterator->i--; + if (!(info->node.flags & flags)) + continue; + + ir_node *node = info->node.node; + ir_mode *mode = get_irn_mode(node); + if (!mode_is_datab(mode)) + continue; + if (!arch_irn_consider_in_reg_alloc(cls, node)) + continue; + return node; + } + return NULL; } -static INLINE pset *_put_live_out(const ir_node *block, pset *s) -{ - _put_live(block, live_state_out, s); - return s; -} +#define be_lv_foreach(lv, block, flags, node) \ + for (bool once = true; once;) \ + for (lv_iterator_t iter = be_lv_iteration_begin((lv), (block)); once; once = false) \ + for (ir_node *node; (node = be_lv_iteration_next(&iter, (flags))) != NULL;) -static INLINE pset *_put_live_end(const ir_node *block, pset *s) -{ - _put_live(block, live_state_end, s); - return s; -} - - -#define is_live_in(bl,irn) _is_live_in(bl, irn) -#define is_live_out(bl,irn) _is_live_out(bl, irn) -#define is_live_end(bl,irn) _is_live_end(bl, irn) -#define put_live_in(bl,s) _put_live_in(bl, s) -#define put_live_out(bl,s) _put_live_out(bl, s) -#define put_live_end(bl,s) _put_live_end(bl, s) - -/** - * Initialize the liveness module. - * To be called from be_init(). - */ -void be_liveness_init(void); +#define be_lv_foreach_cls(lv, block, flags, cls, node) \ + for (bool once = true; once;) \ + for (lv_iterator_t iter = be_lv_iteration_begin((lv), (block)); once; once = false) \ + for (ir_node *node; (node = be_lv_iteration_cls_next(&iter, (flags), (cls))) != NULL;) #endif