Changeset 133

Timestamp:

11/13/07 04:47:28 (10 months ago)

Author:

Don Clugston

Message:

Factored out the expression simplification code. Duplicate symbols now get removed. SSE/SSE2 now uses simplified expressions (not tested, but works for the existing cases at least).

Files:

• trunk/blade/Blade.d (modified) (4 diffs)
• trunk/blade/BladeDemo.d (modified) (1 diff)
• trunk/blade/BladeRank.d (modified) (1 diff)
• trunk/blade/BladeSimplify.d (added)

trunk/blade/Blade.d

@@ -48 +48 @@
-private import blade.BladeUtil : wrapInQuotes, startsWith;
-private import blade.BladeRank;
+private import blade.BladeSimplify : simplifySyntaxTree, RevisedExpression;
-public import blade.CodegenX86 : generateCodeForAsmX87, generateCodeForSSE, MAX_X87_VECTORS, MAX_SSE_VECTORS;
-
-public:
+
+// FOR MIXIN: Generate code to evaluate the given vector expression.
+char [] vectorize(char [] expr)
+{
+    return "mixin(makeVectorCode(" ~ syntaxtreeof(expr) ~ "));";
+}        
+
+// Simplify the expression, categorise it, 
+// and dispatch to the appropriate code generator.
+char [] makeVectorCode(AbstractSyntaxTree tree)
+{
+    RevisedExpression revised = simplifySyntaxTree(tree);
+    
+    VecExpressionType exprType = categorizeExpression(tree);
+    if (exprType == VecExpressionType.SSE2Expression || exprType == VecExpressionType.SSE1Expression) {
+        return invokeSSE((exprType == VecExpressionType.SSE2Expression), tree, revised);
+    } else if (exprType == VecExpressionType.X87Expression) {
+        return invokeX87(tree);
+    } else {
+//        return "pragma(msg, " ~ wrapInQuotes(DCodeGenerator(tree)) ~ ");" ~ DCodeGenerator(tree);
+        return DCodeGenerator(tree);
+    }    
+}
+
-// These functions have the complete expression encoded in the template type.
-// One of these functions is instantiated for each expression.
@@ -77 +102 @@
-    mixin(generateCodeForAsmX87(typelist, ranklist, expr));
-}
+
+
+private:
-
-// ------------------------------------
@@ -171 +199 @@
-
-/// Generate code which will call the SSE/SSE2 code generation function
-
+, RevisedExpression revised
-{
-    char [] result = assertAllVectorLengthsEqual(tree);
-    result ~= assertAllVectorsAlign128(tree);
-    
-
+
+
+
+
-    // For SSE2, everything must be implicitly convertible to double.
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    }
-    result ~= ")(";
-    int firstVector = findVectorForLength(tree);
-    result ~= tree.symbolTable[firstVector].value ~ ".length";
-
-
-
-
-
-
+
+
-    return result ~ ");";
-}
@@ -275 +314 @@
-}
-
-
-// Simplify a vector expression
-//  - Use slicing distributive law: A[B..C] for expressions A,B,C
-//     where B and C are both rank 0, and A is rank 1, the slice can
-//     be moved to every vector inside A.
-//  - Convert A[]*B into B*A[] (assumes * is commutative,
-//      not valid for quaternions).
-//  - Use associativity of *: A*(B*C[]) == (A*B)*C[]
-//  - Use * distributive law over + and -. (Not strictly correct).
-// Convert -A*B into +(-A)*B whenever possible.
-// Combine all scalars into a single scalar.
-
-// Categorise the expression, and dispatch to the appropriate code generator.
-char [] makeVectorCode(AbstractSyntaxTree tree)
-{
-    int [] ranks=[];
-    for (int i=0; i<tree.symbolTable.length; ++i) {ranks~=tree.symbolTable[i].rank; }    
-    RevisedExpression e = simplifyVectorExpression(tree.expression, ranks);
-    
-    VecExpressionType exprType = categorizeExpression(tree);
-    if (exprType == VecExpressionType.SSE2Expression || exprType == VecExpressionType.SSE1Expression) {
-        return invokeSSE((exprType == VecExpressionType.SSE2Expression), tree);
-    } else if (exprType == VecExpressionType.X87Expression) {
-        return invokeX87(tree);
-    } else {
-//        return "pragma(msg, " ~ wrapInQuotes(DCodeGenerator(tree)) ~ ");" ~ DCodeGenerator(tree);
-        return DCodeGenerator(tree);
-    }    
-}
-
-char [] vectorize(char [] expr)
-{
-    return "mixin(makeVectorCode(" ~ syntaxtreeof(expr) ~ "));";
-}        

