src/IceTargetLowering.cpp

   1 //===- subzero/src/IceTargetLowering.cpp - Basic lowering implementation --===//
   2 //
   3 //                        The Subzero Code Generator
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the skeleton of the TargetLowering class,
  11 // specifically invoking the appropriate lowering method for a given
  12 // instruction kind and driving global register allocation.  It also
  13 // implements the non-deleted instruction iteration in
  14 // LoweringContext.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "IceAssemblerARM32.h"
  19 #include "IceAssemblerX8632.h"
  20 #include "assembler_mips32.h"
  21 #include "IceCfg.h" // setError()
  22 #include "IceCfgNode.h"
  23 #include "IceGlobalInits.h"
  24 #include "IceOperand.h"
  25 #include "IceRegAlloc.h"
  26 #include "IceTargetLowering.h"
  27 #include "IceTargetLoweringARM32.h"
  28 #include "IceTargetLoweringMIPS32.h"
  29 #include "IceTargetLoweringX8632.h"
  30
  31 namespace Ice {
  32
  33 void LoweringContext::init(CfgNode *N) {
  34   Node = N;
  35   End = getNode()->getInsts().end();
  36   rewind();
  37   advanceForward(Next);
  38 }
  39
  40 void LoweringContext::rewind() {
  41   Begin = getNode()->getInsts().begin();
  42   Cur = Begin;
  43   skipDeleted(Cur);
  44   Next = Cur;
  45 }
  46
  47 void LoweringContext::insert(Inst *Inst) {
  48   getNode()->getInsts().insert(Next, Inst);
  49   LastInserted = Inst;
  50 }
  51
  52 void LoweringContext::skipDeleted(InstList::iterator &I) const {
  53   while (I != End && I->isDeleted())
  54     ++I;
  55 }
  56
  57 void LoweringContext::advanceForward(InstList::iterator &I) const {
  58   if (I != End) {
  59     ++I;
  60     skipDeleted(I);
  61   }
  62 }
  63
  64 Inst *LoweringContext::getLastInserted() const {
  65   assert(LastInserted);
  66   return LastInserted;
  67 }
  68
  69 TargetLowering *TargetLowering::createLowering(TargetArch Target, Cfg *Func) {
  70 #define SUBZERO_TARGET(X)                                                      \
  71   if (Target == Target_##X)                                                    \
  72     return Target##X::create(Func);
  73 #include "llvm/Config/SZTargets.def"
  74
  75   Func->setError("Unsupported target");
  76   return nullptr;
  77 }
  78
  79 TargetLowering::TargetLowering(Cfg *Func)
  80     : Func(Func), Ctx(Func->getContext()), HasComputedFrame(false),
  81       CallsReturnsTwice(false), StackAdjustment(0), NextLabelNumber(0),
  82       Context(), SnapshotStackAdjustment(0) {}
  83
  84 std::unique_ptr<Assembler> TargetLowering::createAssembler(TargetArch Target,
  85                                                            Cfg *Func) {
  86 #define SUBZERO_TARGET(X)                                                      \
  87   if (Target == Target_##X)                                                    \
  88     return std::unique_ptr<Assembler>(new X::Assembler##X());
  89 #include "llvm/Config/SZTargets.def"
  90
  91   Func->setError("Unsupported target assembler");
  92   return nullptr;
  93 }
  94
  95 void TargetLowering::doAddressOpt() {
  96   if (llvm::isa<InstLoad>(*Context.getCur()))
  97     doAddressOptLoad();
  98   else if (llvm::isa<InstStore>(*Context.getCur()))
  99     doAddressOptStore();
 100   Context.advanceCur();
 101   Context.advanceNext();
 102 }
 103
 104 void TargetLowering::doNopInsertion() {
 105   Inst *I = Context.getCur();
 106   bool ShouldSkip = llvm::isa<InstFakeUse>(I) || llvm::isa<InstFakeDef>(I) ||
 107                     llvm::isa<InstFakeKill>(I) || I->isRedundantAssign() ||
 108                     I->isDeleted();
 109   if (!ShouldSkip) {
 110     int Probability = Ctx->getFlags().getNopProbabilityAsPercentage();
 111     for (int I = 0; I < Ctx->getFlags().getMaxNopsPerInstruction(); ++I) {
 112       randomlyInsertNop(Probability / 100.0);
 113     }
 114   }
 115 }
 116
 117 // Lowers a single instruction according to the information in
 118 // Context, by checking the Context.Cur instruction kind and calling
 119 // the appropriate lowering method.  The lowering method should insert
 120 // target instructions at the Cur.Next insertion point, and should not
 121 // delete the Context.Cur instruction or advance Context.Cur.
 122 //
 123 // The lowering method may look ahead in the instruction stream as
 124 // desired, and lower additional instructions in conjunction with the
 125 // current one, for example fusing a compare and branch.  If it does,
 126 // it should advance Context.Cur to point to the next non-deleted
 127 // instruction to process, and it should delete any additional
 128 // instructions it consumes.
 129 void TargetLowering::lower() {
 130   assert(!Context.atEnd());
 131   Inst *Inst = Context.getCur();
 132   Inst->deleteIfDead();
 133   if (!Inst->isDeleted()) {
 134     // Mark the current instruction as deleted before lowering,
 135     // otherwise the Dest variable will likely get marked as non-SSA.
 136     // See Variable::setDefinition().
 137     Inst->setDeleted();
 138     switch (Inst->getKind()) {
 139     case Inst::Alloca:
 140       lowerAlloca(llvm::cast<InstAlloca>(Inst));
 141       break;
 142     case Inst::Arithmetic:
 143       lowerArithmetic(llvm::cast<InstArithmetic>(Inst));
 144       break;
 145     case Inst::Assign:
 146       lowerAssign(llvm::cast<InstAssign>(Inst));
 147       break;
 148     case Inst::Br:
 149       lowerBr(llvm::cast<InstBr>(Inst));
 150       break;
 151     case Inst::Call:
 152       lowerCall(llvm::cast<InstCall>(Inst));
 153       break;
 154     case Inst::Cast:
 155       lowerCast(llvm::cast<InstCast>(Inst));
 156       break;
 157     case Inst::ExtractElement:
 158       lowerExtractElement(llvm::cast<InstExtractElement>(Inst));
 159       break;
 160     case Inst::Fcmp:
 161       lowerFcmp(llvm::cast<InstFcmp>(Inst));
 162       break;
 163     case Inst::Icmp:
 164       lowerIcmp(llvm::cast<InstIcmp>(Inst));
 165       break;
 166     case Inst::InsertElement:
 167       lowerInsertElement(llvm::cast<InstInsertElement>(Inst));
 168       break;
 169     case Inst::IntrinsicCall: {
 170       InstIntrinsicCall *Call = llvm::cast<InstIntrinsicCall>(Inst);
 171       if (Call->getIntrinsicInfo().ReturnsTwice)
 172         setCallsReturnsTwice(true);
 173       lowerIntrinsicCall(Call);
 174       break;
 175     }
 176     case Inst::Load:
 177       lowerLoad(llvm::cast<InstLoad>(Inst));
 178       break;
 179     case Inst::Phi:
 180       lowerPhi(llvm::cast<InstPhi>(Inst));
 181       break;
 182     case Inst::Ret:
 183       lowerRet(llvm::cast<InstRet>(Inst));
 184       break;
 185     case Inst::Select:
 186       lowerSelect(llvm::cast<InstSelect>(Inst));
 187       break;
 188     case Inst::Store:
 189       lowerStore(llvm::cast<InstStore>(Inst));
 190       break;
 191     case Inst::Switch:
 192       lowerSwitch(llvm::cast<InstSwitch>(Inst));
 193       break;
 194     case Inst::Unreachable:
 195       lowerUnreachable(llvm::cast<InstUnreachable>(Inst));
 196       break;
 197     case Inst::BundleLock:
 198     case Inst::BundleUnlock:
 199     case Inst::FakeDef:
 200     case Inst::FakeUse:
 201     case Inst::FakeKill:
 202     case Inst::Target:
 203       // These are all Target instruction types and shouldn't be
 204       // encountered at this stage.
 205       Func->setError("Can't lower unsupported instruction type");
 206       break;
 207     }
 208
 209     postLower();
 210   }
 211
 212   Context.advanceCur();
 213   Context.advanceNext();
 214 }
 215
 216 // Drives register allocation, allowing all physical registers (except
 217 // perhaps for the frame pointer) to be allocated.  This set of
 218 // registers could potentially be parameterized if we want to restrict
 219 // registers e.g. for performance testing.
 220 void TargetLowering::regAlloc(RegAllocKind Kind) {
 221   TimerMarker T(TimerStack::TT_regAlloc, Func);
 222   LinearScan LinearScan(Func);
 223   RegSetMask RegInclude = RegSet_None;
 224   RegSetMask RegExclude = RegSet_None;
 225   RegInclude |= RegSet_CallerSave;
 226   RegInclude |= RegSet_CalleeSave;
 227   if (hasFramePointer())
 228     RegExclude |= RegSet_FramePointer;
 229   LinearScan.init(Kind);
 230   llvm::SmallBitVector RegMask = getRegisterSet(RegInclude, RegExclude);
 231   LinearScan.scan(RegMask, Ctx->getFlags().shouldRandomizeRegAlloc());
 232 }
 233
 234 void TargetLowering::inferTwoAddress() {
 235   // Find two-address non-SSA instructions where Dest==Src0, and set
 236   // the DestNonKillable flag to keep liveness analysis consistent.
 237   for (auto Inst = Context.getCur(), E = Context.getNext(); Inst != E; ++Inst) {
 238     if (Inst->isDeleted())
 239       continue;
 240     if (Variable *Dest = Inst->getDest()) {
 241       // TODO(stichnot): We may need to consider all source
 242       // operands, not just the first one, if using 3-address
 243       // instructions.
 244       if (Inst->getSrcSize() > 0 && Inst->getSrc(0) == Dest)
 245         Inst->setDestNonKillable();
 246     }
 247   }
 248 }
 249
 250 void TargetLowering::sortVarsByAlignment(VarList &Dest,
 251                                          const VarList &Source) const {
 252   Dest = Source;
 253   // Instead of std::sort, we could do a bucket sort with log2(alignment)
 254   // as the buckets, if performance is an issue.
 255   std::sort(Dest.begin(), Dest.end(),
 256             [this](const Variable *V1, const Variable *V2) {
 257               return typeWidthInBytesOnStack(V1->getType()) >
 258                      typeWidthInBytesOnStack(V2->getType());
 259             });
 260 }
 261
 262 void TargetLowering::getVarStackSlotParams(
 263     VarList &SortedSpilledVariables, llvm::SmallBitVector &RegsUsed,
 264     size_t *GlobalsSize, size_t *SpillAreaSizeBytes,
 265     uint32_t *SpillAreaAlignmentBytes, uint32_t *LocalsSlotsAlignmentBytes,
 266     std::function<bool(Variable *)> TargetVarHook) {
 267   const VariablesMetadata *VMetadata = Func->getVMetadata();
 268   llvm::BitVector IsVarReferenced(Func->getNumVariables());
 269   for (CfgNode *Node : Func->getNodes()) {
 270     for (Inst &Inst : Node->getInsts()) {
 271       if (Inst.isDeleted())
 272         continue;
 273       if (const Variable *Var = Inst.getDest())
 274         IsVarReferenced[Var->getIndex()] = true;
 275       for (SizeT I = 0; I < Inst.getSrcSize(); ++I) {
 276         Operand *Src = Inst.getSrc(I);
 277         SizeT NumVars = Src->getNumVars();
 278         for (SizeT J = 0; J < NumVars; ++J) {
 279           const Variable *Var = Src->getVar(J);
 280           IsVarReferenced[Var->getIndex()] = true;
 281         }
 282       }
 283     }
 284   }
 285
 286   // If SimpleCoalescing is false, each variable without a register
 287   // gets its own unique stack slot, which leads to large stack
 288   // frames.  If SimpleCoalescing is true, then each "global" variable
 289   // without a register gets its own slot, but "local" variable slots
 290   // are reused across basic blocks.  E.g., if A and B are local to
 291   // block 1 and C is local to block 2, then C may share a slot with A or B.
 292   //
 293   // We cannot coalesce stack slots if this function calls a "returns twice"
 294   // function. In that case, basic blocks may be revisited, and variables
 295   // local to those basic blocks are actually live until after the
 296   // called function returns a second time.
 297   const bool SimpleCoalescing = !callsReturnsTwice();
 298
 299   std::vector<size_t> LocalsSize(Func->getNumNodes());
 300   const VarList &Variables = Func->getVariables();
 301   VarList SpilledVariables;
 302   for (Variable *Var : Variables) {
 303     if (Var->hasReg()) {
 304       RegsUsed[Var->getRegNum()] = true;
 305       continue;
 306     }
 307     // An argument either does not need a stack slot (if passed in a
 308     // register) or already has one (if passed on the stack).
 309     if (Var->getIsArg())
 310       continue;
 311     // An unreferenced variable doesn't need a stack slot.
 312     if (!IsVarReferenced[Var->getIndex()])
 313       continue;
 314     // Check a target-specific variable (it may end up sharing stack slots)
 315     // and not need accounting here.
 316     if (TargetVarHook(Var))
 317       continue;
 318     SpilledVariables.push_back(Var);
 319   }
 320
 321   SortedSpilledVariables.reserve(SpilledVariables.size());
 322   sortVarsByAlignment(SortedSpilledVariables, SpilledVariables);
 323
 324   for (Variable *Var : SortedSpilledVariables) {
 325     size_t Increment = typeWidthInBytesOnStack(Var->getType());
 326     // We have sorted by alignment, so the first variable we encounter that
 327     // is located in each area determines the max alignment for the area.
 328     if (!*SpillAreaAlignmentBytes)
 329       *SpillAreaAlignmentBytes = Increment;
 330     if (SimpleCoalescing && VMetadata->isTracked(Var)) {
 331       if (VMetadata->isMultiBlock(Var)) {
 332         *GlobalsSize += Increment;
 333       } else {
 334         SizeT NodeIndex = VMetadata->getLocalUseNode(Var)->getIndex();
 335         LocalsSize[NodeIndex] += Increment;
 336         if (LocalsSize[NodeIndex] > *SpillAreaSizeBytes)
 337           *SpillAreaSizeBytes = LocalsSize[NodeIndex];
 338         if (!*LocalsSlotsAlignmentBytes)
 339           *LocalsSlotsAlignmentBytes = Increment;
 340       }
 341     } else {
 342       *SpillAreaSizeBytes += Increment;
 343     }
 344   }
 345 }
 346
 347 void TargetLowering::alignStackSpillAreas(uint32_t SpillAreaStartOffset,
 348                                           uint32_t SpillAreaAlignmentBytes,
 349                                           size_t GlobalsSize,
 350                                           uint32_t LocalsSlotsAlignmentBytes,
 351                                           uint32_t *SpillAreaPaddingBytes,
 352                                           uint32_t *LocalsSlotsPaddingBytes) {
 353   if (SpillAreaAlignmentBytes) {
 354     uint32_t PaddingStart = SpillAreaStartOffset;
 355     uint32_t SpillAreaStart =
 356         Utils::applyAlignment(PaddingStart, SpillAreaAlignmentBytes);
 357     *SpillAreaPaddingBytes = SpillAreaStart - PaddingStart;
 358   }
 359
 360   // If there are separate globals and locals areas, make sure the
 361   // locals area is aligned by padding the end of the globals area.
 362   if (LocalsSlotsAlignmentBytes) {
 363     uint32_t GlobalsAndSubsequentPaddingSize = GlobalsSize;
 364     GlobalsAndSubsequentPaddingSize =
 365         Utils::applyAlignment(GlobalsSize, LocalsSlotsAlignmentBytes);
 366     *LocalsSlotsPaddingBytes = GlobalsAndSubsequentPaddingSize - GlobalsSize;
 367   }
 368 }
 369
 370 void TargetLowering::assignVarStackSlots(VarList &SortedSpilledVariables,
 371                                          size_t SpillAreaPaddingBytes,
 372                                          size_t SpillAreaSizeBytes,
 373                                          size_t GlobalsAndSubsequentPaddingSize,
 374                                          bool UsesFramePointer) {
 375   const VariablesMetadata *VMetadata = Func->getVMetadata();
 376   size_t GlobalsSpaceUsed = SpillAreaPaddingBytes;
 377   size_t NextStackOffset = SpillAreaPaddingBytes;
 378   std::vector<size_t> LocalsSize(Func->getNumNodes());
 379   const bool SimpleCoalescing = !callsReturnsTwice();
 380   for (Variable *Var : SortedSpilledVariables) {
 381     size_t Increment = typeWidthInBytesOnStack(Var->getType());
 382     if (SimpleCoalescing && VMetadata->isTracked(Var)) {
 383       if (VMetadata->isMultiBlock(Var)) {
 384         GlobalsSpaceUsed += Increment;
 385         NextStackOffset = GlobalsSpaceUsed;
 386       } else {
 387         SizeT NodeIndex = VMetadata->getLocalUseNode(Var)->getIndex();
 388         LocalsSize[NodeIndex] += Increment;
 389         NextStackOffset = SpillAreaPaddingBytes +
 390                           GlobalsAndSubsequentPaddingSize +
 391                           LocalsSize[NodeIndex];
 392       }
 393     } else {
 394       NextStackOffset += Increment;
 395     }
 396     if (UsesFramePointer)
 397       Var->setStackOffset(-NextStackOffset);
 398     else
 399       Var->setStackOffset(SpillAreaSizeBytes - NextStackOffset);
 400   }
 401 }
 402
 403 InstCall *TargetLowering::makeHelperCall(const IceString &Name, Variable *Dest,
 404                                          SizeT MaxSrcs) {
 405   const bool HasTailCall = false;
 406   Constant *CallTarget = Ctx->getConstantExternSym(Name);
 407   InstCall *Call =
 408       InstCall::create(Func, MaxSrcs, Dest, CallTarget, HasTailCall);
 409   return Call;
 410 }
 411
 412 void TargetLowering::emitWithoutPrefix(const ConstantRelocatable *C) const {
 413   if (!ALLOW_DUMP)
 414     return;
 415   Ostream &Str = Ctx->getStrEmit();
 416   if (C->getSuppressMangling())
 417     Str << C->getName();
 418   else
 419     Str << Ctx->mangleName(C->getName());
 420   RelocOffsetT Offset = C->getOffset();
 421   if (Offset) {
 422     if (Offset > 0)
 423       Str << "+";
 424     Str << Offset;
 425   }
 426 }
 427
 428 void TargetLowering::emit(const ConstantRelocatable *C) const {
 429   if (!ALLOW_DUMP)
 430     return;
 431   Ostream &Str = Ctx->getStrEmit();
 432   Str << getConstantPrefix();
 433   emitWithoutPrefix(C);
 434 }
 435
 436 std::unique_ptr<TargetDataLowering>
 437 TargetDataLowering::createLowering(GlobalContext *Ctx) {
 438   TargetArch Target = Ctx->getFlags().getTargetArch();
 439 #define SUBZERO_TARGET(X)                                                      \
 440   if (Target == Target_##X)                                                    \
 441     return TargetData##X::create(Ctx);
 442 #include "llvm/Config/SZTargets.def"
 443
 444   llvm::report_fatal_error("Unsupported target data lowering");
 445 }
 446
 447 TargetDataLowering::~TargetDataLowering() {}
 448
 449 void TargetDataLowering::emitGlobal(const VariableDeclaration &Var) {
 450   if (!ALLOW_DUMP)
 451     return;
 452
 453   // If external and not initialized, this must be a cross test.
 454   // Don't generate a declaration for such cases.
 455   bool IsExternal = Var.isExternal() || Ctx->getFlags().getDisableInternal();
 456   if (IsExternal && !Var.hasInitializer())
 457     return;
 458
 459   Ostream &Str = Ctx->getStrEmit();
 460   const VariableDeclaration::InitializerListType &Initializers =
 461       Var.getInitializers();
 462   bool HasNonzeroInitializer = Var.hasNonzeroInitializer();
 463   bool IsConstant = Var.getIsConstant();
 464   uint32_t Align = Var.getAlignment();
 465   SizeT Size = Var.getNumBytes();
 466   IceString MangledName = Var.mangleName(Ctx);
 467   IceString SectionSuffix = "";
 468   if (Ctx->getFlags().getDataSections())
 469     SectionSuffix = "." + MangledName;
 470
 471   Str << "\t.type\t" << MangledName << ",%object\n";
 472
 473   if (IsConstant)
 474     Str << "\t.section\t.rodata" << SectionSuffix << ",\"a\",%progbits\n";
 475   else if (HasNonzeroInitializer)
 476     Str << "\t.section\t.data" << SectionSuffix << ",\"aw\",%progbits\n";
 477   else
 478     Str << "\t.section\t.bss" << SectionSuffix << ",\"aw\",%nobits\n";
 479
 480   if (IsExternal)
 481     Str << "\t.globl\t" << MangledName << "\n";
 482
 483   if (Align > 1) {
 484     assert(llvm::isPowerOf2_32(Align));
 485     // Use the .p2align directive, since the .align N directive can either
 486     // interpret N as bytes, or power of 2 bytes, depending on the target.
 487     Str << "\t.p2align\t" << llvm::Log2_32(Align) << "\n";
 488   }
 489
 490   Str << MangledName << ":\n";
 491
 492   if (HasNonzeroInitializer) {
 493     for (VariableDeclaration::Initializer *Init : Initializers) {
 494       switch (Init->getKind()) {
 495       case VariableDeclaration::Initializer::DataInitializerKind: {
 496         const auto Data = llvm::cast<VariableDeclaration::DataInitializer>(Init)
 497                               ->getContents();
 498         for (SizeT i = 0; i < Init->getNumBytes(); ++i) {
 499           Str << "\t.byte\t" << (((unsigned)Data[i]) & 0xff) << "\n";
 500         }
 501         break;
 502       }
 503       case VariableDeclaration::Initializer::ZeroInitializerKind:
 504         Str << "\t.zero\t" << Init->getNumBytes() << "\n";
 505         break;
 506       case VariableDeclaration::Initializer::RelocInitializerKind: {
 507         const auto Reloc =
 508             llvm::cast<VariableDeclaration::RelocInitializer>(Init);
 509         Str << "\t" << getEmit32Directive() << "\t";
 510         Str << Reloc->getDeclaration()->mangleName(Ctx);
 511         if (RelocOffsetT Offset = Reloc->getOffset()) {
 512           if (Offset >= 0 || (Offset == INT32_MIN))
 513             Str << " + " << Offset;
 514           else
 515             Str << " - " << -Offset;
 516         }
 517         Str << "\n";
 518         break;
 519       }
 520       }
 521     }
 522   } else
 523     // NOTE: for non-constant zero initializers, this is BSS (no bits),
 524     // so an ELF writer would not write to the file, and only track
 525     // virtual offsets, but the .s writer still needs this .zero and
 526     // cannot simply use the .size to advance offsets.
 527     Str << "\t.zero\t" << Size << "\n";
 528
 529   Str << "\t.size\t" << MangledName << ", " << Size << "\n";
 530 }
 531
 532 std::unique_ptr<TargetHeaderLowering>
 533 TargetHeaderLowering::createLowering(GlobalContext *Ctx) {
 534   TargetArch Target = Ctx->getFlags().getTargetArch();
 535 #define SUBZERO_TARGET(X)                                                      \
 536   if (Target == Target_##X)                                                    \
 537     return TargetHeader##X::create(Ctx);
 538 #include "llvm/Config/SZTargets.def"
 539
 540   llvm::report_fatal_error("Unsupported target header lowering");
 541 }
 542
 543 TargetHeaderLowering::~TargetHeaderLowering() {}
 544
 545 } // end of namespace Ice