root/trunk/blade/PostfixX86.d

//  Written in the D programming language 1.0
/**
* BLADE  -- Basic Linear Algebra D Expressions
*
* Given an expression string of the form "A+(B*C)*D", and a ranklist string
* the entries of which correspond to A, B, C, ...,
* values being'0'=scalar, '1'=vector, '2'=matrix.
* This string is converted to postfix, applying simple X86-specific optimisations.
*
* The elements of the postfix string may be:
*  ABC          a variable or constant, to be pushed onto the stack
*  0            the literal zero (used to initialize a dot product, for example)
*  *+-/         ST(0)*ST(1), ST(0)+ST(1), ST(0)-ST(1), ST(0)/ST(1) and pop stack
*  _            ST(1)-ST(0) and pop stack
*  =            store ST(0) and pop stack
*  ,            duplicate stack top (so ,* means ST=ST*ST, ,+ means ST*=2)
*  a            abs
*  n            unary negation
*  m            ST(0) = max(ST(0), ST(1))
*  u            ST(1) = min(ST(0), ST(1))
*  q            sqrt
*  1            the literal one (used to initialize a product, for example)
*
*  NOT YET IMPLEMENTED:
*  scel         sin, cos, exp, log
*
* Unassigned lower case letters: bdfghijkoprtvwxyz
*/

module blade.PostfixX86;
private import blade.BladeVisitor;

public:
/// Converts an infix string into postfix.
/// Apply x87-specific optimisations during the conversion.
char [] makePostfixForX87(char [] operations, char [][] typelist, char[] ranklist)
{
    return beginVisit(X87PostfixVisitor(typelist, ranklist), operations);
}

/// Converts an infix string into postfix.
/// Apply SSE/SSE2-specific optimisations during the conversion.
char [] makePostfixForSSE(char [] operations, char [] ranklist)
{
    return beginVisit(SSEPostfixVisitor(ranklist), operations);
}

private:
// ------------------------------------------------
//   Convert infix string to postfix
// ------------------------------------------------

struct X87PostfixVisitor {
    alias typeof(*this) This;
    alias char [] ReturnType;
    char [][] typelist;
    char [] ranklist;
static:
    ReturnType onVisitSymbol(This this_, char [] sym) {
        return sym;
    }
    ReturnType onVisitFunction(This this_, char [] func, char [][] args) {
        char [] left = doVisit(this_,args[0]);
        switch(func) {
        case "dot":
            char [] right = doVisit(this_, args[1]);
            if (left==right) return "0" ~ left ~ ",*+";
            return "0" ~ left ~ right ~ "*+";
        case "prod":
            return "1" ~ left ~ "*";
        case "sum":  return "0" ~ left ~ "+";
//        case "max":  return left ~ "m";
//        case "min":  return left ~ "u";
        case "abs":  return left ~ "a";
        case "sqrt": return left ~ "q";
        default:     assert(0, "BLADE ICE: Unsupported");
        }
    }
    ReturnType onVisitPrefix(This this_, char [] op, char [] expr) {
        if (op=="-") return doVisit(this_, expr) ~ "n"; // unary minus
        assert(0, "BLADE ICE: Unsupported");
    }
    ReturnType onVisitPostfix(This this_, char [] op, char [] expr) {
        assert(0, "BLADE ICE: Unsupported");
    }
    ReturnType onVisitIndex(This this_, char [] base, char [][2][] slices) {
        assert(0, "BLADE ICE: Unsupported");
    }
    ReturnType onVisitBinaryOp(This this_, char [] op, char [] left, char [] right) {
        char [] first = doVisit(this_, left);
        char [] second;
        if (op.length==2 && op[1]=='=') { // +=, -=, *=, /=
            // Convert "A+=B" into "A=A+B"
            second = beginVisit(this_, left ~ op[0] ~ right);
            return second ~ first ~ "=";
        }
        second = doVisit(this_, right);
        if (op=="=") {
            return second ~ first ~ "=";
        }
        if (second == first) return first ~ "," ~ op;

        // x87 OPTIMISATION #1
        // On x87, fmul has a long latency, so we want to delay using the
        // result of a multiply. Since + is commutative, we can achieve this
        // by calculating the value with the multiply, before the other one.
        // We can also do the same thing with -, but we'll need to use fsubr
        // instead of fsub. We use _ to mean reversed subtraction.
        if (op=="+" || op=="-") {
            char [] oprvs = (op=="-")? "_" : op;
            if (second[second.length-1]=='*'&& first[first.length-1]!='*') {
               return second ~ first ~ oprvs;
            }
            // x87 OPTIMISATION #2
            // When an operation is performed between a real[] and a non-real[],
            // we want to have the real[] being the one which is loaded first.
            if (second.length==1 && this_.typelist[second[0]-'A']=="real" && this_.ranklist[second[0]-'A']=='1') {
                   return second ~ first ~ oprvs;
            }
        }
        return first ~ second ~ op;
    }
}


