diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Utils')
16 files changed, 560 insertions, 419 deletions
diff --git a/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp index 92464e8..b4f74f9 100644 --- a/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -153,13 +153,13 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P) { // Delete the unconditional branch from the predecessor... PredBB->getInstList().pop_back(); - // Move all definitions in the successor to the predecessor... - PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); - // Make all PHI nodes that referred to BB now refer to Pred as their // source... BB->replaceAllUsesWith(PredBB); + // Move all definitions in the successor to the predecessor... + PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); + // Inherit predecessors name if it exists. if (!PredBB->hasName()) PredBB->takeName(BB); diff --git a/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp index d6206a3..92ce500 100644 --- a/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -193,44 +193,22 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // If there are any PHI nodes in DestBB, we need to update them so that they // merge incoming values from NewBB instead of from TIBB. - if (PHINode *APHI = dyn_cast<PHINode>(DestBB->begin())) { - // This conceptually does: - // foreach (PHINode *PN in DestBB) - // PN->setIncomingBlock(PN->getIncomingBlock(TIBB), NewBB); - // but is optimized for two cases. - - if (APHI->getNumIncomingValues() <= 8) { // Small # preds case. - unsigned BBIdx = 0; - for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { - // We no longer enter through TIBB, now we come in through NewBB. - // Revector exactly one entry in the PHI node that used to come from - // TIBB to come from NewBB. - PHINode *PN = cast<PHINode>(I); - - // Reuse the previous value of BBIdx if it lines up. In cases where we - // have multiple phi nodes with *lots* of predecessors, this is a speed - // win because we don't have to scan the PHI looking for TIBB. This - // happens because the BB list of PHI nodes are usually in the same - // order. - if (PN->getIncomingBlock(BBIdx) != TIBB) - BBIdx = PN->getBasicBlockIndex(TIBB); - PN->setIncomingBlock(BBIdx, NewBB); - } - } else { - // However, the foreach loop is slow for blocks with lots of predecessors - // because PHINode::getIncomingBlock is O(n) in # preds. Instead, walk - // the user list of TIBB to find the PHI nodes. - SmallPtrSet<PHINode*, 16> UpdatedPHIs; - - for (Value::use_iterator UI = TIBB->use_begin(), E = TIBB->use_end(); - UI != E; ) { - Value::use_iterator Use = UI++; - if (PHINode *PN = dyn_cast<PHINode>(*Use)) { - // Remove one entry from each PHI. - if (PN->getParent() == DestBB && UpdatedPHIs.insert(PN)) - PN->setOperand(Use.getOperandNo(), NewBB); - } - } + { + unsigned BBIdx = 0; + for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { + // We no longer enter through TIBB, now we come in through NewBB. + // Revector exactly one entry in the PHI node that used to come from + // TIBB to come from NewBB. + PHINode *PN = cast<PHINode>(I); + + // Reuse the previous value of BBIdx if it lines up. In cases where we + // have multiple phi nodes with *lots* of predecessors, this is a speed + // win because we don't have to scan the PHI looking for TIBB. This + // happens because the BB list of PHI nodes are usually in the same + // order. + if (PN->getIncomingBlock(BBIdx) != TIBB) + BBIdx = PN->getBasicBlockIndex(TIBB); + PN->setIncomingBlock(BBIdx, NewBB); } } diff --git a/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp b/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp index d967ceb..6ea831f 100644 --- a/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp +++ b/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp @@ -140,7 +140,7 @@ void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, Function *llvm::CloneFunction(const Function *F, ValueToValueMapTy &VMap, bool ModuleLevelChanges, ClonedCodeInfo *CodeInfo) { - std::vector<const Type*> ArgTypes; + std::vector<Type*> ArgTypes; // The user might be deleting arguments to the function by specifying them in // the VMap. If so, we need to not add the arguments to the arg ty vector @@ -342,18 +342,6 @@ ConstantFoldMappedInstruction(const Instruction *I) { Ops.size(), TD); } -static DebugLoc -UpdateInlinedAtInfo(const DebugLoc &InsnDL, const DebugLoc &TheCallDL, - LLVMContext &Ctx) { - DebugLoc NewLoc = TheCallDL; - if (MDNode *IA = InsnDL.getInlinedAt(Ctx)) - NewLoc = UpdateInlinedAtInfo(DebugLoc::getFromDILocation(IA), TheCallDL, - Ctx); - - return DebugLoc::get(InsnDL.getLine(), InsnDL.getCol(), - InsnDL.getScope(Ctx), NewLoc.getAsMDNode(Ctx)); -} - /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, /// except that it does some simple constant prop and DCE on the fly. The /// effect of this is to copy significantly less code in cases where (for @@ -418,50 +406,14 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, if (PHINode *PN = dyn_cast<PHINode>(I)) { // Skip over all PHI nodes, remembering them for later. BasicBlock::const_iterator OldI = BI->begin(); - for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI) { - if (I->hasMetadata()) { - if (!TheCallDL.isUnknown()) { - DebugLoc IDL = I->getDebugLoc(); - if (!IDL.isUnknown()) { - DebugLoc NewDL = UpdateInlinedAtInfo(IDL, TheCallDL, - I->getContext()); - I->setDebugLoc(NewDL); - } - } else { - // The cloned instruction has dbg info but the call instruction - // does not have dbg info. Remove dbg info from cloned instruction. - I->setDebugLoc(DebugLoc()); - } - } + for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI) PHIToResolve.push_back(cast<PHINode>(OldI)); - } } - // FIXME: - // FIXME: - // FIXME: Unclone all this metadata stuff. - // FIXME: - // FIXME: - // Otherwise, remap the rest of the instructions normally. - for (; I != NewBB->end(); ++I) { - if (I->hasMetadata()) { - if (!TheCallDL.isUnknown()) { - DebugLoc IDL = I->getDebugLoc(); - if (!IDL.isUnknown()) { - DebugLoc NewDL = UpdateInlinedAtInfo(IDL, TheCallDL, - I->getContext()); - I->setDebugLoc(NewDL); - } - } else { - // The cloned instruction has dbg info but the call instruction - // does not have dbg info. Remove dbg info from cloned instruction. - I->setDebugLoc(DebugLoc()); - } - } + for (; I != NewBB->end(); ++I) RemapInstruction(I, VMap, ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges); - } } // Defer PHI resolution until rest of function is resolved, PHI resolution @@ -572,12 +524,12 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, // removed, so we just need to splice the blocks. BI->eraseFromParent(); - // Move all the instructions in the succ to the pred. - I->getInstList().splice(I->end(), Dest->getInstList()); - // Make all PHI nodes that referred to Dest now refer to I as their source. Dest->replaceAllUsesWith(I); + // Move all the instructions in the succ to the pred. + I->getInstList().splice(I->end(), Dest->getInstList()); + // Remove the dest block. Dest->eraseFromParent(); diff --git a/contrib/llvm/lib/Transforms/Utils/CloneLoop.cpp b/contrib/llvm/lib/Transforms/Utils/CloneLoop.cpp deleted file mode 100644 index 87dd141..0000000 --- a/contrib/llvm/lib/Transforms/Utils/CloneLoop.cpp +++ /dev/null @@ -1,128 +0,0 @@ -//===- CloneLoop.cpp - Clone loop nest ------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the CloneLoop interface which makes a copy of a loop. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/BasicBlock.h" -#include "llvm/Analysis/LoopPass.h" -#include "llvm/Analysis/Dominators.h" - - -using namespace llvm; - -/// CloneDominatorInfo - Clone a basic block's dominator tree. It is expected -/// that the basic block is already cloned. -static void CloneDominatorInfo(BasicBlock *BB, - ValueToValueMapTy &VMap, - DominatorTree *DT) { - - assert (DT && "DominatorTree is not available"); - ValueToValueMapTy::iterator BI = VMap.find(BB); - assert (BI != VMap.end() && "BasicBlock clone is missing"); - BasicBlock *NewBB = cast<BasicBlock>(BI->second); - - // NewBB already got dominator info. - if (DT->getNode(NewBB)) - return; - - assert (DT->getNode(BB) && "BasicBlock does not have dominator info"); - // Entry block is not expected here. Infinite loops are not to cloned. - assert (DT->getNode(BB)->getIDom() && "BasicBlock does not have immediate dominator"); - BasicBlock *BBDom = DT->getNode(BB)->getIDom()->getBlock(); - - // NewBB's dominator is either BB's dominator or BB's dominator's clone. - BasicBlock *NewBBDom = BBDom; - ValueToValueMapTy::iterator BBDomI = VMap.find(BBDom); - if (BBDomI != VMap.end()) { - NewBBDom = cast<BasicBlock>(BBDomI->second); - if (!DT->getNode(NewBBDom)) - CloneDominatorInfo(BBDom, VMap, DT); - } - DT->addNewBlock(NewBB, NewBBDom); -} - -/// CloneLoop - Clone Loop. Clone dominator info. Populate VMap -/// using old blocks to new blocks mapping. -Loop *llvm::CloneLoop(Loop *OrigL, LPPassManager *LPM, LoopInfo *LI, - ValueToValueMapTy &VMap, Pass *P) { - - DominatorTree *DT = NULL; - if (P) - DT = P->getAnalysisIfAvailable<DominatorTree>(); - - SmallVector<BasicBlock *, 16> NewBlocks; - - // Populate loop nest. - SmallVector<Loop *, 8> LoopNest; - LoopNest.push_back(OrigL); - - - Loop *NewParentLoop = NULL; - do { - Loop *L = LoopNest.pop_back_val(); - Loop *NewLoop = new Loop(); - - if (!NewParentLoop) - NewParentLoop = NewLoop; - - LPM->insertLoop(NewLoop, L->getParentLoop()); - - // Clone Basic Blocks. - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) { - BasicBlock *BB = *I; - BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".clone"); - VMap[BB] = NewBB; - if (P) - LPM->cloneBasicBlockSimpleAnalysis(BB, NewBB, L); - NewLoop->addBasicBlockToLoop(NewBB, LI->getBase()); - NewBlocks.push_back(NewBB); - } - - // Clone dominator info. - if (DT) - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) { - BasicBlock *BB = *I; - CloneDominatorInfo(BB, VMap, DT); - } - - // Process sub loops - for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) - LoopNest.push_back(*I); - } while (!LoopNest.empty()); - - // Remap instructions to reference operands from VMap. - for(SmallVector<BasicBlock *, 16>::iterator NBItr = NewBlocks.begin(), - NBE = NewBlocks.end(); NBItr != NBE; ++NBItr) { - BasicBlock *NB = *NBItr; - for(BasicBlock::iterator BI = NB->begin(), BE = NB->end(); - BI != BE; ++BI) { - Instruction *Insn = BI; - for (unsigned index = 0, num_ops = Insn->getNumOperands(); - index != num_ops; ++index) { - Value *Op = Insn->getOperand(index); - ValueToValueMapTy::iterator OpItr = VMap.find(Op); - if (OpItr != VMap.end()) - Insn->setOperand(index, OpItr->second); - } - } - } - - BasicBlock *Latch = OrigL->getLoopLatch(); - Function *F = Latch->getParent(); - F->getBasicBlockList().insert(OrigL->getHeader(), - NewBlocks.begin(), NewBlocks.end()); - - - return NewParentLoop; -} diff --git a/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp b/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp index 1046c38..a08fa35 100644 --- a/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp +++ b/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp @@ -15,7 +15,6 @@ #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Module.h" #include "llvm/DerivedTypes.h" -#include "llvm/TypeSymbolTable.h" #include "llvm/Constant.h" #include "llvm/Transforms/Utils/ValueMapper.h" using namespace llvm; @@ -32,20 +31,13 @@ Module *llvm::CloneModule(const Module *M) { return CloneModule(M, VMap); } -Module *llvm::CloneModule(const Module *M, - ValueToValueMapTy &VMap) { - // First off, we need to create the new module... +Module *llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap) { + // First off, we need to create the new module. Module *New = new Module(M->getModuleIdentifier(), M->getContext()); New->setDataLayout(M->getDataLayout()); New->setTargetTriple(M->getTargetTriple()); New->setModuleInlineAsm(M->getModuleInlineAsm()); - - // Copy all of the type symbol table entries over. - const TypeSymbolTable &TST = M->getTypeSymbolTable(); - for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end(); - TI != TE; ++TI) - New->addTypeName(TI->first, TI->second); - + // Copy all of the dependent libraries over. for (Module::lib_iterator I = M->lib_begin(), E = M->lib_end(); I != E; ++I) New->addLibrary(*I); @@ -88,8 +80,7 @@ Module *llvm::CloneModule(const Module *M, I != E; ++I) { GlobalVariable *GV = cast<GlobalVariable>(VMap[I]); if (I->hasInitializer()) - GV->setInitializer(cast<Constant>(MapValue(I->getInitializer(), - VMap, RF_None))); + GV->setInitializer(MapValue(I->getInitializer(), VMap)); GV->setLinkage(I->getLinkage()); GV->setThreadLocal(I->isThreadLocal()); GV->setConstant(I->isConstant()); @@ -119,8 +110,8 @@ Module *llvm::CloneModule(const Module *M, I != E; ++I) { GlobalAlias *GA = cast<GlobalAlias>(VMap[I]); GA->setLinkage(I->getLinkage()); - if (const Constant* C = I->getAliasee()) - GA->setAliasee(cast<Constant>(MapValue(C, VMap, RF_None))); + if (const Constant *C = I->getAliasee()) + GA->setAliasee(MapValue(C, VMap)); } // And named metadata.... @@ -129,8 +120,7 @@ Module *llvm::CloneModule(const Module *M, const NamedMDNode &NMD = *I; NamedMDNode *NewNMD = New->getOrInsertNamedMetadata(NMD.getName()); for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i) - NewNMD->addOperand(cast<MDNode>(MapValue(NMD.getOperand(i), VMap, - RF_None))); + NewNMD->addOperand(MapValue(NMD.getOperand(i), VMap)); } return New; diff --git a/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp b/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp index 8c133ea..0813523 100644 --- a/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ b/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -258,7 +258,7 @@ Function *CodeExtractor::constructFunction(const Values &inputs, default: RetTy = Type::getInt16Ty(header->getContext()); break; } - std::vector<const Type*> paramTy; + std::vector<Type*> paramTy; // Add the types of the input values to the function's argument list for (Values::const_iterator i = inputs.begin(), @@ -279,7 +279,7 @@ Function *CodeExtractor::constructFunction(const Values &inputs, } DEBUG(dbgs() << "Function type: " << *RetTy << " f("); - for (std::vector<const Type*>::iterator i = paramTy.begin(), + for (std::vector<Type*>::iterator i = paramTy.begin(), e = paramTy.end(); i != e; ++i) DEBUG(dbgs() << **i << ", "); DEBUG(dbgs() << ")\n"); @@ -403,7 +403,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, AllocaInst *Struct = 0; if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { - std::vector<const Type*> ArgTypes; + std::vector<Type*> ArgTypes; for (Values::iterator v = StructValues.begin(), ve = StructValues.end(); v != ve; ++v) ArgTypes.push_back((*v)->getType()); @@ -429,7 +429,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, } // Emit the call to the function - CallInst *call = CallInst::Create(newFunction, params.begin(), params.end(), + CallInst *call = CallInst::Create(newFunction, params, NumExitBlocks > 1 ? "targetBlock" : ""); codeReplacer->getInstList().push_back(call); diff --git a/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp b/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp index 8416170..d5b382e 100644 --- a/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp +++ b/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp @@ -449,11 +449,8 @@ static bool HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, for (unsigned i = 2, e = Outer->getNumArgOperands(); i != e; ++i) NewSelector.push_back(Outer->getArgOperand(i)); - CallInst *NewInner = CallInst::Create(Inner->getCalledValue(), - NewSelector.begin(), - NewSelector.end(), - "", - Inner); + CallInst *NewInner = + IRBuilder<>(Inner).CreateCall(Inner->getCalledValue(), NewSelector); // No need to copy attributes, calling convention, etc. NewInner->takeName(Inner); Inner->replaceAllUsesWith(NewInner); @@ -489,8 +486,7 @@ static bool HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, Invoke.getOuterUnwindDest(), - InvokeArgs.begin(), InvokeArgs.end(), - CI->getName(), BB); + InvokeArgs, CI->getName(), BB); II->setCallingConv(CI->getCallingConv()); II->setAttributes(CI->getAttributes()); @@ -664,7 +660,7 @@ static Value *HandleByValArgument(Value *Arg, Instruction *TheCall, LLVMContext &Context = Arg->getContext(); - const Type *VoidPtrTy = Type::getInt8PtrTy(Context); + Type *VoidPtrTy = Type::getInt8PtrTy(Context); // Create the alloca. If we have TargetData, use nice alignment. unsigned Align = 1; @@ -681,10 +677,10 @@ static Value *HandleByValArgument(Value *Arg, Instruction *TheCall, Value *NewAlloca = new AllocaInst(AggTy, 0, Align, Arg->getName(), &*Caller->begin()->begin()); // Emit a memcpy. - const Type *Tys[3] = {VoidPtrTy, VoidPtrTy, Type::getInt64Ty(Context)}; + Type *Tys[3] = {VoidPtrTy, VoidPtrTy, Type::getInt64Ty(Context)}; Function *MemCpyFn = Intrinsic::getDeclaration(Caller->getParent(), Intrinsic::memcpy, - Tys, 3); + Tys); Value *DestCast = new BitCastInst(NewAlloca, VoidPtrTy, "tmp", TheCall); Value *SrcCast = new BitCastInst(Arg, VoidPtrTy, "tmp", TheCall); @@ -703,7 +699,7 @@ static Value *HandleByValArgument(Value *Arg, Instruction *TheCall, ConstantInt::get(Type::getInt32Ty(Context), 1), ConstantInt::getFalse(Context) // isVolatile }; - CallInst::Create(MemCpyFn, CallArgs, CallArgs+5, "", TheCall); + IRBuilder<>(TheCall).CreateCall(MemCpyFn, CallArgs); // Uses of the argument in the function should use our new alloca // instead. @@ -734,17 +730,52 @@ static bool hasLifetimeMarkers(AllocaInst *AI) { if (AI->getType() == Int8PtrTy) return isUsedByLifetimeMarker(AI); - // Do a scan to find all the bitcasts to i8*. + // Do a scan to find all the casts to i8*. for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); I != E; ++I) { if (I->getType() != Int8PtrTy) continue; - if (!isa<BitCastInst>(*I)) continue; + if (I->stripPointerCasts() != AI) continue; if (isUsedByLifetimeMarker(*I)) return true; } return false; } +/// updateInlinedAtInfo - Helper function used by fixupLineNumbers to recursively +/// update InlinedAtEntry of a DebugLoc. +static DebugLoc updateInlinedAtInfo(const DebugLoc &DL, + const DebugLoc &InlinedAtDL, + LLVMContext &Ctx) { + if (MDNode *IA = DL.getInlinedAt(Ctx)) { + DebugLoc NewInlinedAtDL + = updateInlinedAtInfo(DebugLoc::getFromDILocation(IA), InlinedAtDL, Ctx); + return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(Ctx), + NewInlinedAtDL.getAsMDNode(Ctx)); + } + + return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(Ctx), + InlinedAtDL.getAsMDNode(Ctx)); +} + + +/// fixupLineNumbers - Update inlined instructions' line numbers to +/// to encode location where these instructions are inlined. +static void fixupLineNumbers(Function *Fn, Function::iterator FI, + Instruction *TheCall) { + DebugLoc TheCallDL = TheCall->getDebugLoc(); + if (TheCallDL.isUnknown()) + return; + + for (; FI != Fn->end(); ++FI) { + for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); + BI != BE; ++BI) { + DebugLoc DL = BI->getDebugLoc(); + if (!DL.isUnknown()) + BI->setDebugLoc(updateInlinedAtInfo(DL, TheCallDL, BI->getContext())); + } + } +} + // InlineFunction - This function inlines the called function into the basic // block of the caller. This returns false if it is not possible to inline this // call. The program is still in a well defined state if this occurs though. @@ -847,6 +878,9 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { // Update the callgraph if requested. if (IFI.CG) UpdateCallGraphAfterInlining(CS, FirstNewBlock, VMap, IFI); + + // Update inlined instructions' line number information. + fixupLineNumbers(Caller, FirstNewBlock, TheCall); } // If there are any alloca instructions in the block that used to be the entry @@ -920,13 +954,13 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { Function *StackRestore=Intrinsic::getDeclaration(M,Intrinsic::stackrestore); // Insert the llvm.stacksave. - CallInst *SavedPtr = CallInst::Create(StackSave, "savedstack", - FirstNewBlock->begin()); + CallInst *SavedPtr = IRBuilder<>(FirstNewBlock, FirstNewBlock->begin()) + .CreateCall(StackSave, "savedstack"); // Insert a call to llvm.stackrestore before any return instructions in the // inlined function. for (unsigned i = 0, e = Returns.size(); i != e; ++i) { - CallInst::Create(StackRestore, SavedPtr, "", Returns[i]); + IRBuilder<>(Returns[i]).CreateCall(StackRestore, SavedPtr); } // Count the number of StackRestore calls we insert. @@ -938,7 +972,7 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { for (Function::iterator BB = FirstNewBlock, E = Caller->end(); BB != E; ++BB) if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { - CallInst::Create(StackRestore, SavedPtr, "", UI); + IRBuilder<>(UI).CreateCall(StackRestore, SavedPtr); ++NumStackRestores; } } @@ -1098,15 +1132,15 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { TheCall->replaceAllUsesWith(Returns[0]->getReturnValue()); } + // Update PHI nodes that use the ReturnBB to use the AfterCallBB. + BasicBlock *ReturnBB = Returns[0]->getParent(); + ReturnBB->replaceAllUsesWith(AfterCallBB); + // Splice the code from the return block into the block that it will return // to, which contains the code that was after the call. - BasicBlock *ReturnBB = Returns[0]->getParent(); AfterCallBB->getInstList().splice(AfterCallBB->begin(), ReturnBB->getInstList()); - // Update PHI nodes that use the ReturnBB to use the AfterCallBB. - ReturnBB->replaceAllUsesWith(AfterCallBB); - // Delete the return instruction now and empty ReturnBB now. Returns[0]->eraseFromParent(); ReturnBB->eraseFromParent(); @@ -1126,8 +1160,8 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { // Splice the code entry block into calling block, right before the // unconditional branch. - OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); CalleeEntry->replaceAllUsesWith(OrigBB); // Update PHI nodes + OrigBB->getInstList().splice(Br, CalleeEntry->getInstList()); // Remove the unconditional branch. OrigBB->getInstList().erase(Br); diff --git a/contrib/llvm/lib/Transforms/Utils/Local.cpp b/contrib/llvm/lib/Transforms/Utils/Local.cpp index 3bdbaa5..0f6d9ae 100644 --- a/contrib/llvm/lib/Transforms/Utils/Local.cpp +++ b/contrib/llvm/lib/Transforms/Utils/Local.cpp @@ -427,10 +427,6 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { BasicBlock *PredBB = DestBB->getSinglePredecessor(); assert(PredBB && "Block doesn't have a single predecessor!"); - // Splice all the instructions from PredBB to DestBB. - PredBB->getTerminator()->eraseFromParent(); - DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); - // Zap anything that took the address of DestBB. Not doing this will give the // address an invalid value. if (DestBB->hasAddressTaken()) { @@ -445,6 +441,10 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { // Anything that branched to PredBB now branches to DestBB. PredBB->replaceAllUsesWith(DestBB); + // Splice all the instructions from PredBB to DestBB. + PredBB->getTerminator()->eraseFromParent(); + DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); + if (P) { DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); if (DT) { @@ -536,9 +536,9 @@ static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an /// unconditional branch, and contains no instructions other than PHI nodes, -/// potential debug intrinsics and the branch. If possible, eliminate BB by -/// rewriting all the predecessors to branch to the successor block and return -/// true. If we can't transform, return false. +/// potential side-effect free intrinsics and the branch. If possible, +/// eliminate BB by rewriting all the predecessors to branch to the successor +/// block and return true. If we can't transform, return false. bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { assert(BB != &BB->getParent()->getEntryBlock() && "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); @@ -613,13 +613,15 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { } } - while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { - if (Succ->getSinglePredecessor()) { - // BB is the only predecessor of Succ, so Succ will end up with exactly - // the same predecessors BB had. - Succ->getInstList().splice(Succ->begin(), - BB->getInstList(), BB->begin()); - } else { + if (Succ->getSinglePredecessor()) { + // BB is the only predecessor of Succ, so Succ will end up with exactly + // the same predecessors BB had. + + // Copy over any phi, debug or lifetime instruction. + BB->getTerminator()->eraseFromParent(); + Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); + } else { + while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. assert(PN->use_empty() && "There shouldn't be any uses here!"); PN->eraseFromParent(); @@ -642,7 +644,7 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { bool Changed = false; // This implementation doesn't currently consider undef operands - // specially. Theroetically, two phis which are identical except for + // specially. Theoretically, two phis which are identical except for // one having an undef where the other doesn't could be collapsed. // Map from PHI hash values to PHI nodes. If multiple PHIs have @@ -660,12 +662,17 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { // them, which helps expose duplicates, but we have to check all the // operands to be safe in case instcombine hasn't run. uintptr_t Hash = 0; + // This hash algorithm is quite weak as hash functions go, but it seems + // to do a good enough job for this particular purpose, and is very quick. for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { - // This hash algorithm is quite weak as hash functions go, but it seems - // to do a good enough job for this particular purpose, and is very quick. Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); } + for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); + I != E; ++I) { + Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); + Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); + } // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. Hash >>= 1; // If we've never seen this hash value before, it's a unique PHI. @@ -706,39 +713,15 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { /// static unsigned enforceKnownAlignment(Value *V, unsigned Align, unsigned PrefAlign) { + V = V->stripPointerCasts(); - User *U = dyn_cast<User>(V); - if (!U) return Align; - - switch (Operator::getOpcode(U)) { - default: break; - case Instruction::BitCast: - return enforceKnownAlignment(U->getOperand(0), Align, PrefAlign); - case Instruction::GetElementPtr: { - // If all indexes are zero, it is just the alignment of the base pointer. - bool AllZeroOperands = true; - for (User::op_iterator i = U->op_begin() + 1, e = U->op_end(); i != e; ++i) - if (!isa<Constant>(*i) || - !cast<Constant>(*i)->isNullValue()) { - AllZeroOperands = false; - break; - } - - if (AllZeroOperands) { - // Treat this like a bitcast. - return enforceKnownAlignment(U->getOperand(0), Align, PrefAlign); - } - return Align; - } - case Instruction::Alloca: { - AllocaInst *AI = cast<AllocaInst>(V); + if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { // If there is a requested alignment and if this is an alloca, round up. if (AI->getAlignment() >= PrefAlign) return AI->getAlignment(); AI->setAlignment(PrefAlign); return PrefAlign; } - } if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { // If there is a large requested alignment and we can, bump up the alignment diff --git a/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp index f02ffd2..e79fb5a 100644 --- a/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -375,6 +375,7 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), ".preheader", this); + NewBB->getTerminator()->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc()); DEBUG(dbgs() << "LoopSimplify: Creating pre-header " << NewBB->getName() << "\n"); diff --git a/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp b/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp index 7da7271..6772511 100644 --- a/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp @@ -47,6 +47,14 @@ static inline void RemapInstruction(Instruction *I, if (It != VMap.end()) I->setOperand(op, It->second); } + + if (PHINode *PN = dyn_cast<PHINode>(I)) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + ValueToValueMapTy::iterator It = VMap.find(PN->getIncomingBlock(i)); + if (It != VMap.end()) + PN->setIncomingBlock(i, cast<BasicBlock>(It->second)); + } + } } /// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it @@ -75,13 +83,13 @@ static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { // Delete the unconditional branch from the predecessor... OnlyPred->getInstList().pop_back(); - // Move all definitions in the successor to the predecessor... - OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); - // Make all PHI nodes that referred to BB now refer to Pred as their // source... BB->replaceAllUsesWith(OnlyPred); + // Move all definitions in the successor to the predecessor... + OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); + std::string OldName = BB->getName(); // Erase basic block from the function... @@ -247,16 +255,14 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // the successor of the latch block. The successor of the exit block will // be updated specially after unrolling all the way. if (*BB != LatchBlock) - for (Value::use_iterator UI = (*BB)->use_begin(), UE = (*BB)->use_end(); - UI != UE;) { - Instruction *UseInst = cast<Instruction>(*UI); - ++UI; - if (isa<PHINode>(UseInst) && !L->contains(UseInst)) { - PHINode *phi = cast<PHINode>(UseInst); - Value *Incoming = phi->getIncomingValueForBlock(*BB); - phi->addIncoming(Incoming, New); - } - } + for (succ_iterator SI = succ_begin(*BB), SE = succ_end(*BB); SI != SE; + ++SI) + if (!L->contains(*SI)) + for (BasicBlock::iterator BBI = (*SI)->begin(); + PHINode *phi = dyn_cast<PHINode>(BBI); ++BBI) { + Value *Incoming = phi->getIncomingValueForBlock(*BB); + phi->addIncoming(Incoming, New); + } // Keep track of new headers and latches as we create them, so that // we can insert the proper branches later. @@ -288,24 +294,20 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // successor blocks, update them to use the appropriate values computed as the // last iteration of the loop. if (Count != 1) { - SmallPtrSet<PHINode*, 8> Users; - for (Value::use_iterator UI = LatchBlock->use_begin(), - UE = LatchBlock->use_end(); UI != UE; ++UI) - if (PHINode *phi = dyn_cast<PHINode>(*UI)) - Users.insert(phi); - BasicBlock *LastIterationBB = cast<BasicBlock>(LastValueMap[LatchBlock]); - for (SmallPtrSet<PHINode*,8>::iterator SI = Users.begin(), SE = Users.end(); + for (succ_iterator SI = succ_begin(LatchBlock), SE = succ_end(LatchBlock); SI != SE; ++SI) { - PHINode *PN = *SI; - Value *InVal = PN->removeIncomingValue(LatchBlock, false); - // If this value was defined in the loop, take the value defined by the - // last iteration of the loop. - if (Instruction *InValI = dyn_cast<Instruction>(InVal)) { - if (L->contains(InValI)) - InVal = LastValueMap[InVal]; + for (BasicBlock::iterator BBI = (*SI)->begin(); + PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) { + Value *InVal = PN->removeIncomingValue(LatchBlock, false); + // If this value was defined in the loop, take the value defined by the + // last iteration of the loop. + if (Instruction *InValI = dyn_cast<Instruction>(InVal)) { + if (L->contains(InValI)) + InVal = LastValueMap[InVal]; + } + PN->addIncoming(InVal, LastIterationBB); } - PN->addIncoming(InVal, LastIterationBB); } } @@ -352,11 +354,16 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // Replace the conditional branch with an unconditional one. BranchInst::Create(Dest, Term); Term->eraseFromParent(); - // Merge adjacent basic blocks, if possible. - if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) { + } + } + + // Merge adjacent basic blocks, if possible. + for (unsigned i = 0, e = Latches.size(); i != e; ++i) { + BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator()); + if (Term->isUnconditional()) { + BasicBlock *Dest = Term->getSuccessor(0); + if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) std::replace(Latches.begin(), Latches.end(), Dest, Fold); - std::replace(Headers.begin(), Headers.end(), Dest, Fold); - } } } diff --git a/contrib/llvm/lib/Transforms/Utils/LowerExpectIntrinsic.cpp b/contrib/llvm/lib/Transforms/Utils/LowerExpectIntrinsic.cpp new file mode 100644 index 0000000..c1213fa --- /dev/null +++ b/contrib/llvm/lib/Transforms/Utils/LowerExpectIntrinsic.cpp @@ -0,0 +1,166 @@ +#define DEBUG_TYPE "lower-expect-intrinsic" +#include "llvm/Constants.h" +#include "llvm/Function.h" +#include "llvm/BasicBlock.h" +#include "llvm/LLVMContext.h" +#include "llvm/Instructions.h" +#include "llvm/Intrinsics.h" +#include "llvm/Metadata.h" +#include "llvm/Pass.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/Statistic.h" +#include <vector> + +using namespace llvm; + +STATISTIC(IfHandled, "Number of 'expect' intrinsic intructions handled"); + +static cl::opt<uint32_t> +LikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(64), + cl::desc("Weight of the branch likely to be taken (default = 64)")); +static cl::opt<uint32_t> +UnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(4), + cl::desc("Weight of the branch unlikely to be taken (default = 4)")); + +namespace { + + class LowerExpectIntrinsic : public FunctionPass { + + bool HandleSwitchExpect(SwitchInst *SI); + + bool HandleIfExpect(BranchInst *BI); + + public: + static char ID; + LowerExpectIntrinsic() : FunctionPass(ID) { + initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F); + }; +} + + +bool LowerExpectIntrinsic::HandleSwitchExpect(SwitchInst *SI) { + CallInst *CI = dyn_cast<CallInst>(SI->getCondition()); + if (!CI) + return false; + + Function *Fn = CI->getCalledFunction(); + if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) + return false; + + Value *ArgValue = CI->getArgOperand(0); + ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); + if (!ExpectedValue) + return false; + + LLVMContext &Context = CI->getContext(); + const Type *Int32Ty = Type::getInt32Ty(Context); + + unsigned caseNo = SI->findCaseValue(ExpectedValue); + std::vector<Value *> Vec; + unsigned n = SI->getNumCases(); + Vec.resize(n + 1); // +1 for MDString + + Vec[0] = MDString::get(Context, "branch_weights"); + for (unsigned i = 0; i < n; ++i) { + Vec[i + 1] = ConstantInt::get(Int32Ty, i == caseNo ? LikelyBranchWeight : UnlikelyBranchWeight); + } + + MDNode *WeightsNode = llvm::MDNode::get(Context, Vec); + SI->setMetadata(LLVMContext::MD_prof, WeightsNode); + + SI->setCondition(ArgValue); + return true; +} + + +bool LowerExpectIntrinsic::HandleIfExpect(BranchInst *BI) { + if (BI->isUnconditional()) + return false; + + // Handle non-optimized IR code like: + // %expval = call i64 @llvm.expect.i64.i64(i64 %conv1, i64 1) + // %tobool = icmp ne i64 %expval, 0 + // br i1 %tobool, label %if.then, label %if.end + + ICmpInst *CmpI = dyn_cast<ICmpInst>(BI->getCondition()); + if (!CmpI || CmpI->getPredicate() != CmpInst::ICMP_NE) + return false; + + CallInst *CI = dyn_cast<CallInst>(CmpI->getOperand(0)); + if (!CI) + return false; + + Function *Fn = CI->getCalledFunction(); + if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect) + return false; + + Value *ArgValue = CI->getArgOperand(0); + ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1)); + if (!ExpectedValue) + return false; + + LLVMContext &Context = CI->getContext(); + const Type *Int32Ty = Type::getInt32Ty(Context); + bool Likely = ExpectedValue->isOne(); + + // If expect value is equal to 1 it means that we are more likely to take + // branch 0, in other case more likely is branch 1. + Value *Ops[] = { + MDString::get(Context, "branch_weights"), + ConstantInt::get(Int32Ty, Likely ? LikelyBranchWeight : UnlikelyBranchWeight), + ConstantInt::get(Int32Ty, Likely ? UnlikelyBranchWeight : LikelyBranchWeight) + }; + + MDNode *WeightsNode = MDNode::get(Context, Ops); + BI->setMetadata(LLVMContext::MD_prof, WeightsNode); + + CmpI->setOperand(0, ArgValue); + return true; +} + + +bool LowerExpectIntrinsic::runOnFunction(Function &F) { + for (Function::iterator I = F.begin(), E = F.end(); I != E;) { + BasicBlock *BB = I++; + + // Create "block_weights" metadata. + if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { + if (HandleIfExpect(BI)) + IfHandled++; + } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { + if (HandleSwitchExpect(SI)) + IfHandled++; + } + + // remove llvm.expect intrinsics. + for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); + BI != BE; ) { + CallInst *CI = dyn_cast<CallInst>(BI++); + if (!CI) + continue; + + Function *Fn = CI->getCalledFunction(); + if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) { + Value *Exp = CI->getArgOperand(0); + CI->replaceAllUsesWith(Exp); + CI->eraseFromParent(); + } + } + } + + return false; +} + + +char LowerExpectIntrinsic::ID = 0; +INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect", "Lower 'expect' " + "Intrinsics", false, false) + +FunctionPass *llvm::createLowerExpectIntrinsicPass() { + return new LowerExpectIntrinsic(); +} diff --git a/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp b/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp index 025ae0d..f77d19d 100644 --- a/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp @@ -66,7 +66,7 @@ namespace { Constant *AbortFn; // Used for expensive EH support. - const Type *JBLinkTy; + StructType *JBLinkTy; GlobalVariable *JBListHead; Constant *SetJmpFn, *LongJmpFn, *StackSaveFn, *StackRestoreFn; bool useExpensiveEHSupport; @@ -120,24 +120,16 @@ FunctionPass *llvm::createLowerInvokePass(const TargetLowering *TLI, // doInitialization - Make sure that there is a prototype for abort in the // current module. bool LowerInvoke::doInitialization(Module &M) { - const Type *VoidPtrTy = - Type::getInt8PtrTy(M.getContext()); + const Type *VoidPtrTy = Type::getInt8PtrTy(M.getContext()); if (useExpensiveEHSupport) { // Insert a type for the linked list of jump buffers. unsigned JBSize = TLI ? TLI->getJumpBufSize() : 0; JBSize = JBSize ? JBSize : 200; - const Type *JmpBufTy = ArrayType::get(VoidPtrTy, JBSize); - - { // The type is recursive, so use a type holder. - std::vector<const Type*> Elements; - Elements.push_back(JmpBufTy); - OpaqueType *OT = OpaqueType::get(M.getContext()); - Elements.push_back(PointerType::getUnqual(OT)); - PATypeHolder JBLType(StructType::get(M.getContext(), Elements)); - OT->refineAbstractTypeTo(JBLType.get()); // Complete the cycle. - JBLinkTy = JBLType.get(); - M.addTypeName("llvm.sjljeh.jmpbufty", JBLinkTy); - } + Type *JmpBufTy = ArrayType::get(VoidPtrTy, JBSize); + + JBLinkTy = StructType::createNamed(M.getContext(), "llvm.sjljeh.jmpbufty"); + Type *Elts[] = { JmpBufTy, PointerType::getUnqual(JBLinkTy) }; + JBLinkTy->setBody(Elts); const Type *PtrJBList = PointerType::getUnqual(JBLinkTy); @@ -184,8 +176,7 @@ bool LowerInvoke::insertCheapEHSupport(Function &F) { SmallVector<Value*,16> CallArgs(II->op_begin(), II->op_end() - 3); // Insert a normal call instruction... CallInst *NewCall = CallInst::Create(II->getCalledValue(), - CallArgs.begin(), CallArgs.end(), - "",II); + CallArgs, "", II); NewCall->takeName(II); NewCall->setCallingConv(II->getCallingConv()); NewCall->setAttributes(II->getAttributes()); @@ -265,8 +256,7 @@ void LowerInvoke::rewriteExpensiveInvoke(InvokeInst *II, unsigned InvokeNo, // Insert a normal call instruction. SmallVector<Value*,16> CallArgs(II->op_begin(), II->op_end() - 3); CallInst *NewCall = CallInst::Create(II->getCalledValue(), - CallArgs.begin(), CallArgs.end(), "", - II); + CallArgs, "", II); NewCall->takeName(II); NewCall->setCallingConv(II->getCallingConv()); NewCall->setAttributes(II->getAttributes()); @@ -573,7 +563,7 @@ bool LowerInvoke::insertExpensiveEHSupport(Function &F) { Type::getInt8PtrTy(F.getContext()), "tmp", UnwindBlock); Idx[1] = ConstantInt::get(Type::getInt32Ty(F.getContext()), 1); - CallInst::Create(LongJmpFn, &Idx[0], &Idx[2], "", UnwindBlock); + CallInst::Create(LongJmpFn, Idx, "", UnwindBlock); new UnreachableInst(F.getContext(), UnwindBlock); // Set up the term block ("throw without a catch"). diff --git a/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index a1736b9..e5a00f4 100644 --- a/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -38,6 +38,7 @@ #include "llvm/Analysis/DIBuilder.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" @@ -92,6 +93,22 @@ bool llvm::isAllocaPromotable(const AllocaInst *AI) { return false; // Don't allow a store OF the AI, only INTO the AI. if (SI->isVolatile()) return false; + } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) { + if (II->getIntrinsicID() != Intrinsic::lifetime_start && + II->getIntrinsicID() != Intrinsic::lifetime_end) + return false; + } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { + if (BCI->getType() != Type::getInt8PtrTy(U->getContext())) + return false; + if (!onlyUsedByLifetimeMarkers(BCI)) + return false; + } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { + if (GEPI->getType() != Type::getInt8PtrTy(U->getContext())) + return false; + if (!GEPI->hasAllZeroIndices()) + return false; + if (!onlyUsedByLifetimeMarkers(GEPI)) + return false; } else { return false; } @@ -335,6 +352,31 @@ namespace { }; } // end of anonymous namespace +static void removeLifetimeIntrinsicUsers(AllocaInst *AI) { + // Knowing that this alloca is promotable, we know that it's safe to kill all + // instructions except for load and store. + + for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end(); + UI != UE;) { + Instruction *I = cast<Instruction>(*UI); + ++UI; + if (isa<LoadInst>(I) || isa<StoreInst>(I)) + continue; + + if (!I->getType()->isVoidTy()) { + // The only users of this bitcast/GEP instruction are lifetime intrinsics. + // Follow the use/def chain to erase them now instead of leaving it for + // dead code elimination later. + for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); + UI != UE;) { + Instruction *Inst = cast<Instruction>(*UI); + ++UI; + Inst->eraseFromParent(); + } + } + I->eraseFromParent(); + } +} void PromoteMem2Reg::run() { Function &F = *DT.getRoot()->getParent(); @@ -353,6 +395,8 @@ void PromoteMem2Reg::run() { assert(AI->getParent()->getParent() == &F && "All allocas should be in the same function, which is same as DF!"); + removeLifetimeIntrinsicUsers(AI); + if (AI->use_empty()) { // If there are no uses of the alloca, just delete it now. if (AST) AST->deleteValue(AI); diff --git a/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp b/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp index b336194..b47a7cc 100644 --- a/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp +++ b/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp @@ -16,7 +16,6 @@ #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/Analysis/DIBuilder.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Allocator.h" @@ -358,8 +357,7 @@ Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { LoadAndStorePromoter:: LoadAndStorePromoter(const SmallVectorImpl<Instruction*> &Insts, - SSAUpdater &S, DbgDeclareInst *DD, DIBuilder *DB, - StringRef BaseName) : SSA(S), DDI(DD), DIB(DB) { + SSAUpdater &S, StringRef BaseName) : SSA(S) { if (Insts.empty()) return; Value *SomeVal; @@ -407,8 +405,7 @@ run(const SmallVectorImpl<Instruction*> &Insts) const { if (BlockUses.size() == 1) { // If it is a store, it is a trivial def of the value in the block. if (StoreInst *SI = dyn_cast<StoreInst>(User)) { - if (DDI) - ConvertDebugDeclareToDebugValue(DDI, SI, *DIB); + updateDebugInfo(SI); SSA.AddAvailableValue(BB, SI->getOperand(0)); } else // Otherwise it is a load, queue it to rewrite as a live-in load. @@ -462,9 +459,7 @@ run(const SmallVectorImpl<Instruction*> &Insts) const { if (StoreInst *SI = dyn_cast<StoreInst>(II)) { // If this is a store to an unrelated pointer, ignore it. if (!isInstInList(SI, Insts)) continue; - - if (DDI) - ConvertDebugDeclareToDebugValue(DDI, SI, *DIB); + updateDebugInfo(SI); // Remember that this is the active value in the block. StoredValue = SI->getOperand(0); @@ -522,7 +517,4 @@ run(const SmallVectorImpl<Instruction*> &Insts) const { instructionDeleted(User); User->eraseFromParent(); } - - if (DDI) - DDI->eraseFromParent(); } diff --git a/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 6df846c..9d9c324 100644 --- a/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -2211,8 +2211,7 @@ bool SimplifyCFGOpt::SimplifyUnwind(UnwindInst *UI, IRBuilder<> &Builder) { SmallVector<Value*,8> Args(II->op_begin(), II->op_end()-3); Builder.SetInsertPoint(BI); CallInst *CI = Builder.CreateCall(II->getCalledValue(), - Args.begin(), Args.end(), - II->getName()); + Args, II->getName()); CI->setCallingConv(II->getCallingConv()); CI->setAttributes(II->getAttributes()); // If the invoke produced a value, the Call now does instead. @@ -2355,8 +2354,7 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3); Builder.SetInsertPoint(BI); CallInst *CI = Builder.CreateCall(II->getCalledValue(), - Args.begin(), Args.end(), - II->getName()); + Args, II->getName()); CI->setCallingConv(II->getCallingConv()); CI->setAttributes(II->getAttributes()); // If the invoke produced a value, the call does now instead. @@ -2450,6 +2448,77 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI) { return !DeadCases.empty(); } +/// FindPHIForConditionForwarding - If BB would be eligible for simplification +/// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated +/// by an unconditional branch), look at the phi node for BB in the successor +/// block and see if the incoming value is equal to CaseValue. If so, return +/// the phi node, and set PhiIndex to BB's index in the phi node. +static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, + BasicBlock *BB, + int *PhiIndex) { + if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) + return NULL; // BB must be empty to be a candidate for simplification. + if (!BB->getSinglePredecessor()) + return NULL; // BB must be dominated by the switch. + + BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator()); + if (!Branch || !Branch->isUnconditional()) + return NULL; // Terminator must be unconditional branch. + + BasicBlock *Succ = Branch->getSuccessor(0); + + BasicBlock::iterator I = Succ->begin(); + while (PHINode *PHI = dyn_cast<PHINode>(I++)) { + int Idx = PHI->getBasicBlockIndex(BB); + assert(Idx >= 0 && "PHI has no entry for predecessor?"); + + Value *InValue = PHI->getIncomingValue(Idx); + if (InValue != CaseValue) continue; + + *PhiIndex = Idx; + return PHI; + } + + return NULL; +} + +/// ForwardSwitchConditionToPHI - Try to forward the condition of a switch +/// instruction to a phi node dominated by the switch, if that would mean that +/// some of the destination blocks of the switch can be folded away. +/// Returns true if a change is made. +static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { + typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap; + ForwardingNodesMap ForwardingNodes; + + for (unsigned I = 1; I < SI->getNumCases(); ++I) { // 0 is the default case. + ConstantInt *CaseValue = SI->getCaseValue(I); + BasicBlock *CaseDest = SI->getSuccessor(I); + + int PhiIndex; + PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest, + &PhiIndex); + if (!PHI) continue; + + ForwardingNodes[PHI].push_back(PhiIndex); + } + + bool Changed = false; + + for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), + E = ForwardingNodes.end(); I != E; ++I) { + PHINode *Phi = I->first; + SmallVector<int,4> &Indexes = I->second; + + if (Indexes.size() < 2) continue; + + for (size_t I = 0, E = Indexes.size(); I != E; ++I) + Phi->setIncomingValue(Indexes[I], SI->getCondition()); + Changed = true; + } + + return Changed; +} + bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { // If this switch is too complex to want to look at, ignore it. if (!isValueEqualityComparison(SI)) @@ -2486,6 +2555,9 @@ bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { if (EliminateDeadSwitchCases(SI)) return SimplifyCFG(BB) | true; + if (ForwardSwitchConditionToPHI(SI)) + return SimplifyCFG(BB) | true; + return false; } @@ -2530,7 +2602,7 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ BasicBlock *BB = BI->getParent(); // If the Terminator is the only non-phi instruction, simplify the block. - BasicBlock::iterator I = BB->getFirstNonPHIOrDbg(); + BasicBlock::iterator I = BB->getFirstNonPHIOrDbgOrLifetime(); if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && TryToSimplifyUncondBranchFromEmptyBlock(BB)) return true; diff --git a/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp b/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp index a73bf04..973b105 100644 --- a/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp +++ b/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp @@ -13,15 +13,18 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/ValueMapper.h" -#include "llvm/Type.h" #include "llvm/Constants.h" #include "llvm/Function.h" +#include "llvm/InlineAsm.h" +#include "llvm/Instructions.h" #include "llvm/Metadata.h" -#include "llvm/ADT/SmallVector.h" using namespace llvm; -Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, - RemapFlags Flags) { +// Out of line method to get vtable etc for class. +void ValueMapTypeRemapper::Anchor() {} + +Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags, + ValueMapTypeRemapper *TypeMapper) { ValueToValueMapTy::iterator I = VM.find(V); // If the value already exists in the map, use it. @@ -29,8 +32,23 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, // Global values do not need to be seeded into the VM if they // are using the identity mapping. - if (isa<GlobalValue>(V) || isa<InlineAsm>(V) || isa<MDString>(V)) + if (isa<GlobalValue>(V) || isa<MDString>(V)) return VM[V] = const_cast<Value*>(V); + + if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) { + // Inline asm may need *type* remapping. + FunctionType *NewTy = IA->getFunctionType(); + if (TypeMapper) { + NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy)); + + if (NewTy != IA->getFunctionType()) + V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(), + IA->hasSideEffects(), IA->isAlignStack()); + } + + return VM[V] = const_cast<Value*>(V); + } + if (const MDNode *MD = dyn_cast<MDNode>(V)) { // If this is a module-level metadata and we know that nothing at the module @@ -45,14 +63,14 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, // Check all operands to see if any need to be remapped. for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) { Value *OP = MD->getOperand(i); - if (OP == 0 || MapValue(OP, VM, Flags) == OP) continue; + if (OP == 0 || MapValue(OP, VM, Flags, TypeMapper) == OP) continue; // Ok, at least one operand needs remapping. SmallVector<Value*, 4> Elts; Elts.reserve(MD->getNumOperands()); for (i = 0; i != e; ++i) { Value *Op = MD->getOperand(i); - Elts.push_back(Op ? MapValue(Op, VM, Flags) : 0); + Elts.push_back(Op ? MapValue(Op, VM, Flags, TypeMapper) : 0); } MDNode *NewMD = MDNode::get(V->getContext(), Elts); Dummy->replaceAllUsesWith(NewMD); @@ -75,51 +93,75 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, return 0; if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) { - Function *F = cast<Function>(MapValue(BA->getFunction(), VM, Flags)); + Function *F = + cast<Function>(MapValue(BA->getFunction(), VM, Flags, TypeMapper)); BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(), VM, - Flags)); + Flags, TypeMapper)); return VM[V] = BlockAddress::get(F, BB ? BB : BA->getBasicBlock()); } - for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { - Value *Op = C->getOperand(i); - Value *Mapped = MapValue(Op, VM, Flags); - if (Mapped == C) continue; - - // Okay, the operands don't all match. We've already processed some or all - // of the operands, set them up now. - std::vector<Constant*> Ops; - Ops.reserve(C->getNumOperands()); - for (unsigned j = 0; j != i; ++j) - Ops.push_back(cast<Constant>(C->getOperand(i))); + // Otherwise, we have some other constant to remap. Start by checking to see + // if all operands have an identity remapping. + unsigned OpNo = 0, NumOperands = C->getNumOperands(); + Value *Mapped = 0; + for (; OpNo != NumOperands; ++OpNo) { + Value *Op = C->getOperand(OpNo); + Mapped = MapValue(Op, VM, Flags, TypeMapper); + if (Mapped != C) break; + } + + // See if the type mapper wants to remap the type as well. + Type *NewTy = C->getType(); + if (TypeMapper) + NewTy = TypeMapper->remapType(NewTy); + + // If the result type and all operands match up, then just insert an identity + // mapping. + if (OpNo == NumOperands && NewTy == C->getType()) + return VM[V] = C; + + // Okay, we need to create a new constant. We've already processed some or + // all of the operands, set them all up now. + SmallVector<Constant*, 8> Ops; + Ops.reserve(NumOperands); + for (unsigned j = 0; j != OpNo; ++j) + Ops.push_back(cast<Constant>(C->getOperand(j))); + + // If one of the operands mismatch, push it and the other mapped operands. + if (OpNo != NumOperands) { Ops.push_back(cast<Constant>(Mapped)); - + // Map the rest of the operands that aren't processed yet. - for (++i; i != e; ++i) - Ops.push_back(cast<Constant>(MapValue(C->getOperand(i), VM, Flags))); - - if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) - return VM[V] = CE->getWithOperands(Ops); - if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) - return VM[V] = ConstantArray::get(CA->getType(), Ops); - if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) - return VM[V] = ConstantStruct::get(CS->getType(), Ops); - assert(isa<ConstantVector>(C) && "Unknown mapped constant type"); - return VM[V] = ConstantVector::get(Ops); + for (++OpNo; OpNo != NumOperands; ++OpNo) + Ops.push_back(MapValue(cast<Constant>(C->getOperand(OpNo)), VM, + Flags, TypeMapper)); } - - // If we reach here, all of the operands of the constant match. - return VM[V] = C; + + if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) + return VM[V] = CE->getWithOperands(Ops, NewTy); + if (isa<ConstantArray>(C)) + return VM[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops); + if (isa<ConstantStruct>(C)) + return VM[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops); + if (isa<ConstantVector>(C)) + return VM[V] = ConstantVector::get(Ops); + // If this is a no-operand constant, it must be because the type was remapped. + if (isa<UndefValue>(C)) + return VM[V] = UndefValue::get(NewTy); + if (isa<ConstantAggregateZero>(C)) + return VM[V] = ConstantAggregateZero::get(NewTy); + assert(isa<ConstantPointerNull>(C)); + return VM[V] = ConstantPointerNull::get(cast<PointerType>(NewTy)); } /// RemapInstruction - Convert the instruction operands from referencing the /// current values into those specified by VMap. /// void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap, - RemapFlags Flags) { + RemapFlags Flags, ValueMapTypeRemapper *TypeMapper){ // Remap operands. for (User::op_iterator op = I->op_begin(), E = I->op_end(); op != E; ++op) { - Value *V = MapValue(*op, VMap, Flags); + Value *V = MapValue(*op, VMap, Flags, TypeMapper); // If we aren't ignoring missing entries, assert that something happened. if (V != 0) *op = V; @@ -128,14 +170,32 @@ void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap, "Referenced value not in value map!"); } - // Remap attached metadata. + // Remap phi nodes' incoming blocks. + if (PHINode *PN = dyn_cast<PHINode>(I)) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + Value *V = MapValue(PN->getIncomingBlock(i), VMap, Flags); + // If we aren't ignoring missing entries, assert that something happened. + if (V != 0) + PN->setIncomingBlock(i, cast<BasicBlock>(V)); + else + assert((Flags & RF_IgnoreMissingEntries) && + "Referenced block not in value map!"); + } + } + + // Remap attached metadata. Don't bother remapping DebugLoc, it can never + // have mappings to do. SmallVector<std::pair<unsigned, MDNode *>, 4> MDs; - I->getAllMetadata(MDs); + I->getAllMetadataOtherThanDebugLoc(MDs); for (SmallVectorImpl<std::pair<unsigned, MDNode *> >::iterator MI = MDs.begin(), ME = MDs.end(); MI != ME; ++MI) { - Value *Old = MI->second; - Value *New = MapValue(Old, VMap, Flags); + MDNode *Old = MI->second; + MDNode *New = MapValue(Old, VMap, Flags, TypeMapper); if (New != Old) - I->setMetadata(MI->first, cast<MDNode>(New)); + I->setMetadata(MI->first, New); } + + // If the instruction's type is being remapped, do so now. + if (TypeMapper) + I->mutateType(TypeMapper->remapType(I->getType())); } |
