+{-# OPTIONS -w #-}
+-- The above warning supression flag is a temporary kludge.
+-- While working on this module you are encouraged to remove it and fix
+-- any warnings in the module. See
+-- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
+-- for details
+
-----------------------------------------------------------------------------
--
-- Cmm optimisation
--
-----------------------------------------------------------------------------
-{-# OPTIONS_GHC -w #-}
--- The above warning supression flag is a temporary kludge.
--- While working on this module you are encouraged to remove it and fix
--- any warnings in the module. See
--- http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions#Warnings
--- for details
-
module CmmOpt (
cmmMiniInline,
cmmMachOpFold,
#include "HsVersions.h"
import Cmm
+import CmmExpr
import CmmUtils
import CLabel
-import MachOp
import StaticFlags
import UniqFM
import Unique
-
+import FastTypes
import Outputable
import Data.Bits
import Data.Word
import Data.Int
-import GHC.Exts
-- -----------------------------------------------------------------------------
-- The mini-inliner
- if we reach the statement that uses it, inline the rhs
and delete the original assignment.
+[N.B. In the Quick C-- compiler, this optimization is achieved by a
+ combination of two dataflow passes: forward substitution (peephole
+ optimization) and dead-assignment elimination. ---NR]
+
Possible generalisations: here is an example from factorial
Fac_zdwfac_entry:
its occurrences.
-}
+countUses :: UserOfLocalRegs a => a -> UniqFM Int
+countUses a = foldRegsUsed (\m r -> addToUFM m r (count m r + 1)) emptyUFM a
+ where count m r = lookupWithDefaultUFM m (0::Int) r
+
cmmMiniInline :: [CmmBasicBlock] -> [CmmBasicBlock]
cmmMiniInline blocks = map do_inline blocks
- where
- blockUses (BasicBlock _ stmts)
- = foldr (plusUFM_C (+)) emptyUFM (map getStmtUses stmts)
-
- uses = foldr (plusUFM_C (+)) emptyUFM (map blockUses blocks)
-
- do_inline (BasicBlock id stmts)
- = BasicBlock id (cmmMiniInlineStmts uses stmts)
-
+ where do_inline (BasicBlock id stmts)
+ = BasicBlock id (cmmMiniInlineStmts (countUses blocks) stmts)
cmmMiniInlineStmts :: UniqFM Int -> [CmmStmt] -> [CmmStmt]
cmmMiniInlineStmts uses [] = []
-cmmMiniInlineStmts uses (stmt@(CmmAssign (CmmLocal (LocalReg u _ _)) expr) : stmts)
+cmmMiniInlineStmts uses (stmt@(CmmAssign (CmmLocal (LocalReg u _)) expr) : stmts)
+ -- not used at all: just discard this assignment
+ | Nothing <- lookupUFM uses u
+ = cmmMiniInlineStmts uses stmts
+
+ -- used once: try to inline at the use site
| Just 1 <- lookupUFM uses u,
Just stmts' <- lookForInline u expr stmts
=
-- Try to inline a temporary assignment. We can skip over assignments to
-- other tempoararies, because we know that expressions aren't side-effecting
-- and temporaries are single-assignment.
-lookForInline u expr (stmt@(CmmAssign (CmmLocal (LocalReg u' _ _)) rhs) : rest)
+lookForInline u expr (stmt@(CmmAssign (CmmLocal (LocalReg u' _)) rhs) : rest)
| u /= u'
- = case lookupUFM (getExprUses rhs) u of
+ = case lookupUFM (countUses rhs) u of
Just 1 -> Just (inlineStmt u expr stmt : rest)
_other -> case lookForInline u expr rest of
Nothing -> Nothing
lookForInline u expr (CmmNop : rest)
= lookForInline u expr rest
+lookForInline _ _ [] = Nothing
+
lookForInline u expr (stmt:stmts)
- = case lookupUFM (getStmtUses stmt) u of
+ = case lookupUFM (countUses stmt) u of
Just 1 | ok_to_inline -> Just (inlineStmt u expr stmt : stmts)
_other -> Nothing
where
CmmCall{} -> hasNoGlobalRegs expr
_ -> True
--- -----------------------------------------------------------------------------
--- Boring Cmm traversals for collecting usage info and substitutions.
-
-getStmtUses :: CmmStmt -> UniqFM Int
-getStmtUses (CmmAssign _ e) = getExprUses e
-getStmtUses (CmmStore e1 e2) = plusUFM_C (+) (getExprUses e1) (getExprUses e2)
-getStmtUses (CmmCall target _ es _ _)
- = plusUFM_C (+) (uses target) (getExprsUses (map fst es))
- where uses (CmmCallee e _) = getExprUses e
- uses _ = emptyUFM
-getStmtUses (CmmCondBranch e _) = getExprUses e
-getStmtUses (CmmSwitch e _) = getExprUses e
-getStmtUses (CmmJump e _) = getExprUses e
-getStmtUses _ = emptyUFM
-
-getExprUses :: CmmExpr -> UniqFM Int
-getExprUses (CmmReg (CmmLocal (LocalReg u _ _))) = unitUFM u 1
-getExprUses (CmmRegOff (CmmLocal (LocalReg u _ _)) _) = unitUFM u 1
-getExprUses (CmmLoad e _) = getExprUses e
-getExprUses (CmmMachOp _ es) = getExprsUses es
-getExprUses _other = emptyUFM
-
-getExprsUses es = foldr (plusUFM_C (+)) emptyUFM (map getExprUses es)
-
inlineStmt :: Unique -> CmmExpr -> CmmStmt -> CmmStmt
inlineStmt u a (CmmAssign r e) = CmmAssign r (inlineExpr u a e)
inlineStmt u a (CmmStore e1 e2) = CmmStore (inlineExpr u a e1) (inlineExpr u a e2)
= CmmCall (infn target) regs es' srt ret
where infn (CmmCallee fn cconv) = CmmCallee fn cconv
infn (CmmPrim p) = CmmPrim p
- es' = [ (inlineExpr u a e, hint) | (e,hint) <- es ]
+ es' = [ (CmmHinted (inlineExpr u a e) hint) | (CmmHinted e hint) <- es ]
inlineStmt u a (CmmCondBranch e d) = CmmCondBranch (inlineExpr u a e) d
inlineStmt u a (CmmSwitch e d) = CmmSwitch (inlineExpr u a e) d
inlineStmt u a (CmmJump e d) = CmmJump (inlineExpr u a e) d
inlineStmt u a other_stmt = other_stmt
inlineExpr :: Unique -> CmmExpr -> CmmExpr -> CmmExpr
-inlineExpr u a e@(CmmReg (CmmLocal (LocalReg u' _ _)))
+inlineExpr u a e@(CmmReg (CmmLocal (LocalReg u' _)))
| u == u' = a
| otherwise = e
-inlineExpr u a e@(CmmRegOff (CmmLocal (LocalReg u' rep _)) off)
- | u == u' = CmmMachOp (MO_Add rep) [a, CmmLit (CmmInt (fromIntegral off) rep)]
+inlineExpr u a e@(CmmRegOff (CmmLocal (LocalReg u' rep)) off)
+ | u == u' = CmmMachOp (MO_Add width) [a, CmmLit (CmmInt (fromIntegral off) width)]
| otherwise = e
+ where
+ width = typeWidth rep
inlineExpr u a (CmmLoad e rep) = CmmLoad (inlineExpr u a e) rep
inlineExpr u a (CmmMachOp op es) = CmmMachOp op (map (inlineExpr u a) es)
inlineExpr u a other_expr = other_expr
-- "from" type, in order to truncate to the correct size.
-- The final narrow/widen to the destination type
-- is implicit in the CmmLit.
- MO_S_Conv from to
- | isFloatingRep to -> CmmLit (CmmFloat (fromInteger x) to)
- | otherwise -> CmmLit (CmmInt (narrowS from x) to)
- MO_U_Conv from to -> CmmLit (CmmInt (narrowU from x) to)
+ MO_SF_Conv from to -> CmmLit (CmmFloat (fromInteger x) to)
+ MO_SS_Conv from to -> CmmLit (CmmInt (narrowS from x) to)
+ MO_UU_Conv from to -> CmmLit (CmmInt (narrowU from x) to)
_ -> panic "cmmMachOpFold: unknown unary op"
-- Eliminate conversion NOPs
-cmmMachOpFold (MO_S_Conv rep1 rep2) [x] | rep1 == rep2 = x
-cmmMachOpFold (MO_U_Conv rep1 rep2) [x] | rep1 == rep2 = x
+cmmMachOpFold (MO_SS_Conv rep1 rep2) [x] | rep1 == rep2 = x
+cmmMachOpFold (MO_UU_Conv rep1 rep2) [x] | rep1 == rep2 = x
-- Eliminate nested conversions where possible
cmmMachOpFold conv_outer args@[CmmMachOp conv_inner [x]]
cmmMachOpFold (intconv signed1 rep1 rep3) [x]
-- Nested narrowings: collapse
| rep1 > rep2 && rep2 > rep3 ->
- cmmMachOpFold (MO_U_Conv rep1 rep3) [x]
+ cmmMachOpFold (MO_UU_Conv rep1 rep3) [x]
| otherwise ->
CmmMachOp conv_outer args
where
- isIntConversion (MO_U_Conv rep1 rep2)
- | not (isFloatingRep rep1) && not (isFloatingRep rep2)
+ isIntConversion (MO_UU_Conv rep1 rep2)
= Just (rep1,rep2,False)
- isIntConversion (MO_S_Conv rep1 rep2)
- | not (isFloatingRep rep1) && not (isFloatingRep rep2)
+ isIntConversion (MO_SS_Conv rep1 rep2)
= Just (rep1,rep2,True)
isIntConversion _ = Nothing
- intconv True = MO_S_Conv
- intconv False = MO_U_Conv
+ intconv True = MO_SS_Conv
+ intconv False = MO_UU_Conv
-- ToDo: a narrow of a load can be collapsed into a narrow load, right?
-- but what if the architecture only supports word-sized loads, should
= case mop of
-- for comparisons: don't forget to narrow the arguments before
-- comparing, since they might be out of range.
- MO_Eq r -> CmmLit (CmmInt (if x_u == y_u then 1 else 0) wordRep)
- MO_Ne r -> CmmLit (CmmInt (if x_u /= y_u then 1 else 0) wordRep)
+ MO_Eq r -> CmmLit (CmmInt (if x_u == y_u then 1 else 0) wordWidth)
+ MO_Ne r -> CmmLit (CmmInt (if x_u /= y_u then 1 else 0) wordWidth)
- MO_U_Gt r -> CmmLit (CmmInt (if x_u > y_u then 1 else 0) wordRep)
- MO_U_Ge r -> CmmLit (CmmInt (if x_u >= y_u then 1 else 0) wordRep)
- MO_U_Lt r -> CmmLit (CmmInt (if x_u < y_u then 1 else 0) wordRep)
- MO_U_Le r -> CmmLit (CmmInt (if x_u <= y_u then 1 else 0) wordRep)
+ MO_U_Gt r -> CmmLit (CmmInt (if x_u > y_u then 1 else 0) wordWidth)
+ MO_U_Ge r -> CmmLit (CmmInt (if x_u >= y_u then 1 else 0) wordWidth)
+ MO_U_Lt r -> CmmLit (CmmInt (if x_u < y_u then 1 else 0) wordWidth)
+ MO_U_Le r -> CmmLit (CmmInt (if x_u <= y_u then 1 else 0) wordWidth)
- MO_S_Gt r -> CmmLit (CmmInt (if x_s > y_s then 1 else 0) wordRep)
- MO_S_Ge r -> CmmLit (CmmInt (if x_s >= y_s then 1 else 0) wordRep)
- MO_S_Lt r -> CmmLit (CmmInt (if x_s < y_s then 1 else 0) wordRep)
- MO_S_Le r -> CmmLit (CmmInt (if x_s <= y_s then 1 else 0) wordRep)
+ MO_S_Gt r -> CmmLit (CmmInt (if x_s > y_s then 1 else 0) wordWidth)
+ MO_S_Ge r -> CmmLit (CmmInt (if x_s >= y_s then 1 else 0) wordWidth)
+ MO_S_Lt r -> CmmLit (CmmInt (if x_s < y_s then 1 else 0) wordWidth)
+ MO_S_Le r -> CmmLit (CmmInt (if x_s <= y_s then 1 else 0) wordWidth)
MO_Add r -> CmmLit (CmmInt (x + y) r)
MO_Sub r -> CmmLit (CmmInt (x - y) r)
= CmmLit (CmmLabelOff lbl (fromIntegral (negate (narrowU rep i))))
--- Comparison of literal with narrowed/widened operand: perform
--- the comparison at a different width, as long as the literal is
--- within range.
+-- Comparison of literal with widened operand: perform the comparison
+-- at the smaller width, as long as the literal is within range.
+
+-- We can't do the reverse trick, when the operand is narrowed:
+-- narrowing throws away bits from the operand, there's no way to do
+-- the same comparison at the larger size.
#if i386_TARGET_ARCH || x86_64_TARGET_ARCH
-- powerPC NCG has a TODO for I8/I16 comparisons, so don't try
cmmMachOpFold cmp [CmmMachOp conv [x], CmmLit (CmmInt i _)]
- | Just (rep, narrow) <- maybe_conversion conv,
- Just narrow_cmp <- maybe_comparison cmp rep,
- let narrow_i = narrow rep i,
- narrow_i == i
- = cmmMachOpFold narrow_cmp [x, CmmLit (CmmInt narrow_i rep)]
+ | -- if the operand is widened:
+ Just (rep, signed, narrow_fn) <- maybe_conversion conv,
+ -- and this is a comparison operation:
+ Just narrow_cmp <- maybe_comparison cmp rep signed,
+ -- and the literal fits in the smaller size:
+ i == narrow_fn rep i
+ -- then we can do the comparison at the smaller size
+ = cmmMachOpFold narrow_cmp [x, CmmLit (CmmInt i rep)]
where
- maybe_conversion (MO_U_Conv from _) = Just (from, narrowU)
- maybe_conversion (MO_S_Conv from _) = Just (from, narrowS)
+ maybe_conversion (MO_UU_Conv from to)
+ | to > from
+ = Just (from, False, narrowU)
+ maybe_conversion (MO_SS_Conv from to)
+ | to > from
+ = Just (from, True, narrowS)
+
+ -- don't attempt to apply this optimisation when the source
+ -- is a float; see #1916
maybe_conversion _ = Nothing
- maybe_comparison (MO_U_Gt _) rep = Just (MO_U_Gt rep)
- maybe_comparison (MO_U_Ge _) rep = Just (MO_U_Ge rep)
- maybe_comparison (MO_U_Lt _) rep = Just (MO_U_Lt rep)
- maybe_comparison (MO_U_Le _) rep = Just (MO_U_Le rep)
- maybe_comparison (MO_S_Gt _) rep = Just (MO_S_Gt rep)
- maybe_comparison (MO_S_Ge _) rep = Just (MO_S_Ge rep)
- maybe_comparison (MO_S_Lt _) rep = Just (MO_S_Lt rep)
- maybe_comparison (MO_S_Le _) rep = Just (MO_S_Le rep)
- maybe_comparison (MO_Eq _) rep = Just (MO_Eq rep)
- maybe_comparison _ _ = Nothing
+ -- careful (#2080): if the original comparison was signed, but
+ -- we were doing an unsigned widen, then we must do an
+ -- unsigned comparison at the smaller size.
+ maybe_comparison (MO_U_Gt _) rep _ = Just (MO_U_Gt rep)
+ maybe_comparison (MO_U_Ge _) rep _ = Just (MO_U_Ge rep)
+ maybe_comparison (MO_U_Lt _) rep _ = Just (MO_U_Lt rep)
+ maybe_comparison (MO_U_Le _) rep _ = Just (MO_U_Le rep)
+ maybe_comparison (MO_Eq _) rep _ = Just (MO_Eq rep)
+ maybe_comparison (MO_S_Gt _) rep True = Just (MO_S_Gt rep)
+ maybe_comparison (MO_S_Ge _) rep True = Just (MO_S_Ge rep)
+ maybe_comparison (MO_S_Lt _) rep True = Just (MO_S_Lt rep)
+ maybe_comparison (MO_S_Le _) rep True = Just (MO_S_Le rep)
+ maybe_comparison (MO_S_Gt _) rep False = Just (MO_U_Gt rep)
+ maybe_comparison (MO_S_Ge _) rep False = Just (MO_U_Ge rep)
+ maybe_comparison (MO_S_Lt _) rep False = Just (MO_U_Lt rep)
+ maybe_comparison (MO_S_Le _) rep False = Just (MO_U_Le rep)
+ maybe_comparison _ _ _ = Nothing
#endif
MO_S_Shr r -> x
MO_U_Shr r -> x
MO_Ne r | isComparisonExpr x -> x
- MO_Eq r | Just x' <- maybeInvertConditionalExpr x -> x'
+ MO_Eq r | Just x' <- maybeInvertCmmExpr x -> x'
MO_U_Gt r | isComparisonExpr x -> x
MO_S_Gt r | isComparisonExpr x -> x
- MO_U_Lt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordRep)
- MO_S_Lt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordRep)
- MO_U_Ge r | isComparisonExpr x -> CmmLit (CmmInt 1 wordRep)
- MO_S_Ge r | isComparisonExpr x -> CmmLit (CmmInt 1 wordRep)
- MO_U_Le r | Just x' <- maybeInvertConditionalExpr x -> x'
- MO_S_Le r | Just x' <- maybeInvertConditionalExpr x -> x'
+ MO_U_Lt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordWidth)
+ MO_S_Lt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordWidth)
+ MO_U_Ge r | isComparisonExpr x -> CmmLit (CmmInt 1 wordWidth)
+ MO_S_Ge r | isComparisonExpr x -> CmmLit (CmmInt 1 wordWidth)
+ MO_U_Le r | Just x' <- maybeInvertCmmExpr x -> x'
+ MO_S_Le r | Just x' <- maybeInvertCmmExpr x -> x'
other -> CmmMachOp mop args
cmmMachOpFold mop args@[x, y@(CmmLit (CmmInt 1 rep))]
MO_U_Quot r -> x
MO_S_Rem r -> CmmLit (CmmInt 0 rep)
MO_U_Rem r -> CmmLit (CmmInt 0 rep)
- MO_Ne r | Just x' <- maybeInvertConditionalExpr x -> x'
+ MO_Ne r | Just x' <- maybeInvertCmmExpr x -> x'
MO_Eq r | isComparisonExpr x -> x
- MO_U_Lt r | Just x' <- maybeInvertConditionalExpr x -> x'
- MO_S_Lt r | Just x' <- maybeInvertConditionalExpr x -> x'
- MO_U_Gt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordRep)
- MO_S_Gt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordRep)
- MO_U_Le r | isComparisonExpr x -> CmmLit (CmmInt 1 wordRep)
- MO_S_Le r | isComparisonExpr x -> CmmLit (CmmInt 1 wordRep)
+ MO_U_Lt r | Just x' <- maybeInvertCmmExpr x -> x'
+ MO_S_Lt r | Just x' <- maybeInvertCmmExpr x -> x'
+ MO_U_Gt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordWidth)
+ MO_S_Gt r | isComparisonExpr x -> CmmLit (CmmInt 0 wordWidth)
+ MO_U_Le r | isComparisonExpr x -> CmmLit (CmmInt 1 wordWidth)
+ MO_S_Le r | isComparisonExpr x -> CmmLit (CmmInt 1 wordWidth)
MO_U_Ge r | isComparisonExpr x -> x
MO_S_Ge r | isComparisonExpr x -> x
other -> CmmMachOp mop args
-- x1 = x >> word_size-1 (unsigned)
-- return = (x + x1) >>= log2(divisor)
let
- bits = fromIntegral (machRepBitWidth rep) - 1
+ bits = fromIntegral (widthInBits rep) - 1
shr = if p == 1 then MO_U_Shr rep else MO_S_Shr rep
x1 = CmmMachOp shr [x, CmmLit (CmmInt bits rep)]
x2 = if p == 1 then x1 else
-- Used to be in MachInstrs --SDM.
-- ToDo: remove use of unboxery --SDM.
-w2i x = word2Int# x
-i2w x = int2Word# x
+-- Unboxery removed in favor of FastInt; but is the function supposed to fail
+-- on inputs >= 2147483648, or was that just an implementation artifact?
+-- And is this speed-critical, or can we just use Integer operations
+-- (including Data.Bits)?
+-- --Isaac Dupree
exactLog2 :: Integer -> Maybe Integer
-exactLog2 x
- = if (x <= 0 || x >= 2147483648) then
+exactLog2 x_
+ = if (x_ <= 0 || x_ >= 2147483648) then
Nothing
else
- case fromInteger x of { I# x# ->
- if (w2i ((i2w x#) `and#` (i2w (0# -# x#))) /=# x#) then
+ case iUnbox (fromInteger x_) of { x ->
+ if (x `bitAndFastInt` negateFastInt x) /=# x then
Nothing
else
- Just (toInteger (I# (pow2 x#)))
+ Just (toInteger (iBox (pow2 x)))
}
where
- pow2 x# | x# ==# 1# = 0#
- | otherwise = 1# +# pow2 (w2i (i2w x# `shiftRL#` 1#))
+ pow2 x | x ==# _ILIT(1) = _ILIT(0)
+ | otherwise = _ILIT(1) +# pow2 (x `shiftR_FastInt` _ILIT(1))
-- -----------------------------------------------------------------------------
-- widening / narrowing
-narrowU :: MachRep -> Integer -> Integer
-narrowU I8 x = fromIntegral (fromIntegral x :: Word8)
-narrowU I16 x = fromIntegral (fromIntegral x :: Word16)
-narrowU I32 x = fromIntegral (fromIntegral x :: Word32)
-narrowU I64 x = fromIntegral (fromIntegral x :: Word64)
+narrowU :: Width -> Integer -> Integer
+narrowU W8 x = fromIntegral (fromIntegral x :: Word8)
+narrowU W16 x = fromIntegral (fromIntegral x :: Word16)
+narrowU W32 x = fromIntegral (fromIntegral x :: Word32)
+narrowU W64 x = fromIntegral (fromIntegral x :: Word64)
narrowU _ _ = panic "narrowTo"
-narrowS :: MachRep -> Integer -> Integer
-narrowS I8 x = fromIntegral (fromIntegral x :: Int8)
-narrowS I16 x = fromIntegral (fromIntegral x :: Int16)
-narrowS I32 x = fromIntegral (fromIntegral x :: Int32)
-narrowS I64 x = fromIntegral (fromIntegral x :: Int64)
+narrowS :: Width -> Integer -> Integer
+narrowS W8 x = fromIntegral (fromIntegral x :: Int8)
+narrowS W16 x = fromIntegral (fromIntegral x :: Int16)
+narrowS W32 x = fromIntegral (fromIntegral x :: Int32)
+narrowS W64 x = fromIntegral (fromIntegral x :: Int64)
narrowS _ _ = panic "narrowTo"
-- -----------------------------------------------------------------------------
-}
cmmLoopifyForC :: RawCmmTop -> RawCmmTop
-cmmLoopifyForC p@(CmmProc info entry_lbl [] blocks@(BasicBlock top_id _ : _))
+cmmLoopifyForC p@(CmmProc info entry_lbl [] (ListGraph blocks@(BasicBlock top_id _ : _)))
| null info = p -- only if there's an info table, ignore case alts
| otherwise =
-- pprTrace "jump_lbl" (ppr jump_lbl <+> ppr entry_lbl) $
- CmmProc info entry_lbl [] blocks'
+ CmmProc info entry_lbl [] (ListGraph blocks')
where blocks' = [ BasicBlock id (map do_stmt stmts)
| BasicBlock id stmts <- blocks ]
isComparisonExpr (CmmMachOp op _) = isComparisonMachOp op
isComparisonExpr _other = False
-maybeInvertConditionalExpr :: CmmExpr -> Maybe CmmExpr
-maybeInvertConditionalExpr (CmmMachOp op args)
- | Just op' <- maybeInvertComparison op = Just (CmmMachOp op' args)
-maybeInvertConditionalExpr _ = Nothing
-
isPicReg (CmmReg (CmmGlobal PicBaseReg)) = True
isPicReg _ = False
+
projects / ghc-hetmet.git / blobdiff