reg-alloc-graph-color (empty) → 0.0.0.0
raw patch · 12 files changed
+907/−0 lines, 12 filesdep +Mapdep +basedep +base-unicode-symbols
Dependencies added: Map, base, base-unicode-symbols, containers, criterion, lenz, lenz-mtl, lenz-template, logict, microlens-mtl, mtl, peano, reg-alloc-graph-color, smallcheck, tasty, tasty-smallcheck, transformers, util
Files
- LICENSE +373/−0
- README.md +1/−0
- bench/Main.hs +6/−0
- reg-alloc-graph-color.cabal +94/−0
- src/RegAlloc.hs +173/−0
- src/RegAlloc/Interference.hs +30/−0
- src/RegAlloc/Nodes.hs +31/−0
- src/RegAlloc/Nodes/Private.hs +9/−0
- src/RegAlloc/UGraph.hs +24/−0
- src/RegAlloc/UGraph/Private.hs +71/−0
- test/Main.hs +8/−0
- test/Tests/RegAlloc.hs +87/−0
+ LICENSE view
@@ -0,0 +1,373 @@+Mozilla Public License Version 2.0+==================================++1. Definitions+--------------++1.1. "Contributor"+ means each individual or legal entity that creates, contributes to+ the creation of, or owns Covered Software.++1.2. "Contributor Version"+ means the combination of the Contributions of others (if any) used+ by a Contributor and that particular Contributor's Contribution.++1.3. "Contribution"+ means Covered Software of a particular Contributor.++1.4. "Covered Software"+ means Source Code Form to which the initial Contributor has attached+ the notice in Exhibit A, the Executable Form of such Source Code+ Form, and Modifications of such Source Code Form, in each case+ including portions thereof.++1.5. "Incompatible With Secondary Licenses"+ means++ (a) that the initial Contributor has attached the notice described+ in Exhibit B to the Covered Software; or++ (b) that the Covered Software was made available under the terms of+ version 1.1 or earlier of the License, but not also under the+ terms of a Secondary License.++1.6. "Executable Form"+ means any form of the work other than Source Code Form.++1.7. "Larger Work"+ means a work that combines Covered Software with other material, in+ a separate file or files, that is not Covered Software.++1.8. "License"+ means this document.++1.9. "Licensable"+ means having the right to grant, to the maximum extent possible,+ whether at the time of the initial grant or subsequently, any and+ all of the rights conveyed by this License.++1.10. "Modifications"+ means any of the following:++ (a) any file in Source Code Form that results from an addition to,+ deletion from, or modification of the contents of Covered+ Software; or++ (b) any new file in Source Code Form that contains any Covered+ Software.++1.11. "Patent Claims" of a Contributor+ means any patent claim(s), including without limitation, method,+ process, and apparatus claims, in any patent Licensable by such+ Contributor that would be infringed, but for the grant of the+ License, by the making, using, selling, offering for sale, having+ made, import, or transfer of either its Contributions or its+ Contributor Version.++1.12. "Secondary License"+ means either the GNU General Public License, Version 2.0, the GNU+ Lesser General Public License, Version 2.1, the GNU Affero General+ Public License, Version 3.0, or any later versions of those+ licenses.++1.13. "Source Code Form"+ means the form of the work preferred for making modifications.++1.14. "You" (or "Your")+ means an individual or a legal entity exercising rights under this+ License. For legal entities, "You" includes any entity that+ controls, is controlled by, or is under common control with You. For+ purposes of this definition, "control" means (a) the power, direct+ or indirect, to cause the direction or management of such entity,+ whether by contract or otherwise, or (b) ownership of more than+ fifty percent (50%) of the outstanding shares or beneficial+ ownership of such entity.++2. License Grants and Conditions+--------------------------------++2.1. Grants++Each Contributor hereby grants You a world-wide, royalty-free,+non-exclusive license:++(a) under intellectual property rights (other than patent or trademark)+ Licensable by such Contributor to use, reproduce, make available,+ modify, display, perform, distribute, and otherwise exploit its+ Contributions, either on an unmodified basis, with Modifications, or+ as part of a Larger Work; and++(b) under Patent Claims of such Contributor to make, use, sell, offer+ for sale, have made, import, and otherwise transfer either its+ Contributions or its Contributor Version.++2.2. Effective Date++The licenses granted in Section 2.1 with respect to any Contribution+become effective for each Contribution on the date the Contributor first+distributes such Contribution.++2.3. Limitations on Grant Scope++The licenses granted in this Section 2 are the only rights granted under+this License. No additional rights or licenses will be implied from the+distribution or licensing of Covered Software under this License.+Notwithstanding Section 2.1(b) above, no patent license is granted by a+Contributor:++(a) for any code that a Contributor has removed from Covered Software;+ or++(b) for infringements caused by: (i) Your and any other third party's+ modifications of Covered Software, or (ii) the combination of its+ Contributions with other software (except as part of its Contributor+ Version); or++(c) under Patent Claims infringed by Covered Software in the absence of+ its Contributions.++This License does not grant any rights in the trademarks, service marks,+or logos of any Contributor (except as may be necessary to comply with+the notice requirements in Section 3.4).++2.4. Subsequent Licenses++No Contributor makes additional grants as a result of Your choice to+distribute the Covered Software under a subsequent version of this+License (see Section 10.2) or under the terms of a Secondary License (if+permitted under the terms of Section 3.3).++2.5. Representation++Each Contributor represents that the Contributor believes its+Contributions are its original creation(s) or it has sufficient rights+to grant the rights to its Contributions conveyed by this License.++2.6. Fair Use++This License is not intended to limit any rights You have under+applicable copyright doctrines of fair use, fair dealing, or other+equivalents.++2.7. Conditions++Sections 3.1, 3.2, 3.3, and 3.4 are conditions of the licenses granted+in Section 2.1.++3. Responsibilities+-------------------++3.1. Distribution of Source Form++All distribution of Covered Software in Source Code Form, including any+Modifications that You create or to which You contribute, must be under+the terms of this License. You must inform recipients that the Source+Code Form of the Covered Software is governed by the terms of this+License, and how they can obtain a copy of this License. You may not+attempt to alter or restrict the recipients' rights in the Source Code+Form.++3.2. Distribution of Executable Form++If You distribute Covered Software in Executable Form then:++(a) such Covered Software must also be made available in Source Code+ Form, as described in Section 3.1, and You must inform recipients of+ the Executable Form how they can obtain a copy of such Source Code+ Form by reasonable means in a timely manner, at a charge no more+ than the cost of distribution to the recipient; and++(b) You may distribute such Executable Form under the terms of this+ License, or sublicense it under different terms, provided that the+ license for the Executable Form does not attempt to limit or alter+ the recipients' rights in the Source Code Form under this License.++3.3. Distribution of a Larger Work++You may create and distribute a Larger Work under terms of Your choice,+provided that You also comply with the requirements of this License for+the Covered Software. If the Larger Work is a combination of Covered+Software with a work governed by one or more Secondary Licenses, and the+Covered Software is not Incompatible With Secondary Licenses, this+License permits You to additionally distribute such Covered Software+under the terms of such Secondary License(s), so that the recipient of+the Larger Work may, at their option, further distribute the Covered+Software under the terms of either this License or such Secondary+License(s).++3.4. Notices++You may not remove or alter the substance of any license notices+(including copyright notices, patent notices, disclaimers of warranty,+or limitations of liability) contained within the Source Code Form of+the Covered Software, except that You may alter any license notices to+the extent required to remedy known factual inaccuracies.++3.5. Application of Additional Terms++You may choose to offer, and to charge a fee for, warranty, support,+indemnity or liability obligations to one or more recipients of Covered+Software. However, You may do so only on Your own behalf, and not on+behalf of any Contributor. You must make it absolutely clear that any+such warranty, support, indemnity, or liability obligation is offered by+You alone, and You hereby agree to indemnify every Contributor for any+liability incurred by such Contributor as a result of warranty, support,+indemnity or liability terms You offer. You may include additional+disclaimers of warranty and limitations of liability specific to any+jurisdiction.++4. Inability to Comply Due to Statute or Regulation+---------------------------------------------------++If it is impossible for You to comply with any of the terms of this+License with respect to some or all of the Covered Software due to+statute, judicial order, or regulation then You must: (a) comply with+the terms of this License to the maximum extent possible; and (b)+describe the limitations and the code they affect. Such description must+be placed in a text file included with all distributions of the Covered+Software under this License. Except to the extent prohibited by statute+or regulation, such description must be sufficiently detailed for a+recipient of ordinary skill to be able to understand it.++5. Termination+--------------++5.1. The rights granted under this License will terminate automatically+if You fail to comply with any of its terms. However, if You become+compliant, then the rights granted under this License from a particular+Contributor are reinstated (a) provisionally, unless and until such+Contributor explicitly and finally terminates Your grants, and (b) on an+ongoing basis, if such Contributor fails to notify You of the+non-compliance by some reasonable means prior to 60 days after You have+come back into compliance. Moreover, Your grants from a particular+Contributor are reinstated on an ongoing basis if such Contributor+notifies You of the non-compliance by some reasonable means, this is the+first time You have received notice of non-compliance with this License+from such Contributor, and You become compliant prior to 30 days after+Your receipt of the notice.++5.2. If You initiate litigation against any entity by asserting a patent+infringement claim (excluding declaratory judgment actions,+counter-claims, and cross-claims) alleging that a Contributor Version+directly or indirectly infringes any patent, then the rights granted to+You by any and all Contributors for the Covered Software under Section+2.1 of this License shall terminate.++5.3. In the event of termination under Sections 5.1 or 5.2 above, all+end user license agreements (excluding distributors and resellers) which+have been validly granted by You or Your distributors under this License+prior to termination shall survive termination.++************************************************************************+* *+* 6. Disclaimer of Warranty *+* ------------------------- *+* *+* Covered Software is provided under this License on an "as is" *+* basis, without warranty of any kind, either expressed, implied, or *+* statutory, including, without limitation, warranties that the *+* Covered Software is free of defects, merchantable, fit for a *+* particular purpose or non-infringing. The entire risk as to the *+* quality and performance of the Covered Software is with You. *+* Should any Covered Software prove defective in any respect, You *+* (not any Contributor) assume the cost of any necessary servicing, *+* repair, or correction. This disclaimer of warranty constitutes an *+* essential part of this License. No use of any Covered Software is *+* authorized under this License except under this disclaimer. *+* *+************************************************************************++************************************************************************+* *+* 7. Limitation of Liability *+* -------------------------- *+* *+* Under no circumstances and under no legal theory, whether tort *+* (including negligence), contract, or otherwise, shall any *+* Contributor, or anyone who distributes Covered Software as *+* permitted above, be liable to You for any direct, indirect, *+* special, incidental, or consequential damages of any character *+* including, without limitation, damages for lost profits, loss of *+* goodwill, work stoppage, computer failure or malfunction, or any *+* and all other commercial damages or losses, even if such party *+* shall have been informed of the possibility of such damages. This *+* limitation of liability shall not apply to liability for death or *+* personal injury resulting from such party's negligence to the *+* extent applicable law prohibits such limitation. Some *+* jurisdictions do not allow the exclusion or limitation of *+* incidental or consequential damages, so this exclusion and *+* limitation may not apply to You. *+* *+************************************************************************++8. Litigation+-------------++Any litigation relating to this License may be brought only in the+courts of a jurisdiction where the defendant maintains its principal+place of business and such litigation shall be governed by laws of that+jurisdiction, without reference to its conflict-of-law provisions.+Nothing in this Section shall prevent a party's ability to bring+cross-claims or counter-claims.++9. Miscellaneous+----------------++This License represents the complete agreement concerning the subject+matter hereof. If any provision of this License is held to be+unenforceable, such provision shall be reformed only to the extent+necessary to make it enforceable. Any law or regulation which provides+that the language of a contract shall be construed against the drafter+shall not be used to construe this License against a Contributor.++10. Versions of the License+---------------------------++10.1. New Versions++Mozilla Foundation is the license steward. Except as provided in Section+10.3, no one other than the license steward has the right to modify or+publish new versions of this License. Each version will be given a+distinguishing version number.++10.2. Effect of New Versions++You may distribute the Covered Software under the terms of the version+of the License under which You originally received the Covered Software,+or under the terms of any subsequent version published by the license+steward.++10.3. Modified Versions++If you create software not governed by this License, and you want to+create a new license for such software, you may create and use a+modified version of this License if you rename the license and remove+any references to the name of the license steward (except to note that+such modified license differs from this License).++10.4. Distributing Source Code Form that is Incompatible With Secondary+Licenses++If You choose to distribute Source Code Form that is Incompatible With+Secondary Licenses under the terms of this version of the License, the+notice described in Exhibit B of this License must be attached.++Exhibit A - Source Code Form License Notice+-------------------------------------------++ This Source Code Form is subject to the terms of the Mozilla Public+ License, v. 2.0. If a copy of the MPL was not distributed with this+ file, You can obtain one at http://mozilla.org/MPL/2.0/.++If it is not possible or desirable to put the notice in a particular+file, then You may include the notice in a location (such as a LICENSE+file in a relevant directory) where a recipient would be likely to look+for such a notice.++You may add additional accurate notices of copyright ownership.++Exhibit B - "Incompatible With Secondary Licenses" Notice+---------------------------------------------------------++ This Source Code Form is "Incompatible With Secondary Licenses", as+ defined by the Mozilla Public License, v. 2.0.
+ README.md view
@@ -0,0 +1,1 @@+# reg-alloc
+ bench/Main.hs view
@@ -0,0 +1,6 @@+module Main where++import Criterion.Main++main :: IO ()+main = defaultMain []
+ reg-alloc-graph-color.cabal view
@@ -0,0 +1,94 @@+cabal-version: 2.2+name: reg-alloc-graph-color+version: 0.0.0.0+synopsis: Register allocation by graph colorization+-- description:+license: MPL-2.0+license-file: LICENSE+author: M Farkas-Dyck+maintainer: strake888@gmail.com+copyright: 2019 M Farkas-Dyck+-- category: +build-type: Simple+extra-source-files: README.md++common c+ default-language: Haskell2010+ default-extensions: UnicodeSyntax+ , LambdaCase+ , EmptyCase+ , InstanceSigs+ , PartialTypeSignatures+ , PolyKinds+ , ConstraintKinds+ , FlexibleContexts+ , FlexibleInstances+ , MonadComprehensions+ , StandaloneDeriving+ , DeriveFunctor, DeriveFoldable, DeriveTraversable+ ghc-options: -Wall -Wcompat -Wredundant-constraints -Wno-name-shadowing+ -Wincomplete-record-updates -Wincomplete-uni-patterns+ -Werror=incomplete-patterns+ -Werror=incomplete-uni-patterns+ -Werror=incomplete-record-updates+ -Werror=missing-fields+ -Werror=missing-methods++library+ import: c+ hs-source-dirs: src+ reexported-modules: RegAlloc+ build-depends: private+ default-language: Haskell2010++library private+ import: c+ hs-source-dirs: src+ exposed-modules: RegAlloc+ , RegAlloc.Interference+ , RegAlloc.Nodes+ , RegAlloc.Nodes.Private+ , RegAlloc.UGraph+ , RegAlloc.UGraph.Private+ build-depends: Map+ , base >= 4.8 && < 5+ , base-unicode-symbols >= 0.2 && < 0.3+ , containers >= 0.5 && < 0.7+ , lenz >= 0.4 && < 0.5+ , lenz-mtl >= 0.1 && < 0.2+ , lenz-template+ , microlens-mtl >= 0.2 && < 0.3+ , mtl >= 2.0 && < 2.3+ , peano >= 0.1 && < 0.2+ , transformers >= 0.4 && < 0.6+ , util >= 0.1.14 && < 0.2++test-suite test+ import: c+ type: exitcode-stdio-1.0+ hs-source-dirs: test+ main-is: Main.hs+ other-modules: Tests.RegAlloc+ build-depends: base >=4.11 && <5+ , base-unicode-symbols+ , containers+ , logict+ , smallcheck >=1.1.4+ , tasty >=1.0+ , tasty-smallcheck >=0.8+ , transformers+ , util+ , private++benchmark bench+ import: c+ type: exitcode-stdio-1.0+ hs-source-dirs: bench+ main-is: Main.hs+ build-depends: base >=4.11 && <5+ , criterion >=1.4.1+ , reg-alloc-graph-color++source-repository head+ type: git+ location: https://github.com/strake/reg-alloc-graph-color.hs
+ src/RegAlloc.hs view
@@ -0,0 +1,173 @@+{-# LANGUAGE BlockArguments #-}+{-# LANGUAGE TemplateHaskell #-}+{-# OPTIONS_GHC -Wno-partial-type-signatures #-}+module RegAlloc (Operation (..), RegCount, allocRegs, allocRegs', colorize) where++import Prelude hiding (id, (.))+import Control.Applicative+import Control.Category+import Control.Lens.TH (mkLens)+import Control.Monad (guard, join)+import Control.Monad.Except+import Control.Monad.State+import qualified Control.Monad.State.Lens as ML+import Control.Monad.Writer+import Data.Bool (bool)+import Data.Foldable (find, toList, traverse_)+import Data.IntMap (IntMap)+import qualified Data.IntMap as IM+import Data.IntSet (IntSet)+import qualified Data.IntSet as IS+import qualified Data.List as List+import Data.Ord (Down (..))+import Data.Peano+import Data.Traversable (for)+import qualified Lens.Micro.Mtl as ML+import Util hiding ((∈))++import RegAlloc.Interference (Interferences, Node (..), Operands, UGraph, interferences, interferes, (!), (∈))+import qualified RegAlloc.Interference as If+import qualified RegAlloc.Nodes as Nodes+import qualified RegAlloc.UGraph as UGr++data St = St+ { _degree :: !Int+ , _ifs :: !Interferences+ , _moves :: !Moves+ }+ deriving (Eq, Show)++type Moves = UGraph++$(mkLens (dropWhile (== '_')) ''St)++allocRegs :: (Traversable f) => RegCount -> f Operation -> Except Interferences (f Int)+allocRegs deg insns = do+ colors <- (allocRegs' deg ifm >=> uncurry (colorize deg ifm)) moves+ for (count insns) \ (k, _) -> maybe (throwError ifm) pure $ colors IM.!? k+ where+ ifm = interferences insns'+ insns' = (\ case NonMove xs -> xs; Move x -> Nodes.fromList [x]) <$> insns+ moves =+ UGr.insertEdges [(k', k :: Int) | (k, Move k') <- toList (count insns)] (UGr.empty deg)++allocRegs' :: RegCount -> Interferences -> Moves -> Except Interferences ([Op], Colors)+allocRegs' deg ifm theMoves =+ execWriterT . flip evalStateT (St { _degree = 1, _ifs = ifm, _moves = theMoves }) $+ whileM (untilFixpointBy (==) (simplifyAndCoalescePhase >> freezePhase) >>+ not . If.null <$> ML.gets ifs) potentialSpillPhase+ where+ simplifyAndCoalescePhase = doWhileM bumpDegree do+ St { _degree = deg } <- get+ untilFixpointBy (==) do+ _ <- untilFixpointBy (==) simplify+ St { _ifs = theIfs, _moves = theMoves } <- get+ let isCoalescibleMove (k, k') =+ not (interferes k' k theIfs) && coalescible deg k' k theIfs+ for (find isCoalescibleMove (UGr.edges theMoves)) \ (k, k') -> coalesce1 k' k+ freezePhase = do+ St { _degree = deg, _ifs = theIfs, _moves = theMoves } <- get+ case [k | k <- [0..deg-1]+ , k' <- Nodes.toList (theMoves ! k)+ , not $ If.interferes k' k theIfs+ , Nodes.size (theIfs ! k) < deg] of+ [] -> pure ()+ k:_ -> () <$ ML.puts moves (UGr.deleteNode k theMoves)+ potentialSpillPhase = do+ k <- ML.zoom ifs potentialSpill+ deleteNode k+ tell ([Select k], IM.empty)+ bumpDegree = compare deg <$> ML.gets degree >>= \ case+ GT -> True <$ ML.modify degree (+1)+ _ -> pure False++colorize+ :: (MonadError Interferences m, Foldable t)+ => RegCount -> Interferences -> t Op -> Colors -> m Colors+colorize deg ifm = execStateT . traverse_ \ case+ Select k -> do+ colors <- get+ let nbrs = ifm ! k+ nbrColors = IS.fromList+ [c | nbr <- Nodes.toList nbrs+ , Just c <- [case nbr of+ Node k -> colors IM.!? k+ Precolored c -> Just c]]+ go k $ find (`IS.notMember` nbrColors) [0..deg-1]+ Coalesce k k' -> go k =<< gets (IM.!? k')+ where go k = maybe (throwError ifm) (modify . IM.insert k)++data Op = Select !Int | Coalesce !Int !Int+ deriving (Show)++deleteNode :: MonadState St m => Int -> m ()+deleteNode k = traverse_ ($ UGr.deleteNode k) [ML.modify ifs, ML.modify moves]++deleteNodes :: MonadState St m => IntSet -> m ()+deleteNodes ks = traverse_ ($ UGr.deleteNodes ks) [ML.modify ifs, ML.modify moves]++coalesce1 :: (MonadState St m, MonadWriter ([Op], Colors) m) => Node -> Int -> m ()+coalesce1 k' k = do+ traverse_ ($ UGr.coalesce k' k) [ML.modify ifs, ML.modify moves]+ tell case k' of+ Node k' -> ([Coalesce k k'], IM.empty)+ Precolored c -> ([], IM.singleton k c)++simplify :: (MonadState St m, MonadWriter ([Op], Colors) m) => m ()+simplify =+ concatMap IS.toList <$> untilFixpointBy (==) simplify1 >>=+ tell . flip (,) IM.empty . fmap Select++simplify1 :: MonadState St m => m IntSet+simplify1 = do+ St { _degree = deg, _ifs = theIfs, _moves = theMoves } <- get+ let moveRelateds = foldMap IS.fromList [[k, k'] | (k, Node k') <- UGr.edges theMoves]+ delenda = IS.fromAscList+ [k | (k, ks) <- If.toAscList theIfs+ , IS.notMember k moveRelateds && k >= 0 && Nodes.size ks < deg]+ delenda <$ deleteNodes delenda++untilFixpointBy :: (MonadState s m) => (s -> s -> Bool) -> m a -> m [a]+untilFixpointBy eq x = go [] where+ go as = do+ s <- get+ a <- x+ t <- get+ bool (go . (a:)) pure (eq s t) as++whileM :: Monad m => m Bool -> m a -> m [a]+whileM = compose2 whileJust (fmap guard) pure++doWhileM :: Monad m => m Bool -> m a -> m [a]+doWhileM p = liftA2 (:) <*> whileM p++coalescible :: RegCount -> Node -> Int -> Interferences -> Bool+coalescible n = join \ case+ Node _ -> briggs n+ Precolored _ -> george n++briggs, george :: RegCount -> Node -> Int -> Interferences -> Bool+briggs n a b ifm = (fromIntegral n :: Peano) > flip count' (Nodes.toList (ifm' ! b)) \ case+ Node c -> Nodes.size (ifm' ! c) > n+ Precolored _ -> True+ where+ ifm' = UGr.coalesce a b ifm+ count' f = List.genericLength . filter f+george n a b ifm = flip all (Nodes.toList (ifm ! b)) \ case+ Node c -> let nbrs = ifm ! c+ in Nodes.size nbrs < n || a ∈ nbrs+ c@(Precolored _) -> all (c ∈) aNbrs'+ where+ aNbrs' = case a of+ Precolored _ -> Nothing+ Node a -> Just (ifm ! a)++potentialSpill :: (MonadState Interferences m, MonadError Interferences m) => m Int+potentialSpill = List.sortOn (Down . Nodes.size . snd) . If.toAscList <$> get >>= \ case+ [] -> get >>= throwError+ (k, _):_ -> pure k++data Operation = Move !Node | NonMove !Operands++type RegCount = Int+type Colors = IntMap Int
+ src/RegAlloc/Interference.hs view
@@ -0,0 +1,30 @@+{-# LANGUAGE BlockArguments #-}+module RegAlloc.Interference (module RegAlloc.UGraph, Interferences, Operands, interferes, interferences) where++import Control.Monad.Trans.State (state, evalState)+import Data.Functor.Reverse (Reverse (..))+import Data.Map.Class (Union (..))+import qualified Data.Map.Class as Map+import Data.IntSet (IntSet)+import qualified Data.IntSet as IS+import Util hiding ((∈))++import RegAlloc.Nodes.Private+import RegAlloc.UGraph+import RegAlloc.UGraph.Private++type Interferences = UGraph++interferes :: Node -> Int -> Interferences -> Bool+interferes = hasEdge++interferences :: (Traversable f) => f Operands -> UGraph+interferences = (.) UGr $+ liveSets & foldMap \ ks -> Union $ Map.fromList [(k, ks) | k <- IS.toList ks]++liveSets :: (Traversable f) => f Operands -> f LiveSet+liveSets = getReverse . flip evalState IS.empty . traverse (go . fmap unNodes) . Reverse . count+ where go (k, ks) = state $ (,) <*> IS.insert k . flip IS.difference ks++type Operands = Nodes+type LiveSet = IntSet
+ src/RegAlloc/Nodes.hs view
@@ -0,0 +1,31 @@+{-# LANGUAGE PatternSynonyms #-}+{-# LANGUAGE ViewPatterns #-}+module RegAlloc.Nodes (Node (Precolored, Node), Nodes, toList, fromList, fromAscList, size, (∈)) where++import Control.Monad (guard)+import Data.Bits (complement)+import qualified Data.IntSet as IS++import RegAlloc.Nodes.Private++pattern Precolored :: Int -> Node+pattern Precolored n <- Node_ ((\ n -> complement n <$ guard (n < 0)) -> Just n)+ where Precolored n = Node_ (complement n)+pattern Node :: Int -> Node+pattern Node n <- Node_ (n@((>= 0) -> True)) where Node n = Node_ n+{-# COMPLETE Precolored, Node #-}++toList :: Nodes -> [Node]+toList = fmap Node_ . IS.toList . unNodes++fromList :: [Node] -> Nodes+fromList = Nodes . IS.fromList . fmap unNode_++fromAscList :: [Node] -> Nodes+fromAscList = Nodes . IS.fromAscList . fmap unNode_++size :: Nodes -> Int+size = IS.size . unNodes++(∈) :: Node -> Nodes -> Bool+Node_ n ∈ Nodes ns = IS.member n ns
+ src/RegAlloc/Nodes/Private.hs view
@@ -0,0 +1,9 @@+module RegAlloc.Nodes.Private where++import Data.IntSet (IntSet)++newtype Node = Node_ { unNode_ :: Int }+ deriving (Eq, Show)++newtype Nodes = Nodes { unNodes :: IntSet }+ deriving (Eq, Show)
+ src/RegAlloc/UGraph.hs view
@@ -0,0 +1,24 @@+{-# LANGUAGE BlockArguments #-}+module RegAlloc.UGraph+ ( Node (Precolored, Node)+ , UGraph+ , Nodes+ , nbrsOf+ , coalesce+ , coalesceIfNoEdge+ , (!), (Nodes.∈)+ , hasEdge+ , toAscList+ , deleteNode+ , deleteNodes+ , nullEdges+ , insertEdge+ , insertEdges+ , empty+ , null+ , edges+ ) where++import Prelude hiding (null)+import RegAlloc.Nodes as Nodes+import RegAlloc.UGraph.Private
+ src/RegAlloc/UGraph/Private.hs view
@@ -0,0 +1,71 @@+{-# LANGUAGE BlockArguments #-}+{-# LANGUAGE DerivingVia #-}+module RegAlloc.UGraph.Private where++import Prelude hiding (null)+import Control.Monad ((>=>))+import qualified Data.Foldable as Foldable+import Data.IntMap (IntMap)+import qualified Data.IntMap as IM+import Data.IntSet (IntSet)+import qualified Data.IntSet as IS+import Data.Map.Class (Union (..), (!?))+import qualified Data.Map.Class as Map+import Data.Maybe (fromMaybe)++import qualified RegAlloc.Nodes as Nodes+import RegAlloc.Nodes.Private++newtype UGraph = UGr { unUGr :: Union IntMap IntSet }+ deriving (Eq, Show)+ deriving (Semigroup, Monoid) via (Union IntMap IntSet)++null, nullEdges :: UGraph -> Bool+null = Foldable.null . unUGr+nullEdges = (all . \ f -> all f . IS.toList) (< 0) . unUGr++(!) :: UGraph -> Int -> Nodes+(!) = flip nbrsOf++nbrsOf :: Int -> UGraph -> Nodes+nbrsOf k+ | k < 0 = pure (Nodes mempty)+ | True = Nodes . fromMaybe mempty . (!? k) . unUGr++coalesce, coalesceIfNoEdge :: Node -> Int -> UGraph -> UGraph+coalesce (Node_ a) b =+ UGr . fmap (replaceIS b a) . Map.delete b .+ (\ gr -> Map.adjust (maybe id (<>) (gr Map.!? b) . IS.delete b) a gr) . unUGr+coalesceIfNoEdge a b gr+ | hasEdge a b gr = gr+ | otherwise = coalesce a b gr++replaceIS :: Int -> Int -> IntSet -> IntSet+replaceIS a b as+ | IS.member a as = IS.insert b . IS.delete a $ as+ | otherwise = as++hasEdge :: Node -> Int -> UGraph -> Bool+hasEdge a b ifm = a Nodes.∈ (ifm ! b)++toAscList :: UGraph -> [(Int, Nodes)]+toAscList = IM.toAscList . fmap Nodes . unUnion . unUGr++deleteNode :: Int -> UGraph -> UGraph+deleteNode k = UGr . fmap (IS.delete k) . Map.delete k . unUGr++deleteNodes :: IntSet -> UGraph -> UGraph+deleteNodes ks = UGr . fmap (flip IS.difference ks) . flip (IS.foldr Map.delete) ks . unUGr++insertEdge :: Node -> Int -> UGraph -> UGraph+insertEdge (Node_ k') k = UGr . go k' k . go k k' . unUGr where+ go i j = Map.adjust (IS.insert j) i++insertEdges :: [(Node, Int)] -> UGraph -> UGraph+insertEdges = flip $ foldr (uncurry insertEdge)++empty :: Int -> UGraph+empty k = (UGr . Map.fromList) [(k, IS.empty) | k <- [0..k-1]]++edges :: UGraph -> [(Int, Node)]+edges = toAscList >=> \ (k, ks') -> [(k, k') | k' <- Nodes.toList ks']
+ test/Main.hs view
@@ -0,0 +1,8 @@+module Main where++import Test.Tasty++import qualified Tests.RegAlloc as RegAlloc++main :: IO ()+main = defaultMain $ testGroup "" [RegAlloc.test]
+ test/Tests/RegAlloc.hs view
@@ -0,0 +1,87 @@+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveAnyClass #-}+{-# LANGUAGE NamedFieldPuns #-}+{-# LANGUAGE DuplicateRecordFields #-}+{-# LANGUAGE RecordWildCards #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE BlockArguments #-}+{-# LANGUAGE MonadComprehensions #-}+module Tests.RegAlloc where++import Control.Monad ((>=>), guard)+import Control.Monad.Logic.Class+import Control.Monad.Trans.Class+import Control.Monad.Trans.Except+import Control.Monad.Trans.Reader+import Data.Bool (bool)+import qualified Data.Foldable.Unicode as Foldable+import Data.Function (on)+import qualified Data.IntMap as IM+import qualified Data.IntSet as IS++import GHC.Generics++import Test.SmallCheck.Series hiding ((<~>))+import Test.Tasty (TestTree)+import Test.Tasty.SmallCheck++import RegAlloc+import RegAlloc.Interference as If+import RegAlloc.UGraph as UGr+import RegAlloc.Nodes as Nodes+import RegAlloc.Nodes.Private++test :: TestTree+test = testProperty "allocRegs" \ (Problem { regCount, ifs, moves }) ->+ case runExcept $ (allocRegs' regCount ifs >=> uncurry (colorize regCount ifs)) moves of+ Left _ -> Right ""+ Right colors -> "" <$ runExcept do+ bool (throwE $ "bad register: " ++ show colors) (pure ()) $ all (< regCount) colors+ bool (throwE $ "bad domain: " ++ show colors) (pure ()) $ IM.keysSet colors == IS.fromAscList (fst <$> If.toAscList ifs)+ bool (throwE $ "bad answer: " ++ show colors) (pure ()) $ flip all (IM.toList colors) \ (k, color) ->+ let nbrColors = (\ case Node k -> colors IM.! k; Precolored c -> c) <$> Nodes.toList (nbrsOf k ifs)+ in color Foldable.∉ nbrColors++data Problem = Problem+ { regCount, nodeCount :: !Int, ifs :: !Interferences, moves :: !UGraph }+ deriving (Eq, Show, Generic)++instance Monad m => Serial m Problem where+ series = series >>- \ parms@(Parms { regCount, nodeCount }) -> flip runReaderT parms $+ [Problem {..} | (ifs, moves) <- (,) <$> ugrSeries <~> ugrSeries]++data Parms = Parms+ { regCount, nodeCount :: !Int }+ deriving (Eq, Show, Generic)+deriving instance Monad m => Serial m Parms++ugrSeries :: Monad m => ReaderT Parms (Series m) UGraph+ugrSeries = do+ Parms { nodeCount } <- ask+ flip UGr.insertEdges (UGr.empty nodeCount) <$> mapReaderT (sortedListSBy p) edgeSeries+ where p = (<) `on` \ (Node_ i, j) -> (i, j)++edgeSeries :: Monad m => ReaderT Parms (Series m) (Node, Int)+edgeSeries = do+ Parms { nodeCount } <- ask+ k' <- nodeSeries+ lift $ getNonNegative <$> series >>- \ k ->+ (k', k) <$ guard (unNode_ k' < k && k < nodeCount)++nodeSeries :: Monad m => ReaderT Parms (Series m) Node+nodeSeries = do+ Parms { regCount, nodeCount } <- ask+ lift $ Node_ <$> rangeS (-regCount, nodeCount)++sortedListSBy :: Monad m => (a -> a -> Bool) -> Series m a -> Series m [a]+sortedListSBy p as = decDepth (pure []) `interleave` decDepth (as >>- go) where+ go a = (:) a <$> decDepth (pure [] `interleave` do b <- as; guard (p a b); go b)++rangeS :: Monad m => (Int, Int) -> Series m Int+rangeS (a, b) = do+ k <- series+ k <$ guard (k >= a && k < b)++infixl 4 <~>+(<~>) :: MonadLogic m => m (a -> b) -> m a -> m b+a <~> b = a >>- (<$> b)