Dear LLVM Community, I am one of the summer of coders working on LLVM this year. My project is to implement the ABCD algorithm for array bounds checking, and also a bitwidth analysis that maps variables to an approximation of its size in bits. To implement this, I will have to simulate a intermediate representation called SSI (Static Single Information) form on top of LLVM SSA representation. The SSI form has the property that each use of a variable post-dominates its definition. Also, if there are two uses of the same variable, say, u(v1) and u(v2), then, either u(v1) dominates u(v2) or vice-versa. I would like to discuss my approach with you guys, so that you can redirect me if I am going through a bad path, so I am listing some points below: 1) I want to implement a very modular design. In this way, I will have an analysis that receives the intervals produced by LiveIntervalAnalysis, plus a list of variables, and creates a new set of intervals, so that each interval designates a new virtual variable, that is visible only inside my analysis. These variables have the SSI property. In this way, it is possible to map constraints such as (a > 10) to an interval. 2) Each client gives to my analysis the variables that it wants mapped to SSI. For instance, the ABCD client passes all the variables that are used as indexes of arrays, or as array sizes. A pass to eliminate dead code passes all the variables used inside conditionals, and the pass that does bitwidth analysis passes all the variables of type int, for instance. 3) This implies that each client will have to traverse the program representation harvesting the variables of interest. My analysis will take care of simulating the SSI representation for those variables. 4) Queries can be made given an instruction index, as computed by LiveIntervalAnalysis. For instance, a typical query would be: is a > x at program point 110. 5) Keeping the intervals ordered, we can answer queries in O(ln N), where N is the maximal program index. I would like to have critics on this approach so it can be well thought before implementation to reduce reimplementation. In particular, to use this technique, my analysis must work at the MachineFunction level, as it must run after LiveIntervalAnalysis. Do I miss essential information at this level, compared to the Function level? I mean, is it possible to analysis conditionals to discover things like a > 10, or a == 10, etc? Please, feel free to ask me any clarification you may think about. I would really appreciate any comments and thoughts you guys may have. Thanks, -- Andre Tavares Master Student in Computer Science - UFMG - Brasil http://dcc.ufmg.br/~andrelct
On Fri, May 15, 2009 at 10:27 AM, Andre Tavares <andrelct at dcc.ufmg.br> wrote:> 1) I want to implement a very modular design. In this way, I will have > an analysis that receives the intervals produced by > LiveIntervalAnalysis, plus a list of variables, and creates a new set of > intervals, so that each interval designates a new virtual variable, that > is visible only inside my analysis. These variables have the SSI > property. In this way, it is possible to map constraints such as (a > > 10) to an interval.I would suggest writing the SSI pass to do some active transformations rather than providing virtual variables. You can use dummy PHI nodes to rename a variable. That seems a lot more straightforward than trying to provide virtual names for a value at multiple places in the program: this way, a variable always represents itself without any special lookups. In any case, I don't think you need liveness information to compute SSI form, so I don't see the need for LiveIntervalAnalysis.> I would like to have critics on this approach so it can be well thought > before implementation to reduce reimplementation. In particular, to use > this technique, my analysis must work at the MachineFunction level, as > it must run after LiveIntervalAnalysis. Do I miss essential information > at this level, compared to the Function level? I mean, is it possible to > analysis conditionals to discover things like a > 10, or a == 10, etc?Working at the MachineFunction level is really late; this sort of analysis should be working at the IR level. If you really need liveness information, I'd suggest writing a new IR-level pass for it; computing liveness on SSA form isn't very difficult. -Eli
Hi Andre, LLVM has a target independent intermediate representation (IR) which is what the optimizations run by "opt" work on. This IR can be fed into the interpreter, the JIT, the code generators, static analysers etc. The code generators generate code for particular target processors; this is what llc does. You want to work at the IR level, not the codegen level, so none of the LLVM code under lib/CodeGen/ is relevant to you. In particular LiveIntervalAnalysis is part of codegen, so you should ignore it. Look instead inside lib/Analysis and lib/Transforms. Ciao, Duncan.> I am one of the summer of coders working on LLVM this year. My > project is to implement the ABCD algorithm for array bounds checking, > and also a bitwidth analysis that maps variables to an approximation of > its size in bits. To implement this, I will have to simulate a > intermediate representation called SSI (Static Single Information) form > on top of LLVM SSA representation. The SSI form has the property that > each use of a variable post-dominates its definition. Also, if there are > two uses of the same variable, say, u(v1) and u(v2), then, either u(v1) > dominates u(v2) or vice-versa. > > I would like to discuss my approach with you guys, so that you can > redirect me if I am going through a bad path, so I am listing some > points below: > > 1) I want to implement a very modular design. In this way, I will have > an analysis that receives the intervals produced by > LiveIntervalAnalysis, plus a list of variables, and creates a new set of > intervals, so that each interval designates a new virtual variable, that > is visible only inside my analysis. These variables have the SSI > property. In this way, it is possible to map constraints such as (a > > 10) to an interval. > > 2) Each client gives to my analysis the variables that it wants mapped > to SSI. For instance, the ABCD client passes all the variables that are > used as indexes of arrays, or as array sizes. A pass to eliminate dead > code passes all the variables used inside conditionals, and the pass > that does bitwidth analysis passes all the variables of type int, for > instance. > > 3) This implies that each client will have to traverse the program > representation harvesting the variables of interest. My analysis will > take care of simulating the SSI representation for those variables. > > 4) Queries can be made given an instruction index, as computed by > LiveIntervalAnalysis. For instance, a typical query would be: is a > x > at program point 110. > > 5) Keeping the intervals ordered, we can answer queries in O(ln N), > where N is the maximal program index. > > I would like to have critics on this approach so it can be well thought > before implementation to reduce reimplementation. In particular, to use > this technique, my analysis must work at the MachineFunction level, as > it must run after LiveIntervalAnalysis. Do I miss essential information > at this level, compared to the Function level? I mean, is it possible to > analysis conditionals to discover things like a > 10, or a == 10, etc? > > Please, feel free to ask me any clarification you may think about. I > would really appreciate any comments and thoughts you guys may have. > > Thanks, >
Andre Tavares wrote:> Dear LLVM Community, > > I am one of the summer of coders working on LLVM this year. My > project is to implement the ABCD algorithm for array bounds checking, > and also a bitwidth analysis that maps variables to an approximation of > its size in bits. To implement this, I will have to simulate a > intermediate representation called SSI (Static Single Information) form > on top of LLVM SSA representation. The SSI form has the property that > each use of a variable post-dominates its definition. Also, if there are > two uses of the same variable, say, u(v1) and u(v2), then, either u(v1) > dominates u(v2) or vice-versa. > > I would like to discuss my approach with you guys, so that you can > redirect me if I am going through a bad path, so I am listing some > points below: > > 1) I want to implement a very modular design. In this way, I will have > an analysis that receives the intervals produced by > LiveIntervalAnalysis, plus a list of variables, and creates a new set of > intervals, so that each interval designates a new virtual variable, that > is visible only inside my analysis. These variables have the SSI > property. In this way, it is possible to map constraints such as (a > > 10) to an interval. > > 2) Each client gives to my analysis the variables that it wants mapped > to SSI. For instance, the ABCD client passes all the variables that are > used as indexes of arrays, or as array sizes. A pass to eliminate dead > code passes all the variables used inside conditionals, and the pass > that does bitwidth analysis passes all the variables of type int, for > instance. > > 3) This implies that each client will have to traverse the program > representation harvesting the variables of interest. My analysis will > take care of simulating the SSI representation for those variables.LLVM's pass system does a good job of forcing you into having a modular design. The two relevant choices are these: * make it an analysis pass. The pass works by studying the IR and building up an in-memory model of the information it wants to represent. Passes that want to access this information have to declare that they need it to the PassManager and then ask for the FooAnalysisPass* when running and query it through its public interface. If another pass wants use this info and also change the IR, it needs to either invalidate the analysis or update it through the public interface. For an example of this, see LoopInfo. * make it a transformation pass. The pass works by modifying the IR such that it maintains a certain property (for example, "there is exactly one exit block"). Passes which require the property declare it to the PassManager then they either declare that they will also preserve the property or it is assumed that they don't. A good example of this is LCSSA. In either case a series of passes will be constructed such that the required analysis/properties are available when needed and not needlessly recomputed in between. I happen to agree with Eli that it would be better to do the "SSI as unary PHI nodes" trick (which LCSSA already does, by the way) than to make the users of this data request it for each interesting variable, but I don't have any solid experience here so I can be persuaded either way.> 4) Queries can be made given an instruction index, as computed by > LiveIntervalAnalysis. For instance, a typical query would be: is a > x > at program point 110.That's a query you'd ask of ABCD not an SSI analysis.> 5) Keeping the intervals ordered, we can answer queries in O(ln N), > where N is the maximal program index.How are they numbered anyway?> I would like to have critics on this approach so it can be well thought > before implementation to reduce reimplementation. In particular, to use > this technique, my analysis must work at the MachineFunction level, as > it must run after LiveIntervalAnalysis. Do I miss essential information > at this level, compared to the Function level? I mean, is it possible to > analysis conditionals to discover things like a > 10, or a == 10, etc?I don't know if there's anything stopping you from porting LiveIntervalAnalysis from working on both Function and MachineFunction like loop strength reduction does. It'd probably be hard. Nick> Please, feel free to ask me any clarification you may think about. I > would really appreciate any comments and thoughts you guys may have.