<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Aug 9, 2008, at 12:14 PM, Hiren Patel wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><tt>My apologies for the vague question formulation. I'll explain my objective with an example.<span class="Apple-converted-space"> </span><br><br>My initial source is as follows:<br></tt><tt>unsigned int fib(unsigned int m) {<br> unsigned int f0 = 0 ;<br> unsigned int f1 = 1, f2, i ;<br> unsigned int l1 = 0;<br> if (m <= 1) {<br></tt><tt> MARKSTART();<br> printf("Return\n");<br></tt><tt> MARKEND();</tt><br><tt> return m;<br> } else {<br> for (i = 2; i <=m; i++) {<br> f2 = f0 + f1;<br> f0 = f1;<br> f1 = f2;<br> for (l1 = 0; l1 <5; l1++) {<br> printf("woof\n");<br> MARKSTART();<br> }<br> MARKEND();<br> MARKSTART();<br> }<br> MARKEND();<br> return f2;<br> }<br>}<br><br>The MARKSTART and MARKEND represent MACROs that implement a certain instruction in a particular processor. The semantics of the MARKEND and MARKSTART can be simply thought of as starting and stopping cycle timers for segments of code between the MARKSTART and MARKEND. The resulting code after the transformation is as follows:</tt><tt><br>unsigned int fib(unsigned int m) {<br> unsigned int f0 = 0 ;<br> unsigned int f1 = 1, f2, i ;<br> unsigned int l1 = 0;<br> if (m <= 1) {<br> MARKSTART0("fib_seq0");<br> printf("Return\n");<br></tt><tt> MARKEND0("fib_seq0");</tt><br><tt> return m;</tt><br><tt> } else {<br> for (i = 2; i <=m; i++) {<br> MARKSTARTCOUNT("bb_k");<br> f2 = f0 + f1;<br> f0 = f1;<br> f1 = f2;<br></tt><tt> MARKENDCOUNT("bb_k");</tt><br><tt> for (l1 = 0; l1 <5; l1++) {<br> printf("woof\n");<br> MARKSTART2("fib_loop1");<br> }<br> MARKEND2("fib_loop1");<br> MARKSTART1("fib_loop0");<br> }<br> MARKEND1("fib_loop0");<br> return f2;<br> }<br>}<br><br>The number after a MARKSTART and MARKEND denotes a timer in the processor and the string, a unique label identifying blocks of interest used during profiling this code. We have certain rules that form a block, such as, a MARKSTART must always follow by a MARKEND and use of timers must be correctly nested. Notice the MARK*COUNT as only one example of labeling one basic block in the source. I would like to add these for every BB in the CFG as well. So the tasks here are:</tt></span></blockquote><div><br></div><div>Hi Hiren,</div><div><br></div><div>My apologies for the delay in my reply. I'll address each of your points inline. In general, I think there are two views you can take of the source:</div><div><br></div><div>1) The constructed ASTs.</div><div><br></div><div>2) A token stream, which literally consists of the stream of tokens passed to/returned from the preprocessor. A good example of this is in RewriteMacros.cpp in Driver.</div><div><br></div><div>We have accurate SourceLocation information for both, but both are different views of the source code. Since macros can expand to arbitrary amounts of code (including code that contains control flow), their is a tricky mapping from macros to their expanded statements, or even the basic blocks in the CFG.</div><div><br></div><div>I assume that by default MARKSTART and MARKEND expand to nothing. Using the token stream approach, you could record the SourceLocations for the approprate macros, and then using the AST approach you can conceivably search for the AST Stmt* that appears closest to those recorded locations (this may require two passes). This might be really tricky. An easier approach might be to have both macros expand (when using clang) to the "annotate" attribute, which can then be affixed to any AST node. Your analysis could then look for Stmt* with the annotation that you are interested in.</div><div><br></div><div>Once you have computed what new MARKSTARTXXX and MARKENDXXX text you want to insert, however, it is easy to add these back to the source. Using the rewriter, you can splice in text at any arbitrary SourceLocation.</div><div><br></div><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><tt>- Identify MARKSTART and MARKEND, allocate a cycle timer such that there are no conflicts between the START and END of a block.<span class="Apple-converted-space"> </span></tt></span></blockquote><div><br></div><div>I'm not quite certain what you mean by "conflicts", but I assume you are referring to the nesting property of MARKSTART and MARKEND above. Once you determine the locations of the MARKSTART and MARKEND macros, determine their association to the appropriate statements, the allocating a cycle timer, etc., may just result in doing a walk on the AST, since the AST is hierarchical and represents the nested structure of the code.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><tt><br>- Identify MARKSTART and MARKEND, add a unique label used in profiling. The labels much match the START and END that form a block.<br>- For every basic block, add MARKSTARTCOUNT and MARKENDCOUNT respectively with a unique BB label.<br></tt></span></blockquote></div><br><div>Note that Basic Blocks in the CFG include lots of control-flow constructs: if statements, loops, ternary operators (?), short circuit evaluation (&&, ||), gotos, etc. If you just want to profile things like loops, you might not even need to go to the CFG at all unless you want to support gotos. With gotos, you then have to identify the loop structure yourself. I think we have analyses like this at the LLVM IR level, but nothing like that yet for source-level analysis.</div><div><br></div><div>Right now the CFG also has some oddities with DeclStmts. If a Decl represents a multiple variable declaration (e.g., int x, y, z), in the CFG the single DeclStmt in the AST is transformed into three DeclStmts to explicitly represent their control-flow dependency. These new DeclStmts don't appear in the original AST, but they should have the correct sourcelocation information. This solution is likely to change soon.</div><div><br></div><div>That said, each basic block is uniquely numbered. I don't know all the details of your analysis, but I think the hardest part of your task will be identifying the locations of the original macros and mapping those to the nearest AST Stmt*.</div></body></html>