Do Caf analysis right before codegen, fix #9718
Needs ReviewPublic

Authored by osa1 on Dec 10 2018, 12:35 PM.

Details

Reviewers
simonpj
simonmar
bgamari
sgraf
Trac Issues
#9718
Summary

Previously CafInfo of ids were computed in TidyPgm and those final
CafInfos were written to interface files. All later passes (CorePrep,
CoreToStg, Stg passes like StgCSE and Unarise) had to preserve the
CafInfos, which caused bugs like Trac #15038 and difficulties in e.g. D4717
(Phab:D4717), and we had large amounts of code to maintain the CafInfos
after TidyPgm.

We now generate interface files without CafInfos, and update the files
with the final CafInfos right before Cmm generation. The code to
maintain CafInfos in TidyPgm and CoreToStg, sanity checks etc. are all
gone.

See comments in stgCafAnal for details of how the new analysis works.

Fixes Trac #9718, Trac #4121.

Some other changes:

  • Update Outputable instance of CafInfo.
  • We no longer print CafInfos when printing Core binders, as all binders are CAFFY in Core now (until we do the analysis right before Cmm generation).

TODOs:

  • Remove duplicated code (from hscWriteIface) in interface updating code in hscGenHardCode. Done.
  • There's at least one bug, see test T4003 (it triggers the assertion in StgCafAnal.depSort). Existing bug, reported as Trac #16038, which is now fixed. Assertion enabled again.
  • We currently generate the interface files as before, and then overwrite them with the correct CafInfos. Instead we should generate the interface files just once (with -fno-code we'll have conservative CafInfos for ids as we don't do the analysis in Core anymore). Done.
  • Eyeball some examples to make sure we really update the iface files with correct and more specific CafInfos (e.g. at least some ids should be NoCafRefs).
  • We should probably make -fno-code a part of the iface fingerprint? (I don't understand this stuff yet)
  • Updating interface files are currently very inefficient, see HscMain.updateModIface. The reason is because ModIface is not suitable for updates as it keeps everything in lists. I need to refactor ModIface type a little bit for this. Done.
  • Move HscMain.updateModIface to one of the iface modules. Done.
  • Run nofib to compare compile times and binary sizes. I suspect we may save a few words per test because we now generate much more precise CafInfos (with the new analysis when building GHC we make 9604 CAFFY ids non-CAFFY). Done.
  • Why are binaries larger now? With more things non-CAFFY I'd expect binaries to be smaller, not larger. This was a bug, fixed now.
  • We probably want to update top-level STG binder CafInfos in stgCafAnal (instead of doing it in another pass) for efficiency. Alternatively consider passing CafInfo map to CmmBuildInfoTables instead of updating CafInfos of binders.
  • Update IdInfos in ModDetails (in HomeModInfo) with final CafInfos. Done, but code is terrible. Also needs careful testing. We don't have good coverage of --make, and any bugs in this would only happen with --make.
  • Figure out why binary sizes got smaller.
  • Bug: StgLiftLams currently uses idCafInfo which is not available until after all the STG passes.

NoFib results are generated with

make EXTRA_RUNTEST_OPTS="+RTS -F1 -RTS"

which gives more stable residency numbers. Results:


        Program           Size    Allocs   TotalMem
-------------------------------------------------------------
             CS          -0.1%      0.0%       0.0%
            CSD          -0.0%      0.0%       0.0%
             FS          -0.1%      0.0%       0.0%
              S          -0.1%      0.0%       0.0%
             VS          -0.1%      0.0%       0.0%
            VSD          -0.0%      0.0%       0.0%
            VSM          -0.1%      0.0%       0.0%
           anna          -0.1%      0.0%       0.0%
           ansi          -0.0%      0.0%       0.0%
           atom          -0.1%      0.0%       0.0%
         awards          -0.0%      0.0%       0.0%
         banner          -0.0%      0.0%       0.0%
     bernouilli          -0.0%      0.0%       0.0%
   binary-trees          -0.1%      0.0%       0.0%
          boyer          -0.0%      0.0%       0.0%
         boyer2          -0.0%      0.0%       0.0%
           bspt          -0.0%      0.0%       0.0%
       calendar          -0.0%      0.0%       0.0%
       cichelli          -0.1%      0.0%       0.0%
        circsim          -0.1%      0.0%       0.0%
       clausify          -0.0%      0.0%       0.0%
  comp_lab_zift          -0.1%      0.0%       0.0%
       compress          -0.1%      0.0%       0.0%
      compress2          -0.0%      0.0%      +8.3%
    constraints          -0.0%      0.0%       0.0%
   cryptarithm1          -0.0%      0.0%       0.0%
   cryptarithm2          -0.1%      0.0%       0.0%
            cse          -0.1%      0.0%       0.0%
   digits-of-e1          -0.0%      0.0%       0.0%
   digits-of-e2          -0.0%      0.0%       0.0%
          eliza          -0.0%      0.0%       0.0%
          event          -0.0%      0.0%       0.0%
    exact-reals          -0.0%      0.0%       0.0%
         exp3_8          -0.0%      0.0%       0.0%
         expert          -0.1%      0.0%       0.0%
 fannkuch-redux          -0.0%     +0.0%       0.0%
          fasta          -0.1%      0.0%       0.0%
            fem          -0.1%      0.0%       0.0%
            fft          -0.1%      0.0%       0.0%
           fft2          -0.1%      0.0%       0.0%
       fibheaps          -0.1%      0.0%       0.0%
           fish          -0.1%      0.0%       0.0%
          fluid          -0.1%      0.0%       0.0%
         fulsom          -0.1%      0.0%       0.0%
         gamteb          -0.1%      0.0%       0.0%
            gcd          -0.1%      0.0%       0.0%
    gen_regexps          -0.1%      0.0%       0.0%
         genfft          -0.0%      0.0%       0.0%
             gg          -0.1%      0.0%       0.0%
           grep          -0.0%      0.0%       0.0%
         hidden          -0.1%      0.0%       0.0%
            hpg          -0.1%      0.0%       0.0%
            ida          -0.1%      0.0%       0.0%
          infer          -0.1%      0.0%       0.0%
        integer          -0.0%      0.0%       0.0%
      integrate          -0.1%      0.0%       0.0%
   k-nucleotide          -0.1%      0.0%       0.0%
          kahan          -0.1%      0.0%       0.0%
        knights          -0.0%      0.0%       0.0%
         lambda          -0.0%      0.0%       0.0%
     last-piece          -0.1%      0.0%       0.0%
           lcss          -0.0%      0.0%       0.0%
           life          -0.1%      0.0%       0.0%
           lift          -0.1%      0.0%       0.0%
         linear          -0.1%      0.0%       0.0%
      listcompr          -0.1%      0.0%       0.0%
       listcopy          -0.0%      0.0%       0.0%
       maillist          -0.1%      0.0%       0.0%
         mandel          -0.0%      0.0%       0.0%
        mandel2          -0.1%      0.0%       0.0%
           mate          -0.1%      0.0%       0.0%
        minimax          -0.1%      0.0%       0.0%
        mkhprog          -0.0%      0.0%       0.0%
     multiplier          -0.0%      0.0%       0.0%
         n-body          -0.1%      0.0%       0.0%
       nucleic2          -0.1%      0.0%       0.0%
           para          -0.1%      0.0%       0.0%
      paraffins          -0.0%      0.0%       0.0%
         parser          -0.0%      0.0%       0.0%
        parstof          -0.0%      0.0%       0.0%
            pic          -0.1%      0.0%       0.0%
       pidigits          -0.1%      0.0%       0.0%
          power          -0.0%      0.0%       0.0%
         pretty          -0.1%      0.0%       0.0%
         primes          -0.0%      0.0%       0.0%
      primetest          -0.0%      0.0%       0.0%
         prolog          -0.1%      0.0%       0.0%
         puzzle          -0.1%      0.0%       0.0%
         queens          -0.1%      0.0%       0.0%
        reptile          -0.1%      0.0%       0.0%
reverse-complem          -0.1%      0.0%       0.0%
        rewrite          -0.0%      0.0%       0.0%
           rfib          -0.1%      0.0%       0.0%
            rsa          -0.1%      0.0%       0.0%
            scc          -0.1%      0.0%       0.0%
          sched          -0.0%      0.0%       0.0%
            scs          -0.1%      0.0%       0.0%
         simple          -0.2%      0.0%       0.0%
          solid          -0.1%      0.0%       0.0%
        sorting          -0.1%      0.0%       0.0%
  spectral-norm          -0.1%      0.0%       0.0%
         sphere          -0.1%      0.0%       0.0%
         symalg          -0.0%      0.0%       0.0%
            tak          -0.0%      0.0%       0.0%
      transform          -0.0%      0.0%       0.0%
       treejoin          -0.1%      0.0%       0.0%
      typecheck          -0.0%      0.0%       0.0%
        veritas          -0.0%      0.0%       0.0%
           wang          -0.1%      0.0%       0.0%
      wave4main          -0.0%      0.0%       0.0%
   wheel-sieve1          -0.0%      0.0%       0.0%
   wheel-sieve2          -0.0%      0.0%       0.0%
           x2n1          -0.1%      0.0%       0.0%
-------------------------------------------------------------
            Min          -0.2%      0.0%       0.0%
            Max          -0.0%     +0.0%      +8.3%
 Geometric Mean          -0.1%     -0.0%      +0.1%
Test Plan

This validates. See nofib results above.

There are a very large number of changes, so older changes are hidden. Show Older Changes
osa1 edited the summary of this revision. (Show Details)Dec 14 2018, 8:26 AM

As far as I can tell, in this diff we calculate the fingerprints as normal in mkIface but then update the CafInfo later. Isn't this wrong? The fingerprints need to take into account the CafInfo, so we have to defer computing the fingerprints until after the CafInfo is added.

compiler/coreSyn/PprCore.hs
478

Why did you remove this? Isn't it useful, e.g. for imported Ids?

osa1 updated this revision to Diff 19176.Dec 17 2018, 11:22 AM
  • Fix -dynamic-too with with --make/backpack
osa1 edited the summary of this revision. (Show Details)Dec 17 2018, 11:00 PM
osa1 added a comment.EditedDec 17 2018, 11:06 PM

As far as I can tell, in this diff we calculate the fingerprints as normal in mkIface but then update the CafInfo later. Isn't this wrong? The fingerprints need to take into account the CafInfo, so we have to defer computing the fingerprints until after the CafInfo is added.

Currently we generate interface files only once so this should be fixed. (in the revision you reviewed I was generating interfaces with conservative CafInfos and then updating with precise CafInfos, without updating fingerprints)

compiler/coreSyn/PprCore.hs
478

As far as I can see this is only used when printing top-level Core binders (see the updated test outputs below) and we don't know CafInfos of those anymore.

osa1 updated this revision to Diff 19183.Dec 17 2018, 11:59 PM
  • Introduce tcLocalIdInfo
  • Move dep analysis to StgCafAnal
osa1 marked 3 inline comments as done.Dec 18 2018, 12:00 AM
osa1 edited the summary of this revision. (Show Details)Dec 18 2018, 2:39 AM
osa1 edited the test plan for this revision. (Show Details)

See nofib results in the description. I'll try to see what caused TotalMem regressions in linear and maillist. (I suspect this is because we float more things out now and trade residency for allocation, but I'll check)

osa1 updated this revision to Diff 19184.Dec 18 2018, 3:53 AM
  • Remove old TODO
  • Add a note
osa1 marked an inline comment as done.Dec 18 2018, 3:54 AM
osa1 edited the summary of this revision. (Show Details)Dec 18 2018, 6:44 AM
osa1 edited the test plan for this revision. (Show Details)
osa1 edited the summary of this revision. (Show Details)Dec 18 2018, 8:08 AM
osa1 edited the test plan for this revision. (Show Details)
osa1 edited the summary of this revision. (Show Details)

Sorry for the noise.. I thought I did a mistake when analysing nofib results, but it turns out there were no mistakes. I also checked linear. For some reason we make things more caffy in that program, but I don't know why yet. I'll now look at maillist, perhaps that's easier to explain.

simonmar requested changes to this revision.Dec 18 2018, 9:08 AM
In D5432#150596, @osa1 wrote:

As far as I can tell, in this diff we calculate the fingerprints as normal in mkIface but then update the CafInfo later. Isn't this wrong? The fingerprints need to take into account the CafInfo, so we have to defer computing the fingerprints until after the CafInfo is added.

Currently we generate interface files only once so this should be fixed. (in the revision you reviewed I was generating interfaces with conservative CafInfos and then updating with precise CafInfos, without updating fingerprints)

Could you explain a bit more how this happens? It looks like you still have the function updateIfaceCafInfos :: ModIface -> NameEnv (a, CafInfo) -> ModIface, which is unsafe: it doesn't update the fingerprints, so the ModIface being returned from this function is wrong.

This revision now requires changes to proceed.Dec 18 2018, 9:08 AM
osa1 added a comment.Dec 18 2018, 9:47 AM
In D5432#150596, @osa1 wrote:

As far as I can tell, in this diff we calculate the fingerprints as normal in mkIface but then update the CafInfo later. Isn't this wrong? The fingerprints need to take into account the CafInfo, so we have to defer computing the fingerprints until after the CafInfo is added.

Currently we generate interface files only once so this should be fixed. (in the revision you reviewed I was generating interfaces with conservative CafInfos and then updating with precise CafInfos, without updating fingerprints)

Could you explain a bit more how this happens? It looks like you still have the function updateIfaceCafInfos :: ModIface -> NameEnv (a, CafInfo) -> ModIface, which is unsafe: it doesn't update the fingerprints, so the ModIface being returned from this function is wrong.

Sorry, you're right, I'll fix this.

osa1 edited the summary of this revision. (Show Details)Dec 19 2018, 6:27 AM

Sign unfortunately I really did make a mistake last time and confused GHC trees. I now updated nofib numbers, binaries are larger now. I'll try to see why. As discussed at the meeting I tried running nofib with +RTS -F1 which made the residencies identical.

osa1 added a comment.Dec 19 2018, 7:28 AM

I also need to think more about the fingerprinting issue -- if I simply call addFingerprints before writing the interface file I break recomp005 (the progress message says A changed instead of D changed when rebuilding E.hs).

osa1 updated this revision to Diff 19201.Dec 19 2018, 11:24 PM
osa1 edited the summary of this revision. (Show Details)
  • Print iface CafInfos as before, to make comparing iface files easier
osa1 added a comment.EditedDec 19 2018, 11:59 PM

Hmm this is really weird. I'm looking at bernoulli to see what's causing the size difference. Core and Stg files and iface dumps (-show-iface) are identical (CafInfos are printed in Stg dumps and those are identical too), but there are differences in Cmm and final binaries have different size (3077896 originally, 3086024 with this patch).

.hi sizes are also slightly different, but the size with this patch is _smaller_, not larger: 2355 originally, 2318 with this patch. I suspect this is because of the slighly more size-efficient IfaceId layout (we now reserve one field for the CafInfo instead of adding one more list item for it, but that one field does not make the type larger becuase there are larger constructors in the type).

I compared one Stg binding which got different SRT with this patch. Originally it looks like this:

[sat_s6Tg_entry() //  [R1]
         { info_tbls: [(c6WP,
                        label: sat_s6Tg_info
                        rep: HeapRep 1 ptrs { Thunk }
                        srt: Just GHC.Integer.Type.plusInteger_closure)]
           stack_info: arg_space: 8 updfr_space: Just 8
         }
         ...
]

With this patch:

[section ""data" . _u6XI_srt" {
     _u6XI_srt:
         const stg_SRT_2_info;
         const GHC.Integer.Type.plusInteger_closure;
         const lvl1_r6SP_closure;
         const 0;
 },
 sat_s6Tg_entry() //  [R1]
         { info_tbls: [(c6WP,
                        label: sat_s6Tg_info
                        rep: HeapRep 1 ptrs { Thunk }
                        srt: Just _u6XI_srt)]
           stack_info: arg_space: 8 updfr_space: Just 8
         }
         ...
]

So previously this object only had one SRT entry, now it has 2. I don't understand how this is possible given that STGs and CafInfos are identical... Could this be because a difference in libraries? (e.g. base)

osa1 added a comment.Dec 20 2018, 12:09 AM

Hmm, I think this is because of a bug. The extra SRT entry is for this closure: lvl1_r6SP_closure. In STG:

lvl1_r6SP :: GHC.Integer.Type.Integer
[GblId, Unf=OtherCon []] =
    CCS_DONT_CARE GHC.Integer.Type.S#! [0#];

In Cmm:

[section ""data" . lvl1_r6SP_closure" {
     lvl1_r6SP_closure:
         const GHC.Integer.Type.S#_con_info;
         const 0;
 }]

This is clearly not a CAF, and I can see this in CafInfo analysis results. So I think this shouldn't be in the SRT, but for some reason it is ...

osa1 added a comment.EditedDec 20 2018, 12:13 AM

Hmm I think this may be because I never update IdInfos in STG (I generate a map from Ids to CafInfo which is used to update the iface), and I think IdInfos are somehow used during SRT generation. I should check if this is the case, and update IdInfos.

osa1 added a comment.Dec 20 2018, 12:47 AM

Yep! That fixed it for bernouilli. I'll now boot GHC again and run nofib again and update numbers.

osa1 edited the summary of this revision. (Show Details)Dec 20 2018, 2:22 AM
osa1 updated this revision to Diff 19202.Dec 20 2018, 2:24 AM
  • Update STG top-level binder CafInfos before codegen
osa1 edited the summary of this revision. (Show Details)Dec 20 2018, 2:26 AM

Great, binaries are 0.1% smaller now. I added one more TODO item for the implementation. There's still one outlier in residency which is compress2. I'll try to see if this is again bad sampling or an actual
change in residency.

osa1 added a comment.Dec 20 2018, 2:37 AM

STGs and Cmms are identical (including CafInfos) so compress2 residency should also be noise.

simonpj added a comment.EditedDec 20 2018, 4:11 AM

Hang on. updateStgCafInfos puts CAF info into the IdInfo of a binder. But who looks at that info? I guess:

  1. We use it when creating the interface file so importing modules see correct CAF info
  2. We use it when creating SRTs

I think you have (1) well under control. Presumably after CAF analysis you pass a finite map (Name -> CAFInfo) to the interface-file-modification stuff?

But what about (2). In CmmBuildInfoTables I think

  • It looks at the references from a CmmProc; that is, the CLabels it mentions.
  • Then it uses CLabel.hasCaf to see if it's a CAFFY label., and if so adds it to the SRT for that CmmProc.
  • hasCAF is true of IdLabel _ MayHaveCafRefs _). How does the IdLabel get that flag?
  • Well, it comes from the IdInfo of the Id. This is, I think, why you are doing updateStgCafInfos.
  • But it's delicate. You are modifying only the _binding sites_ not the _occurrences_. I think you are relying on the code generator's environment to propagate the info to the occurrences.

This all seems much too indirect, relying on a chain of invariants. Here's an alteranative plan:

  • Remove CafInfo from IdLabel entirely.
  • Pass the Name -> CafInfo mapping directly to CmmBuildnfoTables; when you would do hasCaf lbl instead do hasCaf caf_env lbl:
hasCaf :: NameEnv CafInfo -> CLabel -> Bool
hasCaf caf_env (IdLabel n _) = case lookupNameEnf caf_env n of
                                                      Just MayHaveCafRefs -> True
                                                      _ -> False

That is simple and direct. It sends the accurate info from the analysis (directly to where is needed). No mucking about with IdInfo.

PS: One other thing to check.

In GHCi, or --make, we create a ModDetails for subsequent modules to use. We carefully ensure that every Id has the right IdInfo. I think this is done in TidyPgm.

We must make sure that the TypeEnv in this persistent ModDetails has the final CafInfo in it!

osa1 added a comment.Dec 20 2018, 5:28 AM

Hmm, I run it two more times, and I still get +8.3% TotalMem. However in one of the runs I also got -0.2% allocations. That's weird given that we generate identical Cmms...

osa1 added a comment.Dec 20 2018, 6:04 AM

Hang on. updateStgCafInfos puts CAF info into the IdInfo of a binder. But who looks at that info? I guess:

  1. We use it when creating the interface file so importing modules see correct CAF info
  2. We use it when creating SRTs

    I think you have (1) well under control. Presumably after CAF analysis you pass a finite map (Name -> CAFInfo) to the interface-file-modification stuff?

Exactly. I pass the map to updateIfaceCafInfos.

But what about (2). In CmmBuildInfoTables I think

  • It looks at the references from a CmmProc; that is, the CLabels it mentions.
  • Then it uses CLabel.hasCaf to see if it's a CAFFY label., and if so adds it to the SRT for that CmmProc.
  • hasCAF is true of IdLabel _ MayHaveCafRefs _). How does the IdLabel get that flag?
  • Well, it comes from the IdInfo of the Id. This is, I think, why you are doing updateStgCafInfos.
  • But it's delicate. You are modifying only the _binding sites_ not the _occurrences_. I think you are relying on the code generator's environment to propagate the info to the occurrences.

    This all seems much too indirect, relying on a chain of invariants. Here's an alteranative plan:
  • Remove CafInfo from IdLabel entirely.
  • Pass the Name -> CafInfo mapping directly to CmmBuildnfoTables; when you would do hasCaf lbl instead do hasCaf caf_env lbl: ` hasCaf :: NameEnv CafInfo -> CLabel -> Bool hasCaf caf_env (IdLabel n _) = case lookupNameEnf caf_env n of Just MayHaveCafRefs -> True _ -> False ` That is simple and direct. It sends the accurate info from the analysis (directly to where is needed). No mucking about with IdInfo.

I think there may be more uses of idCafInfos. Simply searching in the source code shows that

  • StgCmmBind
  • StgCmmCon
  • StgCmmEnv
  • StgCmmClosure

also use idCafInfo. Maybe they only use it for imported ids, I don't know yet. This imported vs. non-imported distinction is really fragile and I wonder if we could somehow fix that too -- some information are only available for imported ids, but we don't have a distinction of imported vs. local at the type level so it's hard to make sure those information will only be queried for imported ids..

osa1 added a comment.Dec 20 2018, 6:19 AM

PS: One other thing to check.

In GHCi, or --make, we create a ModDetails for subsequent modules to use. We carefully ensure that every Id has the right IdInfo. I think this is done in TidyPgm.

We must make sure that the TypeEnv in this persistent ModDetails has the final CafInfo in it!

Why do we need CafInfos in a TypeEnv? I'd expect TypeEnv to be used for type checking, which shouldn't need CafInfos.

I checked the code, in tidyProgram we I think we create a TypeEnv with only "external" ids (the External constructor is not documented but I'm guessing that it's for imported ids). There are some comments about giving ids in TypeEnv correct IdInfo, but I can't see code for that, so maybe that's outdated. The code looks like this

tidyProgram hsc_env mod_guts = do
    -- Create empty env
    let type_env = typeEnvFromEntities [] tcs fam_insts
    -- Add external ids to the env
    let final_ids  = [ id | id <- bindersOfBinds tidy_binds, isExternalName (idName id)]
    let type_env1  = extendTypeEnvWithIds type_env final_ids
    ...
    -- Add pattern synonyms to the env
    let type_env2    = extendTypeEnvWithPatSyns tidy_patsyns type_env1
    -- Final type env
    tidy_type_env = tidyTypeEnv omit_prags type_env2

tidyTypeEnv has comments about IdInfos but I can't see any IdInfo stuff in the code:

tidyTypeEnv :: Bool       -- Compiling without -O, so omit prags
            -> TypeEnv -> TypeEnv

-- The completed type environment is gotten from
--      a) the types and classes defined here (plus implicit things)
--      b) adding Ids with correct IdInfo, including unfoldings,
--              gotten from the bindings
-- From (b) we keep only those Ids with External names;
--          the CoreTidy pass makes sure these are all and only
--          the externally-accessible ones
-- This truncates the type environment to include only the
-- exported Ids and things needed from them, which saves space
--
-- See Note [Don't attempt to trim data types]

tidyTypeEnv omit_prags type_env
 = let
        type_env1 = filterNameEnv (not . isWiredInName . getName) type_env
          -- (1) remove wired-in things
        type_env2 | omit_prags = mapNameEnv trimThing type_env1
                  | otherwise  = type_env1
          -- (2) trimmed if necessary
    in
    type_env2

I think there may be more uses of idCafInfos. Simply searching in the source code shows that

I looked at StgCmmBind; the idCafInfo is used solely to pass (via mkLocalClosureLabel) to IdLabel. If IdLabel didn't have a CafInfo in it, we would not need this.

Ditto StgCmmCon, StgCmmEnv, StgCmmClosure.

So I think all that's a non-problem.

Why do we need CafInfos in a TypeEnv? I'd expect TypeEnv to be used for type checking, which shouldn't need CafInfos.

When compiling module M, suppose we have the binding

f = A.g True

where A.g is imported from A. We look up A.g's name in type env, to get the Id for A.g. That is the Id that we'll use in the Core that we compile for M. So the arity, strictness -- and CAF info -- for A.g has better be correct.

We do that in tidyIdInfo:

-- tidyTopIdInfo creates the final IdInfo for top-level
-- binders.  There are two delicate pieces:
--
--  * Arity.  After CoreTidy, this arity must not change any more.
--      Indeed, CorePrep must eta expand where necessary to make
--      the manifest arity equal to the claimed arity.
--
--  * CAF info.  This must also remain valid through to code generation.
--      We add the info here so that it propagates to all
--      occurrences of the binders in RHSs, and hence to occurrences in
--      unfoldings, which are inside Ids imported by GHCi. Ditto RULES.
--      CoreToStg makes use of this when constructing SRTs.

Another way to say it is this:

  • The object code
  • The interface file
  • The ModDetails passed on to subsequent modules in --make, GHCi etc

must all agree about arity, stricntess, CAF info.

osa1 edited the summary of this revision. (Show Details)Dec 20 2018, 6:58 AM
osa1 edited the summary of this revision. (Show Details)Dec 20 2018, 7:00 AM
osa1 edited the summary of this revision. (Show Details)Dec 20 2018, 11:43 PM
osa1 added a comment.Dec 20 2018, 11:47 PM

@simonpj one thing I realized is because we don't generate Stg when generating bytecode we can't do CafInfo analysis for interpreted modules, so we can't update ModDetails/HomeModInfo of interpreted modules with CafInfos. Do you think this is a problem?

simonmar added a comment.EditedDec 21 2018, 2:08 AM

@simonpj

Remove CafInfo from IdLabel entirely.
Pass the Name -> CafInfo mapping directly to CmmBuildnfoTables; when you would do hasCaf lbl instead do hasCaf caf_env lbl:

I don't think this works - for imported Ids we need to get the CafInfo from the Id and put it in the IdLabel.

Lacking the CafInfo in the TypeEnv (which is a good point) would only show up with -O --make, and we don't have many tests that compile that way, yet most packages in the wild will be compiled that way. This is an odd blind spot in our testing regime. Perhaps we should compile nofib using both single-module compilation and --make and check that we get the same results?

In D5432#150837, @osa1 wrote:

@simonpj one thing I realized is because we don't generate Stg when generating bytecode we can't do CafInfo analysis for interpreted modules, so we can't update ModDetails/HomeModInfo of interpreted modules with CafInfos. Do you think this is a problem?

It doesn't matter at the moment because

  • We don't have compiled modules that depend on interpreted modules
  • The interpreter doesn't build CAFs or SRTs

So I think this is OK, but worth a comment somewhere.

So I think this is OK, but worth a comment somewhere.

_Definitely_ worth a comment.

Indeed, there should be an overview Note that explains the moving parts; you could make a bullet about interpreted stuff there.

I don't think this works - for imported Ids we need to get the CafInfo from the Id and put it in the IdLabel.

Ah yes, good point. Moreover, now that we have turned the bindings for this module into GlobalIds (done in TidyPgm), it's no longer easy to determine which ones are imported.

What is making me uncomfortable is that our current design looks like this:

  • We get the Name -> CafInfo map
  • We run over the top level binding, augmenting the CafInfo of the _binding sites_ of top level Ids. We don't modify the _occurrences_. Apart from the tiresome inefficiency, it offends me that the binding sites and the occurrence sites differ, in an important way.
  • When code-generating, at the binding site of a let (or at top level) we make a CgIdInfo for each binding, which contains the Id from the binding site
  • At each _occurrence_ site we look up the CgIdInfo for that Id -- and we must be super-careful to use the Id from the CgIdInfo, and NOT the one at the occurrence site, because only the former has correct CafInfo.

What to do? It's not impossible as-is, provided it is very carefully documented. As a runtime check, I suppose we could make the CafInfo for an Id be a Maybe CafInfo with Nothing meaning "you should not be looking at me". (But that costs us at runtime.)

I think a better solution would be to add a CafInfo field to LFReEntrant. Or, better, since it already has a TopLevelFlag field, and CafInfo is only relevant for top-level things, just change the current TopLevelFlag to CgTopLevelFlag, where

data CgTopLevelFlag
  = CgNotTopLevel
  | CgTopLevel CafInfo

Now easily get the CAF info to where it is needed. Would that make sense?

It's extra refactoring, yes, but it seems cleaner.

osa1 updated this revision to Diff 19211.Dec 21 2018, 3:19 AM
  • Update CafInfos in HomeModInfo/ModDetails/TypeEnv
osa1 edited the summary of this revision. (Show Details)Dec 21 2018, 3:23 AM
simonpj added inline comments.Dec 21 2018, 3:53 AM
compiler/main/DriverPipeline.hs
237

Please explain WHY!! Refer to a Note explaining the moving parts.

242

Pass (and return) ModDetails, rather than just TypeEnv to updateTypeEnvCafInfos.

compiler/main/HscTypes.hs
2224

Or perhpas just NameEnv Id. Maps the Name to the Id with the correct CAFinfo. Then you can simply replace in the above code, rather than doing setCafInfo. Fewer pairs, less updating of Ids.

What is making me uncomfortable is that our current design looks like this:

  • We get the Name -> CafInfo map
  • We run over the top level binding, augmenting the CafInfo of the _binding sites_ of top level Ids. We don't modify the _occurrences_. Apart from the tiresome inefficiency, it offends me that the binding sites and the occurrence sites differ, in an important way.
  • When code-generating, at the binding site of a let (or at top level) we make a CgIdInfo for each binding, which contains the Id from the binding site
  • At each _occurrence_ site we look up the CgIdInfo for that Id -- and we must be super-careful to use the Id from the CgIdInfo, and NOT the one at the occurrence site, because only the former has correct CafInfo.

    What to do? It's not impossible as-is, provided it is very carefully documented. As a runtime check, I suppose we could make the CafInfo for an Id be a Maybe CafInfo with Nothing meaning "you should not be looking at me". (But that costs us at runtime.)

I agree this is a bit fragile. Let's at the very least have a test that will break if we get it wrong - I'm much happier relying on something that we proactively tell us if we break it than documentation that we might miss (but we should have docs too, of course).

I suppose the test will have to do -ddump-cmm and grep the result or something horrible like that, unless anyone can think of a better idea.

I think a better solution would be to add a CafInfo field to LFReEntrant. Or, better, since it already has a TopLevelFlag field, and CafInfo is only relevant for top-level things, just change the current TopLevelFlag to CgTopLevelFlag, where

data CgTopLevelFlag
  = CgNotTopLevel
  | CgTopLevel CafInfo

Now easily get the CAF info to where it is needed. Would that make sense?

It's extra refactoring, yes, but it seems cleaner.

I might be missing something, but how does that prevent us from accidentally using the CafInfo from the occurrence Id?

I might be missing something, but how does that prevent us from accidentally using the CafInfo from the occurrence Id?

We can grep for idCafInfo and see there are none!

Or, I suppose, TidyPgm could set the CAFinfo to error "No CAF info", to ensure that no one looks at it.

osa1 added a comment.Dec 21 2018, 4:44 AM

I might be missing something, but how does that prevent us from accidentally using the CafInfo from the occurrence Id?

@simonpj @simonmar what do you think about making IdInfo.cafInfo a Maybe CafInfo instead of CafInfo? That way we can leave caf info of non-imported ids Nothing (initially all ids have Nothing as caf info), and idCafInfo can panic instead of returning the default value when that happens.

We can later do the same thing for arity.

In D5432#150882, @osa1 wrote:

I might be missing something, but how does that prevent us from accidentally using the CafInfo from the occurrence Id?

@simonpj @simonmar what do you think about making IdInfo.cafInfo a Maybe CafInfo instead of CafInfo? That way we can leave caf info of non-imported ids Nothing (initially all ids have Nothing as caf info), and idCafInfo can panic instead of returning the default value when that happens.

We can later do the same thing for arity.

I think error "Don't look at me" is better for now. Less change; more efficient; and it's very much a belt-and-braces check that should never happen

osa1 added a comment.Dec 21 2018, 5:12 AM
In D5432#150882, @osa1 wrote:

I might be missing something, but how does that prevent us from accidentally using the CafInfo from the occurrence Id?

@simonpj @simonmar what do you think about making IdInfo.cafInfo a Maybe CafInfo instead of CafInfo? That way we can leave caf info of non-imported ids Nothing (initially all ids have Nothing as caf info), and idCafInfo can panic instead of returning the default value when that happens.

We can later do the same thing for arity.

Sorry I missed some comments -- phabricator loves to hide comments thinking that they're "old" (for some definition of "old"??). It seems like this is exactly what @simonpj suggested above, and I think it's a good idea. I should read rest of the comments that phabricator hide from me now ...

osa1 added a comment.Dec 21 2018, 5:30 AM

OK, finished reading the comments. @simonpj

Or, I suppose, TidyPgm could set the CAFinfo to error "No CAF info", to ensure that no one looks at it.

Why not just change vanillaCafInfo (and maybe rename it to make it clear that it makes caf info unavailable) to:

vanillaCafInfo :: CafInfo
vanillaCafInfo = pprPanic "vanillaCafInfo" (text "CafInfo for Id not available!")

I think that's the easiest way to make sure, with very little refactoring, that CafInfos won't be read before being set.

Why not just change vanillaCafInfo

That's probably fine.

osa1 updated this revision to Diff 19220.Dec 21 2018, 8:53 AM
  • Remove outdated comment

We can grep for idCafInfo and see there are none!

But don't we still need to do that for imported Ids?

(I've slightly lost track of the discussion, just ignore me if this is superseded)

But don't we still need to do that for imported Ids?

You're right: it'll be where we do getCgIdInfo on an occurrence find it is not in the local_binds (this is StgCmmEnv line 125 or so). Then, yes, we'll need to do a idCafInfo, but it'll be very clear, right there, that it's for an imported thing.

osa1 added a comment.Dec 21 2018, 9:21 AM

I started implementing this. There are some use sites of vanillaIdInfo that may still need MayHaveCafRefs as CafInfo so I have to review all use sites first. Here's the list of all uses of vanillaIdInfo, with whether they should have erroring CafInfo or not after the refactoring:

  • Var.mkCoVar: Coercion variables shouldn't need caf info, so error
  • Id.mkLocalCoVar: Error for the same reason
  • TcIface.tcIdInfo: Error, we should explicitly set caf info here (which we already do)
  • TidyPgm.trimThing: Error. This seems to throw away information that won't be used later in the compilation, so if we use caf info after this point it should fail.
  • Runtime error ids in MkCore: These should be non-CAFFY.
  • CoreTidy.tidyIdBndr: This is only called on non-top-level binders so caf info should error (I don't think we should be using caf infos of non-top-level ids).
  • CoreTidy.tidyLetBndr: Same as above.
  • WwLib.sanitiseCaseBndr: Same, non-top-level binder.
  • SimplMonad.newJoinId: I think join ids can't be top level so same as above.

These I don't know yet:

  • Id.mkVanillaGlobal
  • Id.mkLocalId
  • Id.mkExportedLocalId
  • Id.mkExportedVanillaId
  • TidyPgm.tidyTopIdInfo: This should probably maintain the old caf info (currently it resets it to the default)
  • TidyPgm.globaliseAndTidyId: This very explicitly resets caf info, but I think it shouldn't touch it? Is this a bug?
  • Exitify.exitifyRec
  • SetLevels.abstractVars
osa1 edited the summary of this revision. (Show Details)Dec 22 2018, 1:32 AM
osa1 edited the summary of this revision. (Show Details)Dec 24 2018, 12:41 AM
osa1 added a comment.Dec 24 2018, 1:16 AM

I started doing the refactoring. I currently have cafInfo :: Maybe CafInfo (instead of putting error in the field, becuase this version makes it easier to debug as I can get call stacks by adding HasCallStack to idCafInfo and call sites), and I realized that this comment

I think there may be more uses of idCafInfos. Simply searching in the source code shows that

I looked at StgCmmBind; the idCafInfo is used solely to pass (via mkLocalClosureLabel) to IdLabel. If IdLabel didn't have a CafInfo in it, we would not need this.

Ditto StgCmmCon, StgCmmEnv, StgCmmClosure.

Is not quite right. In StgCmmClosure we have this code:

getCallMethod dflags name id (LFReEntrant _ _ arity _ _) n_args _v_args _cg_loc
              _self_loop_info
  | n_args == 0 -- No args at all
  && not (gopt Opt_SccProfilingOn dflags)
     -- See Note [Evaluating functions with profiling] in rts/Apply.cmm
  = ASSERT( arity /= 0 ) ReturnIt
  | n_args < arity = SlowCall        -- Not enough args
  | otherwise      = DirectEntry (enterIdLabel dflags name (idCafInfo id)) arity

...

enterIdLabel :: DynFlags -> Name -> CafInfo -> CLabel
enterIdLabel dflags id c
  | tablesNextToCode dflags = mkInfoTableLabel id c
  | otherwise               = mkEntryLabel id c

This uses idCafInfos of non-top level ids too. For example, in this binding:

GHC.CString.unpackCString# [InlPrag=NOINLINE CONLIKE]
  :: GHC.Prim.Addr# -> [GHC.Types.Char]
[GblId, Arity=1, Str=<S,U>, Unf=OtherCon []] =
    \r [addr_sGl]
        let {
          unpack_sGm [Occ=LoopBreaker] :: GHC.Prim.Int# -> [GHC.Types.Char]
          [LclId, Arity=1, Str=<S,U>, Unf=OtherCon []] =
              \r [nh_sGn]
                  case indexCharOffAddr# [addr_sGl nh_sGn] of ch_sGo [Occ=Once] {
                    __DEFAULT ->
                        let {
                          sat_sGr [Occ=Once] :: [GHC.Types.Char]
                          [LclId] =
                              \u []
                                  case +# [nh_sGn 1#] of sat_sGq [Occ=Once] {
                                    __DEFAULT -> unpack_sGm sat_sGq;
                                  }; } in
                        let {
                          sat_sGp [Occ=Once] :: GHC.Types.Char
                          [LclId] =
                              CCCS GHC.Types.C#! [ch_sGo];
                        } in  : [sat_sGp sat_sGr];
                    '\NUL'# -> [] [];
                  };
        } in  unpack_sGm 0#;

We no longer assing a CafInfo to unpack_sGm becuase it's not top-level, but we call getCallMethod on this id.

@simonmar any ideas about this? Do we really need CafInfos of non-top-level ids too? We can distinguish top-level-bound ids from non-top-level-bound ids in this code (there's a field for this in LFReEntrant), so for top-level ids we can call idCafInfo as before, for others can we assume CAFFY, or can we use other fields of LFReEntrant to determine CafInfo?

osa1 added a comment.Dec 24 2018, 2:31 AM

sat_sGr in the same binding is also causing problems, because we call mkClosureInfoTableLabel on it, which calls idCafInfo. The CafInfo is again passed to mkInfoTableLabel so this is quite similar to the example above.

I don't think we need CAF-info on non-top-level Ids. Here is why.

The ultimate goal is to build correct Static Reference Tables (SRT). For every blob of code
(including the code for non-top-level closures), we need an SRT. The SRT contains an
entry for all the static, top-level closures that must be kept alive if that code
can be executed. We can find all such closures by looking through the code for
references to top-level closures, or their fast entry points etc.

We don't need to look for references to the code for non-top-level closures.
for example

cx = length [1..100]  -- A CAF

f x = let g = \y. ...cx ...x...
          h = \z.  z + (g 5)
      in ...

Now, the call (g 4) will be a fast-call to the entry code for
g; and g certainly refers to the CAF cx. But in order to call
g we need a pointer to g's closure (see nodeMustPointToIt), and
_that_ will keep cx alive (via g's SRT). In contrast h does not
need an SRT at all.

So all this work is wasted. As I said in this comment https://phabricator.haskell.org/D5432#150851, I propose getting rid of the CafInfo field of IdLabel entirely. Did you try that?

osa1 added a comment.Dec 24 2018, 6:18 AM

Hmm, I guess that makes sense, but I need to think more about this (I still don't understand Cmm generation too well ..). I'll try removing CafInfo from IdLabel and see how it goes. In the meantime, here's what I've got so far: https://github.com/osa1/ghc/commit/f377f048fef88d8f01414d34a913ed18798a7ba6 This makes cafInfo field Maybe, then initializes it as Nothing. The failures are as reported in my previous comments.

osa1 added a comment.Dec 24 2018, 10:03 AM

So all this work is wasted. As I said in this comment https://phabricator.haskell.org/D5432#150851, I propose getting rid of the CafInfo field of IdLabel entirely. Did you try that?

I started doing that, but I'm not sure how to implement cafAnal, more specifically cafTransfers needs to get CAFFY labels in a CmmBlock. Any ideas on this?

osa1 updated this revision to Diff 19238.Dec 24 2018, 11:40 PM
  • Rebase, enable panic in StgCafAnal again
osa1 edited the summary of this revision. (Show Details)Dec 24 2018, 11:43 PM
osa1 added a comment.EditedDec 25 2018, 12:39 AM
In D5432#151106, @osa1 wrote:

So all this work is wasted. As I said in this comment https://phabricator.haskell.org/D5432#150851, I propose getting rid of the CafInfo field of IdLabel entirely. Did you try that?

I started doing that, but I'm not sure how to implement cafAnal, more specifically cafTransfers needs to get CAFFY labels in a CmmBlock. Any ideas on this?

I've been doing some code reading, here's another way to say the same thing: in cafAnal we need to generate a map from Label to a set of Labels that are CAFFY. How do we know which labels are CAFFY? Currently this is recorded in CLabel (in IdLabel). If we remove this we need to somehow get this information from somewhere else. I don't think adding CafInfo field to TopLevelFlag or LFReEntrant would work becuase as far as I can see by the time we're in Cmm we lose CgIdInfos and Ids and work with ULabels (for branching and jumps) and CmmRegs.

Where are we on this work? I've gotten lost? If not complete, perhaps it would be helpful to summarise the state of play, with pointer to the key Notes, wiki pages, or whatever? Thansk!

osa1 added a comment.Jan 8 2019, 8:40 AM

Where are we on this work?

The refactoring plan did not quite work because some of our assumptions turned
out to be wrong. We assumed two things:

  • We only need CafInfos of binders (not occurances!)
  • We only need CafInfos of top-level binders (so no need to assign CafInfo to non-top level binders)

The first assumption is wrong because getCallMethod is called on occurances, and it
looks for CafInfos. So we need CafInfos on occurances too.

The second assumption is wrong because in CmmBuildInfoTables we look for
CafInfo of labels, some of which are derived from non-top-level binders. So to
be able to generate a IdLabel (which records CafInfo) for a non-top-level
binder we need CafInfo.

Finally, and maybe the worst of the problems, is that I think (but I'mn not 100%
sure) after computing CafInfos we need to update all unfoldings with those
CafInfos, because if another module imports the module we just compiled it'll
use some of the Ids, but they won't have a CafInfo.

At this point I'm not sure how to proceed ...

Btw @simonpj let me know if you want me to migrate this diff to Gitlab. I didn't
do it to avoid losing history.