Opened 21 months ago

Last modified 9 months ago

#14620 new bug

Polymorphic functions not easily recognized as join points

Reported by: dfeuer Owned by:
Priority: normal Milestone: 8.10.1
Component: Compiler Version: 8.2.2
Keywords: Cc: nomeata
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #14610 Differential Rev(s):
Wiki Page:

Description

This grew out of ticket:14610#comment:3. If I write

foo :: forall a. (Int -> Bool) -> Int -> a -> a
foo p = go
  where
    go :: Int -> a -> a
    go !n a
      | p n = a
      | otherwise = go (n + 1) a

then I get

foo
  = \ (@ a_aYZ)
      (p_aWO :: Int -> Bool)
      (eta_B2 :: Int)
      (eta1_B1 :: a_aYZ) ->
      case eta_B2 of { GHC.Types.I# ww1_s1bZ ->
      joinrec {
        $wgo_s1c1 [InlPrag=NOUSERINLINE[0], Occ=LoopBreaker]
          :: GHC.Prim.Int# -> a_aYZ -> a_aYZ
        [LclId[JoinId(2)], Arity=2, Str=<L,U><S,1*U>, Unf=OtherCon []]
        $wgo_s1c1 (ww2_X1cu :: GHC.Prim.Int#) (w_s1bW :: a_aYZ)
          = case p_aWO (GHC.Types.I# ww2_X1cu) of {
              False -> jump $wgo_s1c1 (GHC.Prim.+# ww2_X1cu 1#) w_s1bW;
              True -> w_s1bW
            }; } in
      jump $wgo_s1c1 ww1_s1bZ eta1_B1
      }

But if I make go polymorphic,

foo :: (Int -> Bool) -> Int -> a -> a
foo p = go
  where
    go :: Int -> b -> b
    go !n a
      | p n = a
      | otherwise = go (n + 1) a

I get a wrapper and this worker:

T14610.$wfoo
  = \ (@ a_s1cm)
      (w_s1cn :: Int -> Bool)
      (ww_s1cs :: GHC.Prim.Int#)
      (w1_s1cp :: a_s1cm) ->
      letrec {
        $wgo_s1cl [InlPrag=NOUSERINLINE[0], Occ=LoopBreaker]
          :: forall b. GHC.Prim.Int# -> b -> b
        [LclId, Arity=2, Str=<L,U><S,1*U>, Unf=OtherCon []]
        $wgo_s1cl
          = \ (@ b_s1ce) (ww1_s1cj :: GHC.Prim.Int#) (w2_s1cg :: b_s1ce) ->
              case w_s1cn (GHC.Types.I# ww1_s1cj) of {
                False -> $wgo_s1cl @ b_s1ce (GHC.Prim.+# ww1_s1cj 1#) w2_s1cg;
                True -> w2_s1cg
              }; } in
      $wgo_s1cl @ a_s1cm ww_s1cs w1_s1cp

This distinction remains as let vs. let-no-escape in STG. As Joachim Breitner's comments seem to suggest, we could probably recognize this by applying the static argument transformation to the type argument of go. But we don't currently have any machinery for doing that, I don't think. Furthermore, that would fail with polymorphic recursion even if the only type changes are from newtype. That said, the SAT approach would presumably help when the worker has a non-essential type signature for clarity.

Change History (9)

comment:1 Changed 21 months ago by bgamari

Blocking: 14618 added

comment:2 Changed 21 months ago by bgamari

Blocking: 14610 added

comment:3 Changed 21 months ago by dfeuer

Blocking: 14610 removed

comment:4 Changed 21 months ago by bgamari

Blocking: 14610 added; 14618 removed

comment:5 Changed 21 months ago by bgamari

Blocking: 14610 removed

comment:6 Changed 21 months ago by simonpj

The reason we don't make a join point for go is explained in the comment on Type.isValidJoinPointType:

-- | Determine whether a type could be the type of a join point of given total
-- arity, according to the polymorphism rule. A join point cannot be polymorphic
-- in its return type, since given
--   join j @a @b x y z = e1 in e2,
-- the types of e1 and e2 must be the same, and a and b are not in scope for e2.
-- (See Note [The polymorphism rule of join points] in CoreSyn.) 
..
isValidJoinPointType :: JoinArity -> Type -> Bool

The problem described by the ticket is in Note [Excess polymorphism and join points]:

Note [Excess polymorphism and join points]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In principle, if a function would be a join point except that it fails
the polymorphism rule (see Note [The polymorphism rule of join points] in
CoreSyn), it can still be made a join point with some effort. This is because
all tail calls must return the same type (they return to the same context!), and
thus if the return type depends on an argument, that argument must always be the
same.

For instance, consider:

  let f :: forall a. a -> Char -> [a]
      f @a x c = ... f @a y 'a' ...
  in ... f @Int 1 'b' ... f @Int 2 'c' ...

(where the calls are tail calls). `f` fails the polymorphism rule because its
return type is [a], where [a] is bound. But since the type argument is always
'Int', we can rewrite it as:

  let f' :: Int -> Char -> [Int]
      f' x c = ... f' y 'a' ...
  in ... f' 1 'b' ... f 2 'c' ...

and now we can make f' a join point:

  join f' :: Int -> Char -> [Int]
       f' x c = ... jump f' y 'a' ...
  in ... jump f' 1 'b' ... jump f' 2 'c' ...

It's not clear that this comes up often, however. TODO: Measure how often and
add this analysis if necessary.

SAT could help here. In the example of the ticket, SAT would give

T14610.$wfoo
  = \ (@ a_s1cm)
      (w_s1cn :: Int -> Bool)
      (ww_s1cs :: GHC.Prim.Int#)
      (w1_s1cp :: a_s1cm) ->
      letr {
        $wgo_s1cl
          = \ (@ b_s1ce) (ww1_s1cj :: GHC.Prim.Int#) (w2_s1cg :: b_s1ce) ->
            letrec wsat = \ (ww1_s1cj :: GHC.Prim.Int#) ->
                          case w_s1cn (GHC.Types.I# ww1_s1cj) of {
                             False -> wsat (GHC.Prim.+# ww1_s1cj 1#)
                             True -> w2_s1cg
            in wsat ww1_s1cj
              }; } in
      $wgo_s1cl @ a_s1cm ww_s1cs w1_s1cp}}}

Now wsat will turn into a joinrec; and $wgo_s1cl will inline at its (unique) call site.

But SAT won't necessarily nail it. Two difficulties:

  • SAT (activated by -fstatic-argument-transformation, see StaticArgumentTransformation), dones't SAT-ify $wgo because it only has one free variable, so SAT's usual criteria aren't satisfied.
  • There might be many calls to $wgo, so its new non-recursive definition won't get inlined, and things will not be so good. But, for things that could be join points, all the calls will be at the same type. We could try spotting that.

Notice also that loopification (Trac #14068) would effectively do much the same transformation as SAT, provided

  • loopification fired not only when the body call was not in tail position, but also if the isValidJoinPointType test failed.
  • loopification abstracted only over type variables not mentioned in the return type

So yes, I think we could make some progress here.

Last edited 21 months ago by simonpj (previous) (diff)

comment:7 Changed 21 months ago by simonpj

commit f3a0fe2da0c3da597cc65afb0e362eb436be5498
Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Tue Jan 2 17:08:16 2018 +0000

    Comments about join point types
    
    ...provked by #14620

comment:8 Changed 15 months ago by bgamari

Milestone: 8.6.18.8.1

comment:9 Changed 9 months ago by osa1

Milestone: 8.8.18.10.1

Bumping milestones of low-priority tickets.

Note: See TracTickets for help on using tickets.