Message ID | 20170509220619.72375-1-luc.vanoostenryck@gmail.com (mailing list archive) |
---|---|
State | Superseded, archived |
Headers | show |
Over all looks good. Some minor comment follows. On Tue, May 9, 2017 at 3:06 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > +/* > + * Essentially the same as linearize_ptr_list() > + * but ignoring VOID. > + * Returns 0 if the the list contained the expected > + * number of element, 1 or -1 if there was more or less. > + */ > +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list) The function name does not reflect that it is going to skip the VOID entry and the API to return value is a little bit non straight forward. e.g. If the result entries is less than the quest one, there is no way to get know the exact number of entry returned. Just RFC here, how about having one helper function to do the normal linearize ptr and skip the VOID entry. Which return how many entry it scanned. (it return n+1 if there is more than n request one). Then the second function you can do the compare to "n" thing. After inline it would behave exactly like your current function. > +{ > + pseudo_t phi; > + int i = 0; > + > + FOR_EACH_PTR(list, phi) { > + if (phi == VOID) > + continue; > + if (i >= n) > + return 1; > + array[i++] = phi; > + } END_FOR_EACH_PTR(phi); > + return (i == n) ? 0 : -1; Maybe here can be use (i - n)?, it will return -2 if 2 entry less than requested. > - pseudo_t array[3]; > + pseudo_t array[2]; > struct basic_block *parents[3]; > struct basic_block *bb, *bb1, *bb2, *source; > struct instruction *br; > pseudo_t p1, p2; > > bb = insn->bb; > - if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2) > + if (get_phi_list(array, 2, insn->phi_list) != 0) It is not necessary to compare to zero. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, May 11, 2017 at 7:13 PM, Christopher Li <sparse@chrisli.org> wrote: > Over all looks good. Some minor comment follows. > > On Tue, May 9, 2017 at 3:06 PM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: >> +/* >> + * Essentially the same as linearize_ptr_list() >> + * but ignoring VOID. >> + * Returns 0 if the the list contained the expected >> + * number of element, 1 or -1 if there was more or less. >> + */ >> +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list) > > The function name does not reflect that it is going to skip the VOID entry Well yes, but I wasn't ready to use a name like 'get_real_phi_list()' or something like this. These VOIDs really mean 'there is no element here/ the entry has been removed'. So, I think that it's the right thing to put the VOID thing in the comment and have such a function name. But I can look after another name. > and the API to return value is a little bit non straight forward. e.g. > If the result entries is less than the quest one, there is no way to get > know the exact number of entry returned. Yes, I know. My first version did this but then I changed my mind because it was slightly easier so and having the exact number returned is not needed (it's not like we're we're doing some dynamic allocation and redo a malloc() with the right number if the initial guess was too small). The only thing that really matters here is if the effective number of phisrc is the one we're interested in: 2. OTOH, I don't have a strong opinion on how it should best be done and other uses can maybe be interested in the exact number. > Just RFC here, how about having one helper function to do > the normal linearize ptr and skip the VOID entry. Which return how > many entry it scanned. (it return n+1 if there is more than n request one). > > Then the second function you can do the compare to "n" thing. > After inline it would behave exactly like your current function. I'll see what I can do in this direction. >> +{ >> + pseudo_t phi; >> + int i = 0; >> + >> + FOR_EACH_PTR(list, phi) { >> + if (phi == VOID) >> + continue; >> + if (i >= n) >> + return 1; >> + array[i++] = phi; >> + } END_FOR_EACH_PTR(phi); >> + return (i == n) ? 0 : -1; > > Maybe here can be use (i - n)?, it will return -2 if 2 entry less than > requested. Yes, it's a possibility. >> - pseudo_t array[3]; >> + pseudo_t array[2]; >> struct basic_block *parents[3]; >> struct basic_block *bb, *bb1, *bb2, *source; >> struct instruction *br; >> pseudo_t p1, p2; >> >> bb = insn->bb; >> - if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2) >> + if (get_phi_list(array, 2, insn->phi_list) != 0) > > It is not necessary to compare to zero. Indeed. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, May 11, 2017 at 8:50 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > On Thu, May 11, 2017 at 7:13 PM, Christopher Li <sparse@chrisli.org> wrote: >> Over all looks good. Some minor comment follows. >> >> On Tue, May 9, 2017 at 3:06 PM, Luc Van Oostenryck >> <luc.vanoostenryck@gmail.com> wrote: >>> +/* >>> + * Essentially the same as linearize_ptr_list() >>> + * but ignoring VOID. >>> + * Returns 0 if the the list contained the expected >>> + * number of element, 1 or -1 if there was more or less. >>> + */ >>> +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list) >> >> The function name does not reflect that it is going to skip the VOID entry > > Well yes, but I wasn't ready to use a name like 'get_real_phi_list()' or > something like this. These VOIDs really mean 'there is no element here/ > the entry has been removed'. So, I think that it's the right thing to put > the VOID thing in the comment and have such a function name. > > But I can look after another name. > >> and the API to return value is a little bit non straight forward. e.g. >> If the result entries is less than the quest one, there is no way to get >> know the exact number of entry returned. > > Yes, I know. > My first version did this but then I changed my mind because > it was slightly easier so and having the exact number returned > is not needed (it's not like we're we're doing some dynamic allocation > and redo a malloc() with the right number if the initial guess was too > small). The only thing that really matters here is if the effective number > of phisrc is the one we're interested in: 2. > > OTOH, I don't have a strong opinion on how it should best be done > and other uses can maybe be interested in the exact number. > >> Just RFC here, how about having one helper function to do >> the normal linearize ptr and skip the VOID entry. Which return how >> many entry it scanned. (it return n+1 if there is more than n request one). >> >> Then the second function you can do the compare to "n" thing. >> After inline it would behave exactly like your current function. > > I'll see what I can do in this direction. I've looked at this and I really think that it would make things more complicated than needed for no advantages. The function is really a local helper, something specialized, unlike linearize_ptr_list(). So I've changed a bit the name, the comment, the prototype and the meaning of the function to make this more obvious (and yes avoid to (mis)reuse this function in others contexts). New version is coming. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/simplify.c b/simplify.c index 5d00937f1..cf9ca15f2 100644 --- a/simplify.c +++ b/simplify.c @@ -26,16 +26,37 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud return first_basic_block(source->parents); } +/* + * Essentially the same as linearize_ptr_list() + * but ignoring VOID. + * Returns 0 if the the list contained the expected + * number of element, 1 or -1 if there was more or less. + */ +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list) +{ + pseudo_t phi; + int i = 0; + + FOR_EACH_PTR(list, phi) { + if (phi == VOID) + continue; + if (i >= n) + return 1; + array[i++] = phi; + } END_FOR_EACH_PTR(phi); + return (i == n) ? 0 : -1; +} + static int if_convert_phi(struct instruction *insn) { - pseudo_t array[3]; + pseudo_t array[2]; struct basic_block *parents[3]; struct basic_block *bb, *bb1, *bb2, *source; struct instruction *br; pseudo_t p1, p2; bb = insn->bb; - if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2) + if (get_phi_list(array, 2, insn->phi_list) != 0) return 0; if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2) return 0; diff --git a/validation/optim/void-if-convert.c b/validation/optim/void-if-convert.c new file mode 100644 index 000000000..66513c4dc --- /dev/null +++ b/validation/optim/void-if-convert.c @@ -0,0 +1,19 @@ +int foo(int a) +{ + if (a) + return 0; + else + return 1; + return 2; +} + +/* + * check-name: Ignore VOID in if-convert + * check-command: test-linearize -Wno-decl $file + * check-output-ignore + * + * check-output-excludes: phisrc\\. + * check-output-excludes: phi\\. + * check-output-excludes: VOID + * check-output-contains: seteq\\. + */
Simple if-then-else expressions can often be replaced by an OP_SELECT. This is done in a very generic way by looking not at the test/if part but at OP_PHIs which contain exactly 2 values. An implementation detail makes that the address of valid OP_PHI's sources must not change, so the list holding these values must not be repacked and such. As consequence, when a value need to be removed from the list this value is simply replaced in the list by a VOID. These VOIDs must then be ignored when processing OP_PHI's sources. But for the if-conversion, these VOID are not ignored and are thus considered like any other value which in turn make miss some optimizatin opportunities. For example code like: int foo(int a) { if (a) return 0; else return 1; return 2; } will be linearized into something like: ... phi.32 %r2 <- %phi1, %phi2, VOID ret.32 %r2 where %phi1 & %phi2 correspond to the 'return 0' & 'return 1' and the VOID correspond to the dead 'return 2'. This code should be trivially be converted to a select but is not because the OP_PHI is considered as having 3 elements instead of 2. Fix this by filtering out these VOIDs before checking the conditions of the if-conversion. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- simplify.c | 25 +++++++++++++++++++++++-- validation/optim/void-if-convert.c | 19 +++++++++++++++++++ 2 files changed, 42 insertions(+), 2 deletions(-) create mode 100644 validation/optim/void-if-convert.c