From 2eb0f163fcef20607832ad540b68ee1e33b51007 Mon Sep 17 00:00:00 2001 From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= Date: Thu, 2 Sep 2004 14:15:05 +0000 Subject: [PATCH] more analyses for cache optimization [r3815] --- ir/ana/Makefile.in | 4 +- ir/ana/callgraph.c | 81 +++++++++++++---- ir/ana/callgraph.h | 6 ++ ir/ana/field_temperature.c | 177 +++++++++++++++++++++++++++++++++++++ ir/ana/field_temperature.h | 49 ++++++++++ ir/ir/irprog_t.h | 2 + 6 files changed, 301 insertions(+), 18 deletions(-) create mode 100644 ir/ana/field_temperature.c create mode 100644 ir/ana/field_temperature.h diff --git a/ir/ana/Makefile.in b/ir/ana/Makefile.in index 636fe51cb..d240c95cc 100644 --- a/ir/ana/Makefile.in +++ b/ir/ana/Makefile.in @@ -16,7 +16,7 @@ topdir = ../.. subdir := ir/ana INSTALL_HEADERS = irouts.h irdom.h cgana.h irloop.h irtypeinfo.h irsimpletype.h rta.h \ - callgraph.h + callgraph.h field_temperature.h SOURCES = $(INSTALL_HEADERS) @@ -24,7 +24,7 @@ SOURCES += Makefile.in \ irouts.c irdom_t.h irdom.c cgana.c rta.c \ irloop_t.h irbackedge.c irbackedge_t.h irscc.c ircfscc.c \ irtypeinfo.c irsimpletype.c \ - callgraph.c + callgraph.c field_temperature.c include $(topdir)/MakeRules diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c index 41b9f7a50..d0244c8ce 100644 --- a/ir/ana/callgraph.c +++ b/ir/ana/callgraph.c @@ -18,6 +18,8 @@ #include "irgraph_t.h" #include "irnode_t.h" +#include "cgana.h" + #include "array.h" #include "pmap.h" @@ -520,7 +522,6 @@ init_scc (void) { set_irg_link(get_irp_irg(i), new_scc_info()); get_irp_irg(i)->callgraph_recursion_depth = 0; get_irp_irg(i)->callgraph_loop_depth = 0; - get_irp_irg(i)->callgraph_weighted_loop_depth = 0; } } @@ -891,12 +892,27 @@ static void reset_isbe(void) { void compute_loop_depth (ir_graph *irg, void *env) { int current_nesting = *(int *) env; + int old_nesting = irg->callgraph_loop_depth; + int old_visited = get_cg_irg_visited(irg); int i, n_callees; + //return ; + if (cg_irg_visited(irg)) return; + mark_cg_irg_visited(irg); - if (current_nesting == 0 || irg->callgraph_loop_depth < current_nesting) { + //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg); + + + if (old_nesting < current_nesting) + irg->callgraph_loop_depth = current_nesting; + + if (current_nesting > irp->max_callgraph_loop_depth) + irp->max_callgraph_loop_depth = current_nesting; + + if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */ + (old_nesting < current_nesting)) { /* propagate larger nesting */ /* Don't walk the graph, but a tree that is an unfolded graph. */ n_callees = get_irg_n_callees(irg); for (i = 0; i < n_callees; i++) { @@ -907,9 +923,6 @@ void compute_loop_depth (ir_graph *irg, void *env) { } } - if (irg->callgraph_loop_depth < current_nesting) - irg->callgraph_loop_depth = current_nesting; - set_cg_irg_visited(irg, master_cg_visited-1); } @@ -956,13 +969,14 @@ static int in_stack(ana_entry2 *e, ir_loop *g) { void compute_rec_depth (ir_graph *irg, void *env) { ana_entry2 *e = (ana_entry2 *)env; ir_loop *l = irg->l; - int depth; + int depth, old_depth = irg->callgraph_recursion_depth; int i, n_callees; int pushed = 0; if (cg_irg_visited(irg)) return; mark_cg_irg_visited(irg); + /* -- compute and set the new nesting value -- */ if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) { push2(e, l); e->recursion_nesting++; @@ -970,7 +984,14 @@ void compute_rec_depth (ir_graph *irg, void *env) { } depth = e->recursion_nesting; - if (depth == 0 || irg->callgraph_recursion_depth < depth) { + if (old_depth < depth) + irg->callgraph_recursion_depth = depth; + + if (depth > irp->max_callgraph_recursion_depth) + irp->max_callgraph_recursion_depth = depth; + + /* -- spread the nesting value -- */ + if (depth == 0 || old_depth < depth) { /* Don't walk the graph, but a tree that is an unfolded graph. */ n_callees = get_irg_n_callees(irg); for (i = 0; i < n_callees; i++) { @@ -979,9 +1000,7 @@ void compute_rec_depth (ir_graph *irg, void *env) { } } - if (irg->callgraph_recursion_depth < depth) - irg->callgraph_recursion_depth = depth; - + /* -- clean up -- */ if (pushed) { pop2(e); e->recursion_nesting--; @@ -1032,38 +1051,52 @@ void find_callgraph_recursions(void) { } } - /* -- Schleifentiefe berechnen -- */ + /* -- compute the loop depth -- */ int current_nesting = 0; + irp->max_callgraph_loop_depth = 0; master_cg_visited += 2; + //printf (" ** starting at "); DDMG(get_irp_main_irg()); compute_loop_depth(get_irp_main_irg(), ¤t_nesting); for (i = 0; i < n_irgs; i++) { ir_graph *irg = get_irp_irg(i); - if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0) + if ((get_cg_irg_visited(irg) < master_cg_visited-1) && + get_irg_n_callers(irg) == 0) { compute_loop_depth(irg, ¤t_nesting); + //printf (" ** starting at "); DDMG(irg); + } } for (i = 0; i < n_irgs; i++) { ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) + if (get_cg_irg_visited(irg) < master_cg_visited-1) { compute_loop_depth(irg, ¤t_nesting); + //printf (" ** starting at "); DDMG(irg); + } } - /* -- Rekursionstiefe berechnen -- */ + /* -- compute the recursion depth -- */ ana_entry2 e; e.loop_stack = NEW_ARR_F(ir_loop *, 0); e.tos = 0; e.recursion_nesting = 0; + irp->max_callgraph_recursion_depth = 0; master_cg_visited += 2; compute_rec_depth(get_irp_main_irg(), &e); + //printf (" ++ starting at "); DDMG(get_irp_main_irg()); for (i = 0; i < n_irgs; i++) { ir_graph *irg = get_irp_irg(i); - if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0) + if ((get_cg_irg_visited(irg) < master_cg_visited-1) && + get_irg_n_callers(irg) == 0) { compute_rec_depth(irg, &e); + //printf (" ++ starting at "); DDMG(irg); + } } for (i = 0; i < n_irgs; i++) { ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) + if (get_cg_irg_visited(irg) < master_cg_visited-1) { compute_rec_depth(irg, &e); + //printf (" ++ starting at "); DDMG(irg); + } } DEL_ARR_F(e.loop_stack); @@ -1088,3 +1121,19 @@ int get_irg_recursion_depth(ir_graph *irg) { assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent); return irg->callgraph_recursion_depth; } + +void analyse_loop_nesting_depth(void) { + entity **free_methods = NULL; + int arr_len; + + /* establish preconditions. */ + if (get_irp_callee_info_state() != irg_callee_info_consistent) { + cgana(&arr_len, &free_methods, 0); + } + + if (irp_callgraph_consistent != get_irp_callgraph_state()) { + compute_callgraph(); + } + + find_callgraph_recursions(); +} diff --git a/ir/ana/callgraph.h b/ir/ana/callgraph.h index 03ed3ab4d..abedeef00 100644 --- a/ir/ana/callgraph.h +++ b/ir/ana/callgraph.h @@ -85,6 +85,12 @@ void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *e void find_callgraph_recursions(void); +/** Computes the loop nesting information. + * + * Computes callee info and the callgraph if + * this information is not available. + */ +void analyse_loop_nesting_depth(void); #endif /* _CALLGRAPH_H_ */ diff --git a/ir/ana/field_temperature.c b/ir/ana/field_temperature.c new file mode 100644 index 000000000..ca3131743 --- /dev/null +++ b/ir/ana/field_temperature.c @@ -0,0 +1,177 @@ +/* + * Project: libFIRM + * File name: ir/ana/field_temperature.c + * Purpose: Compute an estimate of field temperature, i.e., field access heuristic. + * Author: Goetz Lindenmaier + * Modified by: + * Created: 21.7.2004 + * CVS-ID: $Id$ + * Copyright: (c) 2004 Universität Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#include "field_temperature.h" + +#include "irnode_t.h" +#include "irgraph_t.h" +#include "irprog_t.h" +#include "entity_t.h" +#include "irgwalk.h" + +#include "array.h" + +/* *************************************************************************** */ +/* initialize, global variables. */ +/* *************************************************************************** */ + +/* A list of Load and Store operations that have no analyseable address. */ +static ir_node **unrecognized_access = NULL; + +static void add_unrecognized_access(ir_node *n) { + ARR_APP1(ir_node *, unrecognized_access, n); +} + +/* *************************************************************************** */ +/* Access routines for entities */ +/* *************************************************************************** */ + +/* The entities that can be accessed by this Sel node. */ +int get_Sel_n_accessed_entities(ir_node *sel) { + return 1; +} + +entity *get_Sel_accessed_entity(ir_node *sel, int pos) { + return get_Sel_entity(sel); +} + +int get_entity_n_accesses(entity *ent) { + assert(ent && is_entity(ent)); + + if (!ent->accesses) { ent->accesses = NEW_ARR_F(ir_node *, 0); } + + return ARR_LEN(ent->accesses); +} + +ir_node *get_entity_access(entity *ent, int pos) { + assert(0 <= pos && pos < get_entity_n_accesses(ent)); + + return ent->accesses[pos]; +} + +void add_entity_access(entity *ent, ir_node *n) { + assert(ent && is_entity(ent)); + assert(n && is_ir_node(n)); + + if (!ent->accesses) ent->accesses = NEW_ARR_F(ir_node *, 0); + + ARR_APP1(ir_node *, ent->accesses, n); +} + +void set_entity_access(entity *ent, int pos, ir_node *n) { + assert(0 <= pos && pos < get_entity_n_accesses(ent)); + assert(n && is_ir_node(n)); + + ent->accesses[pos] = n; +} + + +/* *************************************************************************** */ +/* Access routines for nodes */ +/* *************************************************************************** */ + +/* An addr node is a SymConst or a Sel. */ +int get_addr_n_entities(ir_node *addr) { + int n_ents; + + switch (get_irn_opcode(addr)) { + case iro_Sel: + /* Treat jack array sels? */ + n_ents = get_Sel_n_accessed_entities(addr); + break; + case iro_SymConst: + if (get_SymConst_kind(addr) == symconst_addr_ent) { + n_ents = 1; + break; + } + default: + //assert(0 && "unexpected address expression"); + n_ents = 0; + } + + return n_ents; +} + +/* An addr node is a SymConst or a Sel. */ +entity *get_addr_entity(ir_node *addr, int pos) { + entity *ent; + + switch (get_irn_opcode(addr)) { + case iro_Sel: + /* Treat jack array sels? */ + assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr)); + ent = get_Sel_accessed_entity(addr, pos); + break; + case iro_SymConst: + if (get_SymConst_kind(addr) == symconst_addr_ent) { + assert(pos == 0); + ent = get_SymConst_entity(addr); + break; + } + default: + ent = NULL; + } + + return ent; +} + +/* *************************************************************************** */ +/* The analyses */ +/* *************************************************************************** */ + +void init_field_temperature(void) { + assert(!unrecognized_access); + unrecognized_access = NEW_ARR_F(ir_node *, 0); +} + + +void chain_accesses(ir_node *n, void *env) { + int i, n_ents; + ir_node *addr; + + if (get_irn_op(n) == op_Load) { + addr = get_Load_ptr(n); + } else if (get_irn_op(n) == op_Store) { + addr = get_Store_ptr(n); + } else { + return; + } + + n_ents = get_addr_n_entities(addr); + for (i = 0; i < n_ents; ++i) { + entity *ent = get_addr_entity(addr, i); + if (ent) + add_entity_access(ent, n); + else + add_unrecognized_access(n); + } +} + + +/* compute the field temperature. */ +void compute_field_temperature(void) { + + int i, n_irgs = get_irp_n_irgs(); + + init_field_temperature(); + + for (i=0; i < n_irgs; i++) { + current_ir_graph = get_irp_irg(i); + irg_walk_graph(current_ir_graph, NULL, chain_accesses, NULL); + } +} + +/* free occupied memory, reset */ +void free_field_temperature(void) { + DEL_ARR_F(unrecognized_access); + unrecognized_access = NULL; +} diff --git a/ir/ana/field_temperature.h b/ir/ana/field_temperature.h new file mode 100644 index 000000000..ca3836852 --- /dev/null +++ b/ir/ana/field_temperature.h @@ -0,0 +1,49 @@ +/* + * Project: libFIRM + * File name: ir/ana/field_temperature.h + * Purpose: Compute an estimate of field temperature, i.e., field access heuristic. + * Author: Goetz Lindenmaier + * Modified by: + * Created: 21.7.2004 + * CVS-ID: $Id$ + * Copyright: (c) 2004 Universität Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +#ifndef _FIELD_TEMPERATURE_H_ +#define _FIELD_TEMPERATURE_H_ + +/** + * @file field_temperature.h + * + * Watch it! This is highly java dependent. + * + * - All Sel nodes get an array with possibly accessed entities. + * (resolve polymorphy on base of inherited entities.) + * (the mentioned entity in first approximation.) + * + * - Each entity gets all SymConst/Sel nodes, that reference the + * entity (Sel: references as accessed entity.) + * + * - We compute a value for the entity based on the Sel nodes. + */ + +#include "irnode.h" +#include "entity.h" + + +/** The entities that can be accessed by this Sel node. */ +int get_Sel_n_accessed_entities(ir_node *sel); +entity *get_Sel_accessed_entity(ir_node *sel, int pos); + + + + + +/** compute the field temperature. */ +void compute_field_temperature(void); + +/** free occupied memory, reset */ +void free_field_temperature(void); + +#endif /* _FIELD_TEMPERATURE_H_ */ diff --git a/ir/ir/irprog_t.h b/ir/ir/irprog_t.h index 83f154688..8b003fbce 100644 --- a/ir/ir/irprog_t.h +++ b/ir/ir/irprog_t.h @@ -61,6 +61,8 @@ struct ir_prog { irp_callgraph_state callgraph_state; /**< State of the callgraph. */ struct ir_loop *outermost_cg_loop; /**< For callgraph analysis: entry point to looptree over callgraph. */ + int max_callgraph_loop_depth; + int max_callgraph_recursion_depth; #ifdef DEBUG_libfirm long max_node_nr; /**< to generate unique numbers for nodes. */ -- 2.20.1