[llvmlinux] Heavy experiments

Marcelo Sousa marceloabsousa at gmail.com
Wed Jul 24 23:42:21 UTC 2013


Hi again,


On Wed, Jul 24, 2013 at 1:56 PM, Renato Golin <renato.golin at linaro.org>wrote:

> On 24 July 2013 20:43, Marcelo Sousa <marceloabsousa at gmail.com> wrote:
>
>> Things matching by accident on some cases is for me a buggy
>> implementation of LLVM itself.
>>
>
> Some would call it pragmatic...
>

I think we have different perspectives here.

>
>
> Sure it is surjective but that's not a bad thing. It only means that
>> multiple C programs evaluate to the same assembly instructions and there is
>> nothing wrong with that if the compilation is sound.
>>
>
> Yes, but that also means there is less information on the IR than there is
> in the source. This is not just a surjection due "a+b = b+a", but due to
> different C++ classes being lowered as the same IR object (either structs
> or arrays), and you lose a lot of type information in IR, this is why TBAA
> needs a lot of metadata to work well.
>

All I'm saying is that you don't need to lower different C++ classes as the
same IR object.


>
>
>  Do we agree that you can lift the sign information on instructions to
>>> types?
>>>
>>
> Nope. This has been refuted as many times as has been proposed (quite a
> lot). Keeping track of signedness of variables is non-trivial and would
> make optimization passes much more complicated than they already are
> (search the list, too many examples).
>

I will try to investigate this issue further but I don't see why keeping
track of signedness of variables is non-trivial and exactly how it affects
the complexity of optimizations.

>
>
>  Can you give me an example of when multiple ABIs actually influence the
>>> design decision that sign information goes into instructions?
>>>
>>
> On ARM ABI, char is by default unsigned, on Intel it's signed, so "char a"
> actually means different things on different machines.
>

This is interesting. You need a parametrized IR by the ABI to handle this.


>
>  In the case where a function operates in one type and another function
>>> operates on the other, it'll be hard to reason about which group each
>>> function belongs. Again, more of a problem to C++ and higher languages.
>>>
>>
>> Again hard is different than undecidable. You need to provide me with a
>> convincing example of this situation.
>>
>
> Back of the envelope example, might have errors, please search on the list
> for real world examples:
>
> In C++:
> class a { int x; funcA(class a); }
> class b { int y; funcB(class b); }
>
> Becomes in C:
> struct a { int x; }
> struct b { int y; }
> void funcA(struct a) { ... }
> void funcB(struct b) { ... }
>
> In IR, this becomes:
> %struct_A { i32 };
> void funcA(%struct_A)
> void funcB(%struct_A)
>
> Can you revert this into its C++ original? It's not hard, it's impossible,
>

No, but I can revert the following:

%structA { i32 };
%structB { i32 };
void funcA(%struct_A)
void funcB(%struct_B)

In fact, I say that the transformation that generated the IR that you
produced is unsound. I may want to do dynamic software update on class a
and add another int z. In your case, you can't; in my case, I can't.


>
> You can still do some analysis (functional, execution), but you can't
> revert back to the original. Information was lost. Can you tell that
> funcA's and funcB's objects will never alias without further information?
> No, you can't, and this is why TBAA uses metadata.
>
>
>   For me, this is obviously a weakness of the language. I'm quite sure
>>> that you can achieve the same optimization levels without intrinsics and I
>>> don't understand (and not sure if LLVM developers describe) the semantic
>>> different between a LLVM IR instruction and an intrinsic (other than one is
>>> native and the other is a *special* call).
>>>
>>
> I'm not sure I follow you. Instructions can be combined or split apart,
> intrinsics cannot. On the other hand, not all operations can be explained
> in terms of IR and it would make the LangRef 10x as big if we decided to
> make all intrinsics of all targets as native. See the NEON implementation
> for more info.
>

The LangRef is already getting 10x with all the intrinsics. Following your
rationale, can you explain the motivation for cmpxchg to be an instruction
and bwap to be an intrinsic?

>
>
>  Sure it is misconception, but I want to change LLVM IR to be a proper
>>> virtual machine.
>>>
>>
> Do you mean like Java Virtual Machine? LLVM deviated from that path almost
> a decade ago and I don't think you can make it work again. Look at how
> complicated is PNaCl (which tried to do the same) and how much they failed.
> You are seriously underestimating the problem.
>

Something like that. Can you give me a reference for PNaCl?


