Skip to content

postInlineUnconditionally for join points causes multiple Simplifier iterations, and exponential code blowup

In the existing test perf/compiler/T13253-spj (a nice, small, easily-scalable test) we tend to get multiple simplifier iterations, in the Simplifier FinalPhase.

Reason:

  • postInlineUnconditionally is currently switched off altogether for join point, until FinalPhase.
  • Then it see something like 
    j1 x = ....
j2 x = ...j1
j3 x = ...j1
in
case p of
  .. -> j3 x
  .. -> j3 x
  .. -> j2 x
  • The OccInfo on j3 is OneOcc { n_br=2 }; so postInlineUconditinally may fire.
  • But the OccInfo on j1 is ManyOcc because it is used in the RHS of both j2 and j3. This is a shortcoming of the occurrence analyser (#22404 (closed)).
  • So j1 does not inline; but j3 does.
  • But now, in the next iteration of the Simplifer, the OccInfo on j1 is OneOcc, so it inlines.

In T13253-spj, this cascades and each iteration of the Simplifier inlines just one pair of join points. Worse, it's an exponential thing: each double the size of the case tree.

The only thing that currently stops it is that postInlineUnconditionally has an arbitrary n_br < 100 limit, so it stops when one of the join point has more than a hundred calls.

For the record, here is what it looks like, just before that FinalPhase simplification.

foo
  = \ (y_aI4 :: Int) (x_aI5 :: Bool) ->
      join {
        $j_sPz :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPz
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            GHC.Prim.tagToEnum# @Bool (GHC.Prim.># (GHC.Prim.+# x_aP5 1#) 0#)
            } } in
      join {
        $j_sPy :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPy
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            GHC.Prim.tagToEnum# @Bool (GHC.Prim.<# (GHC.Prim.+# x_aP5 1#) 0#)
            } } in
      join {
        $j_sPB :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPB
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 2#) 0# of {
              __DEFAULT -> jump $j_sPy;
              1# -> jump $j_sPz
            }
            } } in
      join {
        $j_sPA :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPA
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 2#) 0# of {
              __DEFAULT -> jump $j_sPy;
              1# -> jump $j_sPz
            }
            } } in
      join {
        $j_sPD :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPD
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 3#) 0# of {
              __DEFAULT -> jump $j_sPA;
              1# -> jump $j_sPB
            }
            } } in
      join {
        $j_sPC :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPC
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 3#) 0# of {
              __DEFAULT -> jump $j_sPA;
              1# -> jump $j_sPB
            }
            } } in
      join {
        $j_sPF :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPF
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 4#) 0# of {
              __DEFAULT -> jump $j_sPC;
              1# -> jump $j_sPD
            }
            } } in
      join {
        $j_sPE :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPE
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 4#) 0# of {
              __DEFAULT -> jump $j_sPC;
              1# -> jump $j_sPD
            }
            } } in
      join {
        $j_sPH :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPH
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 5#) 0# of {
              __DEFAULT -> jump $j_sPE;
              1# -> jump $j_sPF
            }
            } } in
      join {
        $j_sPG :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPG
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 5#) 0# of {
              __DEFAULT -> jump $j_sPE;
              1# -> jump $j_sPF
            }
            } } in
      join {
        $j_sPJ :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPJ
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 6#) 0# of {
              __DEFAULT -> jump $j_sPG;
              1# -> jump $j_sPH
            }
            } } in
      join {
        $j_sPI :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPI
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 6#) 0# of {
              __DEFAULT -> jump $j_sPG;
              1# -> jump $j_sPH
            }
            } } in
      join {
        $j_sPL :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPL
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 7#) 0# of {
              __DEFAULT -> jump $j_sPI;
              1# -> jump $j_sPJ
            }
            } } in
      join {
        $j_sPK :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPK
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 7#) 0# of {
              __DEFAULT -> jump $j_sPI;
              1# -> jump $j_sPJ
            }
            } } in
      join {
        $j_sPN :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPN
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 8#) 0# of {
              __DEFAULT -> jump $j_sPK;
              1# -> jump $j_sPL
            }
            } } in
      join {
        $j_sPM :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPM
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 8#) 0# of {
              __DEFAULT -> jump $j_sPK;
              1# -> jump $j_sPL
            }
            } } in
      join {
        $j_sPP :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPP
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 9#) 0# of {
              __DEFAULT -> jump $j_sPM;
              1# -> jump $j_sPN
            }
            } } in
      join {
        $j_sPO :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPO
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 9#) 0# of {
              __DEFAULT -> jump $j_sPM;
              1# -> jump $j_sPN
            }
            } } in
      join {
        $j_sPR :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPR
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 10#) 0# of {
              __DEFAULT -> jump $j_sPO;
              1# -> jump $j_sPP
            }
            } } in
      join {
        $j_sPQ :: Bool
        [LclId[JoinId(0)(Nothing)]]
        $j_sPQ
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 10#) 0# of {
              __DEFAULT -> jump $j_sPO;
              1# -> jump $j_sPP
            }
            } } in
      join {
        $j_sPT :: Bool
        [LclId[JoinId(0)(Nothing)],
         Unf=Unf{Src=<vanilla>, TopLvl=False,
                 Value=False, ConLike=False, WorkFree=False, Expandable=False,
                 Guidance=IF_ARGS [] 36 0}]
        $j_sPT
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.># (GHC.Prim.+# x_aP5 11#) 0# of {
              __DEFAULT -> jump $j_sPQ;
              1# -> jump $j_sPR
            }
            } } in
      join {
        $j_sPS :: Bool
        [LclId[JoinId(0)(Nothing)],
         Unf=Unf{Src=<vanilla>, TopLvl=False,
                 Value=False, ConLike=False, WorkFree=False, Expandable=False,
                 Guidance=IF_ARGS [] 36 0}]
        $j_sPS
          = case y_aI4 of { GHC.Types.I# x_aP5 ->
            case GHC.Prim.<# (GHC.Prim.+# x_aP5 11#) 0# of {
              __DEFAULT -> jump $j_sPQ;
              1# -> jump $j_sPR
            }
            } } in
      case x_aI5 of {
        False ->
          case y_aI4 of { GHC.Types.I# x_aPX ->
          case GHC.Prim.<# x_aPX 0# of {
            __DEFAULT -> jump $j_sPS;
            1# -> jump $j_sPT
          }
          };
        True ->
          case y_aI4 of { GHC.Types.I# x_aQ5 ->
          case GHC.Prim.># x_aQ5 0# of {
            __DEFAULT -> jump $j_sPS;
            1# -> jump $j_sPT
          }
          }
      }
Edited by Simon Peyton Jones
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information