/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/**
 * @author Intel, Pavel A. Ozhdikhin
 *
 */

#undef STANDALONE_TEST

#include <iostream>
#include <fstream>
#include <float.h>
#include <cstdlib>
#include <algorithm>

#ifdef STANDALONE_TEST

#include "standalonetest2.h"

#else

#include "Opcode.h"
#include "Opnd.h"
#include "Type.h"
#include "Inst.h"
#include "IRBuilder.h"
#include "BitSet.h"
#include "Log.h"
#include "optimizer.h"
#include "simplifier.h"
#include "constantfolder.h"
#include "deadcodeeliminator.h"
#include "optarithmetic.h"
#include "irmanager.h"
#include "CompilationContext.h"

#include <float.h>
#include <math.h>

#include "Stl.h"
#include "simplifier.h"
#include "optarithmetic.h"



namespace Jitrino {

#ifndef DEBUG_MULTIPLYBYCONSTANT
#define DEBUGPRINT(x)
#define DEBUGPRINT2(x,y)

#else
void indent(int indentby) {
    for (int i=0; i<indentby; i++) {
        Log::out() << " ";
    }
}
#define DEBUGPRINT(x) indent(2*depth); Log::out() << x << ::std::endl
#define DEBUGPRINT2(x,y) indent(2*depth); Log::out() << x; y.print(Log::out()); Log::out() << ::std::endl
#endif

#endif


struct MulOp {
    enum Op { pushc=0, pushy=1, swap=2, dup=3, shladd=4, add=5, sub=6, neg=7, shiftl=8, dup2, dup3, numMulOps=11 };
};

const int methodLen = 400;
const int stackDepth = 400;
const int numMulOpnds[MulOp::numMulOps] = { 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0 };

const int COST_LOADZERO = 0;
const int COST_LOADY = 0;
const int COST_NEG = 1;
const int COST_ADD = 1;
const int COST_SUB = 1;

class MulMethod {
private:
public:
    int data[methodLen];
    int len;
    bool foripf;
    int COST_ADDSHIFT_SMALL;
    int COST_SHIFT;
    int SMALL_SHIFT_MAXBITS;
    
    MulMethod(bool ipf) : len(0), foripf(ipf) {
        if (ipf) {
            COST_ADDSHIFT_SMALL = 1;
            COST_SHIFT = 1;
            SMALL_SHIFT_MAXBITS = 4;
        } else {
            COST_ADDSHIFT_SMALL = 2;
            COST_SHIFT = 4;
            SMALL_SHIFT_MAXBITS = 3;
        }
    };

    void append(MulOp::Op op0) { 
        assert((0<=op0)&&(op0<MulOp::numMulOps)); 
        assert(numMulOpnds[op0]==0); 
        data[len] = op0; len += 1; 
    };
    void append(MulOp::Op op0op, int opnd0) { 
        int op0 = (int) op0op;
        assert((0<=op0)&&(op0<MulOp::numMulOps)); 
        assert(numMulOpnds[op0]==1); 
        data[len] = op0; data[len+1] = opnd0; len += 2; 
    };

    void makespace(int k) {
        assert(len+k <= methodLen);
        assert(k>0);
        for (int i=len+k; i>k; i--) {
            data[i] = data[i-k];
        }
        len += k;
    };
    void prepend(MulOp::Op op0) {
        assert((0<=op0)&&(op0<MulOp::numMulOps)); 
        assert(numMulOpnds[op0]==0); 
        makespace(1); data[0] = op0;
    };
    void prepend(MulOp::Op op0, int opnd0) {
        assert((0<=op0)&&(op0<MulOp::numMulOps)); 
        assert(numMulOpnds[op0]==1); 
        makespace(2); data[0] = op0; data[1] = opnd0;
    };

    void append(const MulMethod &other) {
        assert(len+other.len <= methodLen);
        for (int i=0; i < other.len; i++) {
            data[len+i] = other.data[i];
        }
        len += other.len;
    }
    void prepend(const MulMethod &other) {
        makespace(other.len);
        for (int i=0; i < other.len; i++) {
            data[i] = other.data[i];
        }
    }

