Note [DataToTag overview]

Class `DataToTag` is defined like this, in GHC.Magic:

  type DataToTag :: forall {lev :: Levity}.
                    TYPE (BoxedRep lev) -> Constraint
  class DataToTag a where
     dataToTag# :: a -> Int#

`dataToTag#`, evaluates its argument and returns the index of the data
constructor used to build that argument.  Clearly, `dataToTag#` cannot
work on /any/ type, only on data types, hence the type-class constraint.

Users cannot define instances of `DataToTag`
(see `GHC.Tc.Validity.check_special_inst_head`).
Instead, GHC's constraint solver has built-in solving behaviour,
 implemented in `GHC.Tc.Instance.Class.matchGlobalInst`.

(#20441: This common handling of special typeclasses is a bit of a
mess and could use some love, and a dedicated Note.)

GHC solves a wanted constraint `DataToTag @{lev} dty`
when all of the following conditions are met:

C1: `dty` is an algebraic data type, i.e. `dty` matches any of:
       * a "data" declaration,
       * a "data instance" declaration,
       * a boxed tuple type
      But NOT
       * A "type data" declaration; see also wrinkle W2c
         of Note [Type data declarations] in GHC.Rename.Module.
       * A newtype; in principle we could accept newtypes that wrap
         an algebraic data type, but we do not do so.

C2: All of the constructors of that "data" or "data instance"
      declaration are in scope.  Otherwise, `dataToTag#` could be
      used to peek behind the curtain when used with an abstract
      data type whose constructors are intentionally hidden.

C3: `lev` is statically known, either Lifted or Unlifted:
      Otherwise the argument to `dataToTag#` would be
      representation-polymorphic and we couldn't do anything
      with it without Core Lint rightfully complaining.
      This guarantees invariant (DTT1) below.

It would be possible for GHC to generate custom code for each type, like
this:

   instance DataToTag [a] where
     dataToTag# []    = 0#
     dataToTag# (_:_) = 1#

But, to avoid all this boilerplate code, and improve optimisation opportunities,
GHC generates instances like this:

   instance DataToTag [a] where
     dataToTag# = dataToTagSmall#

using one of two dedicated primops: `dataToTagSmall#` and `dataToTagLarge#`.
(Why two primops? What's the difference? See wrinkles DTW4 and DTW5.)
Both primops have the following over-polymorphic type:

  dataToTagLarge# :: forall {l::levity} (a::TYPE (BoxedRep l)). a -> Int#

Every call to either primop that we generate should look like
(dataToTagSmall# @{lev} @ty) with two type arguments that satisfy
these conditions:

(DTT1) `lev` is concrete (either lifted or unlifted), not polymorphic.
   This is an invariant--we must satisfy this or Core Lint will complain.
   (This falls under situation 1 in GHC.Core.Lint's
   Note [Linting representation-polymorphic builtins].)

(DTT2) `ty` is always headed by a TyCon corresponding to one of the following:
   * A boxed tuple
   * A "data" declaration (but NOT a "type data" declaration)
   * The /representation type/ for a "data instance" declaration
     (but NOT the data family TyCon itself)

   This ensures that the DataCons associated with `ty` are easily
   accessible and safe to use in Core without running afoul of
   invariant I1 from Note [Type data declarations] in
   GHC.Rename.Module.  See Note [caseRules for dataToTag] in
   GHC.Core.Opt.ConstantFold for why this matters.

   While wrinkle DTW7 is unresolved, this cannot be a true invariant.
   But with a little effort we can ensure that every primop
   call we generate in a DataToTag instance satisfies this condition.

(DTT3) If the TyCon in wrinkle DTT2 is a "large data type" with more
   constructors than fit in pointer tags on the target, then the
   primop must be dataToTagLarge# and not dataToTagSmall#.
   Otherwise, the primop must be dataToTagSmall# and not dataToTagLarge#.
   (See wrinkles DTW4 and DTW5.)

These two primops have special handling in several parts of
the compiler:

H1. They have a couple of built-in rewrite rules, implemented in
    GHC.Core.Opt.ConstantFold.dataToTagRule

H2. The simplifier rewrites most case expressions scrutinizing their results.
    See Note [caseRules for dataToTag] in GHC.Core.Opt.ConstantFold.

H3. Each evaluates its argument.  But we want to omit this eval when the
    actual argument is already evaluated and properly tagged.  To do this,

    * We have a special case in GHC.Stg.EnforceEpt.Rewrite.rewriteOpApp
      ensuring that any inferred tag information on the argument is
      retained until code generation.

    * We generate code via special cases in GHC.StgToCmm.Expr.cgExpr
      instead of with the other primops in GHC.StgToCmm.Prim.emitPrimOp;
      tag info is not readily available in the latter function.
      (Wrinkle DTW4 describes what we generate after the eval.)

Wrinkles:

(DTW1) To guarantee (DTT2) we need to take care with data families.
  Consider  data family D a
            data instance D (Either p q) = D1 | D2 p q
  To solve the constraint
     [W] DataToTag (D (Either t1 t2))
  GHC uses the built-in instance
     instance DataToTag (D (Either p q)) where
        dataToTag# x = dataToTagSmall# @Lifted @(R:DEither p q)
                                       (x |> sym (ax:DEither p q))
  where `ax:DEither` is the axiom arising from the `data instance`:
    ax:DEither p q :: D (Either p q) ~ R:DEither p q

  Notice that we cast `x` before giving it to `dataToTagSmall#`, so
  that (DTT2) is satisfied.

(DTW2) Suppose we have module A (T(..)) where { data T = TCon }
  and in module B, the constraint `DataToTag T` is needed. Per
  condition C2, we only solve this constraint if `TCon` is in
  scope.  So we had better not later report a warning about the
  import of `TCon` being unused in module B!

  To avoid this simply call `addUsedDataCons` when creating a built-in
  DataToTag instance.

(DTW3) Similar to DTW2, consider this example:

    {-# LANGUAGE MagicHash #