LoopIndVar.cpp

#include "LoopIndVar.h"
#include "LoopDetection.h"
#include "LoopInvariantAnalysis.h"

using namespace ir;

bool LoopInductionVariableAnalysis::fitPattern(Ptr<PhiInst> phiNode, Value val, Value destReg, Ptr<Loop> loop) {
    if (!val.isRegister()) {
        return false;
    }
    if (phiNode->destReg() == val.getRegister()) {
        for (auto inEdge : phiNode->parentBB()->inEdges()) {
            if (inEdge->getCopySrcVal(phiNode) == destReg) {
                continue;
            } else {
                if (loop->bbs().count(inEdge->src()) != 0) {
                    return false;
                }
            }
        }
    } else {
        return false;
    }
    return true;
}
// TODO: handle the initial value of branching variable
// for example, if b = phi [a : a bb in the loop, others : b = a +/- c],
// then we can have the conclusion that a is the initial value of b is a +/- c
// so we need to handle the initial value of b that was defined outside of the loop
Value handleInitialValue(Ptr<PhiInst> phiNode, Value val, Value destReg, Ptr<Loop> loop) {
    auto preHeaderBB = loop->preheaderBB();
    if (!preHeaderBB || preHeaderBB == loop->headerBB()->parentFunc()->entryBB()) {
        loop->createNewPreheaderBB();
    }
    if (phiNode->destReg() == val.getRegister()) {
        for (auto inEdge : phiNode->parentBB()->inEdges()) {
            if (inEdge->getCopySrcVal(phiNode) == destReg) {
                continue; // skip the edge that comes from the loop
            } else {
                auto inBB = inEdge->src();
                auto inVal = inEdge->getCopySrcVal(phiNode);
                if (inVal.isLiteral()) {
                    return inVal;
                }
            }
        }
    }
    return Value();
}

// we assume that all basic induction variable fit phi pattern*:
//
// phi pattern:
//
// ----------
// loop headerBB : phiNodes
// b = phi [a : a bb in the loop, others : none of them comes from a bb in the loop]
// ----------
// loop body : add or sub operInst
// a = b +/- e
// (e is invariant)
// ----------
// then we can have the conclusion that a and b are both basic induction variable
//
// so the way to inplement the algorithm to find basci induction variable :
// 1. find an add or sub instruction
// 2. look for loop headerBB's all inedge
// 3. confirm that only one edge comes from loop'bb
// the following function finds the basic induction variable in a loop
void LoopInductionVariableAnalysis::findBasicIndVar(Ptr<Loop> loop) {