besched.c 6.27 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
2
# include "config.h"
Michael Beck's avatar
Michael Beck committed
3
#endif
4

Michael Beck's avatar
Michael Beck committed
5
6
7
#ifdef HAVE_STDLIB_H
# include <stdlib.h>
#endif
Sebastian Hack's avatar
Sebastian Hack committed
8

Sebastian Hack's avatar
Sebastian Hack committed
9
#include "impl.h"
10
11
#include "irprintf.h"
#include "irgwalk.h"
12
#include "irnode_t.h"
Michael Beck's avatar
Michael Beck committed
13
#include "irgraph_t.h"
14
#include "iredges_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
15
#include "debug.h"
16

Daniel Grund's avatar
Daniel Grund committed
17
#include "bearch.h"
Sebastian Hack's avatar
Sebastian Hack committed
18
#include "besched_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
19
#include "beutil.h"
20
21
#include "belistsched.h"

Sebastian Hack's avatar
Sebastian Hack committed
22
FIRM_IMPL1(sched_get_time_step, int, const ir_node *)
23
FIRM_IMPL1(sched_has_next, int, const ir_node *)
Sebastian Hack's avatar
Sebastian Hack committed
24
FIRM_IMPL1(sched_has_prev, int, const ir_node *)
25
FIRM_IMPL1(sched_next, ir_node *, const ir_node *)
Sebastian Hack's avatar
Sebastian Hack committed
26
27
28
FIRM_IMPL1(sched_prev, ir_node *, const ir_node *)
FIRM_IMPL1(sched_first, ir_node *, const ir_node *)
FIRM_IMPL1(sched_last, ir_node *, const ir_node *)
Sebastian Hack's avatar
Sebastian Hack committed
29
30
FIRM_IMPL2(sched_add_after, ir_node *, ir_node *, ir_node *)
FIRM_IMPL2(sched_add_before, ir_node *, ir_node *, ir_node *)
Michael Beck's avatar
Michael Beck committed
31
FIRM_IMPL2(sched_comes_after, int, const ir_node *, const ir_node *)
32
FIRM_IMPL1_VOID(sched_remove, ir_node *)
Sebastian Hack's avatar
Sebastian Hack committed
33

34
35
36
37
38
39
40
size_t sched_irn_data_offset = 0;

static void block_sched_dumper(ir_node *block, void *env)
{
	FILE *f = env;
	const ir_node *curr;

41
	ir_fprintf(f, "%+F:\n", block);
42
	sched_foreach(block, curr) {
43
44
    sched_info_t *info = get_irn_sched_info(curr);
		ir_fprintf(f, "\t%6d: %+F\n", info->time_step, curr);
45
46
47
	}
}

Michael Beck's avatar
Michael Beck committed
48
void be_sched_dump(FILE *f, ir_graph *irg)
49
{
Michael Beck's avatar
Michael Beck committed
50
	irg_block_walk_graph(irg, block_sched_dumper, NULL, f);
51
52
}

Michael Beck's avatar
Michael Beck committed
53
/* Init the scheduling stuff. */
54
55
56
57
58
void be_sched_init(void)
{
	sched_irn_data_offset = register_additional_node_data(sizeof(sched_info_t));
}

Sebastian Hack's avatar
Sebastian Hack committed
59
60
61
62
63
64
65
66
67
68
69
70
71
void sched_renumber(const ir_node *block)
{
  ir_node *irn;
  sched_info_t *inf;
  sched_timestep_t step = 0;

  sched_foreach(block, irn) {
    inf = get_irn_sched_info(irn);
    inf->time_step = step;
    step += SCHED_INITIAL_GRANULARITY;
  }
}

