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   DefaultActions[TargetOpcode::G_INSERT] = NarrowScalar;
  45   DefaultActions[TargetOpcode::G_FNEG] = Lower;
  46 }
  47
  48 void LegalizerInfo::computeTables() {
  49   for (unsigned Opcode = 0; Opcode <= LastOp - FirstOp; ++Opcode) {
  50     for (unsigned Idx = 0; Idx != Actions[Opcode].size(); ++Idx) {
  51       for (auto &Action : Actions[Opcode][Idx]) {
  52         LLT Ty = Action.first;
  53         if (!Ty.isVector())
  54           continue;
  55
  56         auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
  57                                                         Ty.getElementType())];
  58         Entry = std::max(Entry, Ty.getNumElements());
  59       }
  60     }
  61   }
  62
  63   TablesInitialized = true;
  64 }
  65
  66 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
  67 // probably going to need specialized lookup structures for various types before
  68 // we have any hope of doing well with something like <13 x i3>. Even the common
  69 // cases should do better than what we have now.
  70 std::pair<LegalizerInfo::LegalizeAction, LLT>
  71 LegalizerInfo::getAction(const InstrAspect &Aspect) const {
  72   assert(TablesInitialized && "backend forgot to call computeTables");
  73   // These *have* to be implemented for now, they're the fundamental basis of
  74   // how everything else is transformed.
  75
  76   // FIXME: the long-term plan calls for expansion in terms of load/store (if
  77   // they're not legal).
  78   if (Aspect.Opcode == TargetOpcode::G_EXTRACT ||
  79       Aspect.Opcode == TargetOpcode::G_MERGE_VALUES ||
  80       Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES)
  81     return std::make_pair(Legal, Aspect.Type);
  82
  83   LLT Ty = Aspect.Type;
  84   LegalizeAction Action = findInActions(Aspect);
  85   // LegalizerHelper is not able to handle non-power-of-2 types right now, so do
  86   // not try to legalize them unless they are marked as Legal or Custom.
  87   // FIXME: This is a temporary hack until the general non-power-of-2
  88   // legalization works.
  89   if (!isPowerOf2_64(Ty.getSizeInBits()) &&
  90       !(Action == Legal || Action == Custom))
  91     return std::make_pair(Unsupported, LLT());
  92
  93   if (Action != NotFound)
  94     return findLegalAction(Aspect, Action);
  95
  96   unsigned Opcode = Aspect.Opcode;
  97   if (!Ty.isVector()) {
  98     auto DefaultAction = DefaultActions.find(Aspect.Opcode);
  99     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
 100       return std::make_pair(Legal, Ty);
 101
 102     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Lower)
 103       return std::make_pair(Lower, Ty);
 104
 105     if (DefaultAction == DefaultActions.end() ||
 106         DefaultAction->second != NarrowScalar)
 107       return std::make_pair(Unsupported, LLT());
 108     return findLegalAction(Aspect, NarrowScalar);
 109   }
 110
 111   LLT EltTy = Ty.getElementType();
 112   int NumElts = Ty.getNumElements();
 113
 114   auto ScalarAction = ScalarInVectorActions.find(std::make_pair(Opcode, EltTy));
 115   if (ScalarAction != ScalarInVectorActions.end() &&
 116       ScalarAction->second != Legal)
 117     return findLegalAction(Aspect, ScalarAction->second);
 118
 119   // The element type is legal in principle, but the number of elements is
 120   // wrong.
 121   auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
 122   if (MaxLegalElts > NumElts)
 123     return findLegalAction(Aspect, MoreElements);
 124
 125   if (MaxLegalElts == 0) {
 126     // Scalarize if there's no legal vector type, which is just a special case
 127     // of FewerElements.
 128     return std::make_pair(FewerElements, EltTy);
 129   }
 130
 131   return findLegalAction(Aspect, FewerElements);
 132 }
 133
 134 std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
 135 LegalizerInfo::getAction(const MachineInstr &MI,
 136                          const MachineRegisterInfo &MRI) const {
 137   SmallBitVector SeenTypes(8);
 138   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
 139   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
 140     if (!OpInfo[i].isGenericType())
 141       continue;
 142
 143     // We don't want to repeatedly check the same operand index, that
 144     // could get expensive.
 145     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
 146     if (SeenTypes[TypeIdx])
 147       continue;
 148
 149     SeenTypes.set(TypeIdx);
 150
 151     LLT Ty = MRI.getType(MI.getOperand(i).getReg());
 152     auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
 153     if (Action.first != Legal)
 154       return std::make_tuple(Action.first, TypeIdx, Action.second);
 155   }
 156   return std::make_tuple(Legal, 0, LLT{});
 157 }
 158
 159 bool LegalizerInfo::isLegal(const MachineInstr &MI,
 160                             const MachineRegisterInfo &MRI) const {
 161   return std::get<0>(getAction(MI, MRI)) == Legal;
 162 }
 163
 164 Optional<LLT> LegalizerInfo::findLegalType(const InstrAspect &Aspect,
 165                                  LegalizeAction Action) const {
 166   switch(Action) {
 167   default:
 168     llvm_unreachable("Cannot find legal type");
 169   case Legal:
 170   case Lower:
 171   case Libcall:
 172   case Custom:
 173     return Aspect.Type;
 174   case NarrowScalar: {
 175     return findLegalType(Aspect,
 176                          [](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
 177   }
 178   case WidenScalar: {
 179     return findLegalType(Aspect, [](LLT Ty) -> LLT {
 180       return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
 181     });
 182   }
 183   case FewerElements: {
 184     return findLegalType(Aspect,
 185                          [](LLT Ty) -> LLT { return Ty.halfElements(); });
 186   }
 187   case MoreElements: {
 188     return findLegalType(Aspect,
 189                          [](LLT Ty) -> LLT { return Ty.doubleElements(); });
 190   }
 191   }
 192 }
 193
 194 bool LegalizerInfo::legalizeCustom(MachineInstr &MI,
 195                                    MachineRegisterInfo &MRI,
 196                                    MachineIRBuilder &MIRBuilder) const {
 197   return false;
 198 }