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 
Inst(Cfg * Func,InstKind Kind,SizeT MaxSrcs,Variable * Dest)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 
getInstName() const85 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.
renumber(Cfg * Func)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.
deleteIfDead()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.
isLastUse(const Operand * TestSrc) const140 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.
spliceLivenessInfo(Inst * OrigInst,Inst * SpliceAssn)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 
isMemoryWrite() const195 bool Inst::isMemoryWrite() const {
196   llvm::report_fatal_error("Attempt to call base Inst::isMemoryWrite() method");
197 }
198 
livenessLightweight(Cfg * Func,LivenessBV & Live)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 
liveness(InstNumberT InstNumber,LivenessBV & Live,Liveness * Liveness,LiveBeginEndMap * LiveBegin,LiveBeginEndMap * LiveEnd)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 
InstAlloca(Cfg * Func,Variable * Dest,Operand * ByteCount,uint32_t AlignInBytes)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 
InstArithmetic(Cfg * Func,OpKind Op,Variable * Dest,Operand * Source1,Operand * Source2)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 
getInstName() const288 const char *InstArithmetic::getInstName() const {
289   if (!BuildDefs::dump())
290     return "???";
291 
292   return InstArithmeticAttributes[getOp()].DisplayString;
293 }
294 
getOpName(OpKind Op)295 const char *InstArithmetic::getOpName(OpKind Op) {
296   return Op < InstArithmetic::_num ? InstArithmeticAttributes[Op].DisplayString
297                                    : "???";
298 }
299 
isCommutative() const300 bool InstArithmetic::isCommutative() const {
301   return InstArithmeticAttributes[getOp()].IsCommutative;
302 }
303 
InstAssign(Cfg * Func,Variable * Dest,Operand * Source)304 InstAssign::InstAssign(Cfg *Func, Variable *Dest, Operand *Source)
305     : InstHighLevel(Func, Inst::Assign, 1, Dest) {
306   addSource(Source);
307 }
308 
isVarAssign() const309 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.
InstBr(Cfg * Func,Operand * Source,CfgNode * TargetTrue_,CfgNode * TargetFalse_)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 
InstBr(Cfg * Func,CfgNode * Target)331 InstBr::InstBr(Cfg *Func, CfgNode *Target)
332     : InstHighLevel(Func, Inst::Br, 0, nullptr), TargetFalse(Target),
333       TargetTrue(nullptr) {}
334 
getTerminatorEdges() const335 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 
repointEdges(CfgNode * OldNode,CfgNode * NewNode)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 
InstCast(Cfg * Func,OpKind CastKind,Variable * Dest,Operand * Source)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 
InstExtractElement(Cfg * Func,Variable * Dest,Operand * Source1,Operand * Source2)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 
InstFcmp(Cfg * Func,FCond Condition,Variable * Dest,Operand * Source1,Operand * Source2)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 
InstIcmp(Cfg * Func,ICond Condition,Variable * Dest,Operand * Source1,Operand * Source2)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 
InstInsertElement(Cfg * Func,Variable * Dest,Operand * Source1,Operand * Source2,Operand * Source3)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 
InstLoad(Cfg * Func,Variable * Dest,Operand * SourceAddr)392 InstLoad::InstLoad(Cfg *Func, Variable *Dest, Operand *SourceAddr)
393     : InstHighLevel(Func, Inst::Load, 1, Dest) {
394   addSource(SourceAddr);
395 }
396 
InstPhi(Cfg * Func,SizeT MaxSrcs,Variable * Dest)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.
addArgument(Operand * Source,CfgNode * Label)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.
getOperandForTarget(CfgNode * Target) const414 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.
clearOperandForTarget(CfgNode * Target)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.
livenessPhiOperand(LivenessBV & Live,CfgNode * Target,Liveness * Liveness)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".
lower(Cfg * Func)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 
InstRet(Cfg * Func,Operand * RetValue)474 InstRet::InstRet(Cfg *Func, Operand *RetValue)
475     : InstHighLevel(Func, Ret, RetValue ? 1 : 0, nullptr) {
476   if (RetValue)
477     addSource(RetValue);
478 }
479 
InstSelect(Cfg * Func,Variable * Dest,Operand * Condition,Operand * SourceTrue,Operand * SourceFalse)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 
InstStore(Cfg * Func,Operand * Data,Operand * Addr)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 
getRmwBeacon() const497 Variable *InstStore::getRmwBeacon() const {
498   return llvm::dyn_cast<Variable>(getSrc(2));
499 }
500 
setRmwBeacon(Variable * Beacon)501 void InstStore::setRmwBeacon(Variable *Beacon) {
502   Dest = llvm::dyn_cast<Variable>(getData());
503   Srcs[2] = Beacon;
504 }
505 
InstSwitch(Cfg * Func,SizeT NumCases,Operand * Source,CfgNode * LabelDefault)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 
addBranch(SizeT CaseIndex,uint64_t Value,CfgNode * Label)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 
getTerminatorEdges() const526 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 
repointEdges(CfgNode * OldNode,CfgNode * NewNode)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 
InstUnreachable(Cfg * Func)559 InstUnreachable::InstUnreachable(Cfg *Func)
560     : InstHighLevel(Func, Inst::Unreachable, 0, nullptr) {}
561 
InstBundleLock(Cfg * Func,InstBundleLock::Option BundleOption)562 InstBundleLock::InstBundleLock(Cfg *Func, InstBundleLock::Option BundleOption)
563     : InstHighLevel(Func, Inst::BundleLock, 0, nullptr),
564       BundleOption(BundleOption) {}
565 
InstBundleUnlock(Cfg * Func)566 InstBundleUnlock::InstBundleUnlock(Cfg *Func)
567     : InstHighLevel(Func, Inst::BundleUnlock, 0, nullptr) {}
568 
InstFakeDef(Cfg * Func,Variable * Dest,Variable * Src)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 
InstFakeUse(Cfg * Func,Variable * Src,uint32_t Weight)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 
InstFakeKill(Cfg * Func,const Inst * Linked)583 InstFakeKill::InstFakeKill(Cfg *Func, const Inst *Linked)
584     : InstHighLevel(Func, Inst::FakeKill, 0, nullptr), Linked(Linked) {}
585 
InstShuffleVector(Cfg * Func,Variable * Dest,Operand * Src0,Operand * Src1)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 {
makeName(Cfg * Func,const SizeT Id)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 
InstJumpTable(Cfg * Func,SizeT NumTargets,CfgNode * Default)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 
repointEdges(CfgNode * OldNode,CfgNode * NewNode)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 
toJumpTableData(Assembler * Asm) const628 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 
getReturnType() const637 Type InstCall::getReturnType() const {
638   if (Dest == nullptr)
639     return IceType_void;
640   return Dest->getType();
641 }
642 
643 // ======================== Dump routines ======================== //
644 
dumpDecorated(const Cfg * Func) const645 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 
dump(const Cfg * Func) const666 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 
dumpExtras(const Cfg * Func) const675 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 
dumpSources(const Cfg * Func) const698 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 
emitSources(const Cfg * Func) const709 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 
dumpDest(const Cfg * Func) const720 void Inst::dumpDest(const Cfg *Func) const {
721   if (!BuildDefs::dump())
722     return;
723   if (getDest())
724     getDest()->dump(Func);
725 }
726 
dump(const Cfg * Func) const727 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 
dump(const Cfg * Func) const738 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 
dump(const Cfg * Func) const747 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 
dump(const Cfg * Func) const756 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 
dump(const Cfg * Func) const770 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 
getCastName(InstCast::OpKind Kind)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 
dump(const Cfg * Func) const802 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 
dump(const Cfg * Func) const813 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 
dump(const Cfg * Func) const823 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 
dump(const Cfg * Func) const836 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 
dump(const Cfg * Func) const852 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 
dump(const Cfg * Func) const862 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 
dump(const Cfg * Func) const873 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 
dump(const Cfg * Func) const892 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 
dump(const Cfg * Func) const907 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 
dump(const Cfg * Func) const922 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 
dump(const Cfg * Func) const934 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 
dump(const Cfg * Func) const950 void InstUnreachable::dump(const Cfg *Func) const {
951   if (!BuildDefs::dump())
952     return;
953   Ostream &Str = Func->getContext()->getStrDump();
954   Str << "unreachable";
955 }
956 
emit(const Cfg * Func) const957 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 
dump(const Cfg * Func) const977 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 
emit(const Cfg * Func) const994 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 
dump(const Cfg * Func) const1002 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 
emit(const Cfg * Func) const1009 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 
dump(const Cfg * Func) const1023 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 
emit(const Cfg * Func) const1032 void InstFakeUse::emit(const Cfg *Func) const { (void)Func; }
1033 
dump(const Cfg * Func) const1034 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 
emit(const Cfg * Func) const1042 void InstFakeKill::emit(const Cfg *Func) const { (void)Func; }
1043 
dump(const Cfg * Func) const1044 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 
dump(const Cfg * Func) const1053 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 
dump(const Cfg * Func) const1068 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 
dump(const Cfg * Func) const1078 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 
InstBreakpoint(Cfg * Func)1086 InstBreakpoint::InstBreakpoint(Cfg *Func)
1087     : InstHighLevel(Func, Inst::Breakpoint, 0, nullptr) {}
1088 
reverseConditionAndOperands()1089 void InstIcmp::reverseConditionAndOperands() {
1090   Condition = InstIcmpAttributes[Condition].Reverse;
1091   std::swap(Srcs[0], Srcs[1]);
1092 }
1093 
checkForRedundantAssign(const Variable * Dest,const Operand * Source)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