    int apply(int y, int *latency = 0) {
        int thestack[stackDepth];
        int when[stackDepth];
        thestack[0] = 0xdeadbeef;
        when[0] = -1;
        int ip = 0;
        int sp = 0;
        while (ip < len) {
            enum MulOp::Op op = (enum MulOp::Op) data[ip];
            ip += 1;
            assert(sp < stackDepth);
            switch (op) {
            case MulOp::pushc: assert(ip<len); thestack[sp] = data[ip++]; when[sp] = 0; sp += 1; break;
            case MulOp::pushy: thestack[sp] = y; when[sp] = COST_LOADY; sp += 1; break;
            case MulOp::swap: assert(sp >= 2); ::std::swap(thestack[sp-1], thestack[sp-2]); ::std::swap(when[sp-1], when[sp-2]); break;
            case MulOp::dup: assert(sp >= 1); thestack[sp] = thestack[sp-1]; when[sp] = when[sp-1]; sp += 1; break;
            case MulOp::dup2: assert(sp >= 2); thestack[sp] = thestack[sp-2]; when[sp] = when[sp-2]; sp += 1; break;
            case MulOp::dup3: assert(sp >= 2); thestack[sp] = thestack[sp-3]; when[sp] = when[sp-3]; sp += 1; break;
            case MulOp::add: assert(sp >= 2); 
                thestack[sp-2] = thestack[sp-2] + thestack[sp-1]; 
                when[sp-2] = ::std::max(when[sp-2],when[sp-1]) + COST_ADD;
                sp -=1; 
                break;
            case MulOp::sub: assert(sp >= 2); 
                thestack[sp-2] = thestack[sp-2] - thestack[sp-1]; 
                when[sp-2] = ::std::max(when[sp-2],when[sp-1]) + COST_SUB;
                sp -=1; break;
            case MulOp::shladd: assert(sp >= 2); 
                assert(ip<len);
                assert(data[ip] <= SMALL_SHIFT_MAXBITS);
                thestack[sp-2] = (thestack[sp-2] << data[ip++]) + thestack[sp-1]; 
                when[sp-2] = ::std::max(when[sp-2],
                                      when[sp-1]) + COST_ADDSHIFT_SMALL;
                sp -=1; break;
            case MulOp::neg: assert(sp >= 1); 
                thestack[sp-1] = -thestack[sp-1];
                when[sp-1] = when[sp-1] + COST_NEG;
                break;
            case MulOp::shiftl: assert(sp >= 1); 
                assert(ip<len);
                thestack[sp-1] = thestack[sp-1] << data[ip++];
                when[sp-1] = when[sp-1]+ COST_SHIFT;
                break;
            default:
                assert(0);
            }
        }
        if (sp != 1) {
            ::std::cerr << ::std::endl;
            ::std::cerr << "sp != 1 after applying: ";
            printOps(::std::cerr); ::std::cerr << ::std::endl;
            assert(0);
        }
        if (latency) { *latency = when[0]; }
        return thestack[0];
    };
    void printOps(::std::ostream &outs) const {
        int ip = 0;
        while (ip < len) {
            enum MulOp::Op op = (enum MulOp::Op) data[ip];
            ip += 1;
            switch (op) {
            case MulOp::pushc: outs << "push " << data[ip++] << "; "; break;
            case MulOp::pushy: outs << "push y; "; break;
            case MulOp::swap: outs << "swap; "; break;
            case MulOp::dup: outs << "dup; "; break;
            case MulOp::dup2: outs << "dup2; "; break;
            case MulOp::dup3: outs << "dup3; "; break;
            case MulOp::add: outs << "add; "; break;
            case MulOp::sub: outs << "sub; "; break;
            case MulOp::shladd: outs << "shladd " << data[ip++] << "; "; break;
            case MulOp::neg: outs << "neg; "; break;
            case MulOp::shiftl: outs << "shiftl " << data[ip++] << "; "; break;
            default: break;
            }
        }
    }

