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.

liveness.rs 15.4 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
2
extern crate nalgebra;

qinsoon's avatar
qinsoon committed
3
4
use vm::CompiledFunction;
use vm::MachineCode;
5
use ast::ir::*;
qinsoon's avatar
qinsoon committed
6
7
use ast::types;
use compiler::backend;
8
use utils::vec_utils;
9
use utils::LinkedHashSet;
10
11

use std::collections::LinkedList;
qinsoon's avatar
qinsoon committed
12
13
14
15
use std::collections::{HashMap, HashSet};

use self::nalgebra::DMatrix;

16
17
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Node(usize);
18
#[derive(Clone, Debug, PartialEq)]
qinsoon's avatar
qinsoon committed
19
20
pub struct NodeProperty {
    color: Option<MuID>,
21
22
23
    group: backend::RegGroup,
    temp: MuID,
    spill_cost: f32
qinsoon's avatar
qinsoon committed
24
25
26
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Move{pub from: Node, pub to: Node}
27
28

pub struct InterferenceGraph {
qinsoon's avatar
qinsoon committed
29
    nodes: HashMap<MuID, Node>,
qinsoon's avatar
qinsoon committed
30
    nodes_property: HashMap<Node, NodeProperty>,
qinsoon's avatar
qinsoon committed
31
32
33
    
    matrix: Option<DMatrix<bool>>,
    
qinsoon's avatar
qinsoon committed
34
    moves: HashSet<Move>,
35
36
37
38
}

impl InterferenceGraph {
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
39
40
        InterferenceGraph {
            nodes: HashMap::new(),
qinsoon's avatar
qinsoon committed
41
            nodes_property: HashMap::new(),
qinsoon's avatar
qinsoon committed
42
43
44
45
46
            matrix: None,
            moves: HashSet::new()
        }
    }
    
qinsoon's avatar
qinsoon committed
47
48
49
50
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> Node {
        let entry = context.get_value(reg_id).unwrap();
        
        if !self.nodes.contains_key(&reg_id) {
qinsoon's avatar
qinsoon committed
51
            let index = self.nodes.len();
52
            let node = Node(index);
qinsoon's avatar
qinsoon committed
53
54
55
56
57
58
59
60
61
62
            
            // add the node
            self.nodes.insert(reg_id, node.clone());
            
            // add node property
            let group = {
                let ref ty = entry.ty;
                if types::is_scalar(ty) {
                    if types::is_fp(ty) {
                        backend::RegGroup::FPR
qinsoon's avatar
qinsoon committed
63
64
                    } else {
                        backend::RegGroup::GPR
qinsoon's avatar
qinsoon committed
65
66
67
68
69
70
71
                    }
                } else {
                    unimplemented!()
                }
            };
            let property = NodeProperty {
                color: None,
72
73
74
                group: group,
                temp: reg_id,
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
75
76
            };
            self.nodes_property.insert(node, property);
77
78
79
80
81
82
83
84
85
86
        } 
        
        
        let node = * self.nodes.get(&reg_id).unwrap();
        
        // increase node spill cost
        let property = self.nodes_property.get_mut(&node).unwrap();
        property.spill_cost += 1.0f32;
        
        node
qinsoon's avatar
qinsoon committed
87
88
    }
    
qinsoon's avatar
qinsoon committed
89
    pub fn get_node(&self, reg: MuID) -> Node {
qinsoon's avatar
qinsoon committed
90
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
91
            Some(index) => *index,
qinsoon's avatar
qinsoon committed
92
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
93
94
95
        }
    }
    
96
97
98
99
100
101
102
103
    pub fn temps(&self) -> Vec<MuID>{
        let mut ret = vec![];
        for reg in self.nodes.keys() {
            ret.push(*reg);
        }
        ret
    }
    
qinsoon's avatar
qinsoon committed
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
    pub fn nodes(&self) -> Vec<Node> {
        let mut ret = vec![];
        for node in self.nodes.values() {
            ret.push(node.clone());
        }
        ret
    }
    
    pub fn moves(&self) -> &HashSet<Move> {
        &self.moves
    }
    
    pub fn n_nodes(&self) -> usize {
        self.nodes.len()
    }
    
qinsoon's avatar
qinsoon committed
120
121
122
123
124
    fn init_graph(&mut self) {
        let len = self.nodes.len();
        self.matrix = Some(DMatrix::from_element(len, len, false));
    }
    
qinsoon's avatar
qinsoon committed
125
126
    fn add_move(&mut self, src: Node, dst: Node) {
        self.moves.insert(Move{from: src, to: dst});
127
128
    }
    
