[GIT PULL] llvm fixes

[GIT PULL] llvm fixes

[Luc Van Oostenryck]

Chris,

Please, pull these patches for master. 

No surprises here, it's just all March's good old fixes
for sparse-llvm which have been rebased on top of rc5.

Thanks,
Luc

----------------------------------------------------------------
The following changes since commit 90859bb4e3f9ad11f76ad42e3dce84043bdc3176:

  Bump sparse's version to -rc5 (2017-08-11 18:17:41 +0200)

are available in the git repository at:

  git://github.com/lucvoo/sparse.git llvm-fixes

for you to fetch changes up to fa5266b1770cf8d97158beb290af084082cd335a:

  llvm: fix creation of sparsec's tmp files (2017-08-12 16:05:11 +0200)

----------------------------------------------------------------
Luc Van Oostenryck (68):
      show OP_PHI without VOID
      don't output value of anonymous symbol's pointer
      add table to "negate" some opcode
      use opcode table for compare_opcode()
      canonicalize binops before simplification
      canonicalize compare instructions
      add is_signed_type()
      fix usage of inlined calls
      inlined calls should not block BB packing
      give function's arguments a type via OP_PUSH
      insure that all OP_PUSHs are just before their OP_CALL
      give a type to OP_PHISOURCEs
      give a type to OP_SELs, always
      give a type to OP_SWITCHs
      add doc about sparse's instructions/IR
      add support for wider type in switch-case
      llvm: remove unneeded arg 'module'
      llvm: remove unneeded 'generation'
      llvm: remove unneeded function::type
      llvm: reduce scope of 'bb_nr'
      llvm: use pseudo_list_size() instead of open coding it
      llvm: give arguments a name
      llvm: give a name to call's return values
      llvm: avoid useless temp variable
      llvm: extract get_sym_value() from pseudo_to_value()
      llvm: fix test of floating-point type
      llvm: fix translation of PSEUDO_VALs into a ValueRefs
      llvm: fix output_op_store() which modify its operand
      llvm: fix output_op_[ptr]cast()
      llvm: take care of degenerated rvalues
      llvm: add test cases for symbol's address
      llvm: add test cases for pointers passed as argument
      llvm: add test cases for arrays passed as argument
      llvm: add test cases for degenerated pointers
      llvm: add support for OP_NEG
      llvm: add support for OP_SETVAL with floats
      llvm: add support for OP_SETVAL with labels
      llvm: ignore OP_INLINED_CALL
      llvm: fix pointer/float mixup in comparisons
      llvm: fix type in comparison with an address constant
      llvm: give correct type to binops
      llvm: adjust OP_RET's type
      llvm: variadic functions are not being marked as such
      llvm: fix type of switch constants
      llvm: make pseudo_name() more flexible
      llvm: give a name to all values
      llvm: add support for OP_SWITCH with a range
      llvm: fix OP_SWITCH has no target
      llvm: make value_to_pvalue() more flexible
      llvm: make value_to_ivalue() more flexible
      llvm: add test case pointer compare with cast
      llvm: let pseudo_to_value() directly use the type
      llvm: remove unneeded pseudo_to_value() unneeded argument
      llvm: introduce get_ioperand()
      llvm: fix mutating function pointer
      llvm: fix mutated OP_RET
      llvm: fix mutated OP_SEL
      llvm: fix mutated OP_SWITCH
      llvm: fix mutated OP_PHISOURCE
      llvm: fix mutated OP_[PTR]CAST
      llvm: add support for restricted types
      llvm: fix get value from initialized symbol
      llvm: fix get value from non-anonymous symbol
      llvm: fix type of bitfields
      llvm: add support for OP_FPCAST
      llvm: add support for cast from floats
      llvm: cleanup of output_[ptr]cast()
      llvm: fix creation of sparsec's tmp files

 Documentation/instructions.txt          | 296 ++++++++++++++++
 Makefile                                |   1 +
 compile-i386.c                          |  14 +-
 example.c                               |   4 +-
 flow.c                                  |   3 +-
 linearize.c                             |  80 +++--
 linearize.h                             |  17 +-
 liveness.c                              |  14 +-
 memops.c                                |   2 +-
 opcode.c                                |  36 ++
 opcode.h                                |  10 +
 show-parse.c                            |  11 +-
 simplify.c                              |  77 ++---
 sparse-llvm.c                           | 586 +++++++++++++++++++++-----------
 sparsec                                 |   4 +-
 symbol.h                                |   9 +
 validation/backend/cast.c               |   7 +-
 validation/backend/compare-with-null.c  |  12 +
 validation/backend/constant-pointer.c   |  24 ++
 validation/backend/degenerate-ptr.c     |  72 ++++
 validation/backend/function-ptr-xtype.c |  37 ++
 validation/backend/function-ptr.c       | 148 +++++++-
 validation/backend/label-as-value.c     |  13 +
 validation/backend/load-global.c        |  21 ++
 validation/backend/pointer-add.c        |  54 +++
 validation/backend/pointer-cmp.c        |  12 +
 validation/backend/pointer-param.c      |  42 +++
 validation/backend/pointer-sub.c        |  17 +
 validation/backend/setval.c             |   7 +
 validation/backend/shift-special.c      |  13 +
 validation/backend/store-x2.c           |  16 +
 validation/backend/string-value.c       |  21 ++
 validation/backend/switch.c             | 248 ++++++++++++++
 validation/backend/symaddr.c            |  70 ++++
 validation/backend/type-constant.c      |  23 ++
 validation/call-inlined.c               |  54 +++
 validation/call-variadic.c              |  31 ++
 validation/loop-linearization.c         |   9 +-
 validation/optim/call-inlined.c         |  30 ++
 validation/optim/canonical-cmp.c        | 124 +++++++
 validation/push-call.c                  |  26 ++
 validation/switch-long.c                |  47 +++
 42 files changed, 2024 insertions(+), 318 deletions(-)
 create mode 100644 Documentation/instructions.txt
 create mode 100644 opcode.c
 create mode 100644 opcode.h
 create mode 100644 validation/backend/compare-with-null.c
 create mode 100644 validation/backend/constant-pointer.c
 create mode 100644 validation/backend/degenerate-ptr.c
 create mode 100644 validation/backend/function-ptr-xtype.c
 create mode 100644 validation/backend/label-as-value.c
 create mode 100644 validation/backend/load-global.c
 create mode 100644 validation/backend/pointer-add.c
 create mode 100644 validation/backend/pointer-cmp.c
 create mode 100644 validation/backend/pointer-param.c
 create mode 100644 validation/backend/pointer-sub.c
 create mode 100644 validation/backend/setval.c
 create mode 100644 validation/backend/shift-special.c
 create mode 100644 validation/backend/store-x2.c
 create mode 100644 validation/backend/string-value.c
 create mode 100644 validation/backend/switch.c
 create mode 100644 validation/backend/symaddr.c
 create mode 100644 validation/backend/type-constant.c
 create mode 100644 validation/call-inlined.c
 create mode 100644 validation/call-variadic.c
 create mode 100644 validation/optim/call-inlined.c
 create mode 100644 validation/optim/canonical-cmp.c
 create mode 100644 validation/push-call.c
 create mode 100644 validation/switch-long.c

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Mon, Sep 18, 2017 at 11:51:35AM +0200, Luc Van Oostenryck wrote:
> Chris,
> 
> Please, pull these patches for master. 
> 
> No surprises here, it's just all March's good old fixes
> for sparse-llvm which have been rebased on top of rc5.
> 
> Thanks,
> Luc


