To protect your data, the CISO officer has suggested users to enable GitLab 2FA as soon as possible.

coloring.rs 19.9 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

qinsoon's avatar
qinsoon committed
5
use compiler::backend;
6
use utils::vec_utils;
7
use utils::LinkedHashSet;
qinsoon's avatar
qinsoon committed
8

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

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

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

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