To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.7% of users enabled 2FA.

coloring.rs 20.1 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
use ast::ir::MuID;
2
3
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
use compiler::backend::reg_alloc::graph_coloring::liveness::{Node, Move};
qinsoon's avatar
qinsoon committed
4
use compiler::backend;
5
6
use compiler::backend::reg_alloc::RegAllocFailure;

7
use utils::vec_utils;
8
use utils::LinkedHashSet;
qinsoon's avatar
qinsoon committed
9

qinsoon's avatar
qinsoon committed
10
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
11
12
use std::collections::HashMap;

qinsoon's avatar
qinsoon committed
13
const COALESCING : bool = true;
14

15
16
pub struct GraphColoring {
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
17
    
18
19
    precolored: LinkedHashSet<Node>,
    colors: HashMap<backend::RegGroup, LinkedHashSet<MuID>>,
20
    pub colored_nodes: Vec<Node>,
qinsoon's avatar
qinsoon committed
21
    
22
    initial: Vec<Node>,
23
    degree: HashMap<Node, usize>,
qinsoon's avatar
qinsoon committed
24
    
25
    worklist_moves: Vec<Move>,
qinsoon's avatar
qinsoon committed
26
    movelist: HashMap<Node, RefCell<Vec<Move>>>,
27
28
29
30
    active_moves: LinkedHashSet<Move>,
    coalesced_nodes: LinkedHashSet<Node>,
    coalesced_moves: LinkedHashSet<Move>,
    constrained_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
31
    alias: HashMap<Node, Node>,
qinsoon's avatar
qinsoon committed
32
    
33
    worklist_spill: Vec<Node>,
34
35
36
    spillable: HashMap<MuID, bool>,
    spilled_nodes: Vec<Node>,
    
37
38
    worklist_freeze: LinkedHashSet<Node>,
    frozen_moves: LinkedHashSet<Move>,
39
    
40
    worklist_simplify: LinkedHashSet<Node>,
41
    select_stack: Vec<Node>
qinsoon's avatar
qinsoon committed
42
43
}

44
impl GraphColoring {
45
    pub fn start (ig: InterferenceGraph) -> Result<GraphColoring, RegAllocFailure> {
qinsoon's avatar
qinsoon committed
46
47
        let mut coloring = GraphColoring {
            ig: ig,
qinsoon's avatar
qinsoon committed
48
            
49
            precolored: LinkedHashSet::new(),
50
51
            colors: {
                let mut map = HashMap::new();
52
53
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
54
55
56
                map
            },
            colored_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
57
            
58
            initial: Vec::new(),
qinsoon's avatar
qinsoon committed
59
60
            degree: HashMap::new(),
            
61
            worklist_moves: Vec::new(),
qinsoon's avatar
qinsoon committed
62
            movelist: HashMap::new(),
63
64
65
66
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
67
            alias: HashMap::new(),
qinsoon's avatar
qinsoon committed
68
            
69
            worklist_spill: Vec::new(),
70
71
72
            spillable: HashMap::new(),
            spilled_nodes: Vec::new(),
            
73
74
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
75
            
76
            worklist_simplify: LinkedHashSet::new(),
77
            select_stack: Vec::new()
qinsoon's avatar
qinsoon committed
78
79
        };
        
80
81
82
83
        match coloring.init() {
            Ok(_) => Ok(coloring),
            Err(fail) => Err(fail)
        }
qinsoon's avatar
qinsoon committed
84
85
    }
    
86
    fn init (&mut self) -> Result<(), RegAllocFailure> {
87
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
88
        
qinsoon's avatar
qinsoon committed
89
        // precolor for all machine registers
90
        for reg in backend::all_regs().values() {
91
92
93
94
95
            let reg_id = reg.extract_ssa_id().unwrap();
            let node = self.ig.get_node(reg_id);
            self.precolored.insert(node);
        }
        
qinsoon's avatar
qinsoon committed
96
        // put usable registers as available colors
97
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
98
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
99
100
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
101
102
103
104
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
105
                self.initial.push(node);
106
                let outdegree = self.ig.outdegree_of(node);
107
108
                self.degree.insert(node, outdegree);
                trace!("{} has a degree of {}", self.node_info(node), outdegree);
qinsoon's avatar
qinsoon committed
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
            }
        }
        
        self.build();
        self.make_work_list();
        
        while {
            if !self.worklist_simplify.is_empty() {
                self.simplify();
            } else if !self.worklist_moves.is_empty() {
                self.coalesce();
            } else if !self.worklist_freeze.is_empty() {
                self.freeze();
            } else if !self.worklist_spill.is_empty() {
                self.select_spill();
            }
            
            ! (self.worklist_simplify.is_empty()
            && self.worklist_moves.is_empty()
            && self.worklist_freeze.is_empty()
            && self.worklist_spill.is_empty())
        } {}
        