Chris,

Can you handle this, please?


-- Luc Van Oostenryck

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Mon, Sep 18, 2017 at 11:51:35AM +0200, Luc Van Oostenryck wrote:
> Chris,
> 
> Please, pull these patches for master. 
> 
> No surprises here, it's just all March's good old fixes
> for sparse-llvm which have been rebased on top of rc5.
> 
> Thanks,
> Luc


Chris,

This have been posted 4 weeks ago and I sent a reminder two weeks ago
but I haven't seen anything from you. Same for the patches series I sent
about the same time.

Is there any hopes to see things moving forward soon?

Regards,
-- Luc

Re: [GIT PULL] llvm fixes

[Christopher Li]

On Mon, Sep 18, 2017 at 5:51 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Chris,
>
> Please, pull these patches for master.
>
> No surprises here, it's just all March's good old fixes
> for sparse-llvm which have been rebased on top of rc5.
>

Hi Luc,

Sorry for the delay. I will start to reply to your patch email in this series.
I have some feed back store on my computer a while back but I haven't
have to the chance send out the email.

Over all the the series seems good. It seems have some measurable
speed up in my stress test. There is one of two patch I will comment more
in the follow up email. I will reply in the order of the patch send
out. If a patch
does not have comment, that means it looks good to me.

BTW, I think a lot of the 68 patches can be break into smaller series.
There is some inter dependency but not that much especially relate to
the testsuite. Smaller series will make it easier to review.

