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 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
}