GitLab

Marge Bot pushed to branch master at Glasgow Haskell Compiler / GHC

Commits:

fe2b79f4

by Recursion Ninja at 2025-12-10T08:34:18-05:00

Narrow before optimising MUL/DIV/REM into shifts

The MUL/DIV/REM operations can be optimised into shifts when one of the
operands is a constant power of 2. However, as literals in Cmm are
stored as 'Integer', for this to be correct we first need to narrow the
literal to the appropriate width before checking whether the literal is
a power of 2.

Fixes #25664

4 changed files:

compiler/GHC/Cmm/Opt.hs
+ testsuite/tests/cmm/opt/T25664.hs
+ testsuite/tests/cmm/opt/T25664.stdout
testsuite/tests/cmm/opt/all.T

Changes:

compiler/GHC/Cmm/Opt.hs

@@ -395,26 +395,39 @@ cmmMachOpFoldM platform mop [x, (CmmLit (CmmInt 1 rep))]
      one  = CmmLit (CmmInt 1 (wordWidth platform))
  -- Now look for multiplication/division by powers of 2 (integers).
+-
 -cmmMachOpFoldM platform mop [x, (CmmLit (CmmInt n _))]
 +--
 +-- Naively this is as simple a matter as left/right bit shifts,
 +-- but the Cmm representation if integral values quickly complicated the matter.
 +--
 +-- We must carefully narrow the value to be within the range of values for the
 +-- type's logical bit-width. However, Cmm only represents values as *signed*
 +-- integers internally yet the logical type may be unsigned. If we are dealing
 +-- with a negative integer type at width @_w@, the only negative number that
 +-- wraps around to be a positive power of 2 after calling narrowU is -2^(_w - 1)
 +-- which wraps round to 2^(_w - 1), and multiplying by -2^(_w - 1) is indeed
 +-- the same as a left shift by (w - 1), so this is OK.
 +--
 +-- ToDo: See #25664 (comment 605821) describing a change to the Cmm literal representation.
 +-- When/If this is completed, this code must be refactored to account for the explicit width sizes.
 +cmmMachOpFoldM platform mop [x, (CmmLit (CmmInt n _w))]
    = case mop of
          MO_Mul rep
 -           | Just p <- exactLog2 n ->
 +           | Just p <- exactLog2 (narrowU rep n) ->
                   Just $! (cmmMachOpFold platform (MO_Shl rep) [x, CmmLit (CmmInt p $ wordWidth platform)])
          MO_U_Quot rep
 -           | Just p <- exactLog2 n ->
 +           | Just p <- exactLog2 (narrowU rep n) ->
                   Just $! (cmmMachOpFold platform (MO_U_Shr rep) [x, CmmLit (CmmInt p $ wordWidth platform)])
          MO_U_Rem rep
 -           | Just _ <- exactLog2 n ->
 +           | Just _ <- exactLog2 (narrowU rep n)  ->
                   Just $! (cmmMachOpFold platform (MO_And rep) [x, CmmLit (CmmInt (n - 1) rep)])
          MO_S_Quot rep
 -           | Just p <- exactLog2 n,
 +           | Just p <- exactLog2 (narrowS rep n),
               CmmReg _ <- x ->   -- We duplicate x in signedQuotRemHelper, hence require
                                  -- it is a reg.  FIXME: remove this restriction.
                  Just $! (cmmMachOpFold platform (MO_S_Shr rep)
                    [signedQuotRemHelper rep p, CmmLit (CmmInt p $ wordWidth platform)])
          MO_S_Rem rep
 -           | Just p <- exactLog2 n,
 +           | Just p <- exactLog2 (narrowS rep n),
               CmmReg _ <- x ->   -- We duplicate x in signedQuotRemHelper, hence require
                                  -- it is a reg.  FIXME: remove this restriction.
                  -- We replace (x `rem` 2^p) by (x - (x `quot` 2^p) * 2^p).

testsuite/tests/cmm/opt/T25664.hs

 +{-# OPTIONS_GHC -O -fno-full-laziness #-}
 +{-# LANGUAGE MagicHash #-}
++
 +import GHC.Exts
 +import GHC.Int
++
 +mb8 :: Int8 -> Int8
 +{-# OPAQUE mb8 #-}
 +mb8 (I8# i) = I8# (i `quotInt8#` (noinline intToInt8# 128#))
++
 +mb16 :: Int16 -> Int16
 +{-# OPAQUE mb16 #-}
 +mb16 (I16# i) = I16# (i `quotInt16#` (noinline intToInt16# 32768#))
++
 +main :: IO ()
 +main = print (mb8 minBound) >> print (mb16 minBound)
++

testsuite/tests/cmm/opt/T25664.stdout

	1	+1
	2	+1

testsuite/tests/cmm/opt/all.T

@@ -12,3 +12,6 @@ test('T25771', [cmm_src, only_ways(['optasm']),
                  grep_errmsg(r'(12\.345|0\.6640625)',[1]),
                  ],
       compile, ['-ddump-cmm'])
++
 +# Cmm should correctly account for word size when performing MUL/DIV/REM by a power of 2 optimization.
 +test('T25664', normal, compile_and_run, [''])
 \ No newline at end of file