132
        self.assign_colors()
qinsoon's avatar
qinsoon committed
133
134
135
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
136
137
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
138
139
140
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
            for m in ig.moves() {
qinsoon's avatar
qinsoon committed
141
                trace!("add {:?} to movelist", m);
142
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
143
144
                GraphColoring::movelist_mut(movelist, m.from).borrow_mut().push(m.clone());
                GraphColoring::movelist_mut(movelist, m.to).borrow_mut().push(m.clone());
qinsoon's avatar
qinsoon committed
145
            }
qinsoon's avatar
qinsoon committed
146
147
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
148
149
150
151
        }
    }
    
    fn make_work_list(&mut self) {
152
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
153
        while !self.initial.is_empty() {
154
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
155
156
157
158
            
            if {
                // condition: degree >= K
                let degree = self.ig.degree_of(node); 
159
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
160
161
162
                
                degree >= n_regs
            } {
163
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.node_info(node));
164
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
165
            } else if self.is_move_related(node) {
166
                trace!("{} is move related, push to freeze list", self.node_info(node));
qinsoon's avatar
qinsoon committed
167
168
                self.worklist_freeze.insert(node);
            } else {
169
                trace!("{} has small degree and not move related, push to simplify list", self.node_info(node));
qinsoon's avatar
qinsoon committed
170
171
172
173
174
                self.worklist_simplify.insert(node);
            }
        }
    }
    
175
176
177
178
    fn n_regs_for_node(&self, node: Node) -> usize {
        backend::number_of_regs_in_group(self.ig.get_group_of(node))
    }
    
qinsoon's avatar
qinsoon committed
179
180
181
182
    fn is_move_related(&mut self, node: Node) -> bool {
        !self.node_moves(node).is_empty()
    }
    
183
184
    fn node_moves(&mut self, node: Node) -> LinkedHashSet<Move> {
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
185
186
187
188
189
190
191
192
193
194
195
        
        // addAll(active_moves)
        for m in self.active_moves.iter() {
            moves.insert(m.clone());
        }
        
        // addAll(worklist_moves)
        for m in self.worklist_moves.iter() {
            moves.insert(m.clone());
        }
        
196
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
197
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
198
        for m in moves.iter() {
199
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
200
201
202
203
204
205
206
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
207
208
209
210
211
212
213
214
215
    // avoid using &mut self as argument
    // in build(), we will need to mutate on self.movelist while
    // holding an immmutable reference of self(self.ig)
    fn movelist_mut(list: &mut HashMap<Node, RefCell<Vec<Move>>>, node: Node) -> &RefCell<Vec<Move>> {
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
    fn movelist_check(list: &mut HashMap<Node, RefCell<Vec<Move>>>, node: Node) {
qinsoon's avatar
qinsoon committed
216
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
217
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
218
        }
qinsoon's avatar
qinsoon committed
219
220
221
222
223
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
    unsafe fn movelist_nocheck(list: &HashMap<Node, RefCell<Vec<Move>>>, node: Node) -> &RefCell<Vec<Move>> {
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
224
    }
225
226
    
    fn simplify(&mut self) {
227
        // remove next element from worklist_simplify, we know its not empty
228
        let node = self.worklist_simplify.pop_front().unwrap();
229
230
        
        trace!("Simplifying {}", self.node_info(node));
231
232
233
        
        self.select_stack.push(node);
        
234
        for m in self.adjacent(node).iter() {
235
            self.decrement_degree(*m);
236
237
238
        }
    }
    
239
240
    fn adjacent(&self, n: Node) -> LinkedHashSet<Node> {
        let mut adj = LinkedHashSet::new();
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
        
        // add n's successors
        for s in self.ig.outedges_of(n) {
            adj.insert(s);
        }
        
        // removeAll(select_stack)
        for s in self.select_stack.iter() {
            adj.remove(s);
        }
        
        // removeAll(coalesced_nodes)
        for s in self.coalesced_nodes.iter() {
            adj.remove(s);
        }
        
        adj
    }
    
260
    fn degree(&self, n: Node) -> usize {
261
262
263
264
265
266
267
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
    fn decrement_degree(&mut self, n: Node) {
268
269
270
271
272
273
        if self.precolored.contains(&n) {
            return;
        }
        
        trace!("decrement degree of {}", self.node_info(n));        
        
274
        let d = self.degree(n);
275
        debug_assert!(d != 0);
276
277
        self.degree.insert(n, d - 1);
        
278
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
279
            trace!("{}'s degree is K, no longer need to spill it", self.node_info(n));
280
281
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
282
            trace!("enable moves of {:?}", nodes);
283
284
285
286
287
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
288
                trace!("{} is move related, push to freeze list", self.node_info(n));
289
290
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
291
                trace!("{} is not move related, push to simplify list", self.node_info(n));
292
293
294
295
296
                self.worklist_simplify.insert(n);
            }
        }
    }
    
297
298
299
300
301
    fn enable_moves(&mut self, nodes: LinkedHashSet<Node>) {
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
302
303
304
305
306
307
308
309
310
                if self.active_moves.contains(&mov) {
                    self.active_moves.insert(mov);
                    self.worklist_moves.push(mov);
                }
            }
        }
    }
    
    fn coalesce(&mut self) {
qinsoon's avatar
qinsoon committed
311
312
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
313
314
        trace!("Coalescing on {}", self.move_info(m));
        
qinsoon's avatar
qinsoon committed
315
316
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
317
        trace!("resolve alias: from {} to {}", self.node_info(x), self.node_info(y));
qinsoon's avatar
qinsoon committed
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
        
        let (u, v, precolored_u, precolored_v) = {
            if self.precolored.contains(&y) {
                let u = y;
                let v = x;
                let precolored_u = true;
                let precolored_v = self.precolored.contains(&v);
                
                (u, v, precolored_u, precolored_v)
            } else {
                let u = x;
                let v = y;
                let precolored_u = self.precolored.contains(&u);
                let precolored_v = self.precolored.contains(&v);
                
                (u, v, precolored_u, precolored_v)
            }
        };
qinsoon's avatar
qinsoon committed
336
337
338
339
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
            self.node_info(u),
            self.node_info(v),
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
340
341
        
        if u == v {
qinsoon's avatar
qinsoon committed
342
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
343
344
345
346
347
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
qinsoon's avatar
qinsoon committed
348
349
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
350
351
352
353
354
355
356
357
            if !precolored_u {
                self.add_worklist(u);
            }
            if !precolored_v {
                self.add_worklist(v);
            }
        } else if (precolored_u && self.ok(u, v)) 
          || (!precolored_u && self.conservative(u, v)) {
qinsoon's avatar
qinsoon committed
358
            trace!("precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), coalesce and combine the move");  
qinsoon's avatar
qinsoon committed
359
360
361
362
363
364
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
365
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
366
367
368
369
            self.active_moves.insert(m);
        }
    }
    
