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