Opened 6 years ago

Closed 4 years ago

#5949 closed bug (fixed)

Demand analysis attributes manifestly wrong demand type

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

Description (last modified by simonpj)

Consider:

e :: (Int, Int) -> Int -> (Int, Int)
e x y = x `seq` if y > 10
        then x
        else e x (y + 1)

After worker/wrapper we get:

Rec {
CPR2.$we [Occ=LoopBreaker]
 :: (GHC.Types.Int, GHC.Types.Int)
    -> GHC.Prim.Int# -> (# GHC.Types.Int, GHC.Types.Int #)
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType S(AA)L,
 Unf=OtherCon []]
CPR2.$we =
 \ (w_srv :: (GHC.Types.Int, GHC.Types.Int))
   (ww_srt :: GHC.Prim.Int#) ->
   case GHC.Prim.># ww_srt 10 of _ {
     GHC.Types.False ->
       case GHC.Prim.+# ww_srt 1 of sat_ssS { __DEFAULT ->
       CPR2.$we w_srv sat_ssS
       };
     GHC.Types.True ->
       case w_srv of _ { (ww2_srA, ww3_srB) -> (# ww2_srA, ww3_srB #) }
   }
end Rec }

The demand type S(AA) is entirely wrong because the box is unused (so it should be U(AA)) and because the two components are not absent -- they are used.

This leads to the worker/wrapper transformation being insufficiently agressive. This bites in practice with examples like:

d :: M.Map Int Int -> (Int, Int)
d m = M.foldrWithKey' (\k v (a, b) -> if k + v > 2 then (a, b) else
(b, a)) (0, 1) m

Which generates this inner loop:

Rec {
CPR2.$wgo2 [Occ=LoopBreaker]
 :: (GHC.Types.Int, GHC.Types.Int)
    -> Data.Map.Base.Map GHC.Types.Int GHC.Types.Int
    -> (# GHC.Types.Int, GHC.Types.Int #)
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType S(AA)S,
 Unf=OtherCon []]
CPR2.$wgo2 =
 \ (w_srS :: (GHC.Types.Int, GHC.Types.Int))
   (w1_srQ :: Data.Map.Base.Map GHC.Types.Int GHC.Types.Int) ->
   case w1_srQ of _ {
     Data.Map.Base.Tip ->
       case w_srS of _ { (ww1_srW, ww2_srX) -> (# ww1_srW, ww2_srX #) };
     Data.Map.Base.Bin rb_st1 kx_ss3 x_ssa l_ssk r_ss6 ->
       case kx_ss3 of _ { GHC.Types.I# x1_ssd ->
       case CPR2.$wgo2 w_srS r_ss6 of _ { (# ww1_ssi, ww2_ssh #) ->
       case x_ssa of _ { GHC.Types.I# y_sse ->
       case GHC.Prim.+# x1_ssd y_sse of sat_st0 { __DEFAULT ->
       case GHC.Prim.># sat_st0 2 of _ {
         GHC.Types.False ->
           let {
             sat_ssZ :: (GHC.Types.Int, GHC.Types.Int)
             [LclId]
             sat_ssZ = (ww2_ssh, ww1_ssi) } in
           CPR2.$wgo2 sat_ssZ l_ssk;
         GHC.Types.True ->
           let {
             sat_st6 :: (GHC.Types.Int, GHC.Types.Int)
             [LclId]
             sat_st6 = (ww1_ssi, ww2_ssh) } in
           CPR2.$wgo2 sat_st6 l_ssk
       }
       }
       }
       }
       }
   }
end Rec }

Note that it allocates a pair every go around the loop. If we just ran the demand analyser on this code again we could eliminate this allocation, but the demand analyser shouldn't be generating code which has these manifest problems.

One way to fix this is to change the ending of dmdTransform to read:

   if isTopLevel top_lvl
    then fn_ty -- Don't record top level things
    else case dmd of
           Box (Eval (Poly Abs)) | DmdType _ _ res <- fn_ty,
returnsCPR res -> addVarDmd fn_ty var (Eval (Poly lazyDmd))
           _
     -> addVarDmd fn_ty var dmd

But this is a hack. Better suggestions welcome.

Change History (5)

comment:1 Changed 5 years ago by igloo

difficulty: Unknown
Milestone: 7.8.1

comment:2 Changed 4 years ago by simonpj

Description: modified (diff)

comment:3 Changed 4 years ago by simonpj

Owner: set to nomeata

Seems fixed; Joachim will add a perf test to make sure it stays fixed.

comment:4 Changed 4 years ago by Joachim Breitner <mail@…>

In 19e09df47f48707718150fb9b4b9135ec742bed2/ghc:

Add a test case for #5949

comment:5 Changed 4 years ago by nomeata

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.