>
>
>  BTW: speaking of things in the thesis that I don't see anymore: What
>>> happened to the whole *run-time optimization* for LLVM?
>>>
>>
> If you talking about JIT, it's getting less and less attention. See the
> latest post on the blog for a good description on the new MCJIT and why
> we're departing from that idea:
>
> http://blog.llvm.org/2013/07/using-mcjit-with-kaleidoscope-tutorial.html
>

Not just JIT but this (taken from Lattner's MSc thesis):
"Some transformations are too expensive to perform at run-time, even given
an e fficient representation to work with. For these transformations, the
run-time optimizer gathers pro file information, serializing it to disk.
When idle time is detected on the user's computer, an offl ine reoptimizer
is used to perform the most aggressive profi le-driven optimizations to the
application. "
Where the hell is this functionality?!


>
>
> Regardless, I'm slightly confused that you may be implying that
>> vectorization is unsound in LLVM.
>>
>
> Not sure I ever said that, at least I didn't mean to. All I said was that
> "vectorization bloats code".
>
>
> Well, here we can talk in two perspectives. It's obvious that loop unroll
>> can make our analysis incomplete, and that's *requirement* for example for
>> bounded model checking; but if you know the upper bound of the loop and you
>> unroll it completely, it's still possible to identify the loop right?
>>
>
> No when the unrolled loop gets inlined into another function, or get's
> cropped because of undefined behaviour, or get's pattern-matched into a
> simpler set of instructions that don't look like loops at all. The way LLVM
> recognize loops is to look for specific basic blocks (see LoopPass), and
> that would be gone. You can try to search harder, but you can also match
> false positives.
>
>
> The point is to identify which optimizations passes, and say "Look: if you
>> apply this optimization you're going into a dark path because the
>> optimization is not semantic preserving".
>>
>
> Compilers are not required to preserve semantics, only to produce the same
> results as the original code, when properly defined in the language
> specification. Undefined and implementation specific behaviour is where you
> can "kick the bucket". ;)
>
>
> Undefined behavior needs to be properly formalized in LLVM so that people
>> are clear on the semantics of the IR.
>>
>
> It is. http://llvm.org/docs/LangRef.html
>

That is hardly a formalization of its semantics. In the Vellvm paper
(POPL'12), they show some cases of uses of undefined that are very strange.
It seems that once you have *undef* you can do any optimization whatsoever.
I may be wrong but it feels to me that *undef* is trying to represent the
undefined in any programming language.


>
> Having a verification tool for LLVM sounds great to me!
>>
>
> To me too! By all means, I'm not saying you shouldn't, just that there are
> things you should use the AST, others the IR. Static analysis of the code,
> AST, analysis of correctness, IR.
>
>
> That's not really true in the sense that the *code* is actually going to
>> be execution in some *machine* so I am interested in verifying the
>> expansion for that particular architecture and not all the boilerplate code
>> for other architectures. I want to stress this point.
>>
>
> Different compiler options can create different *code* from the same
> source. The execution *will* be different.
>

That's true to a certain extent :)


>
>
> I'm still running experiments with different variations to for example
>> reduce the number of false positives, but you're right in claiming that for
>> example in the case of the Linux Kernel is hard to even identify from the
>> LLVM IR code the C code because you're getting generic kernel code and
>> architecture code mixed with driver code but that's quite important for a
>> precise analysis.
>>
>
> My hunch is that you'll need heuristics to control false positives without
> introducing false negatives, and that's not a precise analysis.
>

That's incorrect. You can reduce false positives while maintaining
soundness, which is exactly increasing precision.


>
>
> As I told you, I'm very interested in gathering ALL possible sources of
>> fear to verify IR code. Every analysis has limitations, but it's important
>> to be clear on the limitations. We can continue this discussion somewhere
>> else or even meet up, but I'm looking for LLVM IR experts that can raise
>> these issues.
>>
>
> I hope to have raised a few basic issues, but no one will list you all. If
> you ask it on the list you'll get replies like: "please be more specific".
>
> I recommend you to start your analysis, find lots of false positives, and
> enquire the list on each one separately. You'll get a much better feedback.
>
> Good luck on your project, and may the source be with you!
>
> --renato
>

> _______________________________________________
> LLVMLinux mailing list
> LLVMLinux at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/llvmlinux
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/llvmlinux/attachments/20130724/757b958d/attachment-0001.html>


More information about the LLVMLinux mailing list