Mercurial > projects > ldc

changeset 1633:5c0cebff9be8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Improve array append performance. Actually use the appropriate runtime function, instead of just growing the array by one!
author Christian Kamm <kamm incasoftware de>
date Sun, 14 Feb 2010 10:11:05 +0100
parents 8c37dcd7cfde
children 9cc791423e20
files gen/arrays.cpp gen/arrays.h gen/runtime.cpp gen/toir.cpp tango-0.99.9.patch
diffstat 5 files changed, 95 insertions(+), 31 deletions(-) [+]
line wrap: on
line diff
--- a/gen/arrays.cpp	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/arrays.cpp	Sun Feb 14 10:11:05 2010 +0100
@@ -474,7 +474,7 @@
 
     // build dims
     LLValue* dimsArg = DtoArrayAlloca(Type::tsize_t, ndims, ".newdims");
-    LLValue* firstDim = NULL; 
+    LLValue* firstDim = NULL;
     for (size_t i=0; i<ndims; ++i)
     {
         LLValue* dim = dims[i]->getRVal();
@@ -532,30 +532,29 @@
 }
 
 //////////////////////////////////////////////////////////////////////////////////////////
-DSliceValue* DtoCatAssignElement(DValue* array, Expression* exp)
+void DtoCatAssignElement(Type* arrayType, DValue* array, Expression* exp)
 {
     Logger::println("DtoCatAssignElement");
     LOG_SCOPE;
 
     assert(array);
 
-    LLValue* idx = DtoArrayLen(array);
-    LLValue* one = DtoConstSize_t(1);
-    LLValue* len = gIR->ir->CreateAdd(idx,one,"tmp");
-
-    DValue* newdim = new DImValue(Type::tsize_t, len);
-    DSliceValue* slice = DtoResizeDynArray(array->getType(), array, newdim);
+    DValue *expVal = exp->toElem(gIR);
+    LLValue *valueToAppend;
+    if (expVal->isLVal())
+        valueToAppend = expVal->getLVal();
+    else {
+        valueToAppend = DtoAlloca(expVal->getType(), ".appendingElementOnStack");
+        DtoStore(expVal->getRVal(), valueToAppend);
+    }
 
-    LLValue* ptr = slice->ptr;
-    ptr = llvm::GetElementPtrInst::Create(ptr, idx, "tmp", gIR->scopebb());
-
-    DValue* dptr = new DVarValue(exp->type, ptr);
+    LLFunction* fn = LLVM_D_GetRuntimeFunction(gIR->module, "_d_arrayappendcT");
+    LLSmallVector<LLValue*,3> args;
+    args.push_back(DtoTypeInfoOf(arrayType));
+    args.push_back(DtoBitCast(array->getLVal(), getVoidPtrType()));
+    args.push_back(DtoBitCast(valueToAppend, getVoidPtrType()));
 
-    DValue* e = exp->toElem(gIR);
-
-    DtoAssign(exp->loc, dptr, e);
-
-    return slice;
+    gIR->CreateCallOrInvoke(fn, args.begin(), args.end(), ".appendedArray");
 }
 
 //////////////////////////////////////////////////////////////////////////////////////////
@@ -980,7 +979,7 @@
     else if (totype->ty == Tsarray) {
         if (Logger::enabled())
             Logger::cout() << "to sarray" << '\n';
-        
+
         size_t tosize = ((TypeSArray*)totype)->dim->toInteger();
 
         if (fromtype->ty == Tsarray) {
@@ -1004,9 +1003,9 @@
             size_t i = (tosize * totype->nextOf()->size() - 1) / fromtype->nextOf()->size();
             DConstValue index(Type::tsize_t, DtoConstSize_t(i));
             DtoArrayBoundsCheck(loc, u, &index, false);
-            
+
             rval = DtoArrayPtr(u);
-            rval = DtoBitCast(rval, getPtrToType(tolltype));            
+            rval = DtoBitCast(rval, getPtrToType(tolltype));
         }
     }
     else if (totype->ty == Tbool) {
--- a/gen/arrays.h	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/arrays.h	Sun Feb 14 10:11:05 2010 +0100
@@ -24,7 +24,7 @@
 DSliceValue* DtoNewMulDimDynArray(Loc& loc, Type* arrayType, DValue** dims, size_t ndims, bool defaultInit=true);
 DSliceValue* DtoResizeDynArray(Type* arrayType, DValue* array, DValue* newdim);
 
-DSliceValue* DtoCatAssignElement(DValue* arr, Expression* exp);
+void DtoCatAssignElement(Type* type, DValue* arr, Expression* exp);
 DSliceValue* DtoCatAssignArray(DValue* arr, Expression* exp);
 DSliceValue* DtoCatArrays(Type* type, Expression* e1, Expression* e2);
 DSliceValue* DtoCatArrayElement(Type* type, Expression* exp1, Expression* exp2);
--- a/gen/runtime.cpp	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/runtime.cpp	Sun Feb 14 10:11:05 2010 +0100
@@ -326,6 +326,17 @@
         llvm::Function::Create(fty, llvm::GlobalValue::ExternalLinkage, fname2, M);
     }
 
