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