[LLVMdev] Advice on CFG pre-analysis

[Gordon Henriksen]

On May 24, 2008, at 02:53, Talin wrote:

> In the language I am working on, there are cases where the call flow  
> graph can affect the type of a variable. 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. 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.
>
> 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.
>
> 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.


I have to agree with earlier poster, I'm not sure altering the type of  
values is tractable; this seems better as a diagnostic analysis.

A way to leverage the type system here might be with 'match' statement  
like ml's. Consider:

type maybe 'a = None | Some 'a

let maybe_add x y =
   match x, y with
   | Some x, Some y -> x + y
   | Some n, None | None, Some n -> n
   | None, None -> None

Here, the expressions like 'Some x' and 'None' are patterns, which  
match different variants of the 'maybe int' type. 'Some x' and 'Some  
y' additionally bind matched subexpressions to names. For the first  
pattern, I chose to shadow the nullable parameters with the non- 
nullable matched subexpressions.

More to your point, however, the analysis you're proposing seems  
strongly something that should be done in your language's IR prior to  
LLVM lowering. Several of LLVM's graph algorithms are templates, so  
you could possibly specialize a traits type for your compiler's parse  
tree/AST/IR and potentially leverage some of LLVM's code.

— Gordon