    enum What { IsConstant, IsY, IsSub };
    static void printSub(::std::ostream &outs, int onstack, enum What what) {
        switch (what) {
        case IsConstant: outs << onstack; break;
        case IsY: outs << "Y"; break;
        case IsSub: outs << "t" << onstack; break;
        default: assert(0);
            
        }
    }
    void print(::std::ostream &outs) const {
        int thestack[stackDepth];
        What what[stackDepth];
        thestack[0] = 0xdeadbeef;
        what[0] = IsConstant;
        int ip = 0;
        int sp = 0;
        int subnum = 0;
        if (len == 0)
            return; // no reduction
        while (ip < len) {
            enum MulOp::Op op = (enum MulOp::Op) data[ip];
            ip += 1;
            assert(sp < stackDepth);
            switch (op) {
            case MulOp::pushc: assert(ip<len); thestack[sp] = data[ip++]; what[sp] = IsConstant; sp += 1; break;
            case MulOp::pushy: thestack[sp] = 0; what[sp] = IsY; sp += 1; break;
            case MulOp::swap: assert(sp >= 2); ::std::swap(thestack[sp-1], thestack[sp-2]); ::std::swap(what[sp-1], what[sp-2]); break;
            case MulOp::dup: assert(sp >= 1); thestack[sp] = thestack[sp-1]; what[sp] = what[sp-1]; sp += 1; break;
            case MulOp::dup2: assert(sp >= 2); thestack[sp] = thestack[sp-2]; what[sp] = what[sp-2]; sp += 1; break;
            case MulOp::dup3: assert(sp >= 2); thestack[sp] = thestack[sp-3]; what[sp] = what[sp-3]; sp += 1; break;
            case MulOp::add: 
                {
                    assert(sp >= 2); 
                    int thissub = ++subnum;
                    outs << "t" << thissub << " = add ";
                    printSub(outs, thestack[sp-2], what[sp-2]); outs << ", ";
                    printSub(outs, thestack[sp-1], what[sp-1]); outs << "; ";
                    thestack[sp-2] = thissub; what[sp-2] = IsSub; sp -=1; 
                    break;
                }
            case MulOp::sub: 
                {
                    assert(sp >= 2); 
                    int thissub = ++subnum;
                    outs << "t" << thissub << " = sub ";
                    printSub(outs, thestack[sp-2], what[sp-2]); outs << ", ";
                    printSub(outs, thestack[sp-1], what[sp-1]); outs << "; ";
                    thestack[sp-2] = thissub; what[sp-2] = IsSub; sp -=1; 
                    break;
                }
            case MulOp::shladd: 
                {
                    assert(sp >= 2); 
                    assert(ip<len);
                    assert(data[ip] <= SMALL_SHIFT_MAXBITS);
                    int thissub = ++subnum;
                    outs << "t" << thissub << " = shladd ";
                    printSub(outs, thestack[sp-2], what[sp-2]); 
                    outs << ", " << data[ip++] << ", ";
                    printSub(outs, thestack[sp-1], what[sp-1]); outs << "; ";
                    thestack[sp-2] = thissub; what[sp-2] = IsSub; sp -=1; 
                    break;
                }
            case MulOp::neg: 
                {
                    assert(sp >= 1); 
                    int thissub = ++subnum;
                    outs << "t" << thissub << " = neg ";
                    printSub(outs, thestack[sp-1], what[sp-1]); outs << "; ";
                    thestack[sp-1] = thissub; what[sp-1] = IsSub;
                    break;
                }
            case MulOp::shiftl: 
                {
                    assert(sp >= 1); 
                    assert(ip<len);
                    int thissub = ++subnum;
                    outs << "t" << thissub << " = shiftl ";
                    printSub(outs, thestack[sp-1], what[sp-1]); outs << ", " << data[ip++] << "; ";
                    thestack[sp-1] = thissub; what[sp-1] = IsSub;
                    break;
                }
            default:
                assert(0);
            }
        }
        if (sp != 1) {
            ::std::cerr << ::std::endl;
            ::std::cerr << "sp != 1 after applying: ";
            printOps(::std::cerr); ::std::cerr << ::std::endl;
            assert(0);
        }

        outs << "r = ";
        printSub(outs, thestack[sp-1], what[sp-1]);
    };

    int getCost() {
        if (len == 0) {
            return 10000;
        } else {
            int latency;
            apply(13, &latency);
            return latency;
        }
    }
#ifndef STANDALONE_TEST
    Opnd *genCode(Type *type, Simplifier *simp, Opnd *y)
    {
        Opnd *thestack[stackDepth];
        Type::Tag tag = y->getType()->tag;
        bool width32 = ((tag == Type::Int32) || (tag == Type::UInt32));
        thestack[0] = 0;
        int ip = 0;
        int sp = 0;
        if (len == 0)
            return NULL; // no reduction
        while (ip < len) {
            enum MulOp::Op op = (enum MulOp::Op) data[ip];
            ip += 1;
            assert(sp < stackDepth);
            switch (op) {
            case MulOp::pushc: {
                assert(ip<len); 
                int val = data[ip]; ip += 1;
                Opnd *op = (width32 
                            ? simp->genLdConstant((I_32)(val))->getDst()
                            : simp->genLdConstant((int64)(val))->getDst());
                thestack[sp] = op;
                sp += 1;
            } break;
            case MulOp::pushy: thestack[sp] = y; sp += 1; break;
            case MulOp::swap: assert(sp >= 2); ::std::swap(thestack[sp-1], thestack[sp-2]); break;
            case MulOp::dup: assert(sp >= 1); thestack[sp] = thestack[sp-1]; sp += 1; break;
            case MulOp::dup2: assert(sp >= 2); thestack[sp] = thestack[sp-2]; sp += 1; break;
            case MulOp::dup3: assert(sp >= 2); thestack[sp] = thestack[sp-3]; sp += 1; break;
            case MulOp::add: assert(sp >= 2); 
                thestack[sp-2] = simp->genAdd(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), thestack[sp-2], thestack[sp-1])->getDst();
                sp -=1; 
                break;
            case MulOp::sub: assert(sp >= 2); 
                thestack[sp-2] = simp->genSub(type, Modifier(Overflow_None)|Modifier(Exception_Never)|Modifier(Strict_No), thestack[sp-2], thestack[sp-1])->getDst(); 
                sp -=1; break;
            case MulOp::shladd: { 
                assert(sp >= 2); 
                assert(ip<len);
                int val = data[ip]; ip += 1;
                assert(val <= SMALL_SHIFT_MAXBITS);
                Opnd *op = simp->genLdConstant((I_32)(val))->getDst();
                thestack[sp-2] = simp->genShladd(type, thestack[sp-2], op, thestack[sp-1])->getDst(); 
                sp -=1; } break;
            case MulOp::neg: assert(sp >= 1); 
                thestack[sp-1] = simp->genNeg(type, thestack[sp-1])->getDst();
                break;
            case MulOp::shiftl: {
                assert(sp >= 1); 
                assert(ip<len);
                int val = data[ip]; ip += 1;
                Opnd *op = simp->genLdConstant((I_32)(val))->getDst();
                thestack[sp-1] = simp->genShl(type, ShiftMask_None,
                                              thestack[sp-1], op)->getDst();
            } break;
            default:
                assert(0);
            }
        }
        
