InnerLoopFinder Struct Reference

#include <InnerLoopFinder.hh>

Inheritance diagram for InnerLoopFinder:

Collaboration diagram for InnerLoopFinder:

Classes
class	InnerLoopInfo

Public Types
typedef std::map< std::string, std::ostream * >	DumpFileIndex
typedef std::map< const llvm::BasicBlock *, InnerLoopInfo >	InnerLoopInfoIndex

Public Member Functions
	InnerLoopFinder ()
	~InnerLoopFinder ()
virtual void	getAnalysisUsage (llvm::AnalysisUsage &AU) const
std::ostream &	out (llvm::Loop *l)
virtual std::string	loopDescription (llvm::Loop *l)
virtual bool	runOnLoop (llvm::Loop *l, llvm::LPPassManager &LPM)
unsigned	getSmallConstantTripCount (llvm::Loop *loop)
InnerLoopInfoIndex	innerLoopInfo ()

Public Attributes
DumpFileIndex	dumpFiles
bool	dump

Static Public Attributes
static char	ID = 0

Private Attributes
InnerLoopInfoIndex	loopInfos_

Detailed Description

Definition at line 28 of file InnerLoopFinder.hh.

Member Typedef Documentation

DumpFileIndex

typedef std::map<std::string, std::ostream*> InnerLoopFinder::DumpFileIndex

Definition at line 30 of file InnerLoopFinder.hh.

InnerLoopInfoIndex

typedef std::map<const llvm::BasicBlock*, InnerLoopInfo> InnerLoopFinder::InnerLoopInfoIndex

Definition at line 42 of file InnerLoopFinder.hh.

Constructor & Destructor Documentation

InnerLoopFinder()

InnerLoopFinder::InnerLoopFinder

(

)

Definition at line 93 of file InnerLoopFinder.cc.

                                 : 
    LoopPass(ID) {
    dump = DumpLoopInfo;
}

References DumpLoopInfo().

Here is the call graph for this function:

~InnerLoopFinder()

InnerLoopFinder::~InnerLoopFinder

(

)

Definition at line 110 of file InnerLoopFinder.cc.

                                  {
    // flush and close all loop info dump files
    if (dump) {
        for (DumpFileIndex::iterator i = dumpFiles.begin(); 
             i != dumpFiles.end(); ++i) {
            std::ostream* stream = (*i).second;
            stream->flush();
            delete stream;
        }
        dumpFiles.clear();
    }
}

References dump, and dumpFiles.

Member Function Documentation

getAnalysisUsage()

void InnerLoopFinder::getAnalysisUsage ( llvm::AnalysisUsage &  AU ) const

virtual

Definition at line 99 of file InnerLoopFinder.cc.

                                                             {
    AU.setPreservesCFG();
    AU.addRequiredID(llvm::LoopSimplifyID);
    AU.addRequiredID(llvm::LCSSAID);
    AU.addPreservedID(llvm::LCSSAID);
    AU.addRequired<llvm::LoopInfoWrapperPass>();
    AU.addRequired<llvm::ScalarEvolutionWrapperPass>();
    AU.addPreserved<llvm::LoopInfoWrapperPass>();
    AU.addPreserved<llvm::ScalarEvolutionWrapperPass>();
}

getSmallConstantTripCount()

unsigned InnerLoopFinder::getSmallConstantTripCount

(

llvm::Loop *

loop

)

Returns the trip count of the loop as a normal unsigned value, if possible.

Forwardported from LLVM 2.4. Returns 0 if the trip count is unknown or not constant. Will also return 0 if the trip count is very large (>= 2^32).

Definition at line 254 of file InnerLoopFinder.cc.

                                                         {
    ScalarEvolution *SE =
        &getAnalysis<llvm::ScalarEvolutionWrapperPass>().getSE();
    llvm::BasicBlock* loopLatch = loop->getLoopLatch();
    // In case of the forever loop in the exit() the latch does
    // not jump out of the loop and SE cannot analyze the trip count,
    // which is infinite in that case.
    if (loopLatch == NULL || !loop->isLoopExiting(loopLatch))
        return 0;
    return SE->getSmallConstantTripCount(loop, loopLatch);
}

Referenced by runOnLoop().

innerLoopInfo()

InnerLoopInfoIndex InnerLoopFinder::innerLoopInfo ( )

inline

Definition at line 58 of file InnerLoopFinder.hh.

{ return loopInfos_; }

References loopInfos_.

Referenced by llvm::LLVMTCEIRBuilder::buildTCECFG().

loopDescription()

std::string InnerLoopFinder::loopDescription ( llvm::Loop *  l )

virtual

Returns a textual description for the given loop.

Definition at line 152 of file InnerLoopFinder.cc.

                                            {
 
    if (l == NULL)
        return "[none]";
 
    std::ostringstream ss;
    assert(l->getHeader() != NULL);
    assert(l->getHeader()->getParent() != NULL);
    std::string curProcName = l->getHeader()->getParent()->getName().str();
    ss << "in " << curProcName << "()";
 
    return ss.str();
}