qinsoon's avatar
qinsoon committed
129
    pub fn add_interference_edge(&mut self, from: Node, to: Node) {
qinsoon's avatar
qinsoon committed
130
131
132
133
134
135
        // only if two nodes are from the same RegGroup,
        // they may interefere
        if self.nodes_property.get(&from).unwrap().group 
           == self.nodes_property.get(&to).unwrap().group {
            self.matrix.as_mut().unwrap()[(from.0, to.0)] = true;
        }
qinsoon's avatar
qinsoon committed
136
137
    }
    
138
    pub fn color_node(&mut self, node: Node, color: MuID) {
qinsoon's avatar
qinsoon committed
139
        self.nodes_property.get_mut(&node).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
140
141
    }
    
qinsoon's avatar
qinsoon committed
142
143
144
145
    pub fn is_colored(&self, node: Node) -> bool {
        self.nodes_property.get(&node).unwrap().color.is_some()
    }
    
146
147
148
149
    pub fn get_color_of(&self, node: Node) -> Option<MuID> {
        self.nodes_property.get(&node).unwrap().color
    }
    
qinsoon's avatar
qinsoon committed
150
151
    pub fn get_group_of(&self, node: Node) -> backend::RegGroup {
        self.nodes_property.get(&node).unwrap().group
qinsoon's avatar
qinsoon committed
152
153
    }
    
154
155
156
157
158
159
160
161
    pub fn get_temp_of(&self, node: Node) -> MuID {
        self.nodes_property.get(&node).unwrap().temp
    }
    
    pub fn get_spill_cost(&self, node: Node) -> f32 {
        self.nodes_property.get(&node).unwrap().spill_cost
    }
    
162
    fn is_same_node(&self, node1: Node, node2: Node) -> bool {
qinsoon's avatar
qinsoon committed
163
        node1 == node2
qinsoon's avatar
qinsoon committed
164
165
    }
    
qinsoon's avatar
qinsoon committed
166
    pub fn is_adj(&self, from: Node, to: Node) -> bool {
167
168
        let ref matrix = self.matrix.as_ref().unwrap();
        
169
        matrix[(from.0, to.0)] || matrix[(to.0, from.0)]
qinsoon's avatar
qinsoon committed
170
171
    }
    
172
173
174
175
176
177
178
179
180
181
182
183
184
    pub fn outedges_of(&self, node: Node) -> Vec<Node> {
        let mut ret = vec![];
        let matrix = self.matrix.as_ref().unwrap();
        
        for i in 0..self.nodes.len() {
            if matrix[(node.0, i)] {
                ret.push(Node(i));
            }
        }
        
        ret
    }
    
qinsoon's avatar
qinsoon committed
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
    pub fn outdegree_of(&self, node: Node) -> usize {
        let mut count = 0;
        for i in 0..self.nodes.len() {
            if self.matrix.as_ref().unwrap()[(node.0, i)] {
                count += 1;
            }
        }
        
        count
    }
    
    pub fn indegree_of(&self, node: Node) -> usize {
        let mut count = 0;
        for i in 0..self.nodes.len() {
            if self.matrix.as_ref().unwrap()[(i, node.0)] {
                count += 1;
            }
        }
        
        count
    }
    
    pub fn degree_of(&self, node: Node) -> usize {
        self.outdegree_of(node) + self.indegree_of(node)
    }
    
211
212
213
214
    pub fn print(&self) {
        println!("");
        println!("Interference Graph");

qinsoon's avatar
qinsoon committed
215
216
217
218
219
        println!("nodes:");
        for id in self.nodes.keys() {
            println!("Reg {} -> {:?}", id, self.nodes.get(&id).unwrap());
        }

220
        println!("color:");
qinsoon's avatar
qinsoon committed
221
222
        for (n, c) in self.nodes_property.iter() {
            println!("{:?} -> Color/Reg {:?}", n, c);
223
224
225
        }
        println!("moves:");
        for mov in self.moves.iter() {
qinsoon's avatar
qinsoon committed
226
            println!("Move {:?} -> {:?}", mov.from, mov.to);
227
228
229
        }
        println!("graph:");
        {
qinsoon's avatar
qinsoon committed
230
231
            let node_to_reg_id = {
                let mut ret : HashMap<Node, MuID> = HashMap::new();
232
                
qinsoon's avatar
qinsoon committed
233
234
                for reg in self.nodes.keys() {
                    ret.insert(*self.nodes.get(reg).unwrap(), *reg);
235
236
237
238
239
240
241
242
243
                }
                
                ret 
            };
            
            let matrix = self.matrix.as_ref().unwrap();
            for i in 0..matrix.ncols() {
                for j in 0..matrix.nrows() {
                    if matrix[(i, j)] {
244
245
                        let from_node = node_to_reg_id.get(&Node(i)).unwrap();
                        let to_node = node_to_reg_id.get(&Node(j)).unwrap();
246
                        
247
                        println!("Reg {} -> Reg {}", from_node, to_node);
248
249
250
251
252
253
                    }
                }
            }
        }
        println!("");
    }