        assert(sp == 1);
        return thestack[0];
    }
#endif // !STANDALONE_TEST

};

template <typename inttype, int width>
bool testMul(MulMethod &method, inttype d, inttype num);

template <typename inttype, int width>
void planMulCompound(MulMethod &m, inttype d, int depth);

template <typename inttype, int width>
void planMulLookup(MulMethod &m, inttype d, int depth);

template <typename inttype, int width>
void planMulFactor(MulMethod &m, inttype d, int depth);

template <typename inttype, int width>
void planMulLarge(MulMethod &m, inttype d, int depth);

template <typename inttype, int width>
void planMulNeg(MulMethod &m, inttype d, int depth);

template <typename inttype, int width>
void planMul(MulMethod &m, inttype d, int depth);

template <typename inttype, int width>
void planMul(MulMethod &m, inttype d, int depth) {
    DEBUGPRINT("planMul(" << (int)d << ")");
    if (d == -1) {
        m.append(MulOp::pushy); m.append(MulOp::neg);
    } else if (d == 1) {
        m.append(MulOp::pushy);
    } else if (d == 0) {
        m.append(MulOp::pushc, 0);
    } else if (d == -d) {
        int k = width - 1;
        m.append(MulOp::pushy); m.append(MulOp::shiftl, k);
    } else {
    /* ONLY DO REDUCTION FOR THE TWO CASES */
        if ((d < 32) && (d > 0)) {
            planMulLookup<inttype, width>(m, d, depth+1);
        } else if (isPowerOf2(d)) {
            int k = whichPowerOf2<inttype, width>(d);
            m.append(MulOp::pushy); m.append(MulOp::shiftl, k);
        }
    /* 
        if (d < 0) {
            planMulNeg<inttype, width>(m, d, depth);
        } else if (d < 32) {
            planMulLookup<inttype, width>(m, d, depth+1);
        } else if (isPowerOf2(d)) {
            int k = whichPowerOf2<inttype, width>(d);
            m.append(MulOp::pushy); m.append(MulOp::shiftl, k);
        } else {
            planMulLarge<inttype, width>(m, d, depth+1);
        }
    */
    }
#ifdef TEST_OUTPUT
    DEBUGPRINT2("planMul(" << d << ")", res);
    for (int i=0; i<10000; i += 17) {
        inttype num = i;
        if (!(testMul<inttype, width>(m, res, d, num) &&
              testMul<inttype, width>(m, res, d, -num) &&
              testMul<inttype, width>(m, res, d, 0x7fffffff+num) &&
              testMul<inttype, width>(m, res, d, 0x7fffffff-num))) {
            return;
        }
    }
#endif
}

