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