OffsetAliasAnalyzer Class Reference

#include <OffsetAliasAnalyzer.hh>

Inheritance diagram for OffsetAliasAnalyzer:

Collaboration diagram for OffsetAliasAnalyzer:

Classes
struct	OffsetData

Public Member Functions
virtual bool	isAddressTraceable (DataDependenceGraph &ddg, const ProgramOperation &pop)
virtual AliasingResult	analyze (DataDependenceGraph &ddg, const ProgramOperation &pop1, const ProgramOperation &pop2, MoveNodeUse::BBRelation bbRelation)
	OffsetAliasAnalyzer (const TCEString &sp)
	~OffsetAliasAnalyzer ()
Public Member Functions inherited from MemoryAliasAnalyzer
virtual void	initProcedure (TTAProgram::Procedure &)
virtual	~MemoryAliasAnalyzer ()

Private Member Functions
bool	analyzeLoopPtrIncrease (const DataDependenceGraph &ddg, const MoveNode &mn, long &offset)
bool	sameLoopAndPrevSources (const DataDependenceGraph &ddg, const MoveNode &anc1, const MoveNode &anc2)

Private Attributes
std::map< int, OffsetData >	offsetData_
TCEString	sp_

Additional Inherited Members
Public Types inherited from MemoryAliasAnalyzer
enum	AliasingResult { ALIAS_FALSE = 0 , ALIAS_TRUE = 1 , ALIAS_UNKNOWN = 2 , ALIAS_PARTIAL = 3 }
Protected Member Functions inherited from MemoryAliasAnalyzer
AliasingResult	compareIndeces (int index1, int index2, const ProgramOperation &pop1, const ProgramOperation &pop2)
Static Protected Member Functions inherited from MemoryAliasAnalyzer
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)

Detailed Description

Definition at line 46 of file OffsetAliasAnalyzer.hh.

Constructor & Destructor Documentation

OffsetAliasAnalyzer()

OffsetAliasAnalyzer::OffsetAliasAnalyzer

(

const TCEString &

sp

)

Definition at line 492 of file OffsetAliasAnalyzer.cc.

                                                            : sp_(sp) {
}

~OffsetAliasAnalyzer()

OffsetAliasAnalyzer::~OffsetAliasAnalyzer

(

)

Definition at line 490 of file OffsetAliasAnalyzer.cc.

{}

Member Function Documentation

analyze()

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

virtual

Analyzes aliasing of two memory adderesses.

Checks if they are stack offsets and compares the offsets.

Parameters

ddg	ddg where they belong.
node1	first node to compare
another	anpther node to compare

Returns

ALIAS_TRUE if they alias, ALIAS_FALSE if they don't or ALIAS_UNKNOWN if cannot analyze.

Implements MemoryAliasAnalyzer.

