X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FInstruction.cpp;h=2c8b8b23b18e37fe8ab22439812e70ce14385945;hb=b34d837397053da8e9bff90dd714e24f2a3b98b3;hp=a2d0ba9174bf74d410520b17d5daf100b27a7c96;hpb=6b63452c3ad26678b32f93dbca55902a313ee4e9;p=oota-llvm.git diff --git a/lib/VMCore/Instruction.cpp b/lib/VMCore/Instruction.cpp index a2d0ba9174b..2c8b8b23b18 100644 --- a/lib/VMCore/Instruction.cpp +++ b/lib/VMCore/Instruction.cpp @@ -1,20 +1,28 @@ -//===-- Instruction.cpp - Implement the Instruction class --------*- C++ -*--=// +//===-- Instruction.cpp - Implement the Instruction class -----------------===// +// +// 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 Instruction class for the VMCore library. // //===----------------------------------------------------------------------===// -#include "llvm/Function.h" -#include "llvm/SymbolTable.h" +#include "llvm/Instruction.h" #include "llvm/Type.h" -#include "Support/LeakDetector.h" +#include "llvm/Instructions.h" +#include "llvm/Constants.h" +#include "llvm/Module.h" +#include "llvm/Support/CallSite.h" +#include "llvm/Support/LeakDetector.h" +using namespace llvm; -Instruction::Instruction(const Type *ty, unsigned it, const std::string &Name, +Instruction::Instruction(const Type *ty, unsigned it, Use *Ops, unsigned NumOps, Instruction *InsertBefore) - : User(ty, Value::InstructionVal, Name) { - Parent = 0; - iType = it; - + : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(0) { // Make sure that we get added to a basicblock LeakDetector::addGarbageObject(this); @@ -26,26 +34,62 @@ Instruction::Instruction(const Type *ty, unsigned it, const std::string &Name, } } +Instruction::Instruction(const Type *ty, unsigned it, Use *Ops, unsigned NumOps, + BasicBlock *InsertAtEnd) + : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(0) { + // Make sure that we get added to a basicblock + LeakDetector::addGarbageObject(this); + + // append this instruction into the basic block + assert(InsertAtEnd && "Basic block to append to may not be NULL!"); + InsertAtEnd->getInstList().push_back(this); +} + + +// Out of line virtual method, so the vtable, etc has a home. +Instruction::~Instruction() { + assert(Parent == 0 && "Instruction still linked in the program!"); + if (hasMetadataHashEntry()) + clearMetadataHashEntries(); +} + + void Instruction::setParent(BasicBlock *P) { - if (getParent()) - LeakDetector::addGarbageObject(this); + if (getParent()) { + if (!P) LeakDetector::addGarbageObject(this); + } else { + if (P) LeakDetector::removeGarbageObject(this); + } Parent = P; +} - if (getParent()) - LeakDetector::removeGarbageObject(this); +void Instruction::removeFromParent() { + getParent()->getInstList().remove(this); } -// Specialize setName to take care of symbol table majik -void Instruction::setName(const std::string &name, SymbolTable *ST) { - BasicBlock *P = 0; Function *PP = 0; - assert((ST == 0 || !getParent() || !getParent()->getParent() || - ST == &getParent()->getParent()->getSymbolTable()) && - "Invalid symtab argument!"); - if ((P = getParent()) && (PP = P->getParent()) && hasName()) - PP->getSymbolTable().remove(this); - Value::setName(name); - if (PP && hasName()) PP->getSymbolTable().insert(this); +void Instruction::eraseFromParent() { + getParent()->getInstList().erase(this); +} + +/// insertBefore - Insert an unlinked instructions into a basic block +/// immediately before the specified instruction. +void Instruction::insertBefore(Instruction *InsertPos) { + InsertPos->getParent()->getInstList().insert(InsertPos, this); +} + +/// insertAfter - Insert an unlinked instructions into a basic block +/// immediately after the specified instruction. +void Instruction::insertAfter(Instruction *InsertPos) { + InsertPos->getParent()->getInstList().insertAfter(InsertPos, this); +} + +/// moveBefore - Unlink this instruction from its current basic block and +/// insert it into the basic block that MovePos lives in, right before +/// MovePos. +void Instruction::moveBefore(Instruction *MovePos) { + MovePos->getParent()->getInstList().splice(MovePos,getParent()->getInstList(), + this); } @@ -55,66 +99,255 @@ const char *Instruction::getOpcodeName(unsigned OpCode) { case Ret: return "ret"; case Br: return "br"; case Switch: return "switch"; + case IndirectBr: return "indirectbr"; case Invoke: return "invoke"; case Unwind: return "unwind"; - + case Unreachable: return "unreachable"; + // Standard binary operators... case Add: return "add"; + case FAdd: return "fadd"; case Sub: return "sub"; + case FSub: return "fsub"; case Mul: return "mul"; - case Div: return "div"; - case Rem: return "rem"; + case FMul: return "fmul"; + case UDiv: return "udiv"; + case SDiv: return "sdiv"; + case FDiv: return "fdiv"; + case URem: return "urem"; + case SRem: return "srem"; + case FRem: return "frem"; // Logical operators... case And: return "and"; case Or : return "or"; case Xor: return "xor"; - // SetCC operators... - case SetLE: return "setle"; - case SetGE: return "setge"; - case SetLT: return "setlt"; - case SetGT: return "setgt"; - case SetEQ: return "seteq"; - case SetNE: return "setne"; - // Memory instructions... - case Malloc: return "malloc"; - case Free: return "free"; case Alloca: return "alloca"; case Load: return "load"; case Store: return "store"; case GetElementPtr: return "getelementptr"; - + + // Convert instructions... + case Trunc: return "trunc"; + case ZExt: return "zext"; + case SExt: return "sext"; + case FPTrunc: return "fptrunc"; + case FPExt: return "fpext"; + case FPToUI: return "fptoui"; + case FPToSI: return "fptosi"; + case UIToFP: return "uitofp"; + case SIToFP: return "sitofp"; + case IntToPtr: return "inttoptr"; + case PtrToInt: return "ptrtoint"; + case BitCast: return "bitcast"; + // Other instructions... - case PHINode: return "phi"; - case Cast: return "cast"; - case Call: return "call"; - case Shl: return "shl"; - case Shr: return "shr"; - case VarArg: return "va_arg"; + case ICmp: return "icmp"; + case FCmp: return "fcmp"; + case PHI: return "phi"; + case Select: return "select"; + case Call: return "call"; + case Shl: return "shl"; + case LShr: return "lshr"; + case AShr: return "ashr"; + case VAArg: return "va_arg"; + case ExtractElement: return "extractelement"; + case InsertElement: return "insertelement"; + case ShuffleVector: return "shufflevector"; + case ExtractValue: return "extractvalue"; + case InsertValue: return "insertvalue"; default: return " "; } - + return 0; } +/// isIdenticalTo - Return true if the specified instruction is exactly +/// identical to the current one. This means that all operands match and any +/// extra information (e.g. load is volatile) agree. +bool Instruction::isIdenticalTo(const Instruction *I) const { + return isIdenticalToWhenDefined(I) && + SubclassOptionalData == I->SubclassOptionalData; +} + +/// isIdenticalToWhenDefined - This is like isIdenticalTo, except that it +/// ignores the SubclassOptionalData flags, which specify conditions +/// under which the instruction's result is undefined. +bool Instruction::isIdenticalToWhenDefined(const Instruction *I) const { + if (getOpcode() != I->getOpcode() || + getNumOperands() != I->getNumOperands() || + getType() != I->getType()) + return false; + + // We have two instructions of identical opcode and #operands. Check to see + // if all operands are the same. + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) + if (getOperand(i) != I->getOperand(i)) + return false; + + // Check special state that is a part of some instructions. + if (const LoadInst *LI = dyn_cast(this)) + return LI->isVolatile() == cast(I)->isVolatile() && + LI->getAlignment() == cast(I)->getAlignment(); + if (const StoreInst *SI = dyn_cast(this)) + return SI->isVolatile() == cast(I)->isVolatile() && + SI->getAlignment() == cast(I)->getAlignment(); + if (const CmpInst *CI = dyn_cast(this)) + return CI->getPredicate() == cast(I)->getPredicate(); + if (const CallInst *CI = dyn_cast(this)) + return CI->isTailCall() == cast(I)->isTailCall() && + CI->getCallingConv() == cast(I)->getCallingConv() && + CI->getAttributes() == cast(I)->getAttributes(); + if (const InvokeInst *CI = dyn_cast(this)) + return CI->getCallingConv() == cast(I)->getCallingConv() && + CI->getAttributes() == cast(I)->getAttributes(); + if (const InsertValueInst *IVI = dyn_cast(this)) { + if (IVI->getNumIndices() != cast(I)->getNumIndices()) + return false; + for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i) + if (IVI->idx_begin()[i] != cast(I)->idx_begin()[i]) + return false; + return true; + } + if (const ExtractValueInst *EVI = dyn_cast(this)) { + if (EVI->getNumIndices() != cast(I)->getNumIndices()) + return false; + for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i) + if (EVI->idx_begin()[i] != cast(I)->idx_begin()[i]) + return false; + return true; + } + + return true; +} + +// isSameOperationAs +// This should be kept in sync with isEquivalentOperation in +// lib/Transforms/IPO/MergeFunctions.cpp. +bool Instruction::isSameOperationAs(const Instruction *I) const { + if (getOpcode() != I->getOpcode() || + getNumOperands() != I->getNumOperands() || + getType() != I->getType()) + return false; + + // We have two instructions of identical opcode and #operands. Check to see + // if all operands are the same type + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) + if (getOperand(i)->getType() != I->getOperand(i)->getType()) + return false; + + // Check special state that is a part of some instructions. + if (const LoadInst *LI = dyn_cast(this)) + return LI->isVolatile() == cast(I)->isVolatile() && + LI->getAlignment() == cast(I)->getAlignment(); + if (const StoreInst *SI = dyn_cast(this)) + return SI->isVolatile() == cast(I)->isVolatile() && + SI->getAlignment() == cast(I)->getAlignment(); + if (const CmpInst *CI = dyn_cast(this)) + return CI->getPredicate() == cast(I)->getPredicate(); + if (const CallInst *CI = dyn_cast(this)) + return CI->isTailCall() == cast(I)->isTailCall() && + CI->getCallingConv() == cast(I)->getCallingConv() && + CI->getAttributes() == cast(I)->getAttributes(); + if (const InvokeInst *CI = dyn_cast(this)) + return CI->getCallingConv() == cast(I)->getCallingConv() && + CI->getAttributes() == + cast(I)->getAttributes(); + if (const InsertValueInst *IVI = dyn_cast(this)) { + if (IVI->getNumIndices() != cast(I)->getNumIndices()) + return false; + for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i) + if (IVI->idx_begin()[i] != cast(I)->idx_begin()[i]) + return false; + return true; + } + if (const ExtractValueInst *EVI = dyn_cast(this)) { + if (EVI->getNumIndices() != cast(I)->getNumIndices()) + return false; + for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i) + if (EVI->idx_begin()[i] != cast(I)->idx_begin()[i]) + return false; + return true; + } + + return true; +} + +/// isUsedOutsideOfBlock - Return true if there are any uses of I outside of the +/// specified block. Note that PHI nodes are considered to evaluate their +/// operands in the corresponding predecessor block. +bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const { + for (const_use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { + // PHI nodes uses values in the corresponding predecessor block. For other + // instructions, just check to see whether the parent of the use matches up. + const User *U = *UI; + const PHINode *PN = dyn_cast(U); + if (PN == 0) { + if (cast(U)->getParent() != BB) + return true; + continue; + } + + if (PN->getIncomingBlock(UI) != BB) + return true; + } + return false; +} + +/// mayReadFromMemory - Return true if this instruction may read memory. +/// +bool Instruction::mayReadFromMemory() const { + switch (getOpcode()) { + default: return false; + case Instruction::VAArg: + case Instruction::Load: + return true; + case Instruction::Call: + return !cast(this)->doesNotAccessMemory(); + case Instruction::Invoke: + return !cast(this)->doesNotAccessMemory(); + case Instruction::Store: + return cast(this)->isVolatile(); + } +} + +/// mayWriteToMemory - Return true if this instruction may modify memory. +/// +bool Instruction::mayWriteToMemory() const { + switch (getOpcode()) { + default: return false; + case Instruction::Store: + case Instruction::VAArg: + return true; + case Instruction::Call: + return !cast(this)->onlyReadsMemory(); + case Instruction::Invoke: + return !cast(this)->onlyReadsMemory(); + case Instruction::Load: + return cast(this)->isVolatile(); + } +} + +/// mayThrow - Return true if this instruction may throw an exception. +/// +bool Instruction::mayThrow() const { + if (const CallInst *CI = dyn_cast(this)) + return !CI->doesNotThrow(); + return false; +} /// isAssociative - Return true if the instruction is associative: /// -/// Associative operators satisfy: x op (y op z) === (x op y) op z) +/// Associative operators satisfy: x op (y op z) === (x op y) op z /// -/// In LLVM, the Add, Mul, And, Or, and Xor operators are associative, when not -/// applied to floating point types. +/// In LLVM, the Add, Mul, And, Or, and Xor operators are associative. /// -bool Instruction::isAssociative(unsigned Opcode, const Type *Ty) { - if (Opcode == Add || Opcode == Mul || - Opcode == And || Opcode == Or || Opcode == Xor) { - // Floating point operations do not associate! - return !Ty->isFloatingPoint(); - } - return 0; +bool Instruction::isAssociative(unsigned Opcode) { + return Opcode == And || Opcode == Or || Opcode == Xor || + Opcode == Add || Opcode == Mul; } /// isCommutative - Return true if the instruction is commutative: @@ -127,31 +360,77 @@ bool Instruction::isAssociative(unsigned Opcode, const Type *Ty) { bool Instruction::isCommutative(unsigned op) { switch (op) { case Add: + case FAdd: case Mul: - case And: + case FMul: + case And: case Or: case Xor: - case SetEQ: - case SetNE: return true; default: return false; } } +bool Instruction::isSafeToSpeculativelyExecute() const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) + if (Constant *C = dyn_cast(getOperand(i))) + if (C->canTrap()) + return false; -/// isTrappingInstruction - Return true if the instruction may trap. -/// -bool Instruction::isTrapping(unsigned op) { - switch(op) { - case Div: - case Rem: - case Load: - case Store: + switch (getOpcode()) { + default: + return true; + case UDiv: + case URem: { + // x / y is undefined if y == 0, but calcuations like x / 3 are safe. + ConstantInt *Op = dyn_cast(getOperand(1)); + return Op && !Op->isNullValue(); + } + case SDiv: + case SRem: { + // x / y is undefined if y == 0, and might be undefined if y == -1, + // but calcuations like x / 3 are safe. + ConstantInt *Op = dyn_cast(getOperand(1)); + return Op && !Op->isNullValue() && !Op->isAllOnesValue(); + } + case Load: { + const LoadInst *LI = cast(this); + if (LI->isVolatile()) + return false; + return LI->getPointerOperand()->isDereferenceablePointer(); + } case Call: + return false; // The called function could have undefined behavior or + // side-effects. + // FIXME: We should special-case some intrinsics (bswap, + // overflow-checking arithmetic, etc.) + case VAArg: + case Alloca: case Invoke: - return true; - default: - return false; + case PHI: + case Store: + case Ret: + case Br: + case IndirectBr: + case Switch: + case Unwind: + case Unreachable: + return false; // Misc instructions which have effects } } + +Instruction *Instruction::clone() const { + Instruction *New = clone_impl(); + New->SubclassOptionalData = SubclassOptionalData; + if (!hasMetadata()) + return New; + + // Otherwise, enumerate and copy over metadata from the old instruction to the + // new one. + SmallVector, 4> TheMDs; + getAllMetadata(TheMDs); + for (unsigned i = 0, e = TheMDs.size(); i != e; ++i) + New->setMetadata(TheMDs[i].first, TheMDs[i].second); + return New; +}