contrib/llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp

   1 //===---- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer -------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Implement an interface to specify and query how an illegal operation on a
  11 // given type should be expanded.
  12 //
  13 // Issues to be resolved:
  14 //   + Make it fast.
  15 //   + Support weird types like i3, <7 x i3>, ...
  16 //   + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  21
  22 #include "llvm/ADT/SmallBitVector.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/ValueTypes.h"
  26 #include "llvm/IR/Type.h"
  27 #include "llvm/Target/TargetOpcodes.h"
  28 using namespace llvm;
  29
  30 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
  31   // FIXME: these two can be legalized to the fundamental load/store Jakob
  32   // proposed. Once loads & stores are supported.
  33   DefaultActions[TargetOpcode::G_ANYEXT] = Legal;
  34   DefaultActions[TargetOpcode::G_TRUNC] = Legal;
  35
  36   DefaultActions[TargetOpcode::G_INTRINSIC] = Legal;
  37   DefaultActions[TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS] = Legal;
  38
  39   DefaultActions[TargetOpcode::G_ADD] = NarrowScalar;
  40   DefaultActions[TargetOpcode::G_LOAD] = NarrowScalar;
  41   DefaultActions[TargetOpcode::G_STORE] = NarrowScalar;
  42
  43   DefaultActions[TargetOpcode::G_BRCOND] = WidenScalar;
  44 }
  45
  46 void LegalizerInfo::computeTables() {
  47   for (unsigned Opcode = 0; Opcode <= LastOp - FirstOp; ++Opcode) {
  48     for (unsigned Idx = 0; Idx != Actions[Opcode].size(); ++Idx) {
  49       for (auto &Action : Actions[Opcode][Idx]) {
  50         LLT Ty = Action.first;
  51         if (!Ty.isVector())
  52           continue;
  53
  54         auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
  55                                                         Ty.getElementType())];
  56         Entry = std::max(Entry, Ty.getNumElements());
  57       }
  58     }
  59   }
  60
  61   TablesInitialized = true;
  62 }
  63
  64 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
  65 // probably going to need specialized lookup structures for various types before
  66 // we have any hope of doing well with something like <13 x i3>. Even the common
  67 // cases should do better than what we have now.
  68 std::pair<LegalizerInfo::LegalizeAction, LLT>
  69 LegalizerInfo::getAction(const InstrAspect &Aspect) const {
  70   assert(TablesInitialized && "backend forgot to call computeTables");
  71   // These *have* to be implemented for now, they're the fundamental basis of
  72   // how everything else is transformed.
  73
  74   // Nothing is going to go well with types that aren't a power of 2 yet, so
  75   // don't even try because we might make things worse.
  76   if (!isPowerOf2_64(Aspect.Type.getSizeInBits()))
  77       return std::make_pair(Unsupported, LLT());
  78
  79   // FIXME: the long-term plan calls for expansion in terms of load/store (if
  80   // they're not legal).
  81   if (Aspect.Opcode == TargetOpcode::G_SEQUENCE ||
  82       Aspect.Opcode == TargetOpcode::G_EXTRACT)
  83     return std::make_pair(Legal, Aspect.Type);
  84
  85   LegalizeAction Action = findInActions(Aspect);
  86   if (Action != NotFound)
  87     return findLegalAction(Aspect, Action);
  88
  89   unsigned Opcode = Aspect.Opcode;
  90   LLT Ty = Aspect.Type;
  91   if (!Ty.isVector()) {
  92     auto DefaultAction = DefaultActions.find(Aspect.Opcode);
  93     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
  94       return std::make_pair(Legal, Ty);
  95
  96     if (DefaultAction == DefaultActions.end() ||
  97         DefaultAction->second != NarrowScalar)
  98       return std::make_pair(Unsupported, LLT());
  99     return findLegalAction(Aspect, NarrowScalar);
 100   }
 101
 102   LLT EltTy = Ty.getElementType();
 103   int NumElts = Ty.getNumElements();
 104
 105   auto ScalarAction = ScalarInVectorActions.find(std::make_pair(Opcode, EltTy));
 106   if (ScalarAction != ScalarInVectorActions.end() &&
 107       ScalarAction->second != Legal)
 108     return findLegalAction(Aspect, ScalarAction->second);
 109
 110   // The element type is legal in principle, but the number of elements is
 111   // wrong.
 112   auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
 113   if (MaxLegalElts > NumElts)
 114     return findLegalAction(Aspect, MoreElements);
 115
 116   if (MaxLegalElts == 0) {
 117     // Scalarize if there's no legal vector type, which is just a special case
 118     // of FewerElements.
 119     return std::make_pair(FewerElements, EltTy);
 120   }
 121
 122   return findLegalAction(Aspect, FewerElements);
 123 }
 124
 125 std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
 126 LegalizerInfo::getAction(const MachineInstr &MI,
 127                          const MachineRegisterInfo &MRI) const {
 128   SmallBitVector SeenTypes(8);
 129   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
 130   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
 131     if (!OpInfo[i].isGenericType())
 132       continue;
 133
 134     // We don't want to repeatedly check the same operand index, that
 135     // could get expensive.
 136     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
 137     if (SeenTypes[TypeIdx])
 138       continue;
 139
 140     SeenTypes.set(TypeIdx);
 141
 142     LLT Ty = MRI.getType(MI.getOperand(i).getReg());
 143     auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
 144     if (Action.first != Legal)
 145       return std::make_tuple(Action.first, TypeIdx, Action.second);
 146   }
 147   return std::make_tuple(Legal, 0, LLT{});
 148 }
 149
 150 bool LegalizerInfo::isLegal(const MachineInstr &MI,
 151                             const MachineRegisterInfo &MRI) const {
 152   return std::get<0>(getAction(MI, MRI)) == Legal;
 153 }
 154
 155 LLT LegalizerInfo::findLegalType(const InstrAspect &Aspect,
 156                                  LegalizeAction Action) const {
 157   switch(Action) {
 158   default:
 159     llvm_unreachable("Cannot find legal type");
 160   case Legal:
 161   case Lower:
 162   case Libcall:
 163     return Aspect.Type;
 164   case NarrowScalar: {
 165     return findLegalType(Aspect,
 166                          [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
 167   }
 168   case WidenScalar: {
 169     return findLegalType(Aspect, [&](LLT Ty) -> LLT {
 170       return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
 171     });
 172   }
 173   case FewerElements: {
 174     return findLegalType(Aspect,
 175                          [&](LLT Ty) -> LLT { return Ty.halfElements(); });
 176   }
 177   case MoreElements: {
 178     return findLegalType(Aspect,
 179                          [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
 180   }
 181   }
 182 }