More email to follow up.

Thanks for the series and sorry for the delay.

Chris

Re: [GIT PULL] llvm fixes

[Christopher Li]

On Mon, Sep 18, 2017 at 5:51 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Chris,
>
> Please, pull these patches for master.

Ah, I can't find the exact corresponding patch series in the email.
So I will just comment from the git change.
=========quote===========
commit ae7fd3b06c225fd8faf67c3e20db07b64eca7fc3
 don't output value of anonymous symbol's pointer

    The value of this pointer is of no use unless you're
    using a debugger (or just to see if two things are
    identical or not) and it's presence produces noise
    when comparing the output of two runs for testing.

    Change this by issuing it only if 'verbose' is set.
diff --git a/linearize.c b/linearize.c
index 42d1680..b69f838 100644
--- a/linearize.c
+++ b/linearize.c
@@ -120,7 +120,7 @@ const char *show_pseudo(pseudo_t pseudo)
                        break;
                }
                expr = sym->initializer;
-               snprintf(buf, 64, "<anon symbol:%p>", sym);
+               snprintf(buf, 64, "<anon symbol:%p>", verbose ? sym : NULL);
=======================================================

Very trivial feed back:

I think it is better not print out the %p for NULL.
Just skip the %p if not verbose was set.

BTW, I understand you are reluctant to make trivial change to very
old series of branch. That make sense.

In that case, I can make a topic branch to track the feedback and fix up
as incremental change. Then integrate that branch when all the feedback
settle down. I don't mind writing some feedback patches myself if
you prefer.

Thanks

Chris

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Mon, Oct 30, 2017 at 07:31:28AM +0800, Christopher Li wrote:
> On Mon, Sep 18, 2017 at 5:51 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Chris,
> >
> > Please, pull these patches for master.
> 
> Ah, I can't find the exact corresponding patch series in the email.
> So I will just comment from the git change.
> =========quote===========
> commit ae7fd3b06c225fd8faf67c3e20db07b64eca7fc3
>  don't output value of anonymous symbol's pointer
> 
>     The value of this pointer is of no use unless you're
>     using a debugger (or just to see if two things are
>     identical or not) and it's presence produces noise
>     when comparing the output of two runs for testing.
> 
>     Change this by issuing it only if 'verbose' is set.
> diff --git a/linearize.c b/linearize.c
> index 42d1680..b69f838 100644
> --- a/linearize.c
> +++ b/linearize.c
> @@ -120,7 +120,7 @@ const char *show_pseudo(pseudo_t pseudo)
>                         break;
>                 }
>                 expr = sym->initializer;
> -               snprintf(buf, 64, "<anon symbol:%p>", sym);
> +               snprintf(buf, 64, "<anon symbol:%p>", verbose ? sym : NULL);
> =======================================================
> 
> Very trivial feed back:
> 
> I think it is better not print out the %p for NULL.
> Just skip the %p if not verbose was set.

Skipping the '%p' is more complex than what the patch here is doing.
Printing the NULL has also the advantage to have the same output format
which is usefull when the output is analysed by scripts.
 
> BTW, I understand you are reluctant to make trivial change to very
> old series of branch. That make sense.

Yes, "old series" is the keywords here: this series have been posted
in March, 7 months ago, and have never received any feedback.

> In that case, I can make a topic branch to track the feedback and fix up
> as incremental change. Then integrate that branch when all the feedback
> settle down. I don't mind writing some feedback patches myself if
> you prefer.

Well, given it has taken 7 months to have the first feedback, the
usefulness of this feedback and given the 'speed' at wich you handle
patches, pull requests or questions, I wonder how much months or years
this will take (and this series is only the very first one, many others
are waiing, albeit smaller ones, totalling about 230-400 patches).

If it wasn't clear yet: nor the quality of your feedback, nor its 'speed'
is of any use for doing development, on the contrary.

-- Luc

Re: [GIT PULL] llvm fixes

[Christopher Li]

