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_SEQUENCE ||
  79       Aspect.Opcode == TargetOpcode::G_EXTRACT ||
  80       Aspect.Opcode == TargetOpcode::G_MERGE_VALUES ||
  81       Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES)
  82     return std::make_pair(Legal, Aspect.Type);
  83
  84   LLT Ty = Aspect.Type;
  85   LegalizeAction Action = findInActions(Aspect);
  86   // LegalizerHelper is not able to handle non-power-of-2 types right now, so do
  87   // not try to legalize them unless they are marked as Legal or Custom.
  88   // FIXME: This is a temporary hack until the general non-power-of-2
  89   // legalization works.
  90   if (!isPowerOf2_64(Ty.getSizeInBits()) &&
  91       !(Action == Legal || Action == Custom))
  92     return std::make_pair(Unsupported, LLT());
  93
  94   if (Action != NotFound)
  95     return findLegalAction(Aspect, Action);
  96
  97   unsigned Opcode = Aspect.Opcode;
  98   if (!Ty.isVector()) {
  99     auto DefaultAction = DefaultActions.find(Aspect.Opcode);
 100     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
 101       return std::make_pair(Legal, Ty);
 102
 103     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Lower)
 104       return std::make_pair(Lower, Ty);
 105
 106     if (DefaultAction == DefaultActions.end() ||
 107         DefaultAction->second != NarrowScalar)
 108       return std::make_pair(Unsupported, LLT());
 109     return findLegalAction(Aspect, NarrowScalar);
 110   }
 111
 112   LLT EltTy = Ty.getElementType();
 113   int NumElts = Ty.getNumElements();
 114
 115   auto ScalarAction = ScalarInVectorActions.find(std::make_pair(Opcode, EltTy));
 116   if (ScalarAction != ScalarInVectorActions.end() &&
 117       ScalarAction->second != Legal)
 118     return findLegalAction(Aspect, ScalarAction->second);
 119
 120   // The element type is legal in principle, but the number of elements is
 121   // wrong.
 122   auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
 123   if (MaxLegalElts > NumElts)
 124     return findLegalAction(Aspect, MoreElements);
 125
 126   if (MaxLegalElts == 0) {
 127     // Scalarize if there's no legal vector type, which is just a special case
 128     // of FewerElements.
 129     return std::make_pair(FewerElements, EltTy);
 130   }
 131
 132   return findLegalAction(Aspect, FewerElements);
 133 }
 134
 135 std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
 136 LegalizerInfo::getAction(const MachineInstr &MI,
 137                          const MachineRegisterInfo &MRI) const {
 138   SmallBitVector SeenTypes(8);
 139   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
 140   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
 141     if (!OpInfo[i].isGenericType())
 142       continue;
 143
 144     // We don't want to repeatedly check the same operand index, that
 145     // could get expensive.
 146     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
 147     if (SeenTypes[TypeIdx])
 148       continue;
 149
 150     SeenTypes.set(TypeIdx);
 151
 152     LLT Ty = MRI.getType(MI.getOperand(i).getReg());
 153     auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
 154     if (Action.first != Legal)
 155       return std::make_tuple(Action.first, TypeIdx, Action.second);
 156   }
 157   return std::make_tuple(Legal, 0, LLT{});
 158 }
 159
 160 bool LegalizerInfo::isLegal(const MachineInstr &MI,
 161                             const MachineRegisterInfo &MRI) const {
 162   return std::get<0>(getAction(MI, MRI)) == Legal;
 163 }
 164
 165 Optional<LLT> LegalizerInfo::findLegalType(const InstrAspect &Aspect,
 166                                  LegalizeAction Action) const {
 167   switch(Action) {
 168   default:
 169     llvm_unreachable("Cannot find legal type");
 170   case Legal:
 171   case Lower:
 172   case Libcall:
 173   case Custom:
 174     return Aspect.Type;
 175   case NarrowScalar: {
 176     return findLegalType(Aspect,
 177                          [](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
 178   }
 179   case WidenScalar: {
 180     return findLegalType(Aspect, [](LLT Ty) -> LLT {
 181       return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
 182     });
 183   }
 184   case FewerElements: {
 185     return findLegalType(Aspect,
 186                          [](LLT Ty) -> LLT { return Ty.halfElements(); });
 187   }
 188   case MoreElements: {
 189     return findLegalType(Aspect,
 190                          [](LLT Ty) -> LLT { return Ty.doubleElements(); });
 191   }
 192   }
 193 }
 194
 195 bool LegalizerInfo::legalizeCustom(MachineInstr &MI,
 196                                    MachineRegisterInfo &MRI,
 197                                    MachineIRBuilder &MIRBuilder) const {
 198   return false;
 199 }