Produce better code from maskW
authorMateusz Kowalczyk <fuuzetsu@fuuzetsu.co.uk>
Tue, 22 Jan 2019 04:38:16 +0000 (13:38 +0900)
committerDavid Feuer <David.Feuer@gmail.com>
Fri, 12 Apr 2019 20:20:51 +0000 (16:20 -0400)
```
complement (m-1) `xor` m == -m `xor` m
```

Latter produces slightly better assembly.

```asm
movq %rdi, %rax
negq %rax
xorq %rdi, %rax
```

Indeed if we give

```cpp
uint64_t f(uint64_t m_aQU2) {
  return ((m_aQU2 - 1) ^ 18446744073709551615UL) ^ m_aQU2;
}
```

to clang and compile with optimisation, that's the ASM it spits out.
Translating it back to Haskell gives the solution from this branch.
Without same optimisation, even in Haskell it saves an instruction.

```hs
maskW :: Word -> Word
maskW m = complement (m-1) `xor` m

{-
movq %rax,%rbx
xorq $-1,%rbx
decq %rax
xorq %rbx,%rax
-}
```

```hs
maskMine :: Word -> Word
maskMine m = (-m) `xor` m

{-
movq %rax,%rbx
negq %rbx
xorq %rax,%rbx
-}
```

Data/IntMap/Internal.hs

index f275376..edc2bf8 100644 (file)
@@ -1117,7 +1117,7 @@ withoutKeys t1@(Bin p1 m1 _ _) (IntSet.Tip p2 bm2) =
     let minbit = bitmapOf p1
         lt_minbit = minbit - 1
         maxbit = bitmapOf (p1 .|. (m1 .|. (m1 - 1)))
-        gt_maxbit = maxbit `xor` complement (maxbit - 1)
+        gt_maxbit = (-maxbit) `xor` maxbit
     -- TODO(wrengr): should we manually inline/unroll 'updatePrefix'
     -- and 'withoutBM' here, in order to avoid redundant case analyses?
     in updatePrefix p2 t1 $ withoutBM (bm2 .|. lt_minbit .|. gt_maxbit)
@@ -3336,7 +3336,7 @@ mask i m
 -- bit @m@.
 maskW :: Nat -> Nat -> Prefix
 maskW i m
-  = intFromNat (i .&. (complement (m-1) `xor` m))
+  = intFromNat (i .&. ((-m) `xor` m))
 {-# INLINE maskW #-}
 
 -- | Does the left switching bit specify a shorter prefix?