qinsoon's avatar
qinsoon committed
254
255
}

qinsoon's avatar
qinsoon committed
256
pub fn is_machine_reg(reg: MuID) -> bool {
qinsoon's avatar
qinsoon committed
257
    if reg < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
258
259
260
        true
    } else {
        false
261
262
263
    }
}

264
// from Tailoring Graph-coloring Register Allocation For Runtime Compilation, Figure 4
265
pub fn build_chaitin_briggs (cf: &CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
    let mut ig = InterferenceGraph::new();
    
    // precolor machine register nodes
    for reg in backend::all_regs().iter() {
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
        ig.color_node(node, reg_id);
    }
    
    // Initialize and creates nodes for all the involved temps/regs
    for i in 0..cf.mc.number_of_insts() {
        for reg_id in cf.mc.get_inst_reg_defines(i) {
            let reg_id = *reg_id;
            ig.new_node(reg_id, &func.context);
        }
        
        for reg_id in cf.mc.get_inst_reg_uses(i) {
            let reg_id = *reg_id;
            ig.new_node(reg_id, &func.context);
        }
    }
    
    // all nodes has been added, we init graph (create adjacency matrix)
    ig.init_graph();    
    
    for block in cf.mc.get_all_blocks() {
        // Current_Live(B) = LiveOut(B)
        let mut current_live = LinkedHashSet::from_vec(match cf.mc.get_ir_block_liveout(block) {
            Some(liveout) => liveout.to_vec(),
            None => panic!("cannot find liveout for block {}", block)
        });
        
        let range = cf.mc.get_block_range(block);
        if range.is_none() {
            continue;
        }
        
        // for every inst I in reverse order
        for i in range.unwrap().rev() {
            let src : Option<MuID> = {
                if cf.mc.is_move(i) {
                    let src = cf.mc.get_inst_reg_uses(i);
                    let dst = cf.mc.get_inst_reg_defines(i);
                    
qinsoon's avatar
qinsoon committed
310
311
312
313
                    // src:  reg/imm/mem
                    // dest: reg/mem
                    // we dont care if src/dest is mem
                    if cf.mc.is_using_mem_op(i) {
314
                        None
qinsoon's avatar
qinsoon committed
315
316
317
318
319
320
321
322
323
324
                    } else {
                        if src.len() == 1 {
                            let node1 = ig.get_node(src[0]);
                            let node2 = ig.get_node(dst[0]);
                            ig.add_move(node1, node2);
                            
                            Some(src[0])
                        } else {
                            None
                        }
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
                    }
                } else {
                    None
                }
            };
            
            // for every definition D in I
            for d in cf.mc.get_inst_reg_defines(i) {
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
                        let from = ig.get_node(*d);
                        let to = ig.get_node(*e);
                        
                        if !ig.is_same_node(from, to) && !ig.is_adj(from, to) {
                            if !ig.is_colored(from) {
                                ig.add_interference_edge(from, to);
                            }
                            if !ig.is_colored(to) {
                                ig.add_interference_edge(to, from);
                            }
                        }
                    }
                }
            }
            
            // for every definition D in I
            for d in cf.mc.get_inst_reg_defines(i) {
                // remove D from Current_Live
                current_live.remove(d);
            }
            
            // for every use U in I
            for u in cf.mc.get_inst_reg_uses(i) {
                // add U to Current_live
                current_live.insert(*u);
            }
        }
    }
    
    ig
}

369
// from tony's code src/RegAlloc/Liveness.java
370
371
// this function is no longer used
#[allow(dead_code)]
372
pub fn build (cf: &CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
373
374
    let mut ig = InterferenceGraph::new();
    
qinsoon's avatar
qinsoon committed
375
376
377
378
379
380
    // precolor machine register nodes
    for reg in backend::all_regs().iter() {
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
        ig.color_node(node, reg_id);
    }
381
382
383
384
385
386
387
388
389
390
391
392
393
    
    // Liveness Analysis
    let n_insts = cf.mc.number_of_insts();
    let mut live_in : Vec<Vec<MuID>> = vec![vec![]; n_insts];
    let mut live_out : Vec<Vec<MuID>> = vec![vec![]; n_insts];
    let mut work_list : LinkedList<usize> = LinkedList::new();
    
    // Initialize 'in' sets for each node in the flow graph
    // and creates nodes for all the involved temps/regs
    for i in 0..n_insts {
        let ref mut in_set = live_in[i];
        
        for reg_id in cf.mc.get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
394
            let reg_id = *reg_id;
qinsoon's avatar
qinsoon committed
395
            ig.new_node(reg_id, &func.context);
396
397
398
        }
        
        for reg_id in cf.mc.get_inst_reg_uses(i) {
qinsoon's avatar
qinsoon committed
399
            let reg_id = *reg_id;
qinsoon's avatar
qinsoon committed
400
            ig.new_node(reg_id, &func.context);
qinsoon's avatar
qinsoon committed
401
402
            
            in_set.push(reg_id);
403
404
405
406
407
        }
        
        work_list.push_front(i);
    }
    
