drlvm/vm/jitrino/src/optimizer/abcd/abcdbounds.h

/*
 *  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.
 */

#ifndef _ABCD_BOUNDS_H
#define _ABCD_BOUNDS_H

#include <cstddef>
#include <iostream>
#include "open/types.h"
#include "Type.h"

#include "Stl.h"

#include "Opnd.h"

namespace Jitrino {

class Inst;
class Opnd;
class ConstBound;
class PiBoundIter;
class AbcdReasons;

class AbcdReasons {
private:
    AbcdReasons(const AbcdReasons &other) : facts(other.facts) { assert(0); }
    AbcdReasons& operator=(const AbcdReasons &other) { assert(0); return *this; }
public:
    StlSet<SsaTmpOpnd *> facts; // tau operands
    typedef StlSet<SsaTmpOpnd *> facts_type;
    AbcdReasons(MemoryManager &mm) : facts(mm) {};
    void addReasons(AbcdReasons &alsoNeed) {
        facts_type::iterator i = alsoNeed.facts.begin();
        while (i != alsoNeed.facts.end()) {
            facts.insert(*i);
            i++;
        }
    };
    void addReasons(StlVector<AbcdReasons *> *alsoNeeds) { 
        assert(alsoNeeds);
        StlVector<AbcdReasons *>::iterator
            iter = alsoNeeds->begin(),
            end = alsoNeeds->end();
        for ( ; iter != end; ++iter) {
            AbcdReasons *alsoNeed = *iter;
            assert(alsoNeed);
            facts_type::iterator i = alsoNeed->facts.begin();
            while (i != alsoNeed->facts.end()) {
                facts.insert(*i);
                i++;
            }
        }
    };
    void addReason(SsaTmpOpnd *tau) {
        facts.insert(tau);
    };
    void clear() {
        facts.clear();
    }
    void print(::std::ostream &os) const;
};

// rather than having to create new variable objects to represent
// the upper and lower bounds on a variable, we just add a qualifier
// var_is_lb which indicates which of the 2 bounds of that variable this
// bound is based on.
struct VarBound {
    Opnd *the_var;
    bool operator==(const VarBound &other) const {
        return(the_var == other.the_var);
    }
    bool operator<(const VarBound &other) const {
        return(the_var < other.the_var);
    }
    VarBound(Opnd *v) : the_var(v) {};
    VarBound() : the_var(0) {};
    VarBound(const VarBound &other) : the_var(other.the_var) {};
    VarBound(const VarBound &other,
             Opnd *renameFrom, Opnd *renameTo) :
        the_var((other.the_var==renameFrom) ? renameTo : other.the_var)
    {};
    VarBound operator||(const VarBound &other) {
        if (isEmpty()) { return other; }
        else { return *this; };
    }
    VarBound &operator=(const VarBound &other) {
        the_var = other.the_var;
        return *this;
    };
    bool isEmpty() const { return (the_var == 0); };
    void print(::std::ostream &os) const;

    PiBoundIter getPredecessors(bool boundingBelow, 
                                bool useReasons,
                                MemoryManager &mm0) const;
    bool isMinMax(bool isMin) const;
    bool isPhiVar() const;
    bool isConvVar() const;
    VarBound getConvSource() const;
    bool convPassesSource() const; // true if conversion is one-to-one
    size_t hash() const { return ((((size_t)the_var)*17)>>4); };

    bool isConvexFunction() const; // constant inputs => constant outputs
    ConstBound getConvexInputBound(bool isLB, ConstBound outputBound,
                                   VarBound &inputVar) const;

