From d26125ca5720072a4975d37c0a17f7ad6c18de2d Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Wed, 8 Dec 2004 08:55:19 +0000 Subject: [PATCH] Added some backend stuff. nothing big, just a basis. --- ir/be/Makefile.in | 36 +++++ ir/be/be.h | 8 + ir/be/belistsched.c | 356 ++++++++++++++++++++++++++++++++++++++++++++ ir/be/belistsched.h | 52 +++++++ ir/be/belive.c | 181 ++++++++++++++++++++++ ir/be/belive.h | 41 +++++ ir/be/belive_t.h | 62 ++++++++ ir/be/bemain.c | 36 +++++ ir/be/besched.c | 47 ++++++ ir/be/besched.h | 12 ++ ir/be/besched_t.h | 120 +++++++++++++++ ir/be/beutil.h | 42 ++++++ 12 files changed, 993 insertions(+) create mode 100644 ir/be/Makefile.in create mode 100644 ir/be/be.h create mode 100644 ir/be/belistsched.c create mode 100644 ir/be/belistsched.h create mode 100644 ir/be/belive.c create mode 100644 ir/be/belive.h create mode 100644 ir/be/belive_t.h create mode 100644 ir/be/bemain.c create mode 100644 ir/be/besched.c create mode 100644 ir/be/besched.h create mode 100644 ir/be/besched_t.h create mode 100644 ir/be/beutil.h diff --git a/ir/be/Makefile.in b/ir/be/Makefile.in new file mode 100644 index 000000000..2b4b5b4f7 --- /dev/null +++ b/ir/be/Makefile.in @@ -0,0 +1,36 @@ +# +# Project: libFIRM +# File name: ir/ir/Makefile.in +# Purpose: +# Author: Boris Boesler, Till Riedel +# Modified by: +# Created: +# CVS-ID: $Id$ +# Copyright: (c) 1999-2003 Universität Karlsruhe +# Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. +# + +top_srcdir := @top_srcdir@ +srcdir = @srcdir@ +topdir = ../.. +subdir := ir/be + +INSTALL_HEADERS = be.h + +SOURCES = $(INSTALL_HEADERS) + +SOURCES += Makefile.in besched.h belistsched.h belistsched.c \ + beutil.h bemain.c besched.c bemain.c belive.c belive.h + + +include $(topdir)/MakeRules + +CPPFLAGS += -I$(top_srcdir)/ir/adt -I$(top_srcdir)/ir/ir -I$(top_srcdir)/ir/common \ + -I$(top_srcdir)/ir/ident -I$(top_srcdir)/ir/tr -I$(top_srcdir)/ir/tv \ + -I$(top_srcdir)/ir/debug -I$(top_srcdir)/ir/ana -I$(top_srcdir)/ir/st \ + -I$(top_srcdir)/ir/stat -I$(top_srcdir)/ir/external -I$(top_srcdir)/ir/ana2 \ + -I$(topdir)/ir/config + +include $(top_srcdir)/MakeTargets + +all: subdir.o diff --git a/ir/be/be.h b/ir/be/be.h new file mode 100644 index 000000000..3967a6ba6 --- /dev/null +++ b/ir/be/be.h @@ -0,0 +1,8 @@ + +#ifndef _BE_MAIN_H +#define _BE_MAIN_H + +void be_init(void); +void be_main(int argc, const char *argv[]); + +#endif diff --git a/ir/be/belistsched.c b/ir/be/belistsched.c new file mode 100644 index 000000000..d898439b9 --- /dev/null +++ b/ir/be/belistsched.c @@ -0,0 +1,356 @@ +/** + * Scheduling algorithms. + * Just a simple list scheduling algorithm is here. + * @date 20.10.2004 + * @author Sebastian Hack + */ + +#include +#include +#include + +#include "fourcc.h" +#include "obst.h" +#include "irouts.h" +#include "irgwalk.h" +#include "irnode_t.h" +#include "irmode_t.h" +#include "list.h" +#include "iterator.h" +#include "irdump.h" +#include "irprintf_t.h" + +#include "besched_t.h" +#include "beutil.h" +#include "belistsched.h" + +/** + * Scheduling environment for the whole graph. + */ +typedef struct _sched_env_t { + const ir_graph *irg; /**< The graph to schedule. */ + list_sched_selector_t *select; /**< The node selector. */ + void *select_env; /**< A pointer to give to the selector. */ +} sched_env_t; + +ir_node *trivial_selector(void *env, ir_node *block, int curr_time, + pset *already_scheduled, pset *ready_list) +{ + ir_node *res = pset_first(ready_list); + pset_break(ready_list); + return res; +} + +static void list_sched_block(ir_node *block, void *env_ptr); + +void list_sched(ir_graph *irg, list_sched_selector_t *selector, void *select_env) +{ + sched_env_t env; + + memset(&env, 0, sizeof(env)); + env.select = selector; + env.select_env = select_env; + env.irg = irg; + + /* Normalize proj nodes. */ + normalize_proj_nodes(irg); + + /* Compute the outs */ + if(get_irg_outs_state(irg) != outs_consistent) + compute_outs(irg); + + /* Dump the graph. */ + dump_ir_block_graph(irg, "-before-sched"); + + /* Schedule each single block. */ + irg_block_walk_graph(irg, list_sched_block, NULL, &env); +} + + +/** + * Environment for a block scheduler. + */ +typedef struct _block_sched_env_t { + int curr_time; + pset *ready_set; + pset *already_scheduled; + ir_node *block; +} block_sched_env_t; + + + +/** + * Checks, if a node is to appear in a schedule. Such nodes either + * consume real data (mode datab) or produce such. + * @param irn The node to check for. + * @return 1, if the node consumes/produces data, false if not. + */ +static INLINE int to_appear_in_schedule(ir_node *irn) +{ + int i, n; + + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + if(mode_is_datab(get_irn_mode(op))) + return 1; + } + + return mode_is_datab(get_irn_mode(irn)); +} + + +/** + * Try to put a node in the ready set. + * @param env The block scheduler environment. + * @param irn The node to make ready. + * @return 1, if the node could be made ready, 0 else. + */ +static INLINE int make_ready(block_sched_env_t *env, ir_node *irn) +{ + int i, n; + + /* Blocks cannot be scheduled. */ + if(is_Block(irn)) + return 0; + + /* + * Check, if the given ir node is in a different block as the + * currently scheduled one. If that is so, don't make the node ready. + */ + if(env->block != get_nodes_block(irn)) + return 0; + + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + + /* If the operand is local to the scheduled block and not yet + * scheduled, this nodes cannot be made ready, so exit. */ + if(!pset_find_ptr(env->already_scheduled, op) && get_nodes_block(op) == env->block) + return 0; + } + + ir_debugf("\tmaking ready: %n\n", irn); + pset_insert_ptr(env->ready_set, irn); + + return 1; +} + +/** + * Check, if a node is ready in a block schedule. + * @param env The block schedule environment. + * @param irn The node to check for. + * @return 1 if the node was ready, 0 if not. + */ +#define is_ready(env,irn) \ + (pset_find_ptr((env)->ready_set, irn) != NULL) + +/** + * Check, if a node has already been schedules. + * @param env The block schedule environment. + * @param irn The node to check for. + * @return 1 if the node was already scheduled, 0 if not. + */ +#define is_scheduled(env,irn) \ + (pset_find_ptr((env)->already_scheduled, irn) != NULL) + +/** + * Try, to make all users of a node ready. + * In fact, a usage node can only be made ready, if all its operands + * have already been scheduled yet. This is checked my make_ready(). + * @param env The block schedule environment. + * @param irn The node, which usages (successors) are to be made ready. + */ +static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn) +{ + int i, n; + + for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { + ir_node *user = get_irn_out(irn, i); + make_ready(env, user); + } +} + +/** + * Compare to nodes using pointer equality. + * @param p1 Node one. + * @param p2 Node two. + * @return 0 if they are identical. + */ +static int node_cmp_func(const void *p1, const void *p2) +{ + return p1 != p2; +} + +/** + * Append an instruction to a schedule. + * @param env The block scheduleing environment. + * @param irn The node to add to the schedule. + * @return The given node. + */ +static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn) +{ + /* If the node consumes/produces data, it is appended to the schedule + * list, otherwise, it is not put into the list */ + if(to_appear_in_schedule(irn)) { + sched_info_t *info = get_irn_sched_info(irn); + INIT_LIST_HEAD(&info->list); + sched_add(env->block, irn); + + ir_debugf("\tadding %n\n", irn); + } + + /* Insert the node in the set of all already scheduled nodes. */ + pset_insert_ptr(env->already_scheduled, irn); + + /* Remove the node from the ready set */ + if(pset_find_ptr(env->ready_set, irn)) + pset_remove_ptr(env->ready_set, irn); + + return irn; +} + + +/** + * Add the proj nodes of a tuple-mode irn to the schedule immediately + * after the tuple-moded irn. By pinning the projs after the irn, no + * other nodes can create a new lifetime between the tuple-moded irn and + * one of its projs. This should render a realistic image of a + * tuple-moded irn, which in fact models a node which defines multiple + * values. + * + * @param irn The tuple-moded irn. + * @param list The schedule list to append all the projs. + * @param time The time step to which the irn and all its projs are + * related to. + * @param obst The obstack the scheduling data structures shall be + * created upon. + * @param ready_set The ready set of the list scheduler. + * @param already_scheduled A set containing all nodes already + * scheduled. + */ +static void add_tuple_projs(block_sched_env_t *env, ir_node *irn) +{ + int i, n; + assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple"); + + for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { + ir_node *out = get_irn_out(irn, i); + + assert(is_Proj(out) && "successor of a modeT node must be a proj"); + + if(get_irn_mode(out) == mode_T) + add_tuple_projs(env, out); + else { + add_to_sched(env, out); + make_users_ready(env, out); + } + } +} + +/** + * Perform list scheduling on a block. + * + * Note, that the caller must compute a linked list of nodes in the block + * using the link field before calling this function. + * + * Also the outs must have been computed. + * + * @param block The block node. + * @param env Schedulting environment. + */ +static void list_sched_block(ir_node *block, void *env_ptr) +{ + sched_env_t *env = env_ptr; + block_sched_env_t be; + + ir_node *irn; + int j, m; + int phi_seen = 0; + sched_info_t *info = get_irn_sched_info(block); + + /* Initialize the block's list head that will hold the schedule. */ + INIT_LIST_HEAD(&info->list); + + /* Initialize the block scheduling environment */ + be.block = block; + be.curr_time = 0; + be.ready_set = new_pset(node_cmp_func, get_irn_n_outs(block)); + be.already_scheduled = new_pset(node_cmp_func, get_irn_n_outs(block)); + + ir_debugf("scheduling %n\n", block); + + /* Then one can add all nodes are ready to the set. */ + for(int i = 0, n = get_irn_n_outs(block); i < n; ++i) { + ir_node *irn = get_irn_out(block, i); + + /* Phi functions are scheduled immediately, since they only transfer + * data flow from the predecessors to this block. */ + if(is_Phi(irn)) { + add_to_sched(&be, irn); + make_users_ready(&be, irn); + phi_seen = 1; + } + + /* Other nodes must have all operands in other blocks to be made + * ready */ + else { + bool ready = true; + + /* Check, if the operands of a node are not local to this block */ + for(j = 0, m = get_irn_arity(irn); j < m; ++j) { + ir_node *operand = get_irn_n(irn, j); + + if(get_nodes_block(operand) == block) { + ready = false; + break; + } + } + + /* Make the node ready, if all operands live in a foreign block */ + if(ready) { + ir_debugf("\timmediately ready: %n\n", irn); + make_ready(&be, irn); + } + } + } + + /* Increase the time, if some phi functions have been scheduled */ + be.curr_time += phi_seen; + + while(pset_count(be.ready_set) > 0) { + ir_debugf("\tready set: %*n\n", pset_iterator, be.ready_set); + // pset_print(stdout, be.ready_set, irn_printer); + + /* select a node to be scheduled and check if it was ready */ + irn = env->select(env->select_env, block, be.curr_time, + be.already_scheduled, be.ready_set); + + ir_debugf("\tpicked node %n\n", irn); + + /* Add the node to the schedule. */ + add_to_sched(&be, irn); + + if(get_irn_mode(irn) == mode_T) + add_tuple_projs(&be, irn); + else + make_users_ready(&be, irn); + + /* Increase the time step. */ + be.curr_time += 1; + + /* remove the scheduled node from the ready list. */ + if(pset_find_ptr(be.ready_set, irn)) + pset_remove_ptr(be.ready_set, irn); + } + + del_pset(be.ready_set); + del_pset(be.already_scheduled); + + { + sched_info_t *inf; + list_for_each_entry(sched_info_t, inf, &info->list, list) { + ir_node *irn = get_sched_info_irn(inf); + ir_debugf("node: %n, pos: %d\n", irn, inf->time_step); + } + } +} diff --git a/ir/be/belistsched.h b/ir/be/belistsched.h new file mode 100644 index 000000000..f4fb4cf70 --- /dev/null +++ b/ir/be/belistsched.h @@ -0,0 +1,52 @@ +/** + * Primitive list scheduling. + * @date 20.10.2004 + * @author Sebastian Hack + */ + +#ifndef _FIRM_LIST_SCHED +#define _FIRM_LIST_SCHED + +#include "pset.h" +#include "pmap.h" +#include "list.h" + +#include "besched_t.h" + +/** + * The selection function. + * It picks one node out of the ready list to be scheduled next. + * The function does not have to delete the node from the ready set. + * + * @param env Some private information as passed to list_schedule(). + * @param block The block which is currentliy scheduled. + * @param curr_time The current time step which the picked node + * will be assigned to. + * @param already_scheduled A set containing all nodes already + * scheduled. + * @param ready_list A set containing all ready nodes. Pick one of these + * nodes. + * @return The chosen node. + */ +typedef ir_node *(list_sched_selector_t)(void *env, ir_node *block, + int curr_time, pset *already_scheduled, pset *ready_list); + +ir_node *trivial_selector(void *env, ir_node *block, int curr_time, + pset *already_scheduled, pset *ready_list); + +/** + * List schedule a graph. + * Each block in the graph gets a list head to its link field being the + * head of the schedule. You can walk this list using the functions in + * list.h. + * @param irg The graph to schedule. + * @param sched_obst An obstack to allocate the lists on. + * @param map Maps each block to a list head giving the schedule. + * @param select_func A selection function. + * @param env Some private data to give to the select function. + */ +void list_sched(ir_graph *irg, list_sched_selector_t *select_func, void *env); + + + +#endif diff --git a/ir/be/belive.c b/ir/be/belive.c new file mode 100644 index 000000000..d54028ce4 --- /dev/null +++ b/ir/be/belive.c @@ -0,0 +1,181 @@ +/** + * Interblock liveness analysis. + * @author Sebastian Hack + * @date 6.12.2004 + */ + +#include "irouts.h" +#include "irgwalk.h" +#include "irprintf.h" + +#include "beutil.h" +#include "belive_t.h" + +/** The offset of the liveness information in a firm node. */ +size_t live_irn_data_offset = 0; + +void be_liveness_init(void) +{ + live_irn_data_offset = register_additional_node_data(sizeof(live_info_t)); +} + +int (is_live_in)(const ir_node *block, const ir_node *irn) +{ + return _is_live_in(block, irn); +} + +int (is_live_out)(const ir_node *block, const ir_node *irn) +{ + return _is_live_in(block, irn); +} + +static INLINE void mark_live_in(ir_node *block, const ir_node *irn) +{ + block_live_info_t *info = get_block_live_info(block); + pset_insert_ptr(info->in, irn); +} + +static INLINE void mark_live_out(ir_node *block, const ir_node *irn) +{ + block_live_info_t *info = get_block_live_info(block); + pset_insert_ptr(info->out, irn); +} + +/** + * Mark a node (value) live out at a certain block. Do this also + * transitively, i.e. if the block is not the block of the value's + * definition, all predecessors are also marked live. + * @param def The node (value). + * @param block The block to mark the value live out of. + * @param visited A set were all visited blocks are recorded. + */ +static void live_out_at_block(ir_node *def, ir_node *block, pset *visited) +{ + if(pset_find_ptr(visited, block)) + return; + + pset_insert_ptr(visited, block); + mark_live_out(block, def); + + /* + * If this block is not the definition block, we have to go up + * further. + */ + if(get_nodes_block(def) != block) { + int i, n; + + mark_live_in(block, def); + + for(i = 0, n = get_irn_arity(block); i < n; ++i) + live_out_at_block(def, get_nodes_block(get_irn_n(block, i)), visited); + } +} + +/** + * Liveness analysis for a value. + * This functions is meant to be called by a firm walker, to compute the + * set of all blocks a value is live in. + * @param irn The node (value). + * @param env Ignored. + */ +static void liveness_for_node(ir_node *irn, void *env) +{ + int i, n; + ir_node *def_block; + pset *visited; + + /* Don't compute liveness information fornon-data nodes. */ + if(!is_data_node(irn)) + return; + + visited = pset_new_ptr(512); + def_block = get_nodes_block(irn); + + /* Go over all uses of the value */ + for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) { + ir_node *use = get_irn_out(irn, i); + ir_node *use_block; + + /* + * If the usage is no data node, skip this use, since it does not + * affect the liveness of the node. + */ + if(!is_data_node(use)) + continue; + + /* Get the block where the usage is in. */ + use_block = get_nodes_block(use); + + /* + * If the block of the definition equals the use block, we can skip + * the following computations, since this use is local to a block. + */ + if(def_block == use_block) + continue; + + /* + * If the use is a phi function, determine the corresponding block + * through which the value reaches the phi function and mark the + * value as live out of that block. + */ + if(is_Phi(use)) { + int i, n; + + for(i = 0, n = get_irn_arity(use); i < n; ++i) { + if(get_irn_n(use, i) == irn) { + ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); + live_out_at_block(irn, pred_block, visited); + } + } + } + + /* + * Else, the value is live in at this block. Mark it and call live + * out on the predecessors. + */ + else { + int i, n; + + mark_live_in(use_block, irn); + + for(i = 0, n = get_irn_arity(use_block); i < n; ++i) { + ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i)); + live_out_at_block(irn, pred_block, visited); + } + } + } + + del_pset(visited); +} + +static void create_sets(ir_node *block, void *env) +{ + block_live_info_t *info = get_block_live_info(block); + + info->in = pset_new_ptr(128); + info->out = pset_new_ptr(128); +} + +void be_liveness(ir_graph *irg) +{ + irg_block_walk_graph(irg, create_sets, NULL, NULL); + irg_walk_graph(irg, liveness_for_node, NULL, NULL); +} + + +static void liveness_dump(ir_node *block, void *env) +{ + FILE *f = env; + block_live_info_t *info = get_block_live_info(block); + + assert(is_Block(block) && "Need a block here"); + + ir_fprintf(f, "liveness at block %n\n", block); + ir_fprintf(f, "\tlive in: %*n\n", pset_iterator, info->in); + ir_fprintf(f, "\tlive out: %*n\n", pset_iterator, info->out); +} + +void be_liveness_dump(FILE *f, ir_graph *irg) +{ + irg_block_walk_graph(irg, liveness_dump, NULL, f); +} diff --git a/ir/be/belive.h b/ir/be/belive.h new file mode 100644 index 000000000..754847b0e --- /dev/null +++ b/ir/be/belive.h @@ -0,0 +1,41 @@ +/** + * Interblock liveness analysis. + * @author Sebastian Hack + * @date 6.12.2004 + */ + +#ifndef _BELIVE_H +#define _BELIVE_H + +#include + +/** + * Compute the inter block liveness for a graph. + * @param irg The graph. + */ +void be_liveness(ir_graph *irg); + +/** + * Dump the liveness information for a graph. + * @param f The output. + * @param irg The graph. + */ +void be_liveness_dump(FILE *f, ir_graph *irg); + +/** + * Check, if a node is live in at a block. + * @param block The block. + * @param irn The node to check for. + * @return 1, if @p irn is live at the entrance of @p block, 0 if not. + */ +int (is_live_in)(const ir_node *block, const ir_node *irn); + +/** + * Check, if a node is live out at a block. + * @param block The block. + * @param irn The node to check for. + * @return 1, if @p irn is live at the exit of @p block, 0 if not. + */ +int (is_live_out)(const ir_node *block, const ir_node *irn); + +#endif diff --git a/ir/be/belive_t.h b/ir/be/belive_t.h new file mode 100644 index 000000000..57bcc837d --- /dev/null +++ b/ir/be/belive_t.h @@ -0,0 +1,62 @@ +/** + * Internal headers for liveness analysis. + * @author Sebastian Hack + * @date 6.12.2004 + */ + +#ifndef _BELIVE_T_H +#define _BELIVE_T_H + +#include "config.h" + +#include "pset.h" + +typedef struct _block_live_info_t { + pset *in; + pset *out; +} block_live_info_t; + +typedef struct _node_live_info_t { + unsigned last_use_in_block : 1; +} node_live_info_t; + +typedef struct _live_info_t { + union { + block_live_info_t block; + node_live_info_t node; + } v; +} live_info_t; + +extern size_t live_irn_data_offset; + +#define get_irn_live_info(irn) get_irn_data(irn, live_info_t, live_irn_data_offset) +#define get_live_info_irn(inf) get_irn_data_base(inf, live_irn_data_offset) + +#define get_block_live_info(irn) &(get_irn_live_info(irn)->v.block) + +static INLINE int _is_live_in(const ir_node *block, const ir_node *irn) +{ + block_live_info_t *info = get_block_live_info(block); + + assert(is_Block(block) && "Need a block here"); + return pset_find_ptr(info->in, irn) != NULL; +} + +static INLINE int _is_live_out(const ir_node *block, const ir_node *irn) +{ + block_live_info_t *info = get_block_live_info(block); + + assert(is_Block(block) && "Need a block here"); + return pset_find_ptr(info->out, irn) != NULL; +} + +#define is_live_in(block,irn) _is_live_in(block, irn) +#define is_live_out(block,irn) _is_live_out(block, irn) + +/** + * Initialize the liveness module. + * To be called from be_init(). + */ +void be_liveness_init(void); + +#endif diff --git a/ir/be/bemain.c b/ir/be/bemain.c new file mode 100644 index 000000000..e492d4767 --- /dev/null +++ b/ir/be/bemain.c @@ -0,0 +1,36 @@ +/** + * Backend driver. + * @author Sebastian Hack + * @date 25.11.2004 + */ + +#include "besched.h" +#include "belistsched.h" +#include "belive_t.h" +#include "belive.h" + +void be_init(void) +{ + be_sched_init(); + be_liveness_init(); +} + +static void be_main_loop(void) +{ + int i, n; + + for(i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *irg = get_irp_irg(i); + + list_sched(irg, trivial_selector, NULL); + be_liveness(irg); + + be_sched_dump(stdout, irg); + be_liveness_dump(stdout, irg); + } +} + +void be_main(int argc, const char *argv[]) +{ + be_main_loop(); +} diff --git a/ir/be/besched.c b/ir/be/besched.c new file mode 100644 index 000000000..9c8563609 --- /dev/null +++ b/ir/be/besched.c @@ -0,0 +1,47 @@ + +#include "irprintf.h" +#include "irgwalk.h" +#include "irnode.h" + +#include "besched.h" +#include "belistsched.h" + +size_t sched_irn_data_offset = 0; + +static void block_sched_dumper(ir_node *block, void *env) +{ + FILE *f = env; + const ir_node *curr; + + ir_fprintf(f, "%n:\n", block); + sched_foreach(block, curr) { + ir_fprintf(f, "\t%n\n", curr); + } +} + +void be_sched_dump(FILE *f, const ir_graph *irg) +{ + irg_block_walk_graph((ir_graph *) irg, block_sched_dumper, NULL, f); +} + +void be_sched_init(void) +{ + sched_irn_data_offset = register_additional_node_data(sizeof(sched_info_t)); +} + +void be_sched_test(void) +{ + int i, n; + struct obstack obst; + + obstack_init(&obst); + + for(i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *irg = get_irp_irg(i); + + list_sched(irg, trivial_selector, NULL); + be_sched_dump(stdout, irg); + } + + obstack_free(&obst, NULL); +} diff --git a/ir/be/besched.h b/ir/be/besched.h new file mode 100644 index 000000000..564a1c04b --- /dev/null +++ b/ir/be/besched.h @@ -0,0 +1,12 @@ + +#ifndef _BESCHED_H +#define _BESCHED_H + +#include + +#include "besched_t.h" + +void be_sched_init(void); +void be_sched_dump(FILE *f, const ir_graph *irg); + +#endif diff --git a/ir/be/besched_t.h b/ir/be/besched_t.h new file mode 100644 index 000000000..b803b6592 --- /dev/null +++ b/ir/be/besched_t.h @@ -0,0 +1,120 @@ + +#ifndef _BESCHED_T_H +#define _BESCHED_T_H + +#include "list.h" +#include "irnode_t.h" +#include "irgraph_t.h" + +extern size_t sched_irn_data_offset; + +typedef struct _sched_info_t { + struct list_head list; + int time_step; + + unsigned is_last_use_in_block : 1; +} sched_info_t; + +#define _sched_entry(list_head) (list_entry(list_head, sched_info_t, list)) + +#define get_irn_sched_info(irn) get_irn_data(irn, sched_info_t, sched_irn_data_offset) +#define get_sched_info_irn(sched_info) get_irn_data_base(sched_info, sched_irn_data_offset) + +/** + * Check, if an ir_node has a scheduling successor. + * @param irn The ir node. + * @return 1, if the node has a scheduling successor, 0 if not. + */ +static INLINE int sched_has_succ(const ir_node *irn) +{ + const sched_info_t *info = get_irn_sched_info(irn); + const sched_info_t *block_info = get_irn_sched_info(get_nodes_block(irn)); + return info->list.next != &block_info->list; +} + +/** + * Check, if an ir_node has a scheduling predecessor. + * @param irn The ir node. + * @return 1, if the node has a scheduling predecessor, 0 if not. + */ +static INLINE int sched_has_prev(const ir_node *irn) +{ + const sched_info_t *info = get_irn_sched_info(irn); + const sched_info_t *block_info = get_irn_sched_info(get_nodes_block(irn)); + return info->list.prev != &block_info->list; +} + +/** + * Get the scheduling successor of a node. + * @param irn The node. + * @return The next ir node in the schedule or NULL, if this node has no + * successor. + */ +static INLINE const ir_node *sched_succ(const ir_node *irn) +{ + const sched_info_t *info = get_irn_sched_info(irn); + return sched_has_succ(irn) ? get_sched_info_irn(_sched_entry(info->list.next)) : NULL; +} + +/** + * Get the scheduling predecessor of a node. + * @param irn The node. + * @return The next ir node in the schedule or NULL, if this node has no + * predecessor. + */ +static INLINE const ir_node *sched_prev(const ir_node *irn) +{ + const sched_info_t *info = get_irn_sched_info(irn); + return sched_has_prev(irn) ? get_sched_info_irn(_sched_entry(info->list.prev)) : NULL; +} + +/** + * Get the first node in a block schedule. + * @param block The block of which to get the schedule. + * @return The first node in the schedule or NULL if there is none. + */ +static INLINE const ir_node *sched_first(const ir_node *block) +{ + const sched_info_t *info = get_irn_sched_info(block); + assert(is_Block(block) && "Need a block here"); + return !list_empty(&info->list) ? get_sched_info_irn(_sched_entry(info->list.next)) : NULL; +} + +/** + * Get the last node in a schedule. + * @param block The block to get the schedule for. + * @return The last ir node in a schedule, or NULL if no schedule exists + * or it is empty. + */ +static INLINE const ir_node *sched_last(const ir_node *block) +{ + const sched_info_t *info = get_irn_sched_info(block); + assert(is_Block(block) && "Need a block here"); + return !list_empty(&info->list) ? get_sched_info_irn(_sched_entry(info->list.prev)) : NULL; +} + +/** + * Add a node to a block schedule. + * @param block The block to whose schedule the node shall be added to. + * @param irn The node to add. + * @return The given node. + */ +static INLINE const ir_node *sched_add(ir_node *block, const ir_node *irn) +{ + assert(is_Block(block) && "Need a block here"); + list_add_tail(&get_irn_sched_info(irn)->list, &get_irn_sched_info(block)->list); + return irn; +} + +/** + * A shorthand macro for iterating over a schedule. + * @param block The block. + * @param irn A ir node pointer used as an iterator. + */ +#define sched_foreach(block,irn) for(irn = sched_first(block); irn; irn = sched_succ(irn)) + + +#define sched_foreach_reverse(block,irn) \ + for(irn = sched_last(block); irn; irn = sched_prev(irn)) + +#endif diff --git a/ir/be/beutil.h b/ir/be/beutil.h new file mode 100644 index 000000000..3d3704445 --- /dev/null +++ b/ir/be/beutil.h @@ -0,0 +1,42 @@ + +#ifndef _BEUTIL_H +#define _BEUTIL_H + +#include + +#include "irnode.h" +#include "config.h" + +/** Undefine this to disable debugging mode. */ +#define BE_DEBUG 1 + +/** + * Check, if a node produces or consumes a data value. + * If it does, it is significant for scheduling and register allocation. + * A node produces/consumes a data value, if one of its operands is of + * mode datab, or his retuning mode is of mode datab. + * @param irn The node to check for. + * @return 1, if the node is a data node, 0 if not. + */ +static INLINE int is_data_node(const ir_node *irn) +{ + int i, n; + + /* If the node produces a data value, return immediately. */ + if(mode_is_datab(get_irn_mode(irn))) + return 1; + + /* else check, if it takes a data value, if that is so, return */ + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + if(mode_is_datab(get_irn_mode(op))) + return 1; + } + + /* Else the node does not produce/consume a data value */ + return 0; +} + + + +#endif -- 2.20.1