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  if (const PHINode *thisPHI = dyn_cast<PHINode>(this)) {
230    const PHINode *otherPHI = cast<PHINode>(I);
231    for (unsigned i = 0, e = thisPHI->getNumOperands(); i != e; ++i) {
232      if (thisPHI->getIncomingBlock(i) != otherPHI->getIncomingBlock(i))
233        return false;
234    }
235    return true;
236  }
237  return true;
238}
239
240// isSameOperationAs
241// This should be kept in sync with isEquivalentOperation in
242// lib/Transforms/IPO/MergeFunctions.cpp.
243bool Instruction::isSameOperationAs(const Instruction *I,
244                                    unsigned flags) const {
245  bool IgnoreAlignment = flags & CompareIgnoringAlignment;
246  bool UseScalarTypes  = flags & CompareUsingScalarTypes;
247
248  if (getOpcode() != I->getOpcode() ||
249      getNumOperands() != I->getNumOperands() ||
250      (UseScalarTypes ?
251       getType()->getScalarType() != I->getType()->getScalarType() :
252       getType() != I->getType()))
253    return false;
254
255  // We have two instructions of identical opcode and #operands.  Check to see
256  // if all operands are the same type
257  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
258    if (UseScalarTypes ?
259        getOperand(i)->getType()->getScalarType() !=
260          I->getOperand(i)->getType()->getScalarType() :
261        getOperand(i)->getType() != I->getOperand(i)->getType())
262      return false;
263
264  // Check special state that is a part of some instructions.
265  if (const LoadInst *LI = dyn_cast<LoadInst>(this))
266    return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() &&
267           (LI->getAlignment() == cast<LoadInst>(I)->getAlignment() ||
268            IgnoreAlignment) &&
269           LI->getOrdering() == cast<LoadInst>(I)->getOrdering() &&
270           LI->getSynchScope() == cast<LoadInst>(I)->getSynchScope();
271  if (const StoreInst *SI = dyn_cast<StoreInst>(this))
272    return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() &&
273           (SI->getAlignment() == cast<StoreInst>(I)->getAlignment() ||
274            IgnoreAlignment) &&
275           SI->getOrdering() == cast<StoreInst>(I)->getOrdering() &&
276           SI->getSynchScope() == cast<StoreInst>(I)->getSynchScope();
277  if (const CmpInst *CI = dyn_cast<CmpInst>(this))
278    return CI->getPredicate() == cast<CmpInst>(I)->getPredicate();
279  if (const CallInst *CI = dyn_cast<CallInst>(this))
280    return CI->isTailCall() == cast<CallInst>(I)->isTailCall() &&
281           CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() &&
282           CI->getAttributes() == cast<CallInst>(I)->getAttributes();
283  if (const InvokeInst *CI = dyn_cast<InvokeInst>(this))
284    return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() &&
285           CI->getAttributes() ==
286             cast<InvokeInst>(I)->getAttributes();
287  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this))
288    return IVI->getIndices() == cast<InsertValueInst>(I)->getIndices();
289  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this))
290    return EVI->getIndices() == cast<ExtractValueInst>(I)->getIndices();
291  if (const FenceInst *FI = dyn_cast<FenceInst>(this))
292    return FI->getOrdering() == cast<FenceInst>(I)->getOrdering() &&
293           FI->getSynchScope() == cast<FenceInst>(I)->getSynchScope();
294  if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(this))
295    return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I)->isVolatile() &&
296           CXI->getOrdering() == cast<AtomicCmpXchgInst>(I)->getOrdering() &&
297           CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I)->getSynchScope();
298  if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(this))
299    return RMWI->getOperation() == cast<AtomicRMWInst>(I)->getOperation() &&
300           RMWI->isVolatile() == cast<AtomicRMWInst>(I)->isVolatile() &&
301           RMWI->getOrdering() == cast<AtomicRMWInst>(I)->getOrdering() &&
302           RMWI->getSynchScope() == cast<AtomicRMWInst>(I)->getSynchScope();
303
304  return true;
305}
306
307/// isUsedOutsideOfBlock - Return true if there are any uses of I outside of the
308/// specified block.  Note that PHI nodes are considered to evaluate their
309/// operands in the corresponding predecessor block.
310bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const {
311  for (const_use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
312    // PHI nodes uses values in the corresponding predecessor block.  For other
313    // instructions, just check to see whether the parent of the use matches up.
314    const User *U = *UI;
315    const PHINode *PN = dyn_cast<PHINode>(U);
316    if (PN == 0) {
317      if (cast<Instruction>(U)->getParent() != BB)
318        return true;
319      continue;
320    }
321
322    if (PN->getIncomingBlock(UI) != BB)
323      return true;
324  }
325  return false;
326}
327
328/// mayReadFromMemory - Return true if this instruction may read memory.
329///
330bool Instruction::mayReadFromMemory() const {
331  switch (getOpcode()) {
332  default: return false;
333  case Instruction::VAArg:
334  case Instruction::Load:
335  case Instruction::Fence: // FIXME: refine definition of mayReadFromMemory
336  case Instruction::AtomicCmpXchg:
337  case Instruction::AtomicRMW:
338    return true;
339  case Instruction::Call:
340    return !cast<CallInst>(this)->doesNotAccessMemory();
341  case Instruction::Invoke:
342    return !cast<InvokeInst>(this)->doesNotAccessMemory();
343  case Instruction::Store:
344    return !cast<StoreInst>(this)->isUnordered();
345  }
346}
347
348/// mayWriteToMemory - Return true if this instruction may modify memory.
349///
350bool Instruction::mayWriteToMemory() const {
351  switch (getOpcode()) {
352  default: return false;
353  case Instruction::Fence: // FIXME: refine definition of mayWriteToMemory
354  case Instruction::Store:
355  case Instruction::VAArg:
356  case Instruction::AtomicCmpXchg:
357  case Instruction::AtomicRMW:
358    return true;
359  case Instruction::Call:
360    return !cast<CallInst>(this)->onlyReadsMemory();
361  case Instruction::Invoke:
362    return !cast<InvokeInst>(this)->onlyReadsMemory();
363  case Instruction::Load:
364    return !cast<LoadInst>(this)->isUnordered();
365  }
366}
367
368/// mayThrow - Return true if this instruction may throw an exception.
369///
370bool Instruction::mayThrow() const {
371  if (const CallInst *CI = dyn_cast<CallInst>(this))
372    return !CI->doesNotThrow();
373  return isa<ResumeInst>(this);
374}
375
376/// isAssociative - Return true if the instruction is associative:
377///
378///   Associative operators satisfy:  x op (y op z) === (x op y) op z
379///
380/// In LLVM, the Add, Mul, And, Or, and Xor operators are associative.
381///
382bool Instruction::isAssociative(unsigned Opcode) {
383  return Opcode == And || Opcode == Or || Opcode == Xor ||
384         Opcode == Add || Opcode == Mul;
385}
386
387/// isCommutative - Return true if the instruction is commutative:
388///
389///   Commutative operators satisfy: (x op y) === (y op x)
390///
391/// In LLVM, these are the associative operators, plus SetEQ and SetNE, when
392/// applied to any type.
393///
394bool Instruction::isCommutative(unsigned op) {
395  switch (op) {
396  case Add:
397  case FAdd:
398  case Mul:
399  case FMul:
400  case And:
401  case Or:
402  case Xor:
403    return true;
404  default:
405    return false;
406  }
407}
408
409/// isIdempotent - Return true if the instruction is idempotent:
410///
411///   Idempotent operators satisfy:  x op x === x
412///
413/// In LLVM, the And and Or operators are idempotent.
414///
415bool Instruction::isIdempotent(unsigned Opcode) {
416  return Opcode == And || Opcode == Or;
417}
418
419/// isNilpotent - Return true if the instruction is nilpotent:
420///
421///   Nilpotent operators satisfy:  x op x === Id,
422///
423///   where Id is the identity for the operator, i.e. a constant such that
424///     x op Id === x and Id op x === x for all x.
425///
426/// In LLVM, the Xor operator is nilpotent.
427///
428bool Instruction::isNilpotent(unsigned Opcode) {
429  return Opcode == Xor;
430}
431
432Instruction *Instruction::clone() const {
433  Instruction *New = clone_impl();
434  New->SubclassOptionalData = SubclassOptionalData;
435  if (!hasMetadata())
436    return New;
437
438  // Otherwise, enumerate and copy over metadata from the old instruction to the
439  // new one.
440  SmallVector<std::pair<unsigned, MDNode*>, 4> TheMDs;
441  getAllMetadataOtherThanDebugLoc(TheMDs);
442  for (unsigned i = 0, e = TheMDs.size(); i != e; ++i)
443    New->setMetadata(TheMDs[i].first, TheMDs[i].second);
444
445  New->setDebugLoc(getDebugLoc());
446  return New;
447}
448