trunk/blade/BladeDemo.d

@@ -33 +33 @@
-
-    mixin(vectorize(" a   += d*2.01-z"));
-
-
+//
+//
-    
-    writefln("a=", a);

trunk/blade/BladeRank.d

@@ -325 +325 @@
-}
-
-char [] subexprSimplify(char [] expr, int [] rank, char [] mulexpr, char [] indexexpr)
-{
-    if (expr.length==1) {
-        int r = subexprRank(expr, rank);
-        char [] e = expr;
-        if(indexexpr.length>0) {
-            assert(r>0, "BLADE BUG: MISMATCHED INDEX " ~ expr ~ " " ~ indexexpr ~ " " ~ mulexpr);
-            e = " {" ~ expr ~ indexexpr ~ "} ";
-        }
-        if (mulexpr.length>1) {
-            // in this case, it's worth creating a new variable
-            return "( {" ~ mulexpr ~ "} *" ~ e ~ ")";
-        }
-        if (mulexpr.length>0) return "(" ~ mulexpr ~ "*" ~ e ~ ")";
-        return e;
-    }
-    // strip off the parentheses before simplifying
-    return exprSimplify(expr[1..$-1], rank, mulexpr, indexexpr);
-}
-
-/**
- * Rewrite the expression, taking advantage of distributivity of [] and
- * associativity of *. Additionally, we group all scalars together, whenever
- * possible.
- *
- * This process creates compound scalars and vectors, delineated by " {" and "} ".
- * They will be removed in a subsequent step.
- */
-char [] exprSimplify(char [] expr, int [] rank, char [] mulexpr, char [] indexexpr)
-{           
-    // Deal with ++ and --. Only for scalars
-    if (expr.length>2 && (expr[0..2]=="++" || expr[0..2]=="--")) {
-        return expr[0..2] ~ subexprSimplify(expr[2..$], rank, mulexpr, indexexpr);
-    }
-    if (expr.length>2 && (expr[$-2..$]=="++" || expr[$-2..$]=="--")) {
-        return subexprSimplify(expr[0..$-2], rank, mulexpr, indexexpr) ~ expr[$-2..$];
-    }
-    // Deal with unary operators
-    if (expr[0]=='-') {
-        // Fold unary minus into a multiply, if possible.
-        if (mulexpr.length>0) return subexprSimplify(expr[1..$], rank, "-" ~ mulexpr, indexexpr);
-        return "-" ~ subexprSimplify(expr[1..$], rank, mulexpr, indexexpr);
-    }
-    // Just remove unary plus.
-    if (expr[0]=='+') return subexprSimplify(expr[1..$], rank, mulexpr, indexexpr);
-   
-    int x = exprLength(expr);
-    int y = x+1;
-    assert(y < expr.length, expr);
-    // Deal with shifts, op=, and NCEG operators
-    while (expr[y+1]=='<' || expr[y+1]=='>' || expr[y+1]=='=') ++y;    
-
-    char [] op = expr[x+1..y+1];    
-    char [] left = expr[0..x+1];
-    char [] right = expr[y+1..$];
-    if (expr[x+1]=='[') right = expr[y+1..$-1]; // drop off the ']'.
-    int lrank = subexprRank(left, rank);
-    if (op=="[") {
-        // accumulate indexing and slicing operations
-        return subexprSimplify(left, rank, mulexpr, "[" ~ right ~ "]" ~ indexexpr);
-    }
-    int rrank = subexprRank(right, rank);
-    // Fold scalars together
-    if (op=="*") {
-        if (lrank==0) {
-            char [] m = left;
-            if (mulexpr.length>0) m = "(" ~ left ~ "*" ~ mulexpr ~ ")";
-            if (right.length > 1 && hasScalarMultiply(right[1..$-1], rank)) {
-                // opportunity for scalar folding
-                return subexprSimplify(right[1..$-1], rank, m, indexexpr);
-            } else {
-                if (m.length>1) m = " {" ~ m ~ "} ";
-                return "(" ~ m ~ "*" ~ subexprSimplify(right, rank, "", indexexpr) ~ ")";                
-            }
-            
-        } else if (rrank==0) {
-            char [] m = right;
-            if (mulexpr.length>0) m = "(" ~ mulexpr ~ "*" ~ right ~ ")";
-            if (left.length> 1 && hasScalarMultiply(left[1..$-1], rank)) {
-                return subexprSimplify(left, rank, m, indexexpr);
-            } else {                
-                if (m.length>1) m = " {" ~ m ~ "} ";
-                return "(" ~ m ~ "*" ~ subexprSimplify(left, rank, "", indexexpr) ~ ")";                
-            }
-        } // else it's matrix * matrix
-    }
-    if (op=="*=") {
-        if (rrank==0) {
-            char [] m = right; //subexprSimplify(right, rank, "", "");
-            if (mulexpr.length>0) m ~= "*" ~ mulexpr;
-            if (m.length>1)  m= " {" ~ m ~ "} ";
-            return "(" ~ subexprSimplify(left, rank, "", indexexpr)~ "*=" ~ m ~ ")";
-        }
-    }
-    return "(" ~ subexprSimplify(left, rank, mulexpr, indexexpr) ~ op ~ subexprSimplify(right, rank, mulexpr, indexexpr) ~ ")";
-}
-
-struct RevisedExpression {
-    char [] expr; // the revised expression using original variable names
-    char [][] compounds; // the compound variables
-    int [] rank; // rank of all of the compound variables
-    char [] used; // which of the original variables are used.
-}
-
-// revised expression, with unused symbols collapsed.
-// (so, for example, B+=D*F becomes A+=B*C).
-char [] removedUnusedSymbolsFromExpression(RevisedExpression e)
-{
-    char [] m = "";
-    char knt = 'A';
-    for (int i=0; i<e.used.length; ++i) {
-        if (e.used[i]!='-') {
-            m~=knt;
-            ++knt;
-        } else m~="@";
-    }
-    for (int i=0; i<e.compounds.length;++i) {
-        m~=knt; ++knt;
-    }
-   
-    char [] f = "";
-    for (int i=0; i<e.expr.length; ++i) {
-        char c = e.expr[i];
-        if (c>='A' && c<='Z') {
-            f ~= m[c-'A'];
-        } else f ~= c;
-    }
-    return f;
-}
-
-int indexRank(char [] s)
-{
-   int r=0;
-   int numbrack=0;
-   for(int i=1; i<s.length; ++i) {
-        if (s[i]==']') numbrack--;
-        if (s[i]=='[') {
-            if (numbrack==0) ++r;
-            numbrack++;
-        }
-        if (numbrack==0 && s[i]=='.' && s[i-1]=='.') {
-            // if it's a slice, it does not increase the rank
-             r--;
-        }
-   }
-   return r;
-}
-
-
-RevisedExpression simplifyVectorExpression(char [] expr, int [] rank)
-{
-    char [] s = exprSimplify(expr, rank, "", "");
-    if (s.length>1) s = s[1..$-1]; // strip off ()
-    char [][] comp;
-    char [] used="";
-    for (int i=0; i<rank.length; ++i) used~="-";
-    int [] r;
-    char next = cast(char)('A' + rank.length);
-    char [] e = "";
-    for (int i=0; i<s.length; ++i) {
-        if (s[i]==' ') {
-            int k;
-            for (k=i+1; s[k]!=' '; ++k) {}
-            comp ~= s[i+2..k-1];
-            if (s[k-2]==']') {                
-                // it's a vector/matrix of some kind, with rank reduced
-                // by indices. Can't just use exprRank, because the []
-                // aren't wrapped by ().
-                r ~= rank[s[i+2]-'A'] - indexRank(s[i+2..k-1]);
-            } else {
-                // it's a scalar expression. Note that it could involve
-                // a vector expression.
-                r~=0; 
-            }
-            e ~= next;
-            ++next;
-            i = k;
-        } else {
-            e ~= s[i];
-            if (s[i]>='A' && s[i]<='Z') used[s[i]-'A']=s[i];
-        }
-    }
-    return RevisedExpression(e, comp, r, used);
-}
-
-unittest {
-   
-    assert(exprSimplify("A+=(((D[E])*B)[E])", [1,0,3,3,0,0],"","")=="(A+=(B* {D[E][E]} ))");
-    assert(exprSimplify("A+=(B*((C[B])[B..E]))", [1,0,3,3,0,0],"","")=="(A+=(B* {C[B][B..E]} ))");
-    assert(exprSimplify("A*=(B*C)", [1,0,0],"","")== "(A*= {(B*C)} )");
-    assert(exprSimplify("A=((B*C)-D)", [1,1,0,1],"","")=="(A=((C*B)-D))");
-
-    RevisedExpression e = simplifyVectorExpression("A+=(((D[B])*C)[B])", [2,0,0,4]);
-    assert(e.expr == "A+=(C*E)");
-    assert(e.rank[0]==2);
-    assert(e.compounds[0]=="D[B][B]");
-    assert(e.used=="A-C-"); 
-    assert(removedUnusedSymbolsFromExpression(e)=="A+=(B*C)");
-}