To protect your data, the CISO officer has suggested users to enable GitLab 2FA as soon as possible.

coloring.rs 22.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
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
5
6
use compiler::machine_code::CompiledFunction;
use vm::VM;
7

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

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

14
15
16
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

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

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

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

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

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

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

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

            ig: ig,
qinsoon's avatar
qinsoon committed
65

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

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

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

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

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

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

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

        // 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
362
363
364
            info!("a move instruction of two temporaries of different reigsters group");
            info!("from: {:?}, to: {:?}", m.from, m.to);

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

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

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

qinsoon's avatar
qinsoon committed
647
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
648
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
649
650
651
652
653
654
        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
655
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
656
657
658
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
659
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
660
661
662
663

            spilled_mem.insert(*reg_id, mem);
        }

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