StackAliasAnalyzer Class Reference

#include <StackAliasAnalyzer.hh>

Inheritance diagram for StackAliasAnalyzer:

Collaboration diagram for StackAliasAnalyzer:

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

Static Public Member Functions
static bool	getStackOffset (DataDependenceGraph &ddg, const ProgramOperation &pop, long &offset, long &loopIncrement, const TCEString &sp_)

Private Attributes
std::map< int, std::pair< long, long > >	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 StackAliasAnalyzer.hh.

Constructor & Destructor Documentation

StackAliasAnalyzer()

StackAliasAnalyzer::StackAliasAnalyzer

(

const TCEString &

sp

)

Definition at line 236 of file StackAliasAnalyzer.cc.

                                                          : sp_(sp) {
}

~StackAliasAnalyzer()

StackAliasAnalyzer::~StackAliasAnalyzer

(

)

Definition at line 234 of file StackAliasAnalyzer.cc.

{}

Member Function Documentation

analyze()

MemoryAliasAnalyzer::AliasingResult StackAliasAnalyzer::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 182 of file StackAliasAnalyzer.cc.

                                                               {
 
    long addr1, addr2;
    long incr1, incr2;
    auto i = offsetData_.find(pop1.poId());
    if (i != offsetData_.end()) {
        if (i->second.first != INT_MAX) {
            addr1 = i->second.first;
            incr1 = i->second.second;
        } else {
            return ALIAS_UNKNOWN;
        }
    } else {
        if (!(getStackOffset(ddg, pop1, addr1, incr1, sp_))) {
            offsetData_[pop1.poId()] = std::make_pair(INT_MAX, incr1);
            return ALIAS_UNKNOWN;
        } else {
            offsetData_[pop1.poId()] = std::make_pair(addr1, incr1);
        }
    }
 
    i = offsetData_.find(pop2.poId());
    if (i != offsetData_.end()) {
        if (i->second.first != INT_MAX) {
            addr2 = i->second.first;
            incr2 = i->second.second;
        } else {
            return ALIAS_UNKNOWN;
        }
    } else {
        if (!(getStackOffset(ddg, pop2, addr2, incr2, sp_))) {
            offsetData_[pop2.poId()] = std::make_pair(INT_MAX, incr2);
            return ALIAS_UNKNOWN;
        } else {
            offsetData_[pop2.poId()] = std::make_pair(addr2, incr2);
        }
 
    }
 
    if (incr1 != incr2) {
        return ALIAS_UNKNOWN;
    }
 
    if (bbRel != MoveNodeUse::LOOP) {
        return compareIndeces(addr1, addr2, pop1, pop2);
    } else {
        return compareIndeces(addr1 + incr1, addr2, pop1, pop2);
    }
}

References MoveNodeUse::LOOP, and ProgramOperation::poId().

Here is the call graph for this function:

getStackOffset()

bool StackAliasAnalyzer::getStackOffset ( DataDependenceGraph &  ddg, const ProgramOperation &  pop, long &  stackOffset, long &  loopIncrement, const TCEString &  sp  )

static

Gets stack offset of a move which is transporting an address.

Parameters

ddg	DDG where to track the address from.
node	Node which transfers the address.
stackOffset	place where to return the stack offset.

Returns

true if can calculate stack offset, false if not stack offset.

Definition at line 90 of file StackAliasAnalyzer.cc.

                                                                 {
 
    stackOffset = 0;
    loopIncrement = 0;
 
    // TODO: support for base+offset ops here.
 
    const MoveNode* mn = addressOperandMove(pop);
    if (mn == NULL) {
 
        int offsetMul = 0;
        TwoPartAddressOperandDetection addressParts =
            findTwoPartAddressOperands(pop);
        switch(addressParts.offsetOperation) {
        case TwoPartAddressOperandDetection::ADD:
            offsetMul = 1;
            break;
        case TwoPartAddressOperandDetection::SUB:
            offsetMul = -1;
            break;
        case 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.isSourceConstant()) {
            int offsetVal = addr1.move().source().value().intValue();
            stackOffset += (offsetMul * offsetVal);
            mn = &addr2;
        }
        
        if (addr2.isSourceConstant()) {
            int offsetVal = addr2.move().source().value().intValue();
            stackOffset += (offsetMul * offsetVal);
            mn = &addr1;
        }
    }
 
    while(mn != NULL && mn->isMove()) {
        if (mn->isSourceVariable()) {
            if (mn->isSourceReg(sp)) {
                return true;
            }
 
            MoveNode* prevSrc = ddg.onlyRegisterRawSource(*mn,2,2);
            MoveNode* loopSrc = ddg.onlyRegisterRawSource(*mn,2,1);
            // borken ddg??
            if (prevSrc == NULL) {
                break;
            }
            if (loopSrc) {
                if (!findIncrement(*loopSrc, loopIncrement)) {
                    return false;
                }
            } 
            mn = prevSrc;
        } else {
            if (mn->isSourceOperation()) {
                const MoveNode* incrementInput = findIncrement(*mn, stackOffset);
                mn = incrementInput;
            } else {
                return false;
            }
        }
    }
    return false;
}

References MoveNodeSet::at(), MoveNodeSet::count(), ProgramOperation::inputNode(), SimValue::intValue(), MoveNode::isMove(), MoveNode::isSourceConstant(), MoveNode::isSourceOperation(), MoveNode::isSourceReg(), MoveNode::isSourceVariable(), MoveNode::move(), MemoryAliasAnalyzer::TwoPartAddressOperandDetection::offsetOperation, DataDependenceGraph::onlyRegisterRawSource(), MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand1, MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand2, TTAProgram::Move::source(), and TTAProgram::Terminal::value().

Referenced by GlobalVsStackAA::analyze(), and GlobalVsStackAA::isAddressTraceable().

Here is the call graph for this function:

isAddressTraceable()

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

virtual

Checks if the node contains an adress that is an stack 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 62 of file StackAliasAnalyzer.cc.

                                                           {
    auto i = offsetData_.find(pop.poId());
    if (i != offsetData_.end()) {
        return i->second.first != INT_MAX;
    } else {
        long tmp, tmp2;
        bool analyzable = getStackOffset(ddg, pop, tmp, tmp2, sp_);
        if (analyzable) {
            offsetData_[pop.poId()] = std::make_pair(tmp,tmp2);
            return true;
        } else {
            offsetData_[pop.poId()] = std::make_pair(INT_MAX,tmp2);
            return false;
        }
    }
    return false;
}

References ProgramOperation::poId().

Here is the call graph for this function:

Member Data Documentation

offsetData_

std::map<int, std::pair<long, long> > StackAliasAnalyzer::offsetData_

private

Definition at line 62 of file StackAliasAnalyzer.hh.

sp_

TCEString StackAliasAnalyzer::sp_

private

Definition at line 64 of file StackAliasAnalyzer.hh.

---

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

• StackAliasAnalyzer.hh
• StackAliasAnalyzer.cc