Changeset 130

Show
Ignore:
Timestamp:
11/08/07 15:42:46 (1 year ago)
Author:
Don Clugston
Message:

BladeRank? implements scalar value folding (not in generated code yet).

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/blade/BladeRank.d

    r129 r130  
    133133        } 
    134134    } 
     135    assert(0, "BLADE BUG: " ~ s);    
    135136} 
    136137 
    …… 
    239240    assert(exprRank("C+=(A[B])", [3,0,2])==2); 
    240241    assert(exprRank("C~=(((A[B])[B])~C)", [3,0,2])==2); 
    241 } 
     242    assert(exprRank("((D[E])[E])+(-((C[B])[B..E]))", [1,0,2,3,0,0])==1); 
     243} 
     244 
     245// Return true if the entire expression contains a multiplucation by a scalar 
     246bool hasScalarMultiply(char [] expr, int [] rank) 
     247{ 
     248    if (expr.length>2 && (expr[0..2]=="++" || expr[0..2]=="--" || expr[$-2..$]=="++" || expr[$-2..$]=="--")) { 
     249        return false; 
     250    } 
     251    if (expr[0]=='+' || expr[0]=='-') return hasScalarMultiply(expr[1..$], rank); 
     252     
     253    int x = exprLength(expr); 
     254    int y = x+1; 
     255    assert(y < expr.length, "BLADE BUG:" ~ expr); 
     256    // Deal with shifts, op=, and NCEG operators 
     257    while (expr[y+1]=='<' || expr[y+1]=='>' || expr[y+1]=='=') ++y;     
     258 
     259    char [] op = expr[x+1..y+1];     
     260    char [] left = expr[0..x+1]; 
     261    char [] right = expr[y+1..$]; 
     262    if (op=="[") { 
     263        // (A)[C] can still have a multiply by scalar, if A contains a 
     264        // multiply. 
     265        if (left.length==1) return false; 
     266        return hasScalarMultiply(left[1..$], rank); 
     267    } 
     268    if (op=="/") return true; 
     269    if (op!="*" && op!="/") { 
     270        if (left.length==1 || right.length==1) return false;  
     271        // (A+B) could contain a multiply by scalar, if both A and B 
     272        // contain multiplies. 
     273        return hasScalarMultiply(left[1..$-1], rank) && hasScalarMultiply(right[1..$-1], rank); 
     274    } 
     275    // it's not true for matrix*matrix multiplies. 
     276    if (subexprRank(left, rank)==0) return true; 
     277    return subexprRank(right, rank) == 0; 
     278} 
     279 
     280unittest { 
     281 assert(hasScalarMultiply("(A*B)+(B*C)",[1,0,1])); 
     282 assert(!hasScalarMultiply("(A*B)-(C*C)",[1,0,1])); 
     283 assert(!hasScalarMultiply("A+(B*C)",[1,0,1])); 
     284 assert(hasScalarMultiply("(A/B)-((A*B)+(C*B))",[1,0,1])); 
     285 assert(!hasScalarMultiply("A[B]",[2,0])); 
     286 assert(!hasScalarMultiply("(C[B])[B..A]",[0,0,2]) ); 
     287} 
     288 
    242289 
    243290// Rank functions also using placeholder expressions 
    …… 
    276323} 
    277324 
    278 char [] subexprSimplify(char [] expr, int [] rank) 
    279 { 
    280     if (expr.length==1) return expr; 
     325char [] subexprSimplify(char [] expr, int [] rank, char [] mulexpr, char [] indexexpr) 
     326{ 
     327    if (expr.length==1) { 
     328        int r = subexprRank(expr, rank); 
     329        char [] e = expr; 
     330        if(indexexpr.length>0) { 
     331            assert(r>0, "BLADE BUG: MISMATCHED INDEX " ~ expr ~ " " ~ indexexpr ~ " " ~ mulexpr); 
     332            e = " {" ~ expr ~ indexexpr ~ "} "; 
     333        } 
     334        if (mulexpr.length>1) { 
     335            // in this case, it's worth creating a new variable 
     336            return "( {" ~ mulexpr ~ "} *" ~ e ~ ")"; 
     337        } 
     338        if (mulexpr.length>0) return "(" ~ mulexpr ~ "*" ~ e ~ ")"; 
     339        return e; 
     340    } 
    281341    // strip off the parentheses before simplifying 
    282     return "(" ~ exprSimplify(expr[1..$-1], rank) ~ ")"; 
    283 } 
    284  
    285 // TODO: Rewrite the expression, taking advantage of distributivity of [] and 
    286 // associativity of *. 
    287 char [] exprSimplify(char [] expr, int [] rank) 
    288 {     
    289     // BUG: also need to deal with comma, ?:, &&, ||, is, !is, in,  
    290     // unary &, unary ! 
    291          
    292     // Deal with ++ and --. 
     342    return exprSimplify(expr[1..$-1], rank, mulexpr, indexexpr); 
     343} 
     344 
     345/** 
     346 * Rewrite the expression, taking advantage of distributivity of [] and 
     347 * associativity of *. Additionally, we group all scalars together, whenever 
     348 * possible. 
     349 * 
     350 * This process creates compound scalars and vectors, delineated by " {" and "} ". 
     351 * They will be removed in a subsequent step. 
     352 */ 
     353char [] exprSimplify(char [] expr, int [] rank, char [] mulexpr, char [] indexexpr) 
     354{            
     355    // Deal with ++ and --. Only for scalars 
    293356    if (expr.length>2 && (expr[0..2]=="++" || expr[0..2]=="--")) { 
    294         return expr[0..2] ~ subexprSimplify(expr[2..$], rank); 
     357        return expr[0..2] ~ subexprSimplify(expr[2..$], rank, mulexpr, indexexpr); 
    295358    } 
    296359    if (expr.length>2 && (expr[$-2..$]=="++" || expr[$-2..$]=="--")) { 
    297         return subexprSimplify(expr[0..$-2], rank) ~ expr[$-2..$]; 
     360        return subexprSimplify(expr[0..$-2], rank, mulexpr, indexexpr) ~ expr[$-2..$]; 
    298361    } 
    299362    // Deal with unary operators 
    300     if (expr[0]=='+' || expr[0]=='-') return subexprSimplify(expr[1..$], rank); 
     363    if (expr[0]=='-') { 
     364        // Fold unary minus into a multiply, if possible. 
     365        if (mulexpr.length>0) return subexprSimplify(expr[1..$], rank, "-" ~ mulexpr, indexexpr); 
     366        return "-" ~ subexprSimplify(expr[1..$], rank, mulexpr, indexexpr); 
     367    } 
     368    // Just remove unary plus. 
     369    if (expr[0]=='+') return subexprSimplify(expr[1..$], rank, mulexpr, indexexpr); 
    301370    
    302371    int x = exprLength(expr); 
    303372    int y = x+1; 
     373    assert(y < expr.length, expr); 
    304374    // Deal with shifts, op=, and NCEG operators 
    305375    while (expr[y+1]=='<' || expr[y+1]=='>' || expr[y+1]=='=') ++y;     
    …… 
    311381    int lrank = subexprRank(left, rank); 
    312382    if (op=="[") { 
    313         // TODO: 
    314         // We know that 'right' is a 100% scalar. We only need to deal with 'left' 
    315         // We already know that left is a vector or matrix. 
    316         // where I, J, K are scalars: 
    317         // (X*I)[K]  -->  I*(X[K])   where X is any tensor expression 
    318         // (I*X)[K]  -->  I*(X[K]) 
    319         //  
    320         return subexprSimplify(left, rank) ~ "[" ~ right ~ "]"; 
    321     } 
    322     //TODO: 
    323     return subexprSimplify(left, rank) ~ op ~ subexprSimplify(right, rank); 
    324 } 
    325  
    326 unittest { 
    327      assert(exprSimplify("A+=((B++)*(C[B..B]))", [1,0,1])=="A+=((B++)*(C[B..B]))"); 
    328 } 
     383        // accumulate indexing and slicing operations 
     384        return subexprSimplify(left, rank, mulexpr, "[" ~ expr ~ "]" ~ indexexpr); 
     385    } 
     386    int rrank = subexprRank(right, rank); 
     387    // Fold scalars together 
     388    if (op=="*") { 
     389        if (lrank==0) { 
     390            char [] m = left; 
     391            if (mulexpr.length>0) m = "(" ~ left ~ "*" ~ mulexpr ~ ")"; 
     392            if (right.length > 1 && hasScalarMultiply(right[1..$-1], rank)) { 
     393                // opportunity for scalar folding 
     394                return subexprSimplify(right[1..$-1], rank, m, indexexpr); 
     395            } else { 
     396                if (m.length>1) m = " {" ~ m ~ "} "; 
     397                return "(" ~ m ~ "*" ~ subexprSimplify(right, rank, "", indexexpr) ~ ")";                 
     398            } 
     399             
     400        } else if (rrank==0) { 
     401            char [] m = right; 
     402            if (mulexpr.length>0) m = "(" ~ mulexpr ~ "*" ~ right ~ ")"; 
     403            bool b = hasScalarMultiply(left[1..$-1], rank); 
     404            if (left.length> 1 && hasScalarMultiply(left[1..$-1], rank)) { 
     405                return subexprSimplify(left, rank, m, indexexpr); 
     406            } else {                 
     407                if (m.length>1) m = " {" ~ m ~ "} "; 
     408                return "(" ~ m ~ "*" ~ subexprSimplify(left, rank, "", indexexpr) ~ ")";                 
     409            } 
     410        } // else it's matrix * matrix 
     411    } 
     412    if (op=="*=") { 
     413        if (rrank==0) { 
     414            char [] m = right; //subexprSimplify(right, rank, "", ""); 
     415            if (mulexpr.length>0) m ~= "*" ~ mulexpr; 
     416            if (m.length>1)  m= " {" ~ m ~ "} "; 
     417            return "(" ~ subexprSimplify(left, rank, "", indexexpr)~ "*=" ~ m ~ ")"; 
     418        } 
     419    } 
     420    return "(" ~ subexprSimplify(left, rank, mulexpr, indexexpr) ~ op ~ subexprSimplify(right, rank, mulexpr, indexexpr) ~ ")"; 
     421} 
     422 
     423struct RevisedExpression { 
     424    char [] expr; // the revised expression 
     425    char [][] compounds; // the compound variables 
     426    int [] rank; // rank of all of the compound variables 
     427} 
     428 
     429RevisedExpression simplifyVectorExpression(char [] expr, int [] rank) 
     430{ 
     431    char [] s = exprSimplify(expr, rank, "", ""); 
     432    if (s.length>1) s = s[1..$-1]; // strip off () 
     433    char [][] comp; 
     434    char [] used=""; 
     435    int [] r; 
     436    char next = cast(char)('A' + rank.length); 
     437    char [] e = ""; 
     438    for (int i=0; i<s.length; ++i) { 
     439        if (s[i]==' ') { 
     440            int k; 
     441            for (k=i+1; s[k]!=' '; ++k) {} 
     442            comp ~= s[i+2..k-1]; 
     443            // Can't just use exprRank, because the [] aren't wrapped by (). 
     444            if (s[k-2]==']') { 
     445                // it's a vector/matrix of some kind, with indexes. 
     446                r~=100; // BUG - not correct 
     447            } else { 
     448                // it's a scalar expression. Note that it could involve 
     449                // a vector expression. 
     450                r~=0;  
     451            } 
     452            e ~= next; 
     453            ++next; 
     454            i = k; 
     455        } else e ~= s[i]; 
     456    } 
     457    return RevisedExpression(e, comp, r); 
     458} 
     459 
     460unittest { 
     461     assert(exprSimplify("A+=(((D[E])*B)[E])", [1,0,3,3,0,0],"","")=="(A+=(B* {D[D[E]][((D[E])*B)[E]]} ))"); 
     462     assert(exprSimplify("A+=(B*((C[B])[B..E]))", [1,0,3,3,0,0],"","")=="(A+=(B* {C[C[B]][(C[B])[B..E]]} ))"); 
     463     assert(exprSimplify("A*=(B*C)", [1,0,0],"","")== "(A*= {(B*C)} )"); 
     464    
     465    RevisedExpression e = simplifyVectorExpression("A+=(((D[E])*B)[E])", [1,0,3,3,0, 0]); 
     466    assert(e.expr == "A+=(B*G)"); 
     467      
     468//    char [] q = e.expr ~\n ~ e.compounds[0] ~\n;    
     469//    assert(0, q); 
     470} 

  • trunk/blade/SyntaxTree.d

    r129 r130  
    362362    assert(mixin(mixin_getPrecedence("A[B]=E+F"))=="(A[B])=(E+F)"); 
    363363    assert(mixin(mixin_getPrecedence("A+=B[E]"))=="A+=(B[E])"); 
    364     assert(mixin(mixin_getPrecedence("A[$]=A[E]+F"))=="(A[$])=((A[E])+F)"); 
     364    assert(mixin(mixin_getPrecedence("A[B][$]=A[E]+F"))=="((A[B])[$])=((A[E])+F)"); 
    365365    assert(mixin(mixin_getPrecedence("G-=A[B][C..B^D][D]*E+F"))=="G-=(((((A[B])[C..(B^D)])[D])*E)+F)"); 
    366366    assert(mixin(mixin_getPrecedence("E=A[B,C/D]*F"))=="E=((A[B,(C/D)])*F)");