From 3caeefd911a54289bbf7d293289964239a6fed96 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Tue, 18 Apr 2017 14:49:38 +0200 Subject: phi-sources can only have a single user (or none) Currently, OP_PHISOURCES have a list as member, 'phi_users', that should link to all phi-nodes using them but: *) phi-sources are never shared between phi-nodes *) this list is useless because it's only created during liveness and not used after. So, replace the list by a simple pointer to hold the unique phi-node using it and keep this link updated during all its lifetime. Signed-off-by: Luc Van Oostenryck Acked-by: Linus Torvalds --- Documentation/IR.rst | 2 +- flow.c | 21 +-------------------- linearize.c | 14 +++++--------- linearize.h | 8 +++++++- liveness.c | 1 - memops.c | 1 + sparse-llvm.c | 2 -- ssa.c | 2 +- storage.c | 30 ------------------------------ 9 files changed, 16 insertions(+), 65 deletions(-) diff --git a/Documentation/IR.rst b/Documentation/IR.rst index 38df84ff..0cc90ec0 100644 --- a/Documentation/IR.rst +++ b/Documentation/IR.rst @@ -381,7 +381,7 @@ Others * .phi_src: operand (type must be compatible with .target, alias .src) * .target: the "result" PSEUDO_PHI * .type: type of .target - * .phi_users: list of phi instructions using the target pseudo + * .phi_node: the unique phi instruction using the target pseudo .. op:: OP_CALL Function call. diff --git a/flow.c b/flow.c index bda277aa..b776375b 100644 --- a/flow.c +++ b/flow.c @@ -46,25 +46,6 @@ static int rewrite_branch(struct basic_block *bb, return 1; } -/// -// returns the phi-node corresponding to a phi-source -static struct instruction *get_phinode(struct instruction *phisrc) -{ - struct pseudo_user *pu; - - FOR_EACH_PTR(phisrc->target->users, pu) { - struct instruction *user; - - if (!pu) - continue; - user = pu->insn; - assert(user->opcode == OP_PHI); - return user; - } END_FOR_EACH_PTR(pu); - assert(0); -} - - /* * Return the known truth value of a pseudo, or -1 if * it's not known. @@ -843,7 +824,7 @@ static int retarget_parents(struct basic_block *bb, struct basic_block *target) static void remove_merging_phisrc(struct basic_block *top, struct instruction *insn) { - struct instruction *user = get_phinode(insn); + struct instruction *user = insn->phi_node; pseudo_t phi; FOR_EACH_PTR(user->phi_list, phi) { diff --git a/linearize.c b/linearize.c index 7a6f745f..c1aeb159 100644 --- a/linearize.c +++ b/linearize.c @@ -407,11 +407,7 @@ const char *show_instruction(struct instruction *insn) break; case OP_PHISOURCE: { - struct instruction *phi; buf += sprintf(buf, "%s <- %s ", show_pseudo(insn->target), show_pseudo(insn->phi_src)); - FOR_EACH_PTR(insn->phi_users, phi) { - buf += sprintf(buf, " (%s)", show_pseudo(phi->target)); - } END_FOR_EACH_PTR(phi); break; } @@ -1683,8 +1679,8 @@ static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *e return (phi1 == VOID) ? phi1 : phi1->def->src; phi_node = alloc_typed_instruction(OP_PHI, expr->ctype); - use_pseudo(phi_node, phi1, add_pseudo(&phi_node->phi_list, phi1)); - use_pseudo(phi_node, phi2, add_pseudo(&phi_node->phi_list, phi2)); + link_phi(phi_node, phi1); + link_phi(phi_node, phi2); phi_node->target = target = alloc_pseudo(phi_node); add_one_insn(ep, phi_node); return target; @@ -1756,7 +1752,7 @@ static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *cty struct instruction *br = delete_last_instruction(&parent->insns); pseudo_t phi = alloc_phi(parent, src, ctype); add_instruction(&parent->insns, br); - use_pseudo(node, phi, add_pseudo(&node->phi_list, phi)); + link_phi(node, phi); } END_FOR_EACH_PTR(parent); } @@ -1789,7 +1785,7 @@ static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr src2 = linearize_expression_to_bool(ep, expr->right); src2 = cast_pseudo(ep, src2, &bool_ctype, ctype); phi2 = alloc_phi(ep->active, src2, ctype); - use_pseudo(node, phi2, add_pseudo(&node->phi_list, phi2)); + link_phi(node, phi2); // join set_activeblock(ep, merge); @@ -2049,7 +2045,7 @@ static void add_return(struct entrypoint *ep, struct basic_block *bb, struct sym } phi = alloc_phi(ep->active, src, ctype); phi->ident = &return_ident; - use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi)); + link_phi(phi_node, phi); } static pseudo_t linearize_fn_statement(struct entrypoint *ep, struct statement *stmt) diff --git a/linearize.h b/linearize.h index a77e4b3e..18f1d80f 100644 --- a/linearize.h +++ b/linearize.h @@ -109,7 +109,7 @@ struct instruction { }; struct /* phi source */ { pseudo_t phi_src; - struct instruction_list *phi_users; + struct instruction *phi_node; }; struct /* unops */ { pseudo_t src; @@ -292,6 +292,12 @@ static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users); } +static inline void link_phi(struct instruction *node, pseudo_t phi) +{ + use_pseudo(node, phi, add_pseudo(&node->phi_list, phi)); + phi->def->phi_node = node; +} + static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count) { delete_ptr_list_entry((struct ptr_list **)list, entry, count); diff --git a/liveness.c b/liveness.c index 30a9a5b6..4fc16e3d 100644 --- a/liveness.c +++ b/liveness.c @@ -260,7 +260,6 @@ static void track_phi_uses(struct instruction *insn) continue; def = phi->def; assert(def->opcode == OP_PHISOURCE); - add_ptr_list(&def->phi_users, insn); } END_FOR_EACH_PTR(phi); } diff --git a/memops.c b/memops.c index 0a1106b0..ff54208e 100644 --- a/memops.c +++ b/memops.c @@ -100,6 +100,7 @@ found_dominator: phi->ident = phi->ident ? : one->target->ident; add_instruction(&parent->insns, br); use_pseudo(insn, phi, add_pseudo(dominators, phi)); + phi->def->phi_node = insn; } END_FOR_EACH_PTR(parent); return 1; } diff --git a/sparse-llvm.c b/sparse-llvm.c index 658744ee..9ceb19a9 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -1342,8 +1342,6 @@ int main(int argc, char **argv) compile(module, symlist); - /* need ->phi_users */ - dbg_dead = 1; FOR_EACH_PTR(filelist, file) { symlist = sparse(file); if (die_if_error) diff --git a/ssa.c b/ssa.c index 4c86c55c..b9044207 100644 --- a/ssa.c +++ b/ssa.c @@ -350,7 +350,7 @@ static void ssa_rename_phi(struct instruction *insn) pseudo_t phi = alloc_phi(par, val, var); phi->ident = var->ident; add_instruction(&par->insns, term); - use_pseudo(insn, phi, add_pseudo(&insn->phi_list, phi)); + link_phi(insn, phi); mark_phi_used(val); } END_FOR_EACH_PTR(par); } diff --git a/storage.c b/storage.c index acbc477d..6fc6e3d7 100644 --- a/storage.c +++ b/storage.c @@ -261,35 +261,6 @@ static void set_up_argument_storage(struct entrypoint *ep, struct basic_block *b } END_FOR_EACH_PTR(arg); } -/* - * One phi-source may feed multiple phi nodes. If so, combine - * the storage output for this bb into one entry to reduce - * storage pressure. - */ -static void combine_phi_storage(struct basic_block *bb) -{ - struct instruction *insn; - FOR_EACH_PTR(bb->insns, insn) { - struct instruction *phi; - struct storage *last; - - if (!insn->bb || insn->opcode != OP_PHISOURCE) - continue; - last = NULL; - FOR_EACH_PTR(insn->phi_users, phi) { - struct storage *storage = lookup_storage(bb, phi->target, STOR_OUT); - if (!storage) { - DELETE_CURRENT_PTR(phi); - continue; - } - if (last && storage != last) - storage = combine_storage(storage, last); - last = storage; - } END_FOR_EACH_PTR(phi); - PACK_PTR_LIST(&insn->phi_users); - } END_FOR_EACH_PTR(insn); -} - void set_up_storage(struct entrypoint *ep) { struct basic_block *bb; @@ -300,7 +271,6 @@ void set_up_storage(struct entrypoint *ep) /* Then do a list of all the inter-bb storage */ FOR_EACH_PTR(ep->bbs, bb) { set_up_bb_storage(bb); - combine_phi_storage(bb); } END_FOR_EACH_PTR(bb); name_storage(); -- cgit 1.2.3-korg