src/IceInst.h

   1 //===- subzero/src/IceInst.h - High-level instructions ----------*- C++ -*-===//
   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 /// This file declares the Inst class and its target-independent
  12 /// subclasses, which represent the high-level Vanilla ICE instructions
  13 /// and map roughly 1:1 to LLVM instructions.
  14 ///
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef SUBZERO_SRC_ICEINST_H
  18 #define SUBZERO_SRC_ICEINST_H
  19
  20 #include "IceCfg.h"
  21 #include "IceDefs.h"
  22 #include "IceInst.def"
  23 #include "IceIntrinsics.h"
  24 #include "IceTypes.h"
  25
  26 // TODO: The Cfg structure, and instructions in particular, need to be
  27 // validated for things like valid operand types, valid branch targets, proper
  28 // ordering of Phi and non-Phi instructions, etc. Most of the validity checking
  29 // will be done in the bitcode reader. We need a list of everything that should
  30 // be validated, and tests for each.
  31
  32 namespace Ice {
  33
  34 /// Base instruction class for ICE. Inst has two subclasses: InstHighLevel and
  35 /// InstTarget. High-level ICE instructions inherit from InstHighLevel, and
  36 /// low-level (target-specific) ICE instructions inherit from InstTarget.
  37 class Inst : public llvm::ilist_node<Inst> {
  38   Inst() = delete;
  39   Inst(const Inst &) = delete;
  40   Inst &operator=(const Inst &) = delete;
  41
  42 public:
  43   enum InstKind {
  44     // Arbitrary (alphabetical) order, except put Unreachable first.
  45     Unreachable,
  46     Alloca,
  47     Arithmetic,
  48     Br,
  49     Call,
  50     Cast,
  51     ExtractElement,
  52     Fcmp,
  53     Icmp,
  54     IntrinsicCall,
  55     InsertElement,
  56     Load,
  57     Phi,
  58     Ret,
  59     Select,
  60     Store,
  61     Switch,
  62     Assign,       // not part of LLVM/PNaCl bitcode
  63     BundleLock,   // not part of LLVM/PNaCl bitcode
  64     BundleUnlock, // not part of LLVM/PNaCl bitcode
  65     FakeDef,      // not part of LLVM/PNaCl bitcode
  66     FakeUse,      // not part of LLVM/PNaCl bitcode
  67     FakeKill,     // not part of LLVM/PNaCl bitcode
  68     JumpTable,    // not part of LLVM/PNaCl bitcode
  69     // Anything >= Target is an InstTarget subclass. Note that the value-spaces
  70     // are shared across targets. To avoid confusion over the definition of
  71     // shared values, an object specific to one target should never be passed
  72     // to a different target.
  73     Target,
  74     Target_Max = std::numeric_limits<uint8_t>::max(),
  75   };
  76   static_assert(Target <= Target_Max, "Must not be above max.");
  77   InstKind getKind() const { return Kind; }
  78
  79   InstNumberT getNumber() const { return Number; }
  80   void renumber(Cfg *Func);
  81   enum {
  82     NumberDeleted = -1,
  83     NumberSentinel = 0,
  84     NumberInitial = 2,
  85     NumberExtended = NumberInitial - 1
  86   };
  87
  88   bool isDeleted() const { return Deleted; }
  89   void setDeleted() { Deleted = true; }
  90   void setDead(bool Value = true) { Dead = Value; }
  91   void deleteIfDead();
  92
  93   bool hasSideEffects() const { return HasSideEffects; }
  94
  95   bool isDestRedefined() const { return IsDestRedefined; }
  96   void setDestRedefined() { IsDestRedefined = true; }
  97
  98   Variable *getDest() const { return Dest; }
  99
 100   SizeT getSrcSize() const { return NumSrcs; }
 101   Operand *getSrc(SizeT I) const {
 102     assert(I < getSrcSize());
 103     return Srcs[I];
 104   }
 105
 106   bool isLastUse(const Operand *Src) const;
 107   void spliceLivenessInfo(Inst *OrigInst, Inst *SpliceAssn);
 108
 109   /// Returns a list of out-edges corresponding to a terminator instruction,
 110   /// which is the last instruction of the block. The list must not contain
 111   /// duplicates.
 112   virtual NodeList getTerminatorEdges() const {
 113     // All valid terminator instructions override this method. For the default
 114     // implementation, we assert in case some CfgNode is constructed without a
 115     // terminator instruction at the end.
 116     llvm_unreachable(
 117         "getTerminatorEdges() called on a non-terminator instruction");
 118     return NodeList();
 119   }
 120   virtual bool isUnconditionalBranch() const { return false; }
 121   /// If the instruction is a branch-type instruction with OldNode as a target,
 122   /// repoint it to NewNode and return true, otherwise return false. Repoint all
 123   /// instances of OldNode as a target.
 124   virtual bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) {
 125     (void)OldNode;
 126     (void)NewNode;
 127     return false;
 128   }
 129
 130   virtual bool isSimpleAssign() const { return false; }
 131
 132   void livenessLightweight(Cfg *Func, LivenessBV &Live);
 133   /// Calculates liveness for this instruction. Returns true if this instruction
 134   /// is (tentatively) still live and should be retained, and false if this
 135   /// instruction is (tentatively) dead and should be deleted. The decision is
 136   /// tentative until the liveness dataflow algorithm has converged, and then a
 137   /// separate pass permanently deletes dead instructions.
 138   bool liveness(InstNumberT InstNumber, LivenessBV &Live, Liveness *Liveness,
 139                 LiveBeginEndMap *LiveBegin, LiveBeginEndMap *LiveEnd);
 140
 141   /// Get the number of native instructions that this instruction ultimately
 142   /// emits. By default, high-level instructions don't result in any native
 143   /// instructions, and a target-specific instruction results in a single native
 144   /// instruction.
 145   virtual uint32_t getEmitInstCount() const { return 0; }
 146   // TODO(stichnot): Change Inst back to abstract once the g++ build issue is
 147   // fixed. llvm::ilist<Ice::Inst> doesn't work under g++ because the
 148   // resize(size_t, Ice::Inst) method is incorrectly declared and thus doesn't
 149   // allow the abstract class Ice::Inst. The method should be declared
 150   // resize(size_t, const Ice::Inst &). virtual void emit(const Cfg *Func)
 151   // const = 0; virtual void emitIAS(const Cfg *Func) const = 0;
 152   virtual void emit(const Cfg *) const {
 153     llvm_unreachable("emit on abstract class");
 154   }
 155   virtual void emitIAS(const Cfg *Func) const { emit(Func); }
 156   virtual void dump(const Cfg *Func) const;
 157   virtual void dumpExtras(const Cfg *Func) const;
 158   void dumpDecorated(const Cfg *Func) const;
 159   void emitSources(const Cfg *Func) const;
 160   void dumpSources(const Cfg *Func) const;
 161   void dumpDest(const Cfg *Func) const;
 162   virtual bool isRedundantAssign() const { return false; }
 163
 164   ~Inst() = default;
 165
 166 protected:
 167   Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest);
 168   void addSource(Operand *Src) {
 169     assert(Src);
 170     assert(NumSrcs < MaxSrcs);
 171     Srcs[NumSrcs++] = Src;
 172   }
 173   void setLastUse(SizeT VarIndex) {
 174     if (VarIndex < CHAR_BIT * sizeof(LiveRangesEnded))
 175       LiveRangesEnded |= (((LREndedBits)1u) << VarIndex);
 176   }
 177   void resetLastUses() { LiveRangesEnded = 0; }
 178   /// The destroy() method lets the instruction cleanly release any memory that
 179   /// was allocated via the Cfg's allocator.
 180   virtual void destroy(Cfg *Func) { Func->deallocateArrayOf<Operand *>(Srcs); }
 181
 182   const InstKind Kind;
 183   /// Number is the instruction number for describing live ranges.
 184   InstNumberT Number;
 185   /// Deleted means irrevocably deleted.
 186   bool Deleted = false;
 187   /// Dead means one of two things depending on context: (1) pending deletion
 188   /// after liveness analysis converges, or (2) marked for deletion during
 189   /// lowering due to a folded bool operation.
 190   bool Dead = false;
 191   /// HasSideEffects means the instruction is something like a function call or
 192   /// a volatile load that can't be removed even if its Dest variable is not
 193   /// live.
 194   bool HasSideEffects = false;
 195   /// IsDestRedefined indicates that this instruction is not the first
 196   /// definition of Dest in the basic block.  The effect is that liveness
 197   /// analysis shouldn't consider this instruction to be the start of Dest's
 198   /// live range; rather, there is some other instruction earlier in the basic
 199   /// block with the same Dest.  This is maintained because liveness analysis
 200   /// has an invariant (primarily for performance reasons) that any Variable's
 201   /// live range recorded in a basic block has at most one start and at most one
 202   /// end.
 203   bool IsDestRedefined = false;
 204
 205   Variable *Dest;
 206   const SizeT MaxSrcs; // only used for assert
 207   SizeT NumSrcs = 0;
 208   Operand **Srcs;
 209
 210   /// LiveRangesEnded marks which Variables' live ranges end in this
 211   /// instruction. An instruction can have an arbitrary number of source
 212   /// operands (e.g. a call instruction), and each source operand can contain 0
 213   /// or 1 Variable (and target-specific operands could contain more than 1
 214   /// Variable). All the variables in an instruction are conceptually flattened
 215   /// and each variable is mapped to one bit position of the LiveRangesEnded bit
 216   /// vector. Only the first CHAR_BIT * sizeof(LREndedBits) variables are
 217   /// tracked this way.
 218   using LREndedBits = uint32_t; // only first 32 src operands tracked, sorry
 219   LREndedBits LiveRangesEnded;
 220 };
 221
 222 class InstHighLevel : public Inst {
 223   InstHighLevel() = delete;
 224   InstHighLevel(const InstHighLevel &) = delete;
 225   InstHighLevel &operator=(const InstHighLevel &) = delete;
 226
 227 protected:
 228   InstHighLevel(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest)
 229       : Inst(Func, Kind, MaxSrcs, Dest) {}
 230   void emit(const Cfg * /*Func*/) const override {
 231     llvm_unreachable("emit() called on a non-lowered instruction");
 232   }
 233   void emitIAS(const Cfg * /*Func*/) const override {
 234     llvm_unreachable("emitIAS() called on a non-lowered instruction");
 235   }
 236 };
 237
 238 /// Alloca instruction. This captures the size in bytes as getSrc(0), and the
 239 /// required alignment in bytes. The alignment must be either 0 (no alignment
 240 /// required) or a power of 2.
 241 class InstAlloca : public InstHighLevel {
 242   InstAlloca() = delete;
 243   InstAlloca(const InstAlloca &) = delete;
 244   InstAlloca &operator=(const InstAlloca &) = delete;
 245
 246 public:
 247   static InstAlloca *create(Cfg *Func, Operand *ByteCount,
 248                             uint32_t AlignInBytes, Variable *Dest) {
 249     return new (Func->allocate<InstAlloca>())
 250         InstAlloca(Func, ByteCount, AlignInBytes, Dest);
 251   }
 252   uint32_t getAlignInBytes() const { return AlignInBytes; }
 253   Operand *getSizeInBytes() const { return getSrc(0); }
 254   bool getKnownFrameOffset() const { return KnownFrameOffset; }
 255   void setKnownFrameOffset() { KnownFrameOffset = true; }
 256   void dump(const Cfg *Func) const override;
 257   static bool classof(const Inst *Inst) { return Inst->getKind() == Alloca; }
 258
 259 private:
 260   InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes,
 261              Variable *Dest);
 262
 263   const uint32_t AlignInBytes;
 264   bool KnownFrameOffset = false;
 265 };
 266
 267 /// Binary arithmetic instruction. The source operands are captured in getSrc(0)
 268 /// and getSrc(1).
 269 class InstArithmetic : public InstHighLevel {
 270   InstArithmetic() = delete;
 271   InstArithmetic(const InstArithmetic &) = delete;
 272   InstArithmetic &operator=(const InstArithmetic &) = delete;
 273
 274 public:
 275   enum OpKind {
 276 #define X(tag, str, commutative) tag,
 277     ICEINSTARITHMETIC_TABLE
 278 #undef X
 279         _num
 280   };
 281
 282   static InstArithmetic *create(Cfg *Func, OpKind Op, Variable *Dest,
 283                                 Operand *Source1, Operand *Source2) {
 284     return new (Func->allocate<InstArithmetic>())
 285         InstArithmetic(Func, Op, Dest, Source1, Source2);
 286   }
 287   OpKind getOp() const { return Op; }
 288   static const char *getOpName(OpKind Op);
 289   bool isCommutative() const;
 290   void dump(const Cfg *Func) const override;
 291   static bool classof(const Inst *Inst) {
 292     return Inst->getKind() == Arithmetic;
 293   }
 294
 295 private:
 296   InstArithmetic(Cfg *Func, OpKind Op, Variable *Dest, Operand *Source1,
 297                  Operand *Source2);
 298
 299   const OpKind Op;
 300 };
 301
 302 /// Assignment instruction. The source operand is captured in getSrc(0). This is
 303 /// not part of the LLVM bitcode, but is a useful abstraction for some of the
 304 /// lowering. E.g., if Phi instruction lowering happens before target lowering,
 305 /// or for representing an Inttoptr instruction, or as an intermediate step for
 306 /// lowering a Load instruction.
 307 class InstAssign : public InstHighLevel {
 308   InstAssign() = delete;
 309   InstAssign(const InstAssign &) = delete;
 310   InstAssign &operator=(const InstAssign &) = delete;
 311
 312 public:
 313   static InstAssign *create(Cfg *Func, Variable *Dest, Operand *Source) {
 314     return new (Func->allocate<InstAssign>()) InstAssign(Func, Dest, Source);
 315   }
 316   bool isSimpleAssign() const override { return true; }
 317   void dump(const Cfg *Func) const override;
 318   static bool classof(const Inst *Inst) { return Inst->getKind() == Assign; }
 319
 320 private:
 321   InstAssign(Cfg *Func, Variable *Dest, Operand *Source);
 322 };
 323
 324 /// Branch instruction. This represents both conditional and unconditional
 325 /// branches.
 326 class InstBr : public InstHighLevel {
 327   InstBr() = delete;
 328   InstBr(const InstBr &) = delete;
 329   InstBr &operator=(const InstBr &) = delete;
 330
 331 public:
 332   /// Create a conditional branch. If TargetTrue==TargetFalse, it is optimized
 333   /// to an unconditional branch.
 334   static InstBr *create(Cfg *Func, Operand *Source, CfgNode *TargetTrue,
 335                         CfgNode *TargetFalse) {
 336     return new (Func->allocate<InstBr>())
 337         InstBr(Func, Source, TargetTrue, TargetFalse);
 338   }
 339   /// Create an unconditional branch.
 340   static InstBr *create(Cfg *Func, CfgNode *Target) {
 341     return new (Func->allocate<InstBr>()) InstBr(Func, Target);
 342   }
 343   bool isUnconditional() const { return getTargetTrue() == nullptr; }
 344   Operand *getCondition() const {
 345     assert(!isUnconditional());
 346     return getSrc(0);
 347   }
 348   CfgNode *getTargetTrue() const { return TargetTrue; }
 349   CfgNode *getTargetFalse() const { return TargetFalse; }
 350   CfgNode *getTargetUnconditional() const {
 351     assert(isUnconditional());
 352     return getTargetFalse();
 353   }
 354   NodeList getTerminatorEdges() const override;
 355   bool isUnconditionalBranch() const override { return isUnconditional(); }
 356   bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) override;
 357   void dump(const Cfg *Func) const override;
 358   static bool classof(const Inst *Inst) { return Inst->getKind() == Br; }
 359
 360 private:
 361   /// Conditional branch
 362   InstBr(Cfg *Func, Operand *Source, CfgNode *TargetTrue, CfgNode *TargetFalse);
 363   /// Unconditional branch
 364   InstBr(Cfg *Func, CfgNode *Target);
 365
 366   CfgNode *TargetFalse; /// Doubles as unconditional branch target
 367   CfgNode *TargetTrue;  /// nullptr if unconditional branch
 368 };
 369
 370 /// Call instruction. The call target is captured as getSrc(0), and arg I is
 371 /// captured as getSrc(I+1).
 372 class InstCall : public InstHighLevel {
 373   InstCall() = delete;
 374   InstCall(const InstCall &) = delete;
 375   InstCall &operator=(const InstCall &) = delete;
 376
 377 public:
 378   static InstCall *create(Cfg *Func, SizeT NumArgs, Variable *Dest,
 379                           Operand *CallTarget, bool HasTailCall) {
 380     /// Set HasSideEffects to true so that the call instruction can't be
 381     /// dead-code eliminated. IntrinsicCalls can override this if the particular
 382     /// intrinsic is deletable and has no side-effects.
 383     const bool HasSideEffects = true;
 384     const InstKind Kind = Inst::Call;
 385     return new (Func->allocate<InstCall>()) InstCall(
 386         Func, NumArgs, Dest, CallTarget, HasTailCall, HasSideEffects, Kind);
 387   }
 388   void addArg(Operand *Arg) { addSource(Arg); }
 389   Operand *getCallTarget() const { return getSrc(0); }
 390   Operand *getArg(SizeT I) const { return getSrc(I + 1); }
 391   SizeT getNumArgs() const { return getSrcSize() - 1; }
 392   bool isTailcall() const { return HasTailCall; }
 393   void dump(const Cfg *Func) const override;
 394   static bool classof(const Inst *Inst) { return Inst->getKind() == Call; }
 395   Type getReturnType() const;
 396
 397 protected:
 398   InstCall(Cfg *Func, SizeT NumArgs, Variable *Dest, Operand *CallTarget,
 399            bool HasTailCall, bool HasSideEff, InstKind Kind)
 400       : InstHighLevel(Func, Kind, NumArgs + 1, Dest), HasTailCall(HasTailCall) {
 401     HasSideEffects = HasSideEff;
 402     addSource(CallTarget);
 403   }
 404
 405 private:
 406   bool HasTailCall;
 407 };
 408
 409 /// Cast instruction (a.k.a. conversion operation).
 410 class InstCast : public InstHighLevel {
 411   InstCast() = delete;
 412   InstCast(const InstCast &) = delete;
 413   InstCast &operator=(const InstCast &) = delete;
 414
 415 public:
 416   enum OpKind {
 417 #define X(tag, str) tag,
 418     ICEINSTCAST_TABLE
 419 #undef X
 420         _num
 421   };
 422
 423   static const char *getCastName(OpKind Kind);
 424
 425   static InstCast *create(Cfg *Func, OpKind CastKind, Variable *Dest,
 426                           Operand *Source) {
 427     return new (Func->allocate<InstCast>())
 428         InstCast(Func, CastKind, Dest, Source);
 429   }
 430   OpKind getCastKind() const { return CastKind; }
 431   void dump(const Cfg *Func) const override;
 432   static bool classof(const Inst *Inst) { return Inst->getKind() == Cast; }
 433
 434 private:
 435   InstCast(Cfg *Func, OpKind CastKind, Variable *Dest, Operand *Source);
 436
 437   const OpKind CastKind;
 438 };
 439
 440 /// ExtractElement instruction.
 441 class InstExtractElement : public InstHighLevel {
 442   InstExtractElement() = delete;
 443   InstExtractElement(const InstExtractElement &) = delete;
 444   InstExtractElement &operator=(const InstExtractElement &) = delete;
 445
 446 public:
 447   static InstExtractElement *create(Cfg *Func, Variable *Dest, Operand *Source1,
 448                                     Operand *Source2) {
 449     return new (Func->allocate<InstExtractElement>())
 450         InstExtractElement(Func, Dest, Source1, Source2);
 451   }
 452
 453   void dump(const Cfg *Func) const override;
 454   static bool classof(const Inst *Inst) {
 455     return Inst->getKind() == ExtractElement;
 456   }
 457
 458 private:
 459   InstExtractElement(Cfg *Func, Variable *Dest, Operand *Source1,
 460                      Operand *Source2);
 461 };
 462
 463 /// Floating-point comparison instruction. The source operands are captured in
 464 /// getSrc(0) and getSrc(1).
 465 class InstFcmp : public InstHighLevel {
 466   InstFcmp() = delete;
 467   InstFcmp(const InstFcmp &) = delete;
 468   InstFcmp &operator=(const InstFcmp &) = delete;
 469
 470 public:
 471   enum FCond {
 472 #define X(tag, str) tag,
 473     ICEINSTFCMP_TABLE
 474 #undef X
 475         _num
 476   };
 477
 478   static InstFcmp *create(Cfg *Func, FCond Condition, Variable *Dest,
 479                           Operand *Source1, Operand *Source2) {
 480     return new (Func->allocate<InstFcmp>())
 481         InstFcmp(Func, Condition, Dest, Source1, Source2);
 482   }
 483   FCond getCondition() const { return Condition; }
 484   void dump(const Cfg *Func) const override;
 485   static bool classof(const Inst *Inst) { return Inst->getKind() == Fcmp; }
 486
 487 private:
 488   InstFcmp(Cfg *Func, FCond Condition, Variable *Dest, Operand *Source1,
 489            Operand *Source2);
 490
 491   const FCond Condition;
 492 };
 493
 494 /// Integer comparison instruction. The source operands are captured in
 495 /// getSrc(0) and getSrc(1).
 496 class InstIcmp : public InstHighLevel {
 497   InstIcmp() = delete;
 498   InstIcmp(const InstIcmp &) = delete;
 499   InstIcmp &operator=(const InstIcmp &) = delete;
 500
 501 public:
 502   enum ICond {
 503 #define X(tag, str) tag,
 504     ICEINSTICMP_TABLE
 505 #undef X
 506         _num
 507   };
 508
 509   static InstIcmp *create(Cfg *Func, ICond Condition, Variable *Dest,
 510                           Operand *Source1, Operand *Source2) {
 511     return new (Func->allocate<InstIcmp>())
 512         InstIcmp(Func, Condition, Dest, Source1, Source2);
 513   }
 514   ICond getCondition() const { return Condition; }
 515   void dump(const Cfg *Func) const override;
 516   static bool classof(const Inst *Inst) { return Inst->getKind() == Icmp; }
 517
 518 private:
 519   InstIcmp(Cfg *Func, ICond Condition, Variable *Dest, Operand *Source1,
 520            Operand *Source2);
 521
 522   const ICond Condition;
 523 };
 524
 525 /// InsertElement instruction.
 526 class InstInsertElement : public InstHighLevel {
 527   InstInsertElement() = delete;
 528   InstInsertElement(const InstInsertElement &) = delete;
 529   InstInsertElement &operator=(const InstInsertElement &) = delete;
 530
 531 public:
 532   static InstInsertElement *create(Cfg *Func, Variable *Dest, Operand *Source1,
 533                                    Operand *Source2, Operand *Source3) {
 534     return new (Func->allocate<InstInsertElement>())
 535         InstInsertElement(Func, Dest, Source1, Source2, Source3);
 536   }
 537
 538   void dump(const Cfg *Func) const override;
 539   static bool classof(const Inst *Inst) {
 540     return Inst->getKind() == InsertElement;
 541   }
 542
 543 private:
 544   InstInsertElement(Cfg *Func, Variable *Dest, Operand *Source1,
 545                     Operand *Source2, Operand *Source3);
 546 };
 547
 548 /// Call to an intrinsic function. The call target is captured as getSrc(0), and
 549 /// arg I is captured as getSrc(I+1).
 550 class InstIntrinsicCall : public InstCall {
 551   InstIntrinsicCall() = delete;
 552   InstIntrinsicCall(const InstIntrinsicCall &) = delete;
 553   InstIntrinsicCall &operator=(const InstIntrinsicCall &) = delete;
 554
 555 public:
 556   static InstIntrinsicCall *create(Cfg *Func, SizeT NumArgs, Variable *Dest,
 557                                    Operand *CallTarget,
 558                                    const Intrinsics::IntrinsicInfo &Info) {
 559     return new (Func->allocate<InstIntrinsicCall>())
 560         InstIntrinsicCall(Func, NumArgs, Dest, CallTarget, Info);
 561   }
 562   static bool classof(const Inst *Inst) {
 563     return Inst->getKind() == IntrinsicCall;
 564   }
 565
 566   Intrinsics::IntrinsicInfo getIntrinsicInfo() const { return Info; }
 567
 568 private:
 569   InstIntrinsicCall(Cfg *Func, SizeT NumArgs, Variable *Dest,
 570                     Operand *CallTarget, const Intrinsics::IntrinsicInfo &Info)
 571       : InstCall(Func, NumArgs, Dest, CallTarget, false, Info.HasSideEffects,
 572                  Inst::IntrinsicCall),
 573         Info(Info) {}
 574
 575   const Intrinsics::IntrinsicInfo Info;
 576 };
 577
 578 /// Load instruction. The source address is captured in getSrc(0).
 579 class InstLoad : public InstHighLevel {
 580   InstLoad() = delete;
 581   InstLoad(const InstLoad &) = delete;
 582   InstLoad &operator=(const InstLoad &) = delete;
 583
 584 public:
 585   static InstLoad *create(Cfg *Func, Variable *Dest, Operand *SourceAddr,
 586                           uint32_t Align = 1) {
 587     // TODO(kschimpf) Stop ignoring alignment specification.
 588     (void)Align;
 589     return new (Func->allocate<InstLoad>()) InstLoad(Func, Dest, SourceAddr);
 590   }
 591   Operand *getSourceAddress() const { return getSrc(0); }
 592   void dump(const Cfg *Func) const override;
 593   static bool classof(const Inst *Inst) { return Inst->getKind() == Load; }
 594
 595 private:
 596   InstLoad(Cfg *Func, Variable *Dest, Operand *SourceAddr);
 597 };
 598
 599 /// Phi instruction. For incoming edge I, the node is Labels[I] and the Phi
 600 /// source operand is getSrc(I).
 601 class InstPhi : public InstHighLevel {
 602   InstPhi() = delete;
 603   InstPhi(const InstPhi &) = delete;
 604   InstPhi &operator=(const InstPhi &) = delete;
 605
 606 public:
 607   static InstPhi *create(Cfg *Func, SizeT MaxSrcs, Variable *Dest) {
 608     return new (Func->allocate<InstPhi>()) InstPhi(Func, MaxSrcs, Dest);
 609   }
 610   void addArgument(Operand *Source, CfgNode *Label);
 611   Operand *getOperandForTarget(CfgNode *Target) const;
 612   CfgNode *getLabel(SizeT Index) const { return Labels[Index]; }
 613   void livenessPhiOperand(LivenessBV &Live, CfgNode *Target,
 614                           Liveness *Liveness);
 615   Inst *lower(Cfg *Func);
 616   void dump(const Cfg *Func) const override;
 617   static bool classof(const Inst *Inst) { return Inst->getKind() == Phi; }
 618
 619 private:
 620   InstPhi(Cfg *Func, SizeT MaxSrcs, Variable *Dest);
 621   void destroy(Cfg *Func) override {
 622     Func->deallocateArrayOf<CfgNode *>(Labels);
 623     Inst::destroy(Func);
 624   }
 625
 626   /// Labels[] duplicates the InEdges[] information in the enclosing CfgNode,
 627   /// but the Phi instruction is created before InEdges[] is available, so it's
 628   /// more complicated to share the list.
 629   CfgNode **Labels;
 630 };
 631
 632 /// Ret instruction. The return value is captured in getSrc(0), but if there is
 633 /// no return value (void-type function), then getSrcSize()==0 and
 634 /// hasRetValue()==false.
 635 class InstRet : public InstHighLevel {
 636   InstRet() = delete;
 637   InstRet(const InstRet &) = delete;
 638   InstRet &operator=(const InstRet &) = delete;
 639
 640 public:
 641   static InstRet *create(Cfg *Func, Operand *RetValue = nullptr) {
 642     return new (Func->allocate<InstRet>()) InstRet(Func, RetValue);
 643   }
 644   bool hasRetValue() const { return getSrcSize(); }
 645   Operand *getRetValue() const {
 646     assert(hasRetValue());
 647     return getSrc(0);
 648   }
 649   NodeList getTerminatorEdges() const override { return NodeList(); }
 650   void dump(const Cfg *Func) const override;
 651   static bool classof(const Inst *Inst) { return Inst->getKind() == Ret; }
 652
 653 private:
 654   InstRet(Cfg *Func, Operand *RetValue);
 655 };
 656
 657 /// Select instruction.  The condition, true, and false operands are captured.
 658 class InstSelect : public InstHighLevel {
 659   InstSelect() = delete;
 660   InstSelect(const InstSelect &) = delete;
 661   InstSelect &operator=(const InstSelect &) = delete;
 662
 663 public:
 664   static InstSelect *create(Cfg *Func, Variable *Dest, Operand *Condition,
 665                             Operand *SourceTrue, Operand *SourceFalse) {
 666     return new (Func->allocate<InstSelect>())
 667         InstSelect(Func, Dest, Condition, SourceTrue, SourceFalse);
 668   }
 669   Operand *getCondition() const { return getSrc(0); }
 670   Operand *getTrueOperand() const { return getSrc(1); }
 671   Operand *getFalseOperand() const { return getSrc(2); }
 672   void dump(const Cfg *Func) const override;
 673   static bool classof(const Inst *Inst) { return Inst->getKind() == Select; }
 674
 675 private:
 676   InstSelect(Cfg *Func, Variable *Dest, Operand *Condition, Operand *Source1,
 677              Operand *Source2);
 678 };
 679
 680 /// Store instruction. The address operand is captured, along with the data
 681 /// operand to be stored into the address.
 682 class InstStore : public InstHighLevel {
 683   InstStore() = delete;
 684   InstStore(const InstStore &) = delete;
 685   InstStore &operator=(const InstStore &) = delete;
 686
 687 public:
 688   static InstStore *create(Cfg *Func, Operand *Data, Operand *Addr,
 689                            uint32_t Align = 1) {
 690     // TODO(kschimpf) Stop ignoring alignment specification.
 691     (void)Align;
 692     return new (Func->allocate<InstStore>()) InstStore(Func, Data, Addr);
 693   }
 694   Operand *getAddr() const { return getSrc(1); }
 695   Operand *getData() const { return getSrc(0); }
 696   Variable *getRmwBeacon() const;
 697   void setRmwBeacon(Variable *Beacon);
 698   void dump(const Cfg *Func) const override;
 699   static bool classof(const Inst *Inst) { return Inst->getKind() == Store; }
 700
 701 private:
 702   InstStore(Cfg *Func, Operand *Data, Operand *Addr);
 703 };
 704
 705 /// Switch instruction. The single source operand is captured as getSrc(0).
 706 class InstSwitch : public InstHighLevel {
 707   InstSwitch() = delete;
 708   InstSwitch(const InstSwitch &) = delete;
 709   InstSwitch &operator=(const InstSwitch &) = delete;
 710
 711 public:
 712   static InstSwitch *create(Cfg *Func, SizeT NumCases, Operand *Source,
 713                             CfgNode *LabelDefault) {
 714     return new (Func->allocate<InstSwitch>())
 715         InstSwitch(Func, NumCases, Source, LabelDefault);
 716   }
 717   Operand *getComparison() const { return getSrc(0); }
 718   CfgNode *getLabelDefault() const { return LabelDefault; }
 719   SizeT getNumCases() const { return NumCases; }
 720   uint64_t getValue(SizeT I) const {
 721     assert(I < NumCases);
 722     return Values[I];
 723   }
 724   CfgNode *getLabel(SizeT I) const {
 725     assert(I < NumCases);
 726     return Labels[I];
 727   }
 728   void addBranch(SizeT CaseIndex, uint64_t Value, CfgNode *Label);
 729   NodeList getTerminatorEdges() const override;
 730   bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) override;
 731   void dump(const Cfg *Func) const override;
 732   static bool classof(const Inst *Inst) { return Inst->getKind() == Switch; }
 733
 734 private:
 735   InstSwitch(Cfg *Func, SizeT NumCases, Operand *Source, CfgNode *LabelDefault);
 736   void destroy(Cfg *Func) override {
 737     Func->deallocateArrayOf<uint64_t>(Values);
 738     Func->deallocateArrayOf<CfgNode *>(Labels);
 739     Inst::destroy(Func);
 740   }
 741
 742   CfgNode *LabelDefault;
 743   SizeT NumCases;   /// not including the default case
 744   uint64_t *Values; /// size is NumCases
 745   CfgNode **Labels; /// size is NumCases
 746 };
 747
 748 /// Unreachable instruction. This is a terminator instruction with no operands.
 749 class InstUnreachable : public InstHighLevel {
 750   InstUnreachable() = delete;
 751   InstUnreachable(const InstUnreachable &) = delete;
 752   InstUnreachable &operator=(const InstUnreachable &) = delete;
 753
 754 public:
 755   static InstUnreachable *create(Cfg *Func) {
 756     return new (Func->allocate<InstUnreachable>()) InstUnreachable(Func);
 757   }
 758   NodeList getTerminatorEdges() const override { return NodeList(); }
 759   void dump(const Cfg *Func) const override;
 760   static bool classof(const Inst *Inst) {
 761     return Inst->getKind() == Unreachable;
 762   }
 763
 764 private:
 765   explicit InstUnreachable(Cfg *Func);
 766 };
 767
 768 /// BundleLock instruction.  There are no operands. Contains an option
 769 /// indicating whether align_to_end is specified.
 770 class InstBundleLock : public InstHighLevel {
 771   InstBundleLock() = delete;
 772   InstBundleLock(const InstBundleLock &) = delete;
 773   InstBundleLock &operator=(const InstBundleLock &) = delete;
 774
 775 public:
 776   enum Option { Opt_None, Opt_AlignToEnd };
 777   static InstBundleLock *create(Cfg *Func, Option BundleOption) {
 778     return new (Func->allocate<InstBundleLock>())
 779         InstBundleLock(Func, BundleOption);
 780   }
 781   void emit(const Cfg *Func) const override;
 782   void emitIAS(const Cfg * /* Func */) const override {}
 783   void dump(const Cfg *Func) const override;
 784   Option getOption() const { return BundleOption; }
 785   static bool classof(const Inst *Inst) {
 786     return Inst->getKind() == BundleLock;
 787   }
 788
 789 private:
 790   Option BundleOption;
 791   InstBundleLock(Cfg *Func, Option BundleOption);
 792 };
 793
 794 /// BundleUnlock instruction. There are no operands.
 795 class InstBundleUnlock : public InstHighLevel {
 796   InstBundleUnlock() = delete;
 797   InstBundleUnlock(const InstBundleUnlock &) = delete;
 798   InstBundleUnlock &operator=(const InstBundleUnlock &) = delete;
 799
 800 public:
 801   static InstBundleUnlock *create(Cfg *Func) {
 802     return new (Func->allocate<InstBundleUnlock>()) InstBundleUnlock(Func);
 803   }
 804   void emit(const Cfg *Func) const override;
 805   void emitIAS(const Cfg * /* Func */) const override {}
 806   void dump(const Cfg *Func) const override;
 807   static bool classof(const Inst *Inst) {
 808     return Inst->getKind() == BundleUnlock;
 809   }
 810
 811 private:
 812   explicit InstBundleUnlock(Cfg *Func);
 813 };
 814
 815 /// FakeDef instruction. This creates a fake definition of a variable, which is
 816 /// how we represent the case when an instruction produces multiple results.
 817 /// This doesn't happen with high-level ICE instructions, but might with lowered
 818 /// instructions. For example, this would be a way to represent condition flags
 819 /// being modified by an instruction.
 820 ///
 821 /// It's generally useful to set the optional source operand to be the dest
 822 /// variable of the instruction that actually produces the FakeDef dest.
 823 /// Otherwise, the original instruction could be dead-code eliminated if its
 824 /// dest operand is unused, and therefore the FakeDef dest wouldn't be properly
 825 /// initialized.
 826 class InstFakeDef : public InstHighLevel {
 827   InstFakeDef() = delete;
 828   InstFakeDef(const InstFakeDef &) = delete;
 829   InstFakeDef &operator=(const InstFakeDef &) = delete;
 830
 831 public:
 832   static InstFakeDef *create(Cfg *Func, Variable *Dest,
 833                              Variable *Src = nullptr) {
 834     return new (Func->allocate<InstFakeDef>()) InstFakeDef(Func, Dest, Src);
 835   }
 836   void emit(const Cfg *Func) const override;
 837   void emitIAS(const Cfg * /* Func */) const override {}
 838   void dump(const Cfg *Func) const override;
 839   static bool classof(const Inst *Inst) { return Inst->getKind() == FakeDef; }
 840
 841 private:
 842   InstFakeDef(Cfg *Func, Variable *Dest, Variable *Src);
 843 };
 844
 845 /// FakeUse instruction. This creates a fake use of a variable, to keep the
 846 /// instruction that produces that variable from being dead-code eliminated.
 847 /// This is useful in a variety of lowering situations. The FakeUse instruction
 848 /// has no dest, so it can itself never be dead-code eliminated.
 849 class InstFakeUse : public InstHighLevel {
 850   InstFakeUse() = delete;
 851   InstFakeUse(const InstFakeUse &) = delete;
 852   InstFakeUse &operator=(const InstFakeUse &) = delete;
 853
 854 public:
 855   static InstFakeUse *create(Cfg *Func, Variable *Src) {
 856     return new (Func->allocate<InstFakeUse>()) InstFakeUse(Func, Src);
 857   }
 858   void emit(const Cfg *Func) const override;
 859   void emitIAS(const Cfg * /* Func */) const override {}
 860   void dump(const Cfg *Func) const override;
 861   static bool classof(const Inst *Inst) { return Inst->getKind() == FakeUse; }
 862
 863 private:
 864   InstFakeUse(Cfg *Func, Variable *Src);
 865 };
 866
 867 /// FakeKill instruction. This "kills" a set of variables by modeling a trivial
 868 /// live range at this instruction for each (implicit) variable. The primary use
 869 /// is to indicate that scratch registers are killed after a call, so that the
 870 /// register allocator won't assign a scratch register to a variable whose live
 871 /// range spans a call.
 872 ///
 873 /// The FakeKill instruction also holds a pointer to the instruction that kills
 874 /// the set of variables, so that if that linked instruction gets dead-code
 875 /// eliminated, the FakeKill instruction will as well.
 876 class InstFakeKill : public InstHighLevel {
 877   InstFakeKill() = delete;
 878   InstFakeKill(const InstFakeKill &) = delete;
 879   InstFakeKill &operator=(const InstFakeKill &) = delete;
 880
 881 public:
 882   static InstFakeKill *create(Cfg *Func, const Inst *Linked) {
 883     return new (Func->allocate<InstFakeKill>()) InstFakeKill(Func, Linked);
 884   }
 885   const Inst *getLinked() const { return Linked; }
 886   void emit(const Cfg *Func) const override;
 887   void emitIAS(const Cfg * /* Func */) const override {}
 888   void dump(const Cfg *Func) const override;
 889   static bool classof(const Inst *Inst) { return Inst->getKind() == FakeKill; }
 890
 891 private:
 892   InstFakeKill(Cfg *Func, const Inst *Linked);
 893
 894   /// This instruction is ignored if Linked->isDeleted() is true.
 895   const Inst *Linked;
 896 };
 897
 898 /// JumpTable instruction. This represents a jump table that will be stored in
 899 /// the .rodata section. This is used to track and repoint the target CfgNodes
 900 /// which may change, for example due to splitting for phi lowering.
 901 class InstJumpTable : public InstHighLevel {
 902   InstJumpTable() = delete;
 903   InstJumpTable(const InstJumpTable &) = delete;
 904   InstJumpTable &operator=(const InstJumpTable &) = delete;
 905
 906 public:
 907   static InstJumpTable *create(Cfg *Func, SizeT NumTargets, CfgNode *Default) {
 908     return new (Func->allocate<InstJumpTable>())
 909         InstJumpTable(Func, NumTargets, Default);
 910   }
 911   void addTarget(SizeT TargetIndex, CfgNode *Target) {
 912     assert(TargetIndex < NumTargets);
 913     Targets[TargetIndex] = Target;
 914   }
 915   bool repointEdges(CfgNode *OldNode, CfgNode *NewNode) override;
 916   SizeT getId() const { return Id; }
 917   SizeT getNumTargets() const { return NumTargets; }
 918   CfgNode *getTarget(SizeT I) const {
 919     assert(I < NumTargets);
 920     return Targets[I];
 921   }
 922   void dump(const Cfg *Func) const override;
 923   static bool classof(const Inst *Inst) { return Inst->getKind() == JumpTable; }
 924
 925   static IceString makeName(const IceString &FuncName, SizeT Id) {
 926     return ".L" + FuncName + "$jumptable$__" + std::to_string(Id);
 927   }
 928
 929 private:
 930   InstJumpTable(Cfg *Func, SizeT NumTargets, CfgNode *Default);
 931   void destroy(Cfg *Func) override {
 932     Func->deallocateArrayOf<CfgNode *>(Targets);
 933     Inst::destroy(Func);
 934   }
 935
 936   const SizeT Id;
 937   const SizeT NumTargets;
 938   CfgNode **Targets;
 939 };
 940
 941 /// The Target instruction is the base class for all target-specific
 942 /// instructions.
 943 class InstTarget : public Inst {
 944   InstTarget() = delete;
 945   InstTarget(const InstTarget &) = delete;
 946   InstTarget &operator=(const InstTarget &) = delete;
 947
 948 public:
 949   uint32_t getEmitInstCount() const override { return 1; }
 950   void dump(const Cfg *Func) const override;
 951   static bool classof(const Inst *Inst) { return Inst->getKind() >= Target; }
 952
 953 protected:
 954   InstTarget(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest)
 955       : Inst(Func, Kind, MaxSrcs, Dest) {
 956     assert(Kind >= Target);
 957     assert(Kind <= Target_Max);
 958   }
 959 };
 960
 961 bool checkForRedundantAssign(const Variable *Dest, const Operand *Source);
 962
 963 } // end of namespace Ice
 964
 965 namespace llvm {
 966
 967 /// Override the default ilist traits so that Inst's private ctor and deleted
 968 /// dtor aren't invoked.
 969 template <>
 970 struct ilist_traits<Ice::Inst> : public ilist_default_traits<Ice::Inst> {
 971   Ice::Inst *createSentinel() const {
 972     return static_cast<Ice::Inst *>(&Sentinel);
 973   }
 974   static void destroySentinel(Ice::Inst *) {}
 975   Ice::Inst *provideInitialHead() const { return createSentinel(); }
 976   Ice::Inst *ensureHead(Ice::Inst *) const { return createSentinel(); }
 977   static void noteHead(Ice::Inst *, Ice::Inst *) {}
 978   void deleteNode(Ice::Inst *) {}
 979
 980 private:
 981   mutable ilist_half_node<Ice::Inst> Sentinel;
 982 };
 983
 984 } // end of namespace llvm
 985
 986 #endif // SUBZERO_SRC_ICEINST_H