WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

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

coloring.rs 23 KB
Newer Older
1 2
extern crate hprof;

qinsoon's avatar
qinsoon committed
3 4 5
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
6
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
7 8
use compiler::machine_code::CompiledFunction;
use vm::VM;
9

10
use utils::vec_utils;
11
use utils::LinkedHashSet;
12
use utils::LinkedHashMap;
qinsoon's avatar
qinsoon committed
13

qinsoon's avatar
qinsoon committed
14
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
15

16 17 18
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

qinsoon's avatar
qinsoon committed
19
const COALESCING : bool = true;
20

qinsoon's avatar
qinsoon committed
21 22 23 24 25
pub struct GraphColoring<'a> {
    pub func: &'a mut MuFunctionVersion,
    pub cf: &'a mut CompiledFunction,
    pub vm: &'a VM,

26
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
27

28
    precolored: LinkedHashSet<NodeIndex>,
29
    colors: LinkedHashMap<backend::RegGroup, LinkedHashSet<MuID>>,
30
    pub colored_nodes: Vec<NodeIndex>,
qinsoon's avatar
qinsoon committed
31
    
32
    initial: Vec<NodeIndex>,
33
    degree: LinkedHashMap<NodeIndex, usize>,
qinsoon's avatar
qinsoon committed
34
    
35
    worklist_moves: Vec<Move>,
36
    movelist: LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>,
37
    active_moves: LinkedHashSet<Move>,
38
    coalesced_nodes: LinkedHashSet<NodeIndex>,
39 40
    coalesced_moves: LinkedHashSet<Move>,
    constrained_moves: LinkedHashSet<Move>,
41
    alias: LinkedHashMap<NodeIndex, NodeIndex>,
qinsoon's avatar
qinsoon committed
42
    
43
    worklist_spill: Vec<NodeIndex>,
44
    spillable: LinkedHashMap<MuID, bool>,
45
    spilled_nodes: Vec<NodeIndex>,
46
    
47
    worklist_freeze: LinkedHashSet<NodeIndex>,
48
    frozen_moves: LinkedHashSet<Move>,
49
    
50 51
    worklist_simplify: LinkedHashSet<NodeIndex>,
    select_stack: Vec<NodeIndex>
qinsoon's avatar
qinsoon committed
52 53
}

qinsoon's avatar
qinsoon committed
54
impl <'a> GraphColoring<'a> {
55
    pub fn start (func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
56
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
57 58
        cf.mc().trace_mc();

qinsoon's avatar
qinsoon committed
59 60
        let ig = graph_coloring::build_inteference_graph(cf, func);

61
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
62 63 64 65 66
            func: func,
            cf: cf,
            vm: vm,

            ig: ig,
qinsoon's avatar
qinsoon committed
67

68
            precolored: LinkedHashSet::new(),
69
            colors: {
70
                let mut map = LinkedHashMap::new();
71 72
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
73 74 75
                map
            },
            colored_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
76
            
77
            initial: Vec::new(),
78
            degree: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
79
            
80
            worklist_moves: Vec::new(),
81
            movelist: LinkedHashMap::new(),
82 83 84 85
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
86
            alias: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
87
            
88
            worklist_spill: Vec::new(),
89
            spillable: LinkedHashMap::new(),
90 91
            spilled_nodes: Vec::new(),
            
92 93
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
94
            
95
            worklist_simplify: LinkedHashSet::new(),
96
            select_stack: Vec::new()
qinsoon's avatar
qinsoon committed
97 98
        };
        
qinsoon's avatar
qinsoon committed
99
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
100
    }
qinsoon's avatar
qinsoon committed
101

102
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
103 104 105 106 107 108 109 110 111 112 113
        let id = self.ig.get_temp_of(node);
        self.display_id(id)
    }

    fn display_id(&self, id: MuID) -> String {
        self.func.context.get_temp_display(id)
    }

    fn display_move(&self, m: Move) -> String {
        format!("Move: {} -> {}", self.display_node(m.from), self.display_node(m.to))
    }
qinsoon's avatar
qinsoon committed
114
    
115
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
116
        trace!("---InterenceGraph---");
117 118
        let _p = hprof::enter("regalloc: graph coloring");

qinsoon's avatar
qinsoon committed
119
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
120
        
qinsoon's avatar
qinsoon committed
121
        // precolor for all machine registers
