Home | History | Annotate | Download | only in IR 
      1 //===-- Instruction.cpp - Implement the Instruction class -----------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the Instruction class for the IR library.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/IR/Instruction.h"
     15 #include "llvm/IR/CallSite.h"
     16 #include "llvm/IR/Constants.h"
     17 #include "llvm/IR/Instructions.h"
     18 #include "llvm/IR/LeakDetector.h"
     19 #include "llvm/IR/Module.h"
     20 #include "llvm/IR/Operator.h"
     21 #include "llvm/IR/Type.h"
     22 using namespace llvm;
     23 
     24 Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
     25                          Instruction *InsertBefore)
     26   : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(nullptr) {
     27   // Make sure that we get added to a basicblock
     28   LeakDetector::addGarbageObject(this);
     29 
     30   // If requested, insert this instruction into a basic block...
     31   if (InsertBefore) {
     32     assert(InsertBefore->getParent() &&
     33            "Instruction to insert before is not in a basic block!");
     34     InsertBefore->getParent()->getInstList().insert(InsertBefore, this);
     35   }
     36 }
     37 
     38 const DataLayout *Instruction::getDataLayout() const {
     39   return getParent()->getDataLayout();
     40 }
     41 
     42 Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
     43                          BasicBlock *InsertAtEnd)
     44   : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(nullptr) {
     45   // Make sure that we get added to a basicblock
     46   LeakDetector::addGarbageObject(this);
     47 
     48   // append this instruction into the basic block
     49   assert(InsertAtEnd && "Basic block to append to may not be NULL!");
     50   InsertAtEnd->getInstList().push_back(this);
     51 }
     52 
     53 
     54 // Out of line virtual method, so the vtable, etc has a home.
     55 Instruction::~Instruction() {
     56   assert(!Parent && "Instruction still linked in the program!");
     57   if (hasMetadataHashEntry())
     58     clearMetadataHashEntries();
     59 }
     60 
     61 
     62 void Instruction::setParent(BasicBlock *P) {
     63   if (getParent()) {
     64     if (!P) LeakDetector::addGarbageObject(this);
     65   } else {
     66     if (P) LeakDetector::removeGarbageObject(this);
     67   }
     68 
     69   Parent = P;
     70 }
     71 
     72 void Instruction::removeFromParent() {
     73   getParent()->getInstList().remove(this);
     74 }
     75 
     76 void Instruction::eraseFromParent() {
     77   getParent()->getInstList().erase(this);
     78 }
     79 
     80 /// insertBefore - Insert an unlinked instructions into a basic block
     81 /// immediately before the specified instruction.
     82 void Instruction::insertBefore(Instruction *InsertPos) {
     83   InsertPos->getParent()->getInstList().insert(InsertPos, this);
     84 }
     85 
     86 /// insertAfter - Insert an unlinked instructions into a basic block
     87 /// immediately after the specified instruction.
     88 void Instruction::insertAfter(Instruction *InsertPos) {
     89   InsertPos->getParent()->getInstList().insertAfter(InsertPos, this);
     90 }
     91 
     92 /// moveBefore - Unlink this instruction from its current basic block and
     93 /// insert it into the basic block that MovePos lives in, right before
     94 /// MovePos.
     95 void Instruction::moveBefore(Instruction *MovePos) {
     96   MovePos->getParent()->getInstList().splice(MovePos,getParent()->getInstList(),
     97                                              this);
     98 }
     99 
    100 /// Set or clear the unsafe-algebra flag on this instruction, which must be an
    101 /// operator which supports this flag. See LangRef.html for the meaning of this
    102 /// flag.
    103 void Instruction::setHasUnsafeAlgebra(bool B) {
    104   assert(isa<FPMathOperator>(this) && "setting fast-math flag on invalid op");
    105   cast<FPMathOperator>(this)->setHasUnsafeAlgebra(B);
    106 }
    107 
    108 /// Set or clear the NoNaNs flag on this instruction, which must be an operator
    109 /// which supports this flag. See LangRef.html for the meaning of this flag.
    110 void Instruction::setHasNoNaNs(bool B) {
    111   assert(isa<FPMathOperator>(this) && "setting fast-math flag on invalid op");
    112   cast<FPMathOperator>(this)->setHasNoNaNs(B);
    113 }
    114 
    115 /// Set or clear the no-infs flag on this instruction, which must be an operator
    116 /// which supports this flag. See LangRef.html for the meaning of this flag.
    117 void Instruction::setHasNoInfs(bool B) {
    118   assert(isa<FPMathOperator>(this) && "setting fast-math flag on invalid op");
    119   cast<FPMathOperator>(this)->setHasNoInfs(B);
    120 }
    121 
    122 /// Set or clear the no-signed-zeros flag on this instruction, which must be an
    123 /// operator which supports this flag. See LangRef.html for the meaning of this
    124 /// flag.
    125 void Instruction::setHasNoSignedZeros(bool B) {
    126   assert(isa<FPMathOperator>(this) && "setting fast-math flag on invalid op");
    127   cast<FPMathOperator>(this)->setHasNoSignedZeros(B);
    128 }
    129 
    130 /// Set or clear the allow-reciprocal flag on this instruction, which must be an
    131 /// operator which supports this flag. See LangRef.html for the meaning of this
    132 /// flag.
    133 void Instruction::setHasAllowReciprocal(bool B) {
    134   assert(isa<FPMathOperator>(this) && "setting fast-math flag on invalid op");
    135   cast<FPMathOperator>(this)->setHasAllowReciprocal(B);
    136 }
    137 
    138 /// Convenience function for setting all the fast-math flags on this
    139 /// instruction, which must be an operator which supports these flags. See
    140 /// LangRef.html for the meaning of these flats.
    141 void Instruction::setFastMathFlags(FastMathFlags FMF) {
    142   assert(isa<FPMathOperator>(this) && "setting fast-math flag on invalid op");
    143   cast<FPMathOperator>(this)->setFastMathFlags(FMF);
    144 }
    145 
    146 /// Determine whether the unsafe-algebra flag is set.
    147 bool Instruction::hasUnsafeAlgebra() const {
    148   assert(isa<FPMathOperator>(this) && "getting fast-math flag on invalid op");
    149   return cast<FPMathOperator>(this)->hasUnsafeAlgebra();
    150 }
    151 
    152 /// Determine whether the no-NaNs flag is set.
    153 bool Instruction::hasNoNaNs() const {
    154   assert(isa<FPMathOperator>(this) && "getting fast-math flag on invalid op");
    155   return cast<FPMathOperator>(this)->hasNoNaNs();
    156 }
    157 
    158 /// Determine whether the no-infs flag is set.
    159 bool Instruction::hasNoInfs() const {
    160   assert(isa<FPMathOperator>(this) && "getting fast-math flag on invalid op");
    161   return cast<FPMathOperator>(this)->hasNoInfs();
    162 }
    163 
    164 /// Determine whether the no-signed-zeros flag is set.
    165 bool Instruction::hasNoSignedZeros() const {
    166   assert(isa<FPMathOperator>(this) && "getting fast-math flag on invalid op");
    167   return cast<FPMathOperator>(this)->hasNoSignedZeros();
    168 }
    169 
    170 /// Determine whether the allow-reciprocal flag is set.
    171 bool Instruction::hasAllowReciprocal() const {
    172   assert(isa<FPMathOperator>(this) && "getting fast-math flag on invalid op");
    173   return cast<FPMathOperator>(this)->hasAllowReciprocal();
    174 }
    175 
    176 /// Convenience function for getting all the fast-math flags, which must be an
    177 /// operator which supports these flags. See LangRef.html for the meaning of
    178 /// these flats.
    179 FastMathFlags Instruction::getFastMathFlags() const {
    180   assert(isa<FPMathOperator>(this) && "getting fast-math flag on invalid op");
    181   return cast<FPMathOperator>(this)->getFastMathFlags();
    182 }
    183 
    184 /// Copy I's fast-math flags
    185 void Instruction::copyFastMathFlags(const Instruction *I) {
    186   setFastMathFlags(I->getFastMathFlags());
    187 }
    188 
    189 
    190 const char *Instruction::getOpcodeName(unsigned OpCode) {
    191   switch (OpCode) {
    192   // Terminators
    193   case Ret:    return "ret";
    194   case Br:     return "br";
    195   case Switch: return "switch";
    196   case IndirectBr: return "indirectbr";
    197   case Invoke: return "invoke";
    198   case Resume: return "resume";
    199   case Unreachable: return "unreachable";
    200 
    201   // Standard binary operators...
    202   case Add: return "add";
    203   case FAdd: return "fadd";
    204   case Sub: return "sub";
    205   case FSub: return "fsub";
    206   case Mul: return "mul";
    207   case FMul: return "fmul";
    208   case UDiv: return "udiv";
    209   case SDiv: return "sdiv";
    210   case FDiv: return "fdiv";
    211   case URem: return "urem";
    212   case SRem: return "srem";
    213   case FRem: return "frem";
    214 
    215   // Logical operators...
    216   case And: return "and";
    217   case Or : return "or";
    218   case Xor: return "xor";
    219 
    220   // Memory instructions...
    221   case Alloca:        return "alloca";
    222   case Load:          return "load";
    223   case Store:         return "store";
    224   case AtomicCmpXchg: return "cmpxchg";
    225   case AtomicRMW:     return "atomicrmw";
    226   case Fence:         return "fence";
    227   case GetElementPtr: return "getelementptr";
    228 
    229   // Convert instructions...
    230   case Trunc:         return "trunc";
    231   case ZExt:          return "zext";
    232   case SExt:          return "sext";
    233   case FPTrunc:       return "fptrunc";
    234   case FPExt:         return "fpext";
    235   case FPToUI:        return "fptoui";
    236   case FPToSI:        return "fptosi";
    237   case UIToFP:        return "uitofp";
    238   case SIToFP:        return "sitofp";
    239   case IntToPtr:      return "inttoptr";
    240   case PtrToInt:      return "ptrtoint";
    241   case BitCast:       return "bitcast";
    242   case AddrSpaceCast: return "addrspacecast";
    243 
    244   // Other instructions...
    245   case ICmp:           return "icmp";
    246   case FCmp:           return "fcmp";
    247   case PHI:            return "phi";
    248   case Select:         return "select";
    249   case Call:           return "call";
    250   case Shl:            return "shl";
    251   case LShr:           return "lshr";
    252   case AShr:           return "ashr";
    253   case VAArg:          return "va_arg";
    254   case ExtractElement: return "extractelement";
    255   case InsertElement:  return "insertelement";
    256   case ShuffleVector:  return "shufflevector";
    257   case ExtractValue:   return "extractvalue";
    258   case InsertValue:    return "insertvalue";
    259   case LandingPad:     return "landingpad";
    260 
    261   default: return "<Invalid operator> ";
    262   }
    263 }
    264 
    265 /// Return true if both instructions have the same special state
    266 /// This must be kept in sync with lib/Transforms/IPO/MergeFunctions.cpp.
    267 static bool haveSameSpecialState(const Instruction *I1, const Instruction *I2,
    268                                  bool IgnoreAlignment = false) {
    269   assert(I1->getOpcode() == I2->getOpcode() &&
    270          "Can not compare special state of different instructions");
    271 
    272   if (const LoadInst *LI = dyn_cast<LoadInst>(I1))
    273     return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() &&
    274            (LI->getAlignment() == cast<LoadInst>(I2)->getAlignment() ||
    275             IgnoreAlignment) &&
    276            LI->getOrdering() == cast<LoadInst>(I2)->getOrdering() &&
    277            LI->getSynchScope() == cast<LoadInst>(I2)->getSynchScope();
    278   if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
    279     return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
    280            (SI->getAlignment() == cast<StoreInst>(I2)->getAlignment() ||
    281             IgnoreAlignment) &&
    282            SI->getOrdering() == cast<StoreInst>(I2)->getOrdering() &&
    283            SI->getSynchScope() == cast<StoreInst>(I2)->getSynchScope();
    284   if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
    285     return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
    286   if (const CallInst *CI = dyn_cast<CallInst>(I1))
    287     return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() &&
    288            CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
    289            CI->getAttributes() == cast<CallInst>(I2)->getAttributes();
    290   if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
    291     return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
    292            CI->getAttributes() ==
    293              cast<InvokeInst>(I2)->getAttributes();
    294   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1))
    295     return IVI->getIndices() == cast<InsertValueInst>(I2)->getIndices();
    296   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1))
    297     return EVI->getIndices() == cast<ExtractValueInst>(I2)->getIndices();
    298   if (const FenceInst *FI = dyn_cast<FenceInst>(I1))
    299     return FI->getOrdering() == cast<FenceInst>(I2)->getOrdering() &&
    300            FI->getSynchScope() == cast<FenceInst>(I2)->getSynchScope();
    301   if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I1))
    302     return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I2)->isVolatile() &&
    303            CXI->isWeak() == cast<AtomicCmpXchgInst>(I2)->isWeak() &&
    304            CXI->getSuccessOrdering() ==
    305                cast<AtomicCmpXchgInst>(I2)->getSuccessOrdering() &&
    306            CXI->getFailureOrdering() ==
    307                cast<AtomicCmpXchgInst>(I2)->getFailureOrdering() &&
    308            CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I2)->getSynchScope();
    309   if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I1))
    310     return RMWI->getOperation() == cast<AtomicRMWInst>(I2)->getOperation() &&
    311            RMWI->isVolatile() == cast<AtomicRMWInst>(I2)->isVolatile() &&
    312            RMWI->getOrdering() == cast<AtomicRMWInst>(I2)->getOrdering() &&
    313            RMWI->getSynchScope() == cast<AtomicRMWInst>(I2)->getSynchScope();
    314 
    315   return true;
    316 }
    317 
    318 /// isIdenticalTo - Return true if the specified instruction is exactly
    319 /// identical to the current one.  This means that all operands match and any
    320 /// extra information (e.g. load is volatile) agree.
    321 bool Instruction::isIdenticalTo(const Instruction *I) const {
    322   return isIdenticalToWhenDefined(I) &&
    323          SubclassOptionalData == I->SubclassOptionalData;
    324 }
    325 
    326 /// isIdenticalToWhenDefined - This is like isIdenticalTo, except that it
    327 /// ignores the SubclassOptionalData flags, which specify conditions
    328 /// under which the instruction's result is undefined.
    329 bool Instruction::isIdenticalToWhenDefined(const Instruction *I) const {
    330   if (getOpcode() != I->getOpcode() ||
    331       getNumOperands() != I->getNumOperands() ||
    332       getType() != I->getType())
    333     return false;
    334 
    335   // If both instructions have no operands, they are identical.
    336   if (getNumOperands() == 0 && I->getNumOperands() == 0)
    337     return haveSameSpecialState(this, I);
    338 
    339   // We have two instructions of identical opcode and #operands.  Check to see
    340   // if all operands are the same.
    341   if (!std::equal(op_begin(), op_end(), I->op_begin()))
    342     return false;
    343 
    344   if (const PHINode *thisPHI = dyn_cast<PHINode>(this)) {
    345     const PHINode *otherPHI = cast<PHINode>(I);
    346     return std::equal(thisPHI->block_begin(), thisPHI->block_end(),
    347                       otherPHI->block_begin());
    348   }
    349 
    350   return haveSameSpecialState(this, I);
    351 }
    352 
    353 // isSameOperationAs
    354 // This should be kept in sync with isEquivalentOperation in
    355 // lib/Transforms/IPO/MergeFunctions.cpp.
    356 bool Instruction::isSameOperationAs(const Instruction *I,
    357                                     unsigned flags) const {
    358   bool IgnoreAlignment = flags & CompareIgnoringAlignment;
    359   bool UseScalarTypes  = flags & CompareUsingScalarTypes;
    360 
    361   if (getOpcode() != I->getOpcode() ||
    362       getNumOperands() != I->getNumOperands() ||
    363       (UseScalarTypes ?
    364        getType()->getScalarType() != I->getType()->getScalarType() :
    365        getType() != I->getType()))
    366     return false;
    367 
    368   // We have two instructions of identical opcode and #operands.  Check to see
    369   // if all operands are the same type
    370   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
    371     if (UseScalarTypes ?
    372         getOperand(i)->getType()->getScalarType() !=
    373           I->getOperand(i)->getType()->getScalarType() :
    374         getOperand(i)->getType() != I->getOperand(i)->getType())
    375       return false;
    376 
    377   return haveSameSpecialState(this, I, IgnoreAlignment);
    378 }
    379 
    380 /// isUsedOutsideOfBlock - Return true if there are any uses of I outside of the
    381 /// specified block.  Note that PHI nodes are considered to evaluate their
    382 /// operands in the corresponding predecessor block.
    383 bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const {
    384   for (const Use &U : uses()) {
    385     // PHI nodes uses values in the corresponding predecessor block.  For other
    386     // instructions, just check to see whether the parent of the use matches up.
    387     const Instruction *I = cast<Instruction>(U.getUser());
    388     const PHINode *PN = dyn_cast<PHINode>(I);
    389     if (!PN) {
    390       if (I->getParent() != BB)
    391         return true;
    392       continue;
    393     }
    394 
    395     if (PN->getIncomingBlock(U) != BB)
    396       return true;
    397   }
    398   return false;
    399 }
    400 
    401 /// mayReadFromMemory - Return true if this instruction may read memory.
    402 ///
    403 bool Instruction::mayReadFromMemory() const {
    404   switch (getOpcode()) {
    405   default: return false;
    406   case Instruction::VAArg:
    407   case Instruction::Load:
    408   case Instruction::Fence: // FIXME: refine definition of mayReadFromMemory
    409   case Instruction::AtomicCmpXchg:
    410   case Instruction::AtomicRMW:
    411     return true;
    412   case Instruction::Call:
    413     return !cast<CallInst>(this)->doesNotAccessMemory();
    414   case Instruction::Invoke:
    415     return !cast<InvokeInst>(this)->doesNotAccessMemory();
    416   case Instruction::Store:
    417     return !cast<StoreInst>(this)->isUnordered();
    418   }
    419 }
    420 
    421 /// mayWriteToMemory - Return true if this instruction may modify memory.
    422 ///
    423 bool Instruction::mayWriteToMemory() const {
    424   switch (getOpcode()) {
    425   default: return false;
    426   case Instruction::Fence: // FIXME: refine definition of mayWriteToMemory
    427   case Instruction::Store:
    428   case Instruction::VAArg:
    429   case Instruction::AtomicCmpXchg:
    430   case Instruction::AtomicRMW:
    431     return true;
    432   case Instruction::Call:
    433     return !cast<CallInst>(this)->onlyReadsMemory();
    434   case Instruction::Invoke:
    435     return !cast<InvokeInst>(this)->onlyReadsMemory();
    436   case Instruction::Load:
    437     return !cast<LoadInst>(this)->isUnordered();
    438   }
    439 }
    440 
    441 bool Instruction::mayThrow() const {
    442   if (const CallInst *CI = dyn_cast<CallInst>(this))
    443     return !CI->doesNotThrow();
    444   return isa<ResumeInst>(this);
    445 }
    446 
    447 bool Instruction::mayReturn() const {
    448   if (const CallInst *CI = dyn_cast<CallInst>(this))
    449     return !CI->doesNotReturn();
    450   return true;
    451 }
    452 
    453 /// isAssociative - Return true if the instruction is associative:
    454 ///
    455 ///   Associative operators satisfy:  x op (y op z) === (x op y) op z
    456 ///
    457 /// In LLVM, the Add, Mul, And, Or, and Xor operators are associative.
    458 ///
    459 bool Instruction::isAssociative(unsigned Opcode) {
    460   return Opcode == And || Opcode == Or || Opcode == Xor ||
    461          Opcode == Add || Opcode == Mul;
    462 }
    463 
    464 bool Instruction::isAssociative() const {
    465   unsigned Opcode = getOpcode();
    466   if (isAssociative(Opcode))
    467     return true;
    468 
    469   switch (Opcode) {
    470   case FMul:
    471   case FAdd:
    472     return cast<FPMathOperator>(this)->hasUnsafeAlgebra();
    473   default:
    474     return false;
    475   }
    476 }
    477 
    478 /// isCommutative - Return true if the instruction is commutative:
    479 ///
    480 ///   Commutative operators satisfy: (x op y) === (y op x)
    481 ///
    482 /// In LLVM, these are the associative operators, plus SetEQ and SetNE, when
    483 /// applied to any type.
    484 ///
    485 bool Instruction::isCommutative(unsigned op) {
    486   switch (op) {
    487   case Add:
    488   case FAdd:
    489   case Mul:
    490   case FMul:
    491   case And:
    492   case Or:
    493   case Xor:
    494     return true;
    495   default:
    496     return false;
    497   }
    498 }
    499 
    500 /// isIdempotent - Return true if the instruction is idempotent:
    501 ///
    502 ///   Idempotent operators satisfy:  x op x === x
    503 ///
    504 /// In LLVM, the And and Or operators are idempotent.
    505 ///
    506 bool Instruction::isIdempotent(unsigned Opcode) {
    507   return Opcode == And || Opcode == Or;
    508 }
    509 
    510 /// isNilpotent - Return true if the instruction is nilpotent:
    511 ///
    512 ///   Nilpotent operators satisfy:  x op x === Id,
    513 ///
    514 ///   where Id is the identity for the operator, i.e. a constant such that
    515 ///     x op Id === x and Id op x === x for all x.
    516 ///
    517 /// In LLVM, the Xor operator is nilpotent.
    518 ///
    519 bool Instruction::isNilpotent(unsigned Opcode) {
    520   return Opcode == Xor;
    521 }
    522 
    523 Instruction *Instruction::clone() const {
    524   Instruction *New = clone_impl();
    525   New->SubclassOptionalData = SubclassOptionalData;
    526   if (!hasMetadata())
    527     return New;
    528 
    529   // Otherwise, enumerate and copy over metadata from the old instruction to the
    530   // new one.
    531   SmallVector<std::pair<unsigned, MDNode*>, 4> TheMDs;
    532   getAllMetadataOtherThanDebugLoc(TheMDs);
    533   for (const auto &MD : TheMDs)
    534     New->setMetadata(MD.first, MD.second);
    535 
    536   New->setDebugLoc(getDebugLoc());
    537   return New;
    538 }
    539