370
    pub fn get_alias(&self, node: Node) -> Node {
qinsoon's avatar
qinsoon committed
371
372
373
374
375
376
377
378
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
    fn add_worklist(&mut self, node: Node) {
379
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
380
381
382
383
384
385
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
    fn ok(&self, u: Node, v: Node) -> bool {
386
387
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
388
            if !self.precolored.contains(&t) 
389
              || self.degree(t) < self.n_regs_for_node(t)
qinsoon's avatar
qinsoon committed
390
391
392
393
394
395
396
397
398
399
400
401
402
              || self.ig.is_adj(t, u) {
                return false;
            } 
        }
        
        true
    }
    
    fn conservative(&self, u: Node, v: Node) -> bool {
        debug_assert!(self.ig.get_group_of(u) == self.ig.get_group_of(v));
        
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
403
404
405
406
407
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
408
409
        
        let mut k = 0;
410
        for n in nodes.iter() {
411
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
                k += 1;
            }
        }
        
        k < self.n_regs_for_node(u)
    }
    
    fn combine(&mut self, u: Node, v: Node) {
        if self.worklist_freeze.contains(&v) {
            self.worklist_freeze.remove(&v);
            self.coalesced_nodes.insert(v);
        } else {
            vec_utils::remove_value(&mut self.worklist_spill, v);
            self.coalesced_nodes.insert(v);
        }
        
        self.alias.insert(v, u); 
        
        {
            let ref mut movelist = self.movelist;
            GraphColoring::movelist_check(movelist, u);
            GraphColoring::movelist_check(movelist, v);
            // we checked before getting the movelist, its safe
            // use nocheck version which requires only immutable references of movelist
            // avoid maintaining a mutable reference of movelist alive
            let movelist_u = &mut unsafe {GraphColoring::movelist_nocheck(movelist, u)}.borrow_mut();
            let movelist_v = &mut unsafe {GraphColoring::movelist_nocheck(movelist, v)}.borrow_mut();
            
            // addAll()
            movelist_u.extend_from_slice(movelist_v.as_slice());
        }
        
444
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
445
446
447
        nodes.insert(v);
        self.enable_moves(nodes);
        
448
449
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
450
451
452
453
454
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
455
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
    fn add_edge(&mut self, u: Node, v: Node) {
        if u != v && !self.ig.is_adj(u, v) {
            if !self.precolored.contains(&u) {
                self.ig.add_interference_edge(u, v);
                let degree_u = self.degree(u);
                self.degree.insert(u, degree_u + 1);
            }
            if !self.precolored.contains(&v) {
                self.ig.add_interference_edge(v, u);
                let degree_v = self.degree(v);
                self.degree.insert(v, degree_v + 1);
            }
        }
474
475
476
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
477
        // it is not empty (checked before)
478
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
479
        trace!("Freezing {}...", self.node_info(node));
qinsoon's avatar
qinsoon committed
480
481
482
483
484
485
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
    fn freeze_moves(&mut self, u: Node) {
486
487
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
488
489
490
491
492
493
494
495
496
497
            let mut v = self.get_alias(m.from);
            if v == self.get_alias(u) {
                v = self.get_alias(m.to);
            }
            
            self.active_moves.remove(&m);
            self.frozen_moves.insert(m);
            
            if !self.precolored.contains(&v) 
               && self.node_moves(v).is_empty()
498
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
499
500
501
502
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
503
504
505
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
506
        trace!("Selecting a node to spill...");
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
        let mut m : Option<Node> = None;
        
        for n in self.worklist_spill.iter() {
            let n = *n;
            if m.is_none() {
                m = Some(n);
            } else if {
                // m is not none
                let temp = self.ig.get_temp_of(m.unwrap());
                let spillable = {match self.spillable.get(&temp) {
                    None => {
                        //by default, its spillable
                        true
                    },
                    Some(b) => *b
                }};
                
                !spillable
            } {
                m = Some(n);
            } else if (self.ig.get_spill_cost(n) / (self.degree(n) as f32)) 
              < (self.ig.get_spill_cost(m.unwrap()) / (self.degree(m.unwrap()) as f32)) {
                m = Some(n);
            }
        }
        
        // m is not none
        let m = m.unwrap();
qinsoon's avatar
qinsoon committed
535
536
        trace!("Spilling {}...", self.node_info(m));
        
537
538
539
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
540
541
    }
    
542
    fn assign_colors(&mut self) -> Result<(), RegAllocFailure> {
qinsoon's avatar
qinsoon committed
543
        trace!("---coloring done---");
544
545
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
546
            trace!("Assigning color to {}", self.node_info(n));
547
            
548
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
549
550
551
552
553
554
555
            for w in self.ig.outedges_of(n) {
                let w = self.get_alias(w);
                match self.ig.get_color_of(w) {
                    None => {}, // do nothing
                    Some(color) => {ok_colors.remove(&color);}
                }
            }
qinsoon's avatar
qinsoon committed
556
            trace!("available colors: {:?}", ok_colors);
557
558
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
559
                trace!("{} is a spilled node", self.node_info(n));
560
561
                self.spilled_nodes.push(n);
            } else {
562
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
563
                trace!("Color {} as {}", self.node_info(n), first_available_color);
564
565
                
                if !backend::is_callee_saved(first_available_color) {
566
                    warn!("Use caller saved register {}", first_available_color);
567
568
                }
                
569
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
570
                self.ig.color_node(n, first_available_color);
571
572
573
574
575
576
577
            }
        }
        
        for n in self.coalesced_nodes.iter() {
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
578
579
580
            
            trace!("Assign color to {} based on aliased {}", self.node_info(n), self.node_info(alias));
            trace!("Color {} as {}", self.node_info(n), alias_color);
581
582
            self.ig.color_node(n, alias_color);
        }
583
584

        Ok(())
585
586
587
588
589
590
591
592
593
594
595
596
597
    }
    
    pub fn spills(&self) -> Vec<MuID> {
        let mut spills = vec![];
        
        let spill_count = self.spilled_nodes.len();
        if spill_count > 0 {
            for n in self.spilled_nodes.iter() {
                spills.push(self.ig.get_temp_of(*n));
            }
        }
        
        spills
598
    }
qinsoon's avatar
qinsoon committed
599
600
601
602
603
604
605
606
607
    
    fn node_info(&self, node: Node) -> String {
        let reg = self.ig.get_temp_of(node);
        format!("{:?}/Reg {}", node, reg)
    }
    
    fn move_info(&self, m: Move) -> String {
        format!("Move: {} -> {}", self.node_info(m.from), self.node_info(m.to))
    }
608
}