Context Navigation

Changes between Version 7 and Version 8 of PrimBool

Timestamp:: 01/28/13 07:36:09 (4 months ago)
Author:: jstolarek
Comment:: --

Legend:

: Unmodified
: Added
: Removed
: Modified

PrimBool

v7	v8
51	51
52	52	and in following assembler code:
53
54	53	{{{
55	54	.Lc1rf:
…	…
80	79	There 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.
81	80
82		== ~~Possible solutions and their consequence~~s ==
	81	== Workarounds ==
83	82
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.
	83	It 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):
85	84
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	{{{
	86	ghci> import GHC.Exts
	87	ghci> import GHC.Prim
	88	ghci> :set -XMagicHash
	89	ghci> I# (dataToTag# True)
	90	1
	91	ghci> I# (dataToTag# False)
	92	0
	93	ghci> (tagToEnum# 0#) :: Bool
	94	False
	95	ghci> (tagToEnum# 1#) :: Bool
	96	True
	97	ghci>
95	98	}}}
96	99
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:
	100	Having 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
	106	First workaround assumes converting each result of comparison into an unboxed `Int` and replacing `\|\|` with `+#`:
98	107
99	108	{{{
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
102	113	}}}
103	114
104		This ~~approach might require one additional case expression to inspect the value of `Bool` at the Core level. For example~~:
	115	This compiles to:
105	116
106	117	{{{
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		}
	118	case +#
	119	(+#
	120	(+# (dataToTag# (<# x 0)) (dataToTag# (>=# x width)))
	121	(dataToTag# (<# y 0)))
	122	(dataToTag# (>=# y height))
	123	of _ {
	124	__DEFAULT -> E1;
	125	0 -> E2
122	126	}
123	127	}}}
124	128
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 ===
	129	Similarly we can convert logical && into multiplication.
128	130
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
	133	The 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:
130	134
131	135	{{{
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
141	141	}}}
142	142
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.
	143	This 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:
144	144
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
	151	compiles to:
	152
	153	{{{
	154	case 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)))))))
	163	of _ {
	164	False -> E2;
	165	True -> E1
	166	}
	167	}}}
	168
	169	Primitive logical operators `&&#` and `not#` can be defined in a similar matter.
	170
	171	== Solutions ==
	172
	173	It 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.
146	174
147	175	== Places of interest in the source code ==
148	176
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.
	177	The file [[GhcFile(prelude/primops.txt.pp)]] defines !PrimOps and their type signatures.