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.7% of users enabled 2FA.

coloring.rs 21.6 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
2
3
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
4
5
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
use compiler::backend::reg_alloc::graph_coloring::liveness::{Node, Move};
qinsoon's avatar
qinsoon committed
6
7
use compiler::machine_code::CompiledFunction;
use vm::VM;
8

9
use utils::vec_utils;
10
use utils::LinkedHashSet;
qinsoon's avatar
qinsoon committed
11

qinsoon's avatar
qinsoon committed
12
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
13
14
use std::collections::HashMap;

qinsoon's avatar
qinsoon committed
15
const COALESCING : bool = true;
16

qinsoon's avatar
qinsoon committed
17
18
19
20
21
pub struct GraphColoring<'a> {
    pub func: &'a mut MuFunctionVersion,
    pub cf: &'a mut CompiledFunction,
    pub vm: &'a VM,

22
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
23

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

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

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

57
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
58
59
60
61
62
            func: func,
            cf: cf,
            vm: vm,

            ig: ig,
qinsoon's avatar
qinsoon committed
63

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

    fn display_node(&self, node: Node) -> String {
        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
110
    
111
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
112
        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
113
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
114
        
qinsoon's avatar
qinsoon committed
115
        // precolor for all machine registers
116
        for reg in backend::all_regs().values() {
117
118
119
120
121
            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
122
        // put usable registers as available colors
123
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
124
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
125
126
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
127
128
129
130
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
131
                self.initial.push(node);
132
                let outdegree = self.ig.outdegree_of(node);
133
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
134

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

        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
163
164
165
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
166
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
167
168
169
                }
            }

qinsoon's avatar
qinsoon committed
170
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
171

qinsoon's avatar
qinsoon committed
172
            return GraphColoring::start(self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
173
174
        }

175
        self
qinsoon's avatar
qinsoon committed
176
177
178
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
179
180
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
181
182
183
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
            for m in ig.moves() {
qinsoon's avatar
qinsoon committed
184
                trace!("add to movelist: {:?}", m);
185
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
186
187
                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
188
            }
qinsoon's avatar
qinsoon committed
189
190
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
191
192
193
194
        }
    }
    
    fn make_work_list(&mut self) {
195
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
196
        while !self.initial.is_empty() {
197
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
198
199
200
201
            
            if {
                // condition: degree >= K
                let degree = self.ig.degree_of(node); 
202
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
203
204
205
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
206
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
207
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
208
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
209
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
210
211
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
212
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
213
214
215
216
217
                self.worklist_simplify.insert(node);
            }
        }
    }
    
218
219
220
221
    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
222
223
224
225
    fn is_move_related(&mut self, node: Node) -> bool {
        !self.node_moves(node).is_empty()
    }
    
226
227
    fn node_moves(&mut self, node: Node) -> LinkedHashSet<Move> {
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
228
229
230
231
232
233
234
235
236
237
238
        
        // 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());
        }
        
239
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
240
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
241
        for m in moves.iter() {
242
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
243
244
245
246
247
248
249
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
250
251
252
253
254
255
256
257
258
    // 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
259
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
260
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
261
        }
qinsoon's avatar
qinsoon committed
262
263
264
265
266
    }
    
    // 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
267
    }
268
269
    
    fn simplify(&mut self) {
270
        // remove next element from worklist_simplify, we know its not empty
271
        let node = self.worklist_simplify.pop_front().unwrap();
272
        
qinsoon's avatar
qinsoon committed
273
        trace!("Simplifying {}", self.display_node(node));
274
275
276
        
        self.select_stack.push(node);
        
277
        for m in self.adjacent(node).iter() {
278
            self.decrement_degree(*m);
279
280
281
        }
    }
    
282
283
    fn adjacent(&self, n: Node) -> LinkedHashSet<Node> {
        let mut adj = LinkedHashSet::new();
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
        
        // 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
    }
    
