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