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