>commit e4a0824120939235e40277a57425a72fbfcd5b9b
>Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>Date:   Sun Mar 26 19:35:14 2017 +0200
>
>    add table to "negate" some opcode
>
>    Some optimizations transform an instruction opcode
>    into another. For example, it may be needed to know
>    the opcode corresponding to the negation of a comparison.
>
>    This patch make this easy and flexible by adding a table
>    for the relation between opcodes.

>+const struct opcode_table opcode_table[OP_LAST] = {
>+      [OP_SET_EQ] = { .negate = OP_SET_NE, },
>+      [OP_SET_NE] = { .negate = OP_SET_EQ, },
>+      [OP_SET_LT] = { .negate = OP_SET_GE, },
>+      [OP_SET_LE] = { .negate = OP_SET_GT, },
>+      [OP_SET_GE] = { .negate = OP_SET_LT, },
>+      [OP_SET_GT] = { .negate = OP_SET_LE, },
>+      [OP_SET_B ] = { .negate = OP_SET_AE, },
>+      [OP_SET_BE] = { .negate = OP_SET_A , },
>+      [OP_SET_AE] = { .negate = OP_SET_B , },
>+      [OP_SET_A ] = { .negate = OP_SET_BE, },
>+};

I think this patch ideally should be combined with the next patch.
As it is, this patch is not self contain. There is no user of this table.


>commit b38e2263075d1caa7694f47cc5f1cc8d78a2871d
>Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>Date:   Mon Mar 27 17:19:43 2017 +0200
>
>    use opcode table for compare_opcode()
>
>    At the same time, change also the name of the function.
>
...
> static int simplify_seteq_setne(struct instruction *insn, long long value)
> {
>       pseudo_t old = insn->src1;
>@@ -484,7 +460,7 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
>               // and similar for setne/eq ... 0/1
>               src1 = def->src1;
>               src2 = def->src2;
>-              insn->opcode = compare_opcode(opcode, inverse);
>+              insn->opcode = inverse ? opcode_table[opcode].negate : opcode;

I think it would be better to have some kind of assert check here, the opcode
you swap from the table is indeep opcode. Because you assign the opcode
array using sparse index. It is easy to miss a spot creating the empty slot in
the table.

Also, the opcode table might be able to compressed only contain
section of the BINCMP opcodes.

Chris

Re: [GIT PULL] llvm fixes

[Christopher Li]

>commit 5674da2d1af2467605fcc9b798fb54ee2d28efc7
>Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>Date:   Mon Mar 20 15:18:53 2017 +0100
>
>    canonicalize compare instructions
>
>    Currently only commutative instructions are canonicalized
>    (the "simpler" operands, often a constant, is forced, if present
>    to be in the second operand). This improve CSE (more cases are
>    considered as equivalent) and help to reduce the number of "pattern"
>    to be handled at simplification.
>
> const struct opcode_table opcode_table[OP_LAST] = {
>-      [OP_SET_EQ] = { .negate = OP_SET_NE, },
>-      [OP_SET_NE] = { .negate = OP_SET_EQ, },
>-      [OP_SET_LT] = { .negate = OP_SET_GE, },
>-      [OP_SET_LE] = { .negate = OP_SET_GT, },
>-      [OP_SET_GE] = { .negate = OP_SET_LT, },
>-      [OP_SET_GT] = { .negate = OP_SET_LE, },
>-      [OP_SET_B ] = { .negate = OP_SET_AE, },
>-      [OP_SET_BE] = { .negate = OP_SET_A , },
>-      [OP_SET_AE] = { .negate = OP_SET_B , },
>-      [OP_SET_A ] = { .negate = OP_SET_BE, },
>+      [OP_SET_EQ] = { .negate = OP_SET_NE, .swap = OP_SET_EQ, },
>+      [OP_SET_NE] = { .negate = OP_SET_EQ, .swap = OP_SET_NE, },
>+      [OP_SET_LT] = { .negate = OP_SET_GE, .swap = OP_SET_GT, },
>+      [OP_SET_LE] = { .negate = OP_SET_GT, .swap = OP_SET_GE, },
>+      [OP_SET_GE] = { .negate = OP_SET_LT, .swap = OP_SET_LE, },
>+      [OP_SET_GT] = { .negate = OP_SET_LE, .swap = OP_SET_LT, },
>+      [OP_SET_B ] = { .negate = OP_SET_AE, .swap = OP_SET_A , },
>+      [OP_SET_BE] = { .negate = OP_SET_A , .swap = OP_SET_AE, },
>+      [OP_SET_AE] = { .negate = OP_SET_B , .swap = OP_SET_BE, },
>+      [OP_SET_A ] = { .negate = OP_SET_BE, .swap = OP_SET_B , },


Notice that LT and GT and equivalent instructions after swapping the src.
Another way to do it we might just remove one kind of instruction from the
sparse IR. From the linearization point just map GT into LT and swap the source.

So the IR does not allow those duplicated equilateral instructions. There is
less canonization to be done.

Chris

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Sun, Nov 05, 2017 at 04:49:37PM +0800, Christopher Li wrote:
> >commit 5674da2d1af2467605fcc9b798fb54ee2d28efc7
> >Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> >Date:   Mon Mar 20 15:18:53 2017 +0100
> >
> >    canonicalize compare instructions
> >
> >    Currently only commutative instructions are canonicalized
> >    (the "simpler" operands, often a constant, is forced, if present
> >    to be in the second operand). This improve CSE (more cases are
> >    considered as equivalent) and help to reduce the number of "pattern"
> >    to be handled at simplification.
> >
> 
> 
> Notice that LT and GT and equivalent instructions after swapping the src.
> Another way to do it we might just remove one kind of instruction from the
> sparse IR. From the linearization point just map GT into LT and swap the source.
> 
> So the IR does not allow those duplicated equilateral instructions. There is
> less canonization to be done.

The principal and most important action done during canonicalization is
insuring that constants are on the RHS.

-- Luc

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Sun, Nov 05, 2017 at 04:29:57PM +0800, Christopher Li wrote:
> >commit e4a0824120939235e40277a57425a72fbfcd5b9b
> >Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> >Date:   Sun Mar 26 19:35:14 2017 +0200
> >
> 
> I think this patch ideally should be combined with the next patch.
> As it is, this patch is not self contain. There is no user of this table.

I'm fine with this. Certainly when:
*) the user is introduced in the next patch  
*) there is 'static but unused' warnings issued