Michael Beck's avatar
Michael Beck committed
72
/* Verify a schedule. */
Sebastian Hack's avatar
Sebastian Hack committed
73
74
75
76
77
78
int sched_verify(const ir_node *block)
{
  int res = 1;
  const ir_node *irn;
  int i, n;
  int *save_time_step;
79
  const ir_node **save_nodes;
80
81
  const ir_edge_t *edge;
  pset *scheduled_nodes = pset_new_ptr_default();
82
  FIRM_DBG_REGISTER(firm_dbg_module_t *dbg_sched, "firm.be.sched");
83

Sebastian Hack's avatar
Sebastian Hack committed
84
85
86
87
88
  /* Count the number of nodes in the schedule. */
  n = 0;
  sched_foreach(block, irn)
    n++;

89
90
91
  if(n <= 0)
    return 1;

Michael Beck's avatar
Michael Beck committed
92
93
  save_time_step = xmalloc(n * sizeof(save_time_step[0]));
  save_nodes = xmalloc(n * sizeof(save_nodes[0]));
Sebastian Hack's avatar
Sebastian Hack committed
94
95
96
97
98

  i = 0;
  sched_foreach(block, irn) {
    sched_info_t *info = get_irn_sched_info(irn);
    save_time_step[i] = info->time_step;
Christian Würdig's avatar
Christian Würdig committed
99
    save_nodes[i] = (ir_node *)irn;
Sebastian Hack's avatar
Sebastian Hack committed
100
    info->time_step = i;
101
    pset_insert_ptr(scheduled_nodes, irn);
Sebastian Hack's avatar
Sebastian Hack committed
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

    i += 1;
  }

  /*
   * Check if each relevant operand of a node is scheduled before
   * the node itself.
   */
  sched_foreach(block, irn) {
    int i, n;
    int step = sched_get_time_step(irn);

    for(i = 0, n = get_irn_arity(irn); i < n; i++) {
      ir_node *op = get_irn_n(irn, i);

117
      if(to_appear_in_schedule(op)
Sebastian Hack's avatar
Sebastian Hack committed
118
          && !is_Phi(irn)
Sebastian Hack's avatar
Sebastian Hack committed
119
120
121
122
          && get_nodes_block(op) == block
          && sched_get_time_step(op) > step) {

          DBG((dbg_sched, LEVEL_DEFAULT,
Sebastian Hack's avatar
Sebastian Hack committed
123
                "%+F: %+F is operand of %+F but scheduled after\n", block, op, irn));
Sebastian Hack's avatar
Sebastian Hack committed
124
125
126
127
128
129
130
131
132
          res = 0;
      }
    }
  }

  /* Check, if the time steps are correct */
  for(i = 1; i < n; ++i) {
    if(save_time_step[i] - save_time_step[i - 1] <= 0) {
      DBG((dbg_sched, LEVEL_DEFAULT,
Sebastian Hack's avatar
Sebastian Hack committed
133
134
135
            "%+F from %+F(%d) -> %+F(%d) step shrinks from %d -> %d\n",
            block, save_nodes[i - 1], i - 1, save_nodes[i], i,
            save_time_step[i - 1], save_time_step[i]));
Sebastian Hack's avatar
Sebastian Hack committed
136
137
138
139
140
141
142
143
144
145
146
      res = 0;
    }
  }

  /* Restore the old time steps */
  i = 0;
  sched_foreach(block, irn) {
    sched_info_t *info = get_irn_sched_info(irn);
    info->time_step = save_time_step[i++];
  }

147
148
149
150
  /* Check for all nodes in the block if they are scheduled. */
  foreach_out_edge(block, edge) {
    ir_node *irn = get_edge_src_irn(edge);
    if(to_appear_in_schedule(irn) && !pset_find_ptr(scheduled_nodes, irn))
Sebastian Hack's avatar
Sebastian Hack committed
151
152
      DBG((dbg_sched, LEVEL_DEFAULT,
            "%+F: %+F is in block but not scheduled\n", block, irn));
153
154
155
  }

  del_pset(scheduled_nodes);
Sebastian Hack's avatar
Sebastian Hack committed
156
  free(save_time_step);
157
  free((void *) save_nodes);
Sebastian Hack's avatar
Sebastian Hack committed
158
159
160
  return res;
}