122
        for reg in backend::all_regs().values() {
123 124 125 126 127
            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
128
        // put usable registers as available colors
129
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
130
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
131 132
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
133 134 135 136
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
137
                self.initial.push(node);
138
                let outdegree = self.ig.outdegree_of(node);
139
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
140

qinsoon's avatar
qinsoon committed
141
                trace!("{} has a degree of {}", self.display_node(node), outdegree);
qinsoon's avatar
qinsoon committed
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
            }
        }
        
        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())
        } {}
        
qinsoon's avatar
qinsoon committed
165 166
        self.assign_colors();

167 168
        drop(_p);

qinsoon's avatar
qinsoon committed
169 170
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
171 172 173
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
174
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
175 176 177
                }
            }

qinsoon's avatar
qinsoon committed
178
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
179

qinsoon's avatar
qinsoon committed
180
            return GraphColoring::start(self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
181 182
        }

183
        self
qinsoon's avatar
qinsoon committed
184 185 186
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
187 188
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
189 190
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
191
            for m in ig.moves().iter() {
qinsoon's avatar
qinsoon committed
192
                trace!("add to movelist: {:?}", m);
193
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
194 195
                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
196
            }
qinsoon's avatar
qinsoon committed
197 198
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
199 200 201 202
        }
    }
    
    fn make_work_list(&mut self) {
203
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
204
        while !self.initial.is_empty() {
205
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
206 207 208 209
            
            if {
                // condition: degree >= K
                let degree = self.ig.degree_of(node); 
210
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
211 212 213
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
214
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
215
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
216
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
217
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
218 219
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
220
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
221 222 223 224 225
                self.worklist_simplify.insert(node);
            }
        }
    }
    
226
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
227 228 229
        backend::number_of_regs_in_group(self.ig.get_group_of(node))
    }
    
230
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
231 232 233
        !self.node_moves(node).is_empty()
    }
    
234
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
235
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
236 237 238 239 240 241 242 243 244 245 246
        
        // 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());
        }
        
247
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
248
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
249
        for m in moves.iter() {
250
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
251 252 253 254 255 256 257
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
258 259 260
    // 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)
261
    fn movelist_mut(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
262 263 264 265
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
266
    fn movelist_check(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
qinsoon's avatar
qinsoon committed
267
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
268
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
269
        }
qinsoon's avatar
qinsoon committed
270 271 272
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
273
    unsafe fn movelist_nocheck(list: &LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
274
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
275
    }
276 277
    
    fn simplify(&mut self) {
278
        // remove next element from worklist_simplify, we know its not empty
279
        let node = self.worklist_simplify.pop_front().unwrap();
280
        
qinsoon's avatar
qinsoon committed
281
        trace!("Simplifying {}", self.display_node(node));
282 283 284
        
        self.select_stack.push(node);
        
285
        for m in self.adjacent(node).iter() {
286
            self.decrement_degree(*m);
287 288 289
        }
    }
    
290
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
291
        let mut adj = LinkedHashSet::new();
292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
        
        // 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
    }
    
311
    fn degree(&self, n: NodeIndex) -> usize {
312 313 314 315 316 317
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
318
    fn decrement_degree(&mut self, n: NodeIndex) {
319 320 321 322
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
323
        trace!("decrement degree of {}", self.display_node(n));
324
        
325
        let d = self.degree(n);
326
        debug_assert!(d != 0);
327 328
        self.degree.insert(n, d - 1);
        
329
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
330
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
331 332
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
333
            trace!("enable moves of {:?}", nodes);
334 335 336 337 338
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
339
                trace!("{} is move related, push to freeze list", self.display_node(n));
340 341
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
342
                trace!("{} is not move related, push to simplify list", self.display_node(n));
343 344 345 346 347
                self.worklist_simplify.insert(n);
            }
        }
    }
    
348
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
349 350 351 352
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
353 354 355 356 357 358 359 360 361
                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
362 363
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
364
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
365 366 367

        // if they are not from the same register group, we cannot coalesce them
        if self.ig.get_group_of(m.from) != self.ig.get_group_of(m.to) {
qinsoon's avatar
qinsoon committed
368 369 370
            info!("a move instruction of two temporaries of different reigsters group");
            info!("from: {:?}, to: {:?}", m.from, m.to);

qinsoon's avatar
qinsoon committed
371 372
            return;
        }
qinsoon's avatar
qinsoon committed
373
        
qinsoon's avatar
qinsoon committed
374 375
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
376
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
        
        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
