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