1cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar(*===----------------------------------------------------------------------=== 2cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * Code Generation 3cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar *===----------------------------------------------------------------------===*) 4cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 5cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaaropen Llvm 6cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 7cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarexception Error of string 8cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 9cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet context = global_context () 10cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet the_module = create_module context "my cool jit" 11cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet builder = builder context 12cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10 13cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet double_type = double_type context 14cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 15cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar(* Create an alloca instruction in the entry block of the function. This 16cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * is used for mutable variables etc. *) 17cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet create_entry_block_alloca the_function var_name = 18cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let builder = builder_at context (instr_begin (entry_block the_function)) in 19cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar build_alloca double_type var_name builder 20cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 21cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet rec codegen_expr = function 22cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Number n -> const_float double_type n 23cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Variable name -> 24cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let v = try Hashtbl.find named_values name with 25cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Not_found -> raise (Error "unknown variable name") 26cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 27cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Load the value. *) 28cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar build_load v name builder 29cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Unary (op, operand) -> 30cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let operand = codegen_expr operand in 31cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let callee = "unary" ^ (String.make 1 op) in 32cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let callee = 33cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match lookup_function callee the_module with 34cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Some callee -> callee 35cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | None -> raise (Error "unknown unary operator") 36cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 37cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar build_call callee [|operand|] "unop" builder 38cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Binary (op, lhs, rhs) -> 39cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar begin match op with 40cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | '=' -> 41cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Special case '=' because we don't want to emit the LHS as an 42cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * expression. *) 43cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let name = 44cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match lhs with 45cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Variable name -> name 46cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | _ -> raise (Error "destination of '=' must be a variable") 47cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 48cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 49cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Codegen the rhs. *) 50cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let val_ = codegen_expr rhs in 51cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 52cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Lookup the name. *) 53cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let variable = try Hashtbl.find named_values name with 54cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Not_found -> raise (Error "unknown variable name") 55cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 56cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore(build_store val_ variable builder); 57cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar val_ 58cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | _ -> 59cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let lhs_val = codegen_expr lhs in 60cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let rhs_val = codegen_expr rhs in 61cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar begin 62cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match op with 6388364df7b6429fa96bb5130ea73bd40b0629e30eEric Christopher | '+' -> build_fadd lhs_val rhs_val "addtmp" builder 6488364df7b6429fa96bb5130ea73bd40b0629e30eEric Christopher | '-' -> build_fsub lhs_val rhs_val "subtmp" builder 6588364df7b6429fa96bb5130ea73bd40b0629e30eEric Christopher | '*' -> build_fmul lhs_val rhs_val "multmp" builder 66cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | '<' -> 67cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Convert bool 0/1 to double 0.0 or 1.0 *) 68cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in 69cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar build_uitofp i double_type "booltmp" builder 70cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | _ -> 71cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If it wasn't a builtin binary operator, it must be a user defined 72cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * one. Emit a call to it. *) 73cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let callee = "binary" ^ (String.make 1 op) in 74cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let callee = 75cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match lookup_function callee the_module with 76cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Some callee -> callee 77cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | None -> raise (Error "binary operator not found!") 78cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 79cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar build_call callee [|lhs_val; rhs_val|] "binop" builder 80cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar end 81cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar end 82cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Call (callee, args) -> 83cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Look up the name in the module table. *) 84cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let callee = 85cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match lookup_function callee the_module with 86cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Some callee -> callee 87cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | None -> raise (Error "unknown function referenced") 88cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 89cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let params = params callee in 90cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 91cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If argument mismatch error. *) 92cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar if Array.length params == Array.length args then () else 93cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar raise (Error "incorrect # arguments passed"); 94cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let args = Array.map codegen_expr args in 95cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar build_call callee args "calltmp" builder 96cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.If (cond, then_, else_) -> 97cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let cond = codegen_expr cond in 98cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 99cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Convert condition to a bool by comparing equal to 0.0 *) 100cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let zero = const_float double_type 0.0 in 101cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in 102cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 103cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Grab the first block so that we might later add the conditional branch 104cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * to it at the end of the function. *) 105cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let start_bb = insertion_block builder in 106cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let the_function = block_parent start_bb in 107cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 108cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let then_bb = append_block context "then" the_function in 109cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 110cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Emit 'then' value. *) 111cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end then_bb builder; 112cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let then_val = codegen_expr then_ in 113cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 114cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Codegen of 'then' can change the current block, update then_bb for the 115cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * phi. We create a new name because one is used for the phi node, and the 116cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * other is used for the conditional branch. *) 117cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let new_then_bb = insertion_block builder in 118cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 119cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Emit 'else' value. *) 120cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let else_bb = append_block context "else" the_function in 121cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end else_bb builder; 122cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let else_val = codegen_expr else_ in 123cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 124cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Codegen of 'else' can change the current block, update else_bb for the 125cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * phi. *) 126cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let new_else_bb = insertion_block builder in 127cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 128cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Emit merge block. *) 129cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let merge_bb = append_block context "ifcont" the_function in 130cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end merge_bb builder; 131cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in 132cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let phi = build_phi incoming "iftmp" builder in 133cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 134cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Return to the start block to add the conditional branch. *) 135cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end start_bb builder; 136cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore (build_cond_br cond_val then_bb else_bb builder); 137cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 138cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Set a unconditional branch at the end of the 'then' block and the 139cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * 'else' block to the 'merge' block. *) 140cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end new_then_bb builder; ignore (build_br merge_bb builder); 141cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end new_else_bb builder; ignore (build_br merge_bb builder); 142cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 143cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Finally, set the builder to the end of the merge block. *) 144cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end merge_bb builder; 145cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 146cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar phi 147cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.For (var_name, start, end_, step, body) -> 148cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Output this as: 149cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * var = alloca double 150cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * ... 151cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * start = startexpr 152cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * store start -> var 153cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * goto loop 154cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * loop: 155cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * ... 156cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * bodyexpr 157cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * ... 158cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * loopend: 159cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * step = stepexpr 160cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * endcond = endexpr 161cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * 162cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * curvar = load var 163cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * nextvar = curvar + step 164cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * store nextvar -> var 165cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * br endcond, loop, endloop 166cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * outloop: *) 167cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 168cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let the_function = block_parent (insertion_block builder) in 169cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 170cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Create an alloca for the variable in the entry block. *) 171cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let alloca = create_entry_block_alloca the_function var_name in 172cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 173cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Emit the start code first, without 'variable' in scope. *) 174cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let start_val = codegen_expr start in 175cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 176cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Store the value into the alloca. *) 177cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore(build_store start_val alloca builder); 178cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 179cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Make the new basic block for the loop header, inserting after current 180cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * block. *) 181cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let loop_bb = append_block context "loop" the_function in 182cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 183cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Insert an explicit fall through from the current block to the 184cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * loop_bb. *) 185cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore (build_br loop_bb builder); 186cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 187cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Start insertion in loop_bb. *) 188cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end loop_bb builder; 189cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 190cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Within the loop, the variable is defined equal to the PHI node. If it 191cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * shadows an existing variable, we have to restore it, so save it 192cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * now. *) 193cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let old_val = 194cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar try Some (Hashtbl.find named_values var_name) with Not_found -> None 195cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 196cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Hashtbl.add named_values var_name alloca; 197cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 198cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Emit the body of the loop. This, like any other expr, can change the 199cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * current BB. Note that we ignore the value computed by the body, but 200cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * don't allow an error *) 201cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore (codegen_expr body); 202cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 203cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Emit the step value. *) 204cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let step_val = 205cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match step with 206cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Some step -> codegen_expr step 207cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If not specified, use 1.0. *) 208cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | None -> const_float double_type 1.0 209cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 210cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 211cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Compute the end condition. *) 212cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let end_cond = codegen_expr end_ in 213cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 214cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Reload, increment, and restore the alloca. This handles the case where 215cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * the body of the loop mutates the variable. *) 216cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let cur_var = build_load alloca var_name builder in 217cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let next_var = build_add cur_var step_val "nextvar" builder in 218cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore(build_store next_var alloca builder); 219cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 220cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Convert condition to a bool by comparing equal to 0.0. *) 221cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let zero = const_float double_type 0.0 in 222cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in 223cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 224cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Create the "after loop" block and insert it. *) 225cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let after_bb = append_block context "afterloop" the_function in 226cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 227cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Insert the conditional branch into the end of loop_end_bb. *) 228cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore (build_cond_br end_cond loop_bb after_bb builder); 229cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 230cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Any new code will be inserted in after_bb. *) 231cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end after_bb builder; 232cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 233cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Restore the unshadowed variable. *) 234cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar begin match old_val with 235cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Some old_val -> Hashtbl.add named_values var_name old_val 236cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | None -> () 237cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar end; 238cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 239cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* for expr always returns 0.0. *) 240cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar const_null double_type 241cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Var (var_names, body) -> 242cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let old_bindings = ref [] in 243cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 244cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let the_function = block_parent (insertion_block builder) in 245cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 246cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Register all variables and emit their initializer. *) 247cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Array.iter (fun (var_name, init) -> 248cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Emit the initializer before adding the variable to scope, this 249cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * prevents the initializer from referencing the variable itself, and 250cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * permits stuff like this: 251cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * var a = 1 in 252cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * var a = a in ... # refers to outer 'a'. *) 253cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let init_val = 254cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match init with 255cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Some init -> codegen_expr init 256cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If not specified, use 0.0. *) 257cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | None -> const_float double_type 0.0 258cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 259cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 260cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let alloca = create_entry_block_alloca the_function var_name in 261cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore(build_store init_val alloca builder); 262cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 263cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Remember the old variable binding so that we can restore the binding 264cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * when we unrecurse. *) 265cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar begin 266cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar try 267cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let old_value = Hashtbl.find named_values var_name in 268cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar old_bindings := (var_name, old_value) :: !old_bindings; 269cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar with Not_found -> () 270cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar end; 271cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 272cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Remember this binding. *) 273cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Hashtbl.add named_values var_name alloca; 274cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ) var_names; 275cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 276cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Codegen the body, now that all vars are in scope. *) 277cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let body_val = codegen_expr body in 278cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 279cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Pop all our variables from scope. *) 280cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar List.iter (fun (var_name, old_value) -> 281cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Hashtbl.add named_values var_name old_value 282cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ) !old_bindings; 283cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 284cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Return the body computation. *) 285cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar body_val 286cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 287cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet codegen_proto = function 288cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Prototype (name, args) | Ast.BinOpPrototype (name, args, _) -> 289cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Make the function type: double(double,double) etc. *) 290cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let doubles = Array.make (Array.length args) double_type in 291cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let ft = function_type double_type doubles in 292cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let f = 293cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar match lookup_function name the_module with 294cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | None -> declare_function name ft the_module 295cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 296cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If 'f' conflicted, there was already something named 'name'. If it 297cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * has a body, don't allow redefinition or reextern. *) 298cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Some f -> 299cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If 'f' already has a body, reject this. *) 300cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar if block_begin f <> At_end f then 301cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar raise (Error "redefinition of function"); 302cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 303cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If 'f' took a different number of arguments, reject. *) 304cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar if element_type (type_of f) <> ft then 305cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar raise (Error "redefinition of function with different # args"); 306cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar f 307cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 308cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 309cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Set names for all arguments. *) 310cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Array.iteri (fun i a -> 311cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let n = args.(i) in 312cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar set_value_name n a; 313cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Hashtbl.add named_values n a; 314cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ) (params f); 315cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar f 316cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 317cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar(* Create an alloca for each argument and register the argument in the symbol 318cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar * table so that references to it will succeed. *) 319cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet create_argument_allocas the_function proto = 320cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let args = match proto with 321cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Prototype (_, args) | Ast.BinOpPrototype (_, args, _) -> args 322cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar in 323cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Array.iteri (fun i ai -> 324cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let var_name = args.(i) in 325cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Create an alloca for this variable. *) 326cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let alloca = create_entry_block_alloca the_function var_name in 327cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 328cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Store the initial value into the alloca. *) 329cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ignore(build_store ai alloca builder); 330cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 331cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Add arguments to variable symbol table. *) 332cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Hashtbl.add named_values var_name alloca; 333cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar ) (params the_function) 334cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 335cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaarlet codegen_func the_fpm = function 336cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.Function (proto, body) -> 337cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Hashtbl.clear named_values; 338cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let the_function = codegen_proto proto in 339cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 340cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* If this is an operator, install it. *) 341cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar begin match proto with 342cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | Ast.BinOpPrototype (name, args, prec) -> 343cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let op = name.[String.length name - 1] in 344cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Hashtbl.add Parser.binop_precedence op prec; 345cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar | _ -> () 346cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar end; 347cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 348cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Create a new basic block to start insertion into. *) 349cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let bb = append_block context "entry" the_function in 350cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar position_at_end bb builder; 351cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 352cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar try 353cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Add all arguments to the symbol table and create their allocas. *) 354cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar create_argument_allocas the_function proto; 355cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 356cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let ret_val = codegen_expr body in 357cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 358cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Finish off the function. *) 359cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let _ = build_ret ret_val builder in 360cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 361cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Validate the generated code, checking for consistency. *) 362cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar Llvm_analysis.assert_valid_function the_function; 363cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 364cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar (* Optimize the function. *) 365cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar let _ = PassManager.run_function the_function the_fpm in 366cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar 367cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar the_function 368cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar with e -> 369cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar delete_function the_function; 370cabc7af293504ad256d2203ae88ee11cbc34c2edErick Tryzelaar raise e 371