Add kind equalities to GHC.

This implements the ideas originally put forward in
"System FC with Explicit Kind Equality" (ICFP'13).

There are several noteworthy changes with this patch:
 * We now have casts in types. These change the kind
   of a type. See new constructor `CastTy`.

 * All types and all constructors can be promoted.
   This includes GADT constructors. GADT pattern matches
   take place in type family equations. In Core,
   types can now be applied to coercions via the
   `CoercionTy` constructor.

 * Coercions can now be heterogeneous, relating types
   of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2`
   proves both that `t1` and `t2` are the same and also that
   `k1` and `k2` are the same.

 * The `Coercion` type has been significantly enhanced.
   The documentation in `docs/core-spec/core-spec.pdf` reflects
   the new reality.

 * The type of `*` is now `*`. No more `BOX`.

 * Users can write explicit kind variables in their code,
   anywhere they can write type variables. For backward compatibility,
   automatic inference of kind-variable binding is still permitted.

 * The new extension `TypeInType` turns on the new user-facing
   features.

 * Type families and synonyms are now promoted to kinds. This causes
   trouble with parsing `*`, leading to the somewhat awkward new
   `HsAppsTy` constructor for `HsType`. This is dispatched with in
   the renamer, where the kind `*` can be told apart from a
   type-level multiplication operator. Without `-XTypeInType` the
   old behavior persists. With `-XTypeInType`, you need to import
   `Data.Kind` to get `*`, also known as `Type`.

 * The kind-checking algorithms in TcHsType have been significantly
   rewritten to allow for enhanced kinds.

 * The new features are still quite experimental and may be in flux.

 * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203.

 * TODO: Update user manual.

Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142.
Updates Haddock submodule.

13 files changed, 170 insertions, 170 deletions

diff --git a/compiler/nativeGen/RegAlloc/Graph/ArchBase.hs b/compiler/nativeGen/RegAlloc/Graph/ArchBase.hs
index deb3ac1b70..787b1d2f85 100644
--- a/compiler/nativeGen/RegAlloc/Graph/ArchBase.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/ArchBase.hs
@@ -4,10 +4,10 @@
 --   as per: "A Generalized Algorithm for Graph-Coloring Register Allocation"
 --           Michael Smith, Normal Ramsey, Glenn Holloway.
 --           PLDI 2004
---      
+--
 --   These general versions are not used in GHC proper because they are too slow.
 --   Instead, hand written optimised versions are provided for each architecture
---   in MachRegs*.hs 
+--   in MachRegs*.hs
 --
 --   This code is here because we can test the architecture specific code against
 --   it.
@@ -16,7 +16,7 @@ module RegAlloc.Graph.ArchBase (
         RegClass(..),
         Reg(..),
         RegSub(..),
-        
+
         worst,
         bound,
         squeese
@@ -33,7 +33,7 @@ data RegClass
         = ClassG32      -- 32 bit GPRs
         | ClassG16      -- 16 bit GPRs
         | ClassG8       -- 8  bit GPRs
-        
+
         -- floating point regs
         | ClassF64      -- 64 bit FPRs
         deriving (Show, Eq, Enum)
@@ -43,7 +43,7 @@ data RegClass
 data Reg
         -- a register of some class
         = Reg RegClass Int
-        
+
         -- a sub-component of one of the other regs
         | RegSub RegSub Reg
         deriving (Show, Eq)
@@ -56,7 +56,7 @@ instance Uniquable Reg where
          $ fromEnum c * 1000 + i
 
         getUnique (RegSub s (Reg c i))
-         = mkRegSubUnique 
+         = mkRegSubUnique
          $ fromEnum s * 10000 + fromEnum c * 1000 + i
 
         getUnique (RegSub _ (RegSub _ _))
@@ -69,11 +69,11 @@ data RegSub
         | SubL8         -- lowest  8 bits
         | SubL8H        -- second lowest 8 bits
         deriving (Show, Enum, Ord, Eq)
-        
+
 
 -- | Worst case displacement
 --
---      a node N of classN has some number of neighbors, 
+--      a node N of classN has some number of neighbors,
 --      all of which are from classC.
 --
 --      (worst neighbors classN classC) is the maximum number of potential
@@ -93,22 +93,22 @@ worst regsOfClass regAlias neighbors classN classC
         -- all the regs in classes N, C
         regsN           = regsOfClass classN
         regsC           = regsOfClass classC
-        
+
         -- all the possible subsets of c which have size < m
-        regsS           = filter (\s -> sizeUniqSet s >= 1 
+        regsS           = filter (\s -> sizeUniqSet s >= 1
                                      && sizeUniqSet s <= neighbors)
                         $ powersetLS regsC
 
         -- for each of the subsets of C, the regs which conflict
         -- with posiblities for N
-        regsS_conflict 
+        regsS_conflict
                 = map (\s -> intersectUniqSets regsN (regAliasS s)) regsS
 
   in    maximum $ map sizeUniqSet $ regsS_conflict
 
 
 -- | For a node N of classN and neighbors of classesC
---      (bound classN classesC) is the maximum number of potential 
+--      (bound classN classesC) is the maximum number of potential
 --      colors for N that can be lost by coloring its neighbors.
 bound   :: (RegClass    -> UniqSet Reg)
         -> (Reg         -> UniqSet Reg)
@@ -118,13 +118,13 @@ bound regsOfClass regAlias classN classesC
  = let  regAliasS regs  = unionManyUniqSets
                         $ map regAlias
                         $ uniqSetToList regs
- 
+
         regsC_aliases
                 = unionManyUniqSets
                 $ map (regAliasS . regsOfClass) classesC
 
         overlap = intersectUniqSets (regsOfClass classN) regsC_aliases
-   
+
    in   sizeUniqSet overlap
 
 
@@ -132,16 +132,16 @@ bound regsOfClass regAlias classN classesC
 --
 --   A version of this should be constructed for each particular architecture,
 --   possibly including uses of bound, so that alised registers don't get
---   counted twice, as per the paper.        
+--   counted twice, as per the paper.
 squeese :: (RegClass    -> UniqSet Reg)
         -> (Reg         -> UniqSet Reg)
         -> RegClass -> [(Int, RegClass)] -> Int
 
 squeese regsOfClass regAlias classN countCs
-        = sum 
-        $ map (\(i, classC) -> worst regsOfClass regAlias i classN classC) 
+        = sum
+        $ map (\(i, classC) -> worst regsOfClass regAlias i classN classC)
         $ countCs
-        
+
 
 -- | powerset (for lists)
 powersetL :: [a] -> [[a]]
diff --git a/compiler/nativeGen/RegAlloc/Graph/ArchX86.hs b/compiler/nativeGen/RegAlloc/Graph/ArchX86.hs
index c5122693d3..439899071a 100644
--- a/compiler/nativeGen/RegAlloc/Graph/ArchX86.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/ArchX86.hs
@@ -23,56 +23,56 @@ classOfReg :: Reg -> RegClass
 classOfReg reg
  = case reg of
         Reg c _         -> c
-        
+
         RegSub SubL16 _ -> ClassG16
         RegSub SubL8  _ -> ClassG8
         RegSub SubL8H _ -> ClassG8
 
-        
+
 -- | Determine all the regs that make up a certain class.
 regsOfClass :: RegClass -> UniqSet Reg
 regsOfClass c
  = case c of
-        ClassG32        
-         -> mkUniqSet   [ Reg ClassG32  i                     
+        ClassG32
+         -> mkUniqSet   [ Reg ClassG32  i
                         | i <- [0..7] ]
 
-        ClassG16        
+        ClassG16
          -> mkUniqSet   [ RegSub SubL16 (Reg ClassG32 i)
                         | i <- [0..7] ]
 
-        ClassG8 
+        ClassG8
          -> unionUniqSets
                 (mkUniqSet [ RegSub SubL8  (Reg ClassG32 i) | i <- [0..3] ])
                 (mkUniqSet [ RegSub SubL8H (Reg ClassG32 i) | i <- [0..3] ])
-                        
-        ClassF64        
+
+        ClassF64
          -> mkUniqSet   [ Reg ClassF64  i
                         | i <- [0..5] ]
-        
+
 
 -- | Determine the common name of a reg
 --      returns Nothing if this reg is not part of the machine.
 regName :: Reg -> Maybe String
 regName reg
  = case reg of
-        Reg ClassG32 i  
+        Reg ClassG32 i
          | i <= 7-> Just $ [ "eax", "ebx", "ecx", "edx"
                            , "ebp", "esi", "edi", "esp" ] !! i
 
         RegSub SubL16 (Reg ClassG32 i)
          | i <= 7 -> Just $ [ "ax", "bx", "cx", "dx"
                             , "bp", "si", "di", "sp"] !! i
-         
+
         RegSub SubL8  (Reg ClassG32 i)
          | i <= 3 -> Just $ [ "al", "bl", "cl", "dl"] !! i
-         
+
         RegSub SubL8H (Reg ClassG32 i)
          | i <= 3 -> Just $ [ "ah", "bh", "ch", "dh"] !! i
 
         _         -> Nothing
 
-        
+
 -- | Which regs alias what other regs.
 regAlias :: Reg -> UniqSet Reg
 regAlias reg
@@ -80,31 +80,31 @@ regAlias reg
 
         -- 32 bit regs alias all of the subregs
         Reg ClassG32 i
-         
+
          -- for eax, ebx, ecx, eds
-         |  i <= 3              
-         -> mkUniqSet 
+         |  i <= 3
+         -> mkUniqSet
          $ [ Reg ClassG32 i,   RegSub SubL16 reg
            , RegSub SubL8 reg, RegSub SubL8H reg ]
-         
+
          -- for esi, edi, esp, ebp
-         | 4 <= i && i <= 7     
-         -> mkUniqSet 
+         | 4 <= i && i <= 7
+         -> mkUniqSet
          $ [ Reg ClassG32 i,   RegSub SubL16 reg ]
-        
+
         -- 16 bit subregs alias the whole reg
-        RegSub SubL16 r@(Reg ClassG32 _)        
+        RegSub SubL16 r@(Reg ClassG32 _)
          ->     regAlias r
-        
+
         -- 8 bit subregs alias the 32 and 16, but not the other 8 bit subreg
         RegSub SubL8  r@(Reg ClassG32 _)
          -> mkUniqSet $ [ r, RegSub SubL16 r, RegSub SubL8 r ]
 
         RegSub SubL8H r@(Reg ClassG32 _)
          -> mkUniqSet $ [ r, RegSub SubL16 r, RegSub SubL8H r ]
-        
+
         -- fp
-        Reg ClassF64 _  
+        Reg ClassF64 _
          -> unitUniqSet reg
 
         _ -> error "regAlias: invalid register"
@@ -120,27 +120,27 @@ worst n classN classC
                 ClassG16        -> min n 8
                 ClassG8         -> min n 4
                 ClassF64        -> 0
-                
+
         ClassG16
          -> case classC of
                 ClassG32        -> min n 8
                 ClassG16        -> min n 8
                 ClassG8         -> min n 4
                 ClassF64        -> 0
-                
+
         ClassG8
          -> case classC of
                 ClassG32        -> min (n*2) 8
                 ClassG16        -> min (n*2) 8
                 ClassG8         -> min n 8
                 ClassF64        -> 0
-                
+
         ClassF64
          -> case classC of
                 ClassF64        -> min n 6
                 _               -> 0
-                
+
 squeese :: RegClass -> [(Int, RegClass)] -> Int
 squeese classN countCs
         = sum (map (\(i, classC) -> worst i classN classC) countCs)
-        
+
diff --git a/compiler/nativeGen/RegAlloc/Graph/Coalesce.hs b/compiler/nativeGen/RegAlloc/Graph/Coalesce.hs
index 69f0745dc3..7e8047f29f 100644
--- a/compiler/nativeGen/RegAlloc/Graph/Coalesce.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/Coalesce.hs
@@ -23,26 +23,26 @@ import Data.List
 --   second reg is born then the mov only serves to join live ranges.
 --   The two regs can be renamed to be the same and the move instruction
 --   safely erased.
-regCoalesce 
+regCoalesce
         :: Instruction instr
-        => [LiveCmmDecl statics instr] 
+        => [LiveCmmDecl statics instr]
         -> UniqSM [LiveCmmDecl statics instr]
 
 regCoalesce code
- = do   
+ = do
         let joins       = foldl' unionBags emptyBag
                         $ map slurpJoinMovs code
 
-        let alloc       = foldl' buildAlloc emptyUFM 
+        let alloc       = foldl' buildAlloc emptyUFM
                         $ bagToList joins
 
         let patched     = map (patchEraseLive (sinkReg alloc)) code
-                        
+
         return patched
 
 
 -- | Add a v1 = v2 register renaming to the map.
---   The register with the lowest lexical name is set as the 
+--   The register with the lowest lexical name is set as the
 --   canonical version.
 buildAlloc :: UniqFM Reg -> (Reg, Reg) -> UniqFM Reg
 buildAlloc fm (r1, r2)
@@ -57,23 +57,23 @@ sinkReg :: UniqFM Reg -> Reg -> Reg
 sinkReg fm r
  = case lookupUFM fm r of
         Nothing -> r
-        Just r' -> sinkReg fm r'        
-        
+        Just r' -> sinkReg fm r'
+
 
 -- | Slurp out mov instructions that only serve to join live ranges.
 --
 --   During a mov, if the source reg dies and the destiation reg is
 --   born then we can rename the two regs to the same thing and
 --   eliminate the move.
-slurpJoinMovs 
+slurpJoinMovs
         :: Instruction instr
-        => LiveCmmDecl statics instr 
+        => LiveCmmDecl statics instr
         -> Bag (Reg, Reg)
 
 slurpJoinMovs live
         = slurpCmm emptyBag live
- where  
-        slurpCmm   rs  CmmData{} 
+ where
+        slurpCmm   rs  CmmData{}
          = rs
 
         slurpCmm   rs (CmmProc _ _ _ sccs)
@@ -81,7 +81,7 @@ slurpJoinMovs live
 
         slurpBlock rs (BasicBlock _ instrs)
          = foldl' slurpLI    rs instrs
-                
+
         slurpLI    rs (LiveInstr _      Nothing)    = rs
         slurpLI    rs (LiveInstr instr (Just live))
                 | Just (r1, r2) <- takeRegRegMoveInstr instr
@@ -90,10 +90,10 @@ slurpJoinMovs live
 
                 -- only coalesce movs between two virtuals for now,
                 -- else we end up with allocatable regs in the live
-                -- regs list.. 
+                -- regs list..
                 , isVirtualReg r1 && isVirtualReg r2
                 = consBag (r1, r2) rs
-                
+
                 | otherwise
                 = rs
-        
+
diff --git a/compiler/nativeGen/RegAlloc/Graph/Main.hs b/compiler/nativeGen/RegAlloc/Graph/Main.hs
index 8d5a4dbabd..52ed438f81 100644
--- a/compiler/nativeGen/RegAlloc/Graph/Main.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/Main.hs
@@ -30,7 +30,7 @@ import Control.Monad
 
 
 -- | The maximum number of build\/spill cycles we'll allow.
---  
+--
 --   It should only take 3 or 4 cycles for the allocator to converge.
 --   If it takes any longer than this it's probably in an infinite loop,
 --   so it's better just to bail out and report a bug.
@@ -71,11 +71,11 @@ regAlloc dflags regsFree slotsFree code
 -- | Perform solver iterations for the graph coloring allocator.
 --
 --   We extract a register confict graph from the provided cmm code,
---   and try to colour it. If that works then we use the solution rewrite 
+--   and try to colour it. If that works then we use the solution rewrite
 --   the code with real hregs. If coloring doesn't work we add spill code
 --   and try to colour it again. After `maxSpinCount` iterations we give up.
 --
-regAlloc_spin 
+regAlloc_spin
         :: (Instruction instr,
             Outputable instr,
             Outputable statics)
@@ -110,7 +110,7 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
            (  text "It looks like the register allocator is stuck in an infinite loop."
            $$ text "max cycles  = " <> int maxSpinCount
            $$ text "regsFree    = " <> (hcat $ punctuate space $ map ppr
-                                             $ uniqSetToList $ unionManyUniqSets 
+                                             $ uniqSetToList $ unionManyUniqSets
                                              $ eltsUFM regsFree)
            $$ text "slotsFree   = " <> ppr (sizeUniqSet slotsFree))
 
@@ -126,7 +126,7 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
         seqGraph graph `seq` return ()
 
         -- Build a map of the cost of spilling each instruction.
-        -- This is a lazy binding, so the map will only be computed if we 
+        -- This is a lazy binding, so the map will only be computed if we
         -- actually have to spill to the stack.
         let spillCosts  = foldl' plusSpillCostInfo zeroSpillCostInfo
                         $ map (slurpSpillCostInfo platform) code
@@ -135,7 +135,7 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
         let spill       = chooseSpill spillCosts
 
         -- Record startup state in our log.
-        let stat1       
+        let stat1
              = if spinCount == 0
                  then   Just $ RegAllocStatsStart
                         { raLiveCmm     = code
@@ -179,7 +179,7 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
                                 else graph_colored
 
                 -- Rewrite the code to use real hregs, using the colored graph.
-                let code_patched        
+                let code_patched
                         = map (patchRegsFromGraph platform graph_colored_lint)
                               code_coalesced
 
@@ -197,7 +197,7 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
                         = map (stripLive dflags) code_spillclean
 
                 -- Record what happened in this stage for debugging
-                let stat                
+                let stat
                      =  RegAllocStatsColored
                         { raCode                = code
                         , raGraph               = graph
@@ -207,11 +207,11 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
                         , raPatched             = code_patched
                         , raSpillClean          = code_spillclean
                         , raFinal               = code_final
-                        , raSRMs                = foldl' addSRM (0, 0, 0) 
+                        , raSRMs                = foldl' addSRM (0, 0, 0)
                                                 $ map countSRMs code_spillclean }
 
                 -- Bundle up all the register allocator statistics.
-                --   .. but make sure to drop them on the floor if they're not 
+                --   .. but make sure to drop them on the floor if they're not
                 --      needed, otherwise we'll get a space leak.
                 let statList =
                         if dump then [stat] ++ maybeToList stat1 ++ debug_codeGraphs
@@ -243,7 +243,7 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
                 -- NOTE: we have to reverse the SCCs here to get them back into
                 --       the reverse-dependency order required by computeLiveness.
                 --       If they're not in the correct order that function will panic.
-                code_relive     <- mapM (regLiveness platform . reverseBlocksInTops) 
+                code_relive     <- mapM (regLiveness platform . reverseBlocksInTops)
                                         code_spilled
 
                 -- Record what happened in this stage for debugging.
@@ -257,7 +257,7 @@ regAlloc_spin dflags spinCount triv regsFree slotsFree debug_codeGraphs code
                         , raSpilled     = code_spilled }
 
                 -- Bundle up all the register allocator statistics.
-                --   .. but make sure to drop them on the floor if they're not 
+                --   .. but make sure to drop them on the floor if they're not
                 --      needed, otherwise we'll get a space leak.
                 let statList =
                         if dump
@@ -289,7 +289,7 @@ buildGraph code
 
         -- Add the reg-reg conflicts to the graph.
         let conflictBag         = unionManyBags conflictList
-        let graph_conflict      
+        let graph_conflict
                 = foldrBag graphAddConflictSet Color.initGraph conflictBag
 
         -- Add the coalescences edges to the graph.
@@ -381,7 +381,7 @@ patchRegsFromGraph platform graph code
                 -- no node in the graph for this virtual, bad news.
                 | otherwise
                 = pprPanic "patchRegsFromGraph: register mapping failed."
-                        (  text "There is no node in the graph for register " 
+                        (  text "There is no node in the graph for register "
                                 <> ppr reg
                         $$ ppr code
                         $$ Color.dotGraph
diff --git a/compiler/nativeGen/RegAlloc/Graph/Spill.hs b/compiler/nativeGen/RegAlloc/Graph/Spill.hs
index 7267ef8eae..1ec8d1276f 100644
--- a/compiler/nativeGen/RegAlloc/Graph/Spill.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/Spill.hs
@@ -46,7 +46,7 @@ regSpill
         -> UniqSet Int                  -- ^ available stack slots
         -> UniqSet VirtualReg           -- ^ the regs to spill
         -> UniqSM
-            ([LiveCmmDecl statics instr] 
+            ([LiveCmmDecl statics instr]
                  -- code with SPILL and RELOAD meta instructions added.
             , UniqSet Int               -- left over slots
             , SpillStats )              -- stats about what happened during spilling
@@ -83,9 +83,9 @@ regSpill platform code slotsFree regs
 regSpill_top
         :: Instruction instr
         => Platform
-        -> RegMap Int                   
+        -> RegMap Int
                 -- ^ map of vregs to slots they're being spilled to.
-        -> LiveCmmDecl statics instr    
+        -> LiveCmmDecl statics instr
                 -- ^ the top level thing.
         -> SpillM (LiveCmmDecl statics instr)
 
@@ -109,7 +109,7 @@ regSpill_top platform regSlotMap cmm
                 -- after we've done a successful allocation.
                 let liveSlotsOnEntry' :: Map BlockId (Set Int)
                     liveSlotsOnEntry'
-                        = mapFoldWithKey patchLiveSlot 
+                        = mapFoldWithKey patchLiveSlot
                                          liveSlotsOnEntry liveVRegsOnEntry
 
                 let info'
@@ -126,12 +126,12 @@ regSpill_top platform regSlotMap cmm
         -- if registers in this block are being spilled to stack slots,
         -- then record the fact that these slots are now live in those blocks
         -- in the given slotmap.
-        patchLiveSlot 
-                :: BlockId -> RegSet 
+        patchLiveSlot
+                :: BlockId -> RegSet
                 -> Map BlockId (Set Int) -> Map BlockId (Set Int)
 
         patchLiveSlot blockId regsLive slotMap
-         = let  
+         = let
                 -- Slots that are already recorded as being live.
                 curSlotsLive    = fromMaybe Set.empty
                                 $ Map.lookup blockId slotMap
@@ -142,7 +142,7 @@ regSpill_top platform regSlotMap cmm
                                 $ uniqSetToList regsLive
 
                 slotMap'
-                 = Map.insert blockId (Set.union curSlotsLive moreSlotsLive) 
+                 = Map.insert blockId (Set.union curSlotsLive moreSlotsLive)
                               slotMap
 
            in   slotMap'
@@ -295,10 +295,10 @@ patchInstr reg instr
         -- If it's not then something has gone horribly wrong.
         let nReg
              = case reg of
-                RegVirtual vr   
+                RegVirtual vr
                  -> RegVirtual (renameVirtualReg nUnique vr)
 
-                RegReal{}       
+                RegReal{}
                  -> panic "RegAlloc.Graph.Spill.patchIntr: not patching real reg"
 
         let instr'      = patchReg1 reg nReg instr
diff --git a/compiler/nativeGen/RegAlloc/Graph/SpillClean.hs b/compiler/nativeGen/RegAlloc/Graph/SpillClean.hs
index 01ab3efff1..f472d29270 100644
--- a/compiler/nativeGen/RegAlloc/Graph/SpillClean.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/SpillClean.hs
@@ -50,7 +50,7 @@ import qualified Data.Set       as Set
 
 
 -- | The identification number of a spill slot.
---   A value is stored in a spill slot when we don't have a free 
+--   A value is stored in a spill slot when we don't have a free
 --   register to hold it.
 type Slot = Int
 
@@ -58,8 +58,8 @@ type Slot = Int
 -- | Clean out unneeded spill\/reloads from this top level thing.
 cleanSpills
         :: Instruction instr
-        => Platform 
-        -> LiveCmmDecl statics instr 
+        => Platform
+        -> LiveCmmDecl statics instr
         -> LiveCmmDecl statics instr
 
 cleanSpills platform cmm
@@ -84,7 +84,7 @@ cleanSpin platform spinCount code
 
         code_forward    <- mapBlockTopM (cleanBlockForward platform) code
         code_backward   <- cleanTopBackward code_forward
-        
+
         -- During the cleaning of each block we collected information about
         -- what regs were valid across each jump. Based on this, work out
         -- whether it will be safe to erase reloads after join points for
@@ -158,7 +158,7 @@ cleanForward platform blockId assoc acc (li1 : li2 : instrs)
         = do
                 modify $ \s -> s { sCleanedReloadsAcc = sCleanedReloadsAcc s + 1 }
                 cleanForward platform blockId assoc acc
-                 $ li1 : LiveInstr (mkRegRegMoveInstr platform reg1 reg2) Nothing 
+                 $ li1 : LiveInstr (mkRegRegMoveInstr platform reg1 reg2) Nothing
                        : instrs
 
 cleanForward platform blockId assoc acc (li@(LiveInstr i1 _) : instrs)
@@ -245,7 +245,7 @@ cleanReload platform blockId assoc li@(LiveInstr (RELOAD slot reg) _)
         | otherwise
         = do    -- Update the association.
                 let assoc'
-                        = addAssoc (SReg reg)  (SSlot slot)     
+                        = addAssoc (SReg reg)  (SSlot slot)
                                 -- doing the reload makes reg and slot the same value
                         $ delAssoc (SReg reg)
                                 -- reg value changes on reload
@@ -290,7 +290,7 @@ cleanReload _ _ _ _
 --       we should really be updating the noReloads set as we cross jumps also.
 --
 -- TODO: generate noReloads from liveSlotsOnEntry
--- 
+--
 cleanTopBackward
         :: Instruction instr
         => LiveCmmDecl statics instr
@@ -300,17 +300,17 @@ cleanTopBackward cmm
  = case cmm of
         CmmData{}
          -> return cmm
-        
+
         CmmProc info label live sccs
          | LiveInfo _ _ _ liveSlotsOnEntry <- info
          -> do  sccs'   <- mapM (mapSCCM (cleanBlockBackward liveSlotsOnEntry)) sccs
-                return  $ CmmProc info label live sccs' 
+                return  $ CmmProc info label live sccs'
 
 
-cleanBlockBackward 
+cleanBlockBackward
         :: Instruction instr
         => Map BlockId (Set Int)
-        -> LiveBasicBlock instr 
+        -> LiveBasicBlock instr
         -> CleanM (LiveBasicBlock instr)
 
 cleanBlockBackward liveSlotsOnEntry (BasicBlock blockId instrs)
@@ -332,7 +332,7 @@ cleanBackward liveSlotsOnEntry noReloads acc lis
         cleanBackward' liveSlotsOnEntry reloadedBy noReloads acc lis
 
 
-cleanBackward' 
+cleanBackward'
         :: Instruction instr
         => Map BlockId (Set Int)
         -> UniqFM [BlockId]
@@ -379,17 +379,17 @@ cleanBackward' liveSlotsOnEntry reloadedBy noReloads acc (li : instrs)
         --       liveness map doesn't get updated.
         | LiveInstr instr _     <- li
         , targets               <- jumpDestsOfInstr instr
-        = do    
+        = do
                 let slotsReloadedByTargets
                         = Set.unions
                         $ catMaybes
-                        $ map (flip Map.lookup liveSlotsOnEntry) 
+                        $ map (flip Map.lookup liveSlotsOnEntry)
                         $ targets
-                
+
                 let noReloads'
-                        = foldl' delOneFromUniqSet noReloads 
+                        = foldl' delOneFromUniqSet noReloads
                         $ Set.toList slotsReloadedByTargets
-                
+
                 cleanBackward liveSlotsOnEntry noReloads' (li : acc) instrs
 
         -- some other instruction
@@ -423,7 +423,7 @@ findRegOfSlot assoc slot
 
 -------------------------------------------------------------------------------
 -- | Cleaner monad.
-type CleanM 
+type CleanM
         = State CleanS
 
 -- | Cleaner state.
diff --git a/compiler/nativeGen/RegAlloc/Graph/SpillCost.hs b/compiler/nativeGen/RegAlloc/Graph/SpillCost.hs
index 97616baaf1..a797514482 100644
--- a/compiler/nativeGen/RegAlloc/Graph/SpillCost.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/SpillCost.hs
@@ -136,12 +136,12 @@ slurpSpillCostInfo platform cmm
 
 -- | Take all the virtual registers from this set.
 takeVirtuals :: UniqSet Reg -> UniqSet VirtualReg
-takeVirtuals set 
+takeVirtuals set
         = mapUniqSet get_virtual
         $ filterUniqSet isVirtualReg set
         where
-                get_virtual (RegVirtual vr) = vr 
-                get_virtual _ = panic "getVirt" 
+                get_virtual (RegVirtual vr) = vr
+                get_virtual _ = panic "getVirt"
 
 
 -- | Choose a node to spill from this graph
@@ -215,7 +215,7 @@ spillCost_chaitin info graph reg
         = 0
 
         -- Otherwise revert to chaitin's regular cost function.
-        | otherwise     = fromIntegral (uses + defs) 
+        | otherwise     = fromIntegral (uses + defs)
                         / fromIntegral (nodeDegree graph reg)
         where (_, defs, uses, lifetime)
                 = fromMaybe (reg, 0, 0, 0) $ lookupUFM info reg
@@ -232,7 +232,7 @@ spillCost_length info _ reg
         | lifetime <= 1         = 1/0
         | otherwise             = 1 / fromIntegral lifetime
         where (_, _, _, lifetime)
-                = fromMaybe (reg, 0, 0, 0) 
+                = fromMaybe (reg, 0, 0, 0)
                 $ lookupUFM info reg
 
 
@@ -246,19 +246,19 @@ lifeMapFromSpillCostInfo info
 
 -- | Determine the degree (number of neighbors) of this node which
 --   have the same class.
-nodeDegree 
+nodeDegree
         :: (VirtualReg -> RegClass)
-        -> Graph VirtualReg RegClass RealReg 
-        -> VirtualReg 
+        -> Graph VirtualReg RegClass RealReg
+        -> VirtualReg
         -> Int
 
 nodeDegree classOfVirtualReg graph reg
         | Just node     <- lookupUFM (graphMap graph) reg
 
-        , virtConflicts 
-           <- length       
+        , virtConflicts
+           <- length
            $ filter (\r -> classOfVirtualReg r == classOfVirtualReg reg)
-           $ uniqSetToList 
+           $ uniqSetToList
            $ nodeConflicts node
 
         = virtConflicts + sizeUniqSet (nodeExclusions node)
@@ -269,11 +269,11 @@ nodeDegree classOfVirtualReg graph reg
 
 -- | Show a spill cost record, including the degree from the graph
 --   and final calulated spill cost.
-pprSpillCostRecord 
+pprSpillCostRecord
         :: (VirtualReg -> RegClass)
         -> (Reg -> SDoc)
-        -> Graph VirtualReg RegClass RealReg 
-        -> SpillCostRecord 
+        -> Graph VirtualReg RegClass RealReg
+        -> SpillCostRecord
         -> SDoc
 
 pprSpillCostRecord regClass pprReg graph (reg, uses, defs, life)
@@ -283,6 +283,6 @@ pprSpillCostRecord regClass pprReg graph (reg, uses, defs, life)
         , ppr defs
         , ppr life
         , ppr $ nodeDegree regClass graph reg
-        , text $ show $ (fromIntegral (uses + defs) 
+        , text $ show $ (fromIntegral (uses + defs)
                        / fromIntegral (nodeDegree regClass graph reg) :: Float) ]
 
diff --git a/compiler/nativeGen/RegAlloc/Graph/Stats.hs b/compiler/nativeGen/RegAlloc/Graph/Stats.hs
index 8fada96ee2..07f4266b48 100644
--- a/compiler/nativeGen/RegAlloc/Graph/Stats.hs
+++ b/compiler/nativeGen/RegAlloc/Graph/Stats.hs
@@ -41,13 +41,13 @@ data RegAllocStats statics instr
         -- Information about the initial conflict graph.
         = RegAllocStatsStart
         { -- | Initial code, with liveness.
-          raLiveCmm     :: [LiveCmmDecl statics instr]                  
+          raLiveCmm     :: [LiveCmmDecl statics instr]
 
           -- | The initial, uncolored graph.
-        , raGraph       :: Color.Graph VirtualReg RegClass RealReg      
+        , raGraph       :: Color.Graph VirtualReg RegClass RealReg
 
           -- | Information to help choose which regs to spill.
-        , raSpillCosts  :: SpillCostInfo }                              
+        , raSpillCosts  :: SpillCostInfo }
 
 
         -- Information about an intermediate graph.
@@ -55,22 +55,22 @@ data RegAllocStats statics instr
         -- instruction stream.
         | RegAllocStatsSpill
         { -- | Code we tried to allocate registers for.
-          raCode        :: [LiveCmmDecl statics instr]                  
+          raCode        :: [LiveCmmDecl statics instr]
 
           -- | Partially colored graph.
         , raGraph       :: Color.Graph VirtualReg RegClass RealReg
 
           -- | The regs that were coaleced.
-        , raCoalesced   :: UniqFM VirtualReg                            
+        , raCoalesced   :: UniqFM VirtualReg
 
           -- | Spiller stats.
-        , raSpillStats  :: SpillStats                                   
+        , raSpillStats  :: SpillStats
 
           -- | Number of instructions each reg lives for.
-        , raSpillCosts  :: SpillCostInfo                                
+        , raSpillCosts  :: SpillCostInfo
 
           -- | Code with spill instructions added.
-        , raSpilled     :: [LiveCmmDecl statics instr] }                
+        , raSpilled     :: [LiveCmmDecl statics instr] }
 
 
         -- a successful coloring
@@ -103,7 +103,7 @@ data RegAllocStats statics instr
         , raSRMs          :: (Int, Int, Int) }
 
 
-instance (Outputable statics, Outputable instr) 
+instance (Outputable statics, Outputable instr)
        => Outputable (RegAllocStats statics instr) where
 
  ppr (s@RegAllocStatsStart{}) = sdocWithPlatform $ \platform ->
@@ -141,7 +141,7 @@ instance (Outputable statics, Outputable instr)
         $$ ppr (raSpilled s)
 
 
- ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) }) 
+ ppr (s@RegAllocStatsColored { raSRMs = (spills, reloads, moves) })
     = sdocWithPlatform $ \platform ->
            text "#  Colored"
 
@@ -304,7 +304,7 @@ countSRMs cmm
         = execState (mapBlockTopM countSRM_block cmm) (0, 0, 0)
 
 
-countSRM_block 
+countSRM_block
         :: Instruction instr
         => GenBasicBlock (LiveInstr instr)
         -> State (Int, Int, Int) (GenBasicBlock (LiveInstr instr))
diff --git a/compiler/nativeGen/RegAlloc/Linear/Main.hs b/compiler/nativeGen/RegAlloc/Linear/Main.hs
index bee091b584..2d593c626d 100644
--- a/compiler/nativeGen/RegAlloc/Linear/Main.hs
+++ b/compiler/nativeGen/RegAlloc/Linear/Main.hs
@@ -657,12 +657,12 @@ saveClobberedTemps clobbered dying
               -- (2) no free registers: spill the value
               [] -> do
                   (spill, slot)   <- spillR (RegReal reg) temp
-     
+
                   -- record why this reg was spilled for profiling
                   recordSpill (SpillClobber temp)
-     
+
                   let new_assign  = addToUFM assig temp (InBoth reg slot)
-     
+
                   clobber new_assign (spill : instrs) rest
 
 
diff --git a/compiler/nativeGen/RegAlloc/Linear/PPC/FreeRegs.hs b/compiler/nativeGen/RegAlloc/Linear/PPC/FreeRegs.hs
index b76fe79d7d..a2a6dacb65 100644
--- a/compiler/nativeGen/RegAlloc/Linear/PPC/FreeRegs.hs
+++ b/compiler/nativeGen/RegAlloc/Linear/PPC/FreeRegs.hs
@@ -37,7 +37,7 @@ releaseReg (RealRegSingle r) (FreeRegs g f)
 
 releaseReg _ _
         = panic "RegAlloc.Linear.PPC.releaseReg: bad reg"
-    
+
 initFreeRegs :: Platform -> FreeRegs
 initFreeRegs platform = foldr releaseReg noFreeRegs (allocatableRegs platform)
 
@@ -52,7 +52,7 @@ getFreeRegs cls (FreeRegs g f)
                  | otherwise    = go x (m `shiftR` 1) $! i-1
 
 allocateReg :: RealReg -> FreeRegs -> FreeRegs
-allocateReg (RealRegSingle r) (FreeRegs g f) 
+allocateReg (RealRegSingle r) (FreeRegs g f)
     | r > 31    = FreeRegs g (f .&. complement (1 `shiftL` (r - 32)))
     | otherwise = FreeRegs (g .&. complement (1 `shiftL` r)) f
 
diff --git a/compiler/nativeGen/RegAlloc/Linear/SPARC/FreeRegs.hs b/compiler/nativeGen/RegAlloc/Linear/SPARC/FreeRegs.hs
index 2cb9999ce7..89a9407b71 100644
--- a/compiler/nativeGen/RegAlloc/Linear/SPARC/FreeRegs.hs
+++ b/compiler/nativeGen/RegAlloc/Linear/SPARC/FreeRegs.hs
@@ -28,8 +28,8 @@ import Data.Bits
 --
 --      Free regs have a bit set in the corresponding bitmap.
 --
-data FreeRegs 
-        = FreeRegs 
+data FreeRegs
+        = FreeRegs
                 !Word32         -- int    reg bitmap    regs  0..31
                 !Word32         -- float  reg bitmap    regs 32..63
                 !Word32         -- double reg bitmap    regs 32..63
@@ -47,23 +47,23 @@ initFreeRegs :: Platform -> FreeRegs
 initFreeRegs platform
  =      foldr (releaseReg platform) noFreeRegs allocatableRegs
 
-                        
+
 -- | Get all the free registers of this class.
 getFreeRegs :: RegClass -> FreeRegs -> [RealReg]        -- lazily
 getFreeRegs cls (FreeRegs g f d)
-        | RcInteger <- cls = map RealRegSingle                  $ go 1 g 1 0  
-        | RcFloat   <- cls = map RealRegSingle                  $ go 1 f 1 32 
-        | RcDouble  <- cls = map (\i -> RealRegPair i (i+1))    $ go 2 d 1 32 
+        | RcInteger <- cls = map RealRegSingle                  $ go 1 g 1 0
+        | RcFloat   <- cls = map RealRegSingle                  $ go 1 f 1 32
+        | RcDouble  <- cls = map (\i -> RealRegPair i (i+1))    $ go 2 d 1 32
         | otherwise = pprPanic "RegAllocLinear.getFreeRegs: Bad register class " (ppr cls)
         where
                 go _    _      0    _
                         = []
 
-                go step bitmap mask ix 
-                        | bitmap .&. mask /= 0 
-                        = ix : (go step bitmap (mask `shiftL` step) $! ix + step) 
+                go step bitmap mask ix
+                        | bitmap .&. mask /= 0
+                        = ix : (go step bitmap (mask `shiftL` step) $! ix + step)
 
-                        | otherwise    
+                        | otherwise
                         = go step bitmap (mask `shiftL` step) $! ix + step
 
 
@@ -76,19 +76,19 @@ allocateReg platform
         -- can't allocate free regs
         | not $ freeReg platform r
         = pprPanic "SPARC.FreeRegs.allocateReg: not allocating pinned reg" (ppr reg)
-        
+
         -- a general purpose reg
         | r <= 31
         = let   mask    = complement (bitMask r)
-          in    FreeRegs 
-                        (g .&. mask) 
-                        f 
+          in    FreeRegs
+                        (g .&. mask)
+                        f
                         d
 
         -- a float reg
         | r >= 32, r <= 63
         = let   mask    = complement (bitMask (r - 32))
-        
+
                 -- the mask of the double this FP reg aliases
                 maskLow = if r `mod` 2 == 0
                                 then complement (bitMask (r - 32))
@@ -100,11 +100,11 @@ allocateReg platform
 
         | otherwise
         = pprPanic "SPARC.FreeRegs.releaseReg: not allocating bad reg" (ppr reg)
-                        
+
 allocateReg _
          reg@(RealRegPair r1 r2)
              (FreeRegs g f d)
-        
+
         | r1 >= 32, r1 <= 63, r1 `mod` 2 == 0
         , r2 >= 32, r2 <= 63
         = let   mask1   = complement (bitMask (r1 - 32))
@@ -114,19 +114,19 @@ allocateReg _
                         g
                         ((f .&. mask1) .&. mask2)
                         (d .&. mask1)
-                        
+
         | otherwise
         = pprPanic "SPARC.FreeRegs.releaseReg: not allocating bad reg" (ppr reg)
- 
+
 
 
 -- | Release a register from allocation.
---      The register liveness information says that most regs die after a C call, 
+--      The register liveness information says that most regs die after a C call,
 --      but we still don't want to allocate to some of them.
 --
 releaseReg :: Platform -> RealReg -> FreeRegs -> FreeRegs
 releaseReg platform
-         reg@(RealRegSingle r) 
+         reg@(RealRegSingle r)
         regs@(FreeRegs g f d)
 
         -- don't release pinned reg
@@ -134,28 +134,28 @@ releaseReg platform
         = regs
 
         -- a general purpose reg
-        | r <= 31       
+        | r <= 31
         = let   mask    = bitMask r
           in    FreeRegs (g .|. mask) f d
 
         -- a float reg
         | r >= 32, r <= 63
         = let   mask    = bitMask (r - 32)
-                
+
                 -- the mask of the double this FP reg aliases
                 maskLow = if r `mod` 2 == 0
                                 then bitMask (r - 32)
                                 else bitMask (r - 32 - 1)
-          in    FreeRegs 
-                        g 
+          in    FreeRegs
+                        g
                         (f .|. mask)
                         (d .|. maskLow)
 
         | otherwise
         = pprPanic "SPARC.FreeRegs.releaseReg: not releasing bad reg" (ppr reg)
-        
+
 releaseReg _
-         reg@(RealRegPair r1 r2) 
+         reg@(RealRegPair r1 r2)
              (FreeRegs g f d)
 
         | r1 >= 32, r1 <= 63, r1 `mod` 2 == 0
@@ -167,10 +167,10 @@ releaseReg _
                         g
                         ((f .|. mask1) .|. mask2)
                         (d .|. mask1)
-                        
+
         | otherwise
         = pprPanic "SPARC.FreeRegs.releaseReg: not releasing bad reg" (ppr reg)
-           
+
 
 
 bitMask :: Int -> Word32
diff --git a/compiler/nativeGen/RegAlloc/Linear/StackMap.hs b/compiler/nativeGen/RegAlloc/Linear/StackMap.hs
index 85ea6771b8..748fb98c30 100644
--- a/compiler/nativeGen/RegAlloc/Linear/StackMap.hs
+++ b/compiler/nativeGen/RegAlloc/Linear/StackMap.hs
@@ -28,8 +28,8 @@ import Unique
 -- | Identifier for a stack slot.
 type StackSlot = Int
 
-data StackMap 
-        = StackMap 
+data StackMap
+        = StackMap
         { -- | The slots that are still available to be allocated.
           stackMapNextFreeSlot  :: !Int
 
diff --git a/compiler/nativeGen/RegAlloc/Linear/Stats.hs b/compiler/nativeGen/RegAlloc/Linear/Stats.hs
index 83f5fbc950..b7d93f4436 100644
--- a/compiler/nativeGen/RegAlloc/Linear/Stats.hs
+++ b/compiler/nativeGen/RegAlloc/Linear/Stats.hs
@@ -33,7 +33,7 @@ binSpillReasons reasons
 
 
 -- | Count reg-reg moves remaining in this code.
-countRegRegMovesNat 
+countRegRegMovesNat
         :: Instruction instr
         => NatCmmDecl statics instr -> Int
 
@@ -54,8 +54,8 @@ countRegRegMovesNat cmm
 
 
 -- | Pretty print some RegAllocStats
-pprStats 
-        :: Instruction instr 
+pprStats
+        :: Instruction instr
         => [NatCmmDecl statics instr] -> [RegAllocStats] -> SDoc
 
 pprStats code statss