<div dir="ltr">
Hi Philip,

<br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Mar 2, 2018 at 6:06 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div text="#000000" bgcolor="#FFFFFF">
    Reading through this last night got be thinking about how to model
    control flow.  Given most of my source code tends to be very
    branchy, be limited to straight line code is quite restrictive.  The
    main thing is that it requires a lot of hand simplification which
    can be rather error prone at times.  <br>
    <br>
    It occurs to me that we could remove the restriction around branches
    without necessarily fully modeling fetch, decode, or prediction.  If
    in addition to an assembly file, we also feed the tool a trace of
    branch executions, the tool could essentially unroll all loops
    dynamically.  The type of thing I'm thinking of would look like
    something like this: (ENTRY, branch_dest, branch_dest, branch_dest)
    where each "branch_dest" is the taken successor of the next
    encountered branch instruction.  <br>
    <br>
    As an example, consider a simple loop which executes 3 times:<br>
    ENTRY:<br>
      # fallthrough<br>
    bb1:<br>
      # various instructions<br>
      jne bb1<br>
    bb2:<br>
      ret<br>
    <br>
    The trace for this would look like: (ENTRY, bb1, bb1, bb1,
    FALLTHROUGH).  <br>
    <br>
    The nice thing about such a branch trace is that it separate the
    source of the trace from the analysis tool.  You could provide an
    actual trace collected through instrumentation, or a predicted trace
    generated from sample profiling information. <br></div></blockquote><div><br>
<div>I think so too. That would be an interesting extension.<br><br></div><div>Ideally, a trace could contain even more than just branch information. As Andy wrote in his first comment "<span class="gmail-m_2779934164486012970gmail-im"></span>
<span class="gmail-m_2779934164486012970gmail-im">Combining the static model with a sampled dynamic hardware event profile would be amazing.</span>".  The idea of having a branch trace is nice and it can be a start.</div>

 </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF">
    <br>
    (There are obvious extensions to handle indirect branches, calls,
    and such here.  I'm leaving that as an exercise for the reader at
    the moment.)<br>
    <br>
    By itself, this seems like a really useful usability improvement.<br>
    <br>
    You could also build on top of this notion to model both branch
    prediction mispredicts and resource limitations.  (Or only one or
    the other.)  From the perspective of the predictor, the trace would
    be ground truth so you could analyze how well a particularly
    prediction strategy works on that particular trace.  Distinct from
    the prediction, you could model delay between branch execution and
    condition satisfaction to identify resource limits in the actual
    speculative execution.  (I'm very deliberately being vague here;
    it's been a long time since I looked into this aspect of things and
    don't remember the appropriate terminology.  Figured it was better
    to be vague than potentially misleading by getting it wrong.)<span class=""><br></span></div></blockquote><div><br>
<span class="gmail-im"><div><br></div></span><div>Makes sense. Thanks for the idea.</div>

<br></div><div>-Andrea<br> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF"><span class="">
    <br>
    Philip<br>
    </span><br></div></blockquote></div></div></div>