tree_gen.rs 9.88 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3 4 5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
qinsoon's avatar
qinsoon committed
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9 10 11 12 13 14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15
use ast::inst::*;
16 17
use ast::ir::*;
use ast::ptr::*;
18

19
use compiler::CompilerPass;
20
use vm::VM;
21

qinsoon's avatar
qinsoon committed
22 23
use std::any::Any;

qinsoon's avatar
qinsoon committed
24
pub struct TreeGen {
25
    name: &'static str
qinsoon's avatar
qinsoon committed
26
}
27

qinsoon's avatar
qinsoon committed
28 29
impl TreeGen {
    pub fn new() -> TreeGen {
qinsoon's avatar
qinsoon committed
30
        TreeGen {
31
            name: "Tree Geenration"
qinsoon's avatar
qinsoon committed
32
        }
33 34 35
    }
}

36
fn is_movable(inst: &Instruction) -> bool {
qinsoon's avatar
qinsoon committed
37
    is_suitable_child(inst)
38 39
}

qinsoon's avatar
qinsoon committed
40 41 42 43 44
/// is this instruction suitable to be tree child (we may find pattern for it)?
fn is_suitable_child(inst: &Instruction) -> bool {
    use ast::inst::Instruction_::*;

    match inst.v {
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
        Return(_)
        | ThreadExit
        | Throw(_)
        | TailCall(_)
        | Branch1(_)
        | Branch2 { .. }
        | Watchpoint { .. }
        | WPBranch { .. }
        | Call { .. }
        | CCall { .. }
        | SwapStackExc { .. }
        | SwapStackKill { .. }
        | Switch { .. }
        | ExnInstruction { .. }
        | PrintHex(_)
60
        | PrintBool(_)
61
        | PrintTime(_)
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
        | SetRetval(_)
        | KillStack(_)
        | CurrentStack
        | SwapStackExpr { .. }
        | CommonInst_Tr64IsFp(_)
        | CommonInst_Tr64IsInt(_)
        | CommonInst_Tr64IsRef(_)
        | CommonInst_Tr64FromFp(_)
        | CommonInst_Tr64FromInt(_)
        | CommonInst_Tr64FromRef(_, _)
        | CommonInst_Tr64ToFp(_)
        | CommonInst_Tr64ToInt(_)
        | CommonInst_Tr64ToRef(_)
        | CommonInst_Tr64ToTag(_)
        | ExprCall { .. }
        | ExprCCall { .. }
        | New(_)
        | AllocA(_)
        | NewHybrid(_, _)
        | AllocAHybrid(_, _)
82
        | AllocAU(_)
83
        | AllocAUHybrid(_,_)
84 85 86 87 88 89 90
        | NewReg(_)
        | DeleteReg(_)
        | rAlloc(_, _)
        | rAllocHybrid(_,_,_)
        | eAlloc(_)
        | eAllocHybrid(_,_)
        | eDelete(_)
91 92
        | NewStack(_)
        | NewThread { .. }
93
        | NewRTThread { .. }
Javad Ebrahimian Amiri's avatar
Javad Ebrahimian Amiri committed
94
        | NewFutex | DeleteFutex(_) | LockFutex(_) | UnlockFutex(_)
95
        | NotifyThread(_)
96 97 98 99 100
        | SetPriority(_, _)
        | GetPriority(_)
        | AffinityIsset(_, _)
        | AffinitySet(_, _)
        | AffinityClear(_, _)
101 102
        | GetTime
        | SetTime(_)
Javad Ebrahimian Amiri's avatar
Javad Ebrahimian Amiri committed
103 104 105 106 107
        | NewTimer
        | SetTimer(_,_,_,_)
        | CancelTimer(_)
        | DeleteTimer(_)
        | Sleep(_)
108 109 110 111 112 113 114 115 116 117
        | NewFrameCursor(_)
        | Select { .. }
        | Fence(_)
        | CommonInst_SetThreadLocal(_)
        | CommonInst_Pin(_)
        | CommonInst_Unpin(_)
        | CommonInst_GetAddr(_)
        | CmpXchg { .. }
        | AtomicRMW { .. }
        | Store { .. }
118 119
        | RandF(_,_)
        | RandI(_,_)
120
        | GetVMThreadLocal => false,
qinsoon's avatar
qinsoon committed
121

122 123 124 125
        BinOp(_, _, _)
        | BinOpWithStatus(_, _, _, _)
        | CommonInst_GetThreadLocal
        | Move(_) => false,
126

127 128 129 130 131 132 133 134
        CmpOp(_, _, _)
        | ConvOp { .. }
        | Load { .. }
        | GetIRef(_)
        | GetFieldIRef { .. }
        | GetElementIRef { .. }
        | ShiftIRef { .. }
        | GetVarPartIRef { .. } => true,
qinsoon's avatar
qinsoon committed
135 136 137
    }
}

