irscc.c 36.5 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
2
3
4
5
/*
 * Project:     libFIRM
 * File name:   ir/ana/irscc.c
 * Purpose:     Compute the strongly connected regions and build
 *              backedge/loop datastructures.
6
7
 *              A variation on the Tarjan algorithm. See also [Trapp:99],
 *              Chapter 5.2.1.2.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
8
9
10
11
12
13
14
 * Author:      Goetz Lindenmaier
 * Modified by:
 * Created:     7.2002
 * CVS-ID:      $Id$
 * Copyright:   (c) 2002-2003 Universitt Karlsruhe
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */
15

Michael Beck's avatar
Michael Beck committed
16
17
18
19
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

20
21
#include <string.h>

22
#include "irloop_t.h"
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
23
#include "irnode_t.h"
24
25
#include "irgraph_t.h"
#include "array.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
26
#include "pmap.h"
27
#include "irgwalk.h"
28
#include "irprog_t.h"
Michael Beck's avatar
Michael Beck committed
29
#include "irdump.h"
30
31

ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
Florian Liekweg's avatar
Florian Liekweg committed
32
                      for */
33
static ir_loop *current_loop;      /* Current loop construction is working
Florian Liekweg's avatar
Florian Liekweg committed
34
                      on. */
35
static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
Florian Liekweg's avatar
Florian Liekweg committed
36
37
                      Each loop node gets a unique number.
                      What for? ev. remove. @@@ */
38
static int current_dfn = 1;        /* Counter to generate depth first numbering
Florian Liekweg's avatar
Florian Liekweg committed
39
                      of visited nodes.  */
40

Andreas Schösser's avatar
Andreas Schösser committed
41
42
43
44
void link_to_reg_end (ir_node *n, void *env);
void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
ir_node *get_projx_link(ir_node *cb_projx);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
45
46
47
48
49
50
51
/**********************************************************************/
/* Node attributes                                                   **/
/**********************************************************************/

/* A map to get from irnodes to loop nodes. */
static pmap *node_loop_map = NULL;

52
53
54
55
56
57
58
59
/**********************************************************************/
/* Node attributes needed for the construction.                      **/
/**********************************************************************/

typedef struct scc_info {
  bool in_stack;         /* Marks whether node is on the stack. */
  int dfn;               /* Depth first search number. */
  int uplink;            /* dfn number of ancestor. */
60
  /*  ir_loop *loop;         *//* Refers to the containing loop. */
61
62
63
64
65
66
67
  /*
      struct section *section;
      xset def;
      xset use;
  */
} scc_info;

68
static INLINE scc_info* new_scc_info(void) {
69
70
71
72
73
74
75
76
  scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  memset (info, 0, sizeof (scc_info));
  return info;
}

static INLINE void
mark_irn_in_stack (ir_node *n) {
  assert(get_irn_link(n));
77
78
  /*  to slow */
  /* ((scc_info *)get_irn_link(n))->in_stack = true; */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
79
  ((scc_info *)n->link)->in_stack = true;
80
81
82
83
84
}

static INLINE void
mark_irn_not_in_stack (ir_node *n) {
  assert(get_irn_link(n));
85
86
  /*  to slow */
  /* ((scc_info *)get_irn_link(n))->in_stack = false; */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
87
  ((scc_info *)n->link)->in_stack = false;
88
89
90
91
92
}

static INLINE bool
irn_is_in_stack (ir_node *n) {
  assert(get_irn_link(n));
93
94
  /*  to slow */
  /* return ((scc_info *)get_irn_link(n))->in_stack; */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
95
  return ((scc_info *)n->link)->in_stack;
96
97
98
99
100
}

static INLINE void
set_irn_uplink (ir_node *n, int uplink) {
  assert(get_irn_link(n));
101
102
  /*  to slow */
  /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
103
  ((scc_info *)n->link)->uplink = uplink;
104
105
}

106
INLINE int
107
108
get_irn_uplink (ir_node *n) {
  assert(get_irn_link(n));
109
110
  /*  from fast to slow */
  /* return ((scc_info *)get_irn_link(n))->uplink; */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
111
  return ((scc_info *)n->link)->uplink;
112
113
114
115
116
}

static INLINE void
set_irn_dfn (ir_node *n, int dfn) {
  assert(get_irn_link(n));
117
118
  /*  to slow */
  /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
119
  ((scc_info *)n->link)->dfn = dfn;
120
121
}

122
INLINE int
123
124
get_irn_dfn (ir_node *n) {
  assert(get_irn_link(n));
125
126
  /*  to slow */
  /* return ((scc_info *)get_irn_link(n))->dfn; */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
127
  return ((scc_info *)n->link)->dfn;
128
129
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
130
131
132
#if 0
/* Replaced node loop map by real field as hash access dominates runtime
 * of the algorithm. ! */
133
/* Uses temporary information to set the loop */
134
INLINE void
Götz Lindenmaier's avatar
Götz Lindenmaier committed
135
set_irn_loop (ir_node *n, ir_loop* loop) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
136
137
  assert(node_loop_map && "not initialized!");
  pmap_insert(node_loop_map, (void *)n, (void *)loop);
138
139
140
}

/* Uses temporary information to get the loop */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
141
142
143
INLINE ir_loop *
get_irn_loop (ir_node *n) {
  ir_loop *res = NULL;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
144
  if (!node_loop_map) return NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
145
146
147
148
149

  if (pmap_contains(node_loop_map, (void *)n))
    res = (ir_loop *) pmap_get(node_loop_map, (void *)n);

  return res;
150
}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
151
#else
152
INLINE void
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
153
154
155
156
157
158
159
160
161
162
163
set_irn_loop (ir_node *n, ir_loop* loop) {
  n->loop = loop;
}

