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 Unreachable: return "unreachable";
106
107  // Standard binary operators...
108  case Add: return "add";
109  case FAdd: return "fadd";
110  case Sub: return "sub";
111  case FSub: return "fsub";
112  case Mul: return "mul";
113  case FMul: return "fmul";
114  case UDiv: return "udiv";
115  case SDiv: return "sdiv";
116  case FDiv: return "fdiv";
117  case URem: return "urem";
118  case SRem: return "srem";
119  case FRem: return "frem";
120
121  // Logical operators...
122  case And: return "and";
123  case Or : return "or";
124  case Xor: return "xor";
125
126  // Memory instructions...
127  case Alloca:        return "alloca";
128  case Load:          return "load";
129  case Store:         return "store";
130  case AtomicCmpXchg: return "cmpxchg";
131  case AtomicRMW:     return "atomicrmw";
132  case Fence:         return "fence";
133  case GetElementPtr: return "getelementptr";
134
135  // Convert instructions...
136  case Trunc:     return "trunc";
137  case ZExt:      return "zext";
138  case SExt:      return "sext";
139  case FPTrunc:   return "fptrunc";
140  case FPExt:     return "fpext";
141  case FPToUI:    return "fptoui";
142  case FPToSI:    return "fptosi";
143  case UIToFP:    return "uitofp";
144  case SIToFP:    return "sitofp";
145  case IntToPtr:  return "inttoptr";
146  case PtrToInt:  return "ptrtoint";
147  case BitCast:   return "bitcast";
148
149  // Other instructions...
150  case ICmp:           return "icmp";
151  case FCmp:           return "fcmp";
152  case PHI:            return "phi";
153  case Select:         return "select";
154  case Call:           return "call";
155  case Shl:            return "shl";
156  case LShr:           return "lshr";
157  case AShr:           return "ashr";
158  case VAArg:          return "va_arg";
159  case ExtractElement: return "extractelement";
160  case InsertElement:  return "insertelement";
161  case ShuffleVector:  return "shufflevector";
162  case ExtractValue:   return "extractvalue";
163  case InsertValue:    return "insertvalue";
164  case LandingPad:     return "landingpad";
165
166  default: return "<Invalid operator> ";
167  }
168}
169
170/// isIdenticalTo - Return true if the specified instruction is exactly
171/// identical to the current one.  This means that all operands match and any
172/// extra information (e.g. load is volatile) agree.
173bool Instruction::isIdenticalTo(const Instruction *I) const {
174  return isIdenticalToWhenDefined(I) &&
175         SubclassOptionalData == I->SubclassOptionalData;
176}
177
178/// isIdenticalToWhenDefined - This is like isIdenticalTo, except that it
179/// ignores the SubclassOptionalData flags, which specify conditions
180/// under which the instruction's result is undefined.
181bool Instruction::isIdenticalToWhenDefined(const Instruction *I) const {
182  if (getOpcode() != I->getOpcode() ||
183      getNumOperands() != I->getNumOperands() ||
184      getType() != I->getType())
185    return false;
186
187  // We have two instructions of identical opcode and #operands.  Check to see
188  // if all operands are the same.
189  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
190    if (getOperand(i) != I->getOperand(i))
191      return false;
192
193  // Check special state that is a part of some instructions.
194  if (const LoadInst *LI = dyn_cast<LoadInst>(this))
195    return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() &&
196           LI->getAlignment() == cast<LoadInst>(I)->getAlignment() &&
197           LI->getOrdering() == cast<LoadInst>(I)->getOrdering() &&
198           LI->getSynchScope() == cast<LoadInst>(I)->getSynchScope();
199  if (const StoreInst *SI = dyn_cast<StoreInst>(this))
200    return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() &&
201           SI->getAlignment() == cast<StoreInst>(I)->getAlignment() &&
202           SI->getOrdering() == cast<StoreInst>(I)->getOrdering() &&
203           SI->getSynchScope() == cast<StoreInst>(I)->getSynchScope();
204  if (const CmpInst *CI = dyn_cast<CmpInst>(this))
205    return CI->getPredicate() == cast<CmpInst>(I)->getPredicate();
206  if (const CallInst *CI = dyn_cast<CallInst>(this))
207    return CI->isTailCall() == cast<CallInst>(I)->isTailCall() &&
208           CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() &&
209           CI->getAttributes() == cast<CallInst>(I)->getAttributes();
210  if (const InvokeInst *CI = dyn_cast<InvokeInst>(this))
211    return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() &&
212           CI->getAttributes() == cast<InvokeInst>(I)->getAttributes();
213  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this))
214    return IVI->getIndices() == cast<InsertValueInst>(I)->getIndices();
215  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this))
216    return EVI->getIndices() == cast<ExtractValueInst>(I)->getIndices();
217  if (const FenceInst *FI = dyn_cast<FenceInst>(this))
218    return FI->getOrdering() == cast<FenceInst>(FI)->getOrdering() &&
219           FI->getSynchScope() == cast<FenceInst>(FI)->getSynchScope();
220  if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(this))
221    return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I)->isVolatile() &&
222           CXI->getOrdering() == cast<AtomicCmpXchgInst>(I)->getOrdering() &&
223           CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I)->getSynchScope();
224  if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(this))
225    return RMWI->getOperation() == cast<AtomicRMWInst>(I)->getOperation() &&
226           RMWI->isVolatile() == cast<AtomicRMWInst>(I)->isVolatile() &&
227           RMWI->getOrdering() == cast<AtomicRMWInst>(I)->getOrdering() &&
228           RMWI->getSynchScope() == cast<AtomicRMWInst>(I)->getSynchScope();
229
230  return true;
231}
232
233// isSameOperationAs
234// This should be kept in sync with isEquivalentOperation in
235// lib/Transforms/IPO/MergeFunctions.cpp.
236bool Instruction::isSameOperationAs(const Instruction *I) const {
237  if (getOpcode() != I->getOpcode() ||
238      getNumOperands() != I->getNumOperands() ||
239      getType() != I->getType())
240    return false;
241
242  // We have two instructions of identical opcode and #operands.  Check to see
243  // if all operands are the same type
244  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
245    if (getOperand(i)->getType() != I->getOperand(i)->getType())
246      return false;
247
248  // Check special state that is a part of some instructions.
249  if (const LoadInst *LI = dyn_cast<LoadInst>(this))
250    return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() &&
251           LI->getAlignment() == cast<LoadInst>(I)->getAlignment() &&
252           LI->getOrdering() == cast<LoadInst>(I)->getOrdering() &&
253           LI->getSynchScope() == cast<LoadInst>(I)->getSynchScope();
254  if (const StoreInst *SI = dyn_cast<StoreInst>(this))
255    return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() &&
256           SI->getAlignment() == cast<StoreInst>(I)->getAlignment() &&
257           SI->getOrdering() == cast<StoreInst>(I)->getOrdering() &&
258           SI->getSynchScope() == cast<StoreInst>(I)->getSynchScope();
259  if (const CmpInst *CI = dyn_cast<CmpInst>(this))
260    return CI->getPredicate() == cast<CmpInst>(I)->getPredicate();
261  if (const CallInst *CI = dyn_cast<CallInst>(this))
262    return CI->isTailCall() == cast<CallInst>(I)->isTailCall() &&
263           CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() &&
264           CI->getAttributes() == cast<CallInst>(I)->getAttributes();
265  if (const InvokeInst *CI = dyn_cast<InvokeInst>(this))
266    return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() &&
267           CI->getAttributes() ==
268             cast<InvokeInst>(I)->getAttributes();
269  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this))
270    return IVI->getIndices() == cast<InsertValueInst>(I)->getIndices();
271  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this))
272    return EVI->getIndices() == cast<ExtractValueInst>(I)->getIndices();
273  if (const FenceInst *FI = dyn_cast<FenceInst>(this))
274    return FI->getOrdering() == cast<FenceInst>(I)->getOrdering() &&
275           FI->getSynchScope() == cast<FenceInst>(I)->getSynchScope();
276  if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(this))
277    return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I)->isVolatile() &&
278           CXI->getOrdering() == cast<AtomicCmpXchgInst>(I)->getOrdering() &&
279           CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I)->getSynchScope();
280  if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(this))
281    return RMWI->getOperation() == cast<AtomicRMWInst>(I)->getOperation() &&
282           RMWI->isVolatile() == cast<AtomicRMWInst>(I)->isVolatile() &&
283           RMWI->getOrdering() == cast<AtomicRMWInst>(I)->getOrdering() &&
284           RMWI->getSynchScope() == cast<AtomicRMWInst>(I)->getSynchScope();
285
286  return true;
287}
288
289/// isUsedOutsideOfBlock - Return true if there are any uses of I outside of the
290/// specified block.  Note that PHI nodes are considered to evaluate their
291/// operands in the corresponding predecessor block.
292bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const {
293  for (const_use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
294    // PHI nodes uses values in the corresponding predecessor block.  For other
295    // instructions, just check to see whether the parent of the use matches up.
296    const User *U = *UI;
297    const PHINode *PN = dyn_cast<PHINode>(U);
298    if (PN == 0) {
299      if (cast<Instruction>(U)->getParent() != BB)
300        return true;
301      continue;
302    }
303
304    if (PN->getIncomingBlock(UI) != BB)
305      return true;
306  }
307  return false;
308}
309
310/// mayReadFromMemory - Return true if this instruction may read memory.
311///
312bool Instruction::mayReadFromMemory() const {
313  switch (getOpcode()) {
314  default: return false;
315  case Instruction::VAArg:
316  case Instruction::Load:
317  case Instruction::Fence: // FIXME: refine definition of mayReadFromMemory
318  case Instruction::AtomicCmpXchg:
319  case Instruction::AtomicRMW:
320    return true;
321  case Instruction::Call:
322    return !cast<CallInst>(this)->doesNotAccessMemory();
323  case Instruction::Invoke:
324    return !cast<InvokeInst>(this)->doesNotAccessMemory();
325  case Instruction::Store:
326    return !cast<StoreInst>(this)->isUnordered();
327  }
328}
329
330/// mayWriteToMemory - Return true if this instruction may modify memory.
331///
332bool Instruction::mayWriteToMemory() const {
333  switch (getOpcode()) {
334  default: return false;
335  case Instruction::Fence: // FIXME: refine definition of mayWriteToMemory
336  case Instruction::Store:
337  case Instruction::VAArg:
338  case Instruction::AtomicCmpXchg:
339  case Instruction::AtomicRMW:
340    return true;
341  case Instruction::Call:
342    return !cast<CallInst>(this)->onlyReadsMemory();
343  case Instruction::Invoke:
344    return !cast<InvokeInst>(this)->onlyReadsMemory();
345  case Instruction::Load:
346    return !cast<LoadInst>(this)->isUnordered();
347  }
348}
349
350/// mayThrow - Return true if this instruction may throw an exception.
351///
352bool Instruction::mayThrow() const {
353  if (const CallInst *CI = dyn_cast<CallInst>(this))
354    return !CI->doesNotThrow();
355  return isa<ResumeInst>(this);
356}
357
358/// isAssociative - Return true if the instruction is associative:
359///
360///   Associative operators satisfy:  x op (y op z) === (x op y) op z
361///
362/// In LLVM, the Add, Mul, And, Or, and Xor operators are associative.
363///
364bool Instruction::isAssociative(unsigned Opcode) {
365  return Opcode == And || Opcode == Or || Opcode == Xor ||
366         Opcode == Add || Opcode == Mul;
367}
368
369/// isCommutative - Return true if the instruction is commutative:
370///
371///   Commutative operators satisfy: (x op y) === (y op x)
372///
373/// In LLVM, these are the associative operators, plus SetEQ and SetNE, when
374/// applied to any type.
375///
376bool Instruction::isCommutative(unsigned op) {
377  switch (op) {
378  case Add:
379  case FAdd:
380  case Mul:
381  case FMul:
382  case And:
383  case Or:
384  case Xor:
385    return true;
386  default:
387    return false;
388  }
389}
390
391Instruction *Instruction::clone() const {
392  Instruction *New = clone_impl();
393  New->SubclassOptionalData = SubclassOptionalData;
394  if (!hasMetadata())
395    return New;
396
397  // Otherwise, enumerate and copy over metadata from the old instruction to the
398  // new one.
399  SmallVector<std::pair<unsigned, MDNode*>, 4> TheMDs;
400  getAllMetadataOtherThanDebugLoc(TheMDs);
401  for (unsigned i = 0, e = TheMDs.size(); i != e; ++i)
402    New->setMetadata(TheMDs[i].first, TheMDs[i].second);
403
404  New->setDebugLoc(getDebugLoc());
405  return New;
406}
407