395
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
396 397
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
398
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
399 400
        
        if u == v {
qinsoon's avatar
qinsoon committed
401
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
402 403 404 405 406
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
407 408
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
qinsoon's avatar
qinsoon committed
409 410
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
411 412 413 414 415 416 417 418
            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
419 420 421 422
            trace!("ok(u, v) = {}", self.ok(u, v));
            trace!("conservative(u, v) = {}", self.conservative(u, v));

            trace!("precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), coalesce and combine the move");
qinsoon's avatar
qinsoon committed
423 424 425 426 427 428
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
429
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
430 431 432 433
            self.active_moves.insert(m);
        }
    }
    
434
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
435 436 437 438 439 440 441
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
442
    fn add_worklist(&mut self, node: NodeIndex) {
443
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
444 445 446 447 448
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
449
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
450 451
        for t in self.adjacent(v).iter() {
            let t = *t;
452 453 454
            if !(self.degree(t) < self.n_regs_for_node(t)
                || self.precolored.contains(&t)
                || self.ig.is_adj(t, u)) {
qinsoon's avatar
qinsoon committed
455
                return false;
456
            }
qinsoon's avatar
qinsoon committed
457 458 459 460 461
        }
        
        true
    }
    
462
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
463 464
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
465 466 467 468 469
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
470 471
        
        let mut k = 0;
472
        for n in nodes.iter() {
qinsoon's avatar
qinsoon committed
473
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
474 475 476 477
                k += 1;
            }
        }
        
qinsoon's avatar
qinsoon committed
478
        k < self.n_regs_for_node(u) && k < self.n_regs_for_node(v)
qinsoon's avatar
qinsoon committed
479 480
    }
    
481
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505
        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());
        }
        
506
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
507 508 509
        nodes.insert(v);
        self.enable_moves(nodes);
        
510 511
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
512 513 514 515 516
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
517
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
518 519 520 521 522
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
523
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
524 525 526 527 528 529 530 531 532 533 534 535
        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);
            }
        }
536 537 538
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
539
        // it is not empty (checked before)
540
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
541
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
542 543 544 545 546
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
547
    fn freeze_moves(&mut self, u: NodeIndex) {
548 549
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
550 551 552 553 554 555 556 557 558 559
            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()
560
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
561 562 563 564
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
565 566 567
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
568
        trace!("Selecting a node to spill...");
569
        let mut m : Option<NodeIndex> = None;
570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596
        
        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
597
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
598
        
599 600 601
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
602 603
    }
    
604
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
605
        trace!("---coloring done---");
606 607
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
608
            trace!("Assigning color to {}", self.display_node(n));
609
            
610
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
qinsoon's avatar
qinsoon committed
611 612 613

            trace!("all the colors for this temp: {:?}", ok_colors);

614
            for w in self.ig.outedges_of(n) {
qinsoon's avatar
qinsoon committed
615 616
                let w_alias = self.get_alias(w);
                match self.ig.get_color_of(w_alias) {
617
                    None => {}, // do nothing
qinsoon's avatar
qinsoon committed
618 619 620 621
                    Some(color) => {
                        trace!("color {} is used for its neighbor {:?} (aliasing to {:?})", color, self.display_node(w), self.display_node(w_alias));
                        ok_colors.remove(&color);
                    }
622 623
                }
            }
qinsoon's avatar
qinsoon committed
624
            trace!("available colors: {:?}", ok_colors);
625 626
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
627
                trace!("{} is a spilled node", self.display_node(n));
628 629
                self.spilled_nodes.push(n);
            } else {
630
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
631
                trace!("Color {} as {}", self.display_node(n), first_available_color);
632 633
                
                if !backend::is_callee_saved(first_available_color) {
634
                    warn!("Use caller saved register {}", first_available_color);
635 636
                }
                
637
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
638
                self.ig.color_node(n, first_available_color);
639 640 641
            }
        }
        
qinsoon's avatar
qinsoon committed
642
        for n in self.colored_nodes.iter() {
643 644 645
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
646
            
qinsoon's avatar
qinsoon committed
647 648
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
649 650 651
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
652

qinsoon's avatar
qinsoon committed
653
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
654
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
655 656
        let spills = self.spills();

657
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
658 659 660

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
661
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
662 663 664
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
665
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
666 667 668 669

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
670
        // though we are not using this right now
qinsoon's avatar
qinsoon committed
671
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
672
    }
673 674 675 676 677 678 679 680 681 682 683 684
    
    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
685
    }
686
}