<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 10/30/13 9:56 AM, Quentin Colombet
wrote:<br>
</div>
<blockquote
cite="mid:28A6557F-A468-4537-A154-E6AB4E2F04CE@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
Hi Philip,
<div><br>
</div>
<div>Could you define what is an accurate stack trace for your
project?</div>
<div>In other words, what do you mean by full and accurate stack
frame?</div>
<div><br>
</div>
<div>Without this definition, this is difficult to give you any
feedback. In particular, I do not see what it means when we use
inlining.</div>
</blockquote>
Sure. Just to note, I *think* your example was exactly what we're
looking for. I got a bit confused about your notation, so I'm going
to start from scratch. <br>
<br>
By a "full and accurate stack trace" in the face of inlining, I mean
the exact stack trace you would get without any inlining (i.e. in a
unoptimized build.) To put this another way, I need to be able to
distinguish the path by which a function was inlined. Consider the
following example (in approximate C):<br>
<br>
void a() {<br>
if( randomly_true ) print_stack_trace();<br>
}<br>
void b() {<br>
a();<br>
}<br>
void c() {<br>
a();<br>
}<br>
void main() {<br>
b();<br>
c();<br>
}<br>
<br>
In our environment, we need to be able to distinguish the traces
"a;b;main" from "a;c;main" reliably. We need this regardless of
what decisions the optimizer might make about inlining (or other
optimizations for that matter). <br>
<br>
For another example, "a" might be a routine which requires
privileges to execute. "b" might a routine which adds privileges.
"c" might be an untrusted routine. Calling "a" from "b" will
succeed. Calling "a" from "c" will generate an exception. (We can
handle all the details around when to throw exceptions if the
information about stack traces is accurate and trustworthy.) <br>
<br>
Side note: The permission question above can't be addressed
statically. The call to the privileged routine doesn't have to be
direct. "a" could be a series of frames "a1...aN" where "aN" is
actually the privileged one. There can also be virtual (or other
runtime dispatch) calls in that path which prevent static analysis.<br>
<br>
Does that help clarify what we're looking for?<br>
<br>
Philip<br>
<br>
<br>
<blockquote
cite="mid:28A6557F-A468-4537-A154-E6AB4E2F04CE@apple.com"
type="cite">
<div>E.g., what do you expect from code like this:</div>
<div>static void fct1(…) {</div>
<div> ...</div>
<div>}</div>
<div><br>
</div>
<div>static void fct2(…) {</div>
<div> …</div>
<div> fct1(…)</div>
<div> ...</div>
<div>}</div>
<div><br>
</div>
<div>void fct3(…) {</div>
<div> fct1(...)</div>
<div> …</div>
<div> fct2(…)</div>
<div> …</div>
<div>}</div>
<div><br>
</div>
<div>Assuming everything is inlined in fct3, you get:</div>
<div>void fct3(…) {</div>
<div> ….</div>
<div>1. fct1_inst1… fct1_instN</div>
<div> ….</div>
<div>2. fct2_inst1… fct2_instK</div>
<div>3. fct1_inst1… fct1_instN</div>
<div>4. fct2_instzK+1… fct2_instN</div>
<div> ...</div>
<div>}</div>
<div><br>
</div>
<div>Does it mean you what something like this each point of
interest for you stack frame:</div>
<div>1.</div>
<div>#0 fct1</div>
<div>#1 fct3</div>
<div><br>
</div>
<div>2.</div>
<div>
<div>#0 fct2</div>
<div>#1 fct3</div>
</div>
<div><br>
</div>
<div>
<div>3.</div>
<div>
<div>#0 fct1</div>
<div>#1 fct2</div>
<div>#2 fct3</div>
</div>
</div>
<div><br>
</div>
<div>
<div>
<div>4.</div>
<div>
<div>#0 fct2</div>
</div>
</div>
</div>
<div>#1 fct3</div>
<div><br>
</div>
<div>Cheers,<br>
<div apple-content-edited="true">
<div style="color: rgb(0, 0, 0); font-family: Helvetica;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: 2; text-align: -webkit-auto; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; word-wrap: break-word;
-webkit-nbsp-mode: space; -webkit-line-break:
after-white-space; ">-Quentin</div>
</div>
<br>
<div>
<div>On Oct 28, 2013, at 2:56 PM, Philip Reames <<a
moz-do-not-send="true"
href="mailto:listmail@philipreames.com">listmail@philipreames.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">Is there a known way to preserve a
full and accurate stack trace while utilizing most of LLVM's
optimization abilities?<br>
<br>
We are investigating using LLVM as a JIT for a language
which requires the ability to generate an accurate stack
trace from any arbitrary point(1) during the execution. I
know that we can make this work by doing inlining
externally, manually recording virtual frames, and disabling
optimizations such as tail call optimizations. To me, this
seems like an unpleasant hack that would likely inhibit much
of LLVM's built in optimizing ability. I suspect that if we
ended up having to pursue this strategy, it would likely
greatly diminish the benefit we could get by moving to an
LLVM backend. (2)<br>
<br>
Currently, I am aware of two lines of related work. First,
I know that there has been some work into enabling full
speed debug builds (-g -O3) for Clang which may be related.
Second, I know that the various sanitizer tools include
stack traces in their reporting.<br>
<br>
What I have not been able to establish is the intended
semantics of these approaches. Is the intent that a stack
trace will always be preserved? Or simply that a best
effort will be made to preserve the stack trace? Since for
us the need to preserve a full stack trace is a matter of
correctness, we couldn't use a mechanism which only provided
best effort semantics.<br>
<br>
Are there other lines of related work that I have missed?
Are there any other language implementations out there that
have already solved this problem? I would welcome
references to existing implementations or suggestions on how
to approach this problem.<br>
<br>
Philip<br>
<br>
p.s. I know that there are a number of possible approaches
to identifying when a bit of code doesn't actually need a
full stack trace and optimizing these more aggressively.
We're considering a number of these approaches, but I am
mostly interested in identifying a reasonable high
performance base implementation at this time. (Feel free to
comment if you think this is the wrong approach.)<br>
<br>
(1) Technically, the semantics are slightly more limited
then I've described. The primary usage is for exceptions,
security checking, and a couple of rarely used routines in
the standard library.<br>
(2) I haven't actually measured this yet. If anyone feels
my intuition is likely off here, let me know and I'll invest
the time to actually do so.<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</body>
</html>