projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Use backtracking in find_original_value() for the flags emitter.
[libfirm]
/
ir
/
be
/
belive.c
diff --git
a/ir/be/belive.c
b/ir/be/belive.c
index
8f0724d
..
8a81f54
100644
(file)
--- a/
ir/be/belive.c
+++ b/
ir/be/belive.c
@@
-1,5
+1,5
@@
/*
/*
- * Copyright (C) 1995-200
7
University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-200
8
University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
*
* This file is part of libFirm.
*
@@
-36,6
+36,10
@@
#include "irdump_t.h"
#include "irnodeset.h"
#include "irdump_t.h"
#include "irnodeset.h"
+#include "dfs_t.h"
+#include "absgraph.h"
+#include "statev.h"
+
#include "beutil.h"
#include "belive_t.h"
#include "beirg_t.h"
#include "beutil.h"
#include "belive_t.h"
#include "beirg_t.h"
@@
-50,12
+54,16
@@
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
#define LV_USE_BINARY_SEARCH
#undef LV_INTESIVE_CHECKS
#define LV_USE_BINARY_SEARCH
#undef LV_INTESIVE_CHECKS
+void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc);
+
static INLINE int is_liveness_node(const ir_node *irn)
{
switch(get_irn_opcode(irn)) {
case iro_Block:
case iro_Bad:
case iro_End:
static INLINE int is_liveness_node(const ir_node *irn)
{
switch(get_irn_opcode(irn)) {
case iro_Block:
case iro_Bad:
case iro_End:
+ case iro_Anchor:
+ case iro_NoMem:
return 0;
default:;
}
return 0;
default:;
}
@@
-102,15
+110,6
@@
static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned
if(n == 0)
return 0;
if(n == 0)
return 0;
-#if 0
- if(idx < payload[0].u.node.idx)
- return 0;
-
- if(idx > payload[n - 1].u.node.idx)
- return n - 1;
-#endif
-
- /* start a binary search for the requested node. */
while(lo < hi) {
int md = lo + ((hi - lo) >> 1);
unsigned md_idx = payload[md].u.node.idx;
while(lo < hi) {
int md = lo + ((hi - lo) >> 1);
unsigned md_idx = payload[md].u.node.idx;
@@
-162,8
+161,11
@@
static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned
struct _be_lv_info_node_t *be_lv_get(const struct _be_lv_t *li, const ir_node *bl, const ir_node *irn)
{
struct _be_lv_info_node_t *be_lv_get(const struct _be_lv_t *li, const ir_node *bl, const ir_node *irn)
{
- struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);
+ struct _be_lv_info_t *irn_live;
+ struct _be_lv_info_node_t *res = NULL;
+ stat_ev_tim_push();
+ irn_live = phase_get_irn_data(&li->ph, bl);
if(irn_live) {
unsigned idx = get_irn_idx(irn);
if(irn_live) {
unsigned idx = get_irn_idx(irn);
@@
-171,14
+173,15
@@
struct _be_lv_info_node_t *be_lv_get(const struct _be_lv_t *li, const ir_node *b
int pos = _be_liveness_bsearch(irn_live, idx);
/* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
int pos = _be_liveness_bsearch(irn_live, idx);
/* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
- struct _be_lv_info_node_t *re
s
= &irn_live[pos + 1].u.node;
+ struct _be_lv_info_node_t *re
c
= &irn_live[pos + 1].u.node;
/* Check, if the irn is in deed in the array. */
/* Check, if the irn is in deed in the array. */
- if(re
s
->idx == idx)
- re
turn res
;
+ if(re
c
->idx == idx)
+ re
s = rec
;
}
}
+ stat_ev_tim_pop("be_lv_get");
- return
NULL
;
+ return
res
;
}
static struct _be_lv_info_node_t *be_lv_get_or_set(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
}
static struct _be_lv_info_node_t *be_lv_get_or_set(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
@@
-248,7
+251,8
@@
static struct _be_lv_info_node_t *be_lv_get_or_set(struct _be_lv_t *li, ir_node
* Removes a node from the list of live variables of a block.
* @return 1 if the node was live at that block, 0 if not.
*/
* Removes a node from the list of live variables of a block.
* @return 1 if the node was live at that block, 0 if not.
*/
-static int be_lv_remove(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
+static int be_lv_remove(struct _be_lv_t *li, const ir_node *bl,
+ const ir_node *irn)
{
struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);
{
struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);
@@
-364,6
+368,12
@@
struct _lv_walker_t {
void *data;
};
void *data;
};
+typedef struct lv_remove_walker_t {
+ be_lv_t *lv;
+ const ir_node *irn;
+} lv_remove_walker_t;
+
+
/**
* Liveness analysis for a value.
* This functions is meant to be called by a firm walker, to compute the
/**
* Liveness analysis for a value.
* This functions is meant to be called by a firm walker, to compute the
@@
-391,6
+401,9
@@
static void liveness_for_node(ir_node *irn, void *data)
ir_node *use = edge->src;
ir_node *use_block;
ir_node *use = edge->src;
ir_node *use_block;
+ DBG((dbg, LEVEL_4, "%+F: use at %+F, pos %d in %+F\n", irn, use, edge->pos, get_block(use)));
+ assert(get_irn_n(use, edge->pos) == irn);
+
/*
* If the usage is no data node, skip this use, since it does not
* affect the liveness of the node.
/*
* If the usage is no data node, skip this use, since it does not
* affect the liveness of the node.
@@
-430,10
+443,8
@@
static void liveness_for_node(ir_node *irn, void *data)
static void lv_remove_irn_walker(ir_node *bl, void *data)
{
static void lv_remove_irn_walker(ir_node *bl, void *data)
{
- struct _lv_walker_t *w = data;
- be_lv_t *lv = w->lv;
- ir_node *irn = w->data;
- be_lv_remove(lv, bl, irn);
+ lv_remove_walker_t *w = data;
+ be_lv_remove(w->lv, bl, w->irn);
}
static const char *lv_flags_to_str(unsigned flags)
}
static const char *lv_flags_to_str(unsigned flags)
@@
-471,7
+482,7
@@
static void lv_dump_block(void *context, FILE *f, const ir_node *bl)
}
}
}
}
-static void *lv_phase_data_init(ir_phase *phase, ir_node *irn, void *old)
+static void *lv_phase_data_init(ir_phase *phase,
const
ir_node *irn, void *old)
{
struct _be_lv_info_t *info = phase_alloc(phase, LV_STD_SIZE * sizeof(info[0]));
(void) irn;
{
struct _be_lv_info_t *info = phase_alloc(phase, LV_STD_SIZE * sizeof(info[0]));
(void) irn;
@@
-505,6
+516,7
@@
static void compute_liveness(be_lv_t *lv)
ir_node **nodes;
int i, n;
ir_node **nodes;
int i, n;
+ stat_ev_tim_push();
obstack_init(&obst);
irg_walk_graph(lv->irg, collect_nodes, NULL, &obst);
n = obstack_object_size(&obst) / sizeof(nodes[0]);
obstack_init(&obst);
irg_walk_graph(lv->irg, collect_nodes, NULL, &obst);
n = obstack_object_size(&obst) / sizeof(nodes[0]);
@@
-513,7
+525,7
@@
static void compute_liveness(be_lv_t *lv)
/*
* inserting the variables sorted by their ID is probably
* more efficient since the binary sorted set insertion
/*
* inserting the variables sorted by their ID is probably
* more efficient since the binary sorted set insertion
- * will not need to move aroun
f
the data.
+ * will not need to move aroun
d
the data.
* However, if sorting the variables a priori pays off
* needs to be checked, hence the define.
*/
* However, if sorting the variables a priori pays off
* needs to be checked, hence the define.
*/
@@
-529,21
+541,29
@@
static void compute_liveness(be_lv_t *lv)
obstack_free(&obst, NULL);
register_hook(hook_node_info, &lv->hook_info);
obstack_free(&obst, NULL);
register_hook(hook_node_info, &lv->hook_info);
+ stat_ev_tim_pop("be_lv_sets_cons");
}
void be_liveness_assure_sets(be_lv_t *lv)
{
if (!lv->nodes) {
}
void be_liveness_assure_sets(be_lv_t *lv)
{
if (!lv->nodes) {
+ BE_TIMER_PUSH(t_live);
+
lv->nodes = bitset_malloc(2 * get_irg_last_idx(lv->irg));
phase_init(&lv->ph, "liveness", lv->irg, PHASE_DEFAULT_GROWTH, lv_phase_data_init, NULL);
compute_liveness(lv);
lv->nodes = bitset_malloc(2 * get_irg_last_idx(lv->irg));
phase_init(&lv->ph, "liveness", lv->irg, PHASE_DEFAULT_GROWTH, lv_phase_data_init, NULL);
compute_liveness(lv);
+ /* be_live_chk_compare(lv, lv->lvc); */
+
+ BE_TIMER_POP(t_live);
}
}
void be_liveness_assure_chk(be_lv_t *lv)
{
#ifndef USE_LIVE_CHK
}
}
void be_liveness_assure_chk(be_lv_t *lv)
{
#ifndef USE_LIVE_CHK
+ BE_TIMER_PUSH(t_verify);
be_liveness_assure_sets(lv);
be_liveness_assure_sets(lv);
+ BE_TIMER_POP(t_verify);
#else
(void) lv;
#endif
#else
(void) lv;
#endif
@@
-560,14
+580,16
@@
void be_liveness_invalidate(be_lv_t *lv)
}
/* Compute the inter block liveness for a graph. */
}
/* Compute the inter block liveness for a graph. */
-be_lv_t *be_liveness(
ir_graph *
irg)
+be_lv_t *be_liveness(
const be_irg_t *b
irg)
{
be_lv_t *lv = xmalloc(sizeof(lv[0]));
memset(lv, 0, sizeof(lv[0]));
{
be_lv_t *lv = xmalloc(sizeof(lv[0]));
memset(lv, 0, sizeof(lv[0]));
- lv->irg = irg;
+ lv->irg = be_get_birg_irg(birg);
+ lv->birg = birg;
#ifdef USE_LIVE_CHK
#ifdef USE_LIVE_CHK
- lv->lvc = lv_chk_new(irg);
+ lv->dfs = dfs_new(&absgraph_irg_cfg_succ, lv->irg);
+ lv->lvc = lv_chk_new(lv->irg, lv->dfs);
#endif
lv->hook_info.context = lv;
lv->hook_info.hook._hook_node_info = lv_dump_block;
#endif
lv->hook_info.context = lv;
lv->hook_info.hook._hook_node_info = lv_dump_block;
@@
-577,40
+599,47
@@
be_lv_t *be_liveness(ir_graph *irg)
void be_liveness_recompute(be_lv_t *lv)
{
void be_liveness_recompute(be_lv_t *lv)
{
- unsigned last_idx = get_irg_last_idx(lv->irg);
+ unsigned last_idx;
+
+ BE_TIMER_PUSH(t_live);
+ last_idx = get_irg_last_idx(lv->irg);
if(last_idx >= bitset_size(lv->nodes)) {
bitset_free(lv->nodes);
lv->nodes = bitset_malloc(last_idx * 2);
if(last_idx >= bitset_size(lv->nodes)) {
bitset_free(lv->nodes);
lv->nodes = bitset_malloc(last_idx * 2);
- }
-
- else
+ } else
bitset_clear_all(lv->nodes);
phase_free(&lv->ph);
phase_init(&lv->ph, "liveness", lv->irg, PHASE_DEFAULT_GROWTH, lv_phase_data_init, NULL);
compute_liveness(lv);
bitset_clear_all(lv->nodes);
phase_free(&lv->ph);
phase_init(&lv->ph, "liveness", lv->irg, PHASE_DEFAULT_GROWTH, lv_phase_data_init, NULL);
compute_liveness(lv);
+
+ BE_TIMER_POP(t_live);
}
void be_liveness_free(be_lv_t *lv)
{
be_liveness_invalidate(lv);
}
void be_liveness_free(be_lv_t *lv)
{
be_liveness_invalidate(lv);
- free(lv);
+#ifdef USE_LIVE_CHK
+ lv_chk_free(lv->lvc);
+ dfs_free(lv->dfs);
+#endif
+ xfree(lv);
}
}
-void be_liveness_remove(be_lv_t *lv, ir_node *irn)
+void be_liveness_remove(be_lv_t *lv,
const
ir_node *irn)
{
if (lv->nodes) {
unsigned idx = get_irn_idx(irn);
{
if (lv->nodes) {
unsigned idx = get_irn_idx(irn);
-
struct _lv
_walker_t w;
+
lv_remove
_walker_t w;
/*
* Removes a single irn from the liveness information.
* Since an irn can only be live at blocks dominated by the block of its
* definition, we only have to process that dominance subtree.
*/
/*
* Removes a single irn from the liveness information.
* Since an irn can only be live at blocks dominated by the block of its
* definition, we only have to process that dominance subtree.
*/
- w.lv
= lv;
- w.
data
= irn;
+ w.lv = lv;
+ w.
irn
= irn;
dom_tree_walk(get_nodes_block(irn), lv_remove_irn_walker, NULL, &w);
if(idx < bitset_size(lv->nodes))
bitset_clear(lv->nodes, idx);
dom_tree_walk(get_nodes_block(irn), lv_remove_irn_walker, NULL, &w);
if(idx < bitset_size(lv->nodes))
bitset_clear(lv->nodes, idx);
@@
-679,7
+708,7
@@
static void lv_check_walker(ir_node *bl, void *data)
void be_liveness_check(be_lv_t *lv)
{
struct _lv_walker_t w;
void be_liveness_check(be_lv_t *lv)
{
struct _lv_walker_t w;
- be_lv_t *fresh = be_liveness(lv->irg);
+ be_lv_t *fresh = be_liveness(lv->
b
irg);
w.lv = lv;
w.data = fresh;
w.lv = lv;
w.data = fresh;
@@
-769,7
+798,6
@@
void be_liveness_transfer(const arch_env_t *arch_env,
* function. */
assert(!is_Phi(node) && "liveness_transfer produces invalid results for phi nodes");
* function. */
assert(!is_Phi(node) && "liveness_transfer produces invalid results for phi nodes");
-#ifndef SCHEDULE_PROJS
if (get_irn_mode(node) == mode_T) {
const ir_edge_t *edge;
if (get_irn_mode(node) == mode_T) {
const ir_edge_t *edge;
@@
-780,10
+808,7
@@
void be_liveness_transfer(const arch_env_t *arch_env,
ir_nodeset_remove(nodeset, proj);
}
}
ir_nodeset_remove(nodeset, proj);
}
}
- }
-#endif
-
- if (arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
+ } else if (arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
ir_nodeset_remove(nodeset, node);
}
ir_nodeset_remove(nodeset, node);
}
@@
-878,11
+903,12
@@
void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc)
obstack_ptr_grow(&obst, NULL);
nodes = obstack_finish(&obst);
obstack_ptr_grow(&obst, NULL);
nodes = obstack_finish(&obst);
- for (i = 0; blocks[i]; ++i) {
- ir_node *bl = blocks[i];
+ stat_ev_ctx_push("be_lv_chk_compare");
+ for (j = 0; nodes[j]; ++j) {
+ ir_node *irn = nodes[j];
+ for (i = 0; blocks[i]; ++i) {
+ ir_node *bl = blocks[i];
- for (j = 0; nodes[j]; ++j) {
- ir_node *irn = nodes[j];
if (!is_Block(irn)) {
int lvr_in = be_is_live_in (lv, bl, irn);
int lvr_out = be_is_live_out(lv, bl, irn);
if (!is_Block(irn)) {
int lvr_in = be_is_live_in (lv, bl, irn);
int lvr_out = be_is_live_out(lv, bl, irn);
@@
-903,7
+929,7
@@
void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc)
}
}
}
}
}
}
-
+ stat_ev_ctx_pop("be_lv_chk_compare");
obstack_free(&obst, NULL);
}
obstack_free(&obst, NULL);
}