138 139 140 141 142 143 144 145 146
fn should_always_move(inst: &Instruction) -> bool {
    // for instructions that yields int<1>, we always move the instruction
    if let Some(ref vals) = inst.value {
        if vals.len() == 1 && vals[0].ty.is_int_n(1) {
            return true;
        }
    }
    false
}
qinsoon's avatar
qinsoon committed
147

qinsoon's avatar
qinsoon committed
148
impl CompilerPass for TreeGen {
qinsoon's avatar
qinsoon committed
149 150
    fn name(&self) -> &'static str {
        self.name
151
    }
qinsoon's avatar
qinsoon committed
152 153 154 155

    fn as_any(&self) -> &Any {
        self
    }
qinsoon's avatar
qinsoon committed
156

157
    fn execute(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
158
        // We are trying to generate a depth tree from the original AST.
159 160 161
        // If an SSA variable is used only once, and the instruction that
        // generates it is movable, then we replace the use of the SSA
        // with the actual variable
qinsoon's avatar
qinsoon committed
162 163

        // we are doing it in two steps
164 165 166 167 168 169
        // 1. if we see an expression that generates an SSA which is used only
        // once and used    in its next instruction, we take out the
        // expression node 2. if we see an SSA that is used only once
        // (and it is this place for sure), we replace it    with the
        // expression node because of SSA form,  it is guaranteed to see
        // 1 before 2 for SSA variables.
qinsoon's avatar
qinsoon committed
170
        debug!("---CompilerPass {} for {}---", self.name(), func);
qinsoon's avatar
qinsoon committed
171

qinsoon's avatar
qinsoon committed
172 173 174
        {
            let ref mut func_content = func.content;
            let ref mut context = func.context;
175 176 177
            for (label, ref mut block) in
                func_content.as_mut().unwrap().blocks.iter_mut()
            {
178 179 180
                trace!("check block {}", label);
                trace!("");

qinsoon's avatar
qinsoon committed
181 182 183
                // take its content, we will need to put it back
                let mut content = block.content.take().unwrap();
                let body = content.body;
qinsoon's avatar
qinsoon committed
184

qinsoon's avatar
qinsoon committed
185
                let mut new_body = vec![];
qinsoon's avatar
qinsoon committed
186

qinsoon's avatar
qinsoon committed
187
                for i in 0..body.len() {
188 189 190 191
                    let node = body[i].clone();
                    let new_node = insert_inst_as_child(node, context);
                    if !is_child_inst(&new_node, i, &body, context) {
                        new_body.push(new_node);
qinsoon's avatar
qinsoon committed
192 193
                    }
                    trace!("");
194
                }
qinsoon's avatar
qinsoon committed
195

qinsoon's avatar
qinsoon committed
196 197
                content.body = new_body;
                trace!("block {} has {} insts", label, content.body.len());
198
                trace!("");
qinsoon's avatar
qinsoon committed
199

qinsoon's avatar
qinsoon committed
200 201
                // put the content back
                block.content = Some(content);
202 203
            }
        }
qinsoon's avatar
qinsoon committed
204

qinsoon's avatar
qinsoon committed
205
        self.finish_function(vm, func);
qinsoon's avatar
qinsoon committed
206

207 208
        debug!("---finish---");
    }
