MemoryAliasAnalyzer Class Reference

#include <MemoryAliasAnalyzer.hh>

Inheritance diagram for MemoryAliasAnalyzer:

Collaboration diagram for MemoryAliasAnalyzer:

Classes
struct	TwoPartAddressOperandDetection

Public Types
enum	AliasingResult { ALIAS_FALSE = 0, ALIAS_TRUE = 1, ALIAS_UNKNOWN = 2, ALIAS_PARTIAL = 3 }

Public Member Functions
virtual void	initProcedure (TTAProgram::Procedure &)
virtual AliasingResult	analyze (DataDependenceGraph &ddg, const ProgramOperation &pop1, const ProgramOperation &pop2, MoveNodeUse::BBRelation bbInfo)=0
virtual bool	isAddressTraceable (DataDependenceGraph &ddg, const ProgramOperation &pop)=0
virtual	~MemoryAliasAnalyzer ()

Protected Member Functions
AliasingResult	compareIndeces (int index1, int index2, const ProgramOperation &pop1, const ProgramOperation &pop2)

Static Protected Member Functions
static const MoveNode *	addressOperandMove (const ProgramOperation &po)
static TwoPartAddressOperandDetection	findTwoPartAddressOperands (const ProgramOperation &po)
static const MoveNode *	searchLoopIndexBasedIncrement (DataDependenceGraph &ddg, const MoveNode &mn, long &loopIncrement)
static const MoveNode *	findIncrement (const MoveNode &mn, long &increment)
static const MoveNode *	detectConstantScale (const MoveNode &mn, int &shiftAmount)

Private Member Functions
unsigned int	mausOfOperation (const Operation &op)

Detailed Description

Definition at line 47 of file MemoryAliasAnalyzer.hh.

Member Enumeration Documentation

AliasingResult

enum MemoryAliasAnalyzer::AliasingResult

Enumerator
ALIAS_FALSE
ALIAS_TRUE
ALIAS_UNKNOWN
ALIAS_PARTIAL

Definition at line 50 of file MemoryAliasAnalyzer.hh.

                        { ALIAS_FALSE = 0,
                          // Only Use ALIAS_TRUE if they really fully alias.
                          // It's used for transitivity optimizations.
                          ALIAS_TRUE  = 1,
                          ALIAS_UNKNOWN = 2,
                          ALIAS_PARTIAL = 3};

Constructor & Destructor Documentation

~MemoryAliasAnalyzer()

virtual MemoryAliasAnalyzer::~MemoryAliasAnalyzer ( )

inlinevirtual

Definition at line 75 of file MemoryAliasAnalyzer.hh.

{}

Member Function Documentation

addressOperandMove()

const MoveNode * MemoryAliasAnalyzer::addressOperandMove ( const ProgramOperation &  po )

staticprotected

Gets the direct address-writing move of a ProgramOperation which is a memory operation.

If none found, return null

Parameters

po	programOperation whose address write move is being searched.

Returns

MoveNode which writes address to a mem operation or NULL.

Definition at line 147 of file MemoryAliasAnalyzer.cc.

                                {
    const Operation& op = po.operation();
 
    // no mem address if does not use memory
    if (!op.usesMemory()) {
        return NULL;
    }
 
    // loops thru all inputs, checks if it is an address.
    // the index for op.input() starts from 0
    for (int i = 0, inputCount = op.numberOfInputs() ; i < inputCount; i++) {
        Operand& operand = op.input(i);
        if (operand.isAddress()) {
            // the index for po.inpuNode starts from 0 , so add +1
            MoveNodeSet& mns = po.inputNode(i+1);
            if (mns.count() != 1) {
                return NULL;
            } else {
                return &mns.at(0);
            }
        }
    }
    return NULL;
}

References MoveNodeSet::at(), MoveNodeSet::count(), Operation::input(), ProgramOperation::inputNode(), Operand::isAddress(), Operation::numberOfInputs(), ProgramOperation::operation(), and Operation::usesMemory().

Here is the call graph for this function:

analyze()

virtual AliasingResult MemoryAliasAnalyzer::analyze ( DataDependenceGraph &  ddg, const ProgramOperation &  pop1, const ProgramOperation &  pop2, MoveNodeUse::BBRelation  bbInfo  )

pure virtual

Implemented in OffsetAliasAnalyzer, FalseAliasAnalyzer, LLVMAliasAnalyzer, StackAliasAnalyzer, ConstantAliasAnalyzer, PRegionAliasAnalyzer, and GlobalVsStackAA.

Referenced by DataDependenceGraphBuilder::analyzeMemoryAlias().

compareIndeces()

MemoryAliasAnalyzer::AliasingResult MemoryAliasAnalyzer::compareIndeces ( int  index1, int  index2, const ProgramOperation &  pop1, const ProgramOperation &  pop2  )

protected

Compares two indeces (memory addresses or part of memory address). Checks memory operand size and return unknown for partial alias.

This methods takes care of checking memory access size and handling partial aliasing (returning unknown for those)

Parameters

index1	first index to compare
index2	second index to compare
mn1	first node
mn2	second node

Returns

true if alias, false if not alias, unknown for partial alias.

Definition at line 62 of file MemoryAliasAnalyzer.cc.

                                  {
    const Operation& op1 = pop1.operation();
    const Operation& op2 = pop2.operation();
 
    int maus1 = mausOfOperation(op1);
    int maus2 = mausOfOperation(op2);
 
    // unknown op? don't know how much memory it touches.
    if (maus1 == 0 || maus2 == 0) {
        return ALIAS_UNKNOWN;
    }
 
    // if addresses are the same.
    if (index1 == index2) {
        // partial? 
        if (maus1 != maus2) {
            return ALIAS_UNKNOWN;
        } else {
            return ALIAS_TRUE;
        }
    }
    
    int maus = std::max(maus1, maus2);
 
    // partial alias or not?
    if ((index1 & (~(maus-1))) == (index2 & (~(maus-1)))) {
        return ALIAS_UNKNOWN;
    } else {
        return ALIAS_FALSE;
    }
}

References ALIAS_FALSE, ALIAS_TRUE, ALIAS_UNKNOWN, mausOfOperation(), and ProgramOperation::operation().

Here is the call graph for this function:

detectConstantScale()

const MoveNode * MemoryAliasAnalyzer::detectConstantScale ( const MoveNode &  mn, int &  shiftAmount  )

staticprotected

Definition at line 389 of file MemoryAliasAnalyzer.cc.

                                                                                             {
    if (!mn.isSourceOperation()) {
        return NULL;
    }
    ProgramOperation& po = mn.sourceOperation();
    if (po.operation().name() != "SHL") {
        return NULL;
    }
    MoveNodeSet& input1Set = po.inputNode(1);
    MoveNodeSet& input2Set = po.inputNode(2);
    if (input1Set.count() != 1 || input2Set.count() != 1) {
        return NULL;
    }
    const MoveNode& input1 = input1Set.at(0);
    const MoveNode& input2 = input2Set.at(0);
    if (!input1.isSourceVariable() ||
        !input2.isSourceConstant()) {
        return NULL;
    }
    shiftAmount = input2.move().source().value().intValue();
    return &input1;
}

References MoveNodeSet::at(), MoveNodeSet::count(), ProgramOperation::inputNode(), SimValue::intValue(), MoveNode::isSourceConstant(), MoveNode::isSourceOperation(), MoveNode::isSourceVariable(), MoveNode::move(), Operation::name(), ProgramOperation::operation(), TTAProgram::Move::source(), MoveNode::sourceOperation(), and TTAProgram::Terminal::value().

Referenced by searchLoopIndexBasedIncrement().

Here is the call graph for this function:

findIncrement()

const MoveNode * MemoryAliasAnalyzer::findIncrement ( const MoveNode &  mn, long &  increment  )

staticprotected