> ...
> > static int simplify_seteq_setne(struct instruction *insn, long long value)
> > {
> >       pseudo_t old = insn->src1;
> >@@ -484,7 +460,7 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
> >               // and similar for setne/eq ... 0/1
> >               src1 = def->src1;
> >               src2 = def->src2;
> >-              insn->opcode = compare_opcode(opcode, inverse);
> >+              insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
> 
> I think it would be better to have some kind of assert check here, the opcode
> you swap from the table is indeep opcode. Because you assign the opcode
> array using sparse index. It is easy to miss a spot creating the empty slot in
> the table.

Sorry, I see the words, I sorta gues what you mean but I can't parse
what you wrote.

> Also, the opcode table might be able to compressed only contain
> section of the BINCMP opcodes.

Yes, it's something that may be done after all the related changes
are done if the speedup is worth the added complexity.

-- Luc

Re: [GIT PULL] llvm fixes

[Christopher Li]

On Mon, Nov 6, 2017 at 1:10 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> >-              insn->opcode = compare_opcode(opcode, inverse);
>> >+              insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
>>
>> I think it would be better to have some kind of assert check here, the opcode
>> you swap from the table is indeep opcode. Because you assign the opcode
>> array using sparse index. It is easy to miss a spot creating the empty slot in
>> the table.
>
> Sorry, I see the words, I sorta gues what you mean but I can't parse
> what you wrote.

Let me re phrase. The opcode_table has a lot of zero in them.
Even though you thing you give all the op code worthwhile to have .negate
an opcode. The rest of op has .negate to zero.

My suggestion is that make a assert check this new opcode you get back
from the table is not zero.

You initialize the op code table using position index. It is possible to missing
a slot. So have an assert check here is good.

>
>> Also, the opcode table might be able to compressed only contain
>> section of the BINCMP opcodes.
>
> Yes, it's something that may be done after all the related changes
> are done if the speedup is worth the added complexity.

This series will first go into a topic branch any way.
Clearly your opcode is only apply to OP_SETXXXX friends.
I more compact data section is good.


Chris

Re: [GIT PULL] llvm fixes

[Christopher Li]

OK, this is the most difficult review for me to write, the OP_PUSH patch:
I have think this long and hard.

>commit 92fed40628f932a20a6cc95a67e4e5b03d280757
>Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>Date:   Fri Mar 17 11:49:42 2017 +0100
>
>    give function's arguments a type via OP_PUSH
>
>    The linearized code, sparse's IR, have no use of C's complex type
>    system. Those types are checked in previous phases and the pseudos
>    doesn't a type directly attached to them as all needed type info
>    are now conveyed by the instructions (like (register) size,
>    signedness (OP_DIVU vs OP_DIVS), ...).
>
>    In particular, PSEUDO_VAL (used for integer and address constants)
>    are completely typeless.

I think the PSEUDO_VAL being typeless is the problem here.

>    There is a problem with this when calling a variadic function
>    with a constant argument as in this case there is no type in the
>    function prototype (for the variadic part, of course) and there is
>    no defining instructions holding the type of the argument.

No only here as problem. As you hint in your change

======================quote ===========================
>commit e154d59f375bdb307c4d778bab8055a380e2840e
>Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>Date:   Wed Mar 8 08:19:50 2017 +0100
>
>    llvm: fix translation of PSEUDO_VALs into a ValueRefs
>
>    In sparse-llvm there is the assumption that a PSEUDO_VAL is always
>    of integer type. But this is not always the case: constant pointers,
>    like NULL, are also of the PSEUDO_VAL kind.
>
>    Fix this by adding a helper 'val_to_value()' and using the
>    instruction's type where this pseudo is used as the type of the value.
>
>    Note: while this patch improve the situation, like for example for the
>    test cases added here, it's still not correct because now we're making
>    the assumption that 'insn->type' is the type we need for the pseudo.
>    This is often true, but certainly not always.
>    For example this is not true for:
>    - OP_STORE/OP_LOAD's insn->src
>    - OP_SET{EQ,...}'s   insn->src[12]
>    - probably some  others ones
>    - in general, obviously, for any instructions where the target has
>      a different type than the operands.
========================quote ==========================

There is other place  want to have PSEUDO_VAL size which is not provide by
instruction type.

>
>    Fix this by adding a new instruction, OP_PUSH, which will be used
>    to pass arguments to function calls and whose purpose is to give
>    a correct type/size to function's arguments.

This OP_PUSH is fixing a uncommon case (function call variance part
has constant).

I did purpose a different way to fix this problem, actually also
suggested by Linus, you are CC on the email, back in Aug 13.

https://patchwork.kernel.org/patch/9897573/
https://git.kernel.org/pub/scm/devel/sparse/chrisl/sparse.git/log/?h=pseudo-sized-value

Compare OP_PUSH vs PSEUDO_VAL with size.

OP_PUSH:
- break sparse IR compatibility.
- Allocate more memory (mostly duplicate information)
- create special instruction that is not part of bb->insns. Push
instruction in insn.arguments.
- PSEUDO_VAL size still have other case not covered by instruction type.
- more verbose output on linearize instructions.

PSEUDO_VAL with size:
- compatible to previous IR if you don't care about the size.
- no extra memory allocation for storing the size part.
  (there will be extra memory allocation for same value with different size).
- fix other place PSEUDO_VAL size is needed but not provide by instruction type.
- less impact to the code all around.

So far I see PSEUDO_VAL with size has advantage over
OP_PUSH. If I am wrong, please correct me, I am listening.

I think that is the biggest worry I have on this series. The rest
of my feed back is kind of trivial I don't mind merge then fix it.


Chris

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Sun, Nov 12, 2017 at 2:04 AM, Christopher Li <sparse@chrisli.org> wrote:
> OK, this is the most difficult review for me to write, the OP_PUSH patch:
> I have think this long and hard.
>
>>commit 92fed40628f932a20a6cc95a67e4e5b03d280757
>>Author: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>>Date:   Fri Mar 17 11:49:42 2017 +0100
>>
>>    give function's arguments a type via OP_PUSH
>>
>>    The linearized code, sparse's IR, have no use of C's complex type
>>    system. Those types are checked in previous phases and the pseudos
>>    doesn't a type directly attached to them as all needed type info
>>    are now conveyed by the instructions (like (register) size,
>>    signedness (OP_DIVU vs OP_DIVS), ...).
>>
>>    In particular, PSEUDO_VAL (used for integer and address constants)
>>    are completely typeless.
>
> I think the PSEUDO_VAL being typeless is the problem here.

And it has already been explained to you why they are typeless
and why it's fine.

>
> OP_PUSH:
> - break sparse IR compatibility.

What compatibility are you talking about?

>
> So far I see PSEUDO_VAL with size has advantage over
> OP_PUSH. If I am wrong, please correct me, I am listening.

The OP_PUSH solution has at least the advantage to work, to
be integrated with all the other IR generation fixes and to be tested.

-- Luc

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Sun, Nov 12, 2017 at 09:04:43AM +0800, Christopher Li wrote:
> - create special instruction that is not part of bb->insns. Push
> instruction in insn.arguments.

You already came with this previously and I already replied you about it.
I don't know what make you think that OP_PUSH are not in bb->insns
but you're wrong: they are normal instructions and are thus stored
in the bb->insns, the second patch even change their position inside
this list.


-- Luc

Re: [GIT PULL] llvm fixes

[Christopher Li]

On Sun, Nov 12, 2017 at 1:05 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> I think the PSEUDO_VAL being typeless is the problem here.
>
> And it has already been explained to you why they are typeless

And I already explain why your explain is wrong. You are using an
argument Linus used in the earlier email to re-battle the suggestion
make by Linus in the later email. You did not follow up on that email.
The ball is it your court. Do you want me to dig out the email archive?

> and why it's fine.

That is a design choice we can change. You haven't address that
if we choose other, what evil things can happen. Exactly, please
point to the PSEUDO_VAL with size patch and tell me what is evil
about that patch.

BTW, having the size is not the same as have the full type.

>> OP_PUSH:
>> - break sparse IR compatibility.
>
> What compatibility are you talking about?

Every one that write an application depend on the sparse
bytecode will need to update their source code how to handle the
OP_PUSH. You are forcing source code changes on other
projects.

>>
>> So far I see PSEUDO_VAL with size has advantage over
>> OP_PUSH. If I am wrong, please correct me, I am listening.
>
> The OP_PUSH solution has at least the advantage to work, to
> be integrated with all the other IR generation fixes and to be tested.

But the PSEUDO_VAL.size has the technical merit, it is a better
solution in long run. Of course we still need to be tested when it is
merged. That is given. It is not a reason to pick OP_PUSH over PSEUDO_VALE.size.

> You already came with this previously and I already replied you about it.
> I don't know what make you think that OP_PUSH are not in bb->insns
> but you're wrong: they are normal instructions and are thus stored
> in the bb->insns, the second patch even change their position inside
> this list.

Ok, fine. I retract the statement that OP_PUSH not in bb->insns.
But all other points still apply. With this new information.
PSEUDO_VALE.size still have technical merit over OP_PUSH.

Chris

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

FWIW, I've now pushed this to my dev tree at:
	git://github.com/lucvoo/sparse.git master

with the two patches related to OP_PUSH removed and
replaced by something with minimal impact and directly
storing the type of the arguments into the OP_CALL
instructions.

-- Luc Van Oostenryck 

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Fri, Nov 17, 2017 at 06:24:09PM +0800, Christopher Li wrote:
> On Fri, Nov 17, 2017 at 5:51 PM, Luc Van Oostenryck wrote:
> > FWIW, I've now pushed this to my dev tree at:
> >         git://github.com/lucvoo/sparse.git master
> >
> > with the two patches related to OP_PUSH removed and
> > replaced by something with minimal impact and directly
> > storing the type of the arguments into the OP_CALL
> > instructions.
> 
> Isn't type of arguments can be get from the call function prototype?
> 
> So those kind of the information is duplicated most of the time.
> The only useful place is variable arguments that the argument is
> from the variable part and the argument is constant value.

Yes, this has been pretty clear since the beginning:
- Currently, nowhere in the "normal" sparse code is the type or
  the size of a constant something we care about.
- The only place it is needed is:
  - for sparse-llvm and then only for variadic arguments
    (where there is nothing in the prototype about these type).
- Other backends will, obviously, need the same information.

Also, but maybe less obvious:
- Till now, no pseudo has any kind of typing *directly* attached
  to it. In fact, the pseudos are typeless (all of them) and the
  code is designed around this. The types are given by the usage
  or other secondary information.
- Here under, by 'type', you often need to understand
  'some type system', either:
  - the full typing represented by 'struct symbol' 
  - a subset of the this full type, like 'size + integer/float'
  
> I did try to remove the OP_PUSH and the associate type from
> your git series. Removing the OP_PUSH is not too bad. But undoing
> the associate type is a major hassle.
> 
> Do you see any problem using the pseudo value with size patch?
> Now it has the second patch to work with llvm as well. Should be testable.

I already said in June-August that I tried this approach and that
it didn't work (well, I'm sure that it is possible to make it work,
it's just more complex that it seems).

I'm sure it's testable (but what does that mean exactly?).
I'm convinced it passes the testsuite and kernel check.
But given that, as stated here above, nowhere in the code
this information is needed, it's pretty normal that the
changes have zero effect there. OTOH, these changes have
impact on a few things related to the level below, thus
*it is needed* to test things at IR level.

Now, I have no hard problem with the PSEUDO_VAL.size
approach from a theorical point of view (even if I would
prefer the mathematical PoV that 0 is 0, 1 is 1, etc.).
I even think that *eventually* it may very well be
the right solution (probably the whole typing at IR
level need to be revisited).

On a practical level, things are differents:
- The introduction of PSEUDO_VAL.size create
  a segragation between pseudos of the same value
  but different uses (different sizes).
  This has impact on the CSE.
  Admittingly, there shouldn't be any impact and it's
  maybe a sign that something is wrong elsewhere.
- There are places in the code where kinds of implicit
  castings are done (the OP_SET_* instructions are
  especially concerned). Some may consider this as a
  bug, to me it's at least a problem.
  To solve the problems there you need to:
  1) identify all places where such is done
  2) look if the pseudo is a constant
  3) if it is a constant, look at its type/size
  4) make the needed adjustment.