template <typename inttype, int width>
void planMulNeg(MulMethod &m, inttype d, int depth) {
    DEBUGPRINT("planMulNeg(" << (int)d << ")");

    if (depth == 1) {
        // this seems to win by 2 cycles only in about 2/25000 cases
        // and by 1 cycle only in about 1/50 cases
        DEBUGPRINT("planMulNeg(" << (int)d << ") case 1");
        MulMethod res1(m.foripf);
        planMul<inttype, width>(res1, -d, depth+1); res1.append(MulOp::neg);

        // this seems to win by 2 cycles in about 1/250 cases
        // and by 1 cycle in 1/10 cases
        // but that's not enough to justify a search
        DEBUGPRINT("planMulNeg(" << (int) d << ") case 2");
        MulMethod res2(m.foripf);
        inttype dinv = ~d;
        int numones = nlz<inttype, width>(dinv);
        int shiftby = width - numones;
        inttype newd = d + ((inttype)1 << shiftby);
        if (shiftby <= m.SMALL_SHIFT_MAXBITS) {
            DEBUGPRINT("planMulNeg(" << (int) d << ") case 2a, shiftby=" << shiftby);
            res2.append(MulOp::pushy); res2.append(MulOp::neg);
            planMul<inttype, width>(res2, newd, depth+1);
            res2.append(MulOp::shladd, shiftby);
        } else {
            DEBUGPRINT("planMulNeg(" << (int) d << ") case 2b, shiftby=" << shiftby);
            planMul<inttype, width>(res2, newd, depth+1);
            res2.append(MulOp::pushy); res2.append(MulOp::shiftl, shiftby);
            res2.append(MulOp::sub);
        }    

        DEBUGPRINT("planMulNeg(" << (int) d << ") case 3");
        MulMethod res3(m.foripf);
        planMulCompound<inttype, width>(res3, d, depth+1);
        
        int latency1 = res1.getCost();
        int latency2 = res2.getCost();
        int latency3 = res3.getCost();
        if ((latency1 <= latency2) && (latency1 <= latency3)) {
            if (latency2 < latency3) {
                DEBUGPRINT("choose neg method 1 by " << latency2-latency1 << " over 2");
            } else if (latency3 < latency2) {
                DEBUGPRINT("choose neg method 1 by " << latency3-latency1 << " over 3");
            } else {
                DEBUGPRINT("choose neg method 1 by " << latency2-latency1 << " over 2 & 3");
            }
            m.append(res1);
        } else if (latency2 < latency3) {
            if (latency1 < latency3) {
                DEBUGPRINT("choose neg method 2 by " << latency1 - latency2 << " over 1");
            } if (latency1 > latency3) {
                DEBUGPRINT("choose neg method 2 by " << latency3 - latency2 << " over 3");
            } else {
                DEBUGPRINT("choose neg method 2 by " << latency3 - latency2 << " over 1 & 3");
            }
            m.append(res2);
        } else {
            if (latency1 < latency2) {
                DEBUGPRINT("choose neg method 3 by " << latency1 - latency3 << " over 1");
            } if (latency1 > latency2) {
                DEBUGPRINT("choose neg method 3 by " << latency2 - latency3 << " over 2");
            } else {
                DEBUGPRINT("choose neg method 3 by " << latency2 - latency3 << " over 1 & 2");
            }
            m.append(res3);
        }
    } else {
        DEBUGPRINT("planMulNeg(" << (int) d << ") case 3a");
        planMulCompound<inttype, width>(m, d, depth+1);
    }

    DEBUGPRINT("done planMulNeg(" << (int) d << ")");
}

template <typename inttype, int width>
void planMulFactor(MulMethod &m, inttype d, int depth)
{
    DEBUGPRINT("planMulFactor(" << (int) d << ")");
    MulMethod res2(m.foripf);
    int shiftby = m.SMALL_SHIFT_MAXBITS;
    inttype factor = (1 << shiftby) + 1;

    // small factors
    while (factor > 2) {
        if ((d % factor) == 0) {
            DEBUGPRINT("planMulFactor(" << (int) d << ") found factor " << (int) factor);
            MulMethod res1(m.foripf);
            inttype quot = d / factor;
            planMul<inttype, width>(res1, quot, depth+1);
            res1.append(MulOp::dup);
            res1.append(MulOp::shladd, shiftby);
            m.append(res1); 
            return;
        }
        factor = (factor >> 1) + 1;
        shiftby -= 1;
    }

    // bigger factors
    shiftby = width - 2;
    factor = (1 << shiftby) + 1;
    while (factor > (1 << m.SMALL_SHIFT_MAXBITS) + 1) {
        if ((d % factor) == 0) {
            DEBUGPRINT("planMulFactor(" << (int) d << ") found factor " << (int) factor);
            MulMethod res1(m.foripf);
            inttype quot = d / factor;
            planMul<inttype, width>(res1, quot, depth+1);
            res1.append(MulOp::dup);
            res1.append(MulOp::shiftl, shiftby);
            res1.append(MulOp::add);
            m.append(res1); 
            return;
        }
        factor = (factor >> 1) + 1;
        shiftby -= 1;
    }

    // bigger factors
    shiftby = width - 2;
    factor = (1 << (int) shiftby) - 1;
    while (factor > 3) {
        if ((d % factor) == 0) {
            MulMethod res1(m.foripf);
            if (d > 0) {
                DEBUGPRINT("planMulFactor(" << (int) d << ") found factor " << (int) factor);
                inttype quot = d / factor;
                planMul<inttype, width>(res1, quot, depth+1);
                res1.append(MulOp::dup);
                res1.append(MulOp::shiftl, shiftby);
                res1.append(MulOp::swap);
                res1.append(MulOp::sub);
                m.append(res1); 
                return;
            } else {
                DEBUGPRINT("planMulFactor(" << (int) d << ") found factor " << (int) -factor);
                inttype quot = -d / factor;
                planMul<inttype, width>(res1, quot, depth+1);
                res1.append(MulOp::dup);
                res1.append(MulOp::shiftl, shiftby);
                res1.append(MulOp::sub);
                m.append(res1); 
                return;
            }
        }
        factor = ((factor+1) >> 1) - 1;
        shiftby -= 1;
    }

    DEBUGPRINT("done planMulFactor(" << (int) d << ")");
    m.append(res2);
}

