1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implement an interface to specify and query how an illegal operation on a
11 // given type should be expanded.
13 // Issues to be resolved:
15 // + Support weird types like i3, <7 x i3>, ...
16 // + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
18 //===----------------------------------------------------------------------===//
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"
37 LegalizerInfo::LegalizerInfo() {
38 DefaultActions[TargetOpcode::G_IMPLICIT_DEF] = NarrowScalar;
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;
45 DefaultActions[TargetOpcode::G_INTRINSIC] = Legal;
46 DefaultActions[TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS] = Legal;
48 DefaultActions[TargetOpcode::G_ADD] = NarrowScalar;
49 DefaultActions[TargetOpcode::G_LOAD] = NarrowScalar;
50 DefaultActions[TargetOpcode::G_STORE] = NarrowScalar;
52 DefaultActions[TargetOpcode::G_BRCOND] = WidenScalar;
53 DefaultActions[TargetOpcode::G_INSERT] = NarrowScalar;
54 DefaultActions[TargetOpcode::G_EXTRACT] = NarrowScalar;
55 DefaultActions[TargetOpcode::G_FNEG] = Lower;
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;
66 auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
67 Ty.getElementType())];
68 Entry = std::max(Entry, Ty.getNumElements());
73 TablesInitialized = true;
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.
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);
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());
102 if (Action != NotFound)
103 return findLegalAction(Aspect, Action);
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);
111 if (DefaultAction != DefaultActions.end() && DefaultAction->second == Lower)
112 return std::make_pair(Lower, Ty);
114 if (DefaultAction == DefaultActions.end() ||
115 DefaultAction->second != NarrowScalar)
116 return std::make_pair(Unsupported, LLT());
117 return findLegalAction(Aspect, NarrowScalar);
120 LLT EltTy = Ty.getElementType();
121 int NumElts = Ty.getNumElements();
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);
128 // The element type is legal in principle, but the number of elements is
130 auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
131 if (MaxLegalElts > NumElts)
132 return findLegalAction(Aspect, MoreElements);
134 if (MaxLegalElts == 0) {
135 // Scalarize if there's no legal vector type, which is just a special case
137 return std::make_pair(FewerElements, EltTy);
140 return findLegalAction(Aspect, FewerElements);
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())
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])
158 SeenTypes.set(TypeIdx);
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);
165 return std::make_tuple(Legal, 0, LLT{});
168 bool LegalizerInfo::isLegal(const MachineInstr &MI,
169 const MachineRegisterInfo &MRI) const {
170 return std::get<0>(getAction(MI, MRI)) == Legal;
173 Optional<LLT> LegalizerInfo::findLegalType(const InstrAspect &Aspect,
174 LegalizeAction Action) const {
177 llvm_unreachable("Cannot find legal type");
184 return findLegalizableSize(
185 Aspect, [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
188 return findLegalizableSize(Aspect, [&](LLT Ty) -> LLT {
189 return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
192 case FewerElements: {
193 return findLegalizableSize(
194 Aspect, [&](LLT Ty) -> LLT { return Ty.halfElements(); });
197 return findLegalizableSize(
198 Aspect, [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
203 bool LegalizerInfo::legalizeCustom(MachineInstr &MI,
204 MachineRegisterInfo &MRI,
205 MachineIRBuilder &MIRBuilder) const {