similar to: [LLVMdev] Structural Analysis

Hi folks, A few months back I finished writing and testing a pass which implements "structural analysis" as described originally by Sharir in 1980 ("Structural analysis: A new approach to flow analysis in optimizing compilers") and more recently by Muchnick in Advanced Compiler Design and Implementation. It analyses the CFG and recognises specific region schema, such as

At first I'll try the simplest strategy: put the instruction in the machine BB corresponding to the LLVM BB where it comes from. To implement this, I plan to add an operand to non-passive node which points to the BasicBlockSDNode which the node belongs to. Another idea is to use a side map to map each node to its block. But I guess it's difficult to keep the map consistent when

Hi all, We did some benchmarks on code size with clang, gcc 4.5, and open64. Clang performed second in the test. The benchmark is CSiBE. Clang can't compile the linux kernel (some inline asm not supported) and replaypc (error: use of unknown builtin '__builtin_next_arg'). The concrete results are attached. -------------- next part -------------- An HTML attachment was scrubbed... URL:

I am trying to build a DAG for a whole function. The first problem I met is to assign a user for the last instruction of each basic block, be it BRCOND or other node. There is no natural user for such nodes. Without user, it will be removed in later phases. My idea is to use it as chain for nodes in the next basic block. Is this reasonable? -Zhongxing Xu -------------- next part -------------- An

Hi Zhongxing, On 4/8/07, Zhongxing Xu <xuzhongxing at gmail.com> wrote: > I think the real difficult thing in path sensitive program analysis (or > symbolic execution) is not the lack of decision procedures, but the > translation of arbitrary pointer operations and library function calls in > C/C++ program into the mathematics supported by the automated theorem > prover. >

On 4/9/07, Domagoj Babic <babic.domagoj at gmail.com> wrote: > > > Traditionally, such analyses have been considered too expensive to be > practical, and were mostly an academic curiosity. The core of the > problem is the lack of adequate automated decision procedures which > could quickly determine whether a set of constraints is satisfiable or > not, and if it is

On Dec 21, 2009, at 5:30 PM, Zhongxing Xu wrote: > 2009/12/21 Chris Lattner <clattner at apple.com>: >> Hi All, >> >> A few of us got together and started an official LLVM (and its sub- >> projects) blog: >> http://blog.llvm.org/ > > Is it online? I cannot open it. If it's online, I highly suspect it's > blocked by the GFW. Yep, it's

The first question is code placement. How is the compiler going to decide which block (or blocks) to emit an instruction in? The answer to that will help determine how control relationships should be represented. Dan On Jun 7, 2010, at 11:56 PM, Zhongxing Xu <xuzhongxing at gmail.com> wrote: > I am trying to build a DAG for a whole function. The first problem I > met is to

Hi, I wrote a Function pass that requires the IntervalPartition pass in order to obtain the set of intervals for every function: virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired<IntervalPartition>(); } and get a handle to it in the runOnFunction method of my CustomPass: bool CustomPass::runOnFunction(Function& F) { IntervalPartition& iPart =

2009/12/22 Chris Lattner <clattner at apple.com>: > > On Dec 21, 2009, at 5:30 PM, Zhongxing Xu wrote: > >> 2009/12/21 Chris Lattner <clattner at apple.com>: >>> >>> Hi All, >>> >>> A few of us got together and started an official LLVM (and its >>> sub-projects) blog: >>>  http://blog.llvm.org/ >> >> Is it

On 03/15/2010 05:51 PM, James Stanier wrote: > > Hi Tobias, Hi, > > Thanks for getting back to me. I have just had a peek at the documentation > for your region pass, and it looks really cool, and thanks also for the > pointers to the literature. > > If you want an overview of how structural analysis works, some of the pages > from Muchnick's textbook are available

Dear LLVMers, This email is intended for those interested in path-sensitive analysis, integer overflow analysis, static analysis, and (perhaps) loop invariant computation. Traditionally, such analyses have been considered too expensive to be practical, and were mostly an academic curiosity. The core of the problem is the lack of adequate automated decision procedures which could quickly

> > Spear takes a different approach - it is bit-precise, handles all > operators, but > currently doesn't handle arrays directly. However, the other mentioned > thm provers > handle arrays by encoding them as UIFs + several axioms. As UIFs can be > encoded > to SAT, I think that the theory of arrays could be as well. So, with a > bit of effort, > you should be

Hi Trevor, I just studied your diagrams -- I *think* that the "control tree" of structural analysis is not same as the "control flow tree" from your own Java work. However, as you understand your work more than I do, I present you with some fancy coloured diagrams that I drew that might help you (and others!) understand what structural analysis does a bit better than the

ValGrind gives me some info, but I'm not great at memory stuff, and so I'm not sure what to make of it... This is code that worked for someone 8 months ago, and I'm just trying to get it to run on llvm 2.9 instead of 2.8, so the fact that it hasn't been working is frustrating. Anyway, my issues seem to stem from IntervalIterator, as seen below. I have a lot of similar issues

I have another idea: let the BasicBlockSDNode points to the last node in its predecessor blocks. But this will introduce cycles into the selection DAG, making it not a DAG anymore. So what's the impact of a non-DAG on the existing DAG legalizers and combiner? On Wed, Jun 9, 2010 at 9:33 AM, Zhongxing Xu <xuzhongxing at gmail.com> wrote: > At first I'll try the simplest

Hi Chris, Thanks for the reply. I am actually interested in using the Intervals Analysis mainly to be able to do Region based analysis. In fact, I found that the way Intervals are defined mirror exactly the definition of a Region in the second edition of the Dragon Book (Section 9.7 on Region-Based Analysis), so it will be great if the Intervals related code still lives on in LLVM :). I found

On Mon, Apr 19, 2010 at 3:11 AM, Zhongxing Xu <xuzhongxing at gmail.com> wrote: > Hi all, > > We did some benchmarks on code size with clang, gcc 4.5, and open64. Clang > performed second in the test. The benchmark is CSiBE. Clang can't compile > the linux kernel (some inline asm not supported) and replaypc (error: use of > unknown builtin '__builtin_next_arg').

On Jun 11, 2010, at 12:48 AM, Zhongxing Xu <xuzhongxing at gmail.com> wrote: > I have another idea: let the BasicBlockSDNode points to the last > node in its predecessor blocks. But this will introduce cycles into > the selection DAG, making it not a DAG anymore. > > So what's the impact of a non-DAG on the existing DAG legalizers and > combiner? Lots of stuff

On 29 nov 2010 03:47 "Xu Zhongxing" <xuzhongxing at gmail.com> wrote: > Hi, > I enjoyed the new coding style in recent patches. Camel case makes it > easy to pick a descriptive name. Starting functions and variables with > lower cases reduces chances to conflict with a type name. On the other hand, having names that only differ in the case of a single character, is not