<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 8, 2015, at 12:37 PM, Philip Reames <<a href="mailto:listmail@philipreames.com" class="">listmail@philipreames.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
  
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type" class="">
  
  <div bgcolor="#FFFFFF" text="#000000" class="">
    <br class="">
    <div class="moz-cite-prefix">On 01/07/2015 06:42 PM, Adam Nemet
      wrote:<br class="">
    </div>
    <blockquote cite="mid:88BAEE4F-AABE-4CA1-BAA8-55D2BC2B991C@apple.com" type="cite" class="">
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" class="">
      <br class="">
      <div class="">
        <blockquote type="cite" class=""><br class="">
          <div class="">
            <div dir="ltr" style="font-family: Helvetica; font-size:
              12px; font-style: normal; font-variant: normal;
              font-weight: normal; letter-spacing: normal; line-height:
              normal; orphans: auto; text-align: start; text-indent:
              0px; text-transform: none; white-space: normal; widows:
              auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
              <div class="gmail_extra">
                <div class="gmail_quote">
                  <div class="">How does this compare with classical
                    approaches of loop peeling, partitioning, fission,
                    or whatever you might call it? Is there any
                    literature behind this approach or some literature
                    it should be compared with? (I genuinely don't know
                    this area that well, so I'm of little help here…)</div>
                </div>
              </div>
            </div>
          </div>
        </blockquote>
        <div class=""><br class="">
        </div>
        <div class="">I think it’s pretty different from loop
          distribution/fission.  In loop distribution, in order to split
          the loop into multiple consecutive loops, you need to reason
          about the memory references so having a function call makes
          that difficult/impossible.  Phillip’s idea works around this
          exact issue.</div>
        <div class=""><br class="">
        </div>
        <div class="">I explored this space quite a bit recently because we’re
          working on a proposal to add loop distribution to LLVM.  I
          hope to send out the proposal this week.</div>
      </div>
    </blockquote>
    Just to note, I'm going to be very interested in seeing this.  I
    have concerns about profitability, but having a mechanism is clearly
    a good thing.  :)<br class=""></div></div></blockquote><blockquote type="cite" class=""><div bgcolor="#FFFFFF" text="#000000" class="">Are you also looking at loop fusion?  I've seen that come up in
    practice for a few cases where it would *really* help.  Generally,
    filter/reduce patterns implemented by hand.  Nowhere near the top of
    my priority list, but if you happened to be working on it, I'm happy
    to help review and brainstorm.  <br class=""></div></blockquote><div><br class=""></div><div>Yes, we’re planning to look at fusion next.  Thanks for all your feedback so far!</div><div><br class=""></div><div>As to your example, do you mean chain of operations functional-programming style?  E.g. with OO syntax:</div><div><br class=""></div><div>list.map(func1).map(func2).filter(func3).reduce(func4), where these could be squashed into one loop.</div><div><br class=""></div><div>Thanks,</div><div>Adam</div><div><br class=""></div><blockquote type="cite" class=""><div bgcolor="#FFFFFF" text="#000000" class="">
    <blockquote cite="mid:88BAEE4F-AABE-4CA1-BAA8-55D2BC2B991C@apple.com" type="cite" class="">
      <div class="">
        
        <div class="">So I see no issue with trying to handle loops with
          low-probablity function calls with this and fully
          self-contained loops with classical loop distribution.</div>
        <div class=""><br class="">
        </div>
        <div class="">Thanks,</div>
        <div class="">Adam</div>
        <div class=""><br class="">
        </div>
        <blockquote type="cite" class="">
          <div dir="ltr" style="font-family: Helvetica; font-size: 12px;
            font-style: normal; font-variant: normal; font-weight:
            normal; letter-spacing: normal; line-height: normal;
            orphans: auto; text-align: start; text-indent: 0px;
            text-transform: none; white-space: normal; widows: auto;
            word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
            <div class="gmail_extra">
              <div class="gmail_quote">
                <div class="">Some of your points I have quick feedback
                  on:</div>
                <blockquote class="gmail_quote" style="margin: 0px 0px
                  0px 0.8ex; border-left-width: 1px; border-left-color:
                  rgb(204, 204, 204); border-left-style: solid;
                  padding-left: 1ex;">
                  <div bgcolor="#FFFFFF" text="#000000" class="">
                    <div class="">
                      <div class=""><p class="">Points for discussion:</p>
                        <ul class="">
                          <li class="">Is using profile information for
                            this purpose even a reasonable thing to do?</li>
                        </ul>
                      </div>
                    </div>
                  </div>
                </blockquote>
                <div class="">Yes!</div>
                <div class=""> </div>
                <blockquote class="gmail_quote" style="margin: 0px 0px
                  0px 0.8ex; border-left-width: 1px; border-left-color:
                  rgb(204, 204, 204); border-left-style: solid;
                  padding-left: 1ex;">
                  <div bgcolor="#FFFFFF" text="#000000" class="">
                    <div class="">
                      <div class="">
                        <ul class="">
                          <li class="">I chose to implement this without
                            relying on the existing block frequency
                            analysis. My reasoning was that a) this is a
                            rarely taken case and adding an expensive
                            analysis dependency probably wasn't
                            worthwhile and b) that block frequency
                            analysis was more expensive/precise than I
                            really needed. Is this reasonable?</li>
                        </ul>
                      </div>
                    </div>
                  </div>
                </blockquote>
                <div class="">I think we should always use the analyses.
                  Either BlockFrequency or BranchProbability. I think
                  probably both in the common joint usage (frequency of
                  the loop header combined with probability of the cold
                  region).</div>
                <blockquote class="gmail_quote" style="margin: 0px 0px
                  0px 0.8ex; border-left-width: 1px; border-left-color:
                  rgb(204, 204, 204); border-left-style: solid;
                  padding-left: 1ex;">
                  <div bgcolor="#FFFFFF" text="#000000" class="">
                    <div class="">
                      <div class="">
                        <ul class="">
                          <li class="">If so, is the notion of
                            'rareness' of a loop block something that's
                            worth extracting out on it's own and
                            reusing? Are there other similar uses anyone
                            can think of?</li>
                          <li class="">Currently, I'm only supporting a
                            fairly small set of controlling conditions.
                            Are there important cases I'm not
                            considering?</li>
                        </ul>
                      </div>
                    </div>
                  </div>
                </blockquote>
                <div class="">To both of these, I think the general
                  combination to use is to identify the set of blocks
                  dominated by a block which is in the loop body of a
                  hot loop, and is cold relative to the other successors
                  of its predecessor(s). These form cold "regions" as I
                  think of them without requiring the complexity of the
                  region analysis.</div>
                <div class=""> </div>
                <blockquote class="gmail_quote" style="margin: 0px 0px
                  0px 0.8ex; border-left-width: 1px; border-left-color:
                  rgb(204, 204, 204); border-left-style: solid;
                  padding-left: 1ex;">
                  <div bgcolor="#FFFFFF" text="#000000" class="">
                    <div class="">
                      <div class="">
                        <ul class="">
                          <li class="">Since the rarest latch is often
                            deep in a loop - with other "if (X)
                            continue;" (i.e. latches) before it - this
                            tends to create loops with multiple exiting
                            blocks. Some of the existing passes might
                            not deal with this well, is that a major
                            concern? Suggestions for how to analysis and
                            validate?</li>
                        </ul>
                      </div>
                    </div>
                  </div>
                </blockquote>
                <div class="">I'm somewhat concerned about this, but
                  want to think more about the fundamental
                  transformation.</div>
                <div class=""> </div>
                <blockquote class="gmail_quote" style="margin: 0px 0px
                  0px 0.8ex; border-left-width: 1px; border-left-color:
                  rgb(204, 204, 204); border-left-style: solid;
                  padding-left: 1ex;">
                  <div bgcolor="#FFFFFF" text="#000000" class="">
                    <div class="">
                      <div class="">
                        <ul class="">
                          <li class="">Currently, I've structured this
                            as pulling off the rarest latch as an outer
                            iteration. I could also pull off the most
                            popular latch as an inner iteration. This
                            might give different tradeoffs; thoughts?</li>
                        </ul><p class="">Generally, any thoughts anyone have
                          on the problem or approach are welcome. I'm
                          not particular attached to the particular
                          approach laid out here and if there's a more
                          advantageous approach, all the better.</p>
                      </div>
                    </div>
                  </div>
                </blockquote>
              </div>
              Thanks for pushing on this! ;] Now I need to go and ponder
              a lot so i can reply more deeply on the actual transform.<br class="">
              <br class="">
            </div>
          </div>
          <span style="font-family: Helvetica; font-size: 12px;
            font-style: normal; font-variant: normal; font-weight:
            normal; letter-spacing: normal; line-height: normal;
            orphans: auto; text-align: start; text-indent: 0px;
            text-transform: none; white-space: normal; widows: auto;
            word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
            none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style:
            normal; font-variant: normal; font-weight: normal;
            letter-spacing: normal; line-height: normal; orphans: auto;
            text-align: start; text-indent: 0px; text-transform: none;
            white-space: normal; widows: auto; word-spacing: 0px;
            -webkit-text-stroke-width: 0px;" class="">
          <span style="font-family: Helvetica; font-size: 12px;
            font-style: normal; font-variant: normal; font-weight:
            normal; letter-spacing: normal; line-height: normal;
            orphans: auto; text-align: start; text-indent: 0px;
            text-transform: none; white-space: normal; widows: auto;
            word-spacing: 0px; -webkit-text-stroke-width: 0px; float:
            none; display: inline !important;" class="">LLVM Developers
            mailing list</span><br style="font-family: Helvetica;
            font-size: 12px; font-style: normal; font-variant: normal;
            font-weight: normal; letter-spacing: normal; line-height:
            normal; orphans: auto; text-align: start; text-indent: 0px;
            text-transform: none; white-space: normal; widows: auto;
            word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
          <a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu" style="font-family: Helvetica; font-size: 12px; font-style:
            normal; font-variant: normal; font-weight: normal;
            letter-spacing: normal; line-height: normal; orphans: auto;
            text-align: start; text-indent: 0px; text-transform: none;
            white-space: normal; widows: auto; word-spacing: 0px;
            -webkit-text-stroke-width: 0px;" class="">LLVMdev@cs.uiuc.edu</a><span style="font-family: Helvetica; font-size: 12px; font-style:
            normal; font-variant: normal; font-weight: normal;
            letter-spacing: normal; line-height: normal; orphans: auto;
            text-align: start; text-indent: 0px; text-transform: none;
            white-space: normal; widows: auto; word-spacing: 0px;
            -webkit-text-stroke-width: 0px; float: none; display: inline
            !important;" class=""><span class="Apple-converted-space"> </span>        </span><a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu/" style="font-family: Helvetica; font-size: 12px; font-style:
            normal; font-variant: normal; font-weight: normal;
            letter-spacing: normal; line-height: normal; orphans: auto;
            text-align: start; text-indent: 0px; text-transform: none;
            white-space: normal; widows: auto; word-spacing: 0px;
            -webkit-text-stroke-width: 0px;" class="">http://llvm.cs.uiuc.edu</a><br style="font-family: Helvetica; font-size: 12px; font-style:
            normal; font-variant: normal; font-weight: normal;
            letter-spacing: normal; line-height: normal; orphans: auto;
            text-align: start; text-indent: 0px; text-transform: none;
            white-space: normal; widows: auto; word-spacing: 0px;
            -webkit-text-stroke-width: 0px;" class="">
          <a moz-do-not-send="true" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="font-family: Helvetica; font-size: 12px; font-style:
            normal; font-variant: normal; font-weight: normal;
            letter-spacing: normal; line-height: normal; orphans: auto;
            text-align: start; text-indent: 0px; text-transform: none;
            white-space: normal; widows: auto; word-spacing: 0px;
            -webkit-text-stroke-width: 0px;" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></blockquote>
      </div>
      <br class="">
    </blockquote>
    <br class="">
  </div>

</blockquote></div><br class=""></body></html>