<html>
  <head>
    <meta content="text/html; charset=windows-1252"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    A few random comments scattered throughout.  <br>
    <br>
    <div class="moz-cite-prefix">On 01/08/2015 11:45 AM, Chandler
      Carruth wrote:<br>
    </div>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">First off, sorry for not circling back to
        this sooner. I think it managed to get caught in some part of
        the weird mail bounces from one address and I had to find it in
        my other account.</div>
      <div class="gmail_quote"><br>
      </div>
      <div class="gmail_quote">Also, more improtantly, I got distracted.
        But I'm back to hacking on this now and wanted to close the loop
        here.</div>
      <div class="gmail_quote"><br>
      </div>
      <div class="gmail_quote">On Tue Jun 17 2014 at 5:54:39 PM Duncan
        P. N. Exon Smith <<a moz-do-not-send="true"
          href="mailto:dexonsmith@apple.com">dexonsmith@apple.com</a>>
        wrote:<br>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Chandler,<br>
          <br>
          This is a high-level review of the new WIP `PassManager`
          infrastructure.<br>
          <br>
          For those that haven't dug into Chandler's commits, here's a
          very<br>
          high-level overview (assuming IIUC):<br>
          <br>
            - The driver supports simple declarative syntax for
          specifying passes<br>
              to run.  E.g., `module(a,b,function(c,d),e)` runs module
          passes `a`<br>
              and `b`, then function passes `c` and `d` for each
          function, and<br>
              then module pass `e`.<br>
          <br>
            - There is a new concept of an AnalysisManager (AM), which
          runs<br>
              analyses on-demand and caches the results.<br>
          <br>
            - Analysis passes are split conceptually from transformation
          passes.<br>
                  - Analysis:       run: (IRUnit*, AM*) -> Result<br>
                  - Transformation: run: (IRUnit*, AM*) ->
          PreservedAnalyses<br>
          <br>
              Note that neither of these matches the old interface,
          which was<br>
              runOnIRUnit: IRUnit* -> bool.<br>
        </blockquote>
        <div><br>
        </div>
        <div>Minor note for others: the PreservedAnalyses can be
          computed conservatively from the bool by selecting between all
          (false in the old interface) and none (true in the old
          interface)</div>
        <div><br>
        </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
            - PassManagers interoperate via adaptors.  E.g.,<br>
              ModuleToFunctionPassAdaptor is a module transformation
          pass that<br>
              contains a FunctionPassManager (with some set of function
          passes).<br>
          <br>
            - AnalysisManagers interoperate via proxies.  E.g.,<br>
              FunctionAnalysisManagerModuleProxy is a module analysis
          pass that<br>
              forwards to a FunctionAnalysisManager.<br>
          <br>
            - LazyCallGraph and ModuleToPostOrderCGSCCPassAdaptor
          collude to visit<br>
              SCCs in post-order, including API for updating the
          SCC-graph<br>
              on-the-fly without invalidating the traversal.<br>
          <br>
          I think what's done generally looks great.  In particular, the<br>
          declarative syntax is awesome and it's a huge step to have an<br>
          AnalysisManager that can reason about analyses separately from
          the pass<br>
          pipeline.  I haven't analysed the algorithms in LazyCallGraph
          carefully,<br>
          but I think it's great that they keep the traversal valid amid
          a<br>
          changing call graph.<br>
          <br>
          Questions and concerns:<br>
          <br>
           1. PassConcept requires a `name()` for passes.  Why don't<br>
              AnalysisPassConcept and AnalysisResultConcept?<br>
        </blockquote>
        <div><br>
        </div>
        <div>This was just me implementing things as I needed them. I
          hadn't done the analysis debug logging, and so hadn't needed a
          name yet. I've added that at this point for analysis passes
          (along with the name) but not for results. I'm not sure
          results need a name, the pass having a name seems sufficient
          to me.</div>
        <div> </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
           2. AnalysisManagerBase defines two versions of `invalidate()`
          -- one of<br>
              which takes a `Module*` (instead of `IRUnitT`).  It's not
          clear to<br>
              me why the analysis managers (other than
          ModuleAnalysisManager) need<br>
              this.  What am I missing?<br>
        </blockquote>
        <div><br>
        </div>
        <div>There are two ways invalidation happens, and they require
          different interfaces.</div>
        <div><br>
        </div>
        <div>a) A transformation pass returns some set of preserved
          analyses, and all others are invalidated by the pass manager.
          The pass manager can't enumerate the analysis passes and so
          just hands the preserved set and the IR unit to the analysis
          manager.</div>
        <div><br>
        </div>
        <div>b) A transformation pass directly invalidates a specific
          pass for its IR unit, potentially to re-compute a fresh
          version while running. This can be particularly important for
          cross-domain analyses. As a toy example, you could imagine
          having the inliner invalidate and recompute the domtree for
          the caller post inlining if it used the domtree over the
          caller to analyze the call sites.</div>
        <div><br>
        </div>
        <div>This may be a bit more clear now that the "invalidate"
          utility passes are in place, but if not, I should add some
          comments to this effect.</div>
        <div><br>
        </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
           3. The number of lines of code to enable transformation pass
          managers<br>
              (and analysis managers) to interoperate seems to scale
          quadratically<br>
              in the number of types of IRUnit.  Am I reading this
          wrong?  Is<br>
              there a plan to manage that, or is it an open problem? 
          (So far the<br>
              infrastructure only supports Module, SCC, and Function. 
          What<br>
              happens (e.g.) when we add BasicBlock passes?)<br>
        </blockquote>
        <div><br>
        </div>
        <div>You're not wrong. I see several ways of managing it, but so
          far I've just left it open because the overhead of the
          abstractions needed to manage it seem larger than the problem.
          That may change, and we'd need to revisit this if so.</div>
        <div><br>
        </div>
        <div>However, I'm not sure the number of IR units is likely to
          grow that much. Regarding basic block passes, I would like to
          just do away with them completely. I think the complexity they
          bring is greater than the utility they provide.</div>
      </div>
    </blockquote>
    Strongly agreed.  And having a BBPassBase which is a Function pass
    with a pure runOnBB function - with *no* special knowledge anywhere
    else - seems to solve any remaining benefit they do have.  In
    particular, I'd like to remove the can't modify any other block
    requirement since I've yet to meet a pass which actually obeys
    this.  <br>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">
        <div><br>
        </div>
        <div>Notably, I'm not sure it will ever make sense to have
          analysis management at a finer granularity than function,
          because I don't think there are any more narrow domains which
          can compute analysis results in conjunction with
          transformations independently on two units. Maybe I'm wrong?</div>
      </div>
    </blockquote>
    The only one I question is a loop analysis.  What happens if a loop
    transform modifies one small subloop out of a large function?<br>
    <br>
    (I should have read further before typing...)<br>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">
        <div><br>
        </div>
        <div>I'm somewhat expecting the only other significant addition
          to be a loop pass management layer, and I suspect that one
          will not provide the analyses at all.</div>
      </div>
    </blockquote>
    <br>
    I'll be interested in your thoughts on this when you get to it. 
    This might be another one to talk about in person.  :)<br>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">
        <div><br>
        </div>
        <div>I'm curious what you and others think here. I do consider
          this area still "open" in that I don't think we're painted
          into a corner (yet).</div>
        <div> </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
           4. Previously, (e.g.) function analysis passes would
          typically hold<br>
              results only for one function -- when the next function
          was<br>
              analyzed, the previous function's results would be
          invalidated.<br>
              Now, the FunctionAnalysisManager will happily store
          results for<br>
              every function.  (Looking forward,
          BasicBlockAnalysisManager might be<br>
              able to store results for every BasicBlock.)<br>
          <br>
              This is powerful, but costs memory.  What's the plan for
          keeping<br>
              memory usage in check (especially for large modules)?<br>
        </blockquote>
        <div><br>
        </div>
        <div>The is both the benefit and challenge of the new system.
          The "plan" (such as it is) is to teach the pass managers to GC
          analysis results. I'm not focused on that until the system is,
          in essence, working because its hard to know what the right
          balance is here without being able to run a big pipeline of
          passes over a big pile of IR. I have to imagine that the
          module -> SCC adaptor layer is going to do some amount of
          GC'ing of analysis results for SCCs that are quiesced, the
          question is what the right signal is for quiesced. We have a
          *lot* of options here while we're using the caching approach,
          and I have no way to predict which will be the best.</div>
      </div>
    </blockquote>
    Something like a victim cache might be one option, but let's talk
    about this more once you get there.  :)<br>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">
        <div><br>
        </div>
        <div>Ultimately, this is allowing us to consciously make a
          time/space tradeoff. While it means we have to think about
          that tradeoff at least we get to make it now! =]</div>
      </div>
    </blockquote>
    Having this be parametrizable will be nice.  :)<br>
    <br>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">
        <div><br>
        </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
           5. In the old infrastructure, `CGPassManager::runOnModule()`
          (in<br>
              `CallGraphSCCPass.cpp`) has a do-while loop that re-runs
          all passes<br>
              on a given SCC as long something new gets devirtualized,
          up to a<br>
              maximum number of iterations.  I don't see the equivalent
          loop in<br>
              CGSCCPassManager, and I don't see an obvious way to
          accomplish the<br>
              same optimization cycle.<br>
          <br>
                - How will we re-implement this loop?  (Or did I miss
          it?)<br>
        </blockquote>
        <div><br>
        </div>
        <div>I'm planning to have a iterate utility that can add a
          limited amount of iteration based on specific conditions of
          any pass, including a CGSCC pass manager.</div>
        <div> </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
                - There's a potential infinite loop between
          devirtualization and<br>
                  inlining on recursive virtual functions.  How will we
          avoid it?<br>
        </blockquote>
        <div><br>
        </div>
        <div>I don't follow? We don't inline recursive functions.
          Eventually, we either run out of call sites or see direct
          recursion and stop inlining. Am I missing a case where this
          behaves differently during devirtualization?</div>
        <div><br>
        </div>
        <div>(Arguably, we shouldn't just *stop*, we should do something
          more intelligent, but that's orthogonal to the pass manager.
          That's just a weakness of the inliner. And naturally, solving
          it includes setting limits.)</div>
        <div><br>
        </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
           6. There aren't any machine-level pass managers yet.  Will
          they look<br>
              about the same?  (Are there open problems to solve there?)<br>
        </blockquote>
        <div><br>
        </div>
        <div>I have NO IDEA! =[ This is a big open area.</div>
        <div><br>
        </div>
        <div>My current plan is to start off the way the current pass
          manager works: there are currently two independent module pass
          managers. At first, there will still be, and only one will be
          the new pass manager.</div>
        <div><br>
        </div>
        <div>My next planned step is to try to encapsulate codegen
          within a single function pass, and the MC streaming within a
          single module pass. Then, internally, codegen can continue
          using MachineFunctionPass and other things. I don't know how
          well this will work with analyses though.</div>
        <div><br>
        </div>
        <div>Failing that, there will be a new RFC thread about how to
          move CodeGen into the new pass manager world because it'll be
          a substantial chunk of work, and largely independent work.
          This is an area where I would love help of course. =D I think
          the only thing it would depend on is having most of the
          IR-level analysis up and running. From that point on, it
          should be completely independent.</div>
        <div> </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
           7. Andy asked in a separate thread [1] (my words): "Does this<br>
              infrastructure allow for invalidation of classes of
          analyses?"<br>
              (E.g., invalidate all analyses whose results depend on the<br>
              control-flow graph.)  Your response there [2] was (my
          words): "Not<br>
              directly, but `AnalysisManager` will be a good place for
          that API."<br>
          <br>
              I thought a little about this, and it's not clear to me
          how to fit<br>
              this API into AnalysisManager cleanly.<br>
          <br>
              One side seems straightforward.  Assuming you have a
          transformation<br>
              pass that modifies the CFG, tell the AnalysisManager that
          you've<br>
              modified the CFG, and return that all analyses have been
          preserved<br>
              (since everything else has).  This side is easy to make
          opt-in.<br>
          <br>
              The other side is not opt-in, though.  *All* analyses that
          depend on<br>
              the CFG must respond, or the invalidation mechanism
          doesn't work.<br>
        </blockquote>
        <div><br>
        </div>
        <div>My very hand-wavy idea has been to use something along the
          lines of the preserved set for this. Essentially, analyses
          which rely on the CFG can test for whether that has been
          preserved, and if not, become invalid. Then we can just "try"
          to invalidate all the analysis results, and only those that
          are safe will remain.</div>
      </div>
    </blockquote>
    Alternatively, we could add a callback/option/flag on analyses to
    indicate they need to be invalidated on CFG change and 'dummy
    analysis' for each grouping.  The analysis manager could then loop
    through all registered analyses and call invalidate iff the flag is
    set.  <br>
    <br>
    It might be a good idea to segregate passes into hard categories for
    "manually invalidated/preserved" and "inferred from groups". 
    Attempting to use an analysis from one group with the other
    mechanism should result in clear and obvious error messages. 
    (Maybe?  Not sure here.)<br>
    <br>
    Honestly, I'm a bit queasy with the idea of having two ways to
    express invalidation/preservation though.  If we do want to support
    it, it should be unified as early in the process as possible with
    good logging about what's happening.<br>
    <br>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">
        <div><br>
        </div>
        <div>There are several related options with different API
          tradeoffs. I'd need to sit down and implement it to see which
          pattern was really the best. Open to suggestions here.</div>
        <div><br>
        </div>
        <div>Another option I've toyed with, but not yet found a way
          that I like is to have some shared IDs in addition to the
          unique IDs, and use those to form category sets.</div>
        <div> </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">
          <br>
           8. `CGPassManager` was one place where the old return value
          for a<br>
              transformation pass (`bool` representing "did-change") was
          useful.<br>
              Are there any others?</blockquote>
        <div><br>
        </div>
        <div>Not to my knowledge. =[</div>
      </div>
    </blockquote>
    I've got some out of tree code that uses the return code when
    running sub-passes.  And yes, I know that constructing an inner pass
    manager, or even just a single pass, and running it inside another
    pass is utterly unsupported.  It is often useful though.  :)<br>
    <blockquote
cite="mid:CAAwGriHAaguP0Nf=P-mtZBSQqcq5PT-jHX_edSZLEZDL11GywA@mail.gmail.com"
      type="cite">
      <div class="gmail_quote">
        <div> </div>
        <blockquote class="gmail_quote" style="margin:0 0 0
          .8ex;border-left:1px #ccc solid;padding-left:1ex">    Is the
          API using `PreservedAnalyses::all()`<br>
              as a stand-in for "did-not-change"?  If so, does that
          conflict with<br>
              adding more nuanced API for on-the-fly invalidation of
          analyses?<br>
        </blockquote>
        <div><br>
          Currently, yes, it is using preserving all analyses as a
          stand-in for "did no work". This seems fine for invalidation
          purposes, but not so good for the iteration thing I mentioned
          above. I think we'll need a better way to indicate "no work
          done", but not sure what the best way is. Suggestions very
          welcome here as well.</div>
      </div>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
    </blockquote>
    <br>
  </body>
</html>