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