blob: 5a15f65c45edcce8eb9e09cbc8105180633d1339 [file] [log] [blame]
Tim Northover75ad0772016-07-20 21:13:29 +00001//===---- lib/CodeGen/GlobalISel/MachineLegalizer.cpp - IRTranslator -------==//
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
Tim Northoverf8bab1c2016-08-29 21:00:00 +000020#include "llvm/CodeGen/GlobalISel/MachineLegalizer.h"
Tim Northover75ad0772016-07-20 21:13:29 +000021#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/CodeGen/ValueTypes.h"
Tim Northover75ad0772016-07-20 21:13:29 +000023#include "llvm/IR/Type.h"
24#include "llvm/Target/TargetOpcodes.h"
25using namespace llvm;
26
27MachineLegalizer::MachineLegalizer() : TablesInitialized(false) {
Tim Northover32335812016-08-04 18:35:11 +000028 // FIXME: these two can be legalized to the fundamental load/store Jakob
29 // proposed. Once loads & stores are supported.
Tim Northoverbdf67c92016-08-23 21:01:33 +000030 DefaultActions[TargetOpcode::G_ANYEXT] = Legal;
Tim Northover32335812016-08-04 18:35:11 +000031 DefaultActions[TargetOpcode::G_TRUNC] = Legal;
32
Tim Northover8d8812c2016-09-01 20:45:41 +000033 // G_TYPE and G_PHI are essentially an annotated COPY/PHI instructions so
34 // they're always legal.
Tim Northover11a23542016-08-31 21:24:02 +000035 DefaultActions[TargetOpcode::G_TYPE] = Legal;
Tim Northover8d8812c2016-09-01 20:45:41 +000036 DefaultActions[TargetOpcode::G_PHI] = Legal;
Tim Northover11a23542016-08-31 21:24:02 +000037
Tim Northoverb3a0be42016-08-23 21:01:20 +000038 DefaultActions[TargetOpcode::G_INTRINSIC] = Legal;
39 DefaultActions[TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS] = Legal;
40
Tim Northover75ad0772016-07-20 21:13:29 +000041 DefaultActions[TargetOpcode::G_ADD] = NarrowScalar;
Tim Northoverb3a0be42016-08-23 21:01:20 +000042
43 DefaultActions[TargetOpcode::G_BRCOND] = WidenScalar;
Tim Northover75ad0772016-07-20 21:13:29 +000044}
45
Tim Northover75ad0772016-07-20 21:13:29 +000046void MachineLegalizer::computeTables() {
Tim Northoverf8bab1c2016-08-29 21:00:00 +000047 for (unsigned Opcode = 0; Opcode <= LastOp - FirstOp; ++Opcode) {
48 for (unsigned Idx = 0; Idx != Actions[Opcode].size(); ++Idx) {
49 for (auto &Action : Actions[Opcode][Idx]) {
50 LLT Ty = Action.first;
51 if (!Ty.isVector())
52 continue;
Tim Northover75ad0772016-07-20 21:13:29 +000053
Tim Northoverf8bab1c2016-08-29 21:00:00 +000054 auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
55 Ty.getElementType())];
56 Entry = std::max(Entry, Ty.getNumElements());
57 }
58 }
Tim Northover75ad0772016-07-20 21:13:29 +000059 }
60
61 TablesInitialized = true;
62}
63
64// FIXME: inefficient implementation for now. Without ComputeValueVTs we're
65// probably going to need specialized lookup structures for various types before
66// we have any hope of doing well with something like <13 x i3>. Even the common
67// cases should do better than what we have now.
68std::pair<MachineLegalizer::LegalizeAction, LLT>
Tim Northovera01bece2016-08-23 19:30:42 +000069MachineLegalizer::getAction(const InstrAspect &Aspect) const {
Tim Northover75ad0772016-07-20 21:13:29 +000070 assert(TablesInitialized && "backend forgot to call computeTables");
71 // These *have* to be implemented for now, they're the fundamental basis of
72 // how everything else is transformed.
73
Tim Northover33b07d62016-07-22 20:03:43 +000074 // FIXME: the long-term plan calls for expansion in terms of load/store (if
75 // they're not legal).
Tim Northovera01bece2016-08-23 19:30:42 +000076 if (Aspect.Opcode == TargetOpcode::G_SEQUENCE ||
77 Aspect.Opcode == TargetOpcode::G_EXTRACT)
78 return std::make_pair(Legal, Aspect.Type);
Tim Northover33b07d62016-07-22 20:03:43 +000079
Tim Northoverf8bab1c2016-08-29 21:00:00 +000080 LegalizeAction Action = findInActions(Aspect);
81 if (Action != NotFound)
82 return findLegalAction(Aspect, Action);
Tim Northover75ad0772016-07-20 21:13:29 +000083
Tim Northovera01bece2016-08-23 19:30:42 +000084 unsigned Opcode = Aspect.Opcode;
85 LLT Ty = Aspect.Type;
Tim Northover75ad0772016-07-20 21:13:29 +000086 if (!Ty.isVector()) {
Tim Northovera01bece2016-08-23 19:30:42 +000087 auto DefaultAction = DefaultActions.find(Aspect.Opcode);
Tim Northover75ad0772016-07-20 21:13:29 +000088 if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
89 return std::make_pair(Legal, Ty);
90
91 assert(DefaultAction->second == NarrowScalar && "unexpected default");
Tim Northovera01bece2016-08-23 19:30:42 +000092 return findLegalAction(Aspect, NarrowScalar);
Tim Northover75ad0772016-07-20 21:13:29 +000093 }
94
95 LLT EltTy = Ty.getElementType();
96 int NumElts = Ty.getNumElements();
97
98 auto ScalarAction = ScalarInVectorActions.find(std::make_pair(Opcode, EltTy));
99 if (ScalarAction != ScalarInVectorActions.end() &&
100 ScalarAction->second != Legal)
Tim Northovera01bece2016-08-23 19:30:42 +0000101 return findLegalAction(Aspect, ScalarAction->second);
Tim Northover75ad0772016-07-20 21:13:29 +0000102
103 // The element type is legal in principle, but the number of elements is
104 // wrong.
105 auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
106 if (MaxLegalElts > NumElts)
Tim Northovera01bece2016-08-23 19:30:42 +0000107 return findLegalAction(Aspect, MoreElements);
Tim Northover75ad0772016-07-20 21:13:29 +0000108
109 if (MaxLegalElts == 0) {
110 // Scalarize if there's no legal vector type, which is just a special case
111 // of FewerElements.
112 return std::make_pair(FewerElements, EltTy);
113 }
114
Tim Northovera01bece2016-08-23 19:30:42 +0000115 return findLegalAction(Aspect, FewerElements);
Tim Northover75ad0772016-07-20 21:13:29 +0000116}
117
Tim Northovera01bece2016-08-23 19:30:42 +0000118std::tuple<MachineLegalizer::LegalizeAction, unsigned, LLT>
Ahmed Bougachaf49ab9a2016-08-02 11:41:03 +0000119MachineLegalizer::getAction(const MachineInstr &MI) const {
Tim Northovera01bece2016-08-23 19:30:42 +0000120 for (unsigned i = 0; i < MI.getNumTypes(); ++i) {
121 auto Action = getAction({MI.getOpcode(), i, MI.getType(i)});
122 if (Action.first != Legal)
Richard Smith84c4cc42016-08-23 22:21:58 +0000123 return std::make_tuple(Action.first, i, Action.second);
Tim Northovera01bece2016-08-23 19:30:42 +0000124 }
Richard Smith84c4cc42016-08-23 22:21:58 +0000125 return std::make_tuple(Legal, 0, LLT{});
Tim Northover75ad0772016-07-20 21:13:29 +0000126}
127
Ahmed Bougachaf49ab9a2016-08-02 11:41:03 +0000128bool MachineLegalizer::isLegal(const MachineInstr &MI) const {
Tim Northovera01bece2016-08-23 19:30:42 +0000129 return std::get<0>(getAction(MI)) == Legal;
Tim Northover75ad0772016-07-20 21:13:29 +0000130}
131
Tim Northovera01bece2016-08-23 19:30:42 +0000132LLT MachineLegalizer::findLegalType(const InstrAspect &Aspect,
Tim Northover75ad0772016-07-20 21:13:29 +0000133 LegalizeAction Action) const {
134 switch(Action) {
135 default:
136 llvm_unreachable("Cannot find legal type");
137 case Legal:
Tim Northovercecee562016-08-26 17:46:13 +0000138 case Lower:
Tim Northoveredb3c8c2016-08-29 19:07:16 +0000139 case Libcall:
Tim Northovera01bece2016-08-23 19:30:42 +0000140 return Aspect.Type;
Tim Northover75ad0772016-07-20 21:13:29 +0000141 case NarrowScalar: {
Tim Northovera01bece2016-08-23 19:30:42 +0000142 return findLegalType(Aspect,
Tim Northover75ad0772016-07-20 21:13:29 +0000143 [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
144 }
145 case WidenScalar: {
Tim Northovera01bece2016-08-23 19:30:42 +0000146 return findLegalType(Aspect, [&](LLT Ty) -> LLT {
Tim Northoverea904f92016-08-19 22:40:00 +0000147 return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
148 });
Tim Northover75ad0772016-07-20 21:13:29 +0000149 }
150 case FewerElements: {
Tim Northovera01bece2016-08-23 19:30:42 +0000151 return findLegalType(Aspect,
Tim Northover75ad0772016-07-20 21:13:29 +0000152 [&](LLT Ty) -> LLT { return Ty.halfElements(); });
153 }
154 case MoreElements: {
Tim Northovera01bece2016-08-23 19:30:42 +0000155 return findLegalType(Aspect,
156 [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
Tim Northover75ad0772016-07-20 21:13:29 +0000157 }
158 }
159}