LLVM API Documentation

Instruction.cpp

Go to the documentation of this file.
00001 //===-- Instruction.cpp - Implement the Instruction class -----------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the Instruction class for the VMCore library.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Type.h"
00015 #include "llvm/Instructions.h"
00016 #include "llvm/Function.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/GlobalVariable.h"
00019 #include "llvm/Support/CallSite.h"
00020 #include "llvm/Support/LeakDetector.h"
00021 using namespace llvm;
00022 
00023 Instruction::Instruction(const Type *ty, unsigned it, Use *Ops, unsigned NumOps,
00024                          Instruction *InsertBefore)
00025   : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(0) {
00026   // Make sure that we get added to a basicblock
00027   LeakDetector::addGarbageObject(this);
00028 
00029   // If requested, insert this instruction into a basic block...
00030   if (InsertBefore) {
00031     assert(InsertBefore->getParent() &&
00032            "Instruction to insert before is not in a basic block!");
00033     InsertBefore->getParent()->getInstList().insert(InsertBefore, this);
00034   }
00035 }
00036 
00037 Instruction::Instruction(const Type *ty, unsigned it, Use *Ops, unsigned NumOps,
00038                          BasicBlock *InsertAtEnd)
00039   : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(0) {
00040   // Make sure that we get added to a basicblock
00041   LeakDetector::addGarbageObject(this);
00042 
00043   // append this instruction into the basic block
00044   assert(InsertAtEnd && "Basic block to append to may not be NULL!");
00045   InsertAtEnd->getInstList().push_back(this);
00046 }
00047 
00048 
00049 // Out of line virtual method, so the vtable, etc has a home.
00050 Instruction::~Instruction() {
00051   assert(Parent == 0 && "Instruction still linked in the program!");
00052 }
00053 
00054 
00055 void Instruction::setParent(BasicBlock *P) {
00056   if (getParent()) {
00057     if (!P) LeakDetector::addGarbageObject(this);
00058   } else {
00059     if (P) LeakDetector::removeGarbageObject(this);
00060   }
00061 
00062   Parent = P;
00063 }
00064 
00065 void Instruction::removeFromParent() {
00066   getParent()->getInstList().remove(this);
00067 }
00068 
00069 void Instruction::eraseFromParent() {
00070   getParent()->getInstList().erase(this);
00071 }
00072 
00073 /// insertBefore - Insert an unlinked instructions into a basic block
00074 /// immediately before the specified instruction.
00075 void Instruction::insertBefore(Instruction *InsertPos) {
00076   InsertPos->getParent()->getInstList().insert(InsertPos, this);
00077 }
00078 
00079 /// insertAfter - Insert an unlinked instructions into a basic block
00080 /// immediately after the specified instruction.
00081 void Instruction::insertAfter(Instruction *InsertPos) {
00082   InsertPos->getParent()->getInstList().insertAfter(InsertPos, this);
00083 }
00084 
00085 /// moveBefore - Unlink this instruction from its current basic block and
00086 /// insert it into the basic block that MovePos lives in, right before
00087 /// MovePos.
00088 void Instruction::moveBefore(Instruction *MovePos) {
00089   MovePos->getParent()->getInstList().splice(MovePos,getParent()->getInstList(),
00090                                              this);
00091 }
00092 
00093 
00094 const char *Instruction::getOpcodeName(unsigned OpCode) {
00095   switch (OpCode) {
00096   // Terminators
00097   case Ret:    return "ret";
00098   case Br:     return "br";
00099   case Switch: return "switch";
00100   case Invoke: return "invoke";
00101   case Unwind: return "unwind";
00102   case Unreachable: return "unreachable";
00103 
00104   // Standard binary operators...
00105   case Add: return "add";
00106   case FAdd: return "fadd";
00107   case Sub: return "sub";
00108   case FSub: return "fsub";
00109   case Mul: return "mul";
00110   case FMul: return "fmul";
00111   case UDiv: return "udiv";
00112   case SDiv: return "sdiv";
00113   case FDiv: return "fdiv";
00114   case URem: return "urem";
00115   case SRem: return "srem";
00116   case FRem: return "frem";
00117 
00118   // Logical operators...
00119   case And: return "and";
00120   case Or : return "or";
00121   case Xor: return "xor";
00122 
00123   // Memory instructions...
00124   case Malloc:        return "malloc";
00125   case Free:          return "free";
00126   case Alloca:        return "alloca";
00127   case Load:          return "load";
00128   case Store:         return "store";
00129   case GetElementPtr: return "getelementptr";
00130 
00131   // Convert instructions...
00132   case Trunc:     return "trunc";
00133   case ZExt:      return "zext";
00134   case SExt:      return "sext";
00135   case FPTrunc:   return "fptrunc";
00136   case FPExt:     return "fpext";
00137   case FPToUI:    return "fptoui";
00138   case FPToSI:    return "fptosi";
00139   case UIToFP:    return "uitofp";
00140   case SIToFP:    return "sitofp";
00141   case IntToPtr:  return "inttoptr";
00142   case PtrToInt:  return "ptrtoint";
00143   case BitCast:   return "bitcast";
00144 
00145   // Other instructions...
00146   case ICmp:           return "icmp";
00147   case FCmp:           return "fcmp";
00148   case PHI:            return "phi";
00149   case Select:         return "select";
00150   case Call:           return "call";
00151   case Shl:            return "shl";
00152   case LShr:           return "lshr";
00153   case AShr:           return "ashr";
00154   case VAArg:          return "va_arg";
00155   case ExtractElement: return "extractelement";
00156   case InsertElement:  return "insertelement";
00157   case ShuffleVector:  return "shufflevector";
00158   case ExtractValue:   return "extractvalue";
00159   case InsertValue:    return "insertvalue";
00160 
00161   default: return "<Invalid operator> ";
00162   }
00163 
00164   return 0;
00165 }
00166 
00167 /// isIdenticalTo - Return true if the specified instruction is exactly
00168 /// identical to the current one.  This means that all operands match and any
00169 /// extra information (e.g. load is volatile) agree.
00170 bool Instruction::isIdenticalTo(const Instruction *I) const {
00171   return isIdenticalToWhenDefined(I) &&
00172          SubclassOptionalData == I->SubclassOptionalData;
00173 }
00174 
00175 /// isIdenticalToWhenDefined - This is like isIdenticalTo, except that it
00176 /// ignores the SubclassOptionalData flags, which specify conditions
00177 /// under which the instruction's result is undefined.
00178 bool Instruction::isIdenticalToWhenDefined(const Instruction *I) const {
00179   if (getOpcode() != I->getOpcode() ||
00180       getNumOperands() != I->getNumOperands() ||
00181       getType() != I->getType())
00182     return false;
00183 
00184   // We have two instructions of identical opcode and #operands.  Check to see
00185   // if all operands are the same.
00186   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00187     if (getOperand(i) != I->getOperand(i))
00188       return false;
00189 
00190   // Check special state that is a part of some instructions.
00191   if (const LoadInst *LI = dyn_cast<LoadInst>(this))
00192     return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() &&
00193            LI->getAlignment() == cast<LoadInst>(I)->getAlignment();
00194   if (const StoreInst *SI = dyn_cast<StoreInst>(this))
00195     return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() &&
00196            SI->getAlignment() == cast<StoreInst>(I)->getAlignment();
00197   if (const CmpInst *CI = dyn_cast<CmpInst>(this))
00198     return CI->getPredicate() == cast<CmpInst>(I)->getPredicate();
00199   if (const CallInst *CI = dyn_cast<CallInst>(this))
00200     return CI->isTailCall() == cast<CallInst>(I)->isTailCall() &&
00201            CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() &&
00202            CI->getAttributes().getRawPointer() ==
00203              cast<CallInst>(I)->getAttributes().getRawPointer();
00204   if (const InvokeInst *CI = dyn_cast<InvokeInst>(this))
00205     return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() &&
00206            CI->getAttributes().getRawPointer() ==
00207              cast<InvokeInst>(I)->getAttributes().getRawPointer();
00208   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this)) {
00209     if (IVI->getNumIndices() != cast<InsertValueInst>(I)->getNumIndices())
00210       return false;
00211     for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i)
00212       if (IVI->idx_begin()[i] != cast<InsertValueInst>(I)->idx_begin()[i])
00213         return false;
00214     return true;
00215   }
00216   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this)) {
00217     if (EVI->getNumIndices() != cast<ExtractValueInst>(I)->getNumIndices())
00218       return false;
00219     for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i)
00220       if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I)->idx_begin()[i])
00221         return false;
00222     return true;
00223   }
00224 
00225   return true;
00226 }
00227 
00228 // isSameOperationAs
00229 // This should be kept in sync with isEquivalentOperation in
00230 // lib/Transforms/IPO/MergeFunctions.cpp.
00231 bool Instruction::isSameOperationAs(const Instruction *I) const {
00232   if (getOpcode() != I->getOpcode() ||
00233       getNumOperands() != I->getNumOperands() ||
00234       getType() != I->getType())
00235     return false;
00236 
00237   // We have two instructions of identical opcode and #operands.  Check to see
00238   // if all operands are the same type
00239   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00240     if (getOperand(i)->getType() != I->getOperand(i)->getType())
00241       return false;
00242 
00243   // Check special state that is a part of some instructions.
00244   if (const LoadInst *LI = dyn_cast<LoadInst>(this))
00245     return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() &&
00246            LI->getAlignment() == cast<LoadInst>(I)->getAlignment();
00247   if (const StoreInst *SI = dyn_cast<StoreInst>(this))
00248     return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() &&
00249            SI->getAlignment() == cast<StoreInst>(I)->getAlignment();
00250   if (const CmpInst *CI = dyn_cast<CmpInst>(this))
00251     return CI->getPredicate() == cast<CmpInst>(I)->getPredicate();
00252   if (const CallInst *CI = dyn_cast<CallInst>(this))
00253     return CI->isTailCall() == cast<CallInst>(I)->isTailCall() &&
00254            CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() &&
00255            CI->getAttributes().getRawPointer() ==
00256              cast<CallInst>(I)->getAttributes().getRawPointer();
00257   if (const InvokeInst *CI = dyn_cast<InvokeInst>(this))
00258     return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() &&
00259            CI->getAttributes().getRawPointer() ==
00260              cast<InvokeInst>(I)->getAttributes().getRawPointer();
00261   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this)) {
00262     if (IVI->getNumIndices() != cast<InsertValueInst>(I)->getNumIndices())
00263       return false;
00264     for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i)
00265       if (IVI->idx_begin()[i] != cast<InsertValueInst>(I)->idx_begin()[i])
00266         return false;
00267     return true;
00268   }
00269   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this)) {
00270     if (EVI->getNumIndices() != cast<ExtractValueInst>(I)->getNumIndices())
00271       return false;
00272     for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i)
00273       if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I)->idx_begin()[i])
00274         return false;
00275     return true;
00276   }
00277 
00278   return true;
00279 }
00280 
00281 /// isUsedOutsideOfBlock - Return true if there are any uses of I outside of the
00282 /// specified block.  Note that PHI nodes are considered to evaluate their
00283 /// operands in the corresponding predecessor block.
00284 bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const {
00285   for (use_const_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
00286     // PHI nodes uses values in the corresponding predecessor block.  For other
00287     // instructions, just check to see whether the parent of the use matches up.
00288     const PHINode *PN = dyn_cast<PHINode>(*UI);
00289     if (PN == 0) {
00290       if (cast<Instruction>(*UI)->getParent() != BB)
00291         return true;
00292       continue;
00293     }
00294     
00295     if (PN->getIncomingBlock(UI) != BB)
00296       return true;
00297   }
00298   return false;    
00299 }
00300 
00301 /// mayReadFromMemory - Return true if this instruction may read memory.
00302 ///
00303 bool Instruction::mayReadFromMemory() const {
00304   switch (getOpcode()) {
00305   default: return false;
00306   case Instruction::Free:
00307   case Instruction::VAArg:
00308   case Instruction::Load:
00309     return true;
00310   case Instruction::Call:
00311     return !cast<CallInst>(this)->doesNotAccessMemory();
00312   case Instruction::Invoke:
00313     return !cast<InvokeInst>(this)->doesNotAccessMemory();
00314   case Instruction::Store:
00315     return cast<StoreInst>(this)->isVolatile();
00316   }
00317 }
00318 
00319 /// mayWriteToMemory - Return true if this instruction may modify memory.
00320 ///
00321 bool Instruction::mayWriteToMemory() const {
00322   switch (getOpcode()) {
00323   default: return false;
00324   case Instruction::Free:
00325   case Instruction::Store:
00326   case Instruction::VAArg:
00327     return true;
00328   case Instruction::Call:
00329     return !cast<CallInst>(this)->onlyReadsMemory();
00330   case Instruction::Invoke:
00331     return !cast<InvokeInst>(this)->onlyReadsMemory();
00332   case Instruction::Load:
00333     return cast<LoadInst>(this)->isVolatile();
00334   }
00335 }
00336 
00337 /// mayThrow - Return true if this instruction may throw an exception.
00338 ///
00339 bool Instruction::mayThrow() const {
00340   if (const CallInst *CI = dyn_cast<CallInst>(this))
00341     return !CI->doesNotThrow();
00342   return false;
00343 }
00344 
00345 /// isAssociative - Return true if the instruction is associative:
00346 ///
00347 ///   Associative operators satisfy:  x op (y op z) === (x op y) op z
00348 ///
00349 /// In LLVM, the Add, Mul, And, Or, and Xor operators are associative.
00350 ///
00351 bool Instruction::isAssociative(unsigned Opcode, const Type *Ty) {
00352   return Opcode == And || Opcode == Or || Opcode == Xor ||
00353          Opcode == Add || Opcode == Mul;
00354 }
00355 
00356 /// isCommutative - Return true if the instruction is commutative:
00357 ///
00358 ///   Commutative operators satisfy: (x op y) === (y op x)
00359 ///
00360 /// In LLVM, these are the associative operators, plus SetEQ and SetNE, when
00361 /// applied to any type.
00362 ///
00363 bool Instruction::isCommutative(unsigned op) {
00364   switch (op) {
00365   case Add:
00366   case FAdd:
00367   case Mul:
00368   case FMul:
00369   case And:
00370   case Or:
00371   case Xor:
00372     return true;
00373   default:
00374     return false;
00375   }
00376 }
00377 
00378 bool Instruction::isSafeToSpeculativelyExecute() const {
00379   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00380     if (Constant *C = dyn_cast<Constant>(getOperand(i)))
00381       if (C->canTrap())
00382         return false;
00383 
00384   switch (getOpcode()) {
00385   default:
00386     return true;
00387   case UDiv:
00388   case URem: {
00389     // x / y is undefined if y == 0, but calcuations like x / 3 are safe.
00390     ConstantInt *Op = dyn_cast<ConstantInt>(getOperand(1));
00391     return Op && !Op->isNullValue();
00392   }
00393   case SDiv:
00394   case SRem: {
00395     // x / y is undefined if y == 0, and might be undefined if y == -1,
00396     // but calcuations like x / 3 are safe.
00397     ConstantInt *Op = dyn_cast<ConstantInt>(getOperand(1));
00398     return Op && !Op->isNullValue() && !Op->isAllOnesValue();
00399   }
00400   case Load: {
00401     if (cast<LoadInst>(this)->isVolatile())
00402       return false;
00403     if (isa<AllocationInst>(getOperand(0)))
00404       return true;
00405     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(getOperand(0)))
00406       return !GV->hasExternalWeakLinkage();
00407     // FIXME: Handle cases involving GEPs.  We have to be careful because
00408     // a load of a out-of-bounds GEP has undefined behavior.
00409     return false;
00410   }
00411   case Call:
00412     return false; // The called function could have undefined behavior or
00413                   // side-effects.
00414                   // FIXME: We should special-case some intrinsics (bswap,
00415                   // overflow-checking arithmetic, etc.)
00416   case VAArg:
00417   case Alloca:
00418   case Malloc:
00419   case Invoke:
00420   case PHI:
00421   case Store:
00422   case Free:
00423   case Ret:
00424   case Br:
00425   case Switch:
00426   case Unwind:
00427   case Unreachable:
00428     return false; // Misc instructions which have effects
00429   }
00430 }