drlvm/modules/vm/src/main/native/jitrino/shared/optimizer/osr.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 _OSR_H
#define _OSR_H

#include "LoopTree.h"
#include <iostream>
#include "Opcode.h"
#include "ControlFlowGraph.h"
#include "Stl.h"
#include "Dominator.h"
#include "CSEHash.h"
#include "optpass.h"
#include "Opnd.h"
#include "irmanager.h"
#include "constantfolder.h"
#include <utility>

namespace Jitrino {

class IRManager;
class MemoryManager;
class InequalityGraph;
class Node;
class DominatorNode;
class Dominator;
class CFGNode;
class Opnd;
class CFGInst;
class CSEHashTable;
class Type;
class LoopTree;
class DominatorTree;

enum iv_detection_flag {
    CHOOSE_MAX_IN_BRANCH,
    IGNORE_BRANCH
};

/* Class for holding info on operands.
 * Similar to what loop_unroll uses internally.
 * */

class OSROpndInfo {
public:
    enum OpndType {
        DEF_OUT_OF_LOOP,
        LD_CONST,
        COUNTER,
        UNDEF
    };

    OSROpndInfo() {
        type = DEF_OUT_OF_LOOP;
        val = 0;
        phiSplit = false;
        header = 0;
        header_found = false;
        curOpnd = 0;
    } 
    OpndType getType() const {return type;} 

    void setType(OpndType newType) {
        assert(type != newType);
        type = newType;
        val = 0;
    }

    bool isCounter() const { return type == COUNTER;} 
    bool isLDConst() const {return type == LD_CONST;} 
    bool isDOL() const {return type == DEF_OUT_OF_LOOP;} 
    bool isUndefined() const {return type == UNDEF;} 

    U_32 getConst() const {
        assert(getType() == LD_CONST);
        return val;
    }
    void setConst(U_32 v) {
        assert(getType() == LD_CONST);
        val = v;
    }

    int getIncrement() const {
        assert(getType() == COUNTER);
        return val;
    }
    void setIncrement(int v) {
        assert(getType() == COUNTER);
        val = v;
    }
    bool isPhiSplit() const { return phiSplit;} 
    void markPhiSplit() {
        assert(isCounter());
        phiSplit = true;
    }
    Opnd *getHeader() { return header;}
    void setHeader(Opnd * h) {header = h;}
    bool isHeaderFound() { return header_found;}
    void setHeaderFound() {header_found = true;}
    void setOpnd(Opnd * opnd) {curOpnd = opnd;}
    Opnd *getOpnd() {return curOpnd;}

    void print(std::ostream & out) {
        out << "Pruint32ing status for: ";
        curOpnd->print(Log::out());
        out << "\n";
        if (type == DEF_OUT_OF_LOOP)
            out << "DOL";
        else if (type == LD_CONST)
            out << "LDC:" << getConst();
        else if (type == COUNTER)
            out << "CNT:" << getIncrement() << (phiSplit ? " splt" : "");
        else
            out << "UNDEF";
        if (isHeaderFound()) {
            out << "\n Header: ";
            if (header != 0) {
                header->print(Log::out());
            } else {
                Log::out() << "NULL";
            }
            out << "\n";
        }
    }

private:
    friend class OSRInductionDetector;
    OpndType type;
    int val;
    bool phiSplit;
    Opnd *header;
    bool header_found;
    Opnd *curOpnd;
};

class OSRInductionDetector {
public:
    typedef StlVector < Inst* >InstStack;
    static OSROpndInfo processOpnd(LoopTree * tree,
                   LoopNode* loopHead,
                   InstStack& defStack,
                   const Opnd* opnd,
                   iv_detection_flag flag = IGNORE_BRANCH);
    static bool inLoop(LoopTree * tree, Opnd * opnd);
    static bool inExactLoop(LoopTree * tree, Opnd * opnd,
                LoopNode * curnode);
    static void writeHeaderToResult(OSROpndInfo & result,
                    LoopTree * tree, OSROpndInfo info1,
                    OSROpndInfo info2);
};

class OSR {
public:
    OSR(IRManager & irManager0, MemoryManager & memManager,
    LoopTree * loop_Tree, DominatorTree * dtree);
    void runPass();

private:
    SsaOpnd * iv;
    SsaOpnd *rc;