Definition at line 273 of file MemoryAliasAnalyzer.cc.

                                                                                      {
    int myInc = 0;
    if (!mn.isSourceOperation()) {
        return NULL;
    }
 
    ProgramOperation& po = mn.sourceOperation();
    bool isSub = po.operation().name() == "SUB";
    bool isAdd = po.operation().name() == "ADD";
    if (!isSub && !isAdd) {
        return NULL;
    }
 
    // is add or sub
    MoveNodeSet& input1Set = po.inputNode(1);
    MoveNodeSet& input2Set = po.inputNode(2);
    if (input1Set.count() != 1 || input2Set.count() != 1) {
        return NULL;
    }
    MoveNode& input1 = input1Set.at(0);
    MoveNode& input2 = input2Set.at(0);
    MoveNode *immMove = NULL;
    MoveNode* varMove = NULL;
    if (input1.move().source().isGPR() &&
        input2.move().source().isImmediate()) {
        immMove = &input2;
        varMove = &input1;
    } else if (input2.move().source().isGPR() &&
               input1.move().source().isImmediate()) {
        // no sub by variable
        if (isSub) {
            return NULL;
        }
        immMove = &input1;
        varMove = &input2;
    } else { // not yet supported.
        return NULL;
    }
 
    myInc = immMove->move().source().value().intValue();
    if (isSub) {
        increment -= myInc;
    } else {
        increment += myInc;
    }
    return varMove;
}

