Skip to content

OccurAnal: Stable unfoldings prevent contification

#22227 (comment 460568) made me aware of the following issue. Consider

f :: Integer -> Integer -> Integer
f x y = go y
  where
    go :: Integer -> Integer
    go 0 = x
    go n = go (n-1)
    {-# INLINE go #-}

We get the following optimised Core

f = \ (x_aih :: Integer) (y_aii :: Integer) ->
      letrec {
        go_sOg [InlPrag=INLINE (sat-args=1), Occ=LoopBreaker, Dmd=SC(S,L)]
          :: Integer -> Integer
        [LclId,
         Arity=1,
         Str=<1L>,
         Unf=Unf{Src=StableUser, TopLvl=False, Value=True, ConLike=True,
                 WorkFree=True, Expandable=True,
                 Guidance=ALWAYS_IF(arity=1,unsat_ok=False,boring_ok=False)
                 Tmpl= \ (ds_dKe :: Integer) ->
                         join {
                           $j_sOj [Occ=Once3T[0]] :: Integer
                           [LclId[JoinId(0)(Nothing)]]
                           $j_sOj
                             = go_sOg
                                 (GHC.Num.Integer.integerSub ds_dKe (GHC.Num.Integer.IS 1#)) } in
                         case ds_dKe of {
                           GHC.Num.Integer.IS x1_aKr [Occ=Once1!] ->
                             case x1_aKr of {
                               __DEFAULT -> jump $j_sOj;
                               0# -> x_aih
                             };
                           GHC.Num.Integer.IP _ [Occ=Dead] -> jump $j_sOj;
                           GHC.Num.Integer.IN _ [Occ=Dead] -> jump $j_sOj
                         }}]
        go_sOg
          = \ (ds_dKe :: Integer) ->
              case ds_dKe of wild_aKq {
                GHC.Num.Integer.IS x1_aKr ->
                  case x1_aKr of {
                    __DEFAULT -> go_sOg (GHC.Num.Integer.integerSub wild_aKq Lib.f1);
                    0# -> x_aih
                  };
                GHC.Num.Integer.IP x1_aKw ->
                  go_sOg (GHC.Num.Integer.integerSub wild_aKq Lib.f1);
                GHC.Num.Integer.IN x1_aO9 ->
                  go_sOg (GHC.Num.Integer.integerSub wild_aKq Lib.f1)
              }; } in
      go_sOg y_aii

As you can see, go wasn't turned into a join binding. That is entirely due to its stable unfolding and the way occurrence analysis analyses them.

Specifically, the call to occAnalRhs on the unfolding's RHS will zap all tail calls in adjustRhsUsage because mb_join_arity will of course start out as Nothing. Apparently that parameter is to support Note [Join points and unfoldings/rules], but that Note doesn't exactly capture the case of recursive occurrences inside the stable unfolding. go will only be discovered as a join point if its stable unfolding is analysed under the assumption that go already is a join point.

Perhaps @simonpj has a good idea what to do about this.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information