    // true if type1 includes all values from type2
    static bool typeIncludes(Type::Tag type1, Type::Tag type2);
};

class ConstBound {
    int64 the_const;
    enum Flag { Const_PlusInfinity,
                Const_IsConst,
                Const_MinusInfinity,
                Const_IsNull} flag;
public:
    ConstBound() : the_const(0), flag(Const_IsNull) {};
    ConstBound(I_32 c) : the_const(c), flag(Const_IsConst) {};
    ConstBound(int64 c) : the_const(c), flag(Const_IsConst) {};
    ConstBound(bool positive) : the_const(0), 
                                flag(positive ? Const_PlusInfinity
                                     : Const_MinusInfinity) {};
    bool isNull() const { return (flag == Const_IsNull); };
    void setNull() { flag = Const_IsNull; };
    bool isKnown() const { return (flag == Const_IsConst); };
    bool isUnknown() const { return (flag != Const_IsConst); };
    bool isPlusInfinity() const { return (flag == Const_PlusInfinity); };
    bool isMinusInfinity() const { return (flag == Const_MinusInfinity); };
    int64 getInt64() const { return the_const; };
    I_32 getInt32() const { return (I_32)the_const; };
    bool operator ==(const ConstBound &other) const {
        if (flag == other.flag) {
            if (flag == Const_IsConst) {
                return (the_const == other.the_const);
            } else {
                return true;
            }
        } else
            return false;
    }
    bool operator <=(const ConstBound &other) const {
        if (flag == other.flag) {
            if (flag == Const_IsConst) {
                return (the_const <= other.the_const);
            } else {
                return true;
            }
        } else if ((other.flag == Const_PlusInfinity) ||
                   (flag == Const_MinusInfinity)) {
            return true;
        } else
            return false;
    }
    bool operator <(const ConstBound &other) const {
        if (flag == other.flag) {
            if (flag == Const_IsConst) {
                return (the_const < other.the_const);
            } else
                return false;
        } else if ((other.flag == Const_PlusInfinity) ||
                   (flag == Const_MinusInfinity)) {
            return true;
        } else
            return false;
    }
    bool operator >=(const ConstBound &other) const {
        return (other <= *this);
    }
    bool operator >(const ConstBound &other) const {
        return (other < *this);
    }
    ConstBound operator+(const ConstBound &other) const {
        if (flag == other.flag) {
            if (flag == Const_IsConst) {
                int64 result = the_const + other.the_const;
                // check for overflow
                // aeqb has 1 bits wherever a and b are the same.
                int64 aeqb = (the_const ^ other.the_const ^ __INT64_C(-1));
                // overflowed has sign bit set if overflowed
                int64 overflowed = aeqb & (result ^ the_const);
                if (overflowed < 0) {
                    if (the_const > 0) {
                        return ConstBound(true); // PlusInfinity
                    } else {
                        return ConstBound(false); // PlusInfinity
                    }
                } else {
                    return ConstBound(result);
                }
            } else
                return *this;
        } else {
            if (flag == Const_IsConst) {
                return other;
            } else if (other.flag == Const_IsConst) {
                return *this;
            } else {
                assert(0); // is unknown!
                return *this;
            }
        }
    }
    ConstBound operator-() const {
        switch (flag) {
        case Const_IsConst:
            return ConstBound(-the_const);
        case Const_PlusInfinity:
            return ConstBound(false); // MinusInfinity;
        case Const_MinusInfinity:
            return ConstBound(true); // PlusInfinity
    default:
        assert(0);
        break;
        }
        return *this;
    }
    ConstBound operator-(const ConstBound &other) const {
        if (flag == other.flag) {
            if (flag == Const_IsConst) {
                int64 result = the_const - other.the_const;
                // check for overflow
                // avb has 1 bits wherever a and b differ
                int64 avb = (the_const ^ other.the_const);
                // overflowed has sign bit set if overflowed
                int64 overflowed = avb & (result ^ the_const);
                if (overflowed < 0) {
                    if (the_const > 0) {
                        return ConstBound(true); // PlusInfinity
                    } else {
                        return ConstBound(false); // PlusInfinity
                    }
                } else {
                    return ConstBound(result);
                }
            } else {
                // undefined
                assert(0);
                return *this;
            }
        } else {
            if (flag == Const_IsConst) {
                if (other.flag == Const_PlusInfinity) {
                    return ConstBound(false); // MinusInfinity
                } else
                    return ConstBound(true); // PlusInfinity
            } else {
                return *this;
            }
        }
    }
    void print(::std::ostream& os) const;
};
    
// represents condition on some variable x:
//   var_multiple * var_part + const_part
// all arithmetic is appropriate to the given type
//   only compatible operations can be done
class ConstInst;

class PiBound {
    int64 var_multiple;  // 0 if none or undefined or unknown
    VarBound var_part;   // isEmpty() if var_multiple is 0
    int64 const_part;    // 0 if undefined or unknown
    enum Flag { PiBound_Undefined = 0,  // under-constrained
                // as a lower bound, Undefined = -infinity,
                // as an upper bound, Undefined = +infinity,
                PiBound_Normal = 1,
                PiBound_Unknown = 2     // over-constrained
                // as a lower bound, Unknown = +infinity,
                // as an upper bound, Unknown = -infinity,
    } flag;
    enum Type::Tag typetag;
public:
    typedef enum Type::Tag TypeTag;
    TypeTag getType() const { return typetag; };
    PiBound(TypeTag typein, VarBound var, int64 multiple=1) :
        var_multiple(multiple), var_part(var),
        const_part(0), 
        flag(PiBound_Normal), typetag(typein) {};
    PiBound(TypeTag typein, int64 c) : 
        var_multiple(0), var_part(),
        const_part(c), flag(PiBound_Normal), typetag(typein) {};
    PiBound(TypeTag typein, int64 multiple, VarBound var, int64 c) :
        var_multiple(multiple), var_part(var), 
        const_part(c), flag(PiBound_Normal), typetag(typein) {};
    PiBound(TypeTag typein, bool isUnknown) : 
        var_multiple(0), var_part(),
        const_part(0), 
        flag(isUnknown ? PiBound_Unknown : PiBound_Undefined),
        typetag(typein)
    {};
    PiBound(const PiBound &other, Opnd *renameFrom, Opnd *renameTo) :
        var_multiple(other.var_multiple), 
        var_part(other.var_part, renameFrom, renameTo),
        const_part(other.const_part),
        flag(other.flag),
        typetag(other.typetag)
    {};
    PiBound(const PiBound &other, Opnd *renameFrom, 
            const PiBound &renameTo) :
        var_multiple(other.var_multiple),
        var_part(other.var_part),
        const_part(other.const_part),
        flag(other.flag),
        typetag(other.typetag)
    {
        if (other.var_part.the_var == renameFrom) {
            assert(flag == PiBound_Normal);
            if (renameTo.flag == PiBound_Normal) {
                var_multiple = other.var_multiple * renameTo.var_multiple;
                if (var_multiple == 0) {
                    var_part = VarBound();
                } else {
                    assert((other.var_multiple == 1) &&
                           (renameTo.var_multiple == 1) &&
                           (var_multiple == 1)); // for now
                    var_part = renameTo.var_part;
                }
                const_part = other.const_part + renameTo.const_part;
                int64 overflowed = 
                    (((const_part ^ other.const_part) &
                      (const_part ^ renameTo.const_part))
                     & __INT64_C(0x8000000000000));
                if (overflowed) {
                    *this = getUnknown();
                    return;
                }
                assert(renameTo.flag == PiBound_Normal);
                assert(renameTo.typetag == other.typetag);
            } else {
                *this = renameTo;
            }
        }
    };

