2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief SSA construction for a set of nodes
23 * @author Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
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.
31 * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
32 * and its 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
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
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.
49 #ifndef FIRM_BE_BESSACONSTR_H
50 #define FIRM_BE_BESSACONSTR_H
52 #include "firm_types.h"
53 #include "bedomfront.h"
54 #include "irnodeset.h"
59 #include "irnodemap.h"
62 typedef struct be_ssa_construction_env_t {
64 const be_dom_front_info_t *domfronts;
66 const arch_register_class_t *phi_cls;
68 const ir_nodeset_t *ignore_uses;
70 int iterated_domfront_calculated;
73 } be_ssa_construction_env_t;
76 * Initializes an SSA construction environment.
78 * @param env an empty SSA construction environment
79 * @param irg the graph
81 void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg);
83 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
86 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
87 ir_node **copies, size_t copies_len);
89 void be_ssa_construction_set_ignore_uses(be_ssa_construction_env_t *env,
90 const ir_nodeset_t *ignore_uses);
93 * Reconstructs the SSA form for all users of node @p node
95 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
98 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
99 ir_node **nodes, size_t nodes_len);
102 * Recompute the liveness of the inserted phis.
103 * @note Remember that you have to call update_liveness on the copies yourself
105 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
108 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env);
111 * Destroys an SSA construction environment.
113 void be_ssa_construction_destroy(be_ssa_construction_env_t *env);
115 #endif /* FIRM_BE_BESSACONSTR_H */