References assert.

Referenced by runOnLoop().

out()

std::ostream & InnerLoopFinder::out

(

llvm::Loop *

l

)

Returns a stream to dump the loop info to.

Definition at line 127 of file InnerLoopFinder.cc.

                                {
 
    assert(l != NULL);
    
    std::string moduleName = 
        l->getHeader()->getParent()->getParent()->getModuleIdentifier();
    std::string fName = moduleName + ".loopinfo.txt";
    if (moduleName == "<stdin>") {
        fName = "loopinfo.txt";
    }
 
    if (dumpFiles.find(moduleName) == dumpFiles.end()) {
        std::fstream* outStream = 
            new std::fstream(
                fName.c_str(),
                std::ios_base::out | std::ios_base::trunc);
        dumpFiles[moduleName] = outStream;
    }
    return *dumpFiles[moduleName];
}

References assert, and dumpFiles.

Referenced by runOnLoop().

runOnLoop()

bool InnerLoopFinder::runOnLoop ( llvm::Loop *  l, llvm::LPPassManager &  LPM  )

virtual

Saves trip counts of single basic block inner loops.

early exits?

Definition at line 170 of file InnerLoopFinder.cc.

                                                          {
 
    const std::vector<llvm::Loop*>& subLoops = l->getSubLoops();
 
    unsigned subLoopCount = subLoops.size();
    unsigned tripCount = getSmallConstantTripCount(l);
    unsigned bbCount = l->getBlocks().size();
 
 
    /// early exits?
    llvm::SmallVector<llvm::BasicBlock*, 10> exitingBlocks;
 
#if 0
    /*
      This caused an LLVM crash in test cases
      llvm-frontend/tests/{FloatEmulationTest,NewLib,softloat_lowering,HelloWorld}:
 
      /home/visit0r/src/llvm-2.3/include/llvm/Support/Casting.h:199: 
      typename llvm::cast_retty<To, From>::ret_type llvm::cast(const Y&) 
      [with X = llvm::BasicBlock, Y = llvm::Value*]: 
      Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.      
     */
    l->getExitingBlocks(exitingBlocks);
    unsigned exitingBlockCount = exitingBlocks.size();
#endif
 
    unsigned callCount = 0;
    if (subLoopCount == 0) {
    for (llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::
         block_iterator bb = 
                 l->block_begin(); bb != l->block_end(); ++bb) {
            llvm::BasicBlock& basicBlock = **bb;
            for (llvm::BasicBlock::iterator i = basicBlock.begin();  
                 i != basicBlock.end(); ++i) {
                llvm::Instruction& instruction = *i;
                if (instruction.getOpcode() == llvm::Instruction::Call)
                    ++callCount;
            }
        }
    }
 
    const bool innerLoop = 
        bbCount == 1 && subLoopCount == 0 && callCount == 0;
 
    if (innerLoop) {
        if (dump && tripCount > 0) {
            out(l) << "found an inner loop with trip count " 
                   << tripCount << std::endl;
        }
        assert(l->getBlocks().size() > 0);
 
        InnerLoopInfo loopInfo(tripCount);
        loopInfos_[l->getBlocks()[0]] = loopInfo;
    } 
 
    if (dump) {
        out(l) << "loop: " << loopDescription(l) << std::endl
               << "depth: " << l->getLoopDepth() << std::endl;
        out(l) << "sub loops: " << subLoopCount << std::endl;
        out(l) << "trip count: "; 
        if (tripCount != 0) {
            out(l) << "constant: " << tripCount;
        } else {
            out(l) << "unknown ";
        }
        out(l) << std::endl;
        out(l) << "basic blocks: " << bbCount << std::endl;
//        out(l) << "exiting blocks: " << exitingBlocks.size() << std::endl;
        if (subLoopCount == 0)
            out(l) << "calls: " << callCount << std::endl;
        out(l) << std::endl;
    }
    return false; // loop not modified
}

References assert, dump, getSmallConstantTripCount(), loopDescription(), loopInfos_, and out().

Here is the call graph for this function:

Member Data Documentation

dump

bool InnerLoopFinder::dump

Definition at line 45 of file InnerLoopFinder.hh.

Referenced by runOnLoop(), and ~InnerLoopFinder().

dumpFiles

DumpFileIndex InnerLoopFinder::dumpFiles

Definition at line 44 of file InnerLoopFinder.hh.

Referenced by out(), and ~InnerLoopFinder().

ID

find Finds info of the inner loops in the true char InnerLoopFinder::ID = 0

static

Definition at line 29 of file InnerLoopFinder.hh.

loopInfos_

InnerLoopInfoIndex InnerLoopFinder::loopInfos_

private

Definition at line 60 of file InnerLoopFinder.hh.

Referenced by innerLoopInfo(), and runOnLoop().

---

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

• InnerLoopFinder.hh
• InnerLoopFinder.cc