Changeset 167

Timestamp:

01/03/08 09:23:43 (8 months ago)

Author:

Don Clugston

Message:

Added the front end code generation for dot product (this is also the way forward for BLAS2 and BLAS3 operations). No backend codegen yet, although that should be relatively easy.

Files:

• trunk/blade/Blade.d (modified) (15 diffs)
• trunk/blade/BladeDemo.d (modified) (2 diffs)
• trunk/blade/BladeRank.d (modified) (2 diffs)
• trunk/blade/BladeSimplify.d (modified) (11 diffs)
• trunk/blade/BladeVisitor.d (modified) (1 diff)
• trunk/blade/CodegenX86.d (modified) (1 diff)

trunk/blade/Blade.d

@@ -13 +13 @@
-*
-* FEATURES:
-and multiplication
-
+slicing, and
+multiplication 
-*  - Generates either x87 asm code, SSE or SSE2 asm code or pure D, depending on
-*    the complexity of the expression, and the availability of inline asm.
@@ -25 +25 @@
-* FUTURE DIRECTIONS (in order of expected implementation):
-* - Dot product (which was present in BLADE 0.2).
-
-
-
+
+
-*
-* THEORY:
@@ -40 +39 @@
-* 0.2 - Support for a wider variety of expressions. Dot product, imaginary numbers, etc.
-* 0.3 - Based on string mixins. Most of the new features of 0.2 are gone, but SSE2 is added.
-
+
+
+
-*/
-
@@ -47 +48 @@
-public import blade.SyntaxTree : AbstractSyntaxTree, syntaxtreeof, AST, Symbol;
-private import blade.BladeUtil : enquote, itoa;
-
-
+, exprRank
+, remapCompounds
-private import blade.CodegenX86 : generateCodeForAsmX87, MAX_X87_VECTORS,
-                                 MAX_87_REALSCALARSPLUSTEMPORARIES,
-                                 generateCodeForSSE,  MAX_SSE_VECTORS;
+private import blade.BladeVisitor: expressionContainsAssignment;
-
-private import blade.PostfixX86 : makePostfixForX87;
-
-struct BladeStrided(T)
-{
-    T * data;     // Pointer to the first element
-}
-public:
-
@@ -79 +77 @@
-    if (revised.errorMessage.length>0)  return `static assert(0, "BLADE: ` ~ enquote(revised.errorMessage) ~ `");`;
-    VecExpressionType exprType = categorizeExpression(revised);
+    char [] result = generateAsserts(revised, (exprType == VecExpressionType.SSE2Expression || exprType == VecExpressionType.SSE1Expression));
+    debug(BladeFrontEnd) {
+        result ~= "// Simplified: " ~ revised.expression ~ \n;
+    }    
-    if (exprType == VecExpressionType.SSE2Expression || exprType == VecExpressionType.SSE1Expression) {
-invokeSSE((exprType == VecExpressionType.SSE2Expression), revised)
+result ~ invokeSSE((exprType == VecExpressionType.SSE2Expression), revised)~ ";"
-    } else if (exprType == VecExpressionType.X87Expression) {
-invokeX87(revised)
+result ~ invokeX87(revised) ~ ";"
-    } else {
-
+result ~ 
-    }    
-}
-
+// For a compound of a different dimensionality (eg a dot product), we may need
+// to calculate the result seperately.
+char [] makeVectorCodeForDimensionalCompound(char [] expression, AbstractSyntaxTree tree)
+{
+    // TODO:
+    return expression;    
+}
-
-// These functions have the complete expression encoded in the template type.
@@ -139 +148 @@
-    SSE1 = false;
-    X87 = false;
+}
+int wholerank = exprRank(tree.expression, tree.rank);
+
+if (wholerank==0 && expressionContainsAssignment(tree.expression)) {
+    return VecExpressionType.DExpression; // Scalar assignments always use inline D.
-}
-    int numvectors = 0;
@@ -192 +206 @@
-}
-
+
+// This is mainly a workaround for compiler bug #1125. Ideally both
+// pointer and stride would be stored together.
+struct BladeStrided(T)
+{
+    T * data;     // Pointer to the first element
+}
+
-//-------------------------------------------------------
-//                Invoker functions
@@ -203 +225 @@
-char [] invokeX87(RevisedExpression tree)
-{
-assertAllVectorLengthsEqual(tree)
+""
-    char [] stridelist="";
-    char [] alltypes="";
@@ -272 +294 @@
-    int firstVector = findVectorForLength(tree);
-    return result ~ getValueForSymbol(tree.mapping[firstVector], tree) ~ ".length" 
-
+
+
+
+
+
+
+
+
-}
-
-/// Generate code which will call the SSE/SSE2 code generation function
-char [] invokeSSE(bool SSE2, RevisedExpression tree)
-
-
-
-
-
-
+
+
-    // For SSE2, everything must be implicitly convertible to double.
-    char [] vals;
@@ -303 +328 @@
-    result ~= vals;
-
-;
+
-}
-
@@ -399 +424 @@
-        if (comp[$-1]!=']') { // simple compound expression
-            foreach(d; comp) {
+                if (d=='{') assert(0, "BLADE ICE");
-                if (d>='A' && d<='Z') v ~= tree.symbolTable[d-'A'].value;
-                else v ~= d;
@@ -468 +494 @@
-}
-
+
+char [] invokeNestedExpression(char [] expr, Symbol[] symbolTable)
+{
+    char [] ranks;
+    for (int i=0; i<symbolTable.length; ++i) {
+        ranks ~= symbolTable[i].rank;
+    }
+    RevisedExpression revised = remapCompounds(expr, ranks, symbolTable);
+    
+    VecExpressionType exprType = categorizeExpression(revised);
+    if (exprType == VecExpressionType.SSE2Expression || exprType == VecExpressionType.SSE1Expression) {
+        return invokeSSE((exprType == VecExpressionType.SSE2Expression), revised);
+    } else if (exprType == VecExpressionType.X87Expression) {
+        return invokeX87(revised);
+    } else {
+        assert(0, "BLADE ICE: Nested D expressions are not yet supported");
+        return DCodeGenerator(revised);
+    }
+}
+
-char [] getValueForSymbol(char c, RevisedExpression tree, char [] firstIndexExpr="")
-{
@@ -476 +522 @@
-    if (c-'A'<tree.symbolTable.length) {
-        v = tree.symbolTable[c-'A'].value;
-
+      
-        char [] comp = tree.compounds[c-'A'-tree.symbolTable.length];
-        
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-            }
-        } else {
@@ -542 +598 @@
-}
-
-// Convert the compound expression str back into its values.
-char [] reconstituteCompoundExpression(char [] str, Symbol[] table)
-{
-    char [] v = "";
-    foreach(d; str) {
-        if (d>='A' && d<='Z') v ~= table[d-'A'].value;
-        else v ~= d;
-    }
-    return v;
-}
-
-// Generate inline D code for the expression
-char [] DCodeGenerator(RevisedExpression tree)
-{
-
-
-
-
-
-
+
+
+
+
+
+
+
+
-    foreach (c; tree.expression) {
-
+            
-            // restore all symbols into the expression
-            // If it's a vector, index it
@@ -571 +619 @@
-        } else result ~= c;
-    }
+    if (wholerank==0) return result ~ ";";   
-    return result ~ "; }";
-}

