Built-in Natural literals in Core
ClosedPublic

Authored by hsyl20 on Nov 19 2017, 9:33 AM.

Details

Summary

Add support for built-in Natural literals in Core.

  • Replace MachInt,MachWord, LitInteger, etc. with a single LitNumber constructor with a LitNumType field
  • Support built-in Natural literals
  • Add desugar warning for negative literals
  • Move Maybe(..) from GHC.Base to GHC.Maybe for module dependency reasons

This patch introduces only a few rules for Natural literals (compared to Integer's rules). Factorization of the built-in rules for numeric literals will be done in another patch as this one is already big to review.

Test Plan

validate
test build with integer-simple

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
There are a very large number of changes, so older changes are hidden. Show Older Changes
bgamari added inline comments.Nov 20 2017, 8:20 AM
libraries/base/GHC/Natural.hs
132

If we must move this let's move it to GHC.Maybe.

@Bodigrim, would you like to discuss how to proceed on this?

Sorry for disappearance. I got a new job recently, still sorting out things. I plan to continue with this change next week.

Sorry for disappearance. I got a new job recently, still sorting out things. I plan to continue with this change next week.

Quite alright! Do let me know if you would like to chat.

bgamari requested changes to this revision.Jan 21 2018, 11:12 AM

Bumping out of review queue for now.

This revision now requires changes to proceed.Jan 21 2018, 11:12 AM
hsyl20 added a subscriber: hsyl20.Feb 15 2018, 5:43 PM

@Bodigrim I have just been bitten by Trac #14170 too... Is there anything we can help you with to complete this patch?

@Bodigrim I have just been bitten by Trac #14170 too... Is there anything we can help you with to complete this patch?

Well, I got stuck with build error, quoted above. Are you able to build GHC with my patch?

Well, I got stuck with build error, quoted above. Are you able to build GHC with my patch?

No. It fails with the same error (triggered in CoreTidy pass) and sometimes with this one:

libraries/base/GHC/Exception/Type.hs-boot:1:1: error:
    Failed to load interface for ‘GHC.Types’
    There are files missing in the ‘ghc-prim-0.5.2.0’ package,
    try running 'ghc-pkg check'.
    Use -v to see a list of the files searched for.
hvr added a comment.EditedFeb 19 2018, 7:33 AM

I haven't looked into the issue, but I do recognise this kind of error, and I can offer a suggestion which may help you: make sure the the dependencies via hs-boot files are properly handled; this may require some non-obvious tricks to help ghc & build-system out

  • naturalToIntegerName, plusNaturalName, minusNaturalName, timesNaturalName, and mkNaturalName are missing from basicKnownKeyNames in compiler/prelude/PrelNames.hs
  • import GHC.Types () is missing from libraries/base/GHC/Exception/Type.hs-boot

Even with this fixed, I still get the error. -ddump-if-trace shows that GHC is trying to load the interface to find the declaration of mkNatural. Even if the GHC.Natural module is totally empty, I still get the error (maybe related to some autogenerated Typeable stuff?).

hsyl20 commandeered this revision.Mar 1 2018, 7:54 AM
hsyl20 added a reviewer: Bodigrim.

I have fixed the build. I hope it's ok if I commandeer the revision in order to update my patch. @Bodigrim don't hesitate to commandeer it back.

The main issue was that we shouldn't be using Natural literals in base, for the same reason that we shouldn't use Integer literals in integer-*.

hsyl20 updated this revision to Diff 15582.Mar 1 2018, 7:56 AM
  • Split and add base:GHC.Maybe
  • Fix error in naturalFromInteger rule (was returning a LitInteger)
  • Ensure that we avoid using Natural literals in base
  • Fix use of Natural literal in Data.Bits Natural instance
  • Export Natural stuff in basicKnownKeyNames
  • Add some missing imports
hsyl20 updated this revision to Diff 15590.Mar 2 2018, 5:35 AM
  • Fix TH
  • Fix Bits instance
hsyl20 updated this revision to Diff 15593.Mar 2 2018, 7:05 AM
  • Fix tests

Thanks for doing this!

The one obvious thing that seems missing from this patch is one or two test cases that verify that these optimizations actually kick in. The programs from Trac #14170 and Trac #14465 seem like obvious candidates.

compiler/basicTypes/Literal.hs
224

Did you mean Note [Natural literals] here?

libraries/base/GHC/Base.hs
121

Re-export the entire module GHC.Maybe, for consistency with the other exports in this module.

hsyl20 updated this revision to Diff 15595.Mar 2 2018, 10:32 AM
  • NOINLINE naturalToInteger
hsyl20 updated this revision to Diff 15596.Mar 2 2018, 11:22 AM
  • Add tests
  • Warn on negative Natural literals
  • Fix some minor glitches
  • Fix some line length warnings
hsyl20 marked 3 inline comments as done.Mar 2 2018, 11:23 AM

Thanks for doing this!

The one obvious thing that seems missing from this patch is one or two test cases that verify that these optimizations actually kick in. The programs from Trac #14170 and Trac #14465 seem like obvious candidates.

Thanks, I have added them.

hsyl20 edited the summary of this revision. (Show Details)Mar 2 2018, 12:51 PM
hsyl20 edited the test plan for this revision. (Show Details)
hsyl20 updated this revision to Diff 15602.Mar 2 2018, 1:20 PM
  • wordToNatural: use it and add a built-in rule to lift constant applications into Natural literals
hsyl20 updated this revision to Diff 15642.Mar 5 2018, 7:14 AM
  • Fix build with integer-simple
  • Don't use wordToNatural# in base, otherwise built-in rules may produce Natural literals

I wonder if there could be quite a bit less duplication. Otherwise, it looks plausible.

compiler/basicTypes/Literal.hs
131

There's a LOT of duplication in this patch. How much less would there be if we had this representation?

| LitIntNat IntNat Integer Type
....
data IntNat = IsInteger | IsNatural
`
RyanGlScott added inline comments.Mar 5 2018, 10:56 AM
compiler/deSugar/MatchLit.hs
174

I didn't notice in my earlier pass over this patch that this actually adds a new warning! At least, if I understand this correctly, then -Woverflowed-literals will now warn on things like:

(-1 :: Natural)

If so, add a test for this! Also, it would be good to mention this in the 8.6.1 release notes.

hsyl20 updated this revision to Diff 15650.Mar 5 2018, 11:03 AM
  • Add test for negative Natural literal warning
hsyl20 updated this revision to Diff 15651.Mar 5 2018, 11:08 AM
hsyl20 marked an inline comment as done.
  • Add missing stderr file

@simonpj If we go this way, I think we should replace MachInt, MachInt64, MachWord, MachWord64, LitInteger and LitNatural with something like:

| LitNumber LitNumType Integer Type

data LitNumType
  = LitNumInt
  | LitNumWord
  | LitNumInt64
  | LitNumWord64
  | LitNumInteger
  | LitNumNatural

litNumDesc :: LitNumType -> LitNumDesc
litNumDesc = \case ...

litNumType_maybe :: Type -> Maybe LitNumType
litNumType_maybe = ...

data LitNumDesc = LitNumDesc
  { litNumSigned :: Bool
  , litNumBitsize :: Maybe Word
  , litNumMinBound :: Maybe Integer
  , litNumMaxBound :: Maybe Integer
  , litTyConName :: Name
  , litNumAddName :: Name
  , litNumSubName :: Name
  , litNumNegateName :: Maybe Name
  , litNumDesugar :: Maybe (Integer -> CoreExpr)
  ...
  }
  1. We wouldn't have to pass the cvt_integer and cvt_natural functions all the way down to cafRefsL: just use litNumDesugar instead
  2. Constant folding rules (soon to be merged D2858) could be made more generic by only relying on litNumType_maybe and the stuff in LitNumDesc. Currently they don't work with Integer and Natural.
  3. It would be easier to add support for 8-bit, 16-bit and 32-bit literals and primops.

I should fill another ticket for this.

f we go this way, I think we should replace MachInt, MachInt64, MachWord, MachWord64, LitInteger and LitNatural with something like:

Looks plausible to me. But maybe for this patch you can start in that direction, to avoid generating a lot of new code that you then delete?

phadej added a subscriber: phadej.Mar 9 2018, 6:17 AM
phadej added inline comments.
compiler/basicTypes/Literal.hs
131

Why not LitNatural Natural Type?

hsyl20 updated this revision to Diff 15718.Mar 9 2018, 6:36 AM
  • Simplify hasCafRefs
  • Introduce LitNumType and LitNumber constructor
  • Factorize some code
hsyl20 added a comment.Mar 9 2018, 6:47 AM

Looks plausible to me. But maybe for this patch you can start in that direction, to avoid generating a lot of new code that you then delete?

Done!

Much nicer. A few more suggestions, but basically OK with me.

compiler/basicTypes/Literal.hs
146

I would rather *not* have these pattern synonyms, because it makes it harder to see when pattern matches are exhaustive. How bad would it be to get rid of MachInt etc altogther? (use mkMachInt for a smart constructor.

compiler/coreSyn/CoreUtils.hs
2415

Maybe one arg of type LitNumType -> Integer-> CoreExpr?

compiler/prelude/PrelRules.hs
1285

Can we share any code by using the new LitNumTypes stuff?

hsyl20 updated this revision to Diff 16087.Apr 19 2018, 6:59 AM
hsyl20 marked 3 inline comments as done.
  • Remove pattern synonyms
  • Factorise cvt_integer and cvt_natural into cvt_literal
hsyl20 edited the summary of this revision. (Show Details)Apr 19 2018, 7:00 AM
hsyl20 retitled this revision from Performance of Natural to Built-in Natural literals in Core.Apr 19 2018, 7:06 AM
hsyl20 added inline comments.
compiler/prelude/PrelRules.hs
1285

Indeed we can. In fact doing this led me to factorize rules for all numeric literals. I'll upload a separate diff, this one is already quite big.

hsyl20 updated this revision to Diff 16094.Apr 19 2018, 10:59 AM
  • Fix desugaring of overflowing literals
hsyl20 updated this revision to Diff 16115.Apr 19 2018, 7:26 PM
  • Fix test
hsyl20 updated this revision to Diff 16129.Apr 20 2018, 11:55 AM
  • Use Proxy instead of ambiguous types
  • Fix constructor in mkNatural
hsyl20 updated this revision to Diff 16130.Apr 20 2018, 12:07 PM
  • Comment only

The previous update fixes the build with integer-simple. Tests are still running but if they pass I think this patch is finally ready to merge.

hsyl20 updated this revision to Diff 16935.Fri, Jun 15, 11:30 AM
  • Rebae on master
hsyl20 edited the summary of this revision. (Show Details)Fri, Jun 15, 11:39 AM
bgamari accepted this revision.Fri, Jun 15, 3:19 PM

This looks lovely. Thanks!

compiler/basicTypes/Literal.hs
141

I quite like this new scheme.

This revision is now accepted and ready to land.Fri, Jun 15, 3:19 PM
Closed by commit rGHCfe770c211631: Built-in Natural literals in Core (authored by Sylvain Henry <hsyl20@gmail.com>, committed by bgamari). · Explain WhyFri, Jun 15, 4:01 PM
This revision was automatically updated to reflect the committed changes.