    struct OldInst {
        Type* type;
        VarOpnd* var;
        SsaOpnd* ssa;

        bool operator<(OldInst other) const {
            return ((POINTER_SIZE_INT) type + (POINTER_SIZE_SINT) var + (POINTER_SIZE_SINT) ssa) <
            ((POINTER_SIZE_INT) other.type + (POINTER_SIZE_SINT) other.var + (POINTER_SIZE_SINT) other.ssa);
        }
    };

    typedef std::pair < OldInst, Operation > Entry;
    IRManager& irManager;
    MemoryManager& mm;
    LoopTree* loopTree;
    CSEHashTable* hashTable;
    DominatorTree* dominators;
    StlHashMap < SsaOpnd*, SsaOpnd* >leading_operands;

    struct EntryComparison {
        bool operator() (Entry x1, Entry x2) const {
            return std::less < OldInst > () (x1.first, x2.first);
        }
    };

    struct reduceCand {
        reduceCand(SsaOpnd * dst, SsaOpnd * iv, SsaOpnd * rc) {
            this->dst = dst;
            this->iv = iv;
            this->rc = rc;
        } SsaOpnd *iv;
        SsaOpnd *rc;
        SsaOpnd *dst;
    };

    StlMap < Entry, VarOpnd*, EntryComparison > addedOpnds;
    StlVector < reduceCand > cands;

    typedef std::pair < Operation, SsaOpnd* >OperationSsaOpnd;
    typedef std::pair < OperationSsaOpnd, SsaOpnd* >LFTREntry;
    StlHashMap < SsaOpnd *, LFTREntry > LFTRHashMap;

    void writeLeadingOperand(SsaOpnd* opnd, SsaOpnd* header);
    SsaOpnd *getLeadingOperand(SsaOpnd* opnd);
    void replace(SsaOpnd* opnd, SsaOpnd* iv, SsaOpnd* rc);
    SsaOpnd *reduce(Type* type, Opcode opcode, Operation op,
            SsaOpnd* iv, SsaOpnd* rc);
    Inst *lookupReducedDefinition(Operation op, SsaOpnd* iv,
                  SsaOpnd* rc);
    Inst *copyInst(Type* type, Inst* oldDef, SsaOpnd* rc, Operation op);
    void insertInst(Inst * toinsert, Inst * where);
    SsaOpnd *apply(Type* type, Opcode opcode, Operation op,
           SsaOpnd* opnd1, SsaOpnd * opnd2);
    SsaVarOpnd *makeVar(SsaOpnd* opnd, SsaVarOpnd* var, Inst* place);
    SsaTmpOpnd *makeTmp(SsaOpnd* opnd, Inst* place);
    VarOpnd *createOperand(Type* newType, VarOpnd* var, SsaOpnd* rc,
               Operation op);
    bool isLoopInvariant(SsaOpnd * name);
    void writeLFTR(SsaOpnd* iv, Operation op, SsaOpnd*  loop_inv,
           SsaOpnd* result);
    void replaceLinearFuncTest(StlVector < Node* >&postOrderNodes);
    void performLFTR(Inst* inst);
    SsaOpnd *followEdges(SsaOpnd* iv);
    SsaOpnd *applyEdges(SsaOpnd* iv, SsaOpnd* bound);
    void writeInst(Inst* inst);
    Inst *insertNewDef(Type* type, SsaOpnd* iv, SsaOpnd* rc);
    void replaceOperands(Type* type, Inst* newDef, SsaOpnd* iv,
             SsaOpnd* rc, Opcode opcode, Operation op);
    void findLeadingOpnd(Inst* newDef, SsaOpnd* opnd);
    void replaceOperand(U_32 num, Inst* newDef, SsaOpnd* o,
            Opnd* lead, Node* leadBlock, Type* type,
            Opcode opcode, SsaOpnd* rc, Operation op);
    Inst *findInsertionPlace(SsaOpnd* opnd2, SsaOpnd* opnd1);
    void recordIVRC(Inst* inst);
    Inst *chooseLocationForConvert(Inst* inst, Inst* place);
    Inst *createNewVarInst(SsaOpnd* oldDst, Type* type,
               Inst* oldDef, SsaOpnd* rc, Operation op);
    bool isNoArrayInLoop(LoopNode* lnode, SsaOpnd* iv);
};

}
#endif