1 //===- subzero/src/IceInst.cpp - High-level instruction implementation ----===// 2 // 3 // The Subzero Code Generator 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// 10 /// \file 11 /// \brief Implements the Inst class, primarily the various subclass 12 /// constructors and dump routines. 13 /// 14 //===----------------------------------------------------------------------===// 15 16 #include "IceInst.h" 17 18 #include "IceCfg.h" 19 #include "IceCfgNode.h" 20 #include "IceInstVarIter.h" 21 #include "IceLiveness.h" 22 #include "IceOperand.h" 23 #include "IceTargetLowering.h" 24 25 #include "llvm/Support/Format.h" 26 27 namespace Ice { 28 29 namespace { 30 31 // Using non-anonymous struct so that array_lengthof works. 32 const struct InstArithmeticAttributes_ { 33 const char *DisplayString; 34 bool IsCommutative; 35 } InstArithmeticAttributes[] = { 36 #define X(tag, str, commutative) \ 37 { str, commutative } \ 38 , 39 ICEINSTARITHMETIC_TABLE 40 #undef X 41 }; 42 43 // Using non-anonymous struct so that array_lengthof works. 44 const struct InstCastAttributes_ { 45 const char *DisplayString; 46 } InstCastAttributes[] = { 47 #define X(tag, str) \ 48 { str } \ 49 , 50 ICEINSTCAST_TABLE 51 #undef X 52 }; 53 54 // Using non-anonymous struct so that array_lengthof works. 55 const struct InstFcmpAttributes_ { 56 const char *DisplayString; 57 } InstFcmpAttributes[] = { 58 #define X(tag, str) \ 59 { str } \ 60 , 61 ICEINSTFCMP_TABLE 62 #undef X 63 }; 64 65 // Using non-anonymous struct so that array_lengthof works. 66 const struct InstIcmpAttributes_ { 67 const char *DisplayString; 68 InstIcmp::ICond Reverse; 69 } InstIcmpAttributes[] = { 70 #define X(tag, reverse, str) \ 71 { str, InstIcmp::ICond::reverse } \ 72 , 73 ICEINSTICMP_TABLE 74 #undef X 75 }; 76 77 } // end of anonymous namespace 78 79 Inst::Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest) 80 : Kind(Kind), Number(Func->newInstNumber()), Dest(Dest), MaxSrcs(MaxSrcs), 81 LiveRangesEnded(0) { 82 Srcs.reserve(MaxSrcs); 83 } 84 85 const char *Inst::getInstName() const { 86 if (!BuildDefs::dump()) 87 return "???"; 88 89 switch (Kind) { 90 #define X(InstrKind, name) \ 91 case InstrKind: \ 92 return name 93 X(Unreachable, "unreachable"); 94 X(Alloca, "alloca"); 95 X(Arithmetic, "arithmetic"); 96 X(Br, "br"); 97 X(Call, "call"); 98 X(Cast, "cast"); 99 X(ExtractElement, "extractelement"); 100 X(Fcmp, "fcmp"); 101 X(Icmp, "icmp"); 102 X(IntrinsicCall, "intrinsiccall"); 103 X(InsertElement, "insertelement"); 104 X(Load, "load"); 105 X(Phi, "phi"); 106 X(Ret, "ret"); 107 X(Select, "select"); 108 X(Store, "store"); 109 X(Switch, "switch"); 110 X(Assign, "assign"); 111 X(Breakpoint, "break"); 112 X(BundleLock, "bundlelock"); 113 X(BundleUnlock, "bundleunlock"); 114 X(FakeDef, "fakedef"); 115 X(FakeUse, "fakeuse"); 116 X(FakeKill, "fakekill"); 117 X(JumpTable, "jumptable"); 118 X(ShuffleVector, "shufflevector"); 119 #undef X 120 default: 121 assert(Kind >= Target); 122 return "target"; 123 } 124 } 125 126 // Assign the instruction a new number. 127 void Inst::renumber(Cfg *Func) { 128 Number = isDeleted() ? NumberDeleted : Func->newInstNumber(); 129 } 130 131 // Delete the instruction if its tentative Dead flag is still set after 132 // liveness analysis. 133 void Inst::deleteIfDead() { 134 if (Dead) 135 setDeleted(); 136 } 137 138 // If Src is a Variable, it returns true if this instruction ends Src's live 139 // range. Otherwise, returns false. 140 bool Inst::isLastUse(const Operand *TestSrc) const { 141 if (LiveRangesEnded == 0) 142 return false; // early-exit optimization 143 if (auto *TestVar = llvm::dyn_cast<const Variable>(TestSrc)) { 144 LREndedBits Mask = LiveRangesEnded; 145 FOREACH_VAR_IN_INST(Var, *this) { 146 if (Var == TestVar) { 147 // We've found where the variable is used in the instruction. 148 return Mask & 1; 149 } 150 Mask >>= 1; 151 if (Mask == 0) 152 return false; // another early-exit optimization 153 } 154 } 155 return false; 156 } 157 158 // Given an instruction like: 159 // a = b + c + [x,y] + e 160 // which was created from OrigInst: 161 // a = b + c + d + e 162 // with SpliceAssn spliced in: 163 // d = [x,y] 164 // 165 // Reconstruct the LiveRangesEnded bitmask in this instruction by combining the 166 // LiveRangesEnded values of OrigInst and SpliceAssn. If operands d and [x,y] 167 // contain a different number of variables, then the bitmask position for e may 168 // be different in OrigInst and the current instruction, requiring extra shifts 169 // and masks in the computation. In the example above, OrigInst has variable e 170 // in bit position 3, whereas the current instruction has e in bit position 4 171 // because [x,y] consumes 2 bitmask slots while d only consumed 1. 172 // 173 // Additionally, set HasSideEffects if either OrigInst or SpliceAssn have 174 // HasSideEffects set. 175 void Inst::spliceLivenessInfo(Inst *OrigInst, Inst *SpliceAssn) { 176 HasSideEffects |= OrigInst->HasSideEffects; 177 HasSideEffects |= SpliceAssn->HasSideEffects; 178 // Find the bitmask index of SpliceAssn's dest within OrigInst. 179 Variable *SpliceDest = SpliceAssn->getDest(); 180 SizeT Index = 0; 181 for (SizeT I = 0; I < OrigInst->getSrcSize(); ++I) { 182 Operand *Src = OrigInst->getSrc(I); 183 if (Src == SpliceDest) { 184 LREndedBits LeftMask = OrigInst->LiveRangesEnded & ((1 << Index) - 1); 185 LREndedBits RightMask = OrigInst->LiveRangesEnded >> (Index + 1); 186 LiveRangesEnded = LeftMask | (SpliceAssn->LiveRangesEnded << Index) | 187 (RightMask << (Index + getSrc(I)->getNumVars())); 188 return; 189 } 190 Index += getSrc(I)->getNumVars(); 191 } 192 llvm::report_fatal_error("Failed to find splice operand"); 193 } 194 195 bool Inst::isMemoryWrite() const { 196 llvm::report_fatal_error("Attempt to call base Inst::isMemoryWrite() method"); 197 } 198 199 void Inst::livenessLightweight(Cfg *Func, LivenessBV &Live) { 200 assert(!isDeleted()); 201 resetLastUses(); 202 VariablesMetadata *VMetadata = Func->getVMetadata(); 203 FOREACH_VAR_IN_INST(Var, *this) { 204 if (VMetadata->isMultiBlock(Var)) 205 continue; 206 SizeT Index = Var->getIndex(); 207 if (Live[Index]) 208 continue; 209 Live[Index] = true; 210 setLastUse(IndexOfVarInInst(Var)); 211 } 212 } 213 214 bool Inst::liveness(InstNumberT InstNumber, LivenessBV &Live, 215 Liveness *Liveness, LiveBeginEndMap *LiveBegin, 216 LiveBeginEndMap *LiveEnd) { 217 assert(!isDeleted()); 218 219 Dead = false; 220 if (Dest && !Dest->isRematerializable()) { 221 SizeT VarNum = Liveness->getLiveIndex(Dest->getIndex()); 222 if (Live[VarNum]) { 223 if (!isDestRedefined()) { 224 Live[VarNum] = false; 225 if (LiveBegin && Liveness->getRangeMask(Dest->getIndex())) { 226 LiveBegin->push_back(std::make_pair(VarNum, InstNumber)); 227 } 228 } 229 } else { 230 if (!hasSideEffects()) 231 Dead = true; 232 } 233 } 234 if (Dead) 235 return false; 236 // Phi arguments only get added to Live in the predecessor node, but we still 237 // need to update LiveRangesEnded. 238 bool IsPhi = llvm::isa<InstPhi>(this); 239 resetLastUses(); 240 FOREACH_VAR_IN_INST(Var, *this) { 241 if (Var->isRematerializable()) 242 continue; 243 SizeT VarNum = Liveness->getLiveIndex(Var->getIndex()); 244 if (!Live[VarNum]) { 245 setLastUse(IndexOfVarInInst(Var)); 246 if (!IsPhi) { 247 Live[VarNum] = true; 248 // For a variable in SSA form, its live range can end at most once in a 249 // basic block. However, after lowering to two-address instructions, we 250 // end up with sequences like "t=b;t+=c;a=t" where t's live range 251 // begins and ends twice. ICE only allows a variable to have a single 252 // liveness interval in a basic block (except for blocks where a 253 // variable is live-in and live-out but there is a gap in the middle). 254 // Therefore, this lowered sequence needs to represent a single 255 // conservative live range for t. Since the instructions are being 256 // traversed backwards, we make sure LiveEnd is only set once by 257 // setting it only when LiveEnd[VarNum]==0 (sentinel value). Note that 258 // it's OK to set LiveBegin multiple times because of the backwards 259 // traversal. 260 if (LiveEnd && Liveness->getRangeMask(Var->getIndex())) { 261 // Ideally, we would verify that VarNum wasn't already added in this 262 // block, but this can't be done very efficiently with LiveEnd as a 263 // vector. Instead, livenessPostprocess() verifies this after the 264 // vector has been sorted. 265 LiveEnd->push_back(std::make_pair(VarNum, InstNumber)); 266 } 267 } 268 } 269 } 270 return true; 271 } 272 273 InstAlloca::InstAlloca(Cfg *Func, Variable *Dest, Operand *ByteCount, 274 uint32_t AlignInBytes) 275 : InstHighLevel(Func, Inst::Alloca, 1, Dest), AlignInBytes(AlignInBytes) { 276 // Verify AlignInBytes is 0 or a power of 2. 277 assert(AlignInBytes == 0 || llvm::isPowerOf2_32(AlignInBytes)); 278 addSource(ByteCount); 279 } 280 281 InstArithmetic::InstArithmetic(Cfg *Func, OpKind Op, Variable *Dest, 282 Operand *Source1, Operand *Source2) 283 : InstHighLevel(Func, Inst::Arithmetic, 2, Dest), Op(Op) { 284 addSource(Source1); 285 addSource(Source2); 286 } 287 288 const char *InstArithmetic::getInstName() const { 289 if (!BuildDefs::dump()) 290 return "???"; 291 292 return InstArithmeticAttributes[getOp()].DisplayString; 293 } 294 295 const char *InstArithmetic::getOpName(OpKind Op) { 296 return Op < InstArithmetic::_num ? InstArithmeticAttributes[Op].DisplayString 297 : "???"; 298 } 299 300 bool InstArithmetic::isCommutative() const { 301 return InstArithmeticAttributes[getOp()].IsCommutative; 302 } 303 304 InstAssign::InstAssign(Cfg *Func, Variable *Dest, Operand *Source) 305 : InstHighLevel(Func, Inst::Assign, 1, Dest) { 306 addSource(Source); 307 } 308 309 bool InstAssign::isVarAssign() const { return llvm::isa<Variable>(getSrc(0)); } 310 311 // If TargetTrue==TargetFalse, we turn it into an unconditional branch. This 312 // ensures that, along with the 'switch' instruction semantics, there is at 313 // most one edge from one node to another. 314 InstBr::InstBr(Cfg *Func, Operand *Source, CfgNode *TargetTrue_, 315 CfgNode *TargetFalse_) 316 : InstHighLevel(Func, Inst::Br, 1, nullptr), TargetFalse(TargetFalse_), 317 TargetTrue(TargetTrue_) { 318 if (auto *Constant = llvm::dyn_cast<ConstantInteger32>(Source)) { 319 int32_t C32 = Constant->getValue(); 320 if (C32 != 0) { 321 TargetFalse = TargetTrue; 322 } 323 TargetTrue = nullptr; // turn into unconditional version 324 } else if (TargetTrue == TargetFalse) { 325 TargetTrue = nullptr; // turn into unconditional version 326 } else { 327 addSource(Source); 328 } 329 } 330 331 InstBr::InstBr(Cfg *Func, CfgNode *Target) 332 : InstHighLevel(Func, Inst::Br, 0, nullptr), TargetFalse(Target), 333 TargetTrue(nullptr) {} 334 335 NodeList InstBr::getTerminatorEdges() const { 336 NodeList OutEdges; 337 OutEdges.reserve(TargetTrue ? 2 : 1); 338 OutEdges.push_back(TargetFalse); 339 if (TargetTrue) 340 OutEdges.push_back(TargetTrue); 341 return OutEdges; 342 } 343 344 bool InstBr::repointEdges(CfgNode *OldNode, CfgNode *NewNode) { 345 bool Found = false; 346 if (TargetFalse == OldNode) { 347 TargetFalse = NewNode; 348 Found = true; 349 } 350 if (TargetTrue == OldNode) { 351 TargetTrue = NewNode; 352 Found = true; 353 } 354 return Found; 355 } 356 357 InstCast::InstCast(Cfg *Func, OpKind CastKind, Variable *Dest, Operand *Source) 358 : InstHighLevel(Func, Inst::Cast, 1, Dest), CastKind(CastKind) { 359 addSource(Source); 360 } 361 362 InstExtractElement::InstExtractElement(Cfg *Func, Variable *Dest, 363 Operand *Source1, Operand *Source2) 364 : InstHighLevel(Func, Inst::ExtractElement, 2, Dest) { 365 addSource(Source1); 366 addSource(Source2); 367 } 368 369 InstFcmp::InstFcmp(Cfg *Func, FCond Condition, Variable *Dest, Operand *Source1, 370 Operand *Source2) 371 : InstHighLevel(Func, Inst::Fcmp, 2, Dest), Condition(Condition) { 372 addSource(Source1); 373 addSource(Source2); 374 } 375 376 InstIcmp::InstIcmp(Cfg *Func, ICond Condition, Variable *Dest, Operand *Source1, 377 Operand *Source2) 378 : InstHighLevel(Func, Inst::Icmp, 2, Dest), Condition(Condition) { 379 addSource(Source1); 380 addSource(Source2); 381 } 382 383 InstInsertElement::InstInsertElement(Cfg *Func, Variable *Dest, 384 Operand *Source1, Operand *Source2, 385 Operand *Source3) 386 : InstHighLevel(Func, Inst::InsertElement, 3, Dest) { 387 addSource(Source1); 388 addSource(Source2); 389 addSource(Source3); 390 } 391 392 InstLoad::InstLoad(Cfg *Func, Variable *Dest, Operand *SourceAddr) 393 : InstHighLevel(Func, Inst::Load, 1, Dest) { 394 addSource(SourceAddr); 395 } 396 397 InstPhi::InstPhi(Cfg *Func, SizeT MaxSrcs, Variable *Dest) 398 : InstHighLevel(Func, Phi, MaxSrcs, Dest) { 399 Labels.reserve(MaxSrcs); 400 } 401 402 // TODO: A Switch instruction (and maybe others) can add duplicate edges. We 403 // may want to de-dup Phis and validate consistency (i.e., the source operands 404 // are the same for duplicate edges), though it seems the current lowering code 405 // is OK with this situation. 406 void InstPhi::addArgument(Operand *Source, CfgNode *Label) { 407 assert(Label); 408 Labels.push_back(Label); 409 addSource(Source); 410 } 411 412 // Find the source operand corresponding to the incoming edge for the given 413 // node. 414 Operand *InstPhi::getOperandForTarget(CfgNode *Target) const { 415 for (SizeT I = 0; I < getSrcSize(); ++I) { 416 if (Labels[I] == Target) 417 return getSrc(I); 418 } 419 llvm_unreachable("Phi target not found"); 420 return nullptr; 421 } 422 423 // Replace the source operand corresponding to the incoming edge for the given 424 // node by a zero of the appropriate type. 425 void InstPhi::clearOperandForTarget(CfgNode *Target) { 426 for (SizeT I = 0; I < getSrcSize(); ++I) { 427 if (getLabel(I) == Target) { 428 Type Ty = Dest->getType(); 429 Srcs[I] = Target->getCfg()->getContext()->getConstantZero(Ty); 430 return; 431 } 432 } 433 llvm_unreachable("Phi target not found"); 434 } 435 436 // Updates liveness for a particular operand based on the given predecessor 437 // edge. Doesn't mark the operand as live if the Phi instruction is dead or 438 // deleted. 439 void InstPhi::livenessPhiOperand(LivenessBV &Live, CfgNode *Target, 440 Liveness *Liveness) { 441 if (isDeleted() || Dead) 442 return; 443 for (SizeT I = 0; I < getSrcSize(); ++I) { 444 if (Labels[I] == Target) { 445 if (auto *Var = llvm::dyn_cast<Variable>(getSrc(I))) { 446 if (!Var->isRematerializable()) { 447 SizeT SrcIndex = Liveness->getLiveIndex(Var->getIndex()); 448 if (!Live[SrcIndex]) { 449 setLastUse(I); 450 Live[SrcIndex] = true; 451 } 452 } 453 } 454 return; 455 } 456 } 457 llvm_unreachable("Phi operand not found for specified target node"); 458 } 459 460 // Change "a=phi(...)" to "a_phi=phi(...)" and return a new instruction 461 // "a=a_phi". 462 Inst *InstPhi::lower(Cfg *Func) { 463 Variable *Dest = getDest(); 464 assert(Dest); 465 Variable *NewSrc = Func->makeVariable(Dest->getType()); 466 if (BuildDefs::dump()) 467 NewSrc->setName(Func, Dest->getName() + "_phi"); 468 if (auto *NewSrc64On32 = llvm::dyn_cast<Variable64On32>(NewSrc)) 469 NewSrc64On32->initHiLo(Func); 470 this->Dest = NewSrc; 471 return InstAssign::create(Func, Dest, NewSrc); 472 } 473 474 InstRet::InstRet(Cfg *Func, Operand *RetValue) 475 : InstHighLevel(Func, Ret, RetValue ? 1 : 0, nullptr) { 476 if (RetValue) 477 addSource(RetValue); 478 } 479 480 InstSelect::InstSelect(Cfg *Func, Variable *Dest, Operand *Condition, 481 Operand *SourceTrue, Operand *SourceFalse) 482 : InstHighLevel(Func, Inst::Select, 3, Dest) { 483 assert(typeElementType(Condition->getType()) == IceType_i1); 484 addSource(Condition); 485 addSource(SourceTrue); 486 addSource(SourceFalse); 487 } 488 489 InstStore::InstStore(Cfg *Func, Operand *Data, Operand *Addr) 490 : InstHighLevel(Func, Inst::Store, 3, nullptr) { 491 addSource(Data); 492 addSource(Addr); 493 // The 3rd operand is a dummy placeholder for the RMW beacon. 494 addSource(Data); 495 } 496 497 Variable *InstStore::getRmwBeacon() const { 498 return llvm::dyn_cast<Variable>(getSrc(2)); 499 } 500 501 void InstStore::setRmwBeacon(Variable *Beacon) { 502 Dest = llvm::dyn_cast<Variable>(getData()); 503 Srcs[2] = Beacon; 504 } 505 506 InstSwitch::InstSwitch(Cfg *Func, SizeT NumCases, Operand *Source, 507 CfgNode *LabelDefault) 508 : InstHighLevel(Func, Inst::Switch, 1, nullptr), LabelDefault(LabelDefault), 509 NumCases(NumCases) { 510 addSource(Source); 511 Values = Func->allocateArrayOf<uint64_t>(NumCases); 512 Labels = Func->allocateArrayOf<CfgNode *>(NumCases); 513 // Initialize in case buggy code doesn't set all entries 514 for (SizeT I = 0; I < NumCases; ++I) { 515 Values[I] = 0; 516 Labels[I] = nullptr; 517 } 518 } 519 520 void InstSwitch::addBranch(SizeT CaseIndex, uint64_t Value, CfgNode *Label) { 521 assert(CaseIndex < NumCases); 522 Values[CaseIndex] = Value; 523 Labels[CaseIndex] = Label; 524 } 525 526 NodeList InstSwitch::getTerminatorEdges() const { 527 NodeList OutEdges; 528 OutEdges.reserve(NumCases + 1); 529 assert(LabelDefault); 530 OutEdges.push_back(LabelDefault); 531 for (SizeT I = 0; I < NumCases; ++I) { 532 assert(Labels[I]); 533 OutEdges.push_back(Labels[I]); 534 } 535 std::sort(OutEdges.begin(), OutEdges.end(), 536 [](const CfgNode *x, const CfgNode *y) { 537 return x->getIndex() < y->getIndex(); 538 }); 539 auto Last = std::unique(OutEdges.begin(), OutEdges.end()); 540 OutEdges.erase(Last, OutEdges.end()); 541 return OutEdges; 542 } 543 544 bool InstSwitch::repointEdges(CfgNode *OldNode, CfgNode *NewNode) { 545 bool Found = false; 546 if (LabelDefault == OldNode) { 547 LabelDefault = NewNode; 548 Found = true; 549 } 550 for (SizeT I = 0; I < NumCases; ++I) { 551 if (Labels[I] == OldNode) { 552 Labels[I] = NewNode; 553 Found = true; 554 } 555 } 556 return Found; 557 } 558 559 InstUnreachable::InstUnreachable(Cfg *Func) 560 : InstHighLevel(Func, Inst::Unreachable, 0, nullptr) {} 561 562 InstBundleLock::InstBundleLock(Cfg *Func, InstBundleLock::Option BundleOption) 563 : InstHighLevel(Func, Inst::BundleLock, 0, nullptr), 564 BundleOption(BundleOption) {} 565 566 InstBundleUnlock::InstBundleUnlock(Cfg *Func) 567 : InstHighLevel(Func, Inst::BundleUnlock, 0, nullptr) {} 568 569 InstFakeDef::InstFakeDef(Cfg *Func, Variable *Dest, Variable *Src) 570 : InstHighLevel(Func, Inst::FakeDef, Src ? 1 : 0, Dest) { 571 assert(Dest); 572 if (Src) 573 addSource(Src); 574 } 575 576 InstFakeUse::InstFakeUse(Cfg *Func, Variable *Src, uint32_t Weight) 577 : InstHighLevel(Func, Inst::FakeUse, Weight, nullptr) { 578 assert(Src); 579 for (uint32_t i = 0; i < Weight; ++i) 580 addSource(Src); 581 } 582 583 InstFakeKill::InstFakeKill(Cfg *Func, const Inst *Linked) 584 : InstHighLevel(Func, Inst::FakeKill, 0, nullptr), Linked(Linked) {} 585 586 InstShuffleVector::InstShuffleVector(Cfg *Func, Variable *Dest, Operand *Src0, 587 Operand *Src1) 588 : InstHighLevel(Func, Inst::ShuffleVector, 2, Dest), 589 NumIndexes(typeNumElements(Dest->getType())) { 590 addSource(Src0); 591 addSource(Src1); 592 Indexes = Func->allocateArrayOf<ConstantInteger32 *>(NumIndexes); 593 } 594 595 namespace { 596 GlobalString makeName(Cfg *Func, const SizeT Id) { 597 const auto FuncName = Func->getFunctionName(); 598 auto *Ctx = Func->getContext(); 599 if (FuncName.hasStdString()) 600 return GlobalString::createWithString( 601 Ctx, ".L" + FuncName.toString() + "$jumptable$__" + std::to_string(Id)); 602 return GlobalString::createWithString( 603 Ctx, "$J" + std::to_string(FuncName.getID()) + "_" + std::to_string(Id)); 604 } 605 } // end of anonymous namespace 606 607 InstJumpTable::InstJumpTable(Cfg *Func, SizeT NumTargets, CfgNode *Default) 608 : InstHighLevel(Func, Inst::JumpTable, 1, nullptr), 609 Id(Func->getTarget()->makeNextJumpTableNumber()), NumTargets(NumTargets), 610 Name(makeName(Func, Id)), FuncName(Func->getFunctionName()) { 611 Targets = Func->allocateArrayOf<CfgNode *>(NumTargets); 612 for (SizeT I = 0; I < NumTargets; ++I) { 613 Targets[I] = Default; 614 } 615 } 616 617 bool InstJumpTable::repointEdges(CfgNode *OldNode, CfgNode *NewNode) { 618 bool Found = false; 619 for (SizeT I = 0; I < NumTargets; ++I) { 620 if (Targets[I] == OldNode) { 621 Targets[I] = NewNode; 622 Found = true; 623 } 624 } 625 return Found; 626 } 627 628 JumpTableData InstJumpTable::toJumpTableData(Assembler *Asm) const { 629 JumpTableData::TargetList TargetList(NumTargets); 630 for (SizeT i = 0; i < NumTargets; ++i) { 631 const SizeT Index = Targets[i]->getIndex(); 632 TargetList[i] = Asm->getCfgNodeLabel(Index)->getPosition(); 633 } 634 return JumpTableData(Name, FuncName, Id, TargetList); 635 } 636 637 Type InstCall::getReturnType() const { 638 if (Dest == nullptr) 639 return IceType_void; 640 return Dest->getType(); 641 } 642 643 // ======================== Dump routines ======================== // 644 645 void Inst::dumpDecorated(const Cfg *Func) const { 646 if (!BuildDefs::dump()) 647 return; 648 Ostream &Str = Func->getContext()->getStrDump(); 649 if (!Func->isVerbose(IceV_Deleted) && (isDeleted() || isRedundantAssign())) 650 return; 651 if (Func->isVerbose(IceV_InstNumbers)) { 652 InstNumberT Number = getNumber(); 653 if (Number == NumberDeleted) 654 Str << "[XXX]"; 655 else 656 Str << llvm::format("[%3d]", Number); 657 } 658 Str << " "; 659 if (isDeleted()) 660 Str << " //"; 661 dump(Func); 662 dumpExtras(Func); 663 Str << "\n"; 664 } 665 666 void Inst::dump(const Cfg *Func) const { 667 if (!BuildDefs::dump()) 668 return; 669 Ostream &Str = Func->getContext()->getStrDump(); 670 dumpDest(Func); 671 Str << " =~ " << getInstName() << " "; 672 dumpSources(Func); 673 } 674 675 void Inst::dumpExtras(const Cfg *Func) const { 676 if (!BuildDefs::dump()) 677 return; 678 Ostream &Str = Func->getContext()->getStrDump(); 679 bool First = true; 680 // Print "LIVEEND={a,b,c}" for all source operands whose live ranges are 681 // known to end at this instruction. 682 if (Func->isVerbose(IceV_Liveness)) { 683 FOREACH_VAR_IN_INST(Var, *this) { 684 if (isLastUse(Var)) { 685 if (First) 686 Str << " // LIVEEND={"; 687 else 688 Str << ","; 689 Var->dump(Func); 690 First = false; 691 } 692 } 693 if (!First) 694 Str << "}"; 695 } 696 } 697 698 void Inst::dumpSources(const Cfg *Func) const { 699 if (!BuildDefs::dump()) 700 return; 701 Ostream &Str = Func->getContext()->getStrDump(); 702 for (SizeT I = 0; I < getSrcSize(); ++I) { 703 if (I > 0) 704 Str << ", "; 705 getSrc(I)->dump(Func); 706 } 707 } 708 709 void Inst::emitSources(const Cfg *Func) const { 710 if (!BuildDefs::dump()) 711 return; 712 Ostream &Str = Func->getContext()->getStrEmit(); 713 for (SizeT I = 0; I < getSrcSize(); ++I) { 714 if (I > 0) 715 Str << ", "; 716 getSrc(I)->emit(Func); 717 } 718 } 719 720 void Inst::dumpDest(const Cfg *Func) const { 721 if (!BuildDefs::dump()) 722 return; 723 if (getDest()) 724 getDest()->dump(Func); 725 } 726 727 void InstAlloca::dump(const Cfg *Func) const { 728 if (!BuildDefs::dump()) 729 return; 730 Ostream &Str = Func->getContext()->getStrDump(); 731 dumpDest(Func); 732 Str << " = alloca i8, i32 "; 733 getSizeInBytes()->dump(Func); 734 if (getAlignInBytes()) 735 Str << ", align " << getAlignInBytes(); 736 } 737 738 void InstArithmetic::dump(const Cfg *Func) const { 739 if (!BuildDefs::dump()) 740 return; 741 Ostream &Str = Func->getContext()->getStrDump(); 742 dumpDest(Func); 743 Str << " = " << getInstName() << " " << getDest()->getType() << " "; 744 dumpSources(Func); 745 } 746 747 void InstAssign::dump(const Cfg *Func) const { 748 if (!BuildDefs::dump()) 749 return; 750 Ostream &Str = Func->getContext()->getStrDump(); 751 dumpDest(Func); 752 Str << " = " << getDest()->getType() << " "; 753 dumpSources(Func); 754 } 755 756 void InstBr::dump(const Cfg *Func) const { 757 if (!BuildDefs::dump()) 758 return; 759 Ostream &Str = Func->getContext()->getStrDump(); 760 dumpDest(Func); 761 Str << "br "; 762 if (!isUnconditional()) { 763 Str << "i1 "; 764 getCondition()->dump(Func); 765 Str << ", label %" << getTargetTrue()->getName() << ", "; 766 } 767 Str << "label %" << getTargetFalse()->getName(); 768 } 769 770 void InstCall::dump(const Cfg *Func) const { 771 if (!BuildDefs::dump()) 772 return; 773 Ostream &Str = Func->getContext()->getStrDump(); 774 if (getDest()) { 775 dumpDest(Func); 776 Str << " = "; 777 } 778 Str << "call "; 779 if (getDest()) 780 Str << getDest()->getType(); 781 else 782 Str << "void"; 783 Str << " "; 784 getCallTarget()->dump(Func); 785 Str << "("; 786 for (SizeT I = 0; I < getNumArgs(); ++I) { 787 if (I > 0) 788 Str << ", "; 789 Str << getArg(I)->getType() << " "; 790 getArg(I)->dump(Func); 791 } 792 Str << ")"; 793 } 794 795 const char *InstCast::getCastName(InstCast::OpKind Kind) { 796 if (Kind < InstCast::OpKind::_num) 797 return InstCastAttributes[Kind].DisplayString; 798 llvm_unreachable("Invalid InstCast::OpKind"); 799 return "???"; 800 } 801 802 void InstCast::dump(const Cfg *Func) const { 803 if (!BuildDefs::dump()) 804 return; 805 Ostream &Str = Func->getContext()->getStrDump(); 806 dumpDest(Func); 807 Str << " = " << getCastName(getCastKind()) << " " << getSrc(0)->getType() 808 << " "; 809 dumpSources(Func); 810 Str << " to " << getDest()->getType(); 811 } 812 813 void InstIcmp::dump(const Cfg *Func) const { 814 if (!BuildDefs::dump()) 815 return; 816 Ostream &Str = Func->getContext()->getStrDump(); 817 dumpDest(Func); 818 Str << " = icmp " << InstIcmpAttributes[getCondition()].DisplayString << " " 819 << getSrc(0)->getType() << " "; 820 dumpSources(Func); 821 } 822 823 void InstExtractElement::dump(const Cfg *Func) const { 824 if (!BuildDefs::dump()) 825 return; 826 Ostream &Str = Func->getContext()->getStrDump(); 827 dumpDest(Func); 828 Str << " = extractelement "; 829 Str << getSrc(0)->getType() << " "; 830 getSrc(0)->dump(Func); 831 Str << ", "; 832 Str << getSrc(1)->getType() << " "; 833 getSrc(1)->dump(Func); 834 } 835 836 void InstInsertElement::dump(const Cfg *Func) const { 837 if (!BuildDefs::dump()) 838 return; 839 Ostream &Str = Func->getContext()->getStrDump(); 840 dumpDest(Func); 841 Str << " = insertelement "; 842 Str << getSrc(0)->getType() << " "; 843 getSrc(0)->dump(Func); 844 Str << ", "; 845 Str << getSrc(1)->getType() << " "; 846 getSrc(1)->dump(Func); 847 Str << ", "; 848 Str << getSrc(2)->getType() << " "; 849 getSrc(2)->dump(Func); 850 } 851 852 void InstFcmp::dump(const Cfg *Func) const { 853 if (!BuildDefs::dump()) 854 return; 855 Ostream &Str = Func->getContext()->getStrDump(); 856 dumpDest(Func); 857 Str << " = fcmp " << InstFcmpAttributes[getCondition()].DisplayString << " " 858 << getSrc(0)->getType() << " "; 859 dumpSources(Func); 860 } 861 862 void InstLoad::dump(const Cfg *Func) const { 863 if (!BuildDefs::dump()) 864 return; 865 Ostream &Str = Func->getContext()->getStrDump(); 866 dumpDest(Func); 867 Type Ty = getDest()->getType(); 868 Str << " = load " << Ty << ", " << Ty << "* "; 869 dumpSources(Func); 870 Str << ", align " << typeAlignInBytes(Ty); 871 } 872 873 void InstStore::dump(const Cfg *Func) const { 874 if (!BuildDefs::dump()) 875 return; 876 Ostream &Str = Func->getContext()->getStrDump(); 877 Type Ty = getData()->getType(); 878 dumpDest(Func); 879 if (Dest) 880 Str << " = "; 881 Str << "store " << Ty << " "; 882 getData()->dump(Func); 883 Str << ", " << Ty << "* "; 884 getAddr()->dump(Func); 885 Str << ", align " << typeAlignInBytes(Ty); 886 if (getRmwBeacon()) { 887 Str << ", beacon "; 888 getRmwBeacon()->dump(Func); 889 } 890 } 891 892 void InstSwitch::dump(const Cfg *Func) const { 893 if (!BuildDefs::dump()) 894 return; 895 Ostream &Str = Func->getContext()->getStrDump(); 896 Type Ty = getComparison()->getType(); 897 Str << "switch " << Ty << " "; 898 getSrc(0)->dump(Func); 899 Str << ", label %" << getLabelDefault()->getName() << " [\n"; 900 for (SizeT I = 0; I < getNumCases(); ++I) { 901 Str << " " << Ty << " " << static_cast<int64_t>(getValue(I)) 902 << ", label %" << getLabel(I)->getName() << "\n"; 903 } 904 Str << " ]"; 905 } 906 907 void InstPhi::dump(const Cfg *Func) const { 908 if (!BuildDefs::dump()) 909 return; 910 Ostream &Str = Func->getContext()->getStrDump(); 911 dumpDest(Func); 912 Str << " = phi " << getDest()->getType() << " "; 913 for (SizeT I = 0; I < getSrcSize(); ++I) { 914 if (I > 0) 915 Str << ", "; 916 Str << "[ "; 917 getSrc(I)->dump(Func); 918 Str << ", %" << Labels[I]->getName() << " ]"; 919 } 920 } 921 922 void InstRet::dump(const Cfg *Func) const { 923 if (!BuildDefs::dump()) 924 return; 925 Ostream &Str = Func->getContext()->getStrDump(); 926 Type Ty = hasRetValue() ? getRetValue()->getType() : IceType_void; 927 Str << "ret " << Ty; 928 if (hasRetValue()) { 929 Str << " "; 930 dumpSources(Func); 931 } 932 } 933 934 void InstSelect::dump(const Cfg *Func) const { 935 if (!BuildDefs::dump()) 936 return; 937 Ostream &Str = Func->getContext()->getStrDump(); 938 dumpDest(Func); 939 Operand *Condition = getCondition(); 940 Operand *TrueOp = getTrueOperand(); 941 Operand *FalseOp = getFalseOperand(); 942 Str << " = select " << Condition->getType() << " "; 943 Condition->dump(Func); 944 Str << ", " << TrueOp->getType() << " "; 945 TrueOp->dump(Func); 946 Str << ", " << FalseOp->getType() << " "; 947 FalseOp->dump(Func); 948 } 949 950 void InstUnreachable::dump(const Cfg *Func) const { 951 if (!BuildDefs::dump()) 952 return; 953 Ostream &Str = Func->getContext()->getStrDump(); 954 Str << "unreachable"; 955 } 956 957 void InstBundleLock::emit(const Cfg *Func) const { 958 if (!BuildDefs::dump()) 959 return; 960 Ostream &Str = Func->getContext()->getStrEmit(); 961 Str << "\t.bundle_lock"; 962 switch (BundleOption) { 963 case Opt_None: 964 break; 965 case Opt_AlignToEnd: 966 Str << "\t" 967 "align_to_end"; 968 break; 969 case Opt_PadToEnd: 970 Str << "\t" 971 "align_to_end /* pad_to_end */"; 972 break; 973 } 974 Str << "\n"; 975 } 976 977 void InstBundleLock::dump(const Cfg *Func) const { 978 if (!BuildDefs::dump()) 979 return; 980 Ostream &Str = Func->getContext()->getStrDump(); 981 Str << "bundle_lock"; 982 switch (BundleOption) { 983 case Opt_None: 984 break; 985 case Opt_AlignToEnd: 986 Str << " align_to_end"; 987 break; 988 case Opt_PadToEnd: 989 Str << " pad_to_end"; 990 break; 991 } 992 } 993 994 void InstBundleUnlock::emit(const Cfg *Func) const { 995 if (!BuildDefs::dump()) 996 return; 997 Ostream &Str = Func->getContext()->getStrEmit(); 998 Str << "\t.bundle_unlock"; 999 Str << "\n"; 1000 } 1001 1002 void InstBundleUnlock::dump(const Cfg *Func) const { 1003 if (!BuildDefs::dump()) 1004 return; 1005 Ostream &Str = Func->getContext()->getStrDump(); 1006 Str << "bundle_unlock"; 1007 } 1008 1009 void InstFakeDef::emit(const Cfg *Func) const { 1010 if (!BuildDefs::dump()) 1011 return; 1012 // Go ahead and "emit" these for now, since they are relatively rare. 1013 Ostream &Str = Func->getContext()->getStrEmit(); 1014 Str << "\t# "; 1015 getDest()->emit(Func); 1016 Str << " = def.pseudo"; 1017 if (getSrcSize() > 0) 1018 Str << " "; 1019 emitSources(Func); 1020 Str << "\n"; 1021 } 1022 1023 void InstFakeDef::dump(const Cfg *Func) const { 1024 if (!BuildDefs::dump()) 1025 return; 1026 Ostream &Str = Func->getContext()->getStrDump(); 1027 dumpDest(Func); 1028 Str << " = def.pseudo "; 1029 dumpSources(Func); 1030 } 1031 1032 void InstFakeUse::emit(const Cfg *Func) const { (void)Func; } 1033 1034 void InstFakeUse::dump(const Cfg *Func) const { 1035 if (!BuildDefs::dump()) 1036 return; 1037 Ostream &Str = Func->getContext()->getStrDump(); 1038 Str << "use.pseudo "; 1039 dumpSources(Func); 1040 } 1041 1042 void InstFakeKill::emit(const Cfg *Func) const { (void)Func; } 1043 1044 void InstFakeKill::dump(const Cfg *Func) const { 1045 if (!BuildDefs::dump()) 1046 return; 1047 Ostream &Str = Func->getContext()->getStrDump(); 1048 if (Linked->isDeleted()) 1049 Str << "// "; 1050 Str << "kill.pseudo scratch_regs"; 1051 } 1052 1053 void InstShuffleVector::dump(const Cfg *Func) const { 1054 if (!BuildDefs::dump()) 1055 return; 1056 Ostream &Str = Func->getContext()->getStrDump(); 1057 Str << "shufflevector "; 1058 dumpDest(Func); 1059 Str << " = "; 1060 dumpSources(Func); 1061 for (SizeT I = 0; I < NumIndexes; ++I) { 1062 Str << ", "; 1063 Indexes[I]->dump(Func); 1064 } 1065 Str << "\n"; 1066 } 1067 1068 void InstJumpTable::dump(const Cfg *Func) const { 1069 if (!BuildDefs::dump()) 1070 return; 1071 Ostream &Str = Func->getContext()->getStrDump(); 1072 Str << "jump table ["; 1073 for (SizeT I = 0; I < NumTargets; ++I) 1074 Str << "\n " << Targets[I]->getName(); 1075 Str << "\n ]"; 1076 } 1077 1078 void InstTarget::dump(const Cfg *Func) const { 1079 if (!BuildDefs::dump()) 1080 return; 1081 Ostream &Str = Func->getContext()->getStrDump(); 1082 Str << "[TARGET] "; 1083 Inst::dump(Func); 1084 } 1085 1086 InstBreakpoint::InstBreakpoint(Cfg *Func) 1087 : InstHighLevel(Func, Inst::Breakpoint, 0, nullptr) {} 1088 1089 void InstIcmp::reverseConditionAndOperands() { 1090 Condition = InstIcmpAttributes[Condition].Reverse; 1091 std::swap(Srcs[0], Srcs[1]); 1092 } 1093 1094 bool checkForRedundantAssign(const Variable *Dest, const Operand *Source) { 1095 const auto *SrcVar = llvm::dyn_cast<const Variable>(Source); 1096 if (SrcVar == nullptr) 1097 return false; 1098 if (Dest->hasReg() && Dest->getRegNum() == SrcVar->getRegNum()) { 1099 // TODO: On x86-64, instructions like "mov eax, eax" are used to clear the 1100 // upper 32 bits of rax. We need to recognize and preserve these. 1101 return true; 1102 } 1103 if (!Dest->hasReg() && !SrcVar->hasReg()) { 1104 if (!Dest->hasStackOffset() || !SrcVar->hasStackOffset()) { 1105 // If called before stack slots have been assigned (i.e. as part of the 1106 // dump() routine), conservatively return false. 1107 return false; 1108 } 1109 if (Dest->getStackOffset() != SrcVar->getStackOffset()) { 1110 return false; 1111 } 1112 return true; 1113 } 1114 // For a "v=t" assignment where t has a register, v has a stack slot, and v 1115 // has a LinkedTo stack root, and v and t share the same LinkedTo root, return 1116 // true. This is because this assignment is effectively reassigning the same 1117 // value to the original LinkedTo stack root. 1118 if (SrcVar->hasReg() && Dest->hasStackOffset() && 1119 Dest->getLinkedToStackRoot() != nullptr && 1120 Dest->getLinkedToRoot() == SrcVar->getLinkedToRoot()) { 1121 return true; 1122 } 1123 return false; 1124 } 1125 1126 } // end of namespace Ice 1127