template <typename inttype, int width>
void planMulLarge(MulMethod &m, inttype d, int depth)
{
    if (depth < 6) {
        MulMethod res1(m.foripf);
        planMulCompound<inttype, width>(res1, d, depth);
        
        MulMethod res2(m.foripf);
        planMulFactor<inttype, width>(res2, d, depth);
        
        int latency1 = res1.getCost();
        int latency2 = res2.getCost();
        if (latency1 <= latency2) {
            DEBUGPRINT("choose large method 1: compound");
            m.append(res1);
        } else {
            DEBUGPRINT("choose large method 2: factor");
            m.append(res2);
        }
    } else {
        planMulCompound<inttype, width>(m, d, depth);
    }
}

template <typename inttype, int width>
void planMulCompound(MulMethod &m, inttype d, int depth) {
    assert((d < 0) || (d > 31));
    DEBUGPRINT("planMulCompound(" << (int) d << ")");

    inttype delta = d ^ (d >> 1); // bits differing from from bit to left
    int numChanges = popcount<inttype, width>(delta);
    int deltaright = ntz<inttype, width>(delta);
    int deltaleft = nlz<inttype, width>(delta);

    int bitswidth = width - deltaright - deltaleft - 1;
    int small_shift_maxbits = m.SMALL_SHIFT_MAXBITS;

    if ((numChanges < 4) ||
        (bitswidth <= 5)) { // small enough to worry about sign/rightbit issues
        DEBUGPRINT("case few changes");
        // we assume we've dealt with <31 elsewhere, so we must have some shifting ahead of us.
        if ((d & 1) == 1) {
            inttype dinv = ~d;
            DEBUGPRINT("case odd");
            int rightones = ntz<inttype, width>(dinv);
            if (rightones == 1) {
                inttype dsub1 = d-1;
                int dsub1rightzeros = ntz<inttype, width>(dsub1);
                if (dsub1rightzeros > small_shift_maxbits) {
                    planMul<inttype, width>(m, 
                                            dsub1 >> small_shift_maxbits, 
                                            depth+1); 
                    m.append(MulOp::pushy); 
                    m.append(MulOp::shladd, small_shift_maxbits);
                } else {
                    planMul<inttype, width>(m, 
                                            dsub1 >> dsub1rightzeros, 
                                            depth+1); 
                    m.append(MulOp::pushy); 
                    m.append(MulOp::shladd, dsub1rightzeros);
                }
            } else if (rightones <= small_shift_maxbits) {
                planMul<inttype, width>(m, (d+1)>>rightones, depth+1); 
                m.append(MulOp::pushy); 
                m.append(MulOp::neg);
                m.append(MulOp::shladd, rightones);
            } else {
                planMul<inttype, width>(m, (d+1)>>small_shift_maxbits, 
                                        depth+1); 
                m.append(MulOp::pushy); m.append(MulOp::neg);
                m.append(MulOp::shladd, small_shift_maxbits);
            }
        } else {
            DEBUGPRINT("case even");
            int rightzeros = deltaright+1;
            assert((rightzeros == ntz<inttype, width>(d)));
            if (bitswidth <= 5) {
                DEBUGPRINT("case narrow");
                if ((rightzeros <= small_shift_maxbits) &&
                    (rightzeros + bitswidth >= 2 * small_shift_maxbits)) {
                    DEBUGPRINT("case smallshiftadd");
                    inttype newd = d + ((inttype)1 << rightzeros);
                    m.append(MulOp::pushy); m.append(MulOp::neg); 
                    planMul<inttype, width>(m, newd, depth+1); 
                    m.append(MulOp::shladd, rightzeros);
                } else {
                    inttype newd = d >> rightzeros;
                    DEBUGPRINT("case smallshift");
                    planMul<inttype, width>(m, newd, depth+1); 
                    m.append(MulOp::shiftl, rightzeros);
                }
            } else {
                DEBUGPRINT("case even, wider");
                inttype deltasubright = delta - ((inttype)1 << deltaright);
                int deltasubright_ntz = ntz<inttype, width>(deltasubright);
                int region2 = deltasubright_ntz - deltaright +1;
                assert(region2 > 0);
                if (region2 > 2) {
                    inttype newd = d + ((inttype)1 << rightzeros);
                    if (rightzeros <= small_shift_maxbits) {
                        DEBUGPRINT("case wide smalladdshift");
                        m.append(MulOp::pushy); m.append(MulOp::neg);
                        planMul<inttype, width>(m, newd, depth+1);
                        m.append(MulOp::shladd, rightzeros);
                    } else {
                        DEBUGPRINT("case wide sub of shift");
                        planMul<inttype, width>(m, newd, depth+1);
                        m.append(MulOp::pushy); m.append(MulOp::shiftl, rightzeros);
                        m.append(MulOp::sub);
                    }
                } else if (region2 == 2) {
                    inttype newd = d - (3 << rightzeros);
                    DEBUGPRINT("case wide addshift3");
                    if (rightzeros <= small_shift_maxbits) {
                        m.append(MulOp::pushy); m.append(MulOp::pushy); 
                        m.append(MulOp::shladd, 1);
                        planMul<inttype, width>(m, newd, depth+1);
                        m.append(MulOp::shladd, rightzeros);
                    } else {
                        DEBUGPRINT("case wide add shift3");
                        planMul<inttype, width>(m, newd >> small_shift_maxbits,
                                                depth+1);
                        m.append(MulOp::pushy); m.append(MulOp::pushy); 
                        m.append(MulOp::shladd, 1);
                        m.append(MulOp::shiftl, rightzeros);
                        m.append(MulOp::shladd, small_shift_maxbits);
                    }
                } else { // region2 == 1
                    inttype newd = d - ((inttype)1 << rightzeros);
                    if (rightzeros <= small_shift_maxbits) {
                        DEBUGPRINT("case wide smalladdshift1");
                        m.append(MulOp::pushy);
                        planMul<inttype, width>(m, newd, depth+1);
                        m.append(MulOp::shladd, rightzeros);
                    } else {
                        DEBUGPRINT("case wide sub of shift");
                        planMul<inttype, width>(m, newd >> small_shift_maxbits,
                                                depth+1);
                        m.append(MulOp::pushy);
                        m.append(MulOp::shiftl, rightzeros);
                        m.append(MulOp::shladd, small_shift_maxbits);
                    }
                }
            }
        }
    } else { // bitswidth > 5
        assert(numChanges >= 2);
        DEBUGPRINT("case wide");

        if (numChanges == 2) {
            DEBUGPRINT("case numChanges==2");
            if ((numChanges&1)==0) {
                DEBUGPRINT("case wide changes=2 even");
                int rightzeros = deltaright+1;
                int leftzeros = deltaleft;
                assert((rightzeros == ntz<inttype, width>(d)));
                assert((leftzeros == nlz<inttype, width>(d)));
                if (rightzeros <= small_shift_maxbits) {
                    DEBUGPRINT("case wide smallshiftadd");
                    assert(rightzeros+bitswidth >= 2 * small_shift_maxbits);
                    m.append(MulOp::pushy); m.append(MulOp::neg);
                    m.append(MulOp::pushy); m.append(MulOp::shiftl, width - leftzeros);
                    m.append(MulOp::shladd, rightzeros);
                } else {
                    DEBUGPRINT("case wide narrow sub");
                    m.append(MulOp::pushy); m.append(MulOp::shiftl, width - leftzeros);
                    m.append(MulOp::pushy); m.append(MulOp::shiftl, rightzeros);
                    m.append(MulOp::sub);
                }
            } else {
                DEBUGPRINT("case wide changes=2 odd");
            }
        } else {
            // first try: use point width/2 to split number
            DEBUGPRINT("case numChanges>2");
            
            int rightzeros = ((d & 1)!=0) ? 0 : deltaright+1;
#ifndef NDEBUG
            int leftzeros = ((d & ((inttype)1<<(width-1))) != 0) ? 0 : deltaleft;
#endif
            assert((rightzeros == ntz<inttype, width>(d)));
            assert((leftzeros == nlz<inttype, width>(d)));

            int k = (numChanges + 1) >> 2;
            assert(k > 0); // we had numChanges>=3 above.
            inttype stripright = d;
            while (k > 0) {
                // turn rightmost group of 0s into 1s, no effect if none
                inttype striprightzeros = stripright | (stripright - 1);
                // turn rightmost group of 1s into 0s, must be some
                inttype srzinv = ~striprightzeros; // first invert
                inttype sroinv = srzinv | (srzinv - 1); // strip 0s
                stripright = ~sroinv; // invert back
                k -= 1;
            }
            // now stripright is d but with 0s from about the middle
            // of changes to the right
            // find a point one place to the left of the set of 0s
            int zeropoint = ntz<inttype, width>(stripright);
            inttype zerobit = (inttype(1))<<zeropoint;

            assert((d & zerobit) != 0);
            assert((d & (zerobit>>1)) == 0);

            DEBUGPRINT("zerobit is " << (int) zerobit);
            DEBUGPRINT("zeropoint is " << (int) zeropoint);
            inttype rightmask  = zerobit - 1;
            inttype leftmask  = ~rightmask;
            DEBUGPRINT("leftmask is " << (int) leftmask << ", rightmask is " << (int) rightmask);
            
            inttype rightd = d & rightmask;
            inttype leftd = d & leftmask;
            
            DEBUGPRINT("leftd is " << (int) leftd << ", rightd is " << (int) rightd);
            
            int leftdrightzeros = ntz<inttype, width>(leftd);
            
            if (rightzeros == 0) {
                DEBUGPRINT("case 0");
                if (leftdrightzeros < small_shift_maxbits) {
                    DEBUGPRINT("case 0a");
                    planMul<inttype, width>(m, leftd >> leftdrightzeros, 
                                            depth+1);
                    planMul<inttype, width>(m, rightd, depth+1);
                    m.append(MulOp::shladd, leftdrightzeros);
                } else {
                    planMul<inttype, width>(m, leftd, depth+1);
                    planMul<inttype, width>(m, rightd, depth+1);
                    m.append(MulOp::add);
                }
            } else if ((0 < rightzeros) && (rightzeros <= small_shift_maxbits)) {
                DEBUGPRINT("case 1");
                planMul<inttype, width>(m, rightd >> rightzeros, depth+1);
                planMul<inttype, width>(m, leftd, depth+1);
                m.append(MulOp::shladd, rightzeros);
            } else {
                DEBUGPRINT("case 3");
                planMul<inttype, width>(m, leftd >> small_shift_maxbits, 
                                        depth+1);
                planMul<inttype, width>(m, rightd, depth+1);
                m.append(MulOp::shladd, small_shift_maxbits);
            }
            DEBUGPRINT("done");
        }
    }
}

