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