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