LegalizeVectorOps.cpp revision 027657db7cf60bcbf40403496d7e4a170f9ce1ec 
1//===-- LegalizeVectorOps.cpp - Implement SelectionDAG::LegalizeVectors ---===//
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// This file implements the SelectionDAG::LegalizeVectors method.
11//
12// The vector legalizer looks for vector operations which might need to be
13// scalarized and legalizes them. This is a separate step from Legalize because
14// scalarizing can introduce illegal types.  For example, suppose we have an
15// ISD::SDIV of type v2i64 on x86-32.  The type is legal (for example, addition
16// on a v2i64 is legal), but ISD::SDIV isn't legal, so we have to unroll the
17// operation, which introduces nodes with the illegal type i64 which must be
18// expanded.  Similarly, suppose we have an ISD::SRA of type v16i8 on PowerPC;
19// the operation must be unrolled, which introduces nodes with the illegal
20// type i8 which must be promoted.
21//
22// This does not legalize vector manipulations like ISD::BUILD_VECTOR,
23// or operations that happen to take a vector which are custom-lowered;
24// the legalization for such operations never produces nodes
25// with illegal types, so it's okay to put off legalizing them until
26// SelectionDAG::Legalize runs.
27//
28//===----------------------------------------------------------------------===//
29
30#include "llvm/CodeGen/SelectionDAG.h"
31#include "llvm/Target/TargetLowering.h"
32using namespace llvm;
33
34namespace {
35class VectorLegalizer {
36  SelectionDAG& DAG;
37  const TargetLowering &TLI;
38  bool Changed; // Keep track of whether anything changed
39
40  /// LegalizedNodes - For nodes that are of legal width, and that have more
41  /// than one use, this map indicates what regularized operand to use.  This
42  /// allows us to avoid legalizing the same thing more than once.
43  DenseMap<SDValue, SDValue> LegalizedNodes;
44
45  // Adds a node to the translation cache
46  void AddLegalizedOperand(SDValue From, SDValue To) {
47    LegalizedNodes.insert(std::make_pair(From, To));
48    // If someone requests legalization of the new node, return itself.
49    if (From != To)
50      LegalizedNodes.insert(std::make_pair(To, To));
51  }
52
53  // Legalizes the given node
54  SDValue LegalizeOp(SDValue Op);
55  // Assuming the node is legal, "legalize" the results
56  SDValue TranslateLegalizeResults(SDValue Op, SDValue Result);
57  // Implements unrolling a VSETCC.
58  SDValue UnrollVSETCC(SDValue Op);
59  // Implements expansion for FNEG; falls back to UnrollVectorOp if FSUB
60  // isn't legal.
61  SDValue ExpandFNEG(SDValue Op);
62  // Implements vector promotion; this is essentially just bitcasting the
63  // operands to a different type and bitcasting the result back to the
64  // original type.
65  SDValue PromoteVectorOp(SDValue Op);
66
67  public:
68  bool Run();
69  VectorLegalizer(SelectionDAG& dag) :
70      DAG(dag), TLI(dag.getTargetLoweringInfo()), Changed(false) {}
71};
72
73bool VectorLegalizer::Run() {
74  // The legalize process is inherently a bottom-up recursive process (users
75  // legalize their uses before themselves).  Given infinite stack space, we
76  // could just start legalizing on the root and traverse the whole graph.  In
77  // practice however, this causes us to run out of stack space on large basic
78  // blocks.  To avoid this problem, compute an ordering of the nodes where each
79  // node is only legalized after all of its operands are legalized.
80  DAG.AssignTopologicalOrder();
81  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
82       E = prior(DAG.allnodes_end()); I != llvm::next(E); ++I)
83    LegalizeOp(SDValue(I, 0));
84
85  // Finally, it's possible the root changed.  Get the new root.
86  SDValue OldRoot = DAG.getRoot();
87  assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
88  DAG.setRoot(LegalizedNodes[OldRoot]);
89
90  LegalizedNodes.clear();
91
92  // Remove dead nodes now.
93  DAG.RemoveDeadNodes();
94
95  return Changed;
96}
97
98SDValue VectorLegalizer::TranslateLegalizeResults(SDValue Op, SDValue Result) {
99  // Generic legalization: just pass the operand through.
100  for (unsigned i = 0, e = Op.getNode()->getNumValues(); i != e; ++i)
101    AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
102  return Result.getValue(Op.getResNo());
103}
104
105SDValue VectorLegalizer::LegalizeOp(SDValue Op) {
106  // Note that LegalizeOp may be reentered even from single-use nodes, which
107  // means that we always must cache transformed nodes.
108  DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op);
109  if (I != LegalizedNodes.end()) return I->second;
110
111  SDNode* Node = Op.getNode();
112
113  // Legalize the operands
114  SmallVector<SDValue, 8> Ops;
115  for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
116    Ops.push_back(LegalizeOp(Node->getOperand(i)));
117
118  SDValue Result =
119    SDValue(DAG.UpdateNodeOperands(Op.getNode(), Ops.data(), Ops.size()), 0);
120
121  bool HasVectorValue = false;
122  for (SDNode::value_iterator J = Node->value_begin(), E = Node->value_end();
123       J != E;
124       ++J)
125    HasVectorValue |= J->isVector();
126  if (!HasVectorValue)
127    return TranslateLegalizeResults(Op, Result);
128
129  EVT QueryType;
130  switch (Op.getOpcode()) {
131  default:
132    return TranslateLegalizeResults(Op, Result);
133  case ISD::ADD:
134  case ISD::SUB:
135  case ISD::MUL:
136  case ISD::SDIV:
137  case ISD::UDIV:
138  case ISD::SREM:
139  case ISD::UREM:
140  case ISD::FADD:
141  case ISD::FSUB:
142  case ISD::FMUL:
143  case ISD::FDIV:
144  case ISD::FREM:
145  case ISD::AND:
146  case ISD::OR:
147  case ISD::XOR:
148  case ISD::SHL:
149  case ISD::SRA:
150  case ISD::SRL:
151  case ISD::ROTL:
152  case ISD::ROTR:
153  case ISD::CTTZ:
154  case ISD::CTLZ:
155  case ISD::CTPOP:
156  case ISD::SELECT:
157  case ISD::SELECT_CC:
158  case ISD::VSETCC:
159  case ISD::ZERO_EXTEND:
160  case ISD::ANY_EXTEND:
161  case ISD::TRUNCATE:
162  case ISD::SIGN_EXTEND:
163  case ISD::FP_TO_SINT:
164  case ISD::FP_TO_UINT:
165  case ISD::FNEG:
166  case ISD::FABS:
167  case ISD::FSQRT:
168  case ISD::FSIN:
169  case ISD::FCOS:
170  case ISD::FPOWI:
171  case ISD::FPOW:
172  case ISD::FLOG:
173  case ISD::FLOG2:
174  case ISD::FLOG10:
175  case ISD::FEXP:
176  case ISD::FEXP2:
177  case ISD::FCEIL:
178  case ISD::FTRUNC:
179  case ISD::FRINT:
180  case ISD::FNEARBYINT:
181  case ISD::FFLOOR:
182    QueryType = Node->getValueType(0);
183    break;
184  case ISD::SIGN_EXTEND_INREG:
185  case ISD::FP_ROUND_INREG:
186    QueryType = cast<VTSDNode>(Node->getOperand(1))->getVT();
187    break;
188  case ISD::SINT_TO_FP:
189  case ISD::UINT_TO_FP:
190    QueryType = Node->getOperand(0).getValueType();
191    break;
192  }
193
194  switch (TLI.getOperationAction(Node->getOpcode(), QueryType)) {
195  case TargetLowering::Promote:
196    // "Promote" the operation by bitcasting
197    Result = PromoteVectorOp(Op);
198    Changed = true;
199    break;
200  case TargetLowering::Legal: break;
201  case TargetLowering::Custom: {
202    SDValue Tmp1 = TLI.LowerOperation(Op, DAG);
203    if (Tmp1.getNode()) {
204      Result = Tmp1;
205      break;
206    }
207    // FALL THROUGH
208  }
209  case TargetLowering::Expand:
210    if (Node->getOpcode() == ISD::FNEG)
211      Result = ExpandFNEG(Op);
212    else if (Node->getOpcode() == ISD::VSETCC)
213      Result = UnrollVSETCC(Op);
214    else
215      Result = DAG.UnrollVectorOp(Op.getNode());
216    break;
217  }
218
219  // Make sure that the generated code is itself legal.
220  if (Result != Op) {
221    Result = LegalizeOp(Result);
222    Changed = true;
223  }
224
225  // Note that LegalizeOp may be reentered even from single-use nodes, which
226  // means that we always must cache transformed nodes.
227  AddLegalizedOperand(Op, Result);
228  return Result;
229}
230
231SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) {
232  // Vector "promotion" is basically just bitcasting and doing the operation
233  // in a different type.  For example, x86 promotes ISD::AND on v2i32 to
234  // v1i64.
235  EVT VT = Op.getValueType();
236  assert(Op.getNode()->getNumValues() == 1 &&
237         "Can't promote a vector with multiple results!");
238  EVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT);
239  DebugLoc dl = Op.getDebugLoc();
240  SmallVector<SDValue, 4> Operands(Op.getNumOperands());
241
242  for (unsigned j = 0; j != Op.getNumOperands(); ++j) {
243    if (Op.getOperand(j).getValueType().isVector())
244      Operands[j] = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Op.getOperand(j));
245    else
246      Operands[j] = Op.getOperand(j);
247  }
248
249  Op = DAG.getNode(Op.getOpcode(), dl, NVT, &Operands[0], Operands.size());
250
251  return DAG.getNode(ISD::BIT_CONVERT, dl, VT, Op);
252}
253
254SDValue VectorLegalizer::ExpandFNEG(SDValue Op) {
255  if (TLI.isOperationLegalOrCustom(ISD::FSUB, Op.getValueType())) {
256    SDValue Zero = DAG.getConstantFP(-0.0, Op.getValueType());
257    return DAG.getNode(ISD::FSUB, Op.getDebugLoc(), Op.getValueType(),
258                       Zero, Op.getOperand(0));
259  }
260  return DAG.UnrollVectorOp(Op.getNode());
261}
262
263SDValue VectorLegalizer::UnrollVSETCC(SDValue Op) {
264  EVT VT = Op.getValueType();
265  unsigned NumElems = VT.getVectorNumElements();
266  EVT EltVT = VT.getVectorElementType();
267  SDValue LHS = Op.getOperand(0), RHS = Op.getOperand(1), CC = Op.getOperand(2);
268  EVT TmpEltVT = LHS.getValueType().getVectorElementType();
269  DebugLoc dl = Op.getDebugLoc();
270  SmallVector<SDValue, 8> Ops(NumElems);
271  for (unsigned i = 0; i < NumElems; ++i) {
272    SDValue LHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, LHS,
273                                  DAG.getIntPtrConstant(i));
274    SDValue RHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, RHS,
275                                  DAG.getIntPtrConstant(i));
276    Ops[i] = DAG.getNode(ISD::SETCC, dl, TLI.getSetCCResultType(TmpEltVT),
277                         LHSElem, RHSElem, CC);
278    Ops[i] = DAG.getNode(ISD::SELECT, dl, EltVT, Ops[i],
279                         DAG.getConstant(APInt::getAllOnesValue
280                                         (EltVT.getSizeInBits()), EltVT),
281                         DAG.getConstant(0, EltVT));
282  }
283  return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], NumElems);
284}
285
286}
287
288bool SelectionDAG::LegalizeVectors() {
289  return VectorLegalizer(*this).Run();
290}
291