Allow top-level string literals in Core (#8472)
ClosedPublic

Authored by akio on Oct 17 2016, 4:00 AM.

Details

Summary

This commits relaxes the invariants of the Core syntax so that a
top-level variable can be bound to a primitive string literal of type
Addr#.

This commit:

  • Relaxes the invatiants of the Core, and allows top-level bindings whose type is Addr# as long as their RHS is either a primitive string literal or another variable.
  • Allows the simplifier and the full-laziness transformer to float out primitive string literals to the top leve.
  • Introduces the new StgGenTopBinding type to accomodate top-level Addr# bindings.
  • Introduces a new type of labels in the object code, with the suffix "_bytes", for exported top-level Addr# bindings.
  • Makes some built-in rules more robust. This was necessary to keep them functional after the above changes.

This is a continuation of D2554.

Test Plan

./validate --slow

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
This revision now requires changes to proceed.Oct 28 2016, 2:16 AM
akio updated this revision to Diff 9401.Nov 13 2016, 10:25 PM
akio edited edge metadata.
  • Fix rules that were broken by the top-level string change
  • add Note about _bytes label
  • 80 chars
akio updated this revision to Diff 9402.Nov 13 2016, 10:48 PM
akio marked an inline comment as done.
akio edited edge metadata.
  • mention the comment 16 on Trac #8472 in perf/compiler/all.T
akio added a comment.Nov 13 2016, 10:50 PM

@simonmar

I wonder, how does GHCi handle top-level Addr# bindings? Does it just work? (If so, how/why?)

Before the generation of the byte code, all Addr# variables are inlined into their use sites. Actually this may not be ideal because (1) this won't work if the source language had an Addr# variable, and (2) it potentially duplicates data.

@simonpj

That's fine if that's ALL that's going on. Does that fully account for the size increase. If so, fine. Just add an explanation to that effect to the ticket, and point to it from the comment in the perf all.T file.

Done.

compiler/simplCore/SimplUtils.hs
1026 ↗(On Diff #9147)

I fixed the rules, and added a test (simplCore/should_compile/str-rules).

simonmar requested changes to this revision.Nov 14 2016, 3:13 AM
simonmar edited edge metadata.

Before the generation of the byte code, all Addr# variables are inlined into their use sites. Actually this may not be ideal because (1) this won't work if the source language had an Addr# variable, and (2) it potentially duplicates data.

This worries me quite a bit, because we use GHCi on very large codebases with a lot of strings.

How hard is it to support top-level Addr# bindings in GHCi?

This revision now requires changes to proceed.Nov 14 2016, 3:13 AM
akio added a comment.Nov 14 2016, 5:53 PM

@simonmar

This worries me quite a bit, because we use GHCi on very large codebases with a lot of strings.

That sounds like a fair concern, but I can't think of an actual case where this leads to a bad runtime behavior on GHCi.

How hard is it to support top-level Addr# bindings in GHCi?

I'm not sure, because I don't understand the GHCi code well. I imagine that at least ByteCodeGen and ByteCodeAsm need to be changed to deal with top-level Addr# bindings. And it'd somehow need to arrange that those strings are freed when the module is unloaded.

That sounds like a fair concern, but I can't think of an actual case where this leads to a bad runtime behavior on GHCi.

If it can't happen, what's the reasoning? Couldn't the simplifier lift out a string to the top level, then duplicate the reference to it by inlining?

And it'd somehow need to arrange that those strings are freed when the module is unloaded.

Actually we don't try to free strings right now (it's a bug, but not one that I've ever been motivated enough to fix)

akio added a comment.Nov 20 2016, 10:49 PM

@simonmar

If it can't happen, what's the reasoning? Couldn't the simplifier lift out a string to the top level, then duplicate the reference to it by inlining?

For this to cause duplication, the (boxed) binding that originally contained the literal also must have been inlined in multiple places. However, in this case, probably the current version of GHC (without this patch) also duplicates the boxed binding, which means duplicating the string literal as well.

This is certainly not a proof, but I tried to construct an example where this patch causes a code duplication that the current GHC doesn't, and I have been unable to do so.

I've gotten lost on this patch. Can we reset and summarise?

Our goal is simply to allow top-level string literal bindings. But the patch is quite long. Could you give a list summarising the knock-on consequences of this apparently simple decision?

Is there still an open issue about whether we can support top-level literal strings in GHCi?

Simon

compiler/coreSyn/CoreLint.hs
549

Explain! Notably: why do we allow variables; why do we not allow any literals other than MachStr?

compiler/simplCore/SimplUtils.hs
1026 ↗(On Diff #9402)

I'm actually doubtful that this special case is needed. Can you give an example?

PS: the list of consequential changes might be better done on the ticket than buried here in Phab

However, in this case, probably the current version of GHC (without this patch) also duplicates the boxed binding, which means duplicating the string literal as well.

Ok, so your argument is that this is no worse than what we have now? I guess that's probably true.

I would really much prefer it if we did this properly in GHCi, though. I don't think it's that hard:

  1. Collect all the top-level strings and allocate them with iservCmd hsc_env (MallocStrings strings). We already do something similar for C calls during byte-code generation.
  2. Build a mapping from the vars to the RemotePtrs we get back from MallocStrings, instead of the topStrings mapping you have
  3. When we find an instance of one of these things, instead of PUSH_UBX with a MachStr, we want to push the RemotePtr. I suppose we need a new kind of PUSH_UBX that can take a RemotePtr, or you could cheat and turn it into a MachWord.

Akio, Simon and I don't mean to seem discouraging here. Allowing top-level strings really fixes a long-standing problem, so I want to encourage you to persevere. You are doing great -- thank you.

Simon

akio updated this revision to Diff 9785.Dec 5 2016, 1:14 AM
akio edited edge metadata.
  • Revert a change to preInlineUnconditionally
akio updated this object.Dec 5 2016, 1:18 AM
akio edited edge metadata.
akio added a comment.Dec 5 2016, 1:23 AM

@simonpj

I've gotten lost on this patch. Can we reset and summarise?

Our goal is simply to allow top-level string literal bindings. But the patch is quite long. Could you give a list summarising the knock-on consequences of this apparently simple decision?

I put a list in the Summary field of this differential revision, because I thought it should go into the final commit message. Please let me know if you would rather like it in the Trac.

Akio, Simon and I don't mean to seem discouraging here.

I'm not being discouraged by your comments! They are very helpful, thank you.

@simonmar

I'll give it a try.

compiler/coreSyn/CoreLint.hs
549

It's explained in Note [CoreSyn top-level string literals], which is mentioned at the use sites of this function.

compiler/simplCore/SimplUtils.hs
1026 ↗(On Diff #9402)

You are right, removing this doesn't seem to break anything. I think I took this change without really understanding it when I merged @gridaphobe's code.

I have reverted this change.

gridaphobe added inline comments.Dec 5 2016, 4:20 AM
compiler/simplCore/SimplUtils.hs
1026 ↗(On Diff #9402)

I believe I added this because preinlineUnconditionally was immediately undoing the floating of string literals.

If it's not actually needed that's great! But it might be worth a spot check of the Core for T8472?

Relaxes the invatiants of the Core, and allows top-level bindings whose type is Addr# as long as their RHS is either a primitive string literal or another variable.

Why "or another variable"?

I put a list in the Summary field of this differential revision, because I thought it should go into the final commit message. Please let me know if you would rather like it in the Trac.

Could you make a Note (maybe in CoreSyn or Literal that gives an overview of all the moving parts. Much as the summary, perhaps with an example or two

compiler/coreSyn/CoreUtils.hs
1586

Why not use this in CoreLint? Also this one only allows literals, not "literals or variables". (I prefer just literals.)

bgamari requested changes to this revision.Dec 9 2016, 10:16 PM
bgamari edited edge metadata.

Requesting changes due to Simon's request for a note. I'll try to do another pass over this over the weekend.

This revision now requires changes to proceed.Dec 9 2016, 10:16 PM

Here's another round of comments.

Thanks for sticking with this, @akio!

compiler/coreSyn/CoreLint.hs
551

Why do we allow Var here?

compiler/coreSyn/CoreUtils.hs
1586

It would be nice to hear the reasoning for this.

compiler/ghci/ByteCodeGen.hs
92

It would be nice to have a short Note summarizing how the bytecode generator deals with these.

compiler/simplCore/Simplify.hs
629

Perhaps add a reference to Note [CoreSyn top-level string literals].

testsuite/tests/simplCore/should_compile/str-rules.hs
17

A few comments explaining what precisely we are looking for in this test would be helpful.

gridaphobe added inline comments.Dec 14 2016, 10:19 PM
compiler/coreSyn/CoreLint.hs
551

As I recall, we would occasionally end up with chains of top-level binders like the following.

foo = "foo"#
foo2 = foo

bar = ... foo2 ...

The foo2 binder would be flagged as bogus by CoreLint even though it's perfectly harmless (and presumably will eventually be simplified away entirely).

Akio/Erik where are we on this. It seems so nearly finished that it'd be great just to get it done! Are you stalled on input from anyone?

Thanks for doing this

Simon

compiler/coreSyn/CoreSyn.hs
370

I totally missed "and a single variable". Give an example. Specifically, we permit a top level binding for x :: Addr#, if it is of form

x = "foo#"

or

x = y

Can you explain why we need the x=y case? I'd prefer not to have it at all. What the compelling reason?

simonmar requested changes to this revision.Dec 19 2016, 6:03 AM
simonmar edited edge metadata.

GHCi changes are still pending here (see https://phabricator.haskell.org/D2605#79832)

GHCi changes are still pending here (see https://phabricator.haskell.org/D2605#79832)

OK... akio, do you know how to proceed? This is blocking D1259, so it'd be great to tie it up. Thanks!

Simon

akio added a comment.Dec 22 2016, 12:49 AM

@simonpj Sorry about being slow. I think I know what to do about the GHCi issue. I'm hoping that I can finish implementing this and address the other comments in a few days.

compiler/coreSyn/CoreUtils.hs
1586

The reason is that the CSE pass tends to leave bindings of the form v = v1 :: Addr#. This fact is mentioned at the end of the Node [CoreSyn top-level string literals].

Perhaps it's better to change the CSE code not to do this, but it was not obvious to me how to do that.

akio updated this revision to Diff 10184.Dec 26 2016, 12:35 AM
akio edited edge metadata.
  • ghci: allocate one RemotePtr for each top-level Addr# binding
  • More comments
akio marked 3 inline comments as done.Dec 26 2016, 12:40 AM

Could you make a Note (maybe in CoreSyn or Literal that gives an overview of all the moving parts. Much as the summary, perhaps with an example or two

I added Note [Compilation plan for top-level string literals] in CoreSyn.hs

compiler/coreSyn/CoreLint.hs
551
akio updated this revision to Diff 10185.Dec 26 2016, 12:42 AM
akio edited edge metadata.
  • Remove duplicate comment

OK I've suggested how to fix the "or Var" thing, so now we can have just literals on the RHS, which has downstream simplifications.

Add a predicate isLitString (or something that) and use it.

Nearly done!!

compiler/coreSyn/CoreUtils.hs
1586

Oh I see. Well, the solution is sure to fix CSE, not to complicate Core! (If we found lots of places where having a variable on the RHS was useful, then I'd think again, but there is only one.)

There are good reasons for CSE to leave behind these trivial bindings; see Note [Top level and postInlineUnconditionally] in SimplUtils`. But when CSE sees

x = "foo"#
y = "foo"#
...x...y...x...y....

it should, I think, produce

x = "foo"#
y = "foo"#
..x..x..x..x

which will satisfy Lint; and then y will be dropped as dead code.

How to do this? Just make a special case in handling top level bindings of CSE. Something like

cseProgram binds = snd (mapAccumL cseTopBind emptyCSEnv binds)

cseTopBind env (NonRec b e)
  | Lit (MachStr _) <- e
  = (env2, NonRec b2, e)  -- See Note [Take care with literal strings]
  where
    e1                = tryForCSE env e
    (env1, b1)        = addBinder env b
    (env2, (b2, _e2)) = addBinding env1 b b1 e1

cseTopBind env bind = cseBind env bind

The GHCi changes look fine, so I'm happy with this once @simonpj's latest CSE suggestion is addressed.

bgamari requested changes to this revision.Jan 5 2017, 3:40 PM
bgamari edited edge metadata.

Bumping out of review queue due to @simonpj's CSE request.

This revision now requires changes to proceed.Jan 5 2017, 3:40 PM
akio updated this revision to Diff 10324.Jan 6 2017, 6:10 PM
akio edited edge metadata.
  • Disallow Addr# variables in the RHS of top-level bindings
akio added a comment.Jan 6 2017, 6:13 PM

@simonpj I've updated the code to simplify the invariant. Thank you for your help!

simonpj accepted this revision.Jan 9 2017, 3:52 AM
simonpj edited edge metadata.

Looks much better. Let's land this. Thanks!

Simon

compiler/simplCore/CSE.hs
271

Rather than defining a new function cseRhsBind, I'd just make a new cseTopBind function, as shown in my comment above. That means that the extra work is not even attempted for nested bindings. (By all means call cseBind in the special case to avoid duplicating cseBind's code)

compiler/simplCore/SimplEnv.hs
400

Refer to a Note somewhere

akio marked an inline comment as done.Jan 9 2017, 4:13 AM
akio added inline comments.
compiler/simplCore/CSE.hs
271

I tried that approach initially, but it created more code duplication because it had to handle both Rec and NonRec cases.

akio updated this revision to Diff 10350.Jan 9 2017, 4:14 AM
akio edited edge metadata.
  • Add a reference to a Note
bgamari accepted this revision.Jan 18 2017, 5:13 PM
bgamari edited edge metadata.

Alright, looks reasonable to me. Let's merge this!

This has required some effort to rebase but I think I have it under control.

This revision was automatically updated to reflect the committed changes.