nsz Git - libfirm/blob - ir/ana/irloop.h

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irloop_t.h
   4  * Purpose:     Loop datastructure and access functions.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     7.2002
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14 * @file irloop.h
  15 *
  16 *  Computes backedges in the control and data flow.
  17 *
  18 *  @author Goetz Lindenmaier
  19 *
  20 *  Only Block and Phi/Filter nodes can have incoming backedges.
  21 *  Constructs loops data structure: indicates loop nesting.
  22 */
  23
  24 # ifndef _IRLOOP_H_
  25 # define _IRLOOP_H_
  26
  27 # include "irgraph.h"
  28 # include "irnode.h"
  29
  30 /* ------------------------------------------------------------------- */
  31 /*
  32  * Backedge information.
  33  *
  34  * Predecessors of Block, Phi and interprocedural Filter nodes can
  35  * have  backedges.  If loop information is computed, this
  36  * information is computed, too.
  37  * The backedge information can only be used if the graph is not in
  38  * phase phase_building.
  39  */
  40 /* ------------------------------------------------------------------- */
  41
  42 /** Returns true if the predesessor pos is a backedge. */
  43 bool is_backedge (ir_node *n, int pos);
  44 /** Remarks that edge pos is a backedge. */
  45 void set_backedge (ir_node *n, int pos);
  46 /** Remarks that edge pos is not a backedge. */
  47 void set_not_backedge (ir_node *n, int pos);
  48 /** Returns true if n has backedges. */
  49 bool has_backedges (ir_node *n);
  50 /** Sets backedge information to zero. */
  51 void clear_backedges (ir_node *n);
  52
  53 /* ------------------------------------------------------------------- */
  54 /**
  55  * The loops datastructure.
  56  *
  57  * The loops datastructure represents circles in the intermediate
  58  * representation.  It does not represent loops in the terms of a
  59  * source program.
  60  * Each ir_graph can contain one outermost loop datastructure.
  61  * loop is the entry point to the nested loops.
  62  * The loop datastructure contains a field indicating the depth of
  63  * the loop within the nesting.  Further it contains a list of the
  64  * loops with nesting depth -1.  Finally it contains a list of all
  65  * nodes in the loop.
  66  *
  67  * @todo We could add a field pointing from a node to the containing loop,
  68  * this would cost a lot of memory, though.
  69  */
  70 /* ------------------------------------------------------------------- */
  71 typedef struct ir_loop ir_loop;
  72
  73 /* Loop elements are loop nodes and ir nodes */
  74 typedef union {
  75     firm_kind *kind;    /**< is either k_ir_node or k_ir_loop */
  76     ir_node *node;      /**< Pointer to an ir_node element */
  77     ir_loop *son;       /**< Pointer to an ir_loop element */
  78 } loop_element;
  79
  80 int      is_ir_loop(const void *thing);
  81
  82 /** Set the outermost loop in ir graph as basic access to loop tree. */
  83 void     set_irg_loop(ir_graph *irg, ir_loop *l);
  84 ir_loop *get_irg_loop(ir_graph *irg);
  85
  86 /** Returns the loop n is contained in.  NULL if node is in no loop. */
  87 ir_loop *get_irn_loop(ir_node *n);
  88
  89 /** Returns outer loop, itself if outermost. */
  90 ir_loop *get_loop_outer_loop (ir_loop *loop);
  91 /** Returns nesting depth of this loop */
  92 int      get_loop_depth (ir_loop *loop);
  93
  94 /* Sons are the inner loops contained in this loop. */
  95 /** Returns the number of inner loops */
  96 int      get_loop_n_sons (ir_loop *loop);
  97 ir_loop *get_loop_son (ir_loop *loop, int pos);
  98 /** Returns the number of nodes contained in loop.  */
  99 int      get_loop_n_nodes (ir_loop *loop);
 100 ir_node *get_loop_node (ir_loop *loop, int pos);
 101
 102 /** Returns the number of elements contained in loop.  */
 103 int      get_loop_n_elements (ir_loop *loop);
 104 /** Returns a loop element.  A loop element can be interpreted as a
 105     kind pointer, an ir_node* or an ir_loop*. */
 106 loop_element get_loop_element (ir_loop *loop, int pos);
 107
 108 /** Returns the element number of the loop son in loop.
 109  *  Returns -1 if not found. O(#elements). */
 110 int get_loop_element_pos(ir_loop *loop, void *le);
 111
 112 /** Returns a unique node number for the loop node to make output
 113     readable. If libfirm_debug is not set it returns the loop cast to
 114     int. */
 115 int get_loop_loop_nr(ir_loop *loop);
 116
 117 /** A field to connect additional information to a loop.  Only valid
 118     if libfirm_debug is set, else returns NULL.  */
 119 void  set_loop_link (ir_loop *loop, void *link);
 120 void *get_loop_link (const ir_loop *loop);
 121
 122 /* ------------------------------------------------------------------- */
 123 /* Constructing and destructing the loop/backedge information.         */
 124 /* ------------------------------------------------------------------- */
 125
 126 /** Constructs backedge information for irg in intraprocedural view.
 127  *  @returns Maximal depth of loop tree. */
 128 /* @@@ Well, maybe construct_loop_information or analyze_loops ? */
 129 int construct_backedges(ir_graph *irg);
 130
 131 /** Constructs backedges for all irgs in interprocedural view.  All
 132     loops in the graph will be marked as such, not only realizeable
 133     loops and recursions in the program.  E.g., if the same funcion is
 134     called twice, there is a loop between the first function return and
 135     the second call.
 136  *  @returns Maximal depth of loop tree. */
 137 int construct_ip_backedges(void);
 138
 139 /* Construct loop tree only for control flow.
 140  * @returns Maximal depth of loop tree. */
 141 int construct_cf_backedges(ir_graph *irg);
 142 int construct_ip_cf_backedges (void);
 143
 144 /** Removes all loop information.
 145     Resets all backedges */
 146 void free_loop_information(ir_graph *irg);
 147 void free_all_loop_information (void);
 148
 149
 150
 151
 152 /* ------------------------------------------------------------------- */
 153 /* Simple analyses based on the loop information                       */
 154 /* ------------------------------------------------------------------- */
 155
 156 /** Test whether a value is loop invariant.
 157  *
 158  * @param n      The node to be tested.
 159  * @param block  A block node.
 160  *
 161  * Returns true, if the node n is not changed in the loop block
 162  * belongs to or in inner loops of this block. */
 163 int is_loop_invariant(ir_node *n, ir_node *block);
 164
 165
 166 #endif /* _IRLOOP_H_ */