trunk/blade/BladeDemo.d

@@ -15 +15 @@
-// cdouble[] always remains aligned, even when sliced.
-
+float dot_product(float[] a, float[] b)
+{
+    return 0;
+}
-  
-void main()
-  
+
-    static z = [3.4, 565, 31.3, 0];
-    double [] a = new double[4];
@@ -53 +57 @@
-    mixin(vectorize("another[0..$,1]=6*a[0..2]"));
-
-
-
+
+
+
+
-
-    writefln("a=", a);
-}
-

trunk/blade/BladeRank.d

@@ -64 +64 @@
-/** Returns the (tensor) rank of the expression expr.
- * A negative number will be returned if an error is detected.
+ * TODO: Should warn of expressions with no effect (ie, with no =).
- *
- * Params:
@@ -226 +227 @@
-    // bug fixes:
-    assert(exprRank("(A[B..$,C])+=D", "2001")==1);
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+

trunk/blade/BladeSimplify.d

@@ -13 +13 @@
-*      where B and C are both rank 0, and A is rank 1 or more, the slice can
-*      be moved to every vector inside A.
-
+
+
+
+
-* (D) Expression standardisation 
-*    - Move multiplies to left: Convert A[]*B into B*A[] (assumes * is commutative,
-*      not valid for quaternions).
-*    - Convert C-A*B into C+(-A)*B whenever possible.
+*    - Remove unary minus where possible, eg convert A-(-B) into A+B.
-*
-* Author:
@@ -29 +33 @@
-public import blade.SyntaxTree : AbstractSyntaxTree, Symbol;
-private import blade.BladeVisitor;
-
-
+
-
-
-/// A simplified vector expression
-struct RevisedExpression {
+    char [] braceExpression; // the expression with compounds in braces
-    char [] expression; // the revised expression using new variable names
-                        // (so, for example, B+=(D-F) becomes A+=(B-C) ).
@@ -60 +64 @@
-    // Check for undefined symbols
-    if (err.length > 0) 
-
+"", 
-    else {
+        // Remove duplicate symbols, convert intrinsics
-        char [] expr2 = removeDuplicates(tree);
-        // Check for rank errors
-        int wholerank = exprRank(expr2, ranks);
-        if (wholerank<0)
-
-
+
+
+
+
-    }
-}
@@ -136 +143 @@
-}
-
-
-
-
+
+
+
+
-    char [][] comp;
-    char [] used = ""; // which of the old variables are used; gives the new mapping
@@ -146 +154 @@
-    char next = cast(char)('A' + rank.length);
-    char [] e = "";
-s
-s
+expr
+expr
-            int k;
-            int bracecount=1;
-            for (k=i+1; bracecount>0; ++k) {
-s
-s
+expr
+expr
-            }
-            --k;
-s
+expr
-            int newi = k;
-s.length-1 && s[i-1]=='(' && s
+expr.length-1 && expr[i-1]=='(' && expr
-                e = e[0..$-1]; // remove the last '('
-                newi=k+1; // don't add ')'
@@ -167 +175 @@
-                e ~= next;
-                ++next;
-s
-s
+expr
+expr
-                    // it's a vector/matrix of some kind, with rank reduced
-                    // by indices. Can't just use exprRank, because the []
-                    // aren't wrapped by ().
-s[i+1]-'A'] - indexRank(s
+expr[i+1]-'A'] - indexRank(expr
-                } else {
-                    // it's a scalar expression. Note that it could involve
@@ -181 +189 @@
-            i = newi;
-        } else {
-s
-s[i]>='A' && s[i]<='Z') used[s[i]-'A']=s
+expr
+expr[i]>='A' && expr[i]<='Z') used[expr[i]-'A']=expr
-        }
-    }
@@ -210 +218 @@
-        } else f ~= c;
-    }
-
+
+
+
+
+
+
+
-}
-
-unittest {    
-
+,[]
-    assert(e.rank=="202");
-    assert(e.compounds[0]=="D[B,B]");
@@ -441 +455 @@
-            ScalarFold left = doVisit(this_,args[0]);
-            ScalarFold right = doVisit(this_, args[1]);
-func ~ "(" ~ left.expr ~ "," ~ right.expr ~ ")
+"{" ~ func ~ "(" ~ left.expr ~ "," ~ right.expr ~ ")}
-        } else {
-            assert(0, "BLADE: Unsupported function");
@@ -554 +568 @@
-    ScalarFold f = beginVisit(ScalarFoldingVisitor(ranks), expr);
-    if (f.multiplier=="") return f.expr;
-"{" ~ f.multiplier ~ "}"
+f.multiplier
-    else return combineMulWithCompound(f.expr, f.multiplier);
-}
@@ -560 +574 @@
-unittest {
-    assert(foldScalars("A*=(B*C)", "100")=="A*={(B*C)}");
-{(d(A,A))*(d(A,A))}
+({d(A,A)})*({d(A,A)})
-    assert(foldScalars("A-(B*C)", "101")=="A+(C*{(-B)})");
-    assert(foldScalars("A-(B*(-C))", "101")=="A+(C*{(-(-B))})");

trunk/blade/BladeVisitor.d

@@ -132 +132 @@
-    return (a.length==1)? a : "(" ~ a ~ ")";
-}
+
+// Return true if this expression contains an assignment.
+bool expressionContainsAssignment(char [] expr)
+{
+    // BUG: also need to deal with comma, ?:, &&, ||, is, !is, in, 
+    // unary &, unary !
+    if (expr.length>1 && expr[0]=='(') expr = expr[1..$-1];
+    else if (expr.length==1 && ((expr[0]>='A' && expr[0]<='Z') || expr[0]=='$')){
+        return false;
+    }
+    if (expr.length>3 && (expr[0]>='a' && expr[1]<='z') && expr[1]=='(') { // function
+        return false;
+    }
+    if (expr.length>2 && (expr[0..2]=="++" || expr[0..2]=="--")) {
+        return false;
+    }
+    if (expr.length>1 && (expr[0]=='+' || expr[0]=='-')) {
+        return false;
+    }
+    if (expr.length>2 && (expr[$-2..$]=="++" || expr[$-2..$]=="--")) {
+        return false; // BUG: actually this is an assignment
+    }
+    int x = exprLength(expr);
+    int y = x+1;
+    assert(y < expr.length, "BLADE ICE:" ~ expr);
+    // Deal with shifts, op=, and NCEG operators
+    if (expr[y+1]=='<' || expr[y+1]=='>') return false;
+    if (expr[y]=='=' && expr[y+1]=='=') return false;
+    if (expr[y]=='=') return true;
+    if (expr[y+1]!='=') return false;
+    if (expr[y]=='<' || expr[y]=='<' || expr[y]=='!') return false;
+    return true;
+}

trunk/blade/CodegenX86.d

@@ -289 +289 @@
-char [] generateCodeForAsmX87(int numStrides, Values...)(char [] postfixOperations)
-{
+// Because of compiler bug #1125, no structs can be stored in the 'values' tuple.
+// Thus, lengths and strides must be stored seperately from vector pointers.
-    char [] ranklist;
-    char [][] typelist;