[llvmlinux] Heavy experiments

Renato Golin renato.golin at linaro.org
Wed Jul 24 20:56:18 UTC 2013


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...


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.


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).


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.


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,

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.


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.


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


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


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.


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.


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/llvmlinux/attachments/20130724/b5daaea1/attachment-0001.html>


More information about the LLVMLinux mailing list