[LLVMdev] Advice on CFG pre-analysis

[Talin]

Thanks (everyone) for the suggestions, they were helpful.

What I decided to do was to essentially "wrap" LLVM's BasicBlock 
structure with my own block class that contains additional high-level 
information. Up to this point I was generating LLVM basic blocks on the 
fly as I walked the statement tree; Now I build my own BB graph, and 
then use that to generate the BB graph for LLVM.

This allows me to do a couple of things. For one thing, its a lot easier 
to traverse the BB graph than the statement tree, and its more amenable 
to manipulation (especially when taking break/continue and other jumps 
into account.) For one thing, implementing Python-style "yield" 
statement (which is a transformation of the graph) will be easier with 
this data structure.

In the case of the nullable types, I don't need to store full use/def 
chains, since all I want to know is "given variable X, is there any 
chance that X could be null at this point?" If there are multiple 
definitions of X reaching a particular use of X, then the value could be 
null if any of the reaching definitions could be null. (In the face of 
incomplete knowledge, assume the worst.) So in other words, the 
"nullable" bits are merely or'd together. I don't need to deep dive into 
subroutines or expressions since "nullable" is propagated upward by the 
type system and frozen at call boundaries. Yes, there will be some false 
positives, but a few extra tests for pointer validity isn't going to 
hurt all that much.

So essentially I just have to store at the beginning of each BB the set 
of variables which could be null, and do the typical intra-block analysis.

The overall motivation for this, BTW, is my attempt to prove a personal 
theory, which is that most static type systems are guarding against the 
wrong things. Type mismatch errors don't keep programmers up at night; 
null pointers, deadlocks and race conditions do. So my language tries to 
check for null pointer errors at compile time using static types.

-- Talin

Chris Lattner wrote:
> On May 23, 2008, at 11:53 PM, Talin wrote:
>   
>> In the language I am working on, there are cases where the call flow
>> graph can affect the type of a variable.
>>     
>
> Ok.
>
>   
>> A simple example is a
>> "nullable" type (a pointer which is allowed to be NULL), which can be
>> converted into a non-nullable type via an if-test. So for example if x
>> is nullable, and I test x != NULL, then inside the conditional block  
>> the
>> type of x is no longer nullable.
>>     
>
> Makes sense.
>
>   
>> Nullable types behave slightly
>> differently (and produce less efficient code) than non-nullable types.
>> For example, a downcast to a nullable type is a dynamic cast  
>> (because if
>> the cast fails, the result can be NULL), whereas a downcast to a
>> non-nullable type throws an exception if the cast fails.
>>     
>
> Sure.
>
>   
>> This kind of analysis is trivial given LLVM's architecture. The  
>> problem
>> I have, however, is that all of the high-level type analysis occurs
>> before LLVM ever gets into the picture. LLVM doesn't know anything  
>> about
>> the front-end type system.
>>     
>
> Why not codegen this logically as a pair of <bool, T> where each is an  
> LLVM Value*?  This would allow the optimizer to propagate around and  
> eliminate the bool.
>
>   
>> What I am wondering is, will I have to re-invent the same sort of CFG
>> analysis that LLVM does in my frontend, or is there some shortcut? I
>> guess this is really a general compiler-design question rather than  
>> one
>> specific to LLVM, but I thought I would ask anyway.
>>     
>
> This issue is fairly straight-forward I think.  More general problems  
> are things like auto-unboxing of types and doing type inference of  
> source level languages.  This can also be done pretty easily in the  
> LLVM IR, if you have questions about that I can explain.
>
> -Chris
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>