Introduce PTR-tagging for big constructor families

Currently only small constructor families come into the benefit of pointer tagging.

In big fams, 1 is the tag that says "I am evaluated". I suggest to do best-effort pointer tagging on big families too by this scheme:

Ptr-tag 1..6 for the first 6 constructors, 7 would signify "look into the info table and branch on that tag". In the info table the tags will then be 6..(familySize - 1).

I have an implementation which I'll submit to fabricator soon.

TODOs: update wiki pages.

Trac metadata

Trac field	Value
Version	8.2.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

mentioned in issue #13861

changed weight to 5

added Tbug Trac import labels

See branch wip/T14373

https://phabricator.haskell.org/D4267 for historical reference only

But this is a very relevant comment: https://phabricator.haskell.org/D4267#119117

assigned to @ggreif

Trac metadata

Trac field	Value
Differential revisions	- → D4267

mentioned in issue #15155 (closed)

added Pnormal label

This is currently blocked on #15155 (closed).

How is #15155 (closed) blocking this?

It isn't blocked on #15155 (closed), it should be pretty independent of everything. I have a half-working branch, with the only snag in it that it relies on basic block ordering. It should be rewritten to not fall through, but create an out-of-line basic block, that later gets nicely placed by @AndreasK's layouter.

Thanks. Can you also point us to your branch?

Sure. As stated by SPJ above: https://gitlab.haskell.org/ghc/ghc/tree/wip/T14373

Removed the emitSwitch hack. Now I use conventional control-flow primitives, and hope that the asm-level branch eliminator will do a good job.

• The last thing missing is robust tests.
• Perf hints documentation
• Double switching explanation needs to be corrected

Review is taking place at !1742 (closed).

marked this issue as related to #15155 (closed)

added code generation label

added pointer tagging label

mentioned in issue #16970 (closed)

marked this issue as related to #16970 (closed)

mentioned in commit 2e34ad26

mentioned in commit c827c348

mentioned in merge request !1692 (closed)

This may worth being implemented for reasons other than performance. In #17088 (closed) we discovered that GC may have to tag untagged pointers (rather than just preserving existing tags), but we currently don't have a way of knowing a pointer's tag. Info tables have a field for "zero based constructor tag", but seeing a constructor with tag e.g. 4 we still can't tell what the tag should be without knowing the family size (e.g. if there are 20 constructors then the tag will be 1, otherwise it'll be 5).

If we implement this then for constructors the GC can just do

tag = min(info_tbl->srt, max_tag)

and it'd work regardless of the family size.