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" 21 using namespace llvm; 22 23 Instruction::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 37 Instruction::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. 50 Instruction::~Instruction() { 51 assert(Parent == 0 && "Instruction still linked in the program!"); 52 if (hasMetadataHashEntry()) 53 clearMetadataHashEntries(); 54 } 55 56 57 void 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 67 void Instruction::removeFromParent() { 68 getParent()->getInstList().remove(this); 69 } 70 71 void 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. 77 void 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. 83 void 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. 90 void Instruction::moveBefore(Instruction *MovePos) { 91 MovePos->getParent()->getInstList().splice(MovePos,getParent()->getInstList(), 92 this); 93 } 94 95 96 const 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 Unwind: return "unwind"; 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 GetElementPtr: return "getelementptr"; 131 132 // Convert instructions... 133 case Trunc: return "trunc"; 134 case ZExt: return "zext"; 135 case SExt: return "sext"; 136 case FPTrunc: return "fptrunc"; 137 case FPExt: return "fpext"; 138 case FPToUI: return "fptoui"; 139 case FPToSI: return "fptosi"; 140 case UIToFP: return "uitofp"; 141 case SIToFP: return "sitofp"; 142 case IntToPtr: return "inttoptr"; 143 case PtrToInt: return "ptrtoint"; 144 case BitCast: return "bitcast"; 145 146 // Other instructions... 147 case ICmp: return "icmp"; 148 case FCmp: return "fcmp"; 149 case PHI: return "phi"; 150 case Select: return "select"; 151 case Call: return "call"; 152 case Shl: return "shl"; 153 case LShr: return "lshr"; 154 case AShr: return "ashr"; 155 case VAArg: return "va_arg"; 156 case ExtractElement: return "extractelement"; 157 case InsertElement: return "insertelement"; 158 case ShuffleVector: return "shufflevector"; 159 case ExtractValue: return "extractvalue"; 160 case InsertValue: return "insertvalue"; 161 162 default: return "<Invalid operator> "; 163 } 164 165 return 0; 166 } 167 168 /// isIdenticalTo - Return true if the specified instruction is exactly 169 /// identical to the current one. This means that all operands match and any 170 /// extra information (e.g. load is volatile) agree. 171 bool Instruction::isIdenticalTo(const Instruction *I) const { 172 return isIdenticalToWhenDefined(I) && 173 SubclassOptionalData == I->SubclassOptionalData; 174 } 175 176 /// isIdenticalToWhenDefined - This is like isIdenticalTo, except that it 177 /// ignores the SubclassOptionalData flags, which specify conditions 178 /// under which the instruction's result is undefined. 179 bool Instruction::isIdenticalToWhenDefined(const Instruction *I) const { 180 if (getOpcode() != I->getOpcode() || 181 getNumOperands() != I->getNumOperands() || 182 getType() != I->getType()) 183 return false; 184 185 // We have two instructions of identical opcode and #operands. Check to see 186 // if all operands are the same. 187 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 188 if (getOperand(i) != I->getOperand(i)) 189 return false; 190 191 // Check special state that is a part of some instructions. 192 if (const LoadInst *LI = dyn_cast<LoadInst>(this)) 193 return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() && 194 LI->getAlignment() == cast<LoadInst>(I)->getAlignment(); 195 if (const StoreInst *SI = dyn_cast<StoreInst>(this)) 196 return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() && 197 SI->getAlignment() == cast<StoreInst>(I)->getAlignment(); 198 if (const CmpInst *CI = dyn_cast<CmpInst>(this)) 199 return CI->getPredicate() == cast<CmpInst>(I)->getPredicate(); 200 if (const CallInst *CI = dyn_cast<CallInst>(this)) 201 return CI->isTailCall() == cast<CallInst>(I)->isTailCall() && 202 CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() && 203 CI->getAttributes() == cast<CallInst>(I)->getAttributes(); 204 if (const InvokeInst *CI = dyn_cast<InvokeInst>(this)) 205 return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() && 206 CI->getAttributes() == cast<InvokeInst>(I)->getAttributes(); 207 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this)) 208 return IVI->getIndices() == cast<InsertValueInst>(I)->getIndices(); 209 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this)) 210 return EVI->getIndices() == cast<ExtractValueInst>(I)->getIndices(); 211 212 return true; 213 } 214 215 // isSameOperationAs 216 // This should be kept in sync with isEquivalentOperation in 217 // lib/Transforms/IPO/MergeFunctions.cpp. 218 bool Instruction::isSameOperationAs(const Instruction *I) const { 219 if (getOpcode() != I->getOpcode() || 220 getNumOperands() != I->getNumOperands() || 221 getType() != I->getType()) 222 return false; 223 224 // We have two instructions of identical opcode and #operands. Check to see 225 // if all operands are the same type 226 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 227 if (getOperand(i)->getType() != I->getOperand(i)->getType()) 228 return false; 229 230 // Check special state that is a part of some instructions. 231 if (const LoadInst *LI = dyn_cast<LoadInst>(this)) 232 return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() && 233 LI->getAlignment() == cast<LoadInst>(I)->getAlignment(); 234 if (const StoreInst *SI = dyn_cast<StoreInst>(this)) 235 return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() && 236 SI->getAlignment() == cast<StoreInst>(I)->getAlignment(); 237 if (const CmpInst *CI = dyn_cast<CmpInst>(this)) 238 return CI->getPredicate() == cast<CmpInst>(I)->getPredicate(); 239 if (const CallInst *CI = dyn_cast<CallInst>(this)) 240 return CI->isTailCall() == cast<CallInst>(I)->isTailCall() && 241 CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() && 242 CI->getAttributes() == cast<CallInst>(I)->getAttributes(); 243 if (const InvokeInst *CI = dyn_cast<InvokeInst>(this)) 244 return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() && 245 CI->getAttributes() == 246 cast<InvokeInst>(I)->getAttributes(); 247 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this)) 248 return IVI->getIndices() == cast<InsertValueInst>(I)->getIndices(); 249 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this)) 250 return EVI->getIndices() == cast<ExtractValueInst>(I)->getIndices(); 251 252 return true; 253 } 254 255 /// isUsedOutsideOfBlock - Return true if there are any uses of I outside of the 256 /// specified block. Note that PHI nodes are considered to evaluate their 257 /// operands in the corresponding predecessor block. 258 bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const { 259 for (const_use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { 260 // PHI nodes uses values in the corresponding predecessor block. For other 261 // instructions, just check to see whether the parent of the use matches up. 262 const User *U = *UI; 263 const PHINode *PN = dyn_cast<PHINode>(U); 264 if (PN == 0) { 265 if (cast<Instruction>(U)->getParent() != BB) 266 return true; 267 continue; 268 } 269 270 if (PN->getIncomingBlock(UI) != BB) 271 return true; 272 } 273 return false; 274 } 275 276 /// mayReadFromMemory - Return true if this instruction may read memory. 277 /// 278 bool Instruction::mayReadFromMemory() const { 279 switch (getOpcode()) { 280 default: return false; 281 case Instruction::VAArg: 282 case Instruction::Load: 283 return true; 284 case Instruction::Call: 285 return !cast<CallInst>(this)->doesNotAccessMemory(); 286 case Instruction::Invoke: 287 return !cast<InvokeInst>(this)->doesNotAccessMemory(); 288 case Instruction::Store: 289 return cast<StoreInst>(this)->isVolatile(); 290 } 291 } 292 293 /// mayWriteToMemory - Return true if this instruction may modify memory. 294 /// 295 bool Instruction::mayWriteToMemory() const { 296 switch (getOpcode()) { 297 default: return false; 298 case Instruction::Store: 299 case Instruction::VAArg: 300 return true; 301 case Instruction::Call: 302 return !cast<CallInst>(this)->onlyReadsMemory(); 303 case Instruction::Invoke: 304 return !cast<InvokeInst>(this)->onlyReadsMemory(); 305 case Instruction::Load: 306 return cast<LoadInst>(this)->isVolatile(); 307 } 308 } 309 310 /// mayThrow - Return true if this instruction may throw an exception. 311 /// 312 bool Instruction::mayThrow() const { 313 if (const CallInst *CI = dyn_cast<CallInst>(this)) 314 return !CI->doesNotThrow(); 315 return false; 316 } 317 318 /// isAssociative - Return true if the instruction is associative: 319 /// 320 /// Associative operators satisfy: x op (y op z) === (x op y) op z 321 /// 322 /// In LLVM, the Add, Mul, And, Or, and Xor operators are associative. 323 /// 324 bool Instruction::isAssociative(unsigned Opcode) { 325 return Opcode == And || Opcode == Or || Opcode == Xor || 326 Opcode == Add || Opcode == Mul; 327 } 328 329 /// isCommutative - Return true if the instruction is commutative: 330 /// 331 /// Commutative operators satisfy: (x op y) === (y op x) 332 /// 333 /// In LLVM, these are the associative operators, plus SetEQ and SetNE, when 334 /// applied to any type. 335 /// 336 bool Instruction::isCommutative(unsigned op) { 337 switch (op) { 338 case Add: 339 case FAdd: 340 case Mul: 341 case FMul: 342 case And: 343 case Or: 344 case Xor: 345 return true; 346 default: 347 return false; 348 } 349 } 350 351 bool Instruction::isSafeToSpeculativelyExecute() const { 352 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 353 if (Constant *C = dyn_cast<Constant>(getOperand(i))) 354 if (C->canTrap()) 355 return false; 356 357 switch (getOpcode()) { 358 default: 359 return true; 360 case UDiv: 361 case URem: { 362 // x / y is undefined if y == 0, but calcuations like x / 3 are safe. 363 ConstantInt *Op = dyn_cast<ConstantInt>(getOperand(1)); 364 return Op && !Op->isNullValue(); 365 } 366 case SDiv: 367 case SRem: { 368 // x / y is undefined if y == 0, and might be undefined if y == -1, 369 // but calcuations like x / 3 are safe. 370 ConstantInt *Op = dyn_cast<ConstantInt>(getOperand(1)); 371 return Op && !Op->isNullValue() && !Op->isAllOnesValue(); 372 } 373 case Load: { 374 const LoadInst *LI = cast<LoadInst>(this); 375 if (LI->isVolatile()) 376 return false; 377 return LI->getPointerOperand()->isDereferenceablePointer(); 378 } 379 case Call: 380 return false; // The called function could have undefined behavior or 381 // side-effects. 382 // FIXME: We should special-case some intrinsics (bswap, 383 // overflow-checking arithmetic, etc.) 384 case VAArg: 385 case Alloca: 386 case Invoke: 387 case PHI: 388 case Store: 389 case Ret: 390 case Br: 391 case IndirectBr: 392 case Switch: 393 case Unwind: 394 case Unreachable: 395 return false; // Misc instructions which have effects 396 } 397 } 398 399 Instruction *Instruction::clone() const { 400 Instruction *New = clone_impl(); 401 New->SubclassOptionalData = SubclassOptionalData; 402 if (!hasMetadata()) 403 return New; 404 405 // Otherwise, enumerate and copy over metadata from the old instruction to the 406 // new one. 407 SmallVector<std::pair<unsigned, MDNode*>, 4> TheMDs; 408 getAllMetadataOtherThanDebugLoc(TheMDs); 409 for (unsigned i = 0, e = TheMDs.size(); i != e; ++i) 410 New->setMetadata(TheMDs[i].first, TheMDs[i].second); 411 412 New->setDebugLoc(getDebugLoc()); 413 return New; 414 } 415
