#include "llvm/InlineAsm.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
-#include "llvm/Target/TargetAsmInfo.h"
+#include "llvm/Analysis/ProfileInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetLowering.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Utils/AddrModeMatcher.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/PatternMatch.h"
+#include "llvm/Support/raw_ostream.h"
using namespace llvm;
using namespace llvm::PatternMatch;
cl::init(false), cl::Hidden);
namespace {
- class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass {
+ class CodeGenPrepare : public FunctionPass {
/// TLI - Keep a pointer of a TargetLowering to consult for determining
/// transformation profitability.
const TargetLowering *TLI;
+ ProfileInfo *PI;
/// BackEdges - Keep a set of all the loop back edges.
///
- SmallSet<std::pair<BasicBlock*,BasicBlock*>, 8> BackEdges;
+ SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges;
public:
static char ID; // Pass identification, replacement for typeid
explicit CodeGenPrepare(const TargetLowering *tli = 0)
: FunctionPass(&ID), TLI(tli) {}
bool runOnFunction(Function &F);
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addPreserved<ProfileInfo>();
+ }
+
private:
bool EliminateMostlyEmptyBlocks(Function &F);
bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
DenseMap<Value*,Value*> &SunkAddrs);
bool OptimizeInlineAsmInst(Instruction *I, CallSite CS,
DenseMap<Value*,Value*> &SunkAddrs);
+ bool MoveExtToFormExtLoad(Instruction *I);
bool OptimizeExtUses(Instruction *I);
- void findLoopBackEdges(Function &F);
+ void findLoopBackEdges(const Function &F);
};
}
/// findLoopBackEdges - Do a DFS walk to find loop back edges.
///
-void CodeGenPrepare::findLoopBackEdges(Function &F) {
- SmallPtrSet<BasicBlock*, 8> Visited;
- SmallVector<std::pair<BasicBlock*, succ_iterator>, 8> VisitStack;
- SmallPtrSet<BasicBlock*, 8> InStack;
-
- BasicBlock *BB = &F.getEntryBlock();
- if (succ_begin(BB) == succ_end(BB))
- return;
- Visited.insert(BB);
- VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
- InStack.insert(BB);
- do {
- std::pair<BasicBlock*, succ_iterator> &Top = VisitStack.back();
- BasicBlock *ParentBB = Top.first;
- succ_iterator &I = Top.second;
-
- bool FoundNew = false;
- while (I != succ_end(ParentBB)) {
- BB = *I++;
- if (Visited.insert(BB)) {
- FoundNew = true;
- break;
- }
- // Successor is in VisitStack, it's a back edge.
- if (InStack.count(BB))
- BackEdges.insert(std::make_pair(ParentBB, BB));
- }
-
- if (FoundNew) {
- // Go down one level if there is a unvisited successor.
- InStack.insert(BB);
- VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
- } else {
- // Go up one level.
- std::pair<BasicBlock*, succ_iterator> &Pop = VisitStack.back();
- InStack.erase(Pop.first);
- VisitStack.pop_back();
- }
- } while (!VisitStack.empty());
+void CodeGenPrepare::findLoopBackEdges(const Function &F) {
+ SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
+ FindFunctionBackedges(F, Edges);
+
+ BackEdges.insert(Edges.begin(), Edges.end());
}
bool CodeGenPrepare::runOnFunction(Function &F) {
bool EverMadeChange = false;
+ PI = getAnalysisIfAvailable<ProfileInfo>();
// First pass, eliminate blocks that contain only PHI nodes and an
// unconditional branch.
EverMadeChange |= EliminateMostlyEmptyBlocks(F);
BranchInst *BI = cast<BranchInst>(BB->getTerminator());
BasicBlock *DestBB = BI->getSuccessor(0);
- DOUT << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB;
+ DEBUG(errs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
// If the destination block has a single pred, then this is a trivial edge,
// just collapse it.
// Remember if SinglePred was the entry block of the function. If so, we
// will need to move BB back to the entry position.
bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
- MergeBasicBlockIntoOnlyPred(DestBB);
+ MergeBasicBlockIntoOnlyPred(DestBB, this);
if (isEntry && BB != &BB->getParent()->getEntryBlock())
BB->moveBefore(&BB->getParent()->getEntryBlock());
- DOUT << "AFTER:\n" << *DestBB << "\n\n\n";
+ DEBUG(errs() << "AFTER:\n" << *DestBB << "\n\n\n");
return;
}
}
// The PHIs are now updated, change everything that refers to BB to use
// DestBB and remove BB.
BB->replaceAllUsesWith(DestBB);
+ if (PI) {
+ PI->replaceAllUses(BB, DestBB);
+ PI->removeEdge(ProfileInfo::getEdge(BB, DestBB));
+ }
BB->eraseFromParent();
- DOUT << "AFTER:\n" << *DestBB << "\n\n\n";
+ DEBUG(errs() << "AFTER:\n" << *DestBB << "\n\n\n");
}
/// predecessor of the succ that is empty (and thus has no phi nodes), use it
/// instead of introducing a new block.
static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum,
- SmallSet<std::pair<BasicBlock*,BasicBlock*>, 8> &BackEdges,
+ SmallSet<std::pair<const BasicBlock*,
+ const BasicBlock*>, 8> &BackEdges,
Pass *P) {
BasicBlock *TIBB = TI->getParent();
BasicBlock *Dest = TI->getSuccessor(SuccNum);
// If we found a workable predecessor, change TI to branch to Succ.
if (FoundMatch) {
+ ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>();
+ if (PI)
+ PI->splitEdge(TIBB, Dest, Pred);
Dest->removePredecessor(TIBB);
TI->setSuccessor(SuccNum, Pred);
return;
/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop
-/// copy (e.g. it's casting from one pointer type to another, int->uint, or
-/// int->sbyte on PPC), sink it into user blocks to reduce the number of virtual
+/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC),
+/// sink it into user blocks to reduce the number of virtual
/// registers that must be created and coalesced.
///
/// Return true if any changes are made.
///
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){
// If this is a noop copy,
- MVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
- MVT DstVT = TLI.getValueType(CI->getType());
+ EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
+ EVT DstVT = TLI.getValueType(CI->getType());
// This is an fp<->int conversion?
if (SrcVT.isInteger() != DstVT.isInteger())
// If these values will be promoted, find out what they will be promoted
// to. This helps us consider truncates on PPC as noop copies when they
// are.
- if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote)
- SrcVT = TLI.getTypeToTransformTo(SrcVT);
- if (TLI.getTypeAction(DstVT) == TargetLowering::Promote)
- DstVT = TLI.getTypeToTransformTo(DstVT);
+ if (TLI.getTypeAction(CI->getContext(), SrcVT) == TargetLowering::Promote)
+ SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
+ if (TLI.getTypeAction(CI->getContext(), DstVT) == TargetLowering::Promote)
+ DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
// If, after promotion, these are the same types, this is a noop copy.
if (SrcVT != DstVT)
BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI();
InsertedCmp =
- CmpInst::Create(CI->getOpcode(), CI->getPredicate(), CI->getOperand(0),
+ CmpInst::Create(CI->getOpcode(),
+ CI->getPredicate(), CI->getOperand(0),
CI->getOperand(1), "", InsertPt);
MadeChange = true;
}
return MadeChange;
}
-//===----------------------------------------------------------------------===//
-// Addressing Mode Analysis and Optimization
-//===----------------------------------------------------------------------===//
-
//===----------------------------------------------------------------------===//
// Memory Optimization
//===----------------------------------------------------------------------===//
// If all the instructions matched are already in this BB, don't do anything.
if (!AnyNonLocal) {
- DEBUG(cerr << "CGP: Found local addrmode: " << AddrMode << "\n");
+ DEBUG(errs() << "CGP: Found local addrmode: " << AddrMode << "\n");
return false;
}
// computation.
Value *&SunkAddr = SunkAddrs[Addr];
if (SunkAddr) {
- DEBUG(cerr << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
- << *MemoryInst);
+ DEBUG(errs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
+ << *MemoryInst);
if (SunkAddr->getType() != Addr->getType())
SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt);
} else {
- DEBUG(cerr << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
- << *MemoryInst);
- const Type *IntPtrTy = TLI->getTargetData()->getIntPtrType();
+ DEBUG(errs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
+ << *MemoryInst);
+ const Type *IntPtrTy =
+ TLI->getTargetData()->getIntPtrType(AccessTy->getContext());
Value *Result = 0;
// Start with the scale value.
}
if (AddrMode.Scale != 1)
V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy,
- AddrMode.Scale),
+ AddrMode.Scale),
"sunkaddr", InsertPt);
Result = V;
}
// Add in the base register.
if (AddrMode.BaseReg) {
Value *V = AddrMode.BaseReg;
- if (V->getType() != IntPtrTy)
+ if (isa<PointerType>(V->getType()))
V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt);
+ if (V->getType() != IntPtrTy)
+ V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true,
+ "sunkaddr", InsertPt);
if (Result)
Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt);
else
return MadeChange;
}
+/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same
+/// basic block as the load, unless conditions are unfavorable. This allows
+/// SelectionDAG to fold the extend into the load.
+///
+bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) {
+ // Look for a load being extended.
+ LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0));
+ if (!LI) return false;
+
+ // If they're already in the same block, there's nothing to do.
+ if (LI->getParent() == I->getParent())
+ return false;
+
+ // If the load has other users and the truncate is not free, this probably
+ // isn't worthwhile.
+ if (!LI->hasOneUse() &&
+ TLI && !TLI->isTruncateFree(I->getType(), LI->getType()))
+ return false;
+
+ // Check whether the target supports casts folded into loads.
+ unsigned LType;
+ if (isa<ZExtInst>(I))
+ LType = ISD::ZEXTLOAD;
+ else {
+ assert(isa<SExtInst>(I) && "Unexpected ext type!");
+ LType = ISD::SEXTLOAD;
+ }
+ if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType())))
+ return false;
+
+ // Move the extend into the same block as the load, so that SelectionDAG
+ // can fold it.
+ I->removeFromParent();
+ I->insertAfter(LI);
+ return true;
+}
+
bool CodeGenPrepare::OptimizeExtUses(Instruction *I) {
BasicBlock *DefBB = I->getParent();
MadeChange |= Change;
}
- if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I)))
+ if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) {
+ MadeChange |= MoveExtToFormExtLoad(I);
MadeChange |= OptimizeExtUses(I);
+ }
} else if (CmpInst *CI = dyn_cast<CmpInst>(I)) {
MadeChange |= OptimizeCmpExpression(CI);
} else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
} else if (CallInst *CI = dyn_cast<CallInst>(I)) {
// If we found an inline asm expession, and if the target knows how to
// lower it to normal LLVM code, do so now.
- if (TLI && isa<InlineAsm>(CI->getCalledValue()))
- if (const TargetAsmInfo *TAI =
- TLI->getTargetMachine().getTargetAsmInfo()) {
- if (TAI->ExpandInlineAsm(CI)) {
- BBI = BB.begin();
- // Avoid processing instructions out of order, which could cause
- // reuse before a value is defined.
- SunkAddrs.clear();
- } else
- // Sink address computing for memory operands into the block.
- MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs);
- }
+ if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
+ if (TLI->ExpandInlineAsm(CI)) {
+ BBI = BB.begin();
+ // Avoid processing instructions out of order, which could cause
+ // reuse before a value is defined.
+ SunkAddrs.clear();
+ } else
+ // Sink address computing for memory operands into the block.
+ MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs);
+ }
}
}
projects / oota-llvm.git / blobdiff