1 -- | Graph Coloring.

2 -- This is a generic graph coloring library, abstracted over the type of

3 -- the node keys, nodes and colors.

4 --

10 colorGraph

11 )

13 where

15 import GraphBase

16 import GraphOps

17 import GraphPpr

19 import Unique

20 import UniqFM

21 import UniqSet

22 import Outputable

28 -- | Try to color a graph with this set of colors.

29 -- Uses Chaitin's algorithm to color the graph.

30 -- The graph is scanned for nodes which are deamed 'trivially colorable'. These nodes

31 -- are pushed onto a stack and removed from the graph.

32 -- Once this process is complete the graph can be colored by removing nodes from

33 -- the stack (ie in reverse order) and assigning them colors different to their neighbors.

34 --

35 colorGraph

43 -> (Graph k cls color -> k) -- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.

49 -- r1 should be replaced by r2 in the source

51 colorGraph iterative spinCount colors triv spill graph0

53 -- If we're not doing iterative coalescing then do an aggressive coalescing first time

54 -- around and then conservative coalescing for subsequent passes.

55 --

56 -- Aggressive coalescing is a quick way to get rid of many reg-reg moves. However, if

57 -- there is a lot of register pressure and we do it on every round then it can make the

58 -- graph less colorable and prevent the algorithm from converging in a sensible number

59 -- of cycles.

60 --

68 -- run the scanner to slurp out all the trivially colorable nodes

69 -- (and do coalescing if iterative coalescing is enabled)

71 = colorScan iterative triv spill graph_coalesced

73 -- If iterative coalescing is enabled, the scanner will coalesce the graph as does its business.

74 -- We need to apply all the coalescences found by the scanner to the original

75 -- graph before doing assignColors.

76 --

77 -- Because we've got the whole, non-pruned graph here we turn on aggressive coalecing

78 -- to force all the (conservative) coalescences found during scanning.

79 --

83 -- color the trivially colorable nodes

84 -- during scanning, keys of triv nodes were added to the front of the list as they were found

85 -- this colors them in the reverse order, as required by the algorithm.

87 = assignColors colors graph_scan_coalesced ksTriv

89 -- try and color the problem nodes

90 -- problem nodes are the ones that were left uncolored because they weren't triv.

91 -- theres a change we can color them here anyway.

93 = assignColors colors graph_triv ksProblems

95 -- if the trivially colorable nodes didn't color then something is probably wrong

96 -- with the provided triv function.

97 --

114 -- | Scan through the conflict graph separating out trivially colorable and

115 -- potentially uncolorable (problem) nodes.

116 --

117 -- Checking whether a node is trivially colorable or not is a resonably expensive operation,

118 -- so after a triv node is found and removed from the graph it's no good to return to the 'start'

119 -- of the graph and recheck a bunch of nodes that will probably still be non-trivially colorable.

120 --

121 -- To ward against this, during each pass through the graph we collect up a list of triv nodes

122 -- that were found, and only remove them once we've finished the pass. The more nodes we can delete

123 -- at once the more likely it is that nodes we've already checked will become trivially colorable

124 -- for the next pass.

125 --

126 -- TODO: add work lists to finding triv nodes is easier.

127 -- If we've just scanned the graph, and removed triv nodes, then the only

128 -- nodes that we need to rescan are the ones we've removed edges from.

130 colorScan

136 -> (Graph k cls color -> k) -- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.

141 colorScan iterative triv spill graph

144 colorScan_spin

149 -> Triv k cls color

151 -> Graph k cls color

157 colorScan_spin iterative triv spill graph

158 ksTriv ksSpill kksCoalesce

160 -- if the graph is empty then we're done

161 | isNullUFM $ graphMap graph

164 -- Simplify:

165 -- Look for trivially colorable nodes.

166 -- If we can find some then remove them from the graph and go back for more.

167 --

171 -- for iterative coalescing we only want non-move related

172 -- nodes here

174 $ graph

179 graph ksTrivFound

181 = colorScan_spin iterative triv spill graph2

183 ksSpill

184 kksCoalesce

186 -- Coalesce:

187 -- If we're doing iterative coalescing and no triv nodes are avaliable

188 -- then it's time for a coalescing pass.

189 | iterative

192 -- we were able to coalesce something

193 -- go back to Simplify and see if this frees up more nodes to be trivially colorable.

195 -> colorScan_spin iterative triv spill graph2

198 -- Freeze:

199 -- nothing could be coalesced (or was triv),

200 -- time to choose a node to freeze and give up on ever coalescing it.

204 -- we were able to freeze something

205 -- hopefully this will free up something for Simplify

207 -> colorScan_spin iterative triv spill graph3

208 ksTriv ksSpill kksCoalesce

210 -- we couldn't find something to freeze either

211 -- time for a spill

213 -> colorScan_spill iterative triv spill graph3

214 ksTriv ksSpill kksCoalesce

216 -- spill time

217 | otherwise

218 = colorScan_spill iterative triv spill graph

219 ksTriv ksSpill kksCoalesce

222 -- Select:

223 -- we couldn't find any triv nodes or things to freeze or coalesce,

224 -- and the graph isn't empty yet.. We'll have to choose a spill

225 -- candidate and leave it uncolored.

226 --

227 colorScan_spill

232 -> Triv k cls color

234 -> Graph k cls color

240 colorScan_spill iterative triv spill graph

241 ksTriv ksSpill kksCoalesce

244 Just graph' = delNode kSpill graph

249 -- | Try to assign a color to all these nodes.

251 assignColors

260 assignColors colors graph ks

269 -- couldn't color this node

272 -- this node colored ok, so do the rest

276 assignColor colors u graph

277 | Just c <- selectColor colors graph u

280 | otherwise

281 = Nothing

285 -- | Select a color for a certain node

286 -- taking into account preferences, neighbors and exclusions.

287 -- returns Nothing if no color can be assigned to this node.

288 --

289 selectColor

297 selectColor colors graph u

299 Just node = lookupNode graph u

301 -- lookup the available colors for the class of this node.

302 colors_avail

305 Just cs -> cs

307 -- find colors we can't use because they're already being used

308 -- by a node that conflicts with this one.

309 Just nsConflicts

312 $ uniqSetToList

313 $ nodeConflicts node

315 colors_conflict = mkUniqSet

319 -- the prefs of our neighbors

320 colors_neighbor_prefs

321 = mkUniqSet

324 -- colors that are still valid for us

326 colors_ok = minusUniqSet colors_ok_ex colors_conflict

328 -- the colors that we prefer, and are still ok

329 colors_ok_pref = intersectUniqSets

332 -- the colors that we could choose while being nice to our neighbors

333 colors_ok_nice = minusUniqSet

334 colors_ok colors_neighbor_prefs

336 -- the best of all possible worlds..

337 colors_ok_pref_nice

338 = intersectUniqSets

339 colors_ok_nice colors_ok_pref

341 -- make the decision

342 chooseColor

344 -- everyone is happy, yay!

348 = Just c

350 -- we've got one of our preferences

354 = Just c

356 -- it wasn't a preference, but it was still ok

359 = Just c

361 -- no colors were available for us this time.

362 -- looks like we're going around the loop again..

363 | otherwise

364 = Nothing

366 in chooseColor