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))
    }
604
}