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  * @version     $Id$
  26  *
  27  * The problem: Given a value and a set of "copies" that are known to
  28  * represent the same abstract value, rewire all usages of the original value
  29  * to their closest copy while introducing phis as necessary.
  30  *
  31  * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
  32  * and it's copies. Link the copies ordered by dominance to the blocks.  Then
  33  * we search for each use all definitions in the current block, if none is
  34  * found, then we search one in the immediate dominator. If we are in a block
  35  * of the dominance frontier, create a phi and do the same search for all
  36  * phi arguments.
  37  *
  38  * A copy in this context means, that you want to introduce several new
  39  * abstract values (in Firm: nodes) for which you know, that they
  40  * represent the same concrete value. This is the case if you
  41  * - copy
  42  * - spill and reload
  43  * - re-materialize
  44  * a value.
  45  *
  46  * This function reroutes all uses of the original value to the copies in the
  47  * corresponding dominance subtrees and creates Phi functions where necessary.
  48  */
  49 #ifndef FIRM_BE_BESSACONSTR_H
  50 #define FIRM_BE_BESSACONSTR_H
  51
  52 #include "firm_types.h"
  53 #include "bedomfront.h"
  54 #include "irnodeset.h"
  55 #include "belive.h"
  56 #include "bitset.h"
  57 #include "beirg.h"
  58 #include "pdeq.h"
  59
  60 typedef struct be_ssa_construction_env_t {
  61         ir_graph                  *irg;
  62         const be_dom_front_info_t *domfronts;
  63         ir_mode                   *mode;
  64         waitq                     *worklist;
  65         const ir_nodeset_t        *ignore_uses;
  66         ir_node                   **new_phis;
  67         int                       iterated_domfront_calculated;
  68         int                       min_dom;
  69         int                       max_dom;
  70 } be_ssa_construction_env_t;
  71
  72 /**
  73  * Initializes an SSA construction environment.
  74  *
  75  * @param env    an SSA empty construction environment
  76  * @param birg
  77  */
  78 void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg);
  79
  80 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
  81                                   ir_node *value);
  82
  83 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
  84                                     ir_node **copies, size_t copies_len);
  85
  86 void be_ssa_construction_set_ignore_uses(be_ssa_construction_env_t *env,
  87                                          const ir_nodeset_t *ignore_uses);
  88
  89 /**
  90  * Reconstructs the ssa form for all users of node @p node
  91  */
  92 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
  93                                    ir_node *node);
  94
  95 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
  96                                          ir_node **nodes, size_t nodes_len);
  97
  98 /**
  99  * Recompute the liveness of the inserted phis.
 100  * @note Remember that you have to call update_liveness on the copies yourself
 101  */
 102 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
 103                                              be_lv_t *lv);
 104
 105 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env);
 106
 107 /**
 108  * Destroys an ssa construction environment.
 109  */
 110 void be_ssa_construction_destroy(be_ssa_construction_env_t *env);
 111
 112 #endif /* FIRM_BE_BESSACONSTR_H */