- On another level, even if your patch is quite small
  and simple, it's still relatively invasive and is
  guaranted to create bad conflicts in numerous pending patches.

Now, aren't these not solvable?
I'm sure they are solvable. The problems are the price/work
and the moment. Of course, the price and moment mostly
concerns the person who will make the work.

For my part, I consider that there are others things
immensely more important than trying to solve this now,
like, for example, fixing the SSA conversion.

-- Luc Van Oostenryck

Re: [GIT PULL] llvm fixes

[Christopher Li]

On Sat, Nov 18, 2017 at 3:50 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> Do you see any problem using the pseudo value with size patch?
>> Now it has the second patch to work with llvm as well. Should be testable.
>
> I already said in June-August that I tried this approach and that
> it didn't work (well, I'm sure that it is possible to make it work,
> it's just more complex that it seems).
>
> I'm sure it's testable (but what does that mean exactly?).
> I'm convinced it passes the testsuite and kernel check.
> But given that, as stated here above, nowhere in the code
> this information is needed, it's pretty normal that the
> changes have zero effect there. OTOH, these changes have
> impact on a few things related to the level below, thus
> *it is needed* to test things at IR level.
>
> Now, I have no hard problem with the PSEUDO_VAL.size
> approach from a theorical point of view (even if I would
> prefer the mathematical PoV that 0 is 0, 1 is 1, etc.).
> I even think that *eventually* it may very well be
> the right solution (probably the whole typing at IR
> level need to be revisited).

