1. 23 Oct, 2019 6 commits
    • Andreas Klebinger's avatar
      Make dynflag argument for withTiming pure. · 6beea836
      Andreas Klebinger authored
      19 times out of 20 we already have dynflags in scope.
      
      We could just always use `return dflags`. But this is in fact not free.
      When looking at some STG code I noticed that we always allocate a
      closure for this expression in the heap. Clearly a waste in these cases.
      
      For the other cases we can either just modify the callsite to
      get dynflags or use the _D variants of withTiming I added which
      will use getDynFlags under the hood.
      6beea836
    • Andreas Klebinger's avatar
      Fix bug in the x86 backend involving the CFG. · aa778152
      Andreas Klebinger authored
      This is part two of fixing #17334.
      
      There are two parts to this commit:
      
      - A bugfix for computing loop levels
      - A bugfix of basic block invariants in the NCG.
      
      -----------------------------------------------------------
      
      In the first bug we ended up with a CFG of the sort: [A -> B -> C]
      This was represented via maps as fromList [(A,B),(B,C)] and later
      transformed into a adjacency array. However the transformation did
      not include block C in the array (since we only looked at the keys of
      the map).
      
      This was still fine until we tried to look up successors for C and tried
      to read outside of the array bounds when accessing C.
      
      In order to prevent this in the future I refactored to code to include
      all nodes as keys in the map representation. And make this a invariant
      which is checked in a few places.
      
      Overall I expect this to make the code more robust as now any failed
      lookup will represent an error, versus failed lookups sometimes being
      expected and sometimes not.
      
      In terms of performance this makes some things cheaper (getting a list
      of all nodes) and others more expensive (adding a new edge). Overall
      this adds up to no noteable performance difference.
      
      -----------------------------------------------------------
      
      Part 2: When the NCG generated a new basic block, it did
      not always insert a NEWBLOCK meta instruction in the stream which
      caused a quite subtle bug.
      
          During instruction selection a statement `s`
          in a block B with control of the sort: B -> C
          will sometimes result in control
          flow of the sort:
      
                  ┌ < ┐
                  v   ^
            B ->  B1  ┴ -> C
      
          as is the case for some atomic operations.
      
          Now to keep the CFG in sync when introducing B1 we clearly
          want to insert it between B and C. However there is
          a catch when we have to deal with self loops.
      
          We might start with code and a CFG of these forms:
      
          loop:
              stmt1               ┌ < ┐
              ....                v   ^
              stmtX              loop ┘
              stmtY
              ....
              goto loop:
      
          Now we introduce B1:
                                  ┌ ─ ─ ─ ─ ─┐
              loop:               │   ┌ <  ┐ │
              instrs              v   │    │ ^
              ....               loop ┴ B1 ┴ ┘
              instrsFromX
              stmtY
              goto loop:
      
          This is simple, all outgoing edges from loop now simply
          start from B1 instead and the code generator knows which
          new edges it introduced for the self loop of B1.
      
          Disaster strikes if the statement Y follows the same pattern.
          If we apply the same rule that all outgoing edges change then
          we end up with:
      
              loop ─> B1 ─> B2 ┬─┐
                │      │    └─<┤ │
                │      └───<───┘ │
                └───────<────────┘
      
          This is problematic. The edge B1->B1 is modified as expected.
          However the modification is wrong!
      
          The assembly in this case looked like this:
      
          _loop:
              <instrs>
          _B1:
              ...
              cmpxchgq ...
              jne _B1
              <instrs>
              <end _B1>
          _B2:
              ...
              cmpxchgq ...
              jne _B2
              <instrs>
              jmp loop
      
          There is no edge _B2 -> _B1 here. It's still a self loop onto _B1.
      
          The problem here is that really B1 should be two basic blocks.
          Otherwise we have control flow in the *middle* of a basic block.
          A contradiction!
      
          So to account for this we add yet another basic block marker:
      
          _B:
              <instrs>
          _B1:
              ...
              cmpxchgq ...
              jne _B1
              jmp _B1'
          _B1':
              <instrs>
              <end _B1>
          _B2:
              ...
      
          Now when inserting B2 we will only look at the outgoing edges of B1' and
          everything will work out nicely.
      
          You might also wonder why we don't insert jumps at the end of _B1'. There is
          no way another block ends up jumping to the labels _B1 or _B2 since they are
          essentially invisible to other blocks. View them as control flow labels local
          to the basic block if you'd like.
      
          Not doing this ultimately caused (part 2 of) #17334.
      aa778152
    • Ryan Scott's avatar
      Reify oversaturated data family instances correctly (#17296) · a19c7d17
      Ryan Scott authored
      `TcSplice` was not properly handling oversaturated data family
      instances, such as the example in #17296, as it dropped arguments due
      to carelessly zipping data family instance arguments with
      `tyConTyVars`. For data families, the number of `tyConTyVars` can
      sometimes be less than the number of arguments it can accept in a
      data family instance due to the fact that data family instances can
      be oversaturated.
      
      To account for this, `TcSplice.mkIsPolyTvs` has now been renamed to
      `tyConArgsPolyKinded` and now factors in `tyConResKind` in addition
      to `tyConTyVars`. I've also added
      `Note [Reified instances and explicit kind signatures]` which
      explains the various subtleties in play here.
      
      Fixes #17296.
      a19c7d17
    • Alp Mestanogullari's avatar
      compiler: introduce DynFlags plugins · 900cf195
      Alp Mestanogullari authored
      They have type '[CommandLineOpts] -> Maybe (DynFlags -> IO DynFlags)'.
      All plugins that supply a non-Nothing 'dynflagsPlugin' will see their
      updates applied to the current DynFlags right after the plugins are
      loaded.
      
      One use case for this is to superseede !1580 for registering hooks
      from a plugin. Frontend/parser plugins were considered to achieve this
      but they respectively conflict with how this plugin is going to be used
      and don't allow overriding/modifying the DynFlags, which is how hooks have
      to be registered.
      
      This commit comes with a test, 'test-hook-plugin', that registers a "fake"
      meta hook that replaces TH expressions with the 0 integer literal.
      900cf195
    • Richard Eisenberg's avatar
      Implement a coverage checker for injectivity · 1cd3fa29
      Richard Eisenberg authored
      This fixes #16512.
      
      There are lots of parts of this patch:
      
      * The main payload is in FamInst. See
      Note [Coverage condition for injective type families] there
      for the overview. But it doesn't fix the bug.
      
      * We now bump the reduction depth every time we discharge
      a CFunEqCan. See Note [Flatten when discharging CFunEqCan]
      in TcInteract.
      
      * Exploration of this revealed a new, easy to maintain invariant
      for CTyEqCans. See Note [Almost function-free] in TcRnTypes.
      
      * We also realized that type inference for injectivity was a
      bit incomplete. This means we exchanged lookupFlattenTyVar for
      rewriteTyVar. See Note [rewriteTyVar] in TcFlatten. The new
      function is monadic while the previous one was pure, necessitating
      some faff in TcInteract. Nothing too bad.
      
      * zonkCt did not maintain invariants on CTyEqCan. It's not worth
      the bother doing so, so we just transmute CTyEqCans to
      CNonCanonicals.
      
      * The pure unifier was finding the fixpoint of the returned
      substitution, even when doing one-way matching (in tcUnifyTysWithTFs).
      Fixed now.
      
      Test cases: typecheck/should_fail/T16512{a,b}
      1cd3fa29
    • Andreas Klebinger's avatar
      Warn about missing profiled libs when using the Interpreter. · faa30dcb
      Andreas Klebinger authored
      When GHC itself, or it's interpreter is profiled we need to load
      profiled libraries as well.
      
      This requirement is not always obvious, especially when TH
      implicilty uses the interpreter.
      
      When the libs were not found we fall back to assuming the
      are in a DLL. This is usually not the case so now we warn
      users when we do so. This makes it more obvious what is
      happening and gives users a way to fix the issue.
      
      This fixes #17121.
      faa30dcb
  2. 22 Oct, 2019 1 commit
    • Stefan Schulze Frielinghaus's avatar
      Implement s390x LLVM backend. · fd8b666a
      Stefan Schulze Frielinghaus authored
      This patch adds support for the s390x architecture for the LLVM code
      generator. The patch includes a register mapping of STG registers onto
      s390x machine registers which enables a registerised build.
      fd8b666a
  3. 20 Oct, 2019 1 commit
  4. 17 Oct, 2019 1 commit
  5. 16 Oct, 2019 4 commits
    • Ryan Scott's avatar
      Make Coverage.TM a newtype · deb96399
      Ryan Scott authored
      deb96399
    • Richard Eisenberg's avatar
      Break up TcRnTypes, among other modules. · 51fad9e6
      Richard Eisenberg authored
      This introduces three new modules:
      
       - basicTypes/Predicate.hs describes predicates, moving
         this logic out of Type. Predicates don't really exist
         in Core, and so don't belong in Type.
      
       - typecheck/TcOrigin.hs describes the origin of constraints
         and types. It was easy to remove from other modules and
         can often be imported instead of other, scarier modules.
      
       - typecheck/Constraint.hs describes constraints as used in
         the solver. It is taken from TcRnTypes.
      
      No work other than module splitting is in this patch.
      
      This is the first step toward homogeneous equality, which will
      rely more strongly on predicates. And homogeneous equality is the
      next step toward a dependently typed core language.
      51fad9e6
    • Sebastian Graf's avatar
      Infer rho-types instead of sigma-types in guard BindStmts and TransStmts · 6ede3554
      Sebastian Graf authored
      In #17343 we saw that we didn't handle the pattern guard `!_ <-
      undefined` correctly: The `undefined` was never evaluated. Indeed,
      elaboration failed to insert the invisible type aruments to `undefined`.
      So `undefined` was trivially a normal-form and in turn never entered.
      
      The problem is that we used to infer a sigma-type for the RHS of the
      guard, the leading qualifiers of which will never be useful in a pattern
      match situation. Hence we infer a rho-type now.
      
      Fixes #17343.
      6ede3554
    • 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
  6. 15 Oct, 2019 3 commits
    • Alp Mestanogullari's avatar
      a55b8a65
    • Ryan Scott's avatar
      Don't skip validity checks for built-in classes (#17355) · 426b0ddc
      Ryan Scott authored
      Issue #17355 occurred because the control flow for
      `TcValidity.check_valid_inst_head` was structured in such a way that
      whenever it checked a special, built-in class (like `Generic` or
      `HasField`), it would skip the most important check of all:
      `checkValidTypePats`, which rejects nonsense like this:
      
      ```hs
      instance Generic (forall a. a)
      ```
      
      This fixes the issue by carving out `checkValidTypePats` from
      `check_valid_inst_head` so that `checkValidTypePats` is always
      invoked. `check_valid_inst_head` has also been renamed to
      `check_special_inst_head` to reflect its new purpose of _only_
      checking for instances headed by special classes.
      
      Fixes #17355.
      426b0ddc
    • Ryan Scott's avatar
      Refactor some cruft in TcDerivInfer.inferConstraints · a2d3594c
      Ryan Scott authored
      The latest installment in my quest to clean up the code in
      `TcDeriv*`. This time, my sights are set on
      `TcDerivInfer.inferConstraints`, which infers the context for derived
      instances. This function is a wee bit awkward at the moment:
      
      * It's not terribly obvious from a quick glance, but
        `inferConstraints` is only ever invoked when using the `stock` or
        `anyclass` deriving strategies, as the code for inferring the
        context for `newtype`- or `via`-derived instances is located
        separately in `mk_coerce_based_eqn`. But there's no good reason
        for things to be this way, so I moved this code from
        `mk_coerce_based_eqn` to `inferConstraints` so that everything
        related to inferring instance contexts is located in one place.
      * In this process, I discovered that the Haddocks for the auxiliary
        function `inferConstraintsDataConArgs` are completely wrong. It
        claims that it handles both `stock` and `newtype` deriving, but
        this is completely wrong, as discussed above—it only handles
        `stock`. To rectify this, I renamed this function to
        `inferConstraintsStock` to reflect its actual purpose and created
        a new `inferConstraintsCoerceBased` function to specifically
        handle `newtype` (and `via`) deriving.
      
      Doing this revealed some opportunities for further simplification:
      
      * Removing the context-inference–related code from
        `mk_coerce_based_eqn` made me realize that the overall structure
        of the function is basically identical to `mk_originative_eqn`.
        In fact, I was easily able to combine the two functions into a
        single `mk_eqn_from_mechanism` function.
      
        As part of this merger, I now invoke
        `atf_coerce_based_error_checks` from `doDerivInstErrorChecks1`.
      * I discovered that GHC defined this function:
      
        ```hs
        typeToTypeKind = liftedTypeKind `mkVisFunTy` liftedTypeKind
        ```
      
        No fewer than four times in different modules. I consolidated all
        of these definitions in a single location in `TysWiredIn`.
      a2d3594c
  7. 13 Oct, 2019 2 commits
  8. 12 Oct, 2019 4 commits
    • Simon Peyton Jones's avatar
      Do not add a 'solved dict' for quantified constraints · 226d86d2
      Simon Peyton Jones authored
      GHC has a wonderful-but-delicate mechanism for building recursive
      dictionaries by adding a goal to the "solved dictionaries" before
      solving the sub-goals.  See Note [Solved dictionaries] in TcSMonad
      
      Ticket #17267 showed that if you use this mechanism for local
      /quantified/ constraints you can get a loop -- or even unsafe
      coerce.   This patch fixes the bug.
      
      Specifically
      
      * Make TcSMonad.addSolvedDict be conditional on using a
        /top level/ instance, not a quantified one.
      
      * Moreover, we /also/ don't want to add a solved dict
        for equalities (a~b).
      
      * Add lots more comments to Note [Solved dictionaries]
        to explain the above cryptic stuff.
      
      * Extend InstanceWhat to identify those strange built-in
        equality instances.
      
      A couple of other things along the way
      
      * Delete the unused Type.isIPPred_maybe.
      
      * Stop making addSolvedDict conditional on not being an
        impolicit parameter.  This comes from way back. But
        it's irrelevant now because IP dicts are never solved
        via an instance.
      226d86d2
    • Simon Peyton Jones's avatar
      Fix validity checking for inferred types · c50e4c92
      Simon Peyton Jones authored
      GHC is suposed to uphold the principle that an /inferred/ type
      for a let-binding should obey the rules for that module.  E.g.
      we should only accept an inferred higher rank type if we have
      RankNTypes on.
      
      But we were failing to check this: TcValidity.checkValidType
      allowed arbitrary rank for inferred types.
      
      This patch fixes the bug.  It might in principle cause some breakage,
      but if so that's good: the user should add RankNTypes and/or a
      manual signature.  (And almost every package has explicit user
      signatures for all top-level things anyway.)  Let's see.
      
      Fixes #17213.
      
      Metric Decrease:
          T10370
      c50e4c92
    • Ryan Scott's avatar
      Use newDFunName for both manual and derived instances (#17339) · 0a338264
      Ryan Scott authored
      Issue #17339 was caused by using a slightly different version of
      `newDFunName` for derived instances that, confusingly enough, did not
      take all arguments to the class into account when generating the
      `DFun` name. I cannot think of any good reason for doing this, so
      this patch uses `newDFunName` uniformly for both derived instances
      and manually written instances alike.
      
      Fixes #17339.
      0a338264
    • Sebastian Graf's avatar
      Much simpler language for PmCheck · 30f5ac07
      Sebastian Graf authored
      Simon realised that the simple language composed of let bindings, bang
      patterns and flat constructor patterns is enough to capture the
      semantics of the source pattern language that are important for
      pattern-match checking. Well, given that the Oracle is smart enough to
      connect the dots in this less informationally dense form, which it is
      now.
      
      So we transform `translatePat` to return a list of `PmGrd`s relative to
      an incoming match variable. `pmCheck` then trivially translates each of
      the `PmGrd`s into constraints that the oracle understands.
      
      Since we pass in the match variable, we incidentally fix #15884
      (coverage checks for view patterns) through an interaction with !1746.
      30f5ac07
  9. 09 Oct, 2019 4 commits
    • Ryan Scott's avatar
      Use addUsedDataCons more judiciously in TcDeriv (#17324) · d584e3f0
      Ryan Scott authored
      If you derive an instance like this:
      
      ```hs
      deriving <...> instance Foo C
      ```
      
      And the data constructors for `C` aren't in scope, then
      `doDerivInstErrorChecks1` throws an error. Moreover, it will
      _only_ throw an error if `<...>` is either `stock` or `newtype`.
      This is because the code that the `anyclass` or `via` strategies
      would generate would not require the use of the data constructors
      for `C`.
      
      However, `doDerivInstErrorChecks1` has another purpose. If you
      write this:
      
      ```hs
      import M (C(MkC1, ..., MkCn))
      
      deriving <...> instance Foo C
      ```
      
      Then `doDerivInstErrorChecks1` will call `addUsedDataCons` on
      `MkC1` through `MkCn` to ensure that `-Wunused-imports` does not
      complain about them. However, `doDerivInstErrorChecks1` was doing
      this for _every_ deriving strategy, which mean that if `<...>` were
      `anyclass` or `via`, then the warning about `MkC1` through `MkCn`
      being unused would be suppressed!
      
      The fix is simple enough: only call `addUsedDataCons` when the
      strategy is `stock` or `newtype`, just like the other code paths
      in `doDerivInstErrorChecks1`.
      
      Fixes #17324.
      d584e3f0
    • Ben Gamari's avatar
      Test · 35cc5eff
      Ben Gamari authored
      35cc5eff
    • Ben Gamari's avatar
      817c1a94
    • Ben Gamari's avatar
      Rename STAGE macro to GHC_STAGE · 0c0a15a8
      Ben Gamari authored
      To avoid polluting the macro namespace
      0c0a15a8
  10. 08 Oct, 2019 5 commits
    • Sebastian Graf's avatar
      PmCheck: Look up parent data family TyCon when populating `PossibleMatches` · f691f0c2
      Sebastian Graf authored
      The vanilla COMPLETE set is attached to the representation TyCon of a
      data family instance, whereas the user-defined COMPLETE sets are
      attached to the parent data family TyCon itself.
      
      Previously, we weren't trying particularly hard to get back to the
      representation TyCon to the parent data family TyCon, resulting in bugs
      like #17207. Now we should do much better.
      
      Fixes the original issue in #17207, but I found another related bug that
      isn't so easy to fix.
      f691f0c2
    • Richard Eisenberg's avatar
      Solve constraints from top-level groups sooner · 9612e91c
      Richard Eisenberg authored
      Previously, all constraints from all top-level groups (as
      separated by top-level splices) were lumped together and solved
      at the end. This could leak metavariables to TH, though, and
      that's bad. This patch solves each group's constraints before
      running the next group's splice.
      
      Naturally, we now report fewer errors in some cases.
      
      One nice benefit is that this also fixes #11680, but in a much
      simpler way than the original fix for that ticket. Admittedly,
      the error messages degrade just a bit from the fix from #11680
      (previously, we informed users about variables that will be
      brought into scope below a top-level splice, and now we just
      report an out-of-scope error), but the amount of complexity
      required throughout GHC to get that error was just not worth it.
      
      This patch thus reverts much of
      f93c9517.
      
      Fixes #16980
      
      Test cases: th/T16980{,a}
      9612e91c
    • Ryan Scott's avatar
      Mark newtype constructors as used in the Coercible solver (#10347) · bf02c264
      Ryan Scott authored
      Currently, newtype constructors are not marked as used when they are
      accessed under the hood by uses of `coerce`, as described in #10347.
      This fixes #10347 by co-opting the `tcg_keep` field of `TcGblEnv`
      to track uses of newtype constructors in the `Coercible` solver.
      See `Note [Tracking unused binding and imports]` in `TcRnTypes`.
      
      Since #10347 is fixed, I was able to simplify the code in `TcDeriv`
      slightly, as the hack described in
      `Note [Newtype deriving and unused constructors]`
      is no longer necessary.
      bf02c264
    • Ben Gamari's avatar
      e9813afc
    • Sebastian Graf's avatar
      PmCheck: Identify some semantically equivalent expressions · 397c6ed5
      Sebastian Graf authored
      By introducing a `CoreMap Id` to the term oracle, we can represent
      syntactically equivalent expressions by the same `Id`. Combine that with
      `CoreOpt.simpleCoreExpr` and it might even catch non-trivial semantic
      equalities.
      
      Unfortunately due to scoping issues, this will not solve #17208 for
      view patterns yet.
      397c6ed5
  11. 07 Oct, 2019 4 commits
    • Ryan Scott's avatar
      Refactor some cruft in TcGenGenerics · ab945819
      Ryan Scott authored
      * `foldBal` contains needless partiality that can easily be avoided.
      * `mkProd_E` and `mkProd_P` both contain unique supply arguments that
        are completely unused, which can be removed.
      ab945819
    • John Ericson's avatar
      Get rid of wildcard patterns in prim Cmm emitting code · 805653f6
      John Ericson authored
      This way, we can be sure we don't miss a case.
      805653f6
    • Ben Gamari's avatar
      Refactor, document, and optimize LLVM configuration loading · b2577081
      Ben Gamari authored
      As described in the new Note [LLVM Configuration] in SysTools, we now
      load llvm-targets and llvm-passes lazily to avoid the overhead of doing
      so when -fllvm isn't used (also known as "the common case").
      
      Noticed in #17003.
      
      Metric Decrease:
          T12234
          T12150
      b2577081
    • Ryan Scott's avatar
      Only flatten up to type family arity in coreFlattenTyFamApp (#16995) · 825c108b
      Ryan Scott authored
      Among other uses, `coreFlattenTyFamApp` is used by Core Lint as a
      part of its check to ensure that each type family axiom reduces
      according to the way it is defined in the source code. Unfortunately,
      the logic that `coreFlattenTyFamApp` uses to flatten type family
      applications disagreed with the logic in `TcFlatten`, which caused
      it to spuriously complain this program:
      
      ```hs
      type family Param :: Type -> Type
      
      type family LookupParam (a :: Type) :: Type where
        LookupParam (f Char) = Bool
        LookupParam x        = Int
      
      foo :: LookupParam (Param ())
      foo = 42
      ```
      
      This is because `coreFlattenTyFamApp` tries to flatten the `Param ()`
      in `LookupParam (Param ())` to `alpha` (where `alpha` is a flattening
      skolem), and GHC is unable to conclude that `alpha` is apart from
      `f Char`. This patch spruces up `coreFlattenTyFamApp` so that it
      instead flattens `Param ()` to `alpha ()`, which GHC _can_ know for
      sure is apart from `f Char`. See
      `Note [Flatten], wrinkle 3` in `FamInstEnv`.
      825c108b
  12. 05 Oct, 2019 5 commits