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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       SSA construction for a set of nodes
   9  * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
  10  * @date        30.03.2007
  11  *
  12  * The problem: Given a value and a set of "copies" that are known to
  13  * represent the same abstract value, rewire all usages of the original value
  14  * to their closest copy while introducing phis as necessary.
  15  *
  16  * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
  17  * and its copies. Link the copies ordered by dominance to the blocks.  Then
  18  * we search for each use all definitions in the current block, if none is
  19  * found, then we search one in the immediate dominator. If we are in a block
  20  * of the dominance frontier, create a phi and do the same search for all
  21  * phi arguments.
  22  *
  23  * A copy in this context means, that you want to introduce several new
  24  * abstract values (in Firm: nodes) for which you know, that they
  25  * represent the same concrete value. This is the case if you
  26  * - copy
  27  * - spill and reload
  28  * - re-materialize
  29  * a value.
  30  *
  31  * This function reroutes all uses of the original value to the copies in the
  32  * corresponding dominance subtrees and creates Phi functions where necessary.
  33  */
  34 #ifndef FIRM_BE_BESSACONSTR_H
  35 #define FIRM_BE_BESSACONSTR_H
  36
  37 #include <stdbool.h>
  38 #include "firm_types.h"
  39 #include "irnodeset.h"
  40 #include "belive.h"
  41 #include "bitset.h"
  42 #include "pdeq.h"
  43 #include "irnodemap.h"
  44 #include "obst.h"
  45
  46 typedef struct be_ssa_construction_env_t {
  47         ir_graph                    *irg;
  48         ir_mode                     *mode;
  49         const arch_register_req_t   *phi_req;
  50         waitq                       *worklist;
  51         ir_node                    **new_phis;
  52         bool                         iterated_domfront_calculated;
  53         ir_nodemap                   infos;
  54         struct obstack               obst;
  55 } be_ssa_construction_env_t;
  56
  57 /**
  58  * Initializes an SSA construction environment.
  59  *
  60  * @param env    an empty SSA construction environment
  61  * @param irg    the graph
  62  */
  63 void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg);
  64
  65 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
  66                                   ir_node *value);
  67
  68 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
  69                                     ir_node **copies, size_t copies_len);
  70
  71 /**
  72  * Reconstructs the SSA form for all users of node @p node
  73  */
  74 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
  75                                    ir_node *node);
  76
  77 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
  78                                          ir_node **nodes, size_t nodes_len);
  79
  80 /**
  81  * Recompute the liveness of the inserted phis.
  82  * @note Remember that you have to call update_liveness on the copies yourself
  83  */
  84 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
  85                                              be_lv_t *lv);
  86
  87 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env);
  88
  89 /**
  90  * Destroys an SSA construction environment.
  91  */
  92 void be_ssa_construction_destroy(be_ssa_construction_env_t *env);
  93
  94 #endif /* FIRM_BE_BESSACONSTR_H */