nsz Git - libfirm/blob - ir/be/bessaconstr.h

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       SSA construction for a set of nodes
  23  * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
  24  * @date        30.03.2007
  25  *
  26  * The problem: Given a value and a set of "copies" that are known to
  27  * represent the same abstract value, rewire all usages of the original value
  28  * to their closest copy while introducing phis as necessary.
  29  *
  30  * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
  31  * and its copies. Link the copies ordered by dominance to the blocks.  Then
  32  * we search for each use all definitions in the current block, if none is
  33  * found, then we search one in the immediate dominator. If we are in a block
  34  * of the dominance frontier, create a phi and do the same search for all
  35  * phi arguments.
  36  *
  37  * A copy in this context means, that you want to introduce several new
  38  * abstract values (in Firm: nodes) for which you know, that they
  39  * represent the same concrete value. This is the case if you
  40  * - copy
  41  * - spill and reload
  42  * - re-materialize
  43  * a value.
  44  *
  45  * This function reroutes all uses of the original value to the copies in the
  46  * corresponding dominance subtrees and creates Phi functions where necessary.
  47  */
  48 #ifndef FIRM_BE_BESSACONSTR_H
  49 #define FIRM_BE_BESSACONSTR_H
  50
  51 #include "firm_types.h"
  52 #include "bedomfront.h"
  53 #include "irnodeset.h"
  54 #include "belive.h"
  55 #include "bitset.h"
  56 #include "beirg.h"
  57 #include "pdeq.h"
  58 #include "irnodemap.h"
  59 #include "obst.h"
  60
  61 typedef struct be_ssa_construction_env_t {
  62         ir_graph                    *irg;
  63         const be_dom_front_info_t   *domfronts;
  64         ir_mode                     *mode;
  65         const arch_register_req_t   *phi_req;
  66         waitq                       *worklist;
  67         const ir_nodeset_t          *ignore_uses;
  68         ir_node                    **new_phis;
  69         int                          iterated_domfront_calculated;
  70         ir_nodemap                   infos;
  71         struct obstack               obst;
  72 } be_ssa_construction_env_t;
  73
  74 /**
  75  * Initializes an SSA construction environment.
  76  *
  77  * @param env    an empty SSA construction environment
  78  * @param irg    the graph
  79  */
  80 void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg);
  81
  82 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
  83                                   ir_node *value);
  84
  85 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
  86                                     ir_node **copies, size_t copies_len);
  87
  88 void be_ssa_construction_set_ignore_uses(be_ssa_construction_env_t *env,
  89                                          const ir_nodeset_t *ignore_uses);
  90
  91 /**
  92  * Reconstructs the SSA form for all users of node @p node
  93  */
  94 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
  95                                    ir_node *node);
  96
  97 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
  98                                          ir_node **nodes, size_t nodes_len);
  99
 100 /**
 101  * Recompute the liveness of the inserted phis.
 102  * @note Remember that you have to call update_liveness on the copies yourself
 103  */
 104 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
 105                                              be_lv_t *lv);
 106
 107 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env);
 108
 109 /**
 110  * Destroys an SSA construction environment.
 111  */
 112 void be_ssa_construction_destroy(be_ssa_construction_env_t *env);
 113
 114 #endif /* FIRM_BE_BESSACONSTR_H */