Skip to content
  1. Dec 10, 2013
  2. Dec 05, 2013
  3. Dec 02, 2013
    • Diego Novillo's avatar
      Fix dominator descendants for unreachable blocks. · ee592429
      Diego Novillo authored
      When a block is unreachable, asking its dom tree descendants should
      return the empty set. However, the computation of the descendants
      was causing a segmentation fault because the dom tree node we get
      from the basic block is initially NULL.
      
      Fixed by adding a test for a valid dom tree node before we iterate.
      
      The patch also adds some unit tests to the existing dom tree tests.
      
      llvm-svn: 196099
      ee592429
  4. Nov 26, 2013
    • Chandler Carruth's avatar
      [PM] Split the CallGraph out from the ModulePass which creates the · 6378cf53
      Chandler Carruth authored
      CallGraph.
      
      This makes the CallGraph a totally generic analysis object that is the
      container for the graph data structure and the primary interface for
      querying and manipulating it. The pass logic is separated into its own
      class. For compatibility reasons, the pass provides wrapper methods for
      most of the methods on CallGraph -- they all just forward.
      
      This will allow the new pass manager infrastructure to provide its own
      analysis pass that constructs the same CallGraph object and makes it
      available. The idea is that in the new pass manager, the analysis pass's
      'run' method returns a concrete analysis 'result'. Here, that result is
      a 'CallGraph'. The 'run' method will typically do only minimal work,
      deferring much of the work into the implementation of the result object
      in order to be lazy about computing things, but when (like DomTree)
      there is *some* up-front computation, the analysis does it prior to
      handing the result back to the querying pass.
      
      I know some of this is fairly ugly. I'm happy to change it around if
      folks can suggest a cleaner interim state, but there is going to be some
      amount of unavoidable ugliness during the transition period. The good
      thing is that this is very limited and will naturally go away when the
      old pass infrastructure goes away. It won't hang around to bother us
      later.
      
      Next up is the initial new-PM-style call graph analysis. =]
      
      llvm-svn: 195722
      6378cf53
  5. Nov 23, 2013
    • Chandler Carruth's avatar
      [PM] Complete the cross-layer interfaces with a Module-to-Function · c1ff9ed6
      Chandler Carruth authored
      proxy. This lets a function pass query a module analysis manager.
      However, the interface is const to indicate that only cached results can
      be safely queried.
      
      With this, I think the new pass manager is largely functionally complete
      for modules and analyses. Still lots to test, and need to generalize to
      SCCs and Loops, and need to build an adaptor layer to support the use of
      existing Pass objects in the new managers.
      
      llvm-svn: 195538
      c1ff9ed6
    • 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
  6. 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
    • 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
  7. 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
  8. Nov 20, 2013
    • 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
      [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
  9. Nov 17, 2013
  10. Nov 15, 2013
  11. Nov 13, 2013
    • 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
  12. 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
    • Chandler Carruth's avatar
      Move the old pass manager infrastructure into a legacy namespace and · 7caea415
      Chandler Carruth authored
      give the files a legacy prefix in the right directory. Use forwarding
      headers in the old locations to paper over the name change for most
      clients during the transitional period.
      
      No functionality changed here! This is just clearing some space to
      reduce renaming churn later on with a new system.
      
      Even when the new stuff starts to go in, it is going to be hidden behind
      a flag and off-by-default as it is still WIP and under development.
      
      This patch is specifically designed so that very little out-of-tree code
      has to change. I'm going to work as hard as I can to keep that the case.
      Only direct forward declarations of the PassManager class are impacted
      by this change.
      
      llvm-svn: 194324
      7caea415
  13. Oct 31, 2013
  14. Oct 30, 2013
    • Rafael Espindola's avatar
      Add calls to doInitialization() and doFinalization() in verifyFunction() · 55fdcff4
      Rafael Espindola authored
      The function verifyFunction() in lib/IR/Verifier.cpp misses some
      calls. It creates a temporary FunctionPassManager that will run a
      single Verifier pass. Unfortunately, FunctionPassManager is no
      PassManager and does not call doInitialization() and doFinalization()
      by itself. Verifier does important tasks in doInitialization() such as
      collecting type information used to check DebugInfo metadata and
      doFinalization() does some additional checks. Therefore these checks
      were missed and debug info couldn't be verified at all, it just
      crashed if the function had some.
      
      verifyFunction() is currently not used in llvm unless -debug option is
      enabled, and in unittests/IR/VerifierTest.cpp
      
      VerifierTest had to be changed to create the function in a module from
      which the type debug info can be collected.
      
      Patch by Michael Kruse.
      
      llvm-svn: 193719
      55fdcff4
  15. Oct 05, 2013
  16. Sep 30, 2013
  17. Sep 09, 2013
    • Bob Wilson's avatar
      Revert patches to add case-range support for PR1255. · e407736a
      Bob Wilson authored
      The work on this project was left in an unfinished and inconsistent state.
      Hopefully someone will eventually get a chance to implement this feature, but
      in the meantime, it is better to put things back the way the were.  I have
      left support in the bitcode reader to handle the case-range bitcode format,
      so that we do not lose bitcode compatibility with the llvm 3.3 release.
      
      This reverts the following commits: 155464, 156374, 156377, 156613, 156704,
      156757, 156804 156808, 156985, 157046, 157112, 157183, 157315, 157384, 157575,
      157576, 157586, 157612, 157810, 157814, 157815, 157880, 157881, 157882, 157884,
      157887, 157901, 158979, 157987, 157989, 158986, 158997, 159076, 159101, 159100,
      159200, 159201, 159207, 159527, 159532, 159540, 159583, 159618, 159658, 159659,
      159660, 159661, 159703, 159704, 160076, 167356, 172025, 186736
      
      llvm-svn: 190328
      e407736a
  18. Aug 03, 2013
  19. Jul 31, 2013
  20. Jul 30, 2013
  21. Jun 29, 2013
  22. Jun 19, 2013
  23. May 05, 2013
    • Arnold Schwaighofer's avatar
      Add missing PatternMatch.cpp to CMakeLists.txt · eb4f2d63
      Arnold Schwaighofer authored
      llvm-svn: 181147
      eb4f2d63
    • Arnold Schwaighofer's avatar
      PatternMatch: Matcher for (un)ordered floating point min/max · e972d03f
      Arnold Schwaighofer authored
      Add support for matching 'ordered' and 'unordered' floating point min/max
      constructs.
      
      In LLVM we can express min/max functions as a combination of compare and select.
      We have support for matching such constructs for integers but not for floating
      point. In floating point math there is no total order because of the presence of
      'NaN'. Therefore, we have to be careful to preserve the original fcmp semantics
      when interpreting floating point compare select combinations as a minimum or
      maximum function. The resulting 'ordered/unordered' floating point maximum
      function has to select the same value as the select/fcmp combination it is based
      on.
      
       ordered_max(x,y)   = max(x,y) iff x and y are not NaN, y otherwise
       unordered_max(x,y) = max(x,y) iff x and y are not NaN, x otherwise
       ordered_min(x,y)   = min(x,y) iff x and y are not NaN, y otherwise
       unordered_min(x,y) = min(x,y) iff x and y are not NaN, x otherwise
      
      This matches the behavior of the underlying select(fcmp(olt/ult/.., L, R), L, R)
      construct.
      
      Any code using this predicate has to preserve this semantics.
      
      A follow-up patch will use this to implement floating point min/max reductions
      in the vectorizer.
      
      radar://13723044
      
      llvm-svn: 181143
      e972d03f
Loading