/* Uses temporary information to get the loop */
INLINE ir_loop *
get_irn_loop (ir_node *n) {
  return n->loop;
}
#endif

164

Götz Lindenmaier's avatar
Götz Lindenmaier committed
165
#if 0
166
static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
  int i;
  ir_loop *res = NULL;

  /* Test whether n is contained in this loop. */
  for (i = 0; i < get_loop_n_nodes(l); i++)
    if (n == get_loop_node(l, i)) return l;

  /* Is this a leave in the loop tree? If so loop not found. */
  if (get_loop_n_sons(l) == 0) return NULL;

  /* Else descend in the loop tree. */
  for (i = 0; i < get_loop_n_sons(l); i++) {
    res = find_nodes_loop(n, get_loop_son(l, i));
    if (res) break;
  }
  return res;
}

/* @@@ temporary implementation, costly!!! */
ir_loop * get_irn_loop(ir_node *n) {
  ir_loop *l = get_irg_loop(current_ir_graph);
  l = find_nodes_loop(n, l);
  return l;
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
191
#endif
192
193
194
195
196
197
198
199

/**********************************************************************/
/* A stack.                                                          **/
/**********************************************************************/

static ir_node **stack = NULL;
static int tos = 0;                /* top of stack */

200
static INLINE void init_stack(void) {
201
202
203
204
205
206
207
208
  if (stack) {
    ARR_RESIZE (ir_node *, stack, 1000);
  } else {
    stack = NEW_ARR_F (ir_node *, 1000);
  }
  tos = 0;
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
209
#if 0
210
static INLINE void free_stack(void) {
211
212
213
214
  DEL_ARR_F(stack);
  stack = NULL;
  tos = 0;
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
215
#endif
216
217
218
219

static INLINE void
push (ir_node *n)
{
Till Riedel's avatar
Till Riedel committed
220
  /*DDMN(n);*/
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243

  if (tos == ARR_LEN (stack)) {
    int nlen = ARR_LEN (stack) * 2;
    ARR_RESIZE (ir_node *, stack, nlen);
  }
  stack [tos++] = n;
  mark_irn_in_stack(n);
}

static INLINE ir_node *
pop (void)
{
  ir_node *n = stack[--tos];
  mark_irn_not_in_stack(n);
  return n;
}

/* The nodes up to n belong to the current loop.
   Removes them from the stack and adds them to the current loop. */
static INLINE void
pop_scc_to_loop (ir_node *n)
{
  ir_node *m;
244
  int i = 0;
245

246
247
248
  /*for (;;) {*/
  do
    {
249
    m = pop();
250
251
252

    //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);

253
    loop_node_cnt++;
254
    set_irn_dfn(m, loop_node_cnt);
255
    add_loop_node(current_loop, m);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
256
    set_irn_loop(m, current_loop);
257
    i++;
258
259
    /*    if (m==n) break;*/
    } while(m != n);
260
261

  if(i > 1)
Florian Liekweg's avatar
Florian Liekweg committed
262
    printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
263
264
265
266
267
}

/* GL ??? my last son is my grandson???  Removes loops with no
   ir_nodes in them.  Such loops have only another loop as son. (Why
   can't they have two loops as sons? Does it never get that far? ) */
268
static void close_loop (ir_loop *l)
269
270
271
272
273
274
275
276
{
  int last = get_loop_n_elements(l) - 1;
  loop_element lelement = get_loop_element(l, last);
  ir_loop *last_son = lelement.son;

  if (get_kind(last_son) == k_ir_loop &&
      get_loop_n_elements(last_son) == 1)
    {
Michael Beck's avatar
Michael Beck committed
277
278
      ir_loop *gson;

279
      lelement = get_loop_element(last_son, 0);
Michael Beck's avatar
Michael Beck committed
280
      gson = lelement.son;
281
      if(get_kind(gson) == k_ir_loop)
Florian Liekweg's avatar
Florian Liekweg committed
282
    {
283
          loop_element new_last_son;
Michael Beck's avatar
Michael Beck committed
284

Florian Liekweg's avatar
Florian Liekweg committed
285
      gson -> outer_loop = l;
286
          new_last_son.son = gson;
Florian Liekweg's avatar
Florian Liekweg committed
287
288
      l -> children[last] = new_last_son;
    }
289
290
291
    }

  current_loop = l;
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
}

/* Removes and unmarks all nodes up to n from the stack.
   The nodes must be visited once more to assign them to a scc. */
static INLINE void
pop_scc_unmark_visit (ir_node *n)
{
  ir_node *m = NULL;

  while (m != n) {
    m = pop();
    set_irn_visited(m, 0);
  }
}

/**********************************************************************/
/* The loop datastructure.                                           **/
/**********************************************************************/

/* Allocates a new loop as son of current_loop.  Sets current_loop
   to the new loop and returns the father. */
313
ir_loop *new_loop (void) {
314
315
316
317
318
319
320
  ir_loop *father, *son;

  father = current_loop;

  son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
  memset (son, 0, sizeof (ir_loop));
  son->kind = k_ir_loop;
321
322
323
  son->children = NEW_ARR_F (loop_element, 0);
  son->n_nodes = 0;
  son->n_sons=0;
324
325
326
327
328
329
330
331
332
  if (father) {
    son->outer_loop = father;
    add_loop_son(father, son);
    son->depth = father->depth+1;
  } else {  /* The root loop */
    son->outer_loop = son;
    son->depth = 0;
  }

333
334
#ifdef DEBUG_libfirm
  son->loop_nr = get_irp_new_node_nr();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
335
  son->link = NULL;
336
337
#endif

338
339
340
341
  current_loop = son;
  return father;
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
342
#if 0
343
/* Finishes the datastructures, copies the arrays to the obstack
344
345
   of current_ir_graph.
   A. Schoesser: Caution: loop -> sons is gone. */
346
static void mature_loop (ir_loop *loop) {
347
348
349
350
351
352
353
  ir_loop **new_sons;

  new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
  memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
  DEL_ARR_F(loop->sons);
  loop->sons = new_sons;
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
354
#endif
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370

/* Returns outer loop, itself if outermost. */
ir_loop *get_loop_outer_loop (ir_loop *loop) {
  assert(loop && loop->kind == k_ir_loop);
  return loop->outer_loop;
}

/* Returns nesting depth of this loop */
int get_loop_depth (ir_loop *loop) {
  assert(loop); assert(loop->kind == k_ir_loop);
  return loop->depth;
}

/* Returns the number of inner loops */
int      get_loop_n_sons (ir_loop *loop) {
  assert(loop && loop->kind == k_ir_loop);
371
  return(loop -> n_sons);
372
}
373
374
375
376

/* Returns the pos`th loop_node-child              *
 * TODO: This method isn`t very efficient !        *
 * Returns NULL if there isnt`t a pos`th loop_node */
377
ir_loop *get_loop_son (ir_loop *loop, int pos) {
378
379
  int child_nr = 0, loop_nr = -1;

380
  assert(loop && loop->kind == k_ir_loop);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
381
  while(child_nr < ARR_LEN(loop->children))
382
383
384
385
386
387
388
389
   {
    if(*(loop -> children[child_nr].kind) == k_ir_loop)
      loop_nr++;
    if(loop_nr == pos)
      return(loop -> children[child_nr].son);
    child_nr++;
   }
  return NULL;
390
}
391
392
393
394

/* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
   is invalid! */

395
INLINE void
396
add_loop_son(ir_loop *loop, ir_loop *son) {
Till Riedel's avatar
Till Riedel committed
397
398
  loop_element lson;
  lson.son = son;
399
  assert(loop && loop->kind == k_ir_loop);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
400
  assert(get_kind(son) == k_ir_loop);
Till Riedel's avatar
Till Riedel committed
401
  ARR_APP1 (loop_element, loop->children, lson);
402
  loop -> n_sons++;
403
404
405
406
407
}

/* Returns the number of nodes in the loop */
int      get_loop_n_nodes (ir_loop *loop) {
  assert(loop); assert(loop->kind == k_ir_loop);
408
409
  return loop -> n_nodes;
/*  return ARR_LEN(loop->nodes); */
410
}
411
412
413
414

/* Returns the pos`th ir_node-child                *
 * TODO: This method isn`t very efficient !        *
 * Returns NULL if there isnt`t a pos`th ir_node   */
415
ir_node *get_loop_node (ir_loop *loop, int pos) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
416
  int child_nr, node_nr = -1;
417

418
  assert(loop && loop->kind == k_ir_loop);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
419
420
421
  assert(pos < get_loop_n_nodes(loop));

  for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
422
423
424
425
    if(*(loop -> children[child_nr].kind) == k_ir_node)
      node_nr++;
    if(node_nr == pos)
      return(loop -> children[child_nr].node);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
426
  }
427
428
  DDML(loop);
  printf("pos: %d\n", pos);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
429
  assert(0 && "no child at pos found");
430
  return NULL;
431
}
432
433
434
435

/* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
   is invalid! */

436
INLINE void
437
add_loop_node(ir_loop *loop, ir_node *n) {
Till Riedel's avatar
Till Riedel committed
438
  loop_element ln;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
439
  ln.node = n;
440
  assert(loop && loop->kind == k_ir_loop);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
441
  assert(get_kind(n) == k_ir_node);
Till Riedel's avatar
Till Riedel committed
442
  ARR_APP1 (loop_element, loop->children, ln);
443
  loop->n_nodes++;
444
445
}

446
/** Returns the number of elements contained in loop.  */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
447
int get_loop_n_elements (ir_loop *loop) {
448
449
  assert(loop && loop->kind == k_ir_loop);
  return(ARR_LEN(loop->children));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
450
}
451
452
453
454
455

/*
 Returns the pos`th loop element.
 This may be a loop_node or a ir_node. The caller of this function has
 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
456
 and then select the apropriate "loop_element.node" or "loop_element.son".
457
458
*/

Götz Lindenmaier's avatar
Götz Lindenmaier committed
459
loop_element get_loop_element (ir_loop *loop, int pos) {
460
461
462
  assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));

  return(loop -> children[pos]);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
463
464
}

465
466
int get_loop_element_pos(ir_loop *loop, void *le) {
  int i;
Michael Beck's avatar
Michael Beck committed
467
  assert(loop && loop->kind == k_ir_loop);
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482

  for (i = 0; i < get_loop_n_elements(loop); i++)
    if (get_loop_element(loop, i).node == le) return i;
  return -1;
}

int get_loop_loop_nr(ir_loop *loop) {
  assert(loop && loop->kind == k_ir_loop);
#ifdef DEBUG_libfirm
  return loop->loop_nr;
#else
  return (int)loop;
#endif
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500

/** A field to connect additional information to a loop.  Only valid
    if libfirm_debug is set. */
void  set_loop_link (ir_loop *loop, void *link) {
  assert(loop && loop->kind == k_ir_loop);
#ifdef DEBUG_libfirm
  loop->link = link;
#endif
}
void *get_loop_link (const ir_loop *loop) {
  assert(loop && loop->kind == k_ir_loop);
#ifdef DEBUG_libfirm
  return loop->link;
#else
  return NULL;
#endif
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
501
502
503
504
505
506
507
508
509
/* The outermost loop is remarked in the surrounding graph. */
void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
  assert(irg);
  irg->loop = loop;
}
ir_loop *get_irg_loop(ir_graph *irg) {
  assert(irg);
  return irg->loop;
}
510

511

512
513
514
515
516
517
518
519
520
521
/**********************************************************************/
/* Constructing and destructing the loop/backedge information.       **/
/**********************************************************************/

/* Initialization steps. **********************************************/

static INLINE void
init_node (ir_node *n, void *env) {
  set_irn_link (n, new_scc_info());
  clear_backedges(n);
522
523
524
525
#if 0
  /* Also init nodes not visible in intraproc_view. */
    /* @@@ init_node is called for too many nodes -- this wastes memory!.
       The mem is not lost as its on the obstack. */
526
  if (get_irn_op(n) == op_Filter) {
527
528
529
    for (i = 0; i < get_Filter_n_cg_preds(n); i++)
      init_node(get_Filter_cg_pred(n, i), NULL);
  }
530
  if (get_irn_op(n) == op_Block) {
531
532
533
534
535
    for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
      init_node(get_Block_cg_cfgpred(n, i), NULL);
    }
  }
  /* The following pattern matches only after a call from above pattern. */
536
  if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
537
538
539
    /* @@@ init_node is called for every proj -- this wastes memory!.
       The mem is not lost as its on the obstack. */
    ir_node *cb = get_Proj_pred(n);
540
541
542
    if ((get_irn_op(cb) == op_CallBegin) ||
    (get_irn_op(cb) == op_EndReg) ||
    (get_irn_op(cb) == op_EndExcept)) {
543
544
545
      init_node(cb, NULL);
      init_node(get_nodes_Block(cb), NULL);
    }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
546
  }
547
#endif
548
549
550
}