Michael Beck's avatar
Michael Beck committed
161
162
163
164
/**
 * Block-Walker: verify the current block and update the status
 */
static void sched_verify_walker(ir_node *block, void *data)
Sebastian Hack's avatar
Sebastian Hack committed
165
166
{
  int *res = data;
Michael Beck's avatar
Michael Beck committed
167
  *res &= sched_verify(block);
Sebastian Hack's avatar
Sebastian Hack committed
168
169
}

Michael Beck's avatar
Michael Beck committed
170
/* Verify the schedules in all blocks of the irg. */
Sebastian Hack's avatar
Sebastian Hack committed
171
172
173
174
175
176
177
int sched_verify_irg(ir_graph *irg)
{
  int res = 1;
  irg_block_walk_graph(irg, sched_verify_walker, NULL, &res);

  return res;
}
Sebastian Hack's avatar
Sebastian Hack committed
178

Daniel Grund's avatar
Daniel Grund committed
179
180
181
182
183
184
185
186
187
int sched_skip_cf_predicator(const ir_node *irn, void *data) {
  arch_env_t *ae = data;
  return arch_irn_classify(ae, irn) == arch_irn_class_branch;
}

int sched_skip_phi_predicator(const ir_node *irn, void *data) {
	return is_Phi(irn);
}

188
/* Skip nodes in a schedule. */
Michael Beck's avatar
Michael Beck committed
189
ir_node *sched_skip(ir_node *from, int forward, sched_predicator_t *predicator, void *data)
Sebastian Hack's avatar
Sebastian Hack committed
190
{
Daniel Grund's avatar
Daniel Grund committed
191
192
	const ir_node *bl = get_block(from);
	ir_node *curr;
Sebastian Hack's avatar
Sebastian Hack committed
193

Daniel Grund's avatar
Daniel Grund committed
194
195
196
197
198
199
	if (is_Block(from))
		from = forward ? sched_next(from) : sched_prev(from);

	for(curr = from; curr != bl && predicator(curr, data); curr = forward ? sched_next(curr) : sched_prev(curr));

	return curr;
Sebastian Hack's avatar
Sebastian Hack committed
200
}
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258

/** A simple forward single linked list. */
typedef struct {
	ir_node *start;   /**< start of the list */
	ir_node *end;     /**< last block in the list */
	unsigned n_blks;  /**< number of blocks in the list */
} anchor;

/**
 * Ext-Block walker: create a block schedule
 */
static void create_block_list(ir_extblk *blk, void *env) {
	anchor *list = env;
	int i, n;

	for (i = 0, n = get_extbb_n_blocks(blk); i < n; ++i) {
		ir_node *block = get_extbb_block(blk, i);

		set_irn_link(block, NULL);
		if (list->start)
			set_irn_link(list->end, block);
		else
			list->start = block;

		list->end = block;
		++list->n_blks;
	}
}

/*
 * Calculates a block schedule. The schedule is stored as a linked
 * list starting at the start_block of the irg.
 */
ir_node **sched_create_block_schedule(ir_graph *irg)
{
	anchor list;
	ir_node **blk_list, *b, *n;
	unsigned i;

	/* schedule extended basic blocks */
	compute_extbb(irg);

	list.start  = NULL;
	list.end    = NULL;
	list.n_blks = 0;
	irg_extblock_walk_graph(irg, NULL, create_block_list, &list);

	/** create an array, so we can go forward and backward */
	blk_list = NEW_ARR_D(ir_node *, irg->obst,list.n_blks);

	for (i = 0, b = list.start; b; b = n, ++i) {
		n = get_irn_link(b);
		set_irn_link(b, INT_TO_PTR(i));

		blk_list[i] = b;
	}
	return blk_list;
}