    bool isUnknown() const { return (flag == PiBound_Unknown); };
    bool isUndefined() const { return (flag == PiBound_Undefined); };
    PiBound getUnknown() const { return PiBound(typetag, true); }
    PiBound getUndefined() const { return PiBound(typetag, false); }

    bool isNormal() const { return (flag == PiBound_Normal); };
    bool isVar() const { return (isNormal() && (const_part == 0)
                                 && (var_multiple == 1)); };
    bool isConst() const { return (isNormal() && (var_multiple == 0)); };
    bool isVarPlusConst() const { return (isNormal() 
                                          && (var_multiple == 1)); };
    VarBound getVar() const { return var_part; };
    int64 getConst() const { return const_part; };
    
    PiBound add(const PiBound &other, bool is_signed) const;
    PiBound neg() const;
    PiBound mul(const PiBound &other, bool is_signed) const;
    PiBound cast(Type::Tag newtype, bool isLb) const;
    PiBound abs() const;

    bool isComparableWith(const PiBound &other) const;

    bool isNonNegativeConstant() const;
    bool isNegativeConstant() const;
    bool isConstant() const;
    void print(::std::ostream& os) const;

    // Does the range [this, infinity] include [other, infinity]?
    bool isLessEq(const PiBound &other) const;
    // Return x such that [x, infinity] includes the union of
    // the intervals [this, infinity] and [other, infinity].
//    PiBound min(const PiBound &other) const;

    // Does the range [-infinity, this] include [-infinity, other]?
    bool isGreaterEq(const PiBound &other) const;
    // Return x such that [-infinity, x] includes the union of
    // the intervals [-infinity, this] and [-infinity, other].
//    PiBound max(const PiBound &other) const;

    PiBound invert(VarBound vb) const {
        if (isUnknown() || isUndefined()) return *this;
        assert (var_multiple == 1);
        int64 negc = -const_part;
        if (const_part == negc) return getUnknown();
        return PiBound(typetag, 1, vb, negc);
    }

    bool operator<(const PiBound &b) const {
        if ((flag < b.flag) ||
            ((flag == b.flag) &&
             ((getVar().the_var < b.getVar().the_var) ||
              ((getVar().the_var == b.getVar().the_var) &&
               (const_part < b.const_part)))))
            return true;
        return false;
    }

