| Message ID | 20201116222927.51939-5-luc.vanoostenryck@gmail.com (mailing list archive) |
|---|---|
| State | Mainlined, archived |
| Headers | show |
| Series | cfg: early CFG simplification | expand |
On Mon, Nov 16, 2020 at 2:30 PM Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > +static void adjust_phisrc(struct basic_block *top, struct instruction *insn) My only issue is that this is a really odd name, and calling convention. "adjust"? Wouldn't it be more sensible to call this "remove_phisrc()", because that's what it does. It removes the matching phisrc instruction in the specified basic block. (I also think it might be a bit more obvious to do the get_phinode() in the caller, and simply pass in the OP_PHI instruction, but maybe you had reasons to do it that way). Linus
On Mon, Nov 16, 2020 at 02:53:21PM -0800, Linus Torvalds wrote: > On Mon, Nov 16, 2020 at 2:30 PM Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > > > > +static void adjust_phisrc(struct basic_block *top, struct instruction *insn) > > My only issue is that this is a really odd name, and calling convention. > > "adjust"? > > Wouldn't it be more sensible to call this "remove_phisrc()", because > that's what it does. It removes the matching phisrc instruction in the > specified basic block. Yes, the name is horrible and doesn't mean much. I'll change it. > (I also think it might be a bit more obvious to do the get_phinode() > in the caller, and simply pass in the OP_PHI instruction, but maybe > you had reasons to do it that way). In fact, I wrote it first like that but then I've another piece of code that need exactly the same info so I change it into a separate function. This code is a bit weird though, because it actively use the fact that each phi-sources feeds a single phi-node while the underlying data structures are designed so that phi-sources can be shared between phi-nodes (but I think that allowing them the be effectively shared would bring too much problems). -- Luc
On Mon, Nov 16, 2020 at 3:47 PM Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > This code is a bit weird though, because it actively use the fact > that each phi-sources feeds a single phi-node while the underlying > data structures are designed so that phi-sources can be shared > between phi-nodes (but I think that allowing them the be effectively > shared would bring too much problems). Yeah, the phisource nodes are strange I was confused when I wrote the original phi code, and you fixed it all up (to the point where I suspect none of my original confusion exists ;^), but they are still a bit strange. Could the phi_users list be just replaced by the target (OP_PHI) pseudo (or instruction)? Linus Linus
On Mon, Nov 16, 2020 at 04:16:01PM -0800, Linus Torvalds wrote: > > Could the phi_users list be just replaced by the target (OP_PHI) > pseudo (or instruction)? Yes, trivially if set liveness is calculated. But this information could be useful earlier, then it would need some work to track it (not sure it would be worth, though). -- Luc
diff --git a/flow.c b/flow.c index 9ae8612a2312..e9c8f6b7355e 100644 --- a/flow.c +++ b/flow.c @@ -43,6 +43,25 @@ 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. @@ -723,6 +742,24 @@ void vrfy_flow(struct entrypoint *ep) assert(!entry); } +static void adjust_phisrc(struct basic_block *top, struct instruction *insn) +{ + struct instruction *user = get_phinode(insn); + pseudo_t phi; + + FOR_EACH_PTR(user->phi_list, phi) { + struct instruction *phisrc; + + if (phi == VOID) + continue; + phisrc = phi->def; + if (phisrc->bb != top) + continue; + REPLACE_CURRENT_PTR(phi, VOID); + kill_instruction(phisrc); + } END_FOR_EACH_PTR(phi); +} + /// // merge two BBs // @top: the first BB to be merged @@ -748,6 +785,11 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot) if (!insn->bb) continue; assert(insn->bb == bot); + switch (insn->opcode) { + case OP_PHISOURCE: + adjust_phisrc(top, insn); + break; + } insn->bb = top; add_instruction(&top->insns, insn); } END_FOR_EACH_PTR(insn); diff --git a/validation/optim/merge_bbe-adjust_phi.c b/validation/optim/merge_bbe-adjust_phi.c index de4c54cc6d49..6a8ebb73a62d 100644 --- a/validation/optim/merge_bbe-adjust_phi.c +++ b/validation/optim/merge_bbe-adjust_phi.c @@ -16,7 +16,6 @@ int select(void) /* * check-name: merge_bbe-adjust_phi * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-excludes: phisrc\\.
When merging two basic blocks, it may happen that both of theses blocks contain a phi-source for the same phi-node. In this case, only the phi-source from the bottom BB must be taken in account, it kinda overwrites the value from the top BB and the phi-source from the top BB must be ignored, in fact it must be removed. However, it is not the case and this extra phi-source creates different kind of problems. Among other things, it hinders further simplifications. For example, the following code: extern int array[2]; static inline int stupid_select(int idx) { if (idx) idx = 0; return array[idx]; } int select(void) { int d = stupid_select(-1); return d; } should boil down to a simple dereference of the array with an index of zero, like: select: load.32 %r8 <- 0[array] ret.32 %r8 but currently gives: select: phisrc.32 %phi3(idx) <- $0xffffffff phisrc.32 %phi4(idx) <- $0 phi.32 %r12(idx) <- %phi3(idx), %phi4(idx) sext.64 %r5 <- (32) %r12(idx) mul.64 %r6 <- %r5, $4 add.64 %r7 <- %r6, array load.32 %r8 <- 0[%r7] ret.32 %r8 This patch takes care of the problem by: * when merging 2 BBs, check when reaching a phi-source in the bottom BB * if one is found, look after sibling phi-sources * remove such sibling if belonging to the top BB. With this change, the code above gives: select: phisrc.32 %phi4(idx) <- $0 phi.32 %r12(idx) <- %phi4(idx) sext.64 %r5 <- (32) %r12(idx) mul.64 %r6 <- %r5, $4 add.64 %r7 <- %r6, array load.32 %r8 <- 0[%r7] ret.32 %r8 which can the be simplified into the expected result. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- flow.c | 42 +++++++++++++++++++++++++ validation/optim/merge_bbe-adjust_phi.c | 1 - 2 files changed, 42 insertions(+), 1 deletion(-)