template <typename inttype, int width>
void planMulLookup(MulMethod &m, inttype d, int depth) {
    assert((d>=0) && (d < 32));
    DEBUGPRINT("planMulLookup(" << (int) d << ")");
    switch (d) {
    case 0: m.append(MulOp::pushc, 0); break;
    case 1: m.append(MulOp::pushy); break;
    case 2: m.append(MulOp::pushy); m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 3: m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1); break;
    case 4: m.append(MulOp::pushy); m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 2); break;
    case 5: m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 2); break;
    case 6: 
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 7:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1); break;
    case 8: m.append(MulOp::pushy); m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 3); break;
    case 9: m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 3); break;
    case 10:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 2);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 11:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 2);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1); break;
    case 12:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 2); break;
    case 13:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 2); break;
    case 14:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 15:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::dup); m.append(MulOp::shladd, 2); break;
    case 16:
        m.append(MulOp::pushy); 
        if (m.SMALL_SHIFT_MAXBITS == 4) {
            m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 4);
        } else if (m.SMALL_SHIFT_MAXBITS == 3) {
            m.append(MulOp::shiftl, 4);
        } else {
            assert(0);
        }
        break;
    case 17:
        m.append(MulOp::pushy); m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 3);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1);
        break;
    case 18:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 3); 
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 19:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 3); 
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1); break;
    case 20:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 2); 
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 2); break;
    case 21:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 2); 
        m.append(MulOp::pushy); m.append(MulOp::shladd, 2); break;
    case 22:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 2);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 23:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 2);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1); break;
    case 24:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 3); break;
    case 25:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 3); break;
    case 26:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 2);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 27:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::dup); m.append(MulOp::shladd, 3); break;
    case 28:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 2); break;
    case 29:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 2); break;
    case 30:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::dup); m.append(MulOp::shladd, 2);
        m.append(MulOp::pushc, 0); m.append(MulOp::shladd, 1); break;
    case 31:
        m.append(MulOp::pushy); m.append(MulOp::dup); m.append(MulOp::shladd, 1);
        m.append(MulOp::dup); m.append(MulOp::shladd, 2);
        m.append(MulOp::pushy); m.append(MulOp::shladd, 1); break;
    default:
        assert(0);
    }
}