static INLINE void
Götz Lindenmaier's avatar
Götz Lindenmaier committed
551
init_scc_common (void) {
552
553
  current_dfn = 1;
  loop_node_cnt = 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
554
  if (!node_loop_map) node_loop_map = pmap_create();
555
  init_stack();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
556
557
558
559
560
}

static INLINE void
init_scc (ir_graph *irg) {
  init_scc_common();
561
562
563
564
565
566
  irg_walk_graph (irg, init_node, NULL, NULL);
  /*
  irg_walk (irg, link_to_reg_end, NULL, NULL);
  */
}

567
static INLINE void
568
init_ip_scc (void) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
569
  init_scc_common();
570
  cg_walk (init_node, NULL, NULL);
Andreas Schösser's avatar
Andreas Schösser committed
571
572
573
574

#if EXPERIMENTAL_LOOP_TREE
  cg_walk (link_to_reg_end, NULL, NULL);
#endif
575
}
576

577
/* Condition for breaking the recursion. */
578
static bool is_outermost_Start(ir_node *n) {
579
580
  /* Test whether this is the outermost Start node.  If so
     recursion must end. */
581
  if ((get_irn_op(n) == op_Block)     &&
582
      (get_Block_n_cfgpreds(n) == 1)  &&
583
      (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
584
585
586
587
588
589
590
591
      (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
    return true;
  }
#if 0
  /*  @@@ Bad condition:
      not possible in interprocedural view as outermost_graph is
      not necessarily the only with a dead-end start block.
      Besides current_ir_graph is not set properly. */
592
  if ((get_irn_op(n) == op_Block) &&
593
594
      (n == get_irg_start_block(current_ir_graph))) {
    if ((!interprocedural_view)  ||
Florian Liekweg's avatar
Florian Liekweg committed
595
    (current_ir_graph == outermost_ir_graph))
596
597
      return true;
  }
598
#endif
599
600
601
  return false;
}

Andreas Schösser's avatar
Andreas Schösser committed
602
/* When to walk from nodes to blocks. Only for Control flow operations? */
603
604
static INLINE int
get_start_index(ir_node *n) {
Andreas Schösser's avatar
Andreas Schösser committed
605
606
607
608
609
610
611
612
613
614
#undef BLOCK_BEFORE_NODE
#define BLOCK_BEFORE_NODE 1

#if BLOCK_BEFORE_NODE

  /* This version assures, that all nodes are ordered absolutely.  This allows
     to undef all nodes in the heap analysis if the block is false, which means
     not reachable.
     I.e., with this code, the order on the loop tree is correct. But a (single)
     test showed the loop tree is deeper.   */
615
616
617
  if (get_irn_op(n) == op_Phi   ||
      get_irn_op(n) == op_Block ||
      (get_irn_op(n) == op_Filter && interprocedural_view) ||
Andreas Schösser's avatar
Andreas Schösser committed
618
619
      (get_irg_pinned(get_irn_irg(n)) == floats &&
       get_op_pinned(get_irn_op(n)) == floats))
Götz Lindenmaier's avatar
Götz Lindenmaier committed
620
621
622
623
    // Here we could test for backedge at -1 which is illegal
    return 0;
  else
    return -1;
Andreas Schösser's avatar
Andreas Schösser committed
624
625
626
627
628
629
630
631

#else

  /* This version causes deeper loop trees (at least we verified this
     for Polymor).
     But it guarantees that Blocks are analysed before nodes contained in the
     block.  If so, we can set the value to undef if the block is not \
     executed. */
632
   if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
Andreas Schösser's avatar
Andreas Schösser committed
633
634
635
636
     return -1;
   else
     return 0;

637
#endif
638
}
Andreas Schösser's avatar
Andreas Schösser committed
639
640


Götz Lindenmaier's avatar
Götz Lindenmaier committed
641
#if 0
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
static void test(ir_node *pred, ir_node *root, ir_node *this) {
  int i;
  if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;

  printf("this: %d ", get_irn_uplink(this)); DDMN(this);
  printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
  printf("root: %d ", get_irn_uplink(root)); DDMN(root);

  printf("tos: %d\n", tos);

  for (i = tos; i >= 0; i--) {
    ir_node *n = stack[i];
    if (!n) continue;
    printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
  }
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
658
#endif
659

660
661
/* Test for legal loop header: Block, Phi, ... */
INLINE static bool is_possible_loop_head(ir_node *n) {
662
  ir_op *op = get_irn_op(n);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
663
  return ((op == op_Block) ||
Andreas Schösser's avatar
Andreas Schösser committed
664
665
	  (op == op_Phi) ||
	  ((op == op_Filter) && interprocedural_view));
666
667
}

668
669
/* Returns true if n is a loop header, i.e., it is a Block, Phi
   or Filter node and has predecessors within the loop and out
670
671
   of the loop.
   @arg root: only needed for assertion. */
672
673
674
static bool
is_head (ir_node *n, ir_node *root)
{
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
675
  int i, arity;
676
  int some_outof_loop = 0, some_in_loop = 0;
677

678
679
  /* Test for legal loop header: Block, Phi, ... */
  if (!is_possible_loop_head(n))
680
    return false;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
681

682
  if (!is_outermost_Start(n)) {
683
    arity = get_irn_arity(n);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
684
    for (i = get_start_index(n); i < arity; i++) {
685
      ir_node *pred = get_irn_n(n, i);
686
687
688
      assert(pred);
      if (is_backedge(n, i)) continue;
      if (!irn_is_in_stack(pred)) {
Andreas Schösser's avatar
Andreas Schösser committed
689
	some_outof_loop = 1;
690
      } else {
691
692
693
694
	if(get_irn_uplink(pred) < get_irn_uplink(root)) {
	  DDMN(n); DDMN(pred); DDMN(root);
	  assert(get_irn_uplink(pred) >= get_irn_uplink(root));
	}
Andreas Schösser's avatar
Andreas Schösser committed
695
	some_in_loop = 1;
696
697
698
699
700
701
      }
    }
  }
  return some_outof_loop && some_in_loop;
}

702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
/* Returns true if n is possible loop head of an endless loop.
   I.e., it is a Block, Phi or Filter node and has only predecessors
   within the loop.
   @arg root: only needed for assertion. */
static bool
is_endless_head (ir_node *n, ir_node *root)
{
  int i, arity;
  int some_outof_loop = 0, some_in_loop = 0;

  /* Test for legal loop header: Block, Phi, ... */
  if (!is_possible_loop_head(n))
    return false;

  if (!is_outermost_Start(n)) {
    arity = get_irn_arity(n);
    for (i = get_start_index(n); i < arity; i++) {
      ir_node *pred = get_irn_n(n, i);
      assert(pred);
      if (is_backedge(n, i)) { continue; }
      if (!irn_is_in_stack(pred)) {
	some_outof_loop = 1; //printf(" some out of loop ");
      } else {
	if(get_irn_uplink(pred) < get_irn_uplink(root)) {
	  DDMN(pred); DDMN(root);
	  assert(get_irn_uplink(pred) >= get_irn_uplink(root));
	}
	some_in_loop = 1;
      }
    }
  }
  return !some_outof_loop && some_in_loop;
}

736
737
738
739
740
741
742
743
/* Returns index of the predecessor with the smallest dfn number
   greater-equal than limit. */
static int
smallest_dfn_pred (ir_node *n, int limit)
{
  int i, index = -2, min = -1;

  if (!is_outermost_Start(n)) {
744
    int arity = get_irn_arity(n);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
745
    for (i = get_start_index(n); i < arity; i++) {
746
      ir_node *pred = get_irn_n(n, i);
747
748
      assert(pred);
      if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
749
      if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
Andreas Schösser's avatar
Andreas Schösser committed
750
751
	index = i;
	min = get_irn_dfn(pred);
752
753
754
755
756
757
758
759
760
761
762
763
764
      }
    }
  }
  return index;
}

/* Returns index of the predecessor with the largest dfn number. */
static int
largest_dfn_pred (ir_node *n)
{
  int i, index = -2, max = -1;

  if (!is_outermost_Start(n)) {
765
    int arity = get_irn_arity(n);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
766
    for (i = get_start_index(n); i < arity; i++) {
767
      ir_node *pred = get_irn_n(n, i);
768
769
      if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
      if (get_irn_dfn(pred) > max) {
Andreas Schösser's avatar
Andreas Schösser committed
770
771
	index = i;
	max = get_irn_dfn(pred);
772
773
774
775
776
777
      }
    }
  }
  return index;
}

778
779
780
781
782
783
784
785
/** Searches the stack for possible loop heads.  Tests these for backedges.
    If it finds a head with an unmarked backedge it marks this edge and
    returns the tail of the loop.
    If it finds no backedge returns NULL.
    ("disable_backedge" in fiasco)
*
*  @param n  A node where uplink == dfn.
**/
786

787
788
789
790
791
792
793
794
static ir_node *
find_tail (ir_node *n) {
  ir_node *m;
  int i, res_index = -2;

  /*
    if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
  */
795
  m = stack[tos-1];  /* tos = top of stack */
796
797
798
  if (is_head (m, n)) {
    res_index = smallest_dfn_pred(m, 0);
    if ((res_index == -2) &&  /* no smallest dfn pred found. */
Andreas Schösser's avatar
Andreas Schösser committed
799
    (n ==  m))
800
801
      return NULL;
  } else {
802
803
    if (m == n) return NULL;    // Is this to catch Phi - self loops?
    for (i = tos-2; i >= 0; --i) {
804
      m = stack[i];
805

806
      if (is_head (m, n)) {
Andreas Schösser's avatar
Andreas Schösser committed
807
808
809
	res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
	if (res_index == -2)  /* no smallest dfn pred found. */
	  res_index = largest_dfn_pred (m);
810
811
812
813
814
815
816
817
818
819
820

	if ((m == n) && (res_index == -2)) {
	  i = -1;
	}
	break;
      }

      /* We should not walk past our selves on the stack:  The upcoming nodes
	 are not in this loop. We assume a loop not reachable from Start. */
      if (m == n) {
	i = -1;
Andreas Schösser's avatar
Andreas Schösser committed
821
	break;
822
      }
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838

    }

    if (i < 0) {
      /* A dead loop not reachable from Start. */
      for (i = tos-2; i >= 0; --i) {
	m = stack[i];
	if (is_endless_head (m, n)) {
	  res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
	  if (res_index == -2)  /* no smallest dfn pred found. */
	    res_index = largest_dfn_pred (m);
	  break;
	}
	if (m == n) { break; }  /* It's not an unreachable loop, either. */
      }
      //assert(0 && "no head found on stack");
839
    }
840

841
842
843
844
  }
  assert (res_index > -2);

  set_backedge (m, res_index);
845
  return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
846
847
848
}


Andreas Schösser's avatar
Andreas Schösser committed
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
#if EXPERIMENTAL_LOOP_TREE

/*  ----------------------------------------------------------------
    AS:  This is experimantal code to build loop trees suitable for
    the heap analysis. Does not work correctly right now... :-(


    Search in stack for the corresponding first Call-End-ProjX that
    corresponds to one of the control flow predecessors of the given
    block, that is the possible callers.
    returns: the control predecessor to chose\
    or       -1 if no corresponding Call-End-Node could be found
             on the stack.
    - -------------------------------------------------------------- */

int search_endproj_in_stack(ir_node *start_block)
{
  int i, j;
  assert(is_Block(start_block));
  for(i = tos - 1; i >= 0; --i)
    {
      DDMN(stack[i]);
      if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
	 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
	{
	  printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
	  ir_node *end_projx = stack[i];

	  for(j = 0; j < get_irn_arity(start_block); j++)
	    {
	      ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
	      DDMN(begin_projx);
	      if(get_irn_n(start_block, j) == begin_projx)
		{
		  printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
		  return(j);
		}
	    }
	}
    }
  return(-1);
}


static pmap *projx_link = NULL;

void link_to_reg_end (ir_node *n, void *env) {
  if(get_irn_op(n) == op_Proj && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg)
    {
      /* Reg End Projx -> Find the CallBegin Projx and hash it */
      ir_node *end_projx = n;
      ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
      printf("Linked the following ProjxNodes:\n");
      DDMN(begin_projx);
      DDMN(end_projx);
      set_projx_link(begin_projx, end_projx);
    }
}

void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
{
  if(projx_link == NULL)
    projx_link = pmap_create();
  pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
}

ir_node *get_projx_link(ir_node *cb_projx)
{
  return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
}

#endif



924
/*-----------------------------------------------------------*
Andreas Schösser's avatar
Andreas Schösser committed
925
 *                   The core algorithm.                     *
926
 *-----------------------------------------------------------*/
Andreas Schösser's avatar
Andreas Schösser committed
927

928

929
static void scc (ir_node *n) {
930
  int i;
931
932
933
934
935
936
  if (irn_visited(n)) return;
  mark_irn_visited(n);

  /* Initialize the node */
  set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
  set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
937
  set_irn_loop(n, NULL);
938
939
940
  current_dfn ++;
  push(n);

941
942
943
944
  /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
     array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
     so is_backedge does not access array[-1] but correctly returns false! */

945
  if (!is_outermost_Start(n)) {
946
    int arity = get_irn_arity(n);
947

Andreas Schösser's avatar
Andreas Schösser committed
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
#if EXPERIMENTAL_LOOP_TREE

    /* This is meant to be used with the experimenatl code above.
       If the above code is not used any more, this can be deleted, too.... */

    if(interprocedural_view &&
       is_Block(n) &&
       get_irn_op(get_irn_n(n, 0)) == op_Proj &&
       get_irn_op(get_irn_n(get_irn_n(n, 0), 0)) == op_CallBegin)
      {
	/* We are at the start node of a function:
	   Walk to the callers in the correct order! */
	DDMN(n);
	DDMN(get_irn_n(get_irn_n(n, 0), 0));
	for(i = 0; i < arity; i++)
	  {
	    int pred_nr;
	    ir_node *m;

	    pred_nr = search_endproj_in_stack(n);
	    assert(pred_nr >= 0);
	    if(is_backedge(n, pred_nr))
	      continue;
	    m = get_irn_n(n, pred_nr);
	    scc(m);

	    if (irn_is_in_stack(m)) {
	      /* Uplink of m is smaller if n->m is a backedge.
		 Propagate the uplink to mark the loop. */
	      if (get_irn_uplink(m) < get_irn_uplink(n))
		set_irn_uplink(n, get_irn_uplink(m));
	    }
	  }
      }
    else

#endif

      {
	for (i = get_start_index(n); i < arity; i++) {
	  ir_node *m;
	  if (is_backedge(n, i)) continue;
990
991
	  m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
	  /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
Andreas Schösser's avatar
Andreas Schösser committed
992
993
994
995
996
997
998
999
	  scc (m);
	  if (irn_is_in_stack(m)) {
	    /* Uplink of m is smaller if n->m is a backedge.
	       Propagate the uplink to mark the loop. */
	    if (get_irn_uplink(m) < get_irn_uplink(n))
	      set_irn_uplink(n, get_irn_uplink(m));
	  }
	}
1000
1001
      }
  }
1002

1003
  if (get_irn_dfn(n) == get_irn_uplink(n)) {
Andreas Schösser's avatar
Andreas Schösser committed
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
    /* This condition holds for
       1) the node with the incoming backedge.
          That is: We found a loop!
       2) Straight line code, because no uplink has been propagated, so the
          uplink still is the same as the dfn.

       But n might not be a proper loop head for the analysis. Proper loop
       heads are Block and Phi nodes. find_tail searches the stack for
       Block's and Phi's and takes those nodes as loop heads for the current
       loop instead and marks the incoming edge as backedge. */

1015
1016
    ir_node *tail = find_tail(n);
    if (tail) {
Andreas Schösser's avatar
Andreas Schösser committed
1017
1018
1019
1020
1021
1022
1023
1024
      /* We have a loop, that is no straight line code,
	 because we found a loop head!
	 Next actions: Open a new loop on the loop tree and
	               try to find inner loops */


#define NO_LOOPS_WITHOUT_HEAD 1
#if NO_LOOPS_WITHOUT_HEAD
1025
1026
1027
1028

      /* This is an adaption of the algorithm from fiasco / optscc to
       * avoid loops without Block or Phi as first node.  This should
       * severely reduce the number of evaluations of nodes to detect
Andreas Schösser's avatar
Andreas Schösser committed
1029
       * a fixpoint in the heap analysis.
1030
       * Further it avoids loops without firm nodes that cause errors
1031
       * in the heap analyses. */
Andreas Schösser's avatar
Andreas Schösser committed
1032

1033
1034
1035
      ir_loop *l;
      int close;
      if (get_loop_n_elements(current_loop) > 0) {
Andreas Schösser's avatar
Andreas Schösser committed
1036
1037
	l = new_loop();
	close = 1;
1038
      } else {
Andreas Schösser's avatar
Andreas Schösser committed
1039
1040
	l = current_loop;
	close = 0;
1041
      }
Andreas Schösser's avatar
Andreas Schösser committed
1042

1043
#else
Andreas Schösser's avatar
Andreas Schösser committed
1044

1045
      ir_loop *l = new_loop();
Andreas Schösser's avatar
Andreas Schösser committed
1046

1047
#endif
1048

1049
1050
      /* Remove the loop from the stack ... */
      pop_scc_unmark_visit (n);
Andreas Schösser's avatar
Andreas Schösser committed
1051

1052
      /*  GL @@@ remove experimental stuff rem = find_irg_on_stack(tail); */
1053

Andreas Schösser's avatar
Andreas Schösser committed
1054
1055
1056
1057
1058
      /* The current backedge has been marked, that is temporarily eliminated,
	 by find tail. Start the scc algorithm
	 anew on the subgraph thats left (the current loop without the backedge)
	 in order to find more inner loops. */

1059
      scc (tail);
Andreas Schösser's avatar
Andreas Schösser committed
1060

1061
      /*  GL @@@ remove experimental stuff current_ir_graph = rem; */
1062
1063

      assert (irn_visited(n));
1064
1065
1066
#if NO_LOOPS_WITHOUT_HEAD
      if (close)
#endif
Andreas Schösser's avatar
Andreas Schösser committed
1067
1068
1069
1070
1071
1072
	close_loop(l);
    }
    else
      {
	/* AS: No loop head was found, that is we have straightline code.
	       Pop all nodes from the stack to the current loop. */
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
      pop_scc_to_loop(n);
    }
  }
}

/* Constructs backedge information for irg. In interprocedural view constructs
   backedges for all methods called by irg, too. */
void construct_backedges(ir_graph *irg) {
  ir_graph *rem = current_ir_graph;
  ir_loop *head_rem;

1084
  assert(!interprocedural_view &&
Florian Liekweg's avatar
Florian Liekweg committed
1085
     "not implemented, use construct_ip_backedges");
1086

1087
1088
1089
  current_ir_graph = irg;
  outermost_ir_graph = irg;

1090
  init_scc(current_ir_graph);
1091
1092
1093
1094
1095
1096

  current_loop = NULL;
  new_loop();  /* sets current_loop */
  head_rem = current_loop; /* Just for assertion */

  if (interprocedural_view) {
1097
    set_irg_visited(current_ir_graph, inc_max_irg_visited());
1098
1099
    init_ip_walk ();
  } else {
1100
    inc_irg_visited(current_ir_graph);
1101
1102
  }

1103
  scc(get_irg_end(current_ir_graph));
1104
1105
1106
1107

  if (interprocedural_view) finish_ip_walk();

  assert(head_rem == current_loop);
1108
  set_irg_loop(current_ir_graph, current_loop);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
1109
  set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1110
  assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
  /*
  irg->loops = current_loop;
  if (icfg == 1) {
    int count = 0;
    int depth = 0;
    count_loop (the_loop, &count, &depth);
    }
  }
  */
  current_ir_graph = rem;
}
1122
1123


1124
#if 0
1125
void construct_ip_backedges (void) {
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
  ir_graph *rem = current_ir_graph;
  int rem_ipv = interprocedural_view;
  int i, j;

  outermost_ir_graph = get_irp_main_irg();

  init_ip_scc();

  current_loop = NULL;
  new_loop();  /* sets current_loop */
  interprocedural_view = 1;

  inc_max_irg_visited();
  for (i = 0; i < get_irp_n_irgs(); i++)
    set_irg_visited(get_irp_irg(i), get_max_irg_visited());

  for (i = 0; i < get_irp_n_irgs(); i++) {
    ir_node *sb;
    current_ir_graph = get_irp_irg(i);
    /* Find real entry points */
    sb = get_irg_start_block(current_ir_graph);
    if ((get_Block_n_cfgpreds(sb) > 1) ||
Florian Liekweg's avatar
Florian Liekweg committed
1148
    (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1149
1150
1151
1152
1153
1154
1155
1156
1157
    /* Compute scc for this graph */
    outermost_ir_graph = current_ir_graph;
    set_irg_visited(outermost_ir_graph, get_max_irg_visited());
    scc(get_irg_end(current_ir_graph));
    for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
      scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
  }

  set_irg_loop(outermost_ir_graph, current_loop);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
1158
  set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1159
1160
1161
1162
1163
  assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);

  current_ir_graph = rem;
  interprocedural_view = rem_ipv;
}
1164
1165
1166
1167
1168
#else
void construct_ip_backedges (void) {
  ir_graph *rem = current_ir_graph;
  int rem_ipv = interprocedural_view;
  int i;
1169

1170
1171
  assert(get_irp_ip_view_state() == ip_view_valid);

1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
  outermost_ir_graph = get_irp_main_irg();

  init_ip_scc();

  current_loop = NULL;
  new_loop();  /* sets current_loop */
  interprocedural_view = 1;

  inc_max_irg_visited();
  for (i = 0; i < get_irp_n_irgs(); i++)
    set_irg_visited(get_irp_irg(i), get_max_irg_visited());

  /** We have to start the walk at the same nodes as cg_walk. **/
  /* Walk starting at unreachable procedures. Only these
   * have End blocks visible in interprocedural view. */
  for (i = 0; i < get_irp_n_irgs(); i++) {
    ir_node *sb;
    current_ir_graph = get_irp_irg(i);

    sb = get_irg_start_block(current_ir_graph);

    if ((get_Block_n_cfgpreds(sb) > 1) ||
Florian Liekweg's avatar
Florian Liekweg committed
1194
    (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225

    scc(get_irg_end(current_ir_graph));
  }

  /* Check whether we walked all procedures: there could be procedures
     with cyclic calls but no call from the outside. */
  for (i = 0; i < get_irp_n_irgs(); i++) {
    ir_node *sb;
    current_ir_graph = get_irp_irg(i);

    /* Test start block: if inner procedure end and end block are not
     * visible and therefore not marked. */
    sb = get_irg_start_block(current_ir_graph);
    if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
  }

  /* Walk all endless loops in inner procedures.
   * We recognize an inner procedure if the End node is not visited. */
  for (i = 0; i < get_irp_n_irgs(); i++) {
    ir_node *e;
    current_ir_graph = get_irp_irg(i);

    e = get_irg_end(current_ir_graph);
    if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
      int j;
      /* Don't visit the End node. */
      for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
    }
  }

  set_irg_loop(outermost_ir_graph, current_loop);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
1226
  set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1227
1228
1229
1230
1231
1232
  assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);

  current_ir_graph = rem;
  interprocedural_view = rem_ipv;
}
#endif
1233

Götz Lindenmaier's avatar
Götz Lindenmaier committed
1234
1235
1236
1237
1238
1239
static void reset_backedges(ir_node *n) {
  if (is_possible_loop_head(n)) {
    int rem = interprocedural_view;
    interprocedural_view = 1;
    clear_backedges(n);
    interprocedural_view = 0;
1240
    clear_backedges(n);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1241
1242
1243
1244
1245
1246
1247
    interprocedural_view = rem;
  }
}

static void loop_reset_backedges(ir_loop *l) {
  int i;
  reset_backedges(get_loop_node(l, 0));
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
1248
1249
  for (i = 0; i < get_loop_n_nodes(l); ++i)
    set_irn_loop(get_loop_node(l, i), NULL);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1250
1251
1252
  for (i = 0; i < get_loop_n_sons(l); ++i) {
    loop_reset_backedges(get_loop_son(l, i));
  }
1253
1254
1255
1256
1257
}

/** Removes all loop information.
    Resets all backedges */
void free_loop_information(ir_graph *irg) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1258
1259
  if (get_irg_loop(irg))
    loop_reset_backedges(get_irg_loop(irg));
1260
  set_irg_loop(irg, NULL);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
1261
  set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
  /* We cannot free the loop nodes, they are on the obstack. */
}


void free_all_loop_information (void) {
  int i;
  int rem = interprocedural_view;
  interprocedural_view = 1;  /* To visit all filter nodes */
  for (i = 0; i < get_irp_n_irgs(); i++) {
    free_loop_information(get_irp_irg(i));
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1273
1274
  pmap_destroy(node_loop_map);
  node_loop_map = NULL;
1275
1276
  interprocedural_view = rem;
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286





/* Debug stuff *************************************************/

static int test_loop_node(ir_loop *l) {
  int i, has_node = 0, found_problem = 0;
  loop_element le;
Michael Beck's avatar
Michael Beck committed
1287

Götz Lindenmaier's avatar
Götz Lindenmaier committed
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302