2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief SSA construction for a set of nodes
9 * @author Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
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.
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
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
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.
34 #ifndef FIRM_BE_BESSACONSTR_H
35 #define FIRM_BE_BESSACONSTR_H
38 #include "firm_types.h"
39 #include "irnodeset.h"
43 #include "irnodemap.h"
46 typedef struct be_ssa_construction_env_t {
49 const arch_register_req_t *phi_req;
52 bool iterated_domfront_calculated;
55 } be_ssa_construction_env_t;
58 * Initializes an SSA construction environment.
60 * @param env an empty SSA construction environment
61 * @param irg the graph
63 void be_ssa_construction_init(be_ssa_construction_env_t *env, ir_graph *irg);
65 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
68 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
69 ir_node **copies, size_t copies_len);
72 * Reconstructs the SSA form for all users of node @p node
74 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
77 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
78 ir_node **nodes, size_t nodes_len);
81 * Recompute the liveness of the inserted phis.
82 * @note Remember that you have to call update_liveness on the copies yourself
84 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
87 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env);
90 * Destroys an SSA construction environment.
92 void be_ssa_construction_destroy(be_ssa_construction_env_t *env);
94 #endif /* FIRM_BE_BESSACONSTR_H */