#ifdef STANDALONE_TEST

#include "testharness2.h"

#else // !STANDALONE_TEST
Opnd *
Simplifier::planMul32(I_32 multiplier, Opnd *opnd)
{
    const OptimizerFlags& optimizerFlags = irManager.getOptimizerFlags();
    MulMethod method(!optimizerFlags.ia32_code_gen);
    planMul<I_32, 32>(method, multiplier, 1);
    if (Log::isEnabled()) {
        Log::out() << "in multiply(" << (int) multiplier << ", ";
        opnd->print(Log::out());
        Log::out() << "), method is ";
        method.print(Log::out()); Log::out() << ::std::endl;
    }
    return method.genCode(opnd->getType(), this, opnd);
}

Opnd *
Simplifier::planMul64(int64 multiplier, Opnd *opnd)
{
    const OptimizerFlags& optimizerFlags = irManager.getOptimizerFlags();
    MulMethod method(!optimizerFlags.ia32_code_gen);
    planMul<int64, 64>(method, multiplier, 1);
    if (Log::isEnabled()) {
        Log::out() << "in multiply(" << (int) multiplier << ", ";
        opnd->print(Log::out());
        Log::out() << "), method is ";
        method.print(Log::out()); Log::out() << ::std::endl;
    }
    return method.genCode(opnd->getType(), this, opnd);
}

#endif

} //namespace Jitrino