I think constant pseudo have a size is the right
solution in the long run. I

> On a practical level, things are differents:
> - The introduction of PSEUDO_VAL.size create
>   a segragation between pseudos of the same value
>   but different uses (different sizes).
>   This has impact on the CSE.
>   Admittingly, there shouldn't be any impact and it's
>   maybe a sign that something is wrong elsewhere.

As you said, it should be some thing CSE done wrong
to cause it a problem. The pseudo register has a size
being implicit on that. If CSE merge two instruction with
different source pseudo size into one, that seems wrong.

If you know a special test case can trigger that, I would
like to see it as well.

> - There are places in the code where kinds of implicit
>   castings are done (the OP_SET_* instructions are
>   especially concerned). Some may consider this as a
>   bug, to me it's at least a problem.
>   To solve the problems there you need to:
>   1) identify all places where such is done
>   2) look if the pseudo is a constant
>   3) if it is a constant, look at its type/size
>   4) make the needed adjustment.

If there is a size change during the implicit cast,
it can be a good thing to make the truncate and
size extend more obvious. I think you have some idea
relate to that.

Chris

Re: [GIT PULL] llvm fixes

[Luc Van Oostenryck]

On Mon, Nov 27, 2017 at 01:42:55AM +0800, Christopher Li wrote:
> 
> If there is a size change during the implicit cast,
> it can be a good thing to make the truncate and
> size extend more obvious. I think you have some idea
> relate to that.

Yes, I have essentially finished the cast rework. However,
my tests now reveals some forgotten cases and some bugs.
It's a good thing but they must be fixed.

It also won't solve problems with pseudos silently changing
from type/size (which is more a question of IR simplification).

-- Luc