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 22.5 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> {
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);

qinsoon's avatar
qinsoon committed
57
        let mut 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
97
    }
    
qinsoon's avatar
qinsoon committed
98
    fn regalloc(mut self) -> Result<GraphColoring<'a>, RegAllocFailure> {
99
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
100
101

        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
102
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
103
        
qinsoon's avatar
qinsoon committed
104
        // precolor for all machine registers
105
        for reg in backend::all_regs().values() {
106
107
108
109
110
            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
111
        // put usable registers as available colors
112
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
113
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
114
115
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
116
117
118
119
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
120
                self.initial.push(node);
121
                let outdegree = self.ig.outdegree_of(node);
122
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
123
124
125
126
127

                trace!("{} has a degree of {}", {
                    let id = self.ig.get_temp_of(node);
                    self.func.context.get_temp_display(id)
                }, outdegree);
qinsoon's avatar
qinsoon committed
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
            }
        }
        
        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
151
152
153
154
        self.assign_colors();

        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
155
156
157
158
159
160
161
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
                    trace!("{:?}: {:?}", node, self.ig.get_temp_of(*node));
                }
            }

qinsoon's avatar
qinsoon committed
162
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
163

qinsoon's avatar
qinsoon committed
164
            return GraphColoring::start(self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
165
166
        }

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

        Ok(())
620
    }
qinsoon's avatar
qinsoon committed
621

qinsoon's avatar
qinsoon committed
622
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
623
624
625
626
627
628
        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
629
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
630
631
632
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
633
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
634
635
636
637

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
638
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
//
//        self.spilled_nodes.clear();
//
//        self.initial = {
//            let mut ret = vec![];
//
//            for node in self.colored_nodes.iter() {
//                vec_utils::add_unique(&mut ret, node.clone());
//            }
//            for node in self.coalesced_nodes.iter() {
//                vec_utils::add_unique(&mut ret, node.clone());
//            }
//
//            // create nodes for every new temp
//            for tmp in new_temps {
//                let node = self.ig.new_node(tmp.id(), &func.context);
//                vec_utils::add_unique(&mut ret, node.clone());
//            }
//
//            ret
//        };
//
//        self.colored_nodes.clear();
//        self.coalesced_nodes.clear();
    }
664
665
666
667
668
669
670
671
672
673
674
675
    
    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
676
    }
qinsoon's avatar
qinsoon committed
677
678
679
680
681
682
683
684
685
    
    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))
    }
686
}