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 "IceOperand.h"
  24 #include "IceRegAlloc.h"
  25 #include "IceTargetLowering.h"
  26 #include "IceTargetLoweringARM32.h"
  27 #include "IceTargetLoweringMIPS32.h"
  28 #include "IceTargetLoweringX8632.h"
  29
  30 namespace Ice {
  31
  32 void LoweringContext::init(CfgNode *N) {
  33   Node = N;
  34   End = getNode()->getInsts().end();
  35   rewind();
  36   advanceForward(Next);
  37 }
  38
  39 void LoweringContext::rewind() {
  40   Begin = getNode()->getInsts().begin();
  41   Cur = Begin;
  42   skipDeleted(Cur);
  43   Next = Cur;
  44 }
  45
  46 void LoweringContext::insert(Inst *Inst) {
  47   getNode()->getInsts().insert(Next, Inst);
  48   LastInserted = Inst;
  49 }
  50
  51 void LoweringContext::skipDeleted(InstList::iterator &I) const {
  52   while (I != End && I->isDeleted())
  53     ++I;
  54 }
  55
  56 void LoweringContext::advanceForward(InstList::iterator &I) const {
  57   if (I != End) {
  58     ++I;
  59     skipDeleted(I);
  60   }
  61 }
  62
  63 Inst *LoweringContext::getLastInserted() const {
  64   assert(LastInserted);
  65   return LastInserted;
  66 }
  67
  68 TargetLowering *TargetLowering::createLowering(TargetArch Target, Cfg *Func) {
  69 #define SUBZERO_TARGET(X)                                                      \
  70   if (Target == Target_##X)                                                    \
  71     return Target##X::create(Func);
  72 #include "llvm/Config/SZTargets.def"
  73
  74   Func->setError("Unsupported target");
  75   return nullptr;
  76 }
  77
  78 TargetLowering::TargetLowering(Cfg *Func)
  79     : Func(Func), Ctx(Func->getContext()), HasComputedFrame(false),
  80       CallsReturnsTwice(false), StackAdjustment(0), NextLabelNumber(0),
  81       Context(), SnapshotStackAdjustment(0) {}
  82
  83 std::unique_ptr<Assembler> TargetLowering::createAssembler(TargetArch Target,
  84                                                            Cfg *Func) {
  85 #define SUBZERO_TARGET(X)                                                      \
  86   if (Target == Target_##X)                                                    \
  87     return std::unique_ptr<Assembler>(new X::Assembler##X());
  88 #include "llvm/Config/SZTargets.def"
  89
  90   Func->setError("Unsupported target assembler");
  91   return nullptr;
  92 }
  93
  94 void TargetLowering::doAddressOpt() {
  95   if (llvm::isa<InstLoad>(*Context.getCur()))
  96     doAddressOptLoad();
  97   else if (llvm::isa<InstStore>(*Context.getCur()))
  98     doAddressOptStore();
  99   Context.advanceCur();
 100   Context.advanceNext();
 101 }
 102
 103 void TargetLowering::doNopInsertion() {
 104   Inst *I = Context.getCur();
 105   bool ShouldSkip = llvm::isa<InstFakeUse>(I) || llvm::isa<InstFakeDef>(I) ||
 106                     llvm::isa<InstFakeKill>(I) || I->isRedundantAssign() ||
 107                     I->isDeleted();
 108   if (!ShouldSkip) {
 109     int Probability = Ctx->getFlags().getNopProbabilityAsPercentage();
 110     for (int I = 0; I < Ctx->getFlags().getMaxNopsPerInstruction(); ++I) {
 111       randomlyInsertNop(Probability / 100.0);
 112     }
 113   }
 114 }
 115
 116 // Lowers a single instruction according to the information in
 117 // Context, by checking the Context.Cur instruction kind and calling
 118 // the appropriate lowering method.  The lowering method should insert
 119 // target instructions at the Cur.Next insertion point, and should not
 120 // delete the Context.Cur instruction or advance Context.Cur.
 121 //
 122 // The lowering method may look ahead in the instruction stream as
 123 // desired, and lower additional instructions in conjunction with the
 124 // current one, for example fusing a compare and branch.  If it does,
 125 // it should advance Context.Cur to point to the next non-deleted
 126 // instruction to process, and it should delete any additional
 127 // instructions it consumes.
 128 void TargetLowering::lower() {
 129   assert(!Context.atEnd());
 130   Inst *Inst = Context.getCur();
 131   Inst->deleteIfDead();
 132   if (!Inst->isDeleted()) {
 133     // Mark the current instruction as deleted before lowering,
 134     // otherwise the Dest variable will likely get marked as non-SSA.
 135     // See Variable::setDefinition().
 136     Inst->setDeleted();
 137     switch (Inst->getKind()) {
 138     case Inst::Alloca:
 139       lowerAlloca(llvm::cast<InstAlloca>(Inst));
 140       break;
 141     case Inst::Arithmetic:
 142       lowerArithmetic(llvm::cast<InstArithmetic>(Inst));
 143       break;
 144     case Inst::Assign:
 145       lowerAssign(llvm::cast<InstAssign>(Inst));
 146       break;
 147     case Inst::Br:
 148       lowerBr(llvm::cast<InstBr>(Inst));
 149       break;
 150     case Inst::Call:
 151       lowerCall(llvm::cast<InstCall>(Inst));
 152       break;
 153     case Inst::Cast:
 154       lowerCast(llvm::cast<InstCast>(Inst));
 155       break;
 156     case Inst::ExtractElement:
 157       lowerExtractElement(llvm::cast<InstExtractElement>(Inst));
 158       break;
 159     case Inst::Fcmp:
 160       lowerFcmp(llvm::cast<InstFcmp>(Inst));
 161       break;
 162     case Inst::Icmp:
 163       lowerIcmp(llvm::cast<InstIcmp>(Inst));
 164       break;
 165     case Inst::InsertElement:
 166       lowerInsertElement(llvm::cast<InstInsertElement>(Inst));
 167       break;
 168     case Inst::IntrinsicCall: {
 169       InstIntrinsicCall *Call = llvm::cast<InstIntrinsicCall>(Inst);
 170       if (Call->getIntrinsicInfo().ReturnsTwice)
 171         setCallsReturnsTwice(true);
 172       lowerIntrinsicCall(Call);
 173       break;
 174     }
 175     case Inst::Load:
 176       lowerLoad(llvm::cast<InstLoad>(Inst));
 177       break;
 178     case Inst::Phi:
 179       lowerPhi(llvm::cast<InstPhi>(Inst));
 180       break;
 181     case Inst::Ret:
 182       lowerRet(llvm::cast<InstRet>(Inst));
 183       break;
 184     case Inst::Select:
 185       lowerSelect(llvm::cast<InstSelect>(Inst));
 186       break;
 187     case Inst::Store:
 188       lowerStore(llvm::cast<InstStore>(Inst));
 189       break;
 190     case Inst::Switch:
 191       lowerSwitch(llvm::cast<InstSwitch>(Inst));
 192       break;
 193     case Inst::Unreachable:
 194       lowerUnreachable(llvm::cast<InstUnreachable>(Inst));
 195       break;
 196     case Inst::BundleLock:
 197     case Inst::BundleUnlock:
 198     case Inst::FakeDef:
 199     case Inst::FakeUse:
 200     case Inst::FakeKill:
 201     case Inst::Target:
 202       // These are all Target instruction types and shouldn't be
 203       // encountered at this stage.
 204       Func->setError("Can't lower unsupported instruction type");
 205       break;
 206     }
 207
 208     postLower();
 209   }
 210
 211   Context.advanceCur();
 212   Context.advanceNext();
 213 }
 214
 215 // Drives register allocation, allowing all physical registers (except
 216 // perhaps for the frame pointer) to be allocated.  This set of
 217 // registers could potentially be parameterized if we want to restrict
 218 // registers e.g. for performance testing.
 219 void TargetLowering::regAlloc(RegAllocKind Kind) {
 220   TimerMarker T(TimerStack::TT_regAlloc, Func);
 221   LinearScan LinearScan(Func);
 222   RegSetMask RegInclude = RegSet_None;
 223   RegSetMask RegExclude = RegSet_None;
 224   RegInclude |= RegSet_CallerSave;
 225   RegInclude |= RegSet_CalleeSave;
 226   if (hasFramePointer())
 227     RegExclude |= RegSet_FramePointer;
 228   LinearScan.init(Kind);
 229   llvm::SmallBitVector RegMask = getRegisterSet(RegInclude, RegExclude);
 230   LinearScan.scan(RegMask, Ctx->getFlags().shouldRandomizeRegAlloc());
 231 }
 232
 233 void TargetLowering::inferTwoAddress() {
 234   // Find two-address non-SSA instructions where Dest==Src0, and set
 235   // the DestNonKillable flag to keep liveness analysis consistent.
 236   for (auto Inst = Context.getCur(), E = Context.getNext(); Inst != E; ++Inst) {
 237     if (Inst->isDeleted())
 238       continue;
 239     if (Variable *Dest = Inst->getDest()) {
 240       // TODO(stichnot): We may need to consider all source
 241       // operands, not just the first one, if using 3-address
 242       // instructions.
 243       if (Inst->getSrcSize() > 0 && Inst->getSrc(0) == Dest)
 244         Inst->setDestNonKillable();
 245     }
 246   }
 247 }
 248
 249 void TargetLowering::sortVarsByAlignment(VarList &Dest,
 250                                          const VarList &Source) const {
 251   Dest = Source;
 252   // Instead of std::sort, we could do a bucket sort with log2(alignment)
 253   // as the buckets, if performance is an issue.
 254   std::sort(Dest.begin(), Dest.end(),
 255             [this](const Variable *V1, const Variable *V2) {
 256               return typeWidthInBytesOnStack(V1->getType()) >
 257                      typeWidthInBytesOnStack(V2->getType());
 258             });
 259 }
 260
 261 void TargetLowering::getVarStackSlotParams(
 262     VarList &SortedSpilledVariables, llvm::SmallBitVector &RegsUsed,
 263     size_t *GlobalsSize, size_t *SpillAreaSizeBytes,
 264     uint32_t *SpillAreaAlignmentBytes, uint32_t *LocalsSlotsAlignmentBytes,
 265     std::function<bool(Variable *)> TargetVarHook) {
 266   const VariablesMetadata *VMetadata = Func->getVMetadata();
 267   llvm::BitVector IsVarReferenced(Func->getNumVariables());
 268   for (CfgNode *Node : Func->getNodes()) {
 269     for (Inst &Inst : Node->getInsts()) {
 270       if (Inst.isDeleted())
 271         continue;
 272       if (const Variable *Var = Inst.getDest())
 273         IsVarReferenced[Var->getIndex()] = true;
 274       for (SizeT I = 0; I < Inst.getSrcSize(); ++I) {
 275         Operand *Src = Inst.getSrc(I);
 276         SizeT NumVars = Src->getNumVars();
 277         for (SizeT J = 0; J < NumVars; ++J) {
 278           const Variable *Var = Src->getVar(J);
 279           IsVarReferenced[Var->getIndex()] = true;
 280         }
 281       }
 282     }
 283   }
 284
 285   // If SimpleCoalescing is false, each variable without a register
 286   // gets its own unique stack slot, which leads to large stack
 287   // frames.  If SimpleCoalescing is true, then each "global" variable
 288   // without a register gets its own slot, but "local" variable slots
 289   // are reused across basic blocks.  E.g., if A and B are local to
 290   // block 1 and C is local to block 2, then C may share a slot with A or B.
 291   //
 292   // We cannot coalesce stack slots if this function calls a "returns twice"
 293   // function. In that case, basic blocks may be revisited, and variables
 294   // local to those basic blocks are actually live until after the
 295   // called function returns a second time.
 296   const bool SimpleCoalescing = !callsReturnsTwice();
 297
 298   std::vector<size_t> LocalsSize(Func->getNumNodes());
 299   const VarList &Variables = Func->getVariables();
 300   VarList SpilledVariables;
 301   for (Variable *Var : Variables) {
 302     if (Var->hasReg()) {
 303       RegsUsed[Var->getRegNum()] = true;
 304       continue;
 305     }
 306     // An argument either does not need a stack slot (if passed in a
 307     // register) or already has one (if passed on the stack).
 308     if (Var->getIsArg())
 309       continue;
 310     // An unreferenced variable doesn't need a stack slot.
 311     if (!IsVarReferenced[Var->getIndex()])
 312       continue;
 313     // Check a target-specific variable (it may end up sharing stack slots)
 314     // and not need accounting here.
 315     if (TargetVarHook(Var))
 316       continue;
 317     SpilledVariables.push_back(Var);
 318   }
 319
 320   SortedSpilledVariables.reserve(SpilledVariables.size());
 321   sortVarsByAlignment(SortedSpilledVariables, SpilledVariables);
 322
 323   for (Variable *Var : SortedSpilledVariables) {
 324     size_t Increment = typeWidthInBytesOnStack(Var->getType());
 325     // We have sorted by alignment, so the first variable we encounter that
 326     // is located in each area determines the max alignment for the area.
 327     if (!*SpillAreaAlignmentBytes)
 328       *SpillAreaAlignmentBytes = Increment;
 329     if (SimpleCoalescing && VMetadata->isTracked(Var)) {
 330       if (VMetadata->isMultiBlock(Var)) {
 331         *GlobalsSize += Increment;
 332       } else {
 333         SizeT NodeIndex = VMetadata->getLocalUseNode(Var)->getIndex();
 334         LocalsSize[NodeIndex] += Increment;
 335         if (LocalsSize[NodeIndex] > *SpillAreaSizeBytes)
 336           *SpillAreaSizeBytes = LocalsSize[NodeIndex];
 337         if (!*LocalsSlotsAlignmentBytes)
 338           *LocalsSlotsAlignmentBytes = Increment;
 339       }
 340     } else {
 341       *SpillAreaSizeBytes += Increment;
 342     }
 343   }
 344 }
 345
 346 void TargetLowering::alignStackSpillAreas(uint32_t SpillAreaStartOffset,
 347                                           uint32_t SpillAreaAlignmentBytes,
 348                                           size_t GlobalsSize,
 349                                           uint32_t LocalsSlotsAlignmentBytes,
 350                                           uint32_t *SpillAreaPaddingBytes,
 351                                           uint32_t *LocalsSlotsPaddingBytes) {
 352   if (SpillAreaAlignmentBytes) {
 353     uint32_t PaddingStart = SpillAreaStartOffset;
 354     uint32_t SpillAreaStart =
 355         Utils::applyAlignment(PaddingStart, SpillAreaAlignmentBytes);
 356     *SpillAreaPaddingBytes = SpillAreaStart - PaddingStart;
 357   }
 358
 359   // If there are separate globals and locals areas, make sure the
 360   // locals area is aligned by padding the end of the globals area.
 361   if (LocalsSlotsAlignmentBytes) {
 362     uint32_t GlobalsAndSubsequentPaddingSize = GlobalsSize;
 363     GlobalsAndSubsequentPaddingSize =
 364         Utils::applyAlignment(GlobalsSize, LocalsSlotsAlignmentBytes);
 365     *LocalsSlotsPaddingBytes = GlobalsAndSubsequentPaddingSize - GlobalsSize;
 366   }
 367 }
 368
 369 void TargetLowering::assignVarStackSlots(VarList &SortedSpilledVariables,
 370                                          size_t SpillAreaPaddingBytes,
 371                                          size_t SpillAreaSizeBytes,
 372                                          size_t GlobalsAndSubsequentPaddingSize,
 373                                          bool UsesFramePointer) {
 374   const VariablesMetadata *VMetadata = Func->getVMetadata();
 375   size_t GlobalsSpaceUsed = SpillAreaPaddingBytes;
 376   size_t NextStackOffset = SpillAreaPaddingBytes;
 377   std::vector<size_t> LocalsSize(Func->getNumNodes());
 378   const bool SimpleCoalescing = !callsReturnsTwice();
 379   for (Variable *Var : SortedSpilledVariables) {
 380     size_t Increment = typeWidthInBytesOnStack(Var->getType());
 381     if (SimpleCoalescing && VMetadata->isTracked(Var)) {
 382       if (VMetadata->isMultiBlock(Var)) {
 383         GlobalsSpaceUsed += Increment;
 384         NextStackOffset = GlobalsSpaceUsed;
 385       } else {
 386         SizeT NodeIndex = VMetadata->getLocalUseNode(Var)->getIndex();
 387         LocalsSize[NodeIndex] += Increment;
 388         NextStackOffset = SpillAreaPaddingBytes +
 389                           GlobalsAndSubsequentPaddingSize +
 390                           LocalsSize[NodeIndex];
 391       }
 392     } else {
 393       NextStackOffset += Increment;
 394     }
 395     if (UsesFramePointer)
 396       Var->setStackOffset(-NextStackOffset);
 397     else
 398       Var->setStackOffset(SpillAreaSizeBytes - NextStackOffset);
 399   }
 400 }
 401
 402 InstCall *TargetLowering::makeHelperCall(const IceString &Name, Variable *Dest,
 403                                          SizeT MaxSrcs) {
 404   const bool HasTailCall = false;
 405   Constant *CallTarget = Ctx->getConstantExternSym(Name);
 406   InstCall *Call =
 407       InstCall::create(Func, MaxSrcs, Dest, CallTarget, HasTailCall);
 408   return Call;
 409 }
 410
 411 void TargetLowering::emitWithoutPrefix(const ConstantRelocatable *C) const {
 412   if (!ALLOW_DUMP)
 413     return;
 414   Ostream &Str = Ctx->getStrEmit();
 415   if (C->getSuppressMangling())
 416     Str << C->getName();
 417   else
 418     Str << Ctx->mangleName(C->getName());
 419   RelocOffsetT Offset = C->getOffset();
 420   if (Offset) {
 421     if (Offset > 0)
 422       Str << "+";
 423     Str << Offset;
 424   }
 425 }
 426
 427 void TargetLowering::emit(const ConstantRelocatable *C) const {
 428   if (!ALLOW_DUMP)
 429     return;
 430   Ostream &Str = Ctx->getStrEmit();
 431   Str << getConstantPrefix();
 432   emitWithoutPrefix(C);
 433 }
 434
 435 std::unique_ptr<TargetDataLowering>
 436 TargetDataLowering::createLowering(GlobalContext *Ctx) {
 437   TargetArch Target = Ctx->getFlags().getTargetArch();
 438 #define SUBZERO_TARGET(X)                                                      \
 439   if (Target == Target_##X)                                                    \
 440     return std::unique_ptr<TargetDataLowering>(TargetData##X::create(Ctx));
 441 #include "llvm/Config/SZTargets.def"
 442
 443   llvm_unreachable("Unsupported target data lowering");
 444   return nullptr;
 445 }
 446
 447 TargetDataLowering::~TargetDataLowering() {}
 448
 449 } // end of namespace Ice