<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>