Skip to content
  1. Nov 23, 2013
    • Chandler Carruth's avatar
      [PM] Rename TestAnalysisPass to TestFunctionAnalysis to clear the way · 2ad18583
      Chandler Carruth authored
      for a TestModuleAnalysis.
      
      llvm-svn: 195537
      2ad18583
    • Chandler Carruth's avatar
      [PM] Add support to the analysis managers to query explicitly for cached · de9afd84
      Chandler Carruth authored
      results.
      
      This is the last piece of infrastructure needed to effectively support
      querying *up* the analysis layers. The next step will be to introduce
      a proxy which provides access to those layers with appropriate use of
      const to direct queries to the safe interface.
      
      llvm-svn: 195525
      de9afd84
    • Chandler Carruth's avatar
      [PM] Switch the downward invalidation to be incremental where only the · bceeb229
      Chandler Carruth authored
      one function's analyses are invalidated at a time. Also switch the
      preservation of the proxy to *fully* preserve the lower (function)
      analyses.
      
      Combined, this gets both upward and downward analysis invalidation to
      a point I'm happy with:
      
      - A function pass invalidates its function analyses, and its parent's
        module analyses.
      - A module pass invalidates all of its functions' analyses including the
        set of which functions are in the module.
      - A function pass can preserve a module analysis pass.
      - If all function passes preserve a module analysis pass, that
        preservation persists. If any doesn't the module analysis is
        invalidated.
      - A module pass can opt into managing *all* function analysis
        invalidation itself or *none*.
      - The conservative default is none, and the proxy takes the maximally
        conservative approach that works even if the set of functions has
        changed.
      - If a module pass opts into managing function analysis invalidation it
        has to propagate the invalidation itself, the proxy just does nothing.
      
      The only thing really missing is a way to query for a cached analysis or
      nothing at all. With this, function passes can more safely request
      a cached module analysis pass without fear of it accidentally running
      part way through.
      
      llvm-svn: 195519
      bceeb229
  2. Nov 22, 2013
    • Chandler Carruth's avatar
      [PM] Teach the analysis managers to pass themselves as arguments to the · f2edc075
      Chandler Carruth authored
      run methods of the analysis passes.
      
      Also generalizes and re-uses the SFINAE for transformation passes so
      that users can write an analysis pass and only accept an analysis
      manager if that is useful to their pass.
      
      This completes the plumbing to make an analysis manager available
      through every pass's run method if desired so that passes no longer need
      to be constructed around them.
      
      llvm-svn: 195451
      f2edc075
    • Chandler Carruth's avatar
      [PM] Remove the IRUnitT typedef requirement for analysis passes. · bf950c0f
      Chandler Carruth authored
      Since the analysis managers were split into explicit function and module
      analysis managers, it is now completely trivial to specify this when
      building up the concept and model types explicitly, and it is impossible
      to end up with a type error at run time. We instantiate a template when
      registering a pass that will enforce the requirement at a type-system
      level, and we produce a dynamic error on all the other query paths to
      the analysis manager if the pass in question isn't registered.
      
      llvm-svn: 195447
      bf950c0f
    • Chandler Carruth's avatar
      [PM] Fix the analysis templates' usage of IRUnitT. · 5bf5e31c
      Chandler Carruth authored
      This is supposed to be the whole type of the IR unit, and so we
      shouldn't pass a pointer to it but rather the value itself. In turn, we
      need to provide a 'Module *' as that type argument (for example). This
      will become more relevant with SCCs or other units which may not be
      passed as a pointer type, but also brings consistency with the
      transformation pass templates.
      
      llvm-svn: 195445
      5bf5e31c
    • Michael Gottesman's avatar
    • Chandler Carruth's avatar
      [PM] Switch analysis managers to be threaded through the run methods · b3e72199
      Chandler Carruth authored
      rather than the constructors of passes.
      
      This simplifies the APIs of passes significantly and removes an error
      prone pattern where the *same* manager had to be given to every
      different layer. With the new API the analysis managers themselves will
      have to be cross connected with proxy analyses that allow a pass at one
      layer to query for the analysis manager of another layer. The proxy will
      both expose a handle to the other layer's manager and it will provide
      the invalidation hooks to ensure things remain consistent across layers.
      Finally, the outer-most analysis manager has to be passed to the run
      method of the outer-most pass manager. The rest of the propagation is
      automatic.
      
      I've used SFINAE again to allow passes to completely disregard the
      analysis manager if they don't need or want to care. This helps keep
      simple things simple for users of the new pass manager.
      
      Also, the system specifically supports passing a null pointer into the
      outer-most run method if your pass pipeline neither needs nor wants to
      deal with analyses. I find this of dubious utility as while some
      *passes* don't care about analysis, I'm not sure there are any
      real-world users of the pass manager itself that need to avoid even
      creating an analysis manager. But it is easy to support, so there we go.
      
      Finally I renamed the module proxy for the function analysis manager to
      the more verbose but less confusing name of
      FunctionAnalysisManagerModuleProxy. I hate this name, but I have no idea
      what else to name these things. I'm expecting in the fullness of time to
      potentially have the complete cross product of types at the proxy layer:
      
      {Module,SCC,Function,Loop,Region}AnalysisManager{Module,SCC,Function,Loop,Region}Proxy
      
      (except for XAnalysisManagerXProxy which doesn't make any sense)
      
      This should make it somewhat easier to do the next phases which is to
      build the upward proxy and get its invalidation correct, as well as to
      make the invalidation within the Module -> Function mapping pass be more
      fine grained so as to invalidate fewer fuction analyses.
      
      After all of the proxy analyses are done and the invalidation working,
      I'll finally be able to start working on the next two fun fronts: how to
      adapt an existing pass to work in both the legacy pass world and the new
      one, and building the SCC, Loop, and Region counterparts. Fun times!
      
      llvm-svn: 195400
      b3e72199
  3. Nov 21, 2013
    • Chandler Carruth's avatar
      [PM] Widen the interface for invalidate on an analysis result now that · 2846e9ef
      Chandler Carruth authored
      it is completely optional, and sink the logic for handling the preserved
      analysis set into it.
      
      This allows us to implement the delegation logic desired in the proxy
      module analysis for the function analysis manager where if the proxy
      itself is preserved we assume the set of functions hasn't changed and we
      do a fine grained invalidation by walking the functions in the module
      and running the invalidate for them all at the manager level and letting
      it try to invalidate any passes.
      
      This in turn makes it blindingly obvious why we should hoist the
      invalidate trait and have two collections of results. That allows
      handling invalidation for almost all analyses without indirect calls and
      it allows short circuiting when the preserved set is all.
      
      llvm-svn: 195338
      2846e9ef
    • Chandler Carruth's avatar
      [PM] Add support for using SFINAE to reflect on an analysis's result · f6e9986a
      Chandler Carruth authored
      type and detect whether or not it provides an 'invalidate' member the
      analysis manager should use.
      
      This lets the overwhelming common case of *not* caring about custom
      behavior when an analysis is invalidated be the the obvious default
      behavior with no code written by the author of an analysis. Only when
      they write code specifically to handle invalidation does it get used.
      
      Both cases are actually covered by tests here. The test analysis uses
      the default behavior, and the proxy module analysis actually has custom
      behavior on invalidation that is firing correctly. (In fact, this is the
      analysis which was the primary motivation for having custom invalidation
      behavior in the first place.)
      
      llvm-svn: 195332
      f6e9986a
    • Chandler Carruth's avatar
      [PM] Add a module analysis pass proxy for the function analysis manager. · 851a2aa0
      Chandler Carruth authored
      This proxy will fill the role of proxying invalidation events down IR
      unit layers so that when a module changes we correctly invalidate
      function analyses. Currently this is a very coarse solution -- any
      change blows away the entire thing -- but the next step is to make
      invalidation handling more nuanced so that we can propagate specific
      amounts of invalidation from one layer to the next.
      
      The test is extended to place a module pass between two function pass
      managers each of which have preserved function analyses which get
      correctly invalidated by the module pass that might have changed what
      functions are even in the module.
      
      llvm-svn: 195304
      851a2aa0
    • Nick Kledzik's avatar
      YAML I/O add support for validate() · 7cd45f29
      Nick Kledzik authored
      MappingTrait template specializations can now have a validate() method which 
      performs semantic checking. For details, see <http://llvm.org/docs/YamlIO.html>.
      
      llvm-svn: 195286
      7cd45f29
    • Nick Kledzik's avatar
      revert r194655 · 4761c60e
      Nick Kledzik authored
      llvm-svn: 195285
      4761c60e
  4. Nov 20, 2013
    • Chandler Carruth's avatar
      Make the moved-from SmallPtrSet be a valid, empty, small-state object. · c74010df
      Chandler Carruth authored
      Enhance the tests to actually require moves in C++11 mode, in addition
      to testing the moved-from state. Further enhance the tests to cover
      copy-assignment into a moved-from object and moving a large-state
      object. (Note that we can't really test small-state vs. large-state as
      that isn't an observable property of the API really.) This should finish
      addressing review on r195239.
      
      llvm-svn: 195261
      c74010df
    • Chandler Carruth's avatar
      Add a test for assignment operator behavior which was changed in · 6d888bc0
      Chandler Carruth authored
      r195239, as well as a comment about the fact that assigning over
      a moved-from object was in fact tested. Addresses some of the review
      feedback on r195239.
      
      llvm-svn: 195260
      6d888bc0
    • Chandler Carruth's avatar
      [PM] Add the preservation system to the new pass manager. · c0bfa8c2
      Chandler Carruth authored
      This adds a new set-like type which represents a set of preserved
      analysis passes. The set is managed via the opaque PassT::ID() void*s.
      The expected convenience templates for interacting with specific passes
      are provided. It also supports a symbolic "all" state which is
      represented by an invalid pointer in the set. This state is nicely
      saturating as it comes up often. Finally, it supports intersection which
      is used when finding the set of preserved passes after N different
      transforms.
      
      The pass API is then changed to return the preserved set rather than
      a bool. This is much more self-documenting than the previous system.
      Returning "none" is a conservatively correct solution just like
      returning "true" from todays passes and not marking any passes as
      preserved. Passes can also be dynamically preserved or not throughout
      the run of the pass, and whatever gets returned is the binding state.
      Finally, preserving "all" the passes is allowed for no-op transforms
      that simply can't harm such things.
      
      Finally, the analysis managers are changed to instead of blindly
      invalidating all of the analyses, invalidate those which were not
      preserved. This should rig up all of the basic preservation
      functionality. This also correctly combines the preservation moving up
      from one IR-layer to the another and the preservation aggregation across
      N pass runs. Still to go is incrementally correct invalidation and
      preservation across IR layers incrementally during N pass runs. That
      will wait until we have a device for even exposing analyses across IR
      layers.
      
      While the core of this change is obvious, I'm not happy with the current
      testing, so will improve it to cover at least some of the invalidation
      that I can test easily in a subsequent commit.
      
      llvm-svn: 195241
      c0bfa8c2
    • Chandler Carruth's avatar
      Give SmallPtrSet move semantics when we have R-value references. · 55758e96
      Chandler Carruth authored
      Somehow, this ADT got missed which is moderately terrifying considering
      the efficiency of move for it.
      
      The code to implement move semantics for it is pretty horrible
      currently but was written to reasonably closely match the rest of the
      code. Unittests that cover both copying and moving (at a basic level)
      added.
      
      llvm-svn: 195239
      55758e96
    • Chandler Carruth's avatar
      [PM] Make the function pass manager more regular. · d895e29e
      Chandler Carruth authored
      The FunctionPassManager is now itself a function pass. When run over
      a function, it runs all N of its passes over that function. This is the
      1:N mapping in the pass dimension only. This allows it to be used in
      either a ModulePassManager or potentially some other manager that
      works on IR units which are supersets of Functions.
      
      This commit also adds the obvious adaptor to map from a module pass to
      a function pass, running the function pass across every function in the
      module.
      
      The test has been updated to use this new pattern.
      
      llvm-svn: 195192
      d895e29e
    • Chandler Carruth's avatar
      [PM] Split the analysis manager into a function-specific interface and · ed1ffe01
      Chandler Carruth authored
      a module-specific interface. This is the first of many steps necessary
      to generalize the infrastructure such that we can support both
      a Module-to-Function and Module-to-SCC-to-Function pass manager
      nestings.
      
      After a *lot* of attempts that never worked and didn't even make it to
      a committable state, it became clear that I had gotten the layering
      design of analyses flat out wrong. Four days later, I think I have most
      of the plan for how to correct this, and I'm starting to reshape the
      code into it. This is just a baby step I'm afraid, but starts separating
      the fundamentally distinct concepts of function analysis passes and
      module analysis passes so that in subsequent steps we can effectively
      layer them, and have a consistent design for the eventual SCC layer.
      
      As part of this, I've started some interface changes to make passes more
      regular. The module pass accepts the module in the run method, and some
      of the constructor parameters are gone. I'm still working out exactly
      where constructor parameters vs. method parameters will be used, so
      I expect this to fluctuate a bit.
      
      This actually makes the invalidation less "correct" at this phase,
      because now function passes don't invalidate module analysis passes, but
      that was actually somewhat of a misfeature. It will return in a better
      factored form which can scale to other units of IR. The documentation
      has gotten less verbose and helpful.
      
      llvm-svn: 195189
      ed1ffe01
  5. Nov 19, 2013
  6. Nov 18, 2013
  7. Nov 17, 2013
    • Michael Gottesman's avatar
      [block-freq] Add BlockFrequency::scale that returns a remainder from the... · 4d078a3d
      Michael Gottesman authored
      [block-freq] Add BlockFrequency::scale that returns a remainder from the division and make the private scale in BlockFrequency more performant.
      
      This change is the first in a series of changes improving LLVM's Block
      Frequency propogation implementation to not lose probability mass in
      branchy code when propogating block frequency information from a basic
      block to its successors. This patch is a simple infrastructure
      improvement that does not actually modify the block frequency
      algorithm. The specific changes are:
      
      1. Changes the division algorithm used when scaling block frequencies by
      branch probabilities to a short division algorithm. This gives us the
      remainder for free as well as provides a nice speed boost. When I
      benched the old routine and the new routine on a Sandy Bridge iMac with
      disabled turbo mode performing 8192 iterations on an array of length
      32768, I saw ~600% increase in speed in mean/median performance.
      
      2. Exposes a scale method that returns a remainder. This is important so
      we can ensure that when we scale a block frequency by some branch
      probability BP = N/D, the remainder from the division by D can be
      retrieved and propagated to other children to ensure no probability mass
      is lost (more to come on this).
      
      llvm-svn: 194950
      4d078a3d
    • Chandler Carruth's avatar
      [PM] Completely remove support for explicit 'require' methods on the · a8df4760
      Chandler Carruth authored
      AnalysisManager. All this method did was assert something and we have
      a perfectly good way to trigger that assert from the query path.
      
      llvm-svn: 194947
      a8df4760
  8. Nov 15, 2013
  9. Nov 14, 2013
  10. Nov 13, 2013
    • Rui Ueyama's avatar
      Path: Add tests for existing file magics. · 5e3de7a7
      Rui Ueyama authored
      llvm-svn: 194607
      5e3de7a7
    • Rui Ueyama's avatar
      Whitespace. · 89d1bdb6
      Rui Ueyama authored
      llvm-svn: 194605
      89d1bdb6
    • Chandler Carruth's avatar
      Fix a null pointer dereference when copying a null polymorphic pointer. · ccb19097
      Chandler Carruth authored
      This bug only bit the C++98 build bots because all of the actual uses
      really do move. ;] But not *quite* ready to do the whole C++11 switch
      yet, so clean it up. Also add a unit test that catches this immediately.
      
      llvm-svn: 194548
      ccb19097
    • Chandler Carruth's avatar
      Introduce an AnalysisManager which is like a pass manager but with a lot · 74015a70
      Chandler Carruth authored
      more smarts in it. This is where most of the interesting logic that used
      to live in the implicit-scheduling-hackery of the old pass manager will
      live.
      
      Like the previous commits, note that this is a very early prototype!
      I expect substantial changes before this is ready to use.
      
      The core of the design is the following:
      
      - We have an AnalysisManager which can be used across a series of
        passes over a module.
      - The code setting up a pass pipeline registers the analyses available
        with the manager.
      - Individual transform passes can check than an analysis manager
        provides the analyses they require in order to fail-fast.
      - There is *no* implicit registration or scheduling.
      - Analysis passes are different from other passes: they produce an
        analysis result that is cached and made available via the analysis
        manager.
      - Cached results are invalidated automatically by the pass managers.
      - When a transform pass requests an analysis result, either the analysis
        is run to produce the result or a cached result is provided.
      
      There are a few aspects of this design that I *know* will change in
      subsequent commits:
      - Currently there is no "preservation" system, that needs to be added.
      - All of the analysis management should move up to the analysis library.
      - The analysis management needs to support at least SCC passes. Maybe
        loop passes. Living in the analysis library will facilitate this.
      - Need support for analyses which are *both* module and function passes.
      - Need support for pro-actively running module analyses to have cached
        results within a function pass manager.
      - Need a clear design for "immutable" passes.
      - Need support for requesting cached results when available and not
        re-running the pass even if that would be necessary.
      - Need more thorough testing of all of this infrastructure.
      
      There are other aspects that I view as open questions I'm hoping to
      resolve as I iterate a bit on the infrastructure, and especially as
      I start writing actual passes against this.
      - Should we have separate management layers for function, module, and
        SCC analyses? I think "yes", but I'm not yet ready to switch the code.
        Adding SCC support will likely resolve this definitively.
      - How should the 'require' functionality work? Should *that* be the only
        way to request results to ensure that passes always require things?
      - How should preservation work?
      - Probably some other things I'm forgetting. =]
      
      Look forward to more patches in shorter order now that this is in place.
      
      llvm-svn: 194538
      74015a70
  11. Nov 09, 2013
    • Chandler Carruth's avatar
      [PM] Start sketching out the new module and function pass manager. · 90a835d2
      Chandler Carruth authored
      This is still just a skeleton. I'm trying to pull together the
      experimentation I've done into committable chunks, and this is the first
      coherent one. Others will follow in hopefully short order that move this
      more toward a useful initial implementation. I still expect the design
      to continue evolving in small ways as I work through the different
      requirements and features needed here though.
      
      Keep in mind, all of this is off by default.
      
      Currently, this mostly exercises the use of a polymorphic smart pointer
      and templates to hide the polymorphism for the pass manager from the
      pass implementation. The next step will be more significant, adding the
      first framework of analysis support.
      
      llvm-svn: 194325
      90a835d2
Loading