1. 16 Oct, 2019 1 commit
    • Andreas Klebinger's avatar
      Add loop level analysis to the NCG backend. · 535a88e1
      Andreas Klebinger authored
      For backends maintaining the CFG during codegen
      we can now find loops and their nesting level.
      
      This is based on the Cmm CFG and dominator analysis.
      
      As a result we can estimate edge frequencies a lot better
      for methods, resulting in far better code layout.
      
      Speedup on nofib: ~1.5%
      Increase in compile times: ~1.9%
      
      To make this feasible this commit adds:
      * Dominator analysis based on the Lengauer-Tarjan Algorithm.
      * An algorithm estimating global edge frequences from branch
      probabilities - In CFG.hs
      
      A few static branch prediction heuristics:
      
      * Expect to take the backedge in loops.
      * Expect to take the branch NOT exiting a loop.
      * Expect integer vs constant comparisons to be false.
      
      We also treat heap/stack checks special for branch prediction
      to avoid them being treated as loops.
      535a88e1
  2. 13 Oct, 2019 1 commit
    • Andreas Klebinger's avatar
      Fix #17334 where NCG did not properly update the CFG. · c1bd07cd
      Andreas Klebinger authored
      Statements can change the basic block in which instructions
      are placed during instruction selection.
      
      We have to keep track of this switch of the current basic block
      as we need this information in order to properly update the CFG.
      
      This commit implements this change and fixes #17334.
      
      We do so by having stmtToInstr return the new block id
      if a statement changed the basic block.
      c1bd07cd
  3. 05 Sep, 2019 1 commit
  4. 27 Aug, 2019 1 commit
  5. 15 Aug, 2019 1 commit
    • James Foster's avatar
      Remove unused imports of the form 'import foo ()' (Fixes #17065) · ca71d551
      James Foster authored
      These kinds of imports are necessary in some cases such as
      importing instances of typeclasses or intentionally creating
      dependencies in the build system, but '-Wunused-imports' can't
      detect when they are no longer needed. This commit removes the
      unused ones currently in the code base (not including test files
      or submodules), with the hope that doing so may increase
      parallelism in the build system by removing unnecessary
      dependencies.
      ca71d551
  6. 25 Mar, 2019 1 commit
    • Takenobu Tani's avatar
      Update Wiki URLs to point to GitLab · 3769e3a8
      Takenobu Tani authored
      This moves all URL references to Trac Wiki to their corresponding
      GitLab counterparts.
      
      This substitution is classified as follows:
      
      1. Automated substitution using sed with Ben's mapping rule [1]
          Old: ghc.haskell.org/trac/ghc/wiki/XxxYyy...
          New: gitlab.haskell.org/ghc/ghc/wikis/xxx-yyy...
      
      2. Manual substitution for URLs containing `#` index
          Old: ghc.haskell.org/trac/ghc/wiki/XxxYyy...#Zzz
          New: gitlab.haskell.org/ghc/ghc/wikis/xxx-yyy...#zzz
      
      3. Manual substitution for strings starting with `Commentary`
          Old: Commentary/XxxYyy...
          New: commentary/xxx-yyy...
      
      See also !539
      
      [1]: https://gitlab.haskell.org/bgamari/gitlab-migration/blob/master/wiki-mapping.json
      3769e3a8
  7. 31 Jan, 2019 2 commits
  8. 17 Nov, 2018 1 commit
    • Andreas Klebinger's avatar
      NCG: New code layout algorithm. · 912fd2b6
      Andreas Klebinger authored
      Summary:
      This patch implements a new code layout algorithm.
      It has been tested for x86 and is disabled on other platforms.
      
      Performance varies slightly be CPU/Machine but in general seems to be better
      by around 2%.
      Nofib shows only small differences of about +/- ~0.5% overall depending on
      flags/machine performance in other benchmarks improved significantly.
      
      Other benchmarks includes at least the benchmarks of: aeson, vector, megaparsec, attoparsec,
      containers, text and xeno.
      
      While the magnitude of gains differed three different CPUs where tested with
      all getting faster although to differing degrees. I tested: Sandy Bridge(Xeon), Haswell,
      Skylake
      
      * Library benchmark results summarized:
        * containers: ~1.5% faster
        * aeson: ~2% faster
        * megaparsec: ~2-5% faster
        * xml library benchmarks: 0.2%-1.1% faster
        * vector-benchmarks: 1-4% faster
        * text: 5.5% faster
      
      On average GHC compile times go down, as GHC compiled with the new layout
      is faster than the overhead introduced by using the new layout algorithm,
      
      Things this patch does:
      
      * Move code responsilbe for block layout in it's own module.
      * Move the NcgImpl Class into the NCGMonad module.
      * Extract a control flow graph from the input cmm.
      * Update this cfg to keep it in sync with changes during
        asm codegen. This has been tested on x64 but should work on x86.
        Other platforms still use the old codelayout.
      * Assign weights to the edges in the CFG based on type and limited static
        analysis which are then used for block layout.
      * Once we have the final code layout eliminate some redundant jumps.
      
        In particular turn a sequences of:
            jne .foo
            jmp .bar
          foo:
        into
            je bar
          foo:
            ..
      
      Test Plan: ci
      
      Reviewers: bgamari, jmct, jrtc27, simonmar, simonpj, RyanGlScott
      
      Reviewed By: RyanGlScott
      
      Subscribers: RyanGlScott, trommler, jmct, carter, thomie, rwbarton
      
      GHC Trac Issues: #15124
      
      Differential Revision: https://phabricator.haskell.org/D4726
      912fd2b6