Changes between Version 7 and Version 8 of PrimBool


Ignore:
Timestamp:
Jan 28, 2013 3:36:09 PM (15 months ago)
Author:
jstolarek
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • PrimBool

    v7 v8  
    5151 
    5252and in following assembler code: 
    53  
    5453{{{ 
    5554.Lc1rf: 
     
    8079There are five possible branches to take, although four of them have the same result. This is caused by code duplication introduced by case-of-case transform (see [http://ics.p.lodz.pl/~stolarek/blog/2013/01/taking-magic-out-of-ghc-or-tracing-compilation-by-transformation/ this blog post] for a step by step derivation). According to Ben Lippmeier, who submitted the original bug report, mis-predicted branches are bad in object code because they stall the pipeline. 
    8180 
    82 == Possible solutions and their consequences == 
     81== Workarounds == 
    8382 
    84 Unnecessary branches could be eliminated by introducing primitive logical operators AND, OR and NOT (they will be denoted as `||#`, `&&#` and `not#` respectively). These operators would be strict and treat their logical parameters as unboxed integers (`1#` for `True` and `0#` for `False`). Result would be produced by using low-level bitwise operations. This means that if logical operators were chained together like in a given example only the final result would have to be inspected and thus only one branch would be necessary. 
     83It is possible to work around the issue of code duplication by using GHC primops `tagToEnum#` and `dataToTag#`. These allow to distinguish between `True` and `False` by means of accessing the tag of a data type constructor. This means that `dataToTag#` can convert `True` to `1#` and `False` to `0#`, while `tagToEnum#` does the opposite (see paper [http://research.microsoft.com/en-us/um/people/simonpj/papers/ptr-tag/index.htm "Faster Laziness Using Dynamic Pointer Tagging"] for more details):  
    8584 
    86 Note (Jan Stolarek): My first thought was that introducing primitve logical operators will require changing `Bool` data type to a primitive unboxed version. This might not be the case. Please treat two solution apporaches as possibly wrong. 
    87  
    88 === First approach === 
    89  
    90 Treat `Bool` as a boxed version of primitive `Bool#`. `True` would be equivalent of `B# True#`, `False` of `B# False#`: 
    91   {{{ 
    92 data Bool = B# True# | B# False#  
    93  
    94 -- B# :: Bool# -> Bool 
     85{{{ 
     86ghci> import GHC.Exts 
     87ghci> import GHC.Prim 
     88ghci> :set -XMagicHash 
     89ghci> I# (dataToTag# True) 
     901 
     91ghci> I# (dataToTag# False) 
     920 
     93ghci> (tagToEnum# 0#) :: Bool 
     94False 
     95ghci> (tagToEnum# 1#) :: Bool 
     96True 
     97ghci> 
    9598}}} 
    9699 
    97 Not sure if this can be considered equivalent to what the Haskell Report says about Bool. We need to ensure that `Bool#` is populated only by `True#` and `False#` and that these two are translated to `1#` and `0#` in the Core. It should be **impossible** to write such a function at Haskell level: 
     100Having the possibility of converting `Bool` to an unboxed `Int#` allows us to compute results of logical expression by means of logical bitwise operations. The result can be converted back to a `Bool` so this is transparent on the Haskell source level, except for the fact that defined logical binary operators will be strict in both their arguments. 
     101 
     102'''NOTE: Validity of this solution is based on assumption that `True` will always have a tag of `1#`, while `False` will have a tag of `0#`. Changing this invariant in the future would make these primitive logical operators invalid.''' 
     103 
     104=== First workaround === 
     105 
     106First workaround assumes converting each result of comparison into an unboxed `Int` and replacing `||` with `+#`: 
    98107 
    99108{{{ 
    100 g :: Bool -> Int -> Int 
    101 g (B# b) (I# i) = I# (b + i) 
     109 case (dataToTag# (x <# 0#)) +# (dataToTag# (x >=# width)) +# 
     110      (dataToTag# (y <# 0#)) +# (dataToTag# (y >=# height)) of 
     111  0# -> E2 -- note that branch order is reversed 
     112  _  -> E1 
    102113}}} 
    103114 
    104 This approach might require one additional case expression to inspect the value of `Bool` at the Core level. For example: 
     115This compiles to: 
    105116 
    106117{{{ 
    107 f :: Int -> Int -> Int 
    108 f x y = if x > y 
    109         then x 
    110         else y 
    111 }}} 
    112  
    113 would compile to: 
    114  
    115 {{{ 
    116 case x of _ { I# xP -> 
    117  case y of _ { I# yP -> 
    118    case ># xP yP of _ { 
    119      B# bP -> case bP of _ { 1# -> e1; 0# -> e2 } 
    120    } 
    121  } 
     118case +# 
     119       (+# 
     120          (+# (dataToTag# (<# x 0)) (dataToTag# (>=# x width))) 
     121          (dataToTag# (<# y 0))) 
     122       (dataToTag# (>=# y height)) 
     123of _ { 
     124  __DEFAULT -> E1; 
     125  0 -> E2 
    122126} 
    123127}}} 
    124128 
    125 This would complicate Core a bit but it should be possible to compile such Core to exactly the same result as with normal `Bool`. This code assumes that `>#` has type `Int# -> Int# -> Bool`, but to truly avoid branching in the Core we need `.># :: Int# -> Int# -> Bool#` so that we get a primitive value that doesn't need to be inspected using case expression but can be directly used by primitive logical operators. 
    126   
    127 === Second approach === 
     129Similarly we can convert logical && into multiplication. 
    128130 
    129 Second approach assumes creating type `Bool#` that is independent of type `Bool`. Boxing and unboxing would have to be done explicitly via additional functions: 
     131=== Second workaround === 
     132 
     133The above workaround is a bit clumsy: `dataToTag#`s make the code verbose and it may not be very obvious what the code is doing. Hence the second workaround, that defines an alternative logical `or` operator: 
    130134 
    131135{{{ 
    132 data Bool = True | False -- no changes here 
    133  
    134 bBox :: Bool# -> Bool 
    135 bBox 1# = True 
    136 bBox 0# = False 
    137  
    138 bUnbox :: Bool -> Bool# 
    139 bUnbox True  = 1# 
    140 bUnbox False = 0# 
     136(||#) :: Bool -> Bool -> Bool 
     137(||#) x y = let xW = int2Word# (dataToTag# x) 
     138                yW = int2Word# (dataToTag# y) 
     139                zI = word2Int# (yW `or#` xW) 
     140            in tagToEnum# zI 
    141141}}} 
    142142 
    143 `Bool#` could not be implemented as an ADT because it is unlifted and unboxed, while ADT value constructors need to be boxed and lifted (see comments in [[GhcFile(compiler/types/TyCon.lhs)]]). There would need to be some magical way of ensuring that `Bool#` is populated only by `#0` and `1#` and that these values cannot be mixed with unboxed integers. Perhaps this could be done by preventing programmer from explicitly creating values of that type (can this be done?) and allow her only to use values returned from functions. 
     143This operator is defined in terms of primops `dataToTag#`, `tagToEnum#` and a bitwise or primop `or#`. Since the last one operates only on `Word`s we need to use `int2Word#` and `word2Int#` for conversion between these data types. Luckily, GHC does a good job of removing unnecessary conversions between data types. This means that: 
    144144 
    145 Another problem with this approach is that it would introduce primitive logical operations ||# and &&# with type `Int# -> Int# -> Int#` - it is questionable whether anyone would want such operations available to the programmer. I think it is desirable to have primitive logical operators of type `Bool# -> Bool# -> Bool#`. 
     145{{{ 
     146 case (x <# 0#) ||# (x >=# width) ||# (y <# 0#) ||# (y >=# height) of 
     147  True  -> E1 
     148  False -> E2 
     149}}} 
     150 
     151compiles to: 
     152 
     153{{{ 
     154case tagToEnum# 
     155       (word2Int# 
     156          (or# 
     157             (int2Word# (dataToTag# (>=# y height))) 
     158             (or# 
     159                (int2Word# (dataToTag# (<# y 0))) 
     160                (or# 
     161                   (int2Word# (dataToTag# (>=# x width))) 
     162                   (int2Word# (dataToTag# (<# x 0))))))) 
     163of _ { 
     164  False -> E2; 
     165  True  -> E1 
     166} 
     167}}} 
     168 
     169Primitive logical operators `&&#` and `not#` can be defined in a similar matter. 
     170 
     171== Solutions == 
     172 
     173It seems that the best solution to the problem would be implementing second of the above workarounds as a separate primop. Alternatively we can implement primitive bitwise `or`, `and` and `xor` that work on `Int`s instead of `Word`s and define new logical operators using bitwise operators in one of the libraries. 
    146174 
    147175== Places of interest in the source code == 
    148176 
    149 The file [[GhcFile(prelude/primops.txt.pp)]] defines !PrimOps and their type signatures. An example definition looks like this: 
    150  
    151 {{{ 
    152 primop   IntGtOp  ">#"   Compare   Int# -> Int# -> Bool 
    153    with fixity = infix 4 
    154 }}} 
    155  
    156 Existing definitions should remain unchanged or the code using them would break and that is a Very Bad Thing. This would require creating new !PrimOps: 
    157  
    158 {{{ 
    159 primop   IntGtOpB  ".>#"   Compare   Int# -> Int# -> Bool# 
    160    with fixity = infix 4 
    161 }}} 
    162  
    163 The tricky part here is `Compare`. This a value constructor of `PrimOpInfo` data type defined in [[GhcFile(prelude/PrimOp.lhs)]]: 
    164  
    165 {{{ 
    166 data PrimOpInfo 
    167   = Dyadic      OccName         -- string :: T -> T -> T 
    168                 Type 
    169   | Monadic     OccName         -- string :: T -> T 
    170                 Type 
    171   | Compare     OccName         -- string :: T -> T -> Bool 
    172                 Type 
    173   | GenPrimOp   OccName         -- string :: \/a1..an . T1 -> .. -> Tk -> T 
    174                 [TyVar] 
    175                 [Type] 
    176                 Type 
    177 }}} 
    178  
    179 We would need new `PrimOpInfo` value to denote !PrimOps of type `T -> T -> Bool#`. Appropriate functions like `primOpSig` and `getPrimOpResultInfo` would have to be adjusted accordingly. 
     177The file [[GhcFile(prelude/primops.txt.pp)]] defines !PrimOps and their type signatures.