303
    fn degree(&self, n: Node) -> usize {
304
305
306
307
308
309
310
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
    fn decrement_degree(&mut self, n: Node) {
311
312
313
314
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
315
        trace!("decrement degree of {}", self.display_node(n));
316
        
317
        let d = self.degree(n);
318
        debug_assert!(d != 0);
319
320
        self.degree.insert(n, d - 1);
        
321
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
322
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
323
324
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
325
            trace!("enable moves of {:?}", nodes);
326
327
328
329
330
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
331
                trace!("{} is move related, push to freeze list", self.display_node(n));
332
333
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
334
                trace!("{} is not move related, push to simplify list", self.display_node(n));
335
336
337
338
339
                self.worklist_simplify.insert(n);
            }
        }
    }
    
340
341
342
343
344
    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;
345
346
347
348
349
350
351
352
353
                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
354
355
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
356
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
357
        
qinsoon's avatar
qinsoon committed
358
359
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
360
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
        
        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
379
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
380
381
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
382
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
383
384
        
        if u == v {
qinsoon's avatar
qinsoon committed
385
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
386
387
388
389
390
            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
391
392
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
393
394
395
396
397
398
399
400
            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
401
            trace!("precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), coalesce and combine the move");  
qinsoon's avatar
qinsoon committed
402
403
404
405
406
407
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
408
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
409
410
411
412
            self.active_moves.insert(m);
        }
    }
    
413
    pub fn get_alias(&self, node: Node) -> Node {
qinsoon's avatar
qinsoon committed
414
415
416
417
418
419
420
421
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
    fn add_worklist(&mut self, node: Node) {
422
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
423
424
425
426
427
428
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
    fn ok(&self, u: Node, v: Node) -> bool {
429
430
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
431
            if !self.precolored.contains(&t) 
432
              || self.degree(t) < self.n_regs_for_node(t)
qinsoon's avatar
qinsoon committed
433
434
435
436
437
438
439
440
441
442
443
444
445
              || 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);
446
447
448
449
450
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
451
452
        
        let mut k = 0;
453
        for n in nodes.iter() {
454
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
                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());
        }
        
487
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
488
489
490
        nodes.insert(v);
        self.enable_moves(nodes);
        
491
492
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
493
494
495
496
497
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
498
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
            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);
            }
        }
517
518
519
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
520
        // it is not empty (checked before)
521
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
522
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
523
524
525
526
527
528
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
    fn freeze_moves(&mut self, u: Node) {
529
530
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
531
532
533
534
535
536
537
538
539
540
            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()
541
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
542
543
544
545
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
546
547
548
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
549
        trace!("Selecting a node to spill...");
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
        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
578
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
579
        
580
581
582
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
583
584
    }
    
585
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
586
        trace!("---coloring done---");
587
588
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
589
            trace!("Assigning color to {}", self.display_node(n));
590
            
591
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
592
593
594
595
596
597
598
            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
599
            trace!("available colors: {:?}", ok_colors);
600
601
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
602
                trace!("{} is a spilled node", self.display_node(n));
603
604
                self.spilled_nodes.push(n);
            } else {
605
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
606
                trace!("Color {} as {}", self.display_node(n), first_available_color);
607
608
                
                if !backend::is_callee_saved(first_available_color) {
609
                    warn!("Use caller saved register {}", first_available_color);
610
611
                }
                
612
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
613
                self.ig.color_node(n, first_available_color);
614
615
616
            }
        }
        
qinsoon's avatar
qinsoon committed
617
        for n in self.colored_nodes.iter() {
618
619
620
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
621
            
qinsoon's avatar
qinsoon committed
622
623
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
624
625
626
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
627

qinsoon's avatar
qinsoon committed
628
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
629
630
631
632
633
634
        let spills = self.spills();

        let mut spilled_mem = HashMap::new();

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
635
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
636
637
638
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
639
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
640
641
642
643

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
644
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
645
    }
646
647
648
649
650
651
652
653
654
655
656
657
    
    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
658
    }
659
}