qinsoon's avatar
qinsoon committed
209

210
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
211
    fn finish_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
212
        debug!("check depth tree for {}", func);
qinsoon's avatar
qinsoon committed
213

214
        for entry in func.content.as_ref().unwrap().blocks.iter() {
215
            debug!("block {}", entry.1.name());
qinsoon's avatar
qinsoon committed
216

217
            for inst in entry.1.content.as_ref().unwrap().body.iter() {
218
                debug!("{}", inst);
219 220 221
            }
        }
    }
222
}
223 224 225 226 227

fn is_child_inst(
    node: &P<TreeNode>,
    cur_index: usize,
    body: &Vec<P<TreeNode>>,
228
    context: &mut FunctionContext
229 230 231 232
) -> bool {
    trace!("is child inst: {}", node);
    match node.v {
        TreeNode_::Instruction(ref inst) => {
233 234
            // check whether the instruction generates an SSA that is used only
            // once An instruction can replace its value if
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
            // * it generates only one value
            // * the value is used only once
            // * the instruction is movable
            // * the value is used in the next instruction
            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 ref val_lhs = left[0];
                    let lhs = context
                        .get_value_mut(left[0].extract_ssa_id().unwrap())
                        .unwrap();
                    if lhs.use_count() == 1 {
                        let next_inst_uses_lhs = {
                            if cur_index != body.len() - 1 {
252 253 254 255 256 257
                                let ref next_inst =
                                    body[cur_index + 1].as_inst();
                                next_inst
                                    .ops
                                    .iter()
                                    .any(|x| x.as_value() == val_lhs)
258 259 260 261
                            } else {
                                false
                            }
                        };
262 263 264
                        if should_always_move(&inst)
                            || (is_movable(&inst) && next_inst_uses_lhs)
                        {
265 266 267 268 269 270
                            // FIXME: should be able to move the inst here
                            lhs.assign_expr(inst.clone());

                            trace!("  yes, extract the inst");
                            return true;
                        } else {
271 272 273
                            trace!(
                                "  no, not movable or not used by next inst"
                            );
274 275 276 277 278 279 280 281 282 283 284 285
                        }
                    } else {
                        trace!("  no, use count more than 1");
                    }
                } else {
                    trace!("  no, yields more than 1 SSA var");
                }
            } else {
                trace!("  no, no value yielded");
            }
            false
        }
286
        _ => panic!("expected an instruction node here")
287 288 289
    }
}

290 291 292 293
fn insert_inst_as_child(
    node: P<TreeNode>,
    context: &mut FunctionContext
) -> P<TreeNode> {
294 295 296 297 298 299 300 301 302
    trace!("insert child for: {}", node);
    let mut inst = node.as_inst().clone();

    // check whether any operands (SSA) can be replaced by expression
    {
        let ref mut ops = inst.ops;
        for index in 0..ops.len() {
            let ssa_id = ops[index].extract_ssa_id();
            if ssa_id.is_some() {
303 304
                let entry_value =
                    context.get_value_mut(ssa_id.unwrap()).unwrap();
305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323

                if entry_value.has_expr() {
                    // replace the node with its expr
                    let expr = entry_value.take_expr();

                    trace!("  {} replaced by {}", ops[index], expr);
                    ops[index] = TreeNode::new_inst(expr);
                }
            } else {
                trace!("  {} cant be replaced", ops[index]);
            }
        }
    }

    let new_node = TreeNode::new_inst(inst);
    trace!("  rewrite node as {}", new_node);

    new_node
}