References MoveNodeSet::at(), MoveNodeSet::count(), ProgramOperation::inputNode(), SimValue::intValue(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediate(), MoveNode::isSourceOperation(), MoveNode::move(), Operation::name(), ProgramOperation::operation(), TTAProgram::Move::source(), MoveNode::sourceOperation(), and TTAProgram::Terminal::value().

Referenced by OffsetAliasAnalyzer::analyzeLoopPtrIncrease(), and searchLoopIndexBasedIncrement().

Here is the call graph for this function:

findTwoPartAddressOperands()

MemoryAliasAnalyzer::TwoPartAddressOperandDetection MemoryAliasAnalyzer::findTwoPartAddressOperands ( const ProgramOperation &  po )

staticprotected

Definition at line 175 of file MemoryAliasAnalyzer.cc.

                                {
    
    TwoPartAddressOperandDetection result;
    //   std::set<int> operandIndeces;
    
    const Operation& op = po.operation();
    // TODO: assumes only one operation of dag uses memory.
    // like base + offset stores/loads.        
    for (int i = 0; i < op.dagCount(); i++) {
        OperationDAG& oDag = op.dag(i);
        OperationDAG::NodeSet tailNodes = oDag.endNodes();
        for (OperationDAG::NodeSet::iterator j = tailNodes.begin();
             j != tailNodes.end(); j++) {
            OperationDAGNode* n = *j;
            OperationNode* on = dynamic_cast<OperationNode*>(n);
            if (on == NULL) {
                continue;
            }
            Operation& tailOp = on->referencedOperation();
            if (!tailOp.usesMemory()) {
                continue;
            }
            int addrOperandNum = 0;
            for (int k = 0, inputCount = tailOp.numberOfInputs() ; 
                 k < inputCount; k++) {
                Operand& operand = tailOp.input(k);
                if (operand.isAddress()) {
                    addrOperandNum = k+1;
                }
            }
            if (addrOperandNum == 0) {
                continue;
            }
            
            // now we know the address operand of the mem op in dag.
            
            OperationDAGNode* addressSource = NULL;
            for (int k = 0; k < oDag.inDegree(*n); k++) {
                OperationDAGEdge& e = oDag.inEdge(*n,k);
                if (e.dstOperand() == addrOperandNum) {
                    addressSource = &oDag.tailNode(e);
                }
            }
            if (addressSource == NULL) {
                continue;
            }
            
            OperationNode* addrSrcOn = dynamic_cast<OperationNode*>(
                addressSource);
            if (addrSrcOn == NULL) {
                continue;
            }
            Operation& addrOp = addrSrcOn->referencedOperation();
            if (addrOp.name() == "add" ||
                addrOp.name() == "ADD") {
                result.offsetOperation = 
                    TwoPartAddressOperandDetection::ADD;
            } else {
                if (addrOp.name() == "sub" ||
                    addrOp.name() == "SUB") {
                    result.offsetOperation = 
                        TwoPartAddressOperandDetection::SUB;
                } else {
                    result.offsetOperation = 
                        TwoPartAddressOperandDetection::NOT_FOUND;
                    continue;
                }
            }
            OperationDAG::NodeSet addrInputs = oDag.predecessors(
                *addressSource);
            
            if (addrInputs.size() != 2) {
                result.clear();
                continue;
            }
            for (OperationDAG::NodeSet::iterator k = addrInputs.begin();
                 k != addrInputs.end(); k++) {
                TerminalNode* tn = dynamic_cast<TerminalNode*>(*k);
                if (tn == NULL) {
                    break;
                }
                if (result.operand1 == 0) {
                    result.operand1 = tn->operandIndex();
                } else {
                    result.operand2 = tn->operandIndex();
                }
            }
            if (result.operand2 != 0) {
                return result;
            } else {
                result.clear();
            }
        }
    }
    return result;
}

References MemoryAliasAnalyzer::TwoPartAddressOperandDetection::ADD, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::clear(), Operation::dag(), Operation::dagCount(), OperationDAGEdge::dstOperand(), OperationDAG::endNodes(), BoostGraph< GraphNode, GraphEdge >::inDegree(), BoostGraph< GraphNode, GraphEdge >::inEdge(), Operation::input(), Operand::isAddress(), Operation::name(), MemoryAliasAnalyzer::TwoPartAddressOperandDetection::NOT_FOUND, Operation::numberOfInputs(), MemoryAliasAnalyzer::TwoPartAddressOperandDetection::offsetOperation, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand1, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand2, TerminalNode::operandIndex(), ProgramOperation::operation(), BoostGraph< GraphNode, GraphEdge >::predecessors(), OperationNode::referencedOperation(), MemoryAliasAnalyzer::TwoPartAddressOperandDetection::SUB, BoostGraph< GraphNode, GraphEdge >::tailNode(), and Operation::usesMemory().

Here is the call graph for this function:

initProcedure()

virtual void MemoryAliasAnalyzer::initProcedure ( TTAProgram::Procedure &  )

inlinevirtual

Definition at line 57 of file MemoryAliasAnalyzer.hh.

{}

isAddressTraceable()

virtual bool MemoryAliasAnalyzer::isAddressTraceable ( DataDependenceGraph &  ddg, const ProgramOperation &  pop  )

pure virtual

Checks whether the analyzer knows anything about the address.

ie. if it can return true or false to some query concerning this address.

Returns

true if analyzer can know something about the address.

Implemented in FalseAliasAnalyzer, LLVMAliasAnalyzer, OffsetAliasAnalyzer, StackAliasAnalyzer, ConstantAliasAnalyzer, PRegionAliasAnalyzer, and GlobalVsStackAA.

mausOfOperation()

unsigned int MemoryAliasAnalyzer::mausOfOperation ( const Operation &  op )

private

Returns the size of memory operation memory access in mau's. if unknown, returns 0.

Definition at line 100 of file MemoryAliasAnalyzer.cc.

                                                        {
    
    // no mem address if does not use memory
    if (!op.usesMemory()) {
        throw InvalidData(__FILE__,__LINE__,__func__, "does not use mem!");
    }
 
    // loops thru all inputs, checks if it is address.
    // the index for op.input() starts from 0 
    for (int i = 0; i < op.numberOfInputs(); i++) {
        Operand& operand = op.input(i);
        if (operand.isAddress()) {
            return operand.memoryUnits();
        }
    }
 
    // TODO: assumes only operation of dag uses memory.
    // like base + offset stores/loads.
    for (int i = 0; i < op.dagCount(); i++) {
        OperationDAG& oDag = op.dag(i);
        OperationDAG::NodeSet tailNodes = oDag.endNodes();
        for (OperationDAG::NodeSet::iterator j = tailNodes.begin();
             j != tailNodes.end(); j++) {
            OperationDAGNode* n = *j;
            OperationNode* on = dynamic_cast<OperationNode*>(n);
            if (on != NULL) {
                Operation& tailOp = on->referencedOperation();
                if (tailOp.usesMemory()) {
                    return mausOfOperation(tailOp);
                }
            }
        }
    }
    // unknown or no specified
    return 0;
}

References __func__, Operation::dag(), Operation::dagCount(), OperationDAG::endNodes(), Operation::input(), Operand::isAddress(), Operand::memoryUnits(), Operation::numberOfInputs(), OperationNode::referencedOperation(), and Operation::usesMemory().

Referenced by compareIndeces().

Here is the call graph for this function:

searchLoopIndexBasedIncrement()

const MoveNode * MemoryAliasAnalyzer::searchLoopIndexBasedIncrement ( DataDependenceGraph &  ddg, const MoveNode &  mn, long &  loopIncrement  )

staticprotected

Definition at line 321 of file MemoryAliasAnalyzer.cc.

                                                                       {
 
    ProgramOperation& po = mn.sourceOperation();
    if (po.operation().name() != "ADD") return NULL;
 
    MoveNodeSet& input1Set = po.inputNode(1);
    MoveNodeSet& input2Set = po.inputNode(2);
    if (input1Set.count() != 1 || input2Set.count() != 1) {
        return NULL;
    }
    const MoveNode& input1 = input1Set.at(0);
    const MoveNode& input2 = input2Set.at(0);
 
    if (!input1.isSourceVariable() || !input2.isSourceVariable()) {
        return NULL;
    }
 
    const MoveNode* prevSrc2 = ddg.onlyRegisterRawSource(input2,2,2);
    const MoveNode* loopSrc2 = ddg.onlyRegisterRawSource(input2,2,1);
    if (prevSrc2 == NULL) {
        return NULL;
    }
 
    int loopMul = 1;
    if (!loopSrc2) {
        int shiftAmount;
        const MoveNode* loopIndex;
        if (( loopIndex = detectConstantScale(*prevSrc2, shiftAmount))) {
            prevSrc2 = ddg.onlyRegisterRawSource(*loopIndex,2,2);
            if (prevSrc2 == NULL) {
                return NULL;
            }
            loopMul <<= shiftAmount;
            if (!(loopSrc2 = ddg.onlyRegisterRawSource(*loopIndex,2,1))) {
                return NULL;
            }
        } else {
            return NULL;
        }
    }
 
    while (prevSrc2->isSourceVariable()) {
        prevSrc2 = ddg.onlyRegisterRawSource(*prevSrc2);
        if (prevSrc2 == NULL) {
            return NULL;
        }
    }
 
    // TODO: track over multiple copies
    if (!prevSrc2->isSourceConstant()) {
        return NULL;
    }
    int counterInit = prevSrc2->move().source().value().intValue();
    if (counterInit != 0) {
        return NULL;
    }
 
    long increment = 0;
    const MoveNode* baseOfInc = findIncrement(*loopSrc2, increment);
    if (!baseOfInc) {
        return NULL;
    }
    loopIncrement = increment * loopMul;
    // TODO: should check that the loop update really goes over the loop
    return &input1;
}

References MoveNodeSet::at(), MoveNodeSet::count(), detectConstantScale(), findIncrement(), ProgramOperation::inputNode(), SimValue::intValue(), MoveNode::isSourceConstant(), MoveNode::isSourceVariable(), MoveNode::move(), Operation::name(), DataDependenceGraph::onlyRegisterRawSource(), ProgramOperation::operation(), TTAProgram::Move::source(), MoveNode::sourceOperation(), and TTAProgram::Terminal::value().

Here is the call graph for this function:

---

The documentation for this class was generated from the following files:

• MemoryAliasAnalyzer.hh
• MemoryAliasAnalyzer.cc