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.8 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};
6
use compiler::backend::reg_alloc::RegAllocFailure;
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;
qinsoon's avatar
qinsoon committed
12

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

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

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

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

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

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

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

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

            ig: ig,
qinsoon's avatar
qinsoon committed
64

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

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

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

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

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

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

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

        Ok(())
629
    }
qinsoon's avatar
qinsoon committed
630

qinsoon's avatar
qinsoon committed
631
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
632
633
634
635
636
637
        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
638
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
639
640
641
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
642
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
643
644
645
646

            spilled_mem.insert(*reg_id, mem);
        }

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