Definition at line 166 of file OffsetAliasAnalyzer.cc.

                                                               {
    const MoveNode* anc1 = NULL;
    const MoveNode* anc2 = NULL;
    long offsetVal1 = 0;
    long offsetVal2 = 0;
 
    std::map<int,OffsetData>::const_iterator i = 
        offsetData_.find(pop1.poId());
    if (i != offsetData_.end()) {
        if (i->second.baseNode == NULL) {
            return ALIAS_UNKNOWN;
        } else {
            anc1 = i->second.baseNode;
            offsetVal1 = i->second.offset;
        }
    } else {
 
        const MoveNode* addrMove1 = addressOperandMove(pop1);
        if (addrMove1 == NULL) {
 
            int offsetMul = 0;
            TwoPartAddressOperandDetection addressParts =
                findTwoPartAddressOperands(pop1);
            switch(addressParts.offsetOperation) {
            case TwoPartAddressOperandDetection::ADD:
                offsetMul = 1;
                break;
            case TwoPartAddressOperandDetection::SUB:
                offsetMul = -1;
                break;
            case TwoPartAddressOperandDetection::NOT_FOUND:
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop1.poId(),OffsetData(NULL, INT_MAX)));
                return ALIAS_UNKNOWN;
            }
            
            MoveNodeSet& addr1Set = pop1.inputNode(addressParts.operand1);
            MoveNodeSet& addr2Set = pop1.inputNode(addressParts.operand2);
            if (addr1Set.count() != 1) {
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop1.poId(),OffsetData(NULL, INT_MAX)));
                return ALIAS_UNKNOWN;
            } 
            if (addr2Set.count() != 1) {
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop1.poId(),OffsetData(NULL, INT_MAX)));
                return ALIAS_UNKNOWN;
            }
            MoveNode& addr1 = addr1Set.at(0);
            MoveNode& addr2 = addr2Set.at(0);
            
            if (addr1.isSourceConstant() &&
                addr2.move().source().isGPR()) {
                anc1 = ddg.onlyRegisterRawAncestor(addr2, sp_);
                offsetVal1 = addr1.move().source().value().intValue() *
                    offsetMul;
            } else {
                if (addr2.isSourceConstant() &&
                    addr1.move().source().isGPR()) {
                    anc1 = ddg.onlyRegisterRawAncestor(addr1, sp_);
                    offsetVal1 = addr2.move().source().value().intValue() *
                        offsetMul;
                } else {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                        pop1.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                }
            }
 
            offsetData_.insert(
                std::pair<int,OffsetData>(
                    pop1.poId(),OffsetData(anc1, offsetVal1)));
 
        } else {
            // direct memory op. have to search for the add.
 
            // first find base and index of the first node.
            const MoveNode* rawSrc1 = 
                ddg.onlyRegisterRawAncestor(*addrMove1, sp_);
            
            if (!rawSrc1->isSourceOperation()) {
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop1.poId(),OffsetData(rawSrc1, 0)));
            } else {
            
            ProgramOperation& po1 = rawSrc1->sourceOperation();
            
            if (po1.operation().name() == "ADD" ||
                po1.operation().name() == "SUB") {
                
                
                // offset calc, add or sub. check for node2
                MoveNodeSet& baseSet1 = po1.inputNode(1);
                MoveNodeSet& offsetSet1 = po1.inputNode(2);
                
                if (baseSet1.count() != 1 || offsetSet1.count() != 1) {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop1.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                }
                
                MoveNode& offsetNode1 = offsetSet1.at(0);
                MoveNode& base1 = baseSet1.at(0);
                
                if (!base1.move().source().isGPR() ||
                    !offsetNode1.move().source().isImmediate()) {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop1.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                }
                
                offsetVal1 = offsetNode1.move().source().value().intValue();
                if (po1.operation().name() == "SUB") {
                    offsetVal1 = -offsetVal1;
                }
                
                anc1 = ddg.onlyRegisterRawAncestor(base1, sp_);
                // update cache.
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop1.poId(),OffsetData(anc1, offsetVal1)));
            } else {
                // comes directly from some untraceable op.
                if (ddg.regRawSuccessorCount(*rawSrc1, false) > 1) {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop1.poId(),OffsetData(rawSrc1, 0)));
                    anc1 = rawSrc1;
                    offsetVal1 = 0;
                } else {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop1.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                }
            }
            }
        }
    }
    // then find base and index for second node.
 
    //first search cache.
    i = offsetData_.find(pop2.poId());
    if (i != offsetData_.end()) {
        if (i->second.baseNode == NULL) {
            return ALIAS_UNKNOWN;
        } else {
            anc2 = i->second.baseNode;
            offsetVal2 = i->second.offset;
        }
    } else {
        const MoveNode* addrMove2 = addressOperandMove(pop2);
        if (addrMove2 == NULL) {
 
            int offsetMul = 0;
            TwoPartAddressOperandDetection addressParts =
                findTwoPartAddressOperands(pop2);
            switch(addressParts.offsetOperation) {
            case TwoPartAddressOperandDetection::ADD:
                offsetMul = 1;
                break;
            case TwoPartAddressOperandDetection::SUB:
                offsetMul = -1;
                break;
            case TwoPartAddressOperandDetection::NOT_FOUND:
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop2.poId(),OffsetData(NULL, INT_MAX)));
                return ALIAS_UNKNOWN;
            }
            
            MoveNodeSet& addr1Set = pop2.inputNode(addressParts.operand1);
            MoveNodeSet& addr2Set = pop2.inputNode(addressParts.operand2);
            if (addr1Set.count() != 1) {
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop2.poId(),OffsetData(NULL, INT_MAX)));
                return ALIAS_UNKNOWN;
            } 
            if (addr2Set.count() != 1) {
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop2.poId(),OffsetData(NULL, INT_MAX)));
                return ALIAS_UNKNOWN;
            }
            MoveNode& addr1 = addr1Set.at(0);
            MoveNode& addr2 = addr2Set.at(0);
            
            if (addr1.isSourceConstant() &&
                addr2.move().source().isGPR()) {
                anc2 = ddg.onlyRegisterRawAncestor(addr2, sp_);
                offsetVal2 = addr1.move().source().value().intValue() *
                    offsetMul;
            } else {
                if (addr2.isSourceConstant() &&
                    addr1.move().source().isGPR()) {
                    anc2 = ddg.onlyRegisterRawAncestor(addr1, sp_);
                    offsetVal2 = addr2.move().source().value().intValue() *
                        offsetMul;
                } else {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                        pop2.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                }
            }
 
            offsetData_.insert(
                std::pair<int,OffsetData>(
                    pop2.poId(),OffsetData(anc2, offsetVal2)));
        } else {
            // direct memory op. have to search for the add.
 
            // first find base and index of the first node.
            const MoveNode* rawSrc2 = 
                ddg.onlyRegisterRawAncestor(*addrMove2, sp_);
            
            if (!rawSrc2->isSourceOperation()) {
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop2.poId(),OffsetData(rawSrc2, 0)));
 
            } else {
            
            ProgramOperation& po2 = rawSrc2->sourceOperation();
            
            if (po2.operation().name() == "ADD" ||
                po2.operation().name() == "SUB") {
                
                // offset calc, add or sub. check for node2
                MoveNodeSet& baseSet2 = po2.inputNode(1);
                MoveNodeSet& offsetSet2 = po2.inputNode(2);
                
                if (baseSet2.count() != 1 || offsetSet2.count() != 1) {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop2.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                } 
                
                MoveNode& offsetNode2 = offsetSet2.at(0);
                MoveNode& base2 = baseSet2.at(0);
                
                // check that base is register coming from same place.
                
                if (!base2.move().source().isGPR() ||
                    !offsetNode2.move().source().isImmediate()) {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop2.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                }
                
                offsetVal2 = offsetNode2.move().source().value().intValue();
                if (po2.operation().name() == "SUB") {
                    offsetVal2 = -offsetVal2;
                }
                
                anc2 = ddg.onlyRegisterRawAncestor(base2, sp_);
                // update cache.
                offsetData_.insert(
                    std::pair<int,OffsetData>(
                        pop2.poId(),OffsetData(anc2, offsetVal2)));
            } else {
                // comes directly from some untraceable op.
                if (ddg.regRawSuccessorCount(*rawSrc2, false) > 1) {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop2.poId(),OffsetData(rawSrc2, 0)));
                    anc2 = rawSrc2;
                    offsetVal2 = 0;
                } else {
                    offsetData_.insert(
                        std::pair<int,OffsetData>(
                            pop2.poId(),OffsetData(NULL, INT_MAX)));
                    return ALIAS_UNKNOWN;
                }
            }
            }
        }
    }
    // now we have the defining move for base and offset. compare them
 
    if (anc1 == NULL || anc2 == NULL) {
        return ALIAS_UNKNOWN;
    }
 
    if (anc1 == anc2 || sameLoopAndPrevSources(ddg, *anc1, *anc2)) {
 
        if (bbRel == MoveNodeUse::LOOP) {
            if (!analyzeLoopPtrIncrease(ddg, *anc2, offsetVal2)) {
                return ALIAS_UNKNOWN;
            }
        }
        
        AliasingResult res = compareIndeces(
            offsetVal1, offsetVal2, pop1, pop2);
        
        return res;
    }
    return ALIAS_UNKNOWN;
}

