X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLocal.cpp;h=4ff1e9ad24aea84493901747cf1fb087bdd527d9;hb=f2becca90b832cc02345fba063b9b439b2be33ad;hp=07b3249c8c4eafc88136f66cd643455312ce4808;hpb=1d3b71846b128c20164af62ceadef7d0eff245fa;p=oota-llvm.git diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 07b3249c8c4..4ff1e9ad24a 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -12,105 +12,71 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Support/MathExtras.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Constants.h" +#include "llvm/GlobalAlias.h" +#include "llvm/GlobalVariable.h" +#include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" #include "llvm/Intrinsics.h" -#include -#include +#include "llvm/IntrinsicInst.h" +#include "llvm/LLVMContext.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/DebugInfo.h" +#include "llvm/Analysis/MallocFreeHelper.h" +#include "llvm/Analysis/ProfileInfo.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Support/GetElementPtrTypeIterator.h" +#include "llvm/Support/MathExtras.h" using namespace llvm; //===----------------------------------------------------------------------===// -// Local constant propagation... +// Local analysis. // -/// doConstantPropagation - If an instruction references constants, try to fold -/// them together... -/// -bool llvm::doConstantPropagation(BasicBlock::iterator &II) { - if (Constant *C = ConstantFoldInstruction(II)) { - // Replaces all of the uses of a variable with uses of the constant. - II->replaceAllUsesWith(C); - - // Remove the instruction from the basic block... - II = II->getParent()->getInstList().erase(II); - return true; - } +/// isSafeToLoadUnconditionally - Return true if we know that executing a load +/// from this value cannot trap. If it is not obviously safe to load from the +/// specified pointer, we do a quick local scan of the basic block containing +/// ScanFrom, to determine if the address is already accessed. +bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) { + // If it is an alloca it is always safe to load from. + if (isa(V)) return true; + + // If it is a global variable it is mostly safe to load from. + if (const GlobalValue *GV = dyn_cast(V)) + // Don't try to evaluate aliases. External weak GV can be null. + return !isa(GV) && !GV->hasExternalWeakLinkage(); + + // Otherwise, be a little bit agressive by scanning the local block where we + // want to check to see if the pointer is already being loaded or stored + // from/to. If so, the previous load or store would have already trapped, + // so there is no harm doing an extra load (also, CSE will later eliminate + // the load entirely). + BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin(); + + while (BBI != E) { + --BBI; + + // If we see a free or a call which may write to memory (i.e. which might do + // a free) the pointer could be marked invalid. + if (isFreeCall(BBI) || (isa(BBI) && BBI->mayWriteToMemory() && + !isa(BBI))) + return false; + if (LoadInst *LI = dyn_cast(BBI)) { + if (LI->getOperand(0) == V) return true; + } else if (StoreInst *SI = dyn_cast(BBI)) { + if (SI->getOperand(1) == V) return true; + } + } return false; } -/// ConstantFoldInstruction - Attempt to constant fold the specified -/// instruction. If successful, the constant result is returned, if not, null -/// is returned. Note that this function can only fail when attempting to fold -/// instructions like loads and stores, which have no constant expression form. -/// -Constant *llvm::ConstantFoldInstruction(Instruction *I) { - if (PHINode *PN = dyn_cast(I)) { - if (PN->getNumIncomingValues() == 0) - return Constant::getNullValue(PN->getType()); - - Constant *Result = dyn_cast(PN->getIncomingValue(0)); - if (Result == 0) return 0; - - // Handle PHI nodes specially here... - for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) - if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) - return 0; // Not all the same incoming constants... - - // If we reach here, all incoming values are the same constant. - return Result; - } else if (CallInst *CI = dyn_cast(I)) { - if (Function *F = CI->getCalledFunction()) - if (canConstantFoldCallTo(F)) { - std::vector Args; - for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) - if (Constant *Op = dyn_cast(CI->getOperand(i))) - Args.push_back(Op); - else - return 0; - return ConstantFoldCall(F, Args); - } - return 0; - } - Constant *Op0 = 0, *Op1 = 0; - switch (I->getNumOperands()) { - default: - case 2: - Op1 = dyn_cast(I->getOperand(1)); - if (Op1 == 0) return 0; // Not a constant?, can't fold - case 1: - Op0 = dyn_cast(I->getOperand(0)); - if (Op0 == 0) return 0; // Not a constant?, can't fold - break; - case 0: return 0; - } - - if (isa(I) || isa(I)) - return ConstantExpr::get(I->getOpcode(), Op0, Op1); - - switch (I->getOpcode()) { - default: return 0; - case Instruction::Cast: - return ConstantExpr::getCast(Op0, I->getType()); - case Instruction::Select: - if (Constant *Op2 = dyn_cast(I->getOperand(2))) - return ConstantExpr::getSelect(Op0, Op1, Op2); - return 0; - case Instruction::GetElementPtr: - std::vector IdxList; - IdxList.reserve(I->getNumOperands()-1); - if (Op1) IdxList.push_back(Op1); - for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i) - if (Constant *C = dyn_cast(I->getOperand(i))) - IdxList.push_back(C); - else - return 0; // Non-constant operand - return ConstantExpr::getGetElementPtr(Op0, IdxList); - } -} +//===----------------------------------------------------------------------===// +// Local constant propagation. +// // ConstantFoldTerminator - If a terminator instruction is predicated on a // constant value, convert it into an unconditional branch to the constant @@ -122,14 +88,14 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) { // Branch - See if we are conditional jumping on constant if (BranchInst *BI = dyn_cast(T)) { if (BI->isUnconditional()) return false; // Can't optimize uncond branch - BasicBlock *Dest1 = cast(BI->getOperand(0)); - BasicBlock *Dest2 = cast(BI->getOperand(1)); + BasicBlock *Dest1 = BI->getSuccessor(0); + BasicBlock *Dest2 = BI->getSuccessor(1); - if (ConstantBool *Cond = dyn_cast(BI->getCondition())) { + if (ConstantInt *Cond = dyn_cast(BI->getCondition())) { // Are we branching on constant? // YES. Change to unconditional branch... - BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; - BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; + BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; + BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; //cerr << "Function: " << T->getParent()->getParent() // << "\nRemoving branch from " << T->getParent() @@ -200,7 +166,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) { // now. if (TheOnlyDest) { // Insert the new branch.. - new BranchInst(TheOnlyDest, SI); + BranchInst::Create(TheOnlyDest, SI); BasicBlock *BB = SI->getParent(); // Remove entries from PHI nodes which we no longer branch to... @@ -219,217 +185,166 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) { } else if (SI->getNumSuccessors() == 2) { // Otherwise, we can fold this switch into a conditional branch // instruction if it has only one non-default destination. - Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), - SI->getSuccessorValue(1), "cond", SI); + Value *Cond = new ICmpInst(SI, ICmpInst::ICMP_EQ, SI->getCondition(), + SI->getSuccessorValue(1), "cond"); // Insert the new branch... - new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); + BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); // Delete the old switch... - SI->getParent()->getInstList().erase(SI); + SI->eraseFromParent(); return true; } } return false; } -/// canConstantFoldCallTo - Return true if its even possible to fold a call to -/// the specified function. -bool llvm::canConstantFoldCallTo(Function *F) { - const std::string &Name = F->getName(); - switch (F->getIntrinsicID()) { - case Intrinsic::isunordered: return true; - default: break; - } +//===----------------------------------------------------------------------===// +// Local dead code elimination... +// - switch (Name[0]) - { - case 'a': - return Name == "acos" || Name == "asin" || Name == "atan" || - Name == "atan2"; - case 'c': - return Name == "ceil" || Name == "cos" || Name == "cosf" || - Name == "cosh"; - case 'e': - return Name == "exp"; - case 'f': - return Name == "fabs" || Name == "fmod" || Name == "floor"; - case 'l': - return Name == "log" || Name == "log10"; - case 'p': - return Name == "pow"; - case 's': - return Name == "sin" || Name == "sinh" || Name == "sqrt"; - case 't': - return Name == "tan" || Name == "tanh"; - default: - return false; - } -} +/// isInstructionTriviallyDead - Return true if the result produced by the +/// instruction is not used, and the instruction has no side effects. +/// +bool llvm::isInstructionTriviallyDead(Instruction *I) { + if (!I->use_empty() || isa(I)) return false; + + // We don't want debug info removed by anything this general. + if (isa(I)) return false; + + if (!I->mayHaveSideEffects()) return true; -static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, - const Type *Ty) { - errno = 0; - V = NativeFP(V); - if (errno == 0) - return ConstantFP::get(Ty, V); - return 0; + // Special case intrinsics that "may have side effects" but can be deleted + // when dead. + if (IntrinsicInst *II = dyn_cast(I)) + // Safe to delete llvm.stacksave if dead. + if (II->getIntrinsicID() == Intrinsic::stacksave) + return true; + return false; } -/// ConstantFoldCall - Attempt to constant fold a call to the specified function -/// with the specified arguments, returning null if unsuccessful. -Constant *llvm::ConstantFoldCall(Function *F, - const std::vector &Operands) { - const std::string &Name = F->getName(); - const Type *Ty = F->getReturnType(); - - if (Operands.size() == 1) { - if (ConstantFP *Op = dyn_cast(Operands[0])) { - double V = Op->getValue(); - switch (Name[0]) - { - case 'a': - if (Name == "acos") - return ConstantFoldFP(acos, V, Ty); - else if (Name == "asin") - return ConstantFoldFP(asin, V, Ty); - else if (Name == "atan") - return ConstantFP::get(Ty, atan(V)); - break; - case 'c': - if (Name == "ceil") - return ConstantFoldFP(ceil, V, Ty); - else if (Name == "cos") - return ConstantFP::get(Ty, cos(V)); - else if (Name == "cosh") - return ConstantFP::get(Ty, cosh(V)); - break; - case 'e': - if (Name == "exp") - return ConstantFP::get(Ty, exp(V)); - break; - case 'f': - if (Name == "fabs") - return ConstantFP::get(Ty, fabs(V)); - else if (Name == "floor") - return ConstantFoldFP(floor, V, Ty); - break; - case 'l': - if (Name == "log" && V > 0) - return ConstantFP::get(Ty, log(V)); - else if (Name == "log10" && V > 0) - return ConstantFoldFP(log10, V, Ty); - break; - case 's': - if (Name == "sin") - return ConstantFP::get(Ty, sin(V)); - else if (Name == "sinh") - return ConstantFP::get(Ty, sinh(V)); - else if (Name == "sqrt" && V >= 0) - return ConstantFP::get(Ty, sqrt(V)); - break; - case 't': - if (Name == "tan") - return ConstantFP::get(Ty, tan(V)); - else if (Name == "tanh") - return ConstantFP::get(Ty, tanh(V)); - break; - default: - break; - } - } - } else if (Operands.size() == 2) { - if (ConstantFP *Op1 = dyn_cast(Operands[0])) { - double Op1V = Op1->getValue(); - if (ConstantFP *Op2 = dyn_cast(Operands[1])) { - double Op2V = Op2->getValue(); - - if (Name == "llvm.isunordered") - return ConstantBool::get(IsNAN(Op1V) || IsNAN(Op2V)); - else - if (Name == "pow") { - errno = 0; - double V = pow(Op1V, Op2V); - if (errno == 0) - return ConstantFP::get(Ty, V); - } else if (Name == "fmod") { - errno = 0; - double V = fmod(Op1V, Op2V); - if (errno == 0) - return ConstantFP::get(Ty, V); - } else if (Name == "atan2") - return ConstantFP::get(Ty, atan2(Op1V,Op2V)); - } - else if (Name == "pow" && Op1V == 1.0) { - return ConstantFP::get(Ty,1.0); - } - } else if (ConstantFP* Op2 = dyn_cast(Operands[1])) { - double Op2V = Op2->getValue(); - if (Name == "pow") - if (Op2V == 0.0) - return ConstantFP::get(Ty,1.0); - else if (Op2V == 1.0) - return Operands[0]; +/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a +/// trivially dead instruction, delete it. If that makes any of its operands +/// trivially dead, delete them too, recursively. +void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { + Instruction *I = dyn_cast(V); + if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) + return; + + SmallVector DeadInsts; + DeadInsts.push_back(I); + + while (!DeadInsts.empty()) { + I = DeadInsts.pop_back_val(); + + // Null out all of the instruction's operands to see if any operand becomes + // dead as we go. + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { + Value *OpV = I->getOperand(i); + I->setOperand(i, 0); + + if (!OpV->use_empty()) continue; + + // If the operand is an instruction that became dead as we nulled out the + // operand, and if it is 'trivially' dead, delete it in a future loop + // iteration. + if (Instruction *OpI = dyn_cast(OpV)) + if (isInstructionTriviallyDead(OpI)) + DeadInsts.push_back(OpI); } + + I->eraseFromParent(); } - return 0; } - - +/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively +/// dead PHI node, due to being a def-use chain of single-use nodes that +/// either forms a cycle or is terminated by a trivially dead instruction, +/// delete it. If that makes any of its operands trivially dead, delete them +/// too, recursively. +void +llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { + // We can remove a PHI if it is on a cycle in the def-use graph + // where each node in the cycle has degree one, i.e. only one use, + // and is an instruction with no side effects. + if (!PN->hasOneUse()) + return; + + SmallPtrSet PHIs; + PHIs.insert(PN); + for (Instruction *J = cast(*PN->use_begin()); + J->hasOneUse() && !J->mayHaveSideEffects(); + J = cast(*J->use_begin())) + // If we find a PHI more than once, we're on a cycle that + // won't prove fruitful. + if (PHINode *JP = dyn_cast(J)) + if (!PHIs.insert(cast(JP))) { + // Break the cycle and delete the PHI and its operands. + JP->replaceAllUsesWith(UndefValue::get(JP->getType())); + RecursivelyDeleteTriviallyDeadInstructions(JP); + break; + } +} //===----------------------------------------------------------------------===// -// Local dead code elimination... +// Control Flow Graph Restructuring... // -bool llvm::isInstructionTriviallyDead(Instruction *I) { - return I->use_empty() && !I->mayWriteToMemory() && !isa(I); +/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its +/// predecessor is known to have one successor (DestBB!). Eliminate the edge +/// between them, moving the instructions in the predecessor into DestBB and +/// deleting the predecessor block. +/// +void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { + // If BB has single-entry PHI nodes, fold them. + while (PHINode *PN = dyn_cast(DestBB->begin())) { + Value *NewVal = PN->getIncomingValue(0); + // Replace self referencing PHI with undef, it must be dead. + if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); + PN->replaceAllUsesWith(NewVal); + PN->eraseFromParent(); + } + + 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()); + + // Anything that branched to PredBB now branches to DestBB. + PredBB->replaceAllUsesWith(DestBB); + + if (P) { + ProfileInfo *PI = P->getAnalysisIfAvailable(); + if (PI) { + PI->replaceAllUses(PredBB, DestBB); + PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); + } + } + // Nuke BB. + PredBB->eraseFromParent(); } -// dceInstruction - Inspect the instruction at *BBI and figure out if it's -// [trivially] dead. If so, remove the instruction and update the iterator -// to point to the instruction that immediately succeeded the original -// instruction. -// -bool llvm::dceInstruction(BasicBlock::iterator &BBI) { - // Look for un"used" definitions... - if (isInstructionTriviallyDead(BBI)) { - BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye - return true; +/// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used +/// by DbgIntrinsics. If DbgInUses is specified then the vector is filled +/// with the DbgInfoIntrinsic that use the instruction I. +bool llvm::OnlyUsedByDbgInfoIntrinsics(Instruction *I, + SmallVectorImpl *DbgInUses) { + if (DbgInUses) + DbgInUses->clear(); + + for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; + ++UI) { + if (DbgInfoIntrinsic *DI = dyn_cast(*UI)) { + if (DbgInUses) + DbgInUses->push_back(DI); + } else { + if (DbgInUses) + DbgInUses->clear(); + return false; + } } - return false; + return true; } -//===----------------------------------------------------------------------===// -// PHI Instruction Simplification -// - -/// hasConstantValue - If the specified PHI node always merges together the same -/// value, return the value, otherwise return null. -/// -Value *llvm::hasConstantValue(PHINode *PN) { - // If the PHI node only has one incoming value, eliminate the PHI node... - if (PN->getNumIncomingValues() == 1) - return PN->getIncomingValue(0); - - // Otherwise if all of the incoming values are the same for the PHI, replace - // the PHI node with the incoming value. - // - Value *InVal = 0; - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (PN->getIncomingValue(i) != PN && // Not the PHI node itself... - !isa(PN->getIncomingValue(i))) - if (InVal && PN->getIncomingValue(i) != InVal) - return 0; // Not the same, bail out. - else - InVal = PN->getIncomingValue(i); - - // The only case that could cause InVal to be null is if we have a PHI node - // that only has entries for itself. In this case, there is no entry into the - // loop, so kill the PHI. - // - if (InVal == 0) InVal = UndefValue::get(PN->getType()); - - // All of the incoming values are the same, return the value now. - return InVal; -}