//===-- Local.cpp - Functions to perform local transformations ------------===//
//
+// 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 family of functions perform various local transformations to the
// program.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/Local.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iOperators.h"
-#include "llvm/ConstantHandling.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Instructions.h"
+#include "llvm/Intrinsics.h"
+#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Support/GetElementPtrTypeIterator.h"
+#include "llvm/Support/MathExtras.h"
+#include <cerrno>
+using namespace llvm;
//===----------------------------------------------------------------------===//
// Local constant propagation...
//
-// ConstantFoldInstruction - If an instruction references constants, try to fold
-// them together...
-//
-bool doConstantPropagation(BasicBlock::iterator &II) {
+/// 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;
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<PHINode>(I)) {
+ if (PN->getNumIncomingValues() == 0)
+ return Constant::getNullValue(PN->getType());
+
+ Constant *Result = dyn_cast<Constant>(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;
+ }
+
+ Constant *Op0 = 0, *Op1 = 0;
+ switch (I->getNumOperands()) {
+ default:
+ case 2:
+ Op1 = dyn_cast<Constant>(I->getOperand(1));
+ if (Op1 == 0) return 0; // Not a constant?, can't fold
+ /* FALL THROUGH */
+ case 1:
+ Op0 = dyn_cast<Constant>(I->getOperand(0));
+ if (Op0 == 0) return 0; // Not a constant?, can't fold
+ break;
+ case 0: return 0;
+ }
+
+ if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) {
+ return ConstantExpr::get(I->getOpcode(), Op0, Op1);
+ } else if (isa<ICmpInst>(I)) {
+ return ConstantExpr::getICmp(cast<ICmpInst>(I)->getPredicate(), Op0, Op1);
+ } else if (isa<FCmpInst>(I)) {
+ return ConstantExpr::getFCmp(cast<FCmpInst>(I)->getPredicate(), Op0, Op1);
+ }
+
+ // Scan the operand list, checking to see if they are all constants, if so,
+ // hand off to ConstantFoldInstOperands.
+ std::vector<Constant*> Ops;
+ for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
+ if (Constant *Op = dyn_cast<Constant>(I->getOperand(i)))
+ Ops.push_back(Op);
+ else
+ return 0; // All operands not constant!
+
+ return ConstantFoldInstOperands(I, Ops);
+}
+
+/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
+/// specified opcode and operands. If successful, the constant result is
+/// returned, if not, null is returned. Note that this function can fail when
+/// attempting to fold instructions like loads and stores, which have no
+/// constant expression form.
+///
+Constant *llvm::ConstantFoldInstOperands(const Instruction* I,
+ const std::vector<Constant*> &Ops) {
+ unsigned Opc = I->getOpcode();
+ const Type *DestTy = I->getType();
+
+ // Handle easy binops first
+ if (isa<BinaryOperator>(I))
+ return ConstantExpr::get(Opc, Ops[0], Ops[1]);
+
+ switch (Opc) {
+ default: return 0;
+ case Instruction::Call:
+ if (Function *F = dyn_cast<Function>(Ops[0])) {
+ if (canConstantFoldCallTo(F)) {
+ std::vector<Constant*> Args(Ops.begin()+1, Ops.end());
+ return ConstantFoldCall(F, Args);
+ }
+ }
+ return 0;
+ case Instruction::ICmp:
+ case Instruction::FCmp:
+ return ConstantExpr::getCompare(cast<CmpInst>(I)->getPredicate(), Ops[0],
+ Ops[1]);
+ case Instruction::Shl:
+ case Instruction::LShr:
+ case Instruction::AShr:
+ return ConstantExpr::get(Opc, Ops[0], Ops[1]);
+ case Instruction::Trunc:
+ case Instruction::ZExt:
+ case Instruction::SExt:
+ case Instruction::FPTrunc:
+ case Instruction::FPExt:
+ case Instruction::UIToFP:
+ case Instruction::SIToFP:
+ case Instruction::FPToUI:
+ case Instruction::FPToSI:
+ case Instruction::PtrToInt:
+ case Instruction::IntToPtr:
+ case Instruction::BitCast:
+ return ConstantExpr::getCast(Opc, Ops[0], DestTy);
+ case Instruction::Select:
+ return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
+ case Instruction::ExtractElement:
+ return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
+ case Instruction::InsertElement:
+ return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
+ case Instruction::ShuffleVector:
+ return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
+ case Instruction::GetElementPtr:
+ return ConstantExpr::getGetElementPtr(Ops[0],
+ std::vector<Constant*>(Ops.begin()+1,
+ Ops.end()));
+ }
+}
+
// ConstantFoldTerminator - If a terminator instruction is predicated on a
// constant value, convert it into an unconditional branch to the constant
// destination.
//
-bool ConstantFoldTerminator(BasicBlock *BB) {
+bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
TerminatorInst *T = BB->getTerminator();
-
+
// Branch - See if we are conditional jumping on constant
if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
if (BI->isUnconditional()) return false; // Can't optimize uncond branch
BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
- if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
+ if (ConstantInt *Cond = dyn_cast<ConstantInt>(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()
+ //cerr << "Function: " << T->getParent()->getParent()
+ // << "\nRemoving branch from " << T->getParent()
// << "\n\nTo: " << OldDest << endl;
// Let the basic block know that we are letting go of it. Based on this,
BI->setUnconditionalDest(Destination);
return true;
} else if (Dest2 == Dest1) { // Conditional branch to same location?
- // This branch matches something like this:
+ // This branch matches something like this:
// br bool %cond, label %Dest, label %Dest
// and changes it into: br label %Dest
} 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(ICmpInst::ICMP_EQ, SI->getCondition(),
+ SI->getSuccessorValue(1), "cond", SI);
// Insert the new branch...
new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
return false;
}
+/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
+/// getelementptr constantexpr, return the constant value being addressed by the
+/// constant expression, or null if something is funny and we can't decide.
+Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C,
+ ConstantExpr *CE) {
+ if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
+ return 0; // Do not allow stepping over the value!
+
+ // Loop over all of the operands, tracking down which value we are
+ // addressing...
+ gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
+ for (++I; I != E; ++I)
+ if (const StructType *STy = dyn_cast<StructType>(*I)) {
+ ConstantInt *CU = cast<ConstantInt>(I.getOperand());
+ assert(CU->getZExtValue() < STy->getNumElements() &&
+ "Struct index out of range!");
+ unsigned El = (unsigned)CU->getZExtValue();
+ if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
+ C = CS->getOperand(El);
+ } else if (isa<ConstantAggregateZero>(C)) {
+ C = Constant::getNullValue(STy->getElementType(El));
+ } else if (isa<UndefValue>(C)) {
+ C = UndefValue::get(STy->getElementType(El));
+ } else {
+ return 0;
+ }
+ } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
+ if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) {
+ if (CI->getZExtValue() >= ATy->getNumElements())
+ return 0;
+ if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
+ C = CA->getOperand(CI->getZExtValue());
+ else if (isa<ConstantAggregateZero>(C))
+ C = Constant::getNullValue(ATy->getElementType());
+ else if (isa<UndefValue>(C))
+ C = UndefValue::get(ATy->getElementType());
+ else
+ return 0;
+ } else if (const PackedType *PTy = dyn_cast<PackedType>(*I)) {
+ if (CI->getZExtValue() >= PTy->getNumElements())
+ return 0;
+ if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C))
+ C = CP->getOperand(CI->getZExtValue());
+ else if (isa<ConstantAggregateZero>(C))
+ C = Constant::getNullValue(PTy->getElementType());
+ else if (isa<UndefValue>(C))
+ C = UndefValue::get(PTy->getElementType());
+ else
+ return 0;
+ } else {
+ return 0;
+ }
+ } else {
+ return 0;
+ }
+ return C;
+}
//===----------------------------------------------------------------------===//
// Local dead code elimination...
//
-bool isInstructionTriviallyDead(Instruction *I) {
- return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I);
+bool llvm::isInstructionTriviallyDead(Instruction *I) {
+ if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
+
+ if (!I->mayWriteToMemory()) return true;
+
+ if (CallInst *CI = dyn_cast<CallInst>(I))
+ if (Function *F = CI->getCalledFunction()) {
+ unsigned IntrinsicID = F->getIntrinsicID();
+#define GET_SIDE_EFFECT_INFO
+#include "llvm/Intrinsics.gen"
+#undef GET_SIDE_EFFECT_INFO
+ }
+ return false;
}
// dceInstruction - Inspect the instruction at *BBI and figure out if it's
// to point to the instruction that immediately succeeded the original
// instruction.
//
-bool dceInstruction(BasicBlock::iterator &BBI) {
+bool llvm::dceInstruction(BasicBlock::iterator &BBI) {
// Look for un"used" definitions...
if (isInstructionTriviallyDead(BBI)) {
BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye
projects / oota-llvm.git / blobdiff