    // returns true if ci is representable as a PiBound, 
    // copying it into result
    static bool extractConstant(Type::Tag newtype, ConstInst *ci, PiBound &result);
};


// PiCondition represents a range [lb, ub] (mod 2^k)
// We use PiBound for both bounds, but you can think of it as:
//    lb: Undefined->-infinity; Unknown->+infinity
//    ub: Undefined->+infinity; Unknown->-infinity
// Note that because we use modular arithmetic, it is possible to have
//    ub < lb
// in which case, the range wraps around the (mod 2^k) field.
class PiCondition {
    PiBound lb, ub;
public:
    typedef enum Type::Tag TypeTag;
    PiCondition(const PiBound &l, const PiBound &u) : lb(l), ub(u) {};
    PiCondition(const PiBound &v) : lb(v), ub(v) {};
    PiCondition(const PiCondition &other): lb(other.lb), ub(other.ub){};
    PiCondition(TypeTag typetag, int64 i) : lb(typetag, i), 
                                            ub(typetag, i) {};
    PiCondition(TypeTag typetag, Opnd *opnd) : 
        lb(typetag, VarBound(opnd)),
        ub(typetag, VarBound(opnd)) {};
    PiCondition(const PiCondition &other,
                Opnd *renameFrom,
                Opnd *renameTo) :
        lb(other.lb, renameFrom, renameTo),
        ub(other.ub, renameFrom, renameTo)
    {};
    PiCondition(const PiCondition &other,
                Opnd *renameFrom,
                const PiBound &renameTo) :
        lb(other.lb, renameFrom, renameTo),
        ub(other.ub, renameFrom, renameTo)
    {};


    const PiBound &getLb() const { return lb; };
    const PiBound &getUb() const { return ub; };

    static PiCondition lower_bound(const PiBound &l) {
        return PiCondition(l, PiBound(l.getType(), false));
    };
    static PiCondition upper_bound(const PiBound &u) {
        return PiCondition(PiBound(u.getType(), false), u);
    };
    PiCondition only_lower_bound() const {
        return PiCondition(lb, PiBound(lb.getType(), false));
    };
    PiCondition only_upper_bound() const {
        return PiCondition(PiBound(ub.getType(), false), ub);
    };
    // PiCondition add(const PiCondition &other) const;
    PiCondition neg() const;
    PiCondition add(int64 constant) const;
    PiCondition mul(int64 constant) const;
    PiCondition cast(Type::Tag newtype) const;

    bool isPositiveConstant() const;
    bool isUnknown() const { 
        return (lb.isUnknown() && ub.isUnknown()); 
    };
    void print(::std::ostream& os) const;
    TypeTag getType() const { 
        assert(lb.getType() == ub.getType()); 
        return lb.getType(); 
    };
    static PiCondition typeBounds(TypeTag dstTag, TypeTag srcTag);
    // gets bounds on defining conv of varb, which should be defined by a conv
    static PiCondition convBounds(VarBound varb);
};

extern void printPiCondition(const PiCondition *, ::std::ostream &);

class PiBoundIter {
    bool isLb;
    Inst *instr;  // set to 0 when invalid
    U_32 idx;
    PiBound current;
    MemoryManager &mm;
    AbcdReasons *why;
public:
    PiBoundIter(Inst *i,
                bool boundingBelow, 
                bool useReasons,
                MemoryManager &mm0): isLb(boundingBelow),
                                     instr(i),
                                     idx(0),
                                     current(Type::Int32, true),
                                     mm(mm0),
                                     why(0)
    { 
        init(useReasons);
        setCurrent(); 
    };

    // returns true when invalid
    bool isEmpty() { return (instr == 0); };
    
    bool operator ++() {
        ++idx;
        setCurrent();
        return !isEmpty();
    }
    PiBound getBound(AbcdReasons *why0);
    void print(::std::ostream &) const;
private:
    void setCurrent();
    void init(bool useReasons);
    Opnd *getConstantOpnd(Opnd *op);
};

typedef StlSet<PiBound> AbcdAliasesSet;
class AbcdAliases {
public:
    StlSet<PiBound> theSet;
    AbcdAliases(MemoryManager &mm) : theSet(mm) {};
};

template <typename inttype>
inline bool add_overflowed(inttype sum, inttype a, inttype b) {
    return (((a < 0) == (b < 0)) &&
            ((a < 0) != (sum < 0)));
};

template <typename inttype>
inline bool neg_overflowed(inttype nega, inttype a) {
    return (nega == a);
};

#if 0
template <typename inttype>
inline bool mul_overflowed(inttype prod, inttype a, inttype b) {
    // let's just be really conservative.
    if ((a == 0) || (b == 0)) return true;
    if (((a == -1) && (b == -b)) || ((b == -1) && (a == -a))) {
        if (prod == -prod) 
            return false;
        else
            return true;
    }
    if ((prod / y) != x)
        return true;
    else
        return false;
};
#endif

} //namespace Jitrino 

#endif // _ABCD_BOUNDS_H