References MemoryAliasAnalyzer::addressOperandMove(), MemoryAliasAnalyzer::ALIAS_UNKNOWN, analyzeLoopPtrIncrease(), MoveNodeSet::at(), MemoryAliasAnalyzer::compareIndeces(), MoveNodeSet::count(), MemoryAliasAnalyzer::findTwoPartAddressOperands(), ProgramOperation::inputNode(), SimValue::intValue(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediate(), MoveNode::isSourceConstant(), MoveNode::isSourceOperation(), MoveNodeUse::LOOP, MoveNode::move(), Operation::name(), offsetData_, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::offsetOperation, DataDependenceGraph::onlyRegisterRawAncestor(), MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand1, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand2, ProgramOperation::operation(), ProgramOperation::poId(), DataDependenceGraph::regRawSuccessorCount(), sameLoopAndPrevSources(), TTAProgram::Move::source(), MoveNode::sourceOperation(), sp_, and TTAProgram::Terminal::value().

Here is the call graph for this function:

analyzeLoopPtrIncrease()

bool OffsetAliasAnalyzer::analyzeLoopPtrIncrease ( const DataDependenceGraph &  ddg, const MoveNode &  mn, long &  offset  )

private

Definition at line 495 of file OffsetAliasAnalyzer.cc.

                                                                      {
 
    MoveNode* prevSrc = ddg.onlyRegisterRawSource(mn,2,2);
    MoveNode* loopSrc = ddg.onlyRegisterRawSource(mn,2,1);
    // does not change in loop?
    if (loopSrc == NULL) {
        return true;
    }
 
    if (prevSrc == NULL) {
        return false;
    }
    return findIncrement(*loopSrc, offset);
}

References MemoryAliasAnalyzer::findIncrement(), and DataDependenceGraph::onlyRegisterRawSource().

Referenced by analyze().

Here is the call graph for this function:

isAddressTraceable()

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

virtual

Checks if the node contains an adress that is an offset.

Parameters

ddg	DDG where to analyze from
mn	the node being checked

Returns

true if is a traceable stack offset, false if not.

Implements MemoryAliasAnalyzer.

Definition at line 59 of file OffsetAliasAnalyzer.cc.

                                                           {
 
    std::map<int,OffsetData>::iterator i = offsetData_.find(pop.poId());
    if (i != offsetData_.end()) {
        if (i->second.baseNode == NULL) {
            return false;
        } else {
            return true;
        }
    }
 
    const MoveNode* addrMove = addressOperandMove(pop);
    if (addrMove == NULL) {
 
        TwoPartAddressOperandDetection addressParts =
            findTwoPartAddressOperands(pop);
        if (addressParts.offsetOperation == 
            TwoPartAddressOperandDetection::NOT_FOUND) {
            return false;
        }
        
        MoveNodeSet& addr1Set = pop.inputNode(addressParts.operand1);
        MoveNodeSet& addr2Set = pop.inputNode(addressParts.operand2);
        if (addr1Set.count() != 1) {
            return false;
        } 
        if (addr2Set.count() != 1) {
            return false;
        }
        MoveNode& addr1 = addr1Set.at(0);
        MoveNode& addr2 = addr2Set.at(0);
 
        if ((addr1.move().source().isImmediate() &&
             addr2.move().source().isGPR()) ||
            (addr2.move().source().isImmediate() &&
             addr1.move().source().isGPR())) {
            return true;
        } else {
            return false;
        }
    }
    
    // first find base and index of the first node.
    const MoveNode* rawSrc = ddg.onlyRegisterRawAncestor(*addrMove, sp_);
        
    if (!rawSrc->isSourceOperation()) {
        offsetData_.insert(
            std::pair<int,OffsetData>(
                pop.poId(),OffsetData(rawSrc, 0)));
        return true;
    }
 
    ProgramOperation& po = rawSrc->sourceOperation();
 
    if (po.operation().name() != "ADD" &&
        po.operation().name() != "SUB") {
        if (ddg.regRawSuccessorCount(*rawSrc, false) > 1) {
            offsetData_.insert(
                std::pair<int,OffsetData>(
                    pop.poId(),OffsetData(rawSrc, 0)));
            return true;
        } else {
            offsetData_.insert(
                std::pair<int,OffsetData>(
                    pop.poId(),OffsetData(NULL, INT_MAX)));
            return false;
        }
    }
 
    // offset calc, add or sub. check for node2
    MoveNodeSet& baseSet = po.inputNode(1);
    MoveNodeSet& offsetSet = po.inputNode(2);
    
    if (baseSet.count() != 1 || offsetSet.count() != 1) {
        offsetData_.insert(
            std::pair<int,OffsetData>(
                pop.poId(),OffsetData(NULL, INT_MAX)));
        return false;
    } 
 
    MoveNode& offsetNode = offsetSet.at(0);
    MoveNode& base = baseSet.at(0);
 
    if (!base.move().source().isGPR() || 
        !offsetNode.move().source().isImmediate()) {
        offsetData_.insert(
            std::pair<int,OffsetData>(
                pop.poId(), OffsetData(NULL, INT_MAX)));
        return false;
    }
 
    return true;
}

References MemoryAliasAnalyzer::addressOperandMove(), MoveNodeSet::at(), MoveNodeSet::count(), MemoryAliasAnalyzer::findTwoPartAddressOperands(), ProgramOperation::inputNode(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediate(), MoveNode::isSourceOperation(), MoveNode::move(), Operation::name(), offsetData_, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::offsetOperation, DataDependenceGraph::onlyRegisterRawAncestor(), MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand1, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand2, ProgramOperation::operation(), ProgramOperation::poId(), DataDependenceGraph::regRawSuccessorCount(), TTAProgram::Move::source(), MoveNode::sourceOperation(), and sp_.

Here is the call graph for this function:

sameLoopAndPrevSources()

bool OffsetAliasAnalyzer::sameLoopAndPrevSources ( const DataDependenceGraph &  ddg, const MoveNode &  anc1, const MoveNode &  anc2  )

private

Definition at line 478 of file OffsetAliasAnalyzer.cc.

                                                                                {
 
    MoveNode* prevSrc1 = ddg.onlyRegisterRawSource(anc1,2,2);
    MoveNode* loopSrc1 = ddg.onlyRegisterRawSource(anc1,2,1);
    MoveNode* prevSrc2 = ddg.onlyRegisterRawSource(anc2,2,2);
    MoveNode* loopSrc2 = ddg.onlyRegisterRawSource(anc2,2,1);
 
    return (prevSrc1 == prevSrc2 && loopSrc1 == loopSrc2 &&
            prevSrc1 != NULL);
}

References DataDependenceGraph::onlyRegisterRawSource().

Referenced by analyze().

Here is the call graph for this function:

Member Data Documentation

offsetData_

std::map<int,OffsetData> OffsetAliasAnalyzer::offsetData_

private

Definition at line 69 of file OffsetAliasAnalyzer.hh.

Referenced by analyze(), and isAddressTraceable().

sp_

TCEString OffsetAliasAnalyzer::sp_

private

Definition at line 71 of file OffsetAliasAnalyzer.hh.

Referenced by analyze(), and isAddressTraceable().

---

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

• OffsetAliasAnalyzer.hh
• OffsetAliasAnalyzer.cc