rustc: First stab at implementing interior vector concat in the DPS engine

3 files changed, 267 insertions, 27 deletions

diff --git a/src/comp/middle/trans_dps.rs b/src/comp/middle/trans_dps.rs
index 91d7fef8fd4..8c5743096ec 100644
--- a/src/comp/middle/trans_dps.rs
+++ b/src/comp/middle/trans_dps.rs
@@ -62,6 +62,17 @@ fn mk_const(&@crate_ctxt ccx, &str name, bool exported, ValueRef llval)
 }
 
 
+// Type utilities
+
+fn size_of(&@crate_ctxt ccx, &span sp, ty::t t) -> uint {
+    if ty::type_has_dynamic_size(ccx.tcx, t) {
+        ccx.sess.bug("trans_dps::size_of() called on a type with dynamic " +
+                     "size");
+    }
+    ret llsize_of(ccx, trans::type_of_inner(ccx, sp, t));
+}
+
+
 // Destination utilities
 
 tag dest {
@@ -93,7 +104,12 @@ fn dest_ptr(&dest dest) -> ValueRef {
     alt (dest) {
       dst_nil { fail "nil dest in dest_ptr" }
       dst_imm(_) { fail "immediate dest in dest_ptr" }
-      dst_alias(_) { fail "alias dest in dest_ptr" }
+      dst_alias(?box) {
+        alt (*box) {
+          none { fail "alias wasn't filled in prior to dest_ptr" }
+          some(?llval) { llval }
+        }
+      }
       dst_copy(?llptr) { llptr }
       dst_move(?llptr) { llptr }
     }
@@ -137,6 +153,22 @@ fn ccx_tcx(&@crate_ctxt ccx) -> ty::ctxt { ret ccx.tcx; }
 
 // Common operations
 
+fn memmove(&@block_ctxt bcx, ValueRef lldestptr, ValueRef llsrcptr,
+           ValueRef llsz) {
+    auto lldestty = llelement_type(trans::val_ty(lldestptr));
+    auto llsrcty = llelement_type(trans::val_ty(llsrcptr));
+    auto dest_align = llalign_of(bcx_ccx(bcx), lldestty);
+    auto src_align = llalign_of(bcx_ccx(bcx), llsrcty);
+    auto align = uint::min(dest_align, src_align);
+    auto llfn = bcx_ccx(bcx).intrinsics.get("llvm.memmove.p0i8.p0i8.i32");
+    auto lldestptr_i8 = bcx.build.PointerCast(lldestptr,
+                                              tc::T_ptr(tc::T_i8()));
+    auto llsrcptr_i8 = bcx.build.PointerCast(llsrcptr,
+                                             tc::T_ptr(tc::T_i8()));
+    bcx.build.Call(llfn, ~[lldestptr_i8, llsrcptr_i8, llsz, tc::C_uint(align),
+                           tc::C_bool(false)]);
+}
+
 // If "cast" is true, casts dest appropriately before the store.
 fn store_imm(&@block_ctxt bcx, &dest dest, ValueRef llsrc, bool cast)
         -> @block_ctxt {
@@ -170,22 +202,9 @@ fn store_ptr(&@block_ctxt bcx, &dest dest, ValueRef llsrcptr) -> @block_ctxt {
         *box = some(llsrcptr);
       }
       dst_copy(?lldestptr) | dst_move(?lldestptr) {
-        auto lldestty = llelement_type(trans::val_ty(llsrcptr));
         auto llsrcty = llelement_type(trans::val_ty(llsrcptr));
-        auto dest_align = llalign_of(bcx_ccx(bcx), lldestty);
-        auto src_align = llalign_of(bcx_ccx(bcx), llsrcty);
-        auto align = uint::min(dest_align, src_align);
-        auto llfn = bcx_ccx(bcx).intrinsics.get("llvm.memmove.p0i8.p0i8.i32");
-        auto lldestptr_i8 = bcx.build.PointerCast(lldestptr,
-                                                  tc::T_ptr(tc::T_i8()));
-        auto llsrcptr_i8 = bcx.build.PointerCast(llsrcptr,
-                                                 tc::T_ptr(tc::T_i8()));
-        bcx.build.Call(llfn,
-                       ~[lldestptr_i8,
-                         llsrcptr_i8,
-                         tc::C_uint(llsize_of(bcx_ccx(bcx), llsrcty)),
-                         tc::C_uint(align),
-                         tc::C_bool(false)]);
+        auto llsz = tc::C_uint(llsize_of(bcx_ccx(bcx), llsrcty));
+        memmove(bcx, lldestptr, llsrcptr, llsz);
         ret bcx;
       }
     }
@@ -194,6 +213,9 @@ fn store_ptr(&@block_ctxt bcx, &dest dest, ValueRef llsrcptr) -> @block_ctxt {
 
 // Allocates a value of the given LLVM size on either the task heap or the
 // shared heap.
+//
+// TODO: This should *not* use destination-passing style, because doing so
+// makes callers incur an extra load.
 tag heap { hp_task; hp_shared; }
 fn malloc(&@block_ctxt bcx, ValueRef lldest, heap heap,
           option[ValueRef] llcustom_size_opt) -> @block_ctxt {
@@ -287,18 +309,18 @@ fn trans_lit(&@block_ctxt cx, &dest dest, &ast::lit lit) -> @block_ctxt {
     ret bcx;
 }
 
-fn trans_binary(&@block_ctxt cx, &dest in_dest, ast::binop op,
+fn trans_binary(&@block_ctxt cx, &dest dest, &span sp, ast::binop op,
                 &@ast::expr lhs, &@ast::expr rhs) -> @block_ctxt {
     auto bcx = cx;
-    auto r = spill_alias(bcx, in_dest, ty::expr_ty(bcx_tcx(bcx), lhs));
-    bcx = r._0; auto dest = r._1;
-    bcx = trans_expr(bcx, dest, lhs);
-
-    r = mk_temp(bcx, ty::expr_ty(bcx_tcx(bcx), rhs));
-    bcx = r._0; auto rhs_tmp = r._1;
-    bcx = trans_expr(bcx, rhs_tmp, rhs);
-
-    ret bcx;    // TODO
+    alt (op) {
+      ast::add {
+        bcx = trans_vec::trans_concat(bcx, dest, sp,
+                                      ty::expr_ty(bcx_tcx(bcx), rhs), lhs,
+                                      rhs);
+      }
+      // TODO: Many more to add here.
+    }
+    ret bcx;
 }
 
 fn trans_log(&@block_ctxt cx, &span sp, int level, &@ast::expr expr)
@@ -408,7 +430,7 @@ fn trans_expr(&@block_ctxt bcx, &dest dest, &@ast::expr expr) -> @block_ctxt {
         ret trans_log(bcx, expr.span, level, operand);
       }
       ast::expr_binary(?op, ?lhs, ?rhs) {
-        ret trans_binary(bcx, dest, op, lhs, rhs);
+        ret trans_binary(bcx, dest, expr.span, op, lhs, rhs);
       }
       _ { fail "unhandled expr type in trans_expr"; }
     }
diff --git a/src/comp/middle/trans_vec.rs b/src/comp/middle/trans_vec.rs
new file mode 100644
index 00000000000..682e4eefad4
--- /dev/null
+++ b/src/comp/middle/trans_vec.rs
@@ -0,0 +1,217 @@
+// Translation of vector operations to LLVM IR, in destination-passing style.
+
+import back::abi;
+import lib::llvm::llvm;
+import llvm::ValueRef;
+import middle::trans;
+import middle::trans_common;
+import middle::trans_dps;
+import middle::ty;
+import syntax::ast;
+import syntax::codemap::span;
+import trans::alloca;
+import trans::block_ctxt;
+import trans::load_inbounds;
+import trans::new_sub_block_ctxt;
+import trans::struct_elt;
+import trans::type_of_or_i8;
+import trans_common::C_int;
+import trans_common::C_null;
+import trans_common::C_uint;
+import trans_common::T_int;
+import trans_common::T_ivec_heap;
+import trans_common::T_ivec_heap_part;
+import trans_common::T_opaque_ivec;
+import trans_common::T_ptr;
+import trans_dps::bcx_ccx;
+import trans_dps::bcx_tcx;
+import trans_dps::dest;
+import trans_dps::llsize_of;
+import trans_dps::mk_temp;
+
+import std::option::none;
+import std::option::some;
+import tc = middle::trans_common;
+
+// Returns the length of an interior vector and a pointer to its first
+// element, in that order.
+//
+// TODO: We can optimize this in the cases in which we statically know the
+// vector must be on the stack.
+fn get_len_and_data(&@block_ctxt cx, ty::t t, ValueRef llvecptr)
+        -> tup(@block_ctxt, ValueRef, ValueRef) {
+    auto bcx = cx;
+
+    // If this interior vector has dynamic size, we can't assume anything
+    // about the LLVM type of the value passed in, so we cast it to an
+    // opaque vector type.
+    auto unit_ty = ty::sequence_element_type(bcx_tcx(bcx), t);
+    auto v;
+    if (ty::type_has_dynamic_size(bcx_tcx(bcx), unit_ty)) {
+        v = bcx.build.PointerCast(llvecptr, T_ptr(T_opaque_ivec()));
+    } else {
+        v = llvecptr;
+    }
+
+    auto llunitty = type_of_or_i8(bcx, unit_ty);
+    auto stack_len = load_inbounds(bcx, v, ~[C_int(0),
+                                             C_uint(abi::ivec_elt_len)]);
+    auto stack_elem =
+        bcx.build.InBoundsGEP(v,
+                              ~[C_int(0), C_uint(abi::ivec_elt_elems),
+                                C_int(0)]);
+    auto on_heap =
+        bcx.build.ICmp(lib::llvm::LLVMIntEQ, stack_len, C_int(0));
+    auto on_heap_cx = new_sub_block_ctxt(bcx, "on_heap");
+    auto next_cx = new_sub_block_ctxt(bcx, "next");
+    bcx.build.CondBr(on_heap, on_heap_cx.llbb, next_cx.llbb);
+    auto heap_stub =
+        on_heap_cx.build.PointerCast(v, T_ptr(T_ivec_heap(llunitty)));
+    auto heap_ptr = load_inbounds(on_heap_cx, heap_stub,
+                                  ~[C_int(0),
+                                    C_uint(abi::ivec_heap_stub_elt_ptr)]);
+
+    // Check whether the heap pointer is null. If it is, the vector length
+    // is truly zero.
+
+    auto llstubty = T_ivec_heap(llunitty);
+    auto llheapptrty = struct_elt(llstubty, abi::ivec_heap_stub_elt_ptr);
+    auto heap_ptr_is_null =
+        on_heap_cx.build.ICmp(lib::llvm::LLVMIntEQ, heap_ptr,
+                              C_null(T_ptr(llheapptrty)));
+    auto zero_len_cx = new_sub_block_ctxt(bcx, "zero_len");
+    auto nonzero_len_cx = new_sub_block_ctxt(bcx, "nonzero_len");
+    on_heap_cx.build.CondBr(heap_ptr_is_null, zero_len_cx.llbb,
+                            nonzero_len_cx.llbb);
+    // Technically this context is unnecessary, but it makes this function
+    // clearer.
+
+    auto zero_len = C_int(0);
+    auto zero_elem = C_null(T_ptr(llunitty));
+    zero_len_cx.build.Br(next_cx.llbb);
+    // If we're here, then we actually have a heapified vector.
+
+    auto heap_len = load_inbounds(nonzero_len_cx, heap_ptr,
+                                  ~[C_int(0),
+                                    C_uint(abi::ivec_heap_elt_len)]);
+    auto heap_elem =
+        {
+            auto v = ~[C_int(0), C_uint(abi::ivec_heap_elt_elems),
+                       C_int(0)];
+            nonzero_len_cx.build.InBoundsGEP(heap_ptr,v)
+        };
+
+    nonzero_len_cx.build.Br(next_cx.llbb);
+
+    // Now we can figure out the length of |v| and get a pointer to its
+    // first element.
+
+    auto len =
+        next_cx.build.Phi(T_int(), ~[stack_len, zero_len, heap_len],
+                          ~[bcx.llbb, zero_len_cx.llbb,
+                            nonzero_len_cx.llbb]);
+    auto elem =
+        next_cx.build.Phi(T_ptr(llunitty),
+                          ~[stack_elem, zero_elem, heap_elem],
+                          ~[bcx.llbb, zero_len_cx.llbb,
+                            nonzero_len_cx.llbb]);
+    ret tup(next_cx, len, elem);
+}
+
+fn trans_concat(&@block_ctxt cx, &dest in_dest, &span sp, ty::t t,
+                &@ast::expr lhs, &@ast::expr rhs) -> @block_ctxt {
+    auto bcx = cx;
+
+    // TODO: Skip null if copying strings.
+    // TODO: Detect "a = a + b" and promote to trans_append.
+    // TODO: Detect "a + [ literal ]" and optimize to copying the literal
+    //       elements in directly.
+
+    // Translate the LHS and RHS. Pull out their length and data.
+    auto t = ty::expr_ty(bcx_tcx(bcx), lhs);
+    auto lhs_tmp = trans_dps::dest_alias(bcx_tcx(bcx), t);
+    bcx = trans_dps::trans_expr(bcx, lhs_tmp, lhs);
+    auto lllhsptr = trans_dps::dest_ptr(lhs_tmp);
+
+    auto rhs_tmp = trans_dps::dest_alias(bcx_tcx(bcx), t);
+    bcx = trans_dps::trans_expr(bcx, rhs_tmp, rhs);
+    auto llrhsptr = trans_dps::dest_ptr(rhs_tmp);
+
+    auto r0 = get_len_and_data(bcx, t, lllhsptr);
+    bcx = r0._0; auto lllhslen = r0._1; auto lllhsdata = r0._2;
+    r0 = get_len_and_data(bcx, t, llrhsptr);
+    bcx = r0._0; auto llrhslen = r0._1; auto llrhsdata = r0._2;
+
+    // Allocate the destination.
+    auto r1 = trans_dps::spill_alias(bcx, in_dest, t);
+    bcx = r1._0; auto dest = r1._1;
+
+    auto unit_t = ty::sequence_element_type(bcx_tcx(bcx), t);
+    auto unit_sz = trans_dps::size_of(bcx_ccx(bcx), sp, unit_t);
+
+    auto stack_elems_sz = unit_sz * abi::ivec_default_length;
+    auto lldestptr = trans_dps::dest_ptr(dest);
+    auto llunitty = trans::type_of(bcx_ccx(bcx), sp, unit_t);
+
+    // Decide whether to allocate the result on the stack or on the heap.
+    auto llnewlen = bcx.build.Add(lllhslen, llrhslen);
+    auto llonstack = bcx.build.ICmp(lib::llvm::LLVMIntULE, llnewlen,
+                                    C_uint(stack_elems_sz));
+    auto on_stack_bcx = new_sub_block_ctxt(bcx, "on_stack");
+    auto on_heap_bcx = new_sub_block_ctxt(bcx, "on_heap");
+    bcx.build.CondBr(llonstack, on_stack_bcx.llbb, on_heap_bcx.llbb);
+
+    // On-stack case.
+    auto next_bcx = new_sub_block_ctxt(bcx, "next");
+    trans::store_inbounds(on_stack_bcx, llnewlen, lldestptr,
+                          ~[C_int(0), C_uint(abi::ivec_elt_len)]);
+    trans::store_inbounds(on_stack_bcx, C_uint(stack_elems_sz), lldestptr,
+                          ~[C_int(0), C_uint(abi::ivec_elt_alen)]);
+    auto llonstackdataptr =
+        on_stack_bcx.build.InBoundsGEP(lldestptr,
+                                       ~[C_int(0),
+                                         C_uint(abi::ivec_elt_elems),
+                                         C_int(0)]);
+    on_stack_bcx.build.Br(next_bcx.llbb);
+
+    // On-heap case.
+    auto llheappartty = tc::T_ivec_heap(llunitty);
+    auto lldeststubptr =
+        on_heap_bcx.build.PointerCast(lldestptr, tc::T_ptr(llheappartty));
+    trans::store_inbounds(on_heap_bcx, C_int(0), lldeststubptr,
+                          ~[C_int(0), C_uint(abi::ivec_elt_len)]);
+    trans::store_inbounds(on_heap_bcx, llnewlen, lldeststubptr,
+                          ~[C_int(0), C_uint(abi::ivec_elt_alen)]);
+
+    auto llheappartptrptr =
+        on_heap_bcx.build.InBoundsGEP(lldeststubptr,
+                                      ~[C_int(0),
+                                        C_uint(abi::ivec_elt_elems)]);
+    auto llsizeofint = C_uint(llsize_of(bcx_ccx(bcx), tc::T_int()));
+    on_heap_bcx = trans_dps::malloc(on_heap_bcx, llheappartptrptr,
+                                    trans_dps::hp_shared,
+                                    some(on_heap_bcx.build.Add(llnewlen,
+                                                               llsizeofint)));
+    auto llheappartptr = on_heap_bcx.build.Load(llheappartptrptr);
+    trans::store_inbounds(on_heap_bcx, llnewlen, llheappartptr,
+                          ~[C_int(0), C_uint(abi::ivec_heap_elt_len)]);
+    auto llheapdataptr =
+        on_heap_bcx.build.InBoundsGEP(llheappartptr,
+                                      ~[C_int(0),
+                                        C_uint(abi::ivec_heap_elt_elems),
+                                        C_int(0)]);
+    on_heap_bcx.build.Br(next_bcx.llbb);
+
+    // Perform the memmove.
+    auto lldataptr =
+        next_bcx.build.Phi(T_ptr(llunitty),
+                           ~[llonstackdataptr, llheapdataptr],
+                           ~[on_stack_bcx.llbb, on_heap_bcx.llbb]);
+    trans_dps::memmove(next_bcx, lldataptr, lllhsdata, lllhslen);
+    trans_dps::memmove(next_bcx,
+                       next_bcx.build.InBoundsGEP(lldataptr, ~[lllhslen]),
+                       llrhsdata, llrhslen);
+
+    ret next_bcx;
+}
+
diff --git a/src/comp/rustc.rc b/src/comp/rustc.rc
index a64be9f1686..10e9cb80193 100644
--- a/src/comp/rustc.rc
+++ b/src/comp/rustc.rc
@@ -20,6 +20,7 @@ mod middle {
     mod trans_alt;
     mod trans_comm;
     mod trans_dps;
+    mod trans_vec;
     mod ty;
     mod ast_map;
     mod resolve;