tree_gen.rs 5.59 KB
Newer Older
1
use ast::ir::*;
2
use ast::inst::*;
3
use ast::ir_semantics::*;
4

qinsoon's avatar
qinsoon committed
5
use vm::VM;
6
use compiler::CompilerPass;
7
use compiler::PassExecutionResult;
8

qinsoon's avatar
qinsoon committed
9
pub struct TreeGen {
10
    name: &'static str
qinsoon's avatar
qinsoon committed
11
} 
12

qinsoon's avatar
qinsoon committed
13 14 15
impl TreeGen {
    pub fn new() -> TreeGen {
        TreeGen{name: "Tree Geenration"}
16 17 18
    }
}

19 20 21 22
fn is_movable(expr: &Instruction_) -> bool {
    !has_side_effect(expr)
}

qinsoon's avatar
qinsoon committed
23
impl CompilerPass for TreeGen {
qinsoon's avatar
qinsoon committed
24 25
    fn name(&self) -> &'static str {
        self.name
26
    }
27
    
qinsoon's avatar
qinsoon committed
28
    fn execute(&mut self, vm: &VM, func: &mut MuFunctionVersion) -> PassExecutionResult {
qinsoon's avatar
qinsoon committed
29
        debug!("---CompilerPass {} for {}---", self.name(), func);
30
        
qinsoon's avatar
qinsoon committed
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
        {
            let ref mut func_content = func.content;
            let ref mut context = func.context;
            for (label, ref mut block) in func_content.as_mut().unwrap().blocks.iter_mut() {
                // take its content, we will need to put it back
                let mut content = block.content.take().unwrap();
                let body = content.body;
                
                let mut new_body = vec![];
                
                trace!("check block {}", label);
                trace!("");
                
                for node in body.into_iter() {
                    trace!("check inst: {}", node);
                    match &node.v {
                        &TreeNode_::Instruction(ref inst) => {
                            // check if any operands can be replaced by expression
                            {
                                trace!("check if we can replace any operand with inst");
                                
                                let mut ops = inst.ops.borrow_mut();
                                for index in 0..ops.len() {
                                    let possible_ssa_id = ops[index].extract_ssa_id();
                                    if possible_ssa_id.is_some() {
                                        let entry_value = context.get_value_mut(possible_ssa_id.unwrap()).unwrap();
57
                                        
qinsoon's avatar
qinsoon committed
58 59 60 61 62
                                        if entry_value.expr.is_some() {
                                            // replace the node with its expr
                                            let expr = entry_value.expr.take().unwrap();
                                            
                                            trace!("{} replaced by {}", ops[index], expr);
qinsoon's avatar
qinsoon committed
63
                                            ops[index] = TreeNode::new_inst(vm.next_id(), expr);
qinsoon's avatar
qinsoon committed
64 65 66 67
                                        }
                                    } else {
                                        trace!("{} cant be replaced", ops[index]);
                                    } 
68 69 70
                                }
                            }
                            
qinsoon's avatar
qinsoon committed
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
                            // check if left hand side of an assignment has a single use
                            trace!("check if we should fold the inst");
                            if inst.value.is_some() {
                                let left = inst.value.as_ref().unwrap();
                                
                                // if left is _one_ variable that is used once
                                // we can put the expression as a child node to its use
                                if left.len() == 1 {
                                    let lhs = context.get_value_mut(left[0].extract_ssa_id().unwrap()).unwrap(); 
                                    if lhs.use_count.get() == 1{
                                        if is_movable(&inst.v) {
                                            lhs.expr = Some(inst.clone()); // FIXME: should be able to move the inst here 
                                            
                                            trace!("yes");
                                            trace!("");
                                            continue;
                                        } else {
                                            trace!("no, not movable");
                                        }
90
                                    } else {
qinsoon's avatar
qinsoon committed
91
                                        trace!("no, use count more than 1");
92 93
                                    }
                                } else {
qinsoon's avatar
qinsoon committed
94
                                    trace!("no, yields more than 1 SSA var");
95 96
                                }
                            } else {
qinsoon's avatar
qinsoon committed
97
                                trace!("no, no value yielded");
98
                            }
qinsoon's avatar
qinsoon committed
99 100 101 102 103 104 105
                        },
                        _ => panic!("expected an instruction node here")
                    }
                    
                    trace!("add {} back to block {}", node, label);
                    trace!("");
                    new_body.push(node);
106 107
                }
                
qinsoon's avatar
qinsoon committed
108 109
                content.body = new_body;
                trace!("block {} has {} insts", label, content.body.len());
110
                trace!("");
qinsoon's avatar
qinsoon committed
111 112 113
                            
                // put the content back
                block.content = Some(content);
114 115 116
            }
        }
        
qinsoon's avatar
qinsoon committed
117
        self.finish_function(vm, func);
118 119
        
        debug!("---finish---");
120 121
        
        PassExecutionResult::ProceedToNext
122 123 124
    }
    
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
125
    fn finish_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
126
        debug!("check depth tree for {}", func);
127 128 129 130 131
        
        for entry in func.content.as_ref().unwrap().blocks.iter() {
            debug!("block {}", entry.0);
            
            for inst in entry.1.content.as_ref().unwrap().body.iter() {
132
                debug!("{}", inst);
133 134 135
            }
        }
    }
136
}