+    // void* _d_arrayappendcT(TypeInfo ti, void* array, void* element)
+    {
+        llvm::StringRef fname("_d_arrayappendcT");
+        std::vector<const LLType*> types;
+        types.push_back(typeInfoTy);
+        types.push_back(voidPtrTy);
+        types.push_back(voidPtrTy);
+        const llvm::FunctionType* fty = llvm::FunctionType::get(rt_array(byteTy), types, false);
+        llvm::Function::Create(fty, llvm::GlobalValue::ExternalLinkage, fname, M);
+    }
+
     // Object _d_allocclass(ClassInfo ci)
     {
         llvm::StringRef fname("_d_allocclass");
--- a/gen/toir.cpp	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/toir.cpp	Sun Feb 14 10:11:05 2010 +0100
@@ -624,7 +624,7 @@
     // valid array ops would have been transformed by optimize
     if ((t1->ty == Tarray || t1->ty == Tsarray) &&
         (t2->ty == Tarray || t2->ty == Tsarray)
-       ) 
+       )
     {
         base->error("Array operation %s not recognized", base->toChars());
         fatal();
@@ -1013,7 +1013,7 @@
         return DtoBitCast(gep, DtoType(type));
     }
     else if (
-        e1->op == TOKstructliteral || 
+        e1->op == TOKstructliteral ||
         e1->op == TOKslice)
     {
         error("non-constant expression '%s'", toChars());
@@ -1138,7 +1138,7 @@
         // decide whether this function needs to be looked up in the vtable
         //
         bool vtbllookup = fdecl->isAbstract() || (!fdecl->isFinal() && fdecl->isVirtual());
-        
+
         // even virtual functions are looked up directly if super or DotTypeExp
         // are used, thus we need to walk through the this expression and check
         Expression* e = e1;
@@ -1150,7 +1150,7 @@
             else
                 break;
         }
-        
+
         //
         // look up function
         //
@@ -1237,12 +1237,12 @@
         arrptr = DtoGEP1(l->getRVal(),r->getRVal());
     }
     else if (e1type->ty == Tsarray) {
-        if(global.params.useArrayBounds) 
+        if(global.params.useArrayBounds)
             DtoArrayBoundsCheck(loc, l, r, false);
         arrptr = DtoGEP(l->getRVal(), zero, r->getRVal());
     }
     else if (e1type->ty == Tarray) {
-        if(global.params.useArrayBounds) 
+        if(global.params.useArrayBounds)
             DtoArrayBoundsCheck(loc, l, r, false);
         arrptr = DtoArrayPtr(l);
         arrptr = DtoGEP1(arrptr,r->getRVal());
@@ -1769,7 +1769,7 @@
 
     // class invariants
     if(
-        global.params.useInvariants && 
+        global.params.useInvariants &&
         condty->ty == Tclass &&
         !((TypeClass*)condty)->sym->isInterfaceDeclaration())
     {
@@ -1780,7 +1780,7 @@
     }
     // struct invariants
     else if(
-        global.params.useInvariants && 
+        global.params.useInvariants &&
         condty->ty == Tpointer && condty->nextOf()->ty == Tstruct &&
         (invdecl = ((TypeStruct*)condty->nextOf())->sym->inv) != NULL)
     {
@@ -2234,8 +2234,7 @@
     Type* e2type = e2->type->toBasetype();
 
     if (e2type == elemtype) {
-        DSliceValue* slice = DtoCatAssignElement(l,e2);
-        DtoAssign(loc, l, slice);
+        DtoCatAssignElement(e1type, l, e2);
     }
     else if (e1type == e2type) {
         DSliceValue* slice = DtoCatAssignArray(l,e2);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tango-0.99.9.patch	Sun Feb 14 10:11:05 2010 +0100
@@ -0,0 +1,55 @@
+Index: tango/core/rt/compiler/ldc/rt/lifetime.d
+===================================================================
+--- tango/core/rt/compiler/ldc/rt/lifetime.d	(revision 5368)
++++ tango/core/rt/compiler/ldc/rt/lifetime.d	(working copy)
+@@ -786,6 +786,7 @@
+     return *cast(long*)px;
+ }
+ 
+++/
+ 
+ /**
+  *
+@@ -849,10 +850,11 @@
+ 
+ 
+ /**
+- *
++ * Appends a single element to an array.
+  */
+-extern (C) byte[] _d_arrayappendcT(TypeInfo ti, ref byte[] x, ...)
++extern (C) byte[] _d_arrayappendcT(TypeInfo ti, void* array, void* element)
+ {
++    auto x = cast(byte[]*)array;
+     auto sizeelem = ti.next.tsize();            // array element size
+     auto info = gc_query(x.ptr);
+     auto length = x.length;
+@@ -879,16 +881,16 @@
+         assert(newcap >= newlength * sizeelem);
+         newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
+         memcpy(newdata, x.ptr, length * sizeelem);
+-        (cast(void**)(&x))[1] = newdata;
++        (cast(void**)x)[1] = newdata;
+     }
+   L1:
+-    byte *argp = cast(byte *)(&ti + 2);
++    byte *argp = cast(byte *)element;
+ 
+-    *cast(size_t *)&x = newlength;
++    *cast(size_t *)x = newlength;
+     x.ptr[length * sizeelem .. newsize] = argp[0 .. sizeelem];
+     assert((cast(size_t)x.ptr & 15) == 0);
+     assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
+-    return x;
++    return *x;
+ }
+ 
+ 
+@@ -1128,6 +1130,7 @@
+     return result;
+ }
+ 
++/+
+ 
+ /**
+  *