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 <stdbool.h>
  52 #include "firm_types.h"
  53 #include "irnodeset.h"
  54 #include "belive.h"
  55 #include "bitset.h"
  56 #include "pdeq.h"
  57 #include "irnodemap.h"
  58 #include "obst.h"
  59
  60 typedef struct be_ssa_construction_env_t {
  61         ir_graph                    *irg;
  62         ir_mode                     *mode;
  63         const arch_register_req_t   *phi_req;
  64         waitq                       *worklist;
  65         ir_node                    **new_phis;
  66         bool                         iterated_domfront_calculated;
  67         ir_nodemap                   infos;
  68         struct obstack               obst;
  69 } be_ssa_construction_env_t;
  70
  71 /**
  72  * Initializes an SSA construction environment.
  73  *
  74  * @param env    an empty SSA construction environment
  75  * @param irg    the graph
  76  */
  77 void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg);
  78
  79 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
  80                                   ir_node *value);
  81
  82 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
  83                                     ir_node **copies, size_t copies_len);
  84
  85 /**
  86  * Reconstructs the SSA form for all users of node @p node
  87  */
  88 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
  89                                    ir_node *node);
  90
  91 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
  92                                          ir_node **nodes, size_t nodes_len);
  93
  94 /**
  95  * Recompute the liveness of the inserted phis.
  96  * @note Remember that you have to call update_liveness on the copies yourself
  97  */
  98 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
  99                                              be_lv_t *lv);
 100
 101 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env);
 102
 103 /**
 104  * Destroys an SSA construction environment.
 105  */
 106 void be_ssa_construction_destroy(be_ssa_construction_env_t *env);
 107
 108 #endif /* FIRM_BE_BESSACONSTR_H */