never executed always true always false
    1 -----------------------------------------------------------------------------
    2 --
    3 -- Cmm optimisation
    4 --
    5 -- (c) The University of Glasgow 2006
    6 --
    7 -----------------------------------------------------------------------------
    8 
    9 module GHC.Cmm.Opt (
   10         constantFoldNode,
   11         constantFoldExpr,
   12         cmmMachOpFold,
   13         cmmMachOpFoldM
   14  ) where
   15 
   16 import GHC.Prelude
   17 
   18 import GHC.Cmm.Utils
   19 import GHC.Cmm
   20 import GHC.Utils.Misc
   21 
   22 import GHC.Utils.Panic
   23 import GHC.Platform
   24 
   25 import Data.Maybe
   26 
   27 
   28 constantFoldNode :: Platform -> CmmNode e x -> CmmNode e x
   29 constantFoldNode platform = mapExp (constantFoldExpr platform)
   30 
   31 constantFoldExpr :: Platform -> CmmExpr -> CmmExpr
   32 constantFoldExpr platform = wrapRecExp f
   33   where f (CmmMachOp op args) = cmmMachOpFold platform op args
   34         f (CmmRegOff r 0) = CmmReg r
   35         f e = e
   36 
   37 -- -----------------------------------------------------------------------------
   38 -- MachOp constant folder
   39 
   40 -- Now, try to constant-fold the MachOps.  The arguments have already
   41 -- been optimized and folded.
   42 
   43 cmmMachOpFold
   44     :: Platform
   45     -> MachOp       -- The operation from an CmmMachOp
   46     -> [CmmExpr]    -- The optimized arguments
   47     -> CmmExpr
   48 
   49 cmmMachOpFold platform op args = fromMaybe (CmmMachOp op args) (cmmMachOpFoldM platform op args)
   50 
   51 -- Returns Nothing if no changes, useful for Hoopl, also reduces
   52 -- allocation!
   53 cmmMachOpFoldM
   54     :: Platform
   55     -> MachOp
   56     -> [CmmExpr]
   57     -> Maybe CmmExpr
   58 
   59 cmmMachOpFoldM _ op [CmmLit (CmmInt x rep)]
   60   = Just $! case op of
   61       MO_S_Neg _ -> CmmLit (CmmInt (-x) rep)
   62       MO_Not _   -> CmmLit (CmmInt (complement x) rep)
   63 
   64         -- these are interesting: we must first narrow to the
   65         -- "from" type, in order to truncate to the correct size.
   66         -- The final narrow/widen to the destination type
   67         -- is implicit in the CmmLit.
   68       MO_SF_Conv _from to -> CmmLit (CmmFloat (fromInteger x) to)
   69       MO_SS_Conv  from to -> CmmLit (CmmInt (narrowS from x) to)
   70       MO_UU_Conv  from to -> CmmLit (CmmInt (narrowU from x) to)
   71       MO_XX_Conv  from to -> CmmLit (CmmInt (narrowS from x) to)
   72 
   73       _ -> panic $ "cmmMachOpFoldM: unknown unary op: " ++ show op
   74 
   75 
   76 -- Eliminate conversion NOPs
   77 cmmMachOpFoldM _ (MO_SS_Conv rep1 rep2) [x] | rep1 == rep2 = Just x
   78 cmmMachOpFoldM _ (MO_UU_Conv rep1 rep2) [x] | rep1 == rep2 = Just x
   79 cmmMachOpFoldM _ (MO_XX_Conv rep1 rep2) [x] | rep1 == rep2 = Just x
   80 
   81 -- Eliminate nested conversions where possible
   82 cmmMachOpFoldM platform conv_outer [CmmMachOp conv_inner [x]]
   83   | Just (rep1,rep2,signed1) <- isIntConversion conv_inner,
   84     Just (_,   rep3,signed2) <- isIntConversion conv_outer
   85   = case () of
   86         -- widen then narrow to the same size is a nop
   87       _ | rep1 < rep2 && rep1 == rep3 -> Just x
   88         -- Widen then narrow to different size: collapse to single conversion
   89         -- but remember to use the signedness from the widening, just in case
   90         -- the final conversion is a widen.
   91         | rep1 < rep2 && rep2 > rep3 ->
   92             Just $! cmmMachOpFold platform (intconv signed1 rep1 rep3) [x]
   93         -- Nested widenings: collapse if the signedness is the same
   94         | rep1 < rep2 && rep2 < rep3 && signed1 == signed2 ->
   95             Just $! cmmMachOpFold platform (intconv signed1 rep1 rep3) [x]
   96         -- Nested narrowings: collapse
   97         | rep1 > rep2 && rep2 > rep3 ->
   98             Just $! cmmMachOpFold platform (MO_UU_Conv rep1 rep3) [x]
   99         | otherwise ->
  100             Nothing
  101   where
  102         isIntConversion (MO_UU_Conv rep1 rep2)
  103           = Just (rep1,rep2,False)
  104         isIntConversion (MO_SS_Conv rep1 rep2)
  105           = Just (rep1,rep2,True)
  106         isIntConversion _ = Nothing
  107 
  108         intconv True  = MO_SS_Conv
  109         intconv False = MO_UU_Conv
  110 
  111 cmmMachOpFoldM platform mop [CmmLit (CmmInt x xrep), CmmLit (CmmInt y _)]
  112   = case mop of
  113         -- for comparisons: don't forget to narrow the arguments before
  114         -- comparing, since they might be out of range.
  115         MO_Eq _   -> Just $! CmmLit (CmmInt (if x_u == y_u then 1 else 0) (wordWidth platform))
  116         MO_Ne _   -> Just $! CmmLit (CmmInt (if x_u /= y_u then 1 else 0) (wordWidth platform))
  117 
  118         MO_U_Gt _ -> Just $! CmmLit (CmmInt (if x_u >  y_u then 1 else 0) (wordWidth platform))
  119         MO_U_Ge _ -> Just $! CmmLit (CmmInt (if x_u >= y_u then 1 else 0) (wordWidth platform))
  120         MO_U_Lt _ -> Just $! CmmLit (CmmInt (if x_u <  y_u then 1 else 0) (wordWidth platform))
  121         MO_U_Le _ -> Just $! CmmLit (CmmInt (if x_u <= y_u then 1 else 0) (wordWidth platform))
  122 
  123         MO_S_Gt _ -> Just $! CmmLit (CmmInt (if x_s >  y_s then 1 else 0) (wordWidth platform))
  124         MO_S_Ge _ -> Just $! CmmLit (CmmInt (if x_s >= y_s then 1 else 0) (wordWidth platform))
  125         MO_S_Lt _ -> Just $! CmmLit (CmmInt (if x_s <  y_s then 1 else 0) (wordWidth platform))
  126         MO_S_Le _ -> Just $! CmmLit (CmmInt (if x_s <= y_s then 1 else 0) (wordWidth platform))
  127 
  128         MO_Add r -> Just $! CmmLit (CmmInt (x + y) r)
  129         MO_Sub r -> Just $! CmmLit (CmmInt (x - y) r)
  130         MO_Mul r -> Just $! CmmLit (CmmInt (x * y) r)
  131         MO_U_Quot r | y /= 0 -> Just $! CmmLit (CmmInt (x_u `quot` y_u) r)
  132         MO_U_Rem  r | y /= 0 -> Just $! CmmLit (CmmInt (x_u `rem`  y_u) r)
  133         MO_S_Quot r | y /= 0 -> Just $! CmmLit (CmmInt (x `quot` y) r)
  134         MO_S_Rem  r | y /= 0 -> Just $! CmmLit (CmmInt (x `rem` y) r)
  135 
  136         MO_And   r -> Just $! CmmLit (CmmInt (x .&. y) r)
  137         MO_Or    r -> Just $! CmmLit (CmmInt (x .|. y) r)
  138         MO_Xor   r -> Just $! CmmLit (CmmInt (x `xor` y) r)
  139 
  140         MO_Shl   r -> Just $! CmmLit (CmmInt (x `shiftL` fromIntegral y) r)
  141         MO_U_Shr r -> Just $! CmmLit (CmmInt (x_u `shiftR` fromIntegral y) r)
  142         MO_S_Shr r -> Just $! CmmLit (CmmInt (x `shiftR` fromIntegral y) r)
  143 
  144         _          -> Nothing
  145 
  146    where
  147         x_u = narrowU xrep x
  148         y_u = narrowU xrep y
  149         x_s = narrowS xrep x
  150         y_s = narrowS xrep y
  151 
  152 
  153 -- When possible, shift the constants to the right-hand side, so that we
  154 -- can match for strength reductions.  Note that the code generator will
  155 -- also assume that constants have been shifted to the right when
  156 -- possible.
  157 
  158 cmmMachOpFoldM platform op [x@(CmmLit _), y]
  159    | not (isLit y) && isCommutableMachOp op
  160    = Just $! (cmmMachOpFold platform op [y, x])
  161 
  162 -- Turn (a+b)+c into a+(b+c) where possible.  Because literals are
  163 -- moved to the right, it is more likely that we will find
  164 -- opportunities for constant folding when the expression is
  165 -- right-associated.
  166 --
  167 -- ToDo: this appears to introduce a quadratic behaviour due to the
  168 -- nested cmmMachOpFold.  Can we fix this?
  169 --
  170 -- Why do we check isLit arg1?  If arg1 is a lit, it means that arg2
  171 -- is also a lit (otherwise arg1 would be on the right).  If we
  172 -- put arg1 on the left of the rearranged expression, we'll get into a
  173 -- loop:  (x1+x2)+x3 => x1+(x2+x3)  => (x2+x3)+x1 => x2+(x3+x1) ...
  174 --
  175 -- Also don't do it if arg1 is PicBaseReg, so that we don't separate the
  176 -- PicBaseReg from the corresponding label (or label difference).
  177 --
  178 cmmMachOpFoldM platform mop1 [CmmMachOp mop2 [arg1,arg2], arg3]
  179    | mop2 `associates_with` mop1
  180      && not (isLit arg1) && not (isPicReg arg1)
  181    = Just $! (cmmMachOpFold platform mop2 [arg1, cmmMachOpFold platform mop1 [arg2,arg3]])
  182    where
  183      MO_Add{} `associates_with` MO_Sub{} = True
  184      mop1 `associates_with` mop2 =
  185         mop1 == mop2 && isAssociativeMachOp mop1
  186 
  187 -- special case: (a - b) + c  ==>  a + (c - b)
  188 cmmMachOpFoldM platform mop1@(MO_Add{}) [CmmMachOp mop2@(MO_Sub{}) [arg1,arg2], arg3]
  189    | not (isLit arg1) && not (isPicReg arg1)
  190    = Just $! (cmmMachOpFold platform mop1 [arg1, cmmMachOpFold platform mop2 [arg3,arg2]])
  191 
  192 -- special case: (PicBaseReg + lit) + N  ==>  PicBaseReg + (lit+N)
  193 --
  194 -- this is better because lit+N is a single link-time constant (e.g. a
  195 -- CmmLabelOff), so the right-hand expression needs only one
  196 -- instruction, whereas the left needs two.  This happens when pointer
  197 -- tagging gives us label+offset, and PIC turns the label into
  198 -- PicBaseReg + label.
  199 --
  200 cmmMachOpFoldM _ MO_Add{} [ CmmMachOp op@MO_Add{} [pic, CmmLit lit]
  201                           , CmmLit (CmmInt n rep) ]
  202   | isPicReg pic
  203   = Just $! CmmMachOp op [pic, CmmLit $ cmmOffsetLit lit off ]
  204   where off = fromIntegral (narrowS rep n)
  205 
  206 -- Make a RegOff if we can
  207 cmmMachOpFoldM _ (MO_Add _) [CmmReg reg, CmmLit (CmmInt n rep)]
  208   = Just $! cmmRegOff reg (fromIntegral (narrowS rep n))
  209 cmmMachOpFoldM _ (MO_Add _) [CmmRegOff reg off, CmmLit (CmmInt n rep)]
  210   = Just $! cmmRegOff reg (off + fromIntegral (narrowS rep n))
  211 cmmMachOpFoldM _ (MO_Sub _) [CmmReg reg, CmmLit (CmmInt n rep)]
  212   = Just $! cmmRegOff reg (- fromIntegral (narrowS rep n))
  213 cmmMachOpFoldM _ (MO_Sub _) [CmmRegOff reg off, CmmLit (CmmInt n rep)]
  214   = Just $! cmmRegOff reg (off - fromIntegral (narrowS rep n))
  215 
  216 -- Fold label(+/-)offset into a CmmLit where possible
  217 
  218 cmmMachOpFoldM _ (MO_Add _) [CmmLit lit, CmmLit (CmmInt i rep)]
  219   = Just $! CmmLit (cmmOffsetLit lit (fromIntegral (narrowU rep i)))
  220 cmmMachOpFoldM _ (MO_Add _) [CmmLit (CmmInt i rep), CmmLit lit]
  221   = Just $! CmmLit (cmmOffsetLit lit (fromIntegral (narrowU rep i)))
  222 cmmMachOpFoldM _ (MO_Sub _) [CmmLit lit, CmmLit (CmmInt i rep)]
  223   = Just $! CmmLit (cmmOffsetLit lit (fromIntegral (negate (narrowU rep i))))
  224 
  225 
  226 -- Comparison of literal with widened operand: perform the comparison
  227 -- at the smaller width, as long as the literal is within range.
  228 
  229 -- We can't do the reverse trick, when the operand is narrowed:
  230 -- narrowing throws away bits from the operand, there's no way to do
  231 -- the same comparison at the larger size.
  232 
  233 cmmMachOpFoldM platform cmp [CmmMachOp conv [x], CmmLit (CmmInt i _)]
  234   |     -- powerPC NCG has a TODO for I8/I16 comparisons, so don't try
  235     platformArch platform `elem` [ArchX86, ArchX86_64],
  236         -- if the operand is widened:
  237     Just (rep, signed, narrow_fn) <- maybe_conversion conv,
  238         -- and this is a comparison operation:
  239     Just narrow_cmp <- maybe_comparison cmp rep signed,
  240         -- and the literal fits in the smaller size:
  241     i == narrow_fn rep i
  242         -- then we can do the comparison at the smaller size
  243   = Just $! (cmmMachOpFold platform narrow_cmp [x, CmmLit (CmmInt i rep)])
  244  where
  245     maybe_conversion (MO_UU_Conv from to)
  246         | to > from
  247         = Just (from, False, narrowU)
  248     maybe_conversion (MO_SS_Conv from to)
  249         | to > from
  250         = Just (from, True, narrowS)
  251 
  252         -- don't attempt to apply this optimisation when the source
  253         -- is a float; see #1916
  254     maybe_conversion _ = Nothing
  255 
  256         -- careful (#2080): if the original comparison was signed, but
  257         -- we were doing an unsigned widen, then we must do an
  258         -- unsigned comparison at the smaller size.
  259     maybe_comparison (MO_U_Gt _) rep _     = Just (MO_U_Gt rep)
  260     maybe_comparison (MO_U_Ge _) rep _     = Just (MO_U_Ge rep)
  261     maybe_comparison (MO_U_Lt _) rep _     = Just (MO_U_Lt rep)
  262     maybe_comparison (MO_U_Le _) rep _     = Just (MO_U_Le rep)
  263     maybe_comparison (MO_Eq   _) rep _     = Just (MO_Eq   rep)
  264     maybe_comparison (MO_S_Gt _) rep True  = Just (MO_S_Gt rep)
  265     maybe_comparison (MO_S_Ge _) rep True  = Just (MO_S_Ge rep)
  266     maybe_comparison (MO_S_Lt _) rep True  = Just (MO_S_Lt rep)
  267     maybe_comparison (MO_S_Le _) rep True  = Just (MO_S_Le rep)
  268     maybe_comparison (MO_S_Gt _) rep False = Just (MO_U_Gt rep)
  269     maybe_comparison (MO_S_Ge _) rep False = Just (MO_U_Ge rep)
  270     maybe_comparison (MO_S_Lt _) rep False = Just (MO_U_Lt rep)
  271     maybe_comparison (MO_S_Le _) rep False = Just (MO_U_Le rep)
  272     maybe_comparison _ _ _ = Nothing
  273 
  274 -- We can often do something with constants of 0 and 1 ...
  275 -- See Note [Comparison operators]
  276 
  277 cmmMachOpFoldM platform mop [x, y@(CmmLit (CmmInt 0 _))]
  278   = case mop of
  279         -- Arithmetic
  280         MO_Add   _ -> Just x   -- x + 0 = x
  281         MO_Sub   _ -> Just x   -- x - 0 = x
  282         MO_Mul   _ -> Just y   -- x * 0 = 0
  283 
  284         -- Logical operations
  285         MO_And   _ -> Just y   -- x &     0 = 0
  286         MO_Or    _ -> Just x   -- x |     0 = x
  287         MO_Xor   _ -> Just x   -- x `xor` 0 = x
  288 
  289         -- Shifts
  290         MO_Shl   _ -> Just x   -- x << 0 = x
  291         MO_S_Shr _ -> Just x   -- ditto shift-right
  292         MO_U_Shr _ -> Just x
  293 
  294         -- Comparisons; these ones are trickier
  295         -- See Note [Comparison operators]
  296         MO_Ne    _ | isComparisonExpr x -> Just x                -- (x > y) != 0  =  x > y
  297         MO_Eq    _ | Just x' <- maybeInvertCmmExpr x -> Just x'  -- (x > y) == 0  =  x <= y
  298         MO_U_Gt  _ | isComparisonExpr x -> Just x                -- (x > y) > 0   =  x > y
  299         MO_S_Gt  _ | isComparisonExpr x -> Just x                -- ditto
  300         MO_U_Lt  _ | isComparisonExpr x -> Just zero             -- (x > y) < 0  =  0
  301         MO_S_Lt  _ | isComparisonExpr x -> Just zero
  302         MO_U_Ge  _ | isComparisonExpr x -> Just one              -- (x > y) >= 0  =  1
  303         MO_S_Ge  _ | isComparisonExpr x -> Just one
  304 
  305         MO_U_Le  _ | Just x' <- maybeInvertCmmExpr x -> Just x'  -- (x > y) <= 0  =  x <= y
  306         MO_S_Le  _ | Just x' <- maybeInvertCmmExpr x -> Just x'
  307         _ -> Nothing
  308   where
  309     zero = CmmLit (CmmInt 0 (wordWidth platform))
  310     one  = CmmLit (CmmInt 1 (wordWidth platform))
  311 
  312 cmmMachOpFoldM platform mop [x, (CmmLit (CmmInt 1 rep))]
  313   = case mop of
  314         -- Arithmetic: x*1 = x, etc
  315         MO_Mul    _ -> Just x
  316         MO_S_Quot _ -> Just x
  317         MO_U_Quot _ -> Just x
  318         MO_S_Rem  _ -> Just $! CmmLit (CmmInt 0 rep)
  319         MO_U_Rem  _ -> Just $! CmmLit (CmmInt 0 rep)
  320 
  321         -- Comparisons; trickier
  322         -- See Note [Comparison operators]
  323         MO_Ne    _ | Just x' <- maybeInvertCmmExpr x -> Just x'  -- (x>y) != 1  =  x<=y
  324         MO_Eq    _ | isComparisonExpr x -> Just x                -- (x>y) == 1  =  x>y
  325         MO_U_Lt  _ | Just x' <- maybeInvertCmmExpr x -> Just x'  -- (x>y) < 1   =  x<=y
  326         MO_S_Lt  _ | Just x' <- maybeInvertCmmExpr x -> Just x'  -- ditto
  327         MO_U_Gt  _ | isComparisonExpr x -> Just zero             -- (x>y) > 1   = 0
  328         MO_S_Gt  _ | isComparisonExpr x -> Just zero
  329         MO_U_Le  _ | isComparisonExpr x -> Just one              -- (x>y) <= 1  = 1
  330         MO_S_Le  _ | isComparisonExpr x -> Just one
  331         MO_U_Ge  _ | isComparisonExpr x -> Just x                -- (x>y) >= 1  = x>y
  332         MO_S_Ge  _ | isComparisonExpr x -> Just x
  333         _ -> Nothing
  334   where
  335     zero = CmmLit (CmmInt 0 (wordWidth platform))
  336     one  = CmmLit (CmmInt 1 (wordWidth platform))
  337 
  338 -- Now look for multiplication/division by powers of 2 (integers).
  339 
  340 cmmMachOpFoldM platform mop [x, (CmmLit (CmmInt n _))]
  341   = case mop of
  342         MO_Mul rep
  343            | Just p <- exactLog2 n ->
  344                  Just $! (cmmMachOpFold platform (MO_Shl rep) [x, CmmLit (CmmInt p $ wordWidth platform)])
  345         MO_U_Quot rep
  346            | Just p <- exactLog2 n ->
  347                  Just $! (cmmMachOpFold platform (MO_U_Shr rep) [x, CmmLit (CmmInt p $ wordWidth platform)])
  348         MO_U_Rem rep
  349            | Just _ <- exactLog2 n ->
  350                  Just $! (cmmMachOpFold platform (MO_And rep) [x, CmmLit (CmmInt (n - 1) rep)])
  351         MO_S_Quot rep
  352            | Just p <- exactLog2 n,
  353              CmmReg _ <- x ->   -- We duplicate x in signedQuotRemHelper, hence require
  354                                 -- it is a reg.  FIXME: remove this restriction.
  355                 Just $! (cmmMachOpFold platform (MO_S_Shr rep)
  356                   [signedQuotRemHelper rep p, CmmLit (CmmInt p $ wordWidth platform)])
  357         MO_S_Rem rep
  358            | Just p <- exactLog2 n,
  359              CmmReg _ <- x ->   -- We duplicate x in signedQuotRemHelper, hence require
  360                                 -- it is a reg.  FIXME: remove this restriction.
  361                 -- We replace (x `rem` 2^p) by (x - (x `quot` 2^p) * 2^p).
  362                 -- Moreover, we fuse MO_S_Shr (last operation of MO_S_Quot)
  363                 -- and MO_S_Shl (multiplication by 2^p) into a single MO_And operation.
  364                 Just $! (cmmMachOpFold platform (MO_Sub rep)
  365                     [x, cmmMachOpFold platform (MO_And rep)
  366                       [signedQuotRemHelper rep p, CmmLit (CmmInt (- n) rep)]])
  367         _ -> Nothing
  368   where
  369     -- In contrast with unsigned integers, for signed ones
  370     -- shift right is not the same as quot, because it rounds
  371     -- to minus infinity, whereas quot rounds toward zero.
  372     -- To fix this up, we add one less than the divisor to the
  373     -- dividend if it is a negative number.
  374     --
  375     -- to avoid a test/jump, we use the following sequence:
  376     --      x1 = x >> word_size-1  (all 1s if -ve, all 0s if +ve)
  377     --      x2 = y & (divisor-1)
  378     --      result = x + x2
  379     -- this could be done a bit more simply using conditional moves,
  380     -- but we're processor independent here.
  381     --
  382     -- we optimise the divide by 2 case slightly, generating
  383     --      x1 = x >> word_size-1  (unsigned)
  384     --      return = x + x1
  385     signedQuotRemHelper :: Width -> Integer -> CmmExpr
  386     signedQuotRemHelper rep p = CmmMachOp (MO_Add rep) [x, x2]
  387       where
  388         bits = fromIntegral (widthInBits rep) - 1
  389         shr = if p == 1 then MO_U_Shr rep else MO_S_Shr rep
  390         x1 = CmmMachOp shr [x, CmmLit (CmmInt bits $ wordWidth platform)]
  391         x2 = if p == 1 then x1 else
  392              CmmMachOp (MO_And rep) [x1, CmmLit (CmmInt (n-1) rep)]
  393 
  394 -- ToDo (#7116): optimise floating-point multiplication, e.g. x*2.0 -> x+x
  395 -- Unfortunately this needs a unique supply because x might not be a
  396 -- register.  See #2253 (program 6) for an example.
  397 
  398 
  399 -- Anything else is just too hard.
  400 
  401 cmmMachOpFoldM _ _ _ = Nothing
  402 
  403 {- Note [Comparison operators]
  404 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  405 If we have
  406    CmmCondBranch ((x>#y) == 1) t f
  407 we really want to convert to
  408    CmmCondBranch (x>#y) t f
  409 
  410 That's what the constant-folding operations on comparison operators do above.
  411 -}
  412 
  413 
  414 -- -----------------------------------------------------------------------------
  415 -- Utils
  416 
  417 isPicReg :: CmmExpr -> Bool
  418 isPicReg (CmmReg (CmmGlobal PicBaseReg)) = True
  419 isPicReg _ = False