qinsoon's avatar
qinsoon committed
408
409
410
411
    // all nodes has been added, we init graph (create adjacency matrix)
    ig.init_graph();
    
    // compute liveIn and liveOut iteratively
412
    trace!("build live outs");
413
414
    while !work_list.is_empty() {
        let n = work_list.pop_front().unwrap();
415
        trace!("build liveout for #{}", n);
416
        let ref mut out_set = live_out[n];
qinsoon's avatar
qinsoon committed
417
418
419
        
        // out = union(in[succ]) for all succs
        for succ in cf.mc.get_succs(n) {
420
            trace!("add successor's livein {:?} to #{}", &live_in[*succ], n); 
421
            vec_utils::add_all(out_set, &live_in[*succ]);
qinsoon's avatar
qinsoon committed
422
423
424
425
426
        }
        
        // in = use(i.e. live_in) + (out - def) 
        let mut diff = out_set.clone();
        for def in cf.mc.get_inst_reg_defines(n) {
427
            vec_utils::remove_value(&mut diff, *def);
428
429
            trace!("removing def: {}", *def);
            trace!("diff = {:?}", diff);
qinsoon's avatar
qinsoon committed
430
        }
431
        trace!("out - def = {:?}", diff);
qinsoon's avatar
qinsoon committed
432
433
434
        
        if !diff.is_empty() {
            let ref mut in_set = live_in[n];
435
            trace!("in = (use) {:?}", in_set);
qinsoon's avatar
qinsoon committed
436
            
437
            if vec_utils::add_all(in_set, &diff) {
qinsoon's avatar
qinsoon committed
438
439
440
441
442
                for p in cf.mc.get_preds(n) {
                    work_list.push_front(*p);
                }
            }
        }
443
        trace!("in = use + (out - def) = {:?}", live_in[n]);
444
445
446
447
448
449
450
451
452
    }
    
    // debug live-outs
    if cfg!(debug_assertions) {
        trace!("check live-outs");
        for n in 0..n_insts {
            let ref mut live = live_out[n];
            trace!("#{}\t{:?}", n, live);
        }
qinsoon's avatar
qinsoon committed
453
454
455
456
457
458
459
460
461
462
463
    }
    
    // build interference graph
    for n in 0..n_insts {
        let ref mut live = live_out[n];
        
        let src : Option<MuID> = {
            if cf.mc.is_move(n) {
                let src = cf.mc.get_inst_reg_uses(n);
                let dst = cf.mc.get_inst_reg_defines(n);
                
464
465
                // src may be an immediate number
                // but dest is definitly a register
qinsoon's avatar
qinsoon committed
466
467
                debug_assert!(dst.len() == 1);
                
468
                if src.len() == 1 {
qinsoon's avatar
qinsoon committed
469
470
471
                    let node1 = ig.get_node(src[0]);
                    let node2 = ig.get_node(dst[0]);
                    ig.add_move(node1, node2);
472
473
474
475
476
                    
                    Some(src[0])
                } else {
                    None
                }
qinsoon's avatar
qinsoon committed
477
478
479
480
481
482
483
484
            } else {
                None
            }
        };
        
        for d in cf.mc.get_inst_reg_defines(n) {
            for t in live.iter() {
                if src.is_none() || (src.is_some() && *t != src.unwrap()) {
485
486
                    let from = ig.get_node(*d);
                    let to = ig.get_node(*t);
qinsoon's avatar
qinsoon committed
487
488
                    
                    if !ig.is_same_node(from, to) && !ig.is_adj(from, to) {
qinsoon's avatar
qinsoon committed
489
                        if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
490
491
                            ig.add_interference_edge(from, to);
                        }
qinsoon's avatar
qinsoon committed
492
                        if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
493
494
495
496
497
498
499
500
                            ig.add_interference_edge(to, from);
                        }
                    }
                }
            }
        }
        
        for d in cf.mc.get_inst_reg_defines(n) {
501
            vec_utils::remove_value(live, *d);
qinsoon's avatar
qinsoon committed
502
503
504
505
506
507
508
509
        }
        
        for u in cf.mc.get_inst_reg_uses(n) {
            live.push(*u);
        }
    }
    
    ig
510
}