Instruction.cpp revision 263508
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 case AddrSpaceCast: return "addrspacecast"; 239 240 // Other instructions... 241 case ICmp: return "icmp"; 242 case FCmp: return "fcmp"; 243 case PHI: return "phi"; 244 case Select: return "select"; 245 case Call: return "call"; 246 case Shl: return "shl"; 247 case LShr: return "lshr"; 248 case AShr: return "ashr"; 249 case VAArg: return "va_arg"; 250 case ExtractElement: return "extractelement"; 251 case InsertElement: return "insertelement"; 252 case ShuffleVector: return "shufflevector"; 253 case ExtractValue: return "extractvalue"; 254 case InsertValue: return "insertvalue"; 255 case LandingPad: return "landingpad"; 256 257 default: return "<Invalid operator> "; 258 } 259} 260 261/// isIdenticalTo - Return true if the specified instruction is exactly 262/// identical to the current one. This means that all operands match and any 263/// extra information (e.g. load is volatile) agree. 264bool Instruction::isIdenticalTo(const Instruction *I) const { 265 return isIdenticalToWhenDefined(I) && 266 SubclassOptionalData == I->SubclassOptionalData; 267} 268 269/// isIdenticalToWhenDefined - This is like isIdenticalTo, except that it 270/// ignores the SubclassOptionalData flags, which specify conditions 271/// under which the instruction's result is undefined. 272bool Instruction::isIdenticalToWhenDefined(const Instruction *I) const { 273 if (getOpcode() != I->getOpcode() || 274 getNumOperands() != I->getNumOperands() || 275 getType() != I->getType()) 276 return false; 277 278 // We have two instructions of identical opcode and #operands. Check to see 279 // if all operands are the same. 280 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 281 if (getOperand(i) != I->getOperand(i)) 282 return false; 283 284 // Check special state that is a part of some instructions. 285 if (const LoadInst *LI = dyn_cast<LoadInst>(this)) 286 return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() && 287 LI->getAlignment() == cast<LoadInst>(I)->getAlignment() && 288 LI->getOrdering() == cast<LoadInst>(I)->getOrdering() && 289 LI->getSynchScope() == cast<LoadInst>(I)->getSynchScope(); 290 if (const StoreInst *SI = dyn_cast<StoreInst>(this)) 291 return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() && 292 SI->getAlignment() == cast<StoreInst>(I)->getAlignment() && 293 SI->getOrdering() == cast<StoreInst>(I)->getOrdering() && 294 SI->getSynchScope() == cast<StoreInst>(I)->getSynchScope(); 295 if (const CmpInst *CI = dyn_cast<CmpInst>(this)) 296 return CI->getPredicate() == cast<CmpInst>(I)->getPredicate(); 297 if (const CallInst *CI = dyn_cast<CallInst>(this)) 298 return CI->isTailCall() == cast<CallInst>(I)->isTailCall() && 299 CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() && 300 CI->getAttributes() == cast<CallInst>(I)->getAttributes(); 301 if (const InvokeInst *CI = dyn_cast<InvokeInst>(this)) 302 return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() && 303 CI->getAttributes() == cast<InvokeInst>(I)->getAttributes(); 304 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this)) 305 return IVI->getIndices() == cast<InsertValueInst>(I)->getIndices(); 306 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this)) 307 return EVI->getIndices() == cast<ExtractValueInst>(I)->getIndices(); 308 if (const FenceInst *FI = dyn_cast<FenceInst>(this)) 309 return FI->getOrdering() == cast<FenceInst>(FI)->getOrdering() && 310 FI->getSynchScope() == cast<FenceInst>(FI)->getSynchScope(); 311 if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(this)) 312 return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I)->isVolatile() && 313 CXI->getOrdering() == cast<AtomicCmpXchgInst>(I)->getOrdering() && 314 CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I)->getSynchScope(); 315 if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(this)) 316 return RMWI->getOperation() == cast<AtomicRMWInst>(I)->getOperation() && 317 RMWI->isVolatile() == cast<AtomicRMWInst>(I)->isVolatile() && 318 RMWI->getOrdering() == cast<AtomicRMWInst>(I)->getOrdering() && 319 RMWI->getSynchScope() == cast<AtomicRMWInst>(I)->getSynchScope(); 320 if (const PHINode *thisPHI = dyn_cast<PHINode>(this)) { 321 const PHINode *otherPHI = cast<PHINode>(I); 322 for (unsigned i = 0, e = thisPHI->getNumOperands(); i != e; ++i) { 323 if (thisPHI->getIncomingBlock(i) != otherPHI->getIncomingBlock(i)) 324 return false; 325 } 326 return true; 327 } 328 return true; 329} 330 331// isSameOperationAs 332// This should be kept in sync with isEquivalentOperation in 333// lib/Transforms/IPO/MergeFunctions.cpp. 334bool Instruction::isSameOperationAs(const Instruction *I, 335 unsigned flags) const { 336 bool IgnoreAlignment = flags & CompareIgnoringAlignment; 337 bool UseScalarTypes = flags & CompareUsingScalarTypes; 338 339 if (getOpcode() != I->getOpcode() || 340 getNumOperands() != I->getNumOperands() || 341 (UseScalarTypes ? 342 getType()->getScalarType() != I->getType()->getScalarType() : 343 getType() != I->getType())) 344 return false; 345 346 // We have two instructions of identical opcode and #operands. Check to see 347 // if all operands are the same type 348 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 349 if (UseScalarTypes ? 350 getOperand(i)->getType()->getScalarType() != 351 I->getOperand(i)->getType()->getScalarType() : 352 getOperand(i)->getType() != I->getOperand(i)->getType()) 353 return false; 354 355 // Check special state that is a part of some instructions. 356 if (const LoadInst *LI = dyn_cast<LoadInst>(this)) 357 return LI->isVolatile() == cast<LoadInst>(I)->isVolatile() && 358 (LI->getAlignment() == cast<LoadInst>(I)->getAlignment() || 359 IgnoreAlignment) && 360 LI->getOrdering() == cast<LoadInst>(I)->getOrdering() && 361 LI->getSynchScope() == cast<LoadInst>(I)->getSynchScope(); 362 if (const StoreInst *SI = dyn_cast<StoreInst>(this)) 363 return SI->isVolatile() == cast<StoreInst>(I)->isVolatile() && 364 (SI->getAlignment() == cast<StoreInst>(I)->getAlignment() || 365 IgnoreAlignment) && 366 SI->getOrdering() == cast<StoreInst>(I)->getOrdering() && 367 SI->getSynchScope() == cast<StoreInst>(I)->getSynchScope(); 368 if (const CmpInst *CI = dyn_cast<CmpInst>(this)) 369 return CI->getPredicate() == cast<CmpInst>(I)->getPredicate(); 370 if (const CallInst *CI = dyn_cast<CallInst>(this)) 371 return CI->isTailCall() == cast<CallInst>(I)->isTailCall() && 372 CI->getCallingConv() == cast<CallInst>(I)->getCallingConv() && 373 CI->getAttributes() == cast<CallInst>(I)->getAttributes(); 374 if (const InvokeInst *CI = dyn_cast<InvokeInst>(this)) 375 return CI->getCallingConv() == cast<InvokeInst>(I)->getCallingConv() && 376 CI->getAttributes() == 377 cast<InvokeInst>(I)->getAttributes(); 378 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(this)) 379 return IVI->getIndices() == cast<InsertValueInst>(I)->getIndices(); 380 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(this)) 381 return EVI->getIndices() == cast<ExtractValueInst>(I)->getIndices(); 382 if (const FenceInst *FI = dyn_cast<FenceInst>(this)) 383 return FI->getOrdering() == cast<FenceInst>(I)->getOrdering() && 384 FI->getSynchScope() == cast<FenceInst>(I)->getSynchScope(); 385 if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(this)) 386 return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I)->isVolatile() && 387 CXI->getOrdering() == cast<AtomicCmpXchgInst>(I)->getOrdering() && 388 CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I)->getSynchScope(); 389 if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(this)) 390 return RMWI->getOperation() == cast<AtomicRMWInst>(I)->getOperation() && 391 RMWI->isVolatile() == cast<AtomicRMWInst>(I)->isVolatile() && 392 RMWI->getOrdering() == cast<AtomicRMWInst>(I)->getOrdering() && 393 RMWI->getSynchScope() == cast<AtomicRMWInst>(I)->getSynchScope(); 394 395 return true; 396} 397 398/// isUsedOutsideOfBlock - Return true if there are any uses of I outside of the 399/// specified block. Note that PHI nodes are considered to evaluate their 400/// operands in the corresponding predecessor block. 401bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const { 402 for (const_use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { 403 // PHI nodes uses values in the corresponding predecessor block. For other 404 // instructions, just check to see whether the parent of the use matches up. 405 const User *U = *UI; 406 const PHINode *PN = dyn_cast<PHINode>(U); 407 if (PN == 0) { 408 if (cast<Instruction>(U)->getParent() != BB) 409 return true; 410 continue; 411 } 412 413 if (PN->getIncomingBlock(UI) != BB) 414 return true; 415 } 416 return false; 417} 418 419/// mayReadFromMemory - Return true if this instruction may read memory. 420/// 421bool Instruction::mayReadFromMemory() const { 422 switch (getOpcode()) { 423 default: return false; 424 case Instruction::VAArg: 425 case Instruction::Load: 426 case Instruction::Fence: // FIXME: refine definition of mayReadFromMemory 427 case Instruction::AtomicCmpXchg: 428 case Instruction::AtomicRMW: 429 return true; 430 case Instruction::Call: 431 return !cast<CallInst>(this)->doesNotAccessMemory(); 432 case Instruction::Invoke: 433 return !cast<InvokeInst>(this)->doesNotAccessMemory(); 434 case Instruction::Store: 435 return !cast<StoreInst>(this)->isUnordered(); 436 } 437} 438 439/// mayWriteToMemory - Return true if this instruction may modify memory. 440/// 441bool Instruction::mayWriteToMemory() const { 442 switch (getOpcode()) { 443 default: return false; 444 case Instruction::Fence: // FIXME: refine definition of mayWriteToMemory 445 case Instruction::Store: 446 case Instruction::VAArg: 447 case Instruction::AtomicCmpXchg: 448 case Instruction::AtomicRMW: 449 return true; 450 case Instruction::Call: 451 return !cast<CallInst>(this)->onlyReadsMemory(); 452 case Instruction::Invoke: 453 return !cast<InvokeInst>(this)->onlyReadsMemory(); 454 case Instruction::Load: 455 return !cast<LoadInst>(this)->isUnordered(); 456 } 457} 458 459bool Instruction::mayThrow() const { 460 if (const CallInst *CI = dyn_cast<CallInst>(this)) 461 return !CI->doesNotThrow(); 462 return isa<ResumeInst>(this); 463} 464 465bool Instruction::mayReturn() const { 466 if (const CallInst *CI = dyn_cast<CallInst>(this)) 467 return !CI->doesNotReturn(); 468 return true; 469} 470 471/// isAssociative - Return true if the instruction is associative: 472/// 473/// Associative operators satisfy: x op (y op z) === (x op y) op z 474/// 475/// In LLVM, the Add, Mul, And, Or, and Xor operators are associative. 476/// 477bool Instruction::isAssociative(unsigned Opcode) { 478 return Opcode == And || Opcode == Or || Opcode == Xor || 479 Opcode == Add || Opcode == Mul; 480} 481 482bool Instruction::isAssociative() const { 483 unsigned Opcode = getOpcode(); 484 if (isAssociative(Opcode)) 485 return true; 486 487 switch (Opcode) { 488 case FMul: 489 case FAdd: 490 return cast<FPMathOperator>(this)->hasUnsafeAlgebra(); 491 default: 492 return false; 493 } 494} 495 496/// isCommutative - Return true if the instruction is commutative: 497/// 498/// Commutative operators satisfy: (x op y) === (y op x) 499/// 500/// In LLVM, these are the associative operators, plus SetEQ and SetNE, when 501/// applied to any type. 502/// 503bool Instruction::isCommutative(unsigned op) { 504 switch (op) { 505 case Add: 506 case FAdd: 507 case Mul: 508 case FMul: 509 case And: 510 case Or: 511 case Xor: 512 return true; 513 default: 514 return false; 515 } 516} 517 518/// isIdempotent - Return true if the instruction is idempotent: 519/// 520/// Idempotent operators satisfy: x op x === x 521/// 522/// In LLVM, the And and Or operators are idempotent. 523/// 524bool Instruction::isIdempotent(unsigned Opcode) { 525 return Opcode == And || Opcode == Or; 526} 527 528/// isNilpotent - Return true if the instruction is nilpotent: 529/// 530/// Nilpotent operators satisfy: x op x === Id, 531/// 532/// where Id is the identity for the operator, i.e. a constant such that 533/// x op Id === x and Id op x === x for all x. 534/// 535/// In LLVM, the Xor operator is nilpotent. 536/// 537bool Instruction::isNilpotent(unsigned Opcode) { 538 return Opcode == Xor; 539} 540 541Instruction *Instruction::clone() const { 542 Instruction *New = clone_impl(); 543 New->SubclassOptionalData = SubclassOptionalData; 544 if (!hasMetadata()) 545 return New; 546 547 // Otherwise, enumerate and copy over metadata from the old instruction to the 548 // new one. 549 SmallVector<std::pair<unsigned, MDNode*>, 4> TheMDs; 550 getAllMetadataOtherThanDebugLoc(TheMDs); 551 for (unsigned i = 0, e = TheMDs.size(); i != e; ++i) 552 New->setMetadata(TheMDs[i].first, TheMDs[i].second); 553 554 New->setDebugLoc(getDebugLoc()); 555 return New; 556} 557