unittest {
assert(makePostfixForX87("A=B", ["double", "double"],"11")=="BA=");
assert(makePostfixForX87("(B*C)+A", ["double", "float", "float"],"111")=="BC*A+");
assert(makePostfixForX87("(B*C)+A", ["real", "float", "float"],"111")=="ABC*+");
assert(makePostfixForX87("A-(B*C)", ["double", "float", "float"],"100")=="BC*A_");
assert(makePostfixForX87("(B*C)-A", ["float", "float", "float"],"100")=="BC*A-");
assert(makePostfixForX87("(B*C)-A", ["real", "float", "float"],"100")=="ABC*_");
assert(makePostfixForX87("C+=((B*C)-A)", ["real", "float", "float"],"101")=="CABC*_+C=");
assert(makePostfixForX87("C-=((B*C)-A)", ["real", "float", "float"],"101")=="CABC*_-C=");
assert(makePostfixForX87("C-=(B*A)", ["real", "float", "float"],"101") =="BA*C_C=");
assert(makePostfixForX87("C-=(B*A)", ["real", "float", "real"],"101") =="BA*C_C=");
assert(makePostfixForX87("((A*B)+(C*D))+(E*F)", ["int", "int", "int"],"000")=="EF*AB*CD*++");
}

/// Converts an infix string into postfix.
/// Apply SSE/SSE2-specific optimisations during the conversion.
struct SSEPostfixVisitor {
    alias typeof(*this) This;
    alias char [] ReturnType;
    char [] ranklist;
static:
    ReturnType onVisitSymbol(This this_, char [] sym) {
        return sym;
    }
    ReturnType onVisitFunction(This this_, char [] func, char [][] args) {
        switch(func) {
        case "dot":
            char [] left = doVisit(this_,args[0]);
            char [] right = doVisit(this_, args[1]);
            if (left==right) return "0" ~ left ~ ",*+";
            return "0" ~ left ~ right ~ "*+";
        case "sum":
            return "0" ~ doVisit(this_, args[0]) ~ "+";
        case "abs": return doVisit(this_,args[0]) ~ "a";
        case "sqrt": return doVisit(this_,args[0]) ~ "q";
        case "prod":
            return "1" ~ doVisit(this_, args[0]) ~ "*";
        default:   assert(0, "BLADE ICE: Unsupported");
        }
    }
    ReturnType onVisitPrefix(This this_, char [] op, char [] expr) {
        if (op=="-") return doVisit(this_, expr) ~ "n"; // unary minus
        assert(0, "BLADE ICE: Unsupported");
    }
    ReturnType onVisitPostfix(This this_, char [] op, char [] expr) {
        assert(0, "BLADE ICE: Unsupported");
    }
    ReturnType onVisitIndex(This this_, char [] base, char [][2][] slices) {
        assert(0, "BLADE ICE: Unsupported");
    }
    ReturnType onVisitBinaryOp(This this_, char [] op, char [] left, char [] right) {
        char [] first = doVisit(this_, left);
        char [] second;
        if (op.length==2 && op[1]=='=') { // +=, -=, *=, /=
            // Convert "A+=B" into "A=A+B"
            second = beginVisit(this_, left ~ op[0] ~ right);
            return second ~ first ~ "=";
        }
        second = doVisit(this_, right);
        if (op=="=") {
            return second ~ first ~ "=";
        }
        if (second == first) return first ~ "," ~ op;

        // SSE OPTIMISATION #1
        // Multiplies have a long latency, so we want to delay using the
        // result of a multiply. Since + is commutative, we can achieve this
        // by calculating the value with the multiply, before the other one.
        if (op=="+") {
            if (second[second.length-1]=='*'&& first[first.length-1]!='*') {
               return second ~ first ~ op;
            }
        }
        if (op=="*") {
            // SSE OPTIMISATION #2
            // When an operation is performed between a vector and a scalar
            // we want to have the vector being the one which is loaded first.
            if (first.length==1 && this_.ranklist[first[0]-'A']=='0') {
                   return second ~ first ~ op;
            }
        }
        return first ~ second ~ op;
    }
}

unittest {
assert(makePostfixForSSE("A=B", "11")=="BA=");
assert(makePostfixForSSE("(A*B)+C", "101")=="AB*C+");
assert(makePostfixForSSE("A=(B*C)", "110")=="BC*A=");
assert(makePostfixForSSE("prod((A*B))", "10")=="1AB**");
}