Opened 9 years ago

Closed 9 years ago

Last modified 6 years ago

#4962 closed bug (fixed)

Dead code fed to CorePrep because RULEs keep it alive spuriously

Reported by: batterseapower Owned by:
Priority: normal Milestone: 7.2.1
Component: Compiler Version: 7.0.1
Keywords: Cc: nfrisby
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by simonpj)

This ticket is split off from #4941.

I'm seeing output code that looks roughly like this in the final simplifier output:

let
      {-# RULES go (Just x) = $sgo_s1lg x #-}
      go = ... go ... $w$sgo ...
      $sgo_s1lg = ... $w$sgo_s1mv ...
      $w$sgo_s1mv = ... big ...
in ... $w$sgo_s1mv ...

This is bad because $sgo is will be dead for the purposes of code generation, but currently GHC will allocate a closure for it at runtime anyway.

What we should do is drop the dead binding once we have decided that it's not reachable via the exported RULES in the interface file.

I've confirmed that this patch achieves this effect (and eliminates the main source of increased allocations I was seeing in #4941):

hunk ./compiler/main/TidyPgm.lhs 22
+import OccurAnal        ( occurAnalysePgm )
hunk ./compiler/main/TidyPgm.lhs 43
+import qualified ErrUtils as Err
hunk ./compiler/main/TidyPgm.lhs 47
+import PprCore
hunk ./compiler/main/TidyPgm.lhs 322
+
+          -- Occurrence analyse the input program, assuming all local rules are off,
+          -- but retaining any bindings referred to by external rules.
+          -- Occurrence information may have improved since the last run of the
+          -- simplifier because some bindings will become dead once RULES are dropped.
+          --
+          -- The analysis itself will take care of dropping any newly-dead syntax.
+        ; Err.dumpIfSet_dyn dflags Opt_D_dump_occur_anal "BEFORE TidyPgm occurrence analysis" (pprCoreBindings binds)
+        ; binds <- return $ occurAnalysePgm Nothing ext_rules binds
+        ; Err.dumpIfSet_dyn dflags Opt_D_dump_occur_anal "TidyPgm occurrence analysis" (pprCoreBindings binds)
+
hunk ./compiler/simplCore/OccurAnal.lhs 393
-          rule_fvs   = idRuleVars bndr          -- See Note [Rule dependency info]
+          rule_fvs   = case occ_rule_act env of Nothing -> emptyVarSet; Just _ -> idRuleVars bndr          -- See Note [Rule dependency info]
+          -- FIXME: this is a terrible hack to try to have OccAnal drop bindings that are kept alive only due to rules at the CoreTidy stage

However the patch is a bit horrible: because attached RULES keep bindings alive in a LetRec even if the rules can never be activated (i.e. occ_rule_act env == Nothing) the bindings I want to be dropped never get dropped. The reason I consider my fix a hack is that just because the rules are inactive *now* doesn't mean that they will be inactive *later*.

A better approach would perhaps be to wait until the RULES are stripped from the binders entirely (e.g. OccAnal the output of CoreTidy). However, this is not straightforward because CoreTidy has globalised Ids, so OccAnaling the output says that all top level bindings have no FVs and hence turns all LetRecs into Lets!

Attachments (1)

RuleDeads.dpatch (91.8 KB) - added by batterseapower 9 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 9 years ago by batterseapower

Description: modified (diff)

comment:2 Changed 9 years ago by rl

Where is go used in your example? If it isn't, should it be dropped together with the rule?

Simon, didn't we discuss a similar problem a while ago? I vaguely remember that the conclusion was to drop all local rules in CoreTidy or CorePrep because they can't possibly be used anywhere but they keep things alive which would be dead otherwise. Max, wouldn't that solve this problem?

comment:3 Changed 9 years ago by simonpj

But in principle if this definition appears in the interface file, it may be inlined, and then the local RULES may spring into action, no? What you say about dropping local rules is true if the defn doesn't appear in the interface file.

Moreover, even if it does appear in the interface file, there is no need to feed those unused local let-bindings down through CorePrep and the code generator.

Hmm. Consider a defn that does appear in an interface file. We tidy it, and should presumably include RULES on local let-bindings. Now I suppose we want to walk over it again, dropping the RULES (and INLINE pragmas incidentally) and doing occurrence analysis.

The easy way to do this is as follows.

  • Don't change CoreTidy
  • In CorePrep dump all RULES and INLINE pragmas, whether top-level or nested. (Remember, interface files see the result of CoreTidy; CorePrep is the start of the codegen pipeline.)
  • Do occurrence analysis on the result oc CorePrep. This step will drop all dead code. NB that a top-level Id f mentioned only in a RULE for an externally-visible Id g will itself be marked as externally-visible by CoreTidy. And the occurrence ahalyser should keep all such things. (Need to check that.)

comment:4 Changed 9 years ago by rl

Ah, I thought the "drop local rules" bit happens after recording unfoldings for the interface file. So the rules and local bindings would appear in the unfolding but not in the actual code. Basically, I thought that what you are proposing is already happening.

comment:5 Changed 9 years ago by batterseapower

Roman: yes, sorry - let's say that go is used in the body of the let.

Simon: right. However, I'm not so sure that CoreTidy is actually preserving rules on local lets right now.. certainly nothing in tidyLetBndr seems to be using setIdSpecialisation or similar on the outgoing Id. I noticed this when writing the patch above and was actually wondering if was intentional...

I'm not sure if your proposed plan will work exactly as described because at any point after CoreTidy (including in the output of CorePrep) all top level binders are global ids and hence not reported as free variables. This causes the occurrence analyser to rewrite e.g.:

Rec {
f = ... f ... -- Note that f is a globalid!
}

To:

f = ... f ... -- Note that the Rec wrapper has vanished

comment:6 Changed 9 years ago by simonpj

OK, here's a refined plan

  • In CorePrep.cloneBndr, drop all unfoldings or rules
  • In CorePrep.deFloatTop, which is the bit right at the end of CorePrep, do occurAnalyseExpr on the RHS of each top-level binding.

The second step will just drop local dead let-bindings which are the ones you want to drop. For that, it's fine for the top level Ids to be GlobalIds.

I think you are right that local bindings don't currently retain their RUES in CoreTidy, but I think that's ok. It would only matter in a function that was going to be inlined. But if it's small enough to be inlined, it's not going to be big enough to have interesting specialisations on local let-bindings.

The reason we keep INLINE unfoldings is that Roman does write INLINE pragmas whose RHS has a local binding with an INLINE pragma. If he wrote local bindings with RULEs I'd have to retract the previous para -- but we have no way to write RULES for local defns (yet)!

Do you feel like trying this out?

Simon

comment:7 Changed 9 years ago by batterseapower

Sounds like a good plan, I'm trying it out.

comment:8 Changed 9 years ago by batterseapower

I've implemented and validated a patch that does this (attached). Pretty straightforward, and it seems to work.

Nofib results are:

            Min          +0.0%     -4.1%     +0.0%     +0.5%     +0.0%
            Max          +0.1%     +0.0%     +2.3%   +274.5%     +0.0%
 Geometric Mean          +0.0%     -0.1%     +0.4%    +14.3%     -0.0%

So a small but solid reduction in allocations (ignore the runtime results, I was doing something else with the machine at the time so they can't be trusted).

Changed 9 years ago by batterseapower

Attachment: RuleDeads.dpatch added

comment:9 Changed 9 years ago by igloo

Milestone: 7.2.1
Status: newpatch

comment:10 Changed 9 years ago by igloo

Resolution: fixed
Status: patchclosed

Applied, thanks!

comment:11 Changed 7 years ago by simonpj

Description: modified (diff)
difficulty: Unknown

comment:12 Changed 6 years ago by nfrisby

Cc: nfrisby added
Note: See TracTickets for help on using tickets.