LegalizeDAG.cpp revision aa975c1c4785a1d7930f2cd1026cb40ce54d21e4
1//===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the SelectionDAG::Legalize method.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/SelectionDAG.h"
15#include "llvm/CodeGen/MachineFunction.h"
16#include "llvm/CodeGen/MachineFrameInfo.h"
17#include "llvm/CodeGen/MachineJumpTableInfo.h"
18#include "llvm/Target/TargetLowering.h"
19#include "llvm/Target/TargetData.h"
20#include "llvm/Target/TargetMachine.h"
21#include "llvm/Target/TargetOptions.h"
22#include "llvm/CallingConv.h"
23#include "llvm/Constants.h"
24#include "llvm/Support/MathExtras.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/Compiler.h"
27#include "llvm/ADT/SmallVector.h"
28#include <map>
29using namespace llvm;
30
31#ifndef NDEBUG
32static cl::opt<bool>
33ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
34                 cl::desc("Pop up a window to show dags before legalize"));
35#else
36static const bool ViewLegalizeDAGs = 0;
37#endif
38
39//===----------------------------------------------------------------------===//
40/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
41/// hacks on it until the target machine can handle it.  This involves
42/// eliminating value sizes the machine cannot handle (promoting small sizes to
43/// large sizes or splitting up large values into small values) as well as
44/// eliminating operations the machine cannot handle.
45///
46/// This code also does a small amount of optimization and recognition of idioms
47/// as part of its processing.  For example, if a target does not support a
48/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
49/// will attempt merge setcc and brc instructions into brcc's.
50///
51namespace {
52class VISIBILITY_HIDDEN SelectionDAGLegalize {
53  TargetLowering &TLI;
54  SelectionDAG &DAG;
55
56  // Libcall insertion helpers.
57
58  /// LastCALLSEQ_END - This keeps track of the CALLSEQ_END node that has been
59  /// legalized.  We use this to ensure that calls are properly serialized
60  /// against each other, including inserted libcalls.
61  SDOperand LastCALLSEQ_END;
62
63  /// IsLegalizingCall - This member is used *only* for purposes of providing
64  /// helpful assertions that a libcall isn't created while another call is
65  /// being legalized (which could lead to non-serialized call sequences).
66  bool IsLegalizingCall;
67
68  enum LegalizeAction {
69    Legal,      // The target natively supports this operation.
70    Promote,    // This operation should be executed in a larger type.
71    Expand      // Try to expand this to other ops, otherwise use a libcall.
72  };
73
74  /// ValueTypeActions - This is a bitvector that contains two bits for each
75  /// value type, where the two bits correspond to the LegalizeAction enum.
76  /// This can be queried with "getTypeAction(VT)".
77  TargetLowering::ValueTypeActionImpl ValueTypeActions;
78
79  /// LegalizedNodes - For nodes that are of legal width, and that have more
80  /// than one use, this map indicates what regularized operand to use.  This
81  /// allows us to avoid legalizing the same thing more than once.
82  std::map<SDOperand, SDOperand> LegalizedNodes;
83
84  /// PromotedNodes - For nodes that are below legal width, and that have more
85  /// than one use, this map indicates what promoted value to use.  This allows
86  /// us to avoid promoting the same thing more than once.
87  std::map<SDOperand, SDOperand> PromotedNodes;
88
89  /// ExpandedNodes - For nodes that need to be expanded this map indicates
90  /// which which operands are the expanded version of the input.  This allows
91  /// us to avoid expanding the same node more than once.
92  std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
93
94  /// SplitNodes - For vector nodes that need to be split, this map indicates
95  /// which which operands are the split version of the input.  This allows us
96  /// to avoid splitting the same node more than once.
97  std::map<SDOperand, std::pair<SDOperand, SDOperand> > SplitNodes;
98
99  /// PackedNodes - For nodes that need to be packed from MVT::Vector types to
100  /// concrete packed types, this contains the mapping of ones we have already
101  /// processed to the result.
102  std::map<SDOperand, SDOperand> PackedNodes;
103
104  void AddLegalizedOperand(SDOperand From, SDOperand To) {
105    LegalizedNodes.insert(std::make_pair(From, To));
106    // If someone requests legalization of the new node, return itself.
107    if (From != To)
108      LegalizedNodes.insert(std::make_pair(To, To));
109  }
110  void AddPromotedOperand(SDOperand From, SDOperand To) {
111    bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
112    assert(isNew && "Got into the map somehow?");
113    // If someone requests legalization of the new node, return itself.
114    LegalizedNodes.insert(std::make_pair(To, To));
115  }
116
117public:
118
119  SelectionDAGLegalize(SelectionDAG &DAG);
120
121  /// getTypeAction - Return how we should legalize values of this type, either
122  /// it is already legal or we need to expand it into multiple registers of
123  /// smaller integer type, or we need to promote it to a larger type.
124  LegalizeAction getTypeAction(MVT::ValueType VT) const {
125    return (LegalizeAction)ValueTypeActions.getTypeAction(VT);
126  }
127
128  /// isTypeLegal - Return true if this type is legal on this target.
129  ///
130  bool isTypeLegal(MVT::ValueType VT) const {
131    return getTypeAction(VT) == Legal;
132  }
133
134  void LegalizeDAG();
135
136private:
137  /// HandleOp - Legalize, Promote, Expand or Pack the specified operand as
138  /// appropriate for its type.
139  void HandleOp(SDOperand Op);
140
141  /// LegalizeOp - We know that the specified value has a legal type.
142  /// Recursively ensure that the operands have legal types, then return the
143  /// result.
144  SDOperand LegalizeOp(SDOperand O);
145
146  /// PromoteOp - Given an operation that produces a value in an invalid type,
147  /// promote it to compute the value into a larger type.  The produced value
148  /// will have the correct bits for the low portion of the register, but no
149  /// guarantee is made about the top bits: it may be zero, sign-extended, or
150  /// garbage.
151  SDOperand PromoteOp(SDOperand O);
152
153  /// ExpandOp - Expand the specified SDOperand into its two component pieces
154  /// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this,
155  /// the LegalizeNodes map is filled in for any results that are not expanded,
156  /// the ExpandedNodes map is filled in for any results that are expanded, and
157  /// the Lo/Hi values are returned.   This applies to integer types and Vector
158  /// types.
159  void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
160
161  /// SplitVectorOp - Given an operand of MVT::Vector type, break it down into
162  /// two smaller values of MVT::Vector type.
163  void SplitVectorOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
164
165  /// PackVectorOp - Given an operand of MVT::Vector type, convert it into the
166  /// equivalent operation that returns a packed value (e.g. MVT::V4F32).  When
167  /// this is called, we know that PackedVT is the right type for the result and
168  /// we know that this type is legal for the target.
169  SDOperand PackVectorOp(SDOperand O, MVT::ValueType PackedVT);
170
171  /// isShuffleLegal - Return true if a vector shuffle is legal with the
172  /// specified mask and type.  Targets can specify exactly which masks they
173  /// support and the code generator is tasked with not creating illegal masks.
174  ///
175  /// Note that this will also return true for shuffles that are promoted to a
176  /// different type.
177  ///
178  /// If this is a legal shuffle, this method returns the (possibly promoted)
179  /// build_vector Mask.  If it's not a legal shuffle, it returns null.
180  SDNode *isShuffleLegal(MVT::ValueType VT, SDOperand Mask) const;
181
182  bool LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest,
183                                    std::set<SDNode*> &NodesLeadingTo);
184
185  void LegalizeSetCCOperands(SDOperand &LHS, SDOperand &RHS, SDOperand &CC);
186
187  SDOperand CreateStackTemporary(MVT::ValueType VT);
188
189  SDOperand ExpandLibCall(const char *Name, SDNode *Node,
190                          SDOperand &Hi);
191  SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy,
192                          SDOperand Source);
193
194  SDOperand ExpandBIT_CONVERT(MVT::ValueType DestVT, SDOperand SrcOp);
195  SDOperand ExpandBUILD_VECTOR(SDNode *Node);
196  SDOperand ExpandSCALAR_TO_VECTOR(SDNode *Node);
197  SDOperand ExpandLegalINT_TO_FP(bool isSigned,
198                                 SDOperand LegalOp,
199                                 MVT::ValueType DestVT);
200  SDOperand PromoteLegalINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT,
201                                  bool isSigned);
202  SDOperand PromoteLegalFP_TO_INT(SDOperand LegalOp, MVT::ValueType DestVT,
203                                  bool isSigned);
204
205  SDOperand ExpandBSWAP(SDOperand Op);
206  SDOperand ExpandBitCount(unsigned Opc, SDOperand Op);
207  bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
208                   SDOperand &Lo, SDOperand &Hi);
209  void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
210                        SDOperand &Lo, SDOperand &Hi);
211
212  SDOperand LowerVEXTRACT_VECTOR_ELT(SDOperand Op);
213  SDOperand ExpandEXTRACT_VECTOR_ELT(SDOperand Op);
214
215  SDOperand getIntPtrConstant(uint64_t Val) {
216    return DAG.getConstant(Val, TLI.getPointerTy());
217  }
218};
219}
220
221/// isVectorShuffleLegal - Return true if a vector shuffle is legal with the
222/// specified mask and type.  Targets can specify exactly which masks they
223/// support and the code generator is tasked with not creating illegal masks.
224///
225/// Note that this will also return true for shuffles that are promoted to a
226/// different type.
227SDNode *SelectionDAGLegalize::isShuffleLegal(MVT::ValueType VT,
228                                             SDOperand Mask) const {
229  switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, VT)) {
230  default: return 0;
231  case TargetLowering::Legal:
232  case TargetLowering::Custom:
233    break;
234  case TargetLowering::Promote: {
235    // If this is promoted to a different type, convert the shuffle mask and
236    // ask if it is legal in the promoted type!
237    MVT::ValueType NVT = TLI.getTypeToPromoteTo(ISD::VECTOR_SHUFFLE, VT);
238
239    // If we changed # elements, change the shuffle mask.
240    unsigned NumEltsGrowth =
241      MVT::getVectorNumElements(NVT) / MVT::getVectorNumElements(VT);
242    assert(NumEltsGrowth && "Cannot promote to vector type with fewer elts!");
243    if (NumEltsGrowth > 1) {
244      // Renumber the elements.
245      SmallVector<SDOperand, 8> Ops;
246      for (unsigned i = 0, e = Mask.getNumOperands(); i != e; ++i) {
247        SDOperand InOp = Mask.getOperand(i);
248        for (unsigned j = 0; j != NumEltsGrowth; ++j) {
249          if (InOp.getOpcode() == ISD::UNDEF)
250            Ops.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
251          else {
252            unsigned InEltNo = cast<ConstantSDNode>(InOp)->getValue();
253            Ops.push_back(DAG.getConstant(InEltNo*NumEltsGrowth+j, MVT::i32));
254          }
255        }
256      }
257      Mask = DAG.getNode(ISD::BUILD_VECTOR, NVT, &Ops[0], Ops.size());
258    }
259    VT = NVT;
260    break;
261  }
262  }
263  return TLI.isShuffleMaskLegal(Mask, VT) ? Mask.Val : 0;
264}
265
266/// getScalarizedOpcode - Return the scalar opcode that corresponds to the
267/// specified vector opcode.
268static unsigned getScalarizedOpcode(unsigned VecOp, MVT::ValueType VT) {
269  switch (VecOp) {
270  default: assert(0 && "Don't know how to scalarize this opcode!");
271  case ISD::VADD:  return MVT::isInteger(VT) ? ISD::ADD : ISD::FADD;
272  case ISD::VSUB:  return MVT::isInteger(VT) ? ISD::SUB : ISD::FSUB;
273  case ISD::VMUL:  return MVT::isInteger(VT) ? ISD::MUL : ISD::FMUL;
274  case ISD::VSDIV: return MVT::isInteger(VT) ? ISD::SDIV: ISD::FDIV;
275  case ISD::VUDIV: return MVT::isInteger(VT) ? ISD::UDIV: ISD::FDIV;
276  case ISD::VAND:  return MVT::isInteger(VT) ? ISD::AND : 0;
277  case ISD::VOR:   return MVT::isInteger(VT) ? ISD::OR  : 0;
278  case ISD::VXOR:  return MVT::isInteger(VT) ? ISD::XOR : 0;
279  }
280}
281
282SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
283  : TLI(dag.getTargetLoweringInfo()), DAG(dag),
284    ValueTypeActions(TLI.getValueTypeActions()) {
285  assert(MVT::LAST_VALUETYPE <= 32 &&
286         "Too many value types for ValueTypeActions to hold!");
287}
288
289/// ComputeTopDownOrdering - Add the specified node to the Order list if it has
290/// not been visited yet and if all of its operands have already been visited.
291static void ComputeTopDownOrdering(SDNode *N, std::vector<SDNode*> &Order,
292                                   std::map<SDNode*, unsigned> &Visited) {
293  if (++Visited[N] != N->getNumOperands())
294    return;  // Haven't visited all operands yet
295
296  Order.push_back(N);
297
298  if (N->hasOneUse()) { // Tail recurse in common case.
299    ComputeTopDownOrdering(*N->use_begin(), Order, Visited);
300    return;
301  }
302
303  // Now that we have N in, add anything that uses it if all of their operands
304  // are now done.
305  for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); UI != E;++UI)
306    ComputeTopDownOrdering(*UI, Order, Visited);
307}
308
309
310void SelectionDAGLegalize::LegalizeDAG() {
311  LastCALLSEQ_END = DAG.getEntryNode();
312  IsLegalizingCall = false;
313
314  // The legalize process is inherently a bottom-up recursive process (users
315  // legalize their uses before themselves).  Given infinite stack space, we
316  // could just start legalizing on the root and traverse the whole graph.  In
317  // practice however, this causes us to run out of stack space on large basic
318  // blocks.  To avoid this problem, compute an ordering of the nodes where each
319  // node is only legalized after all of its operands are legalized.
320  std::map<SDNode*, unsigned> Visited;
321  std::vector<SDNode*> Order;
322
323  // Compute ordering from all of the leaves in the graphs, those (like the
324  // entry node) that have no operands.
325  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
326       E = DAG.allnodes_end(); I != E; ++I) {
327    if (I->getNumOperands() == 0) {
328      Visited[I] = 0 - 1U;
329      ComputeTopDownOrdering(I, Order, Visited);
330    }
331  }
332
333  assert(Order.size() == Visited.size() &&
334         Order.size() ==
335            (unsigned)std::distance(DAG.allnodes_begin(), DAG.allnodes_end()) &&
336         "Error: DAG is cyclic!");
337  Visited.clear();
338
339  for (unsigned i = 0, e = Order.size(); i != e; ++i)
340    HandleOp(SDOperand(Order[i], 0));
341
342  // Finally, it's possible the root changed.  Get the new root.
343  SDOperand OldRoot = DAG.getRoot();
344  assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
345  DAG.setRoot(LegalizedNodes[OldRoot]);
346
347  ExpandedNodes.clear();
348  LegalizedNodes.clear();
349  PromotedNodes.clear();
350  SplitNodes.clear();
351  PackedNodes.clear();
352
353  // Remove dead nodes now.
354  DAG.RemoveDeadNodes();
355}
356
357
358/// FindCallEndFromCallStart - Given a chained node that is part of a call
359/// sequence, find the CALLSEQ_END node that terminates the call sequence.
360static SDNode *FindCallEndFromCallStart(SDNode *Node) {
361  if (Node->getOpcode() == ISD::CALLSEQ_END)
362    return Node;
363  if (Node->use_empty())
364    return 0;   // No CallSeqEnd
365
366  // The chain is usually at the end.
367  SDOperand TheChain(Node, Node->getNumValues()-1);
368  if (TheChain.getValueType() != MVT::Other) {
369    // Sometimes it's at the beginning.
370    TheChain = SDOperand(Node, 0);
371    if (TheChain.getValueType() != MVT::Other) {
372      // Otherwise, hunt for it.
373      for (unsigned i = 1, e = Node->getNumValues(); i != e; ++i)
374        if (Node->getValueType(i) == MVT::Other) {
375          TheChain = SDOperand(Node, i);
376          break;
377        }
378
379      // Otherwise, we walked into a node without a chain.
380      if (TheChain.getValueType() != MVT::Other)
381        return 0;
382    }
383  }
384
385  for (SDNode::use_iterator UI = Node->use_begin(),
386       E = Node->use_end(); UI != E; ++UI) {
387
388    // Make sure to only follow users of our token chain.
389    SDNode *User = *UI;
390    for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
391      if (User->getOperand(i) == TheChain)
392        if (SDNode *Result = FindCallEndFromCallStart(User))
393          return Result;
394  }
395  return 0;
396}
397
398/// FindCallStartFromCallEnd - Given a chained node that is part of a call
399/// sequence, find the CALLSEQ_START node that initiates the call sequence.
400static SDNode *FindCallStartFromCallEnd(SDNode *Node) {
401  assert(Node && "Didn't find callseq_start for a call??");
402  if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
403
404  assert(Node->getOperand(0).getValueType() == MVT::Other &&
405         "Node doesn't have a token chain argument!");
406  return FindCallStartFromCallEnd(Node->getOperand(0).Val);
407}
408
409/// LegalizeAllNodesNotLeadingTo - Recursively walk the uses of N, looking to
410/// see if any uses can reach Dest.  If no dest operands can get to dest,
411/// legalize them, legalize ourself, and return false, otherwise, return true.
412///
413/// Keep track of the nodes we fine that actually do lead to Dest in
414/// NodesLeadingTo.  This avoids retraversing them exponential number of times.
415///
416bool SelectionDAGLegalize::LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest,
417                                            std::set<SDNode*> &NodesLeadingTo) {
418  if (N == Dest) return true;  // N certainly leads to Dest :)
419
420  // If we've already processed this node and it does lead to Dest, there is no
421  // need to reprocess it.
422  if (NodesLeadingTo.count(N)) return true;
423
424  // If the first result of this node has been already legalized, then it cannot
425  // reach N.
426  switch (getTypeAction(N->getValueType(0))) {
427  case Legal:
428    if (LegalizedNodes.count(SDOperand(N, 0))) return false;
429    break;
430  case Promote:
431    if (PromotedNodes.count(SDOperand(N, 0))) return false;
432    break;
433  case Expand:
434    if (ExpandedNodes.count(SDOperand(N, 0))) return false;
435    break;
436  }
437
438  // Okay, this node has not already been legalized.  Check and legalize all
439  // operands.  If none lead to Dest, then we can legalize this node.
440  bool OperandsLeadToDest = false;
441  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
442    OperandsLeadToDest |=     // If an operand leads to Dest, so do we.
443      LegalizeAllNodesNotLeadingTo(N->getOperand(i).Val, Dest, NodesLeadingTo);
444
445  if (OperandsLeadToDest) {
446    NodesLeadingTo.insert(N);
447    return true;
448  }
449
450  // Okay, this node looks safe, legalize it and return false.
451  HandleOp(SDOperand(N, 0));
452  return false;
453}
454
455/// HandleOp - Legalize, Promote, Expand or Pack the specified operand as
456/// appropriate for its type.
457void SelectionDAGLegalize::HandleOp(SDOperand Op) {
458  switch (getTypeAction(Op.getValueType())) {
459  default: assert(0 && "Bad type action!");
460  case Legal:   LegalizeOp(Op); break;
461  case Promote: PromoteOp(Op);  break;
462  case Expand:
463    if (Op.getValueType() != MVT::Vector) {
464      SDOperand X, Y;
465      ExpandOp(Op, X, Y);
466    } else {
467      SDNode *N = Op.Val;
468      unsigned NumOps = N->getNumOperands();
469      unsigned NumElements =
470        cast<ConstantSDNode>(N->getOperand(NumOps-2))->getValue();
471      MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(NumOps-1))->getVT();
472      MVT::ValueType PackedVT = getVectorType(EVT, NumElements);
473      if (PackedVT != MVT::Other && TLI.isTypeLegal(PackedVT)) {
474        // In the common case, this is a legal vector type, convert it to the
475        // packed operation and type now.
476        PackVectorOp(Op, PackedVT);
477      } else if (NumElements == 1) {
478        // Otherwise, if this is a single element vector, convert it to a
479        // scalar operation.
480        PackVectorOp(Op, EVT);
481      } else {
482        // Otherwise, this is a multiple element vector that isn't supported.
483        // Split it in half and legalize both parts.
484        SDOperand X, Y;
485        SplitVectorOp(Op, X, Y);
486      }
487    }
488    break;
489  }
490}
491
492/// ExpandConstantFP - Expands the ConstantFP node to an integer constant or
493/// a load from the constant pool.
494static SDOperand ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP,
495                                  SelectionDAG &DAG, TargetLowering &TLI) {
496  bool Extend = false;
497
498  // If a FP immediate is precise when represented as a float and if the
499  // target can do an extending load from float to double, we put it into
500  // the constant pool as a float, even if it's is statically typed as a
501  // double.
502  MVT::ValueType VT = CFP->getValueType(0);
503  bool isDouble = VT == MVT::f64;
504  ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
505                                      Type::FloatTy, CFP->getValue());
506  if (!UseCP) {
507    double Val = LLVMC->getValue();
508    return isDouble
509      ? DAG.getConstant(DoubleToBits(Val), MVT::i64)
510      : DAG.getConstant(FloatToBits(Val), MVT::i32);
511  }
512
513  if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) &&
514      // Only do this if the target has a native EXTLOAD instruction from f32.
515      TLI.isLoadXLegal(ISD::EXTLOAD, MVT::f32)) {
516    LLVMC = cast<ConstantFP>(ConstantExpr::getFPTrunc(LLVMC,Type::FloatTy));
517    VT = MVT::f32;
518    Extend = true;
519  }
520
521  SDOperand CPIdx = DAG.getConstantPool(LLVMC, TLI.getPointerTy());
522  if (Extend) {
523    return DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
524                          CPIdx, NULL, 0, MVT::f32);
525  } else {
526    return DAG.getLoad(VT, DAG.getEntryNode(), CPIdx, NULL, 0);
527  }
528}
529
530
531/// LegalizeOp - We know that the specified value has a legal type.
532/// Recursively ensure that the operands have legal types, then return the
533/// result.
534SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
535  assert(isTypeLegal(Op.getValueType()) &&
536         "Caller should expand or promote operands that are not legal!");
537  SDNode *Node = Op.Val;
538
539  // If this operation defines any values that cannot be represented in a
540  // register on this target, make sure to expand or promote them.
541  if (Node->getNumValues() > 1) {
542    for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
543      if (getTypeAction(Node->getValueType(i)) != Legal) {
544        HandleOp(Op.getValue(i));
545        assert(LegalizedNodes.count(Op) &&
546               "Handling didn't add legal operands!");
547        return LegalizedNodes[Op];
548      }
549  }
550
551  // Note that LegalizeOp may be reentered even from single-use nodes, which
552  // means that we always must cache transformed nodes.
553  std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
554  if (I != LegalizedNodes.end()) return I->second;
555
556  SDOperand Tmp1, Tmp2, Tmp3, Tmp4;
557  SDOperand Result = Op;
558  bool isCustom = false;
559
560  switch (Node->getOpcode()) {
561  case ISD::FrameIndex:
562  case ISD::EntryToken:
563  case ISD::Register:
564  case ISD::BasicBlock:
565  case ISD::TargetFrameIndex:
566  case ISD::TargetJumpTable:
567  case ISD::TargetConstant:
568  case ISD::TargetConstantFP:
569  case ISD::TargetConstantPool:
570  case ISD::TargetGlobalAddress:
571  case ISD::TargetExternalSymbol:
572  case ISD::VALUETYPE:
573  case ISD::SRCVALUE:
574  case ISD::STRING:
575  case ISD::CONDCODE:
576  case ISD::GLOBAL_OFFSET_TABLE:
577    // Primitives must all be legal.
578    assert(TLI.isOperationLegal(Node->getValueType(0), Node->getValueType(0)) &&
579           "This must be legal!");
580    break;
581  default:
582    if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
583      // If this is a target node, legalize it by legalizing the operands then
584      // passing it through.
585      SmallVector<SDOperand, 8> Ops;
586      for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
587        Ops.push_back(LegalizeOp(Node->getOperand(i)));
588
589      Result = DAG.UpdateNodeOperands(Result.getValue(0), &Ops[0], Ops.size());
590
591      for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
592        AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
593      return Result.getValue(Op.ResNo);
594    }
595    // Otherwise this is an unhandled builtin node.  splat.
596#ifndef NDEBUG
597    cerr << "NODE: "; Node->dump(); cerr << "\n";
598#endif
599    assert(0 && "Do not know how to legalize this operator!");
600    abort();
601  case ISD::GlobalAddress:
602  case ISD::ExternalSymbol:
603  case ISD::ConstantPool:
604  case ISD::JumpTable: // Nothing to do.
605    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
606    default: assert(0 && "This action is not supported yet!");
607    case TargetLowering::Custom:
608      Tmp1 = TLI.LowerOperation(Op, DAG);
609      if (Tmp1.Val) Result = Tmp1;
610      // FALLTHROUGH if the target doesn't want to lower this op after all.
611    case TargetLowering::Legal:
612      break;
613    }
614    break;
615  case ISD::AssertSext:
616  case ISD::AssertZext:
617    Tmp1 = LegalizeOp(Node->getOperand(0));
618    Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
619    break;
620  case ISD::MERGE_VALUES:
621    // Legalize eliminates MERGE_VALUES nodes.
622    Result = Node->getOperand(Op.ResNo);
623    break;
624  case ISD::CopyFromReg:
625    Tmp1 = LegalizeOp(Node->getOperand(0));
626    Result = Op.getValue(0);
627    if (Node->getNumValues() == 2) {
628      Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
629    } else {
630      assert(Node->getNumValues() == 3 && "Invalid copyfromreg!");
631      if (Node->getNumOperands() == 3) {
632        Tmp2 = LegalizeOp(Node->getOperand(2));
633        Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
634      } else {
635        Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
636      }
637      AddLegalizedOperand(Op.getValue(2), Result.getValue(2));
638    }
639    // Since CopyFromReg produces two values, make sure to remember that we
640    // legalized both of them.
641    AddLegalizedOperand(Op.getValue(0), Result);
642    AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
643    return Result.getValue(Op.ResNo);
644  case ISD::UNDEF: {
645    MVT::ValueType VT = Op.getValueType();
646    switch (TLI.getOperationAction(ISD::UNDEF, VT)) {
647    default: assert(0 && "This action is not supported yet!");
648    case TargetLowering::Expand:
649      if (MVT::isInteger(VT))
650        Result = DAG.getConstant(0, VT);
651      else if (MVT::isFloatingPoint(VT))
652        Result = DAG.getConstantFP(0, VT);
653      else
654        assert(0 && "Unknown value type!");
655      break;
656    case TargetLowering::Legal:
657      break;
658    }
659    break;
660  }
661
662  case ISD::INTRINSIC_W_CHAIN:
663  case ISD::INTRINSIC_WO_CHAIN:
664  case ISD::INTRINSIC_VOID: {
665    SmallVector<SDOperand, 8> Ops;
666    for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
667      Ops.push_back(LegalizeOp(Node->getOperand(i)));
668    Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
669
670    // Allow the target to custom lower its intrinsics if it wants to.
671    if (TLI.getOperationAction(Node->getOpcode(), MVT::Other) ==
672        TargetLowering::Custom) {
673      Tmp3 = TLI.LowerOperation(Result, DAG);
674      if (Tmp3.Val) Result = Tmp3;
675    }
676
677    if (Result.Val->getNumValues() == 1) break;
678
679    // Must have return value and chain result.
680    assert(Result.Val->getNumValues() == 2 &&
681           "Cannot return more than two values!");
682
683    // Since loads produce two values, make sure to remember that we
684    // legalized both of them.
685    AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
686    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
687    return Result.getValue(Op.ResNo);
688  }
689
690  case ISD::LOCATION:
691    assert(Node->getNumOperands() == 5 && "Invalid LOCATION node!");
692    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the input chain.
693
694    switch (TLI.getOperationAction(ISD::LOCATION, MVT::Other)) {
695    case TargetLowering::Promote:
696    default: assert(0 && "This action is not supported yet!");
697    case TargetLowering::Expand: {
698      MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo();
699      bool useDEBUG_LOC = TLI.isOperationLegal(ISD::DEBUG_LOC, MVT::Other);
700      bool useDEBUG_LABEL = TLI.isOperationLegal(ISD::DEBUG_LABEL, MVT::Other);
701
702      if (DebugInfo && (useDEBUG_LOC || useDEBUG_LABEL)) {
703        const std::string &FName =
704          cast<StringSDNode>(Node->getOperand(3))->getValue();
705        const std::string &DirName =
706          cast<StringSDNode>(Node->getOperand(4))->getValue();
707        unsigned SrcFile = DebugInfo->RecordSource(DirName, FName);
708
709        SmallVector<SDOperand, 8> Ops;
710        Ops.push_back(Tmp1);  // chain
711        SDOperand LineOp = Node->getOperand(1);
712        SDOperand ColOp = Node->getOperand(2);
713
714        if (useDEBUG_LOC) {
715          Ops.push_back(LineOp);  // line #
716          Ops.push_back(ColOp);  // col #
717          Ops.push_back(DAG.getConstant(SrcFile, MVT::i32));  // source file id
718          Result = DAG.getNode(ISD::DEBUG_LOC, MVT::Other, &Ops[0], Ops.size());
719        } else {
720          unsigned Line = cast<ConstantSDNode>(LineOp)->getValue();
721          unsigned Col = cast<ConstantSDNode>(ColOp)->getValue();
722          unsigned ID = DebugInfo->RecordLabel(Line, Col, SrcFile);
723          Ops.push_back(DAG.getConstant(ID, MVT::i32));
724          Result = DAG.getNode(ISD::DEBUG_LABEL, MVT::Other,&Ops[0],Ops.size());
725        }
726      } else {
727        Result = Tmp1;  // chain
728      }
729      break;
730    }
731    case TargetLowering::Legal:
732      if (Tmp1 != Node->getOperand(0) ||
733          getTypeAction(Node->getOperand(1).getValueType()) == Promote) {
734        SmallVector<SDOperand, 8> Ops;
735        Ops.push_back(Tmp1);
736        if (getTypeAction(Node->getOperand(1).getValueType()) == Legal) {
737          Ops.push_back(Node->getOperand(1));  // line # must be legal.
738          Ops.push_back(Node->getOperand(2));  // col # must be legal.
739        } else {
740          // Otherwise promote them.
741          Ops.push_back(PromoteOp(Node->getOperand(1)));
742          Ops.push_back(PromoteOp(Node->getOperand(2)));
743        }
744        Ops.push_back(Node->getOperand(3));  // filename must be legal.
745        Ops.push_back(Node->getOperand(4));  // working dir # must be legal.
746        Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
747      }
748      break;
749    }
750    break;
751
752  case ISD::DEBUG_LOC:
753    assert(Node->getNumOperands() == 4 && "Invalid DEBUG_LOC node!");
754    switch (TLI.getOperationAction(ISD::DEBUG_LOC, MVT::Other)) {
755    default: assert(0 && "This action is not supported yet!");
756    case TargetLowering::Legal:
757      Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
758      Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the line #.
759      Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the col #.
760      Tmp4 = LegalizeOp(Node->getOperand(3));  // Legalize the source file id.
761      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4);
762      break;
763    }
764    break;
765
766  case ISD::DEBUG_LABEL:
767    assert(Node->getNumOperands() == 2 && "Invalid DEBUG_LABEL node!");
768    switch (TLI.getOperationAction(ISD::DEBUG_LABEL, MVT::Other)) {
769    default: assert(0 && "This action is not supported yet!");
770    case TargetLowering::Legal:
771      Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
772      Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the label id.
773      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
774      break;
775    }
776    break;
777
778  case ISD::Constant:
779    // We know we don't need to expand constants here, constants only have one
780    // value and we check that it is fine above.
781
782    // FIXME: Maybe we should handle things like targets that don't support full
783    // 32-bit immediates?
784    break;
785  case ISD::ConstantFP: {
786    // Spill FP immediates to the constant pool if the target cannot directly
787    // codegen them.  Targets often have some immediate values that can be
788    // efficiently generated into an FP register without a load.  We explicitly
789    // leave these constants as ConstantFP nodes for the target to deal with.
790    ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
791
792    // Check to see if this FP immediate is already legal.
793    bool isLegal = false;
794    for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
795           E = TLI.legal_fpimm_end(); I != E; ++I)
796      if (CFP->isExactlyValue(*I)) {
797        isLegal = true;
798        break;
799      }
800
801    // If this is a legal constant, turn it into a TargetConstantFP node.
802    if (isLegal) {
803      Result = DAG.getTargetConstantFP(CFP->getValue(), CFP->getValueType(0));
804      break;
805    }
806
807    switch (TLI.getOperationAction(ISD::ConstantFP, CFP->getValueType(0))) {
808    default: assert(0 && "This action is not supported yet!");
809    case TargetLowering::Custom:
810      Tmp3 = TLI.LowerOperation(Result, DAG);
811      if (Tmp3.Val) {
812        Result = Tmp3;
813        break;
814      }
815      // FALLTHROUGH
816    case TargetLowering::Expand:
817      Result = ExpandConstantFP(CFP, true, DAG, TLI);
818    }
819    break;
820  }
821  case ISD::TokenFactor:
822    if (Node->getNumOperands() == 2) {
823      Tmp1 = LegalizeOp(Node->getOperand(0));
824      Tmp2 = LegalizeOp(Node->getOperand(1));
825      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
826    } else if (Node->getNumOperands() == 3) {
827      Tmp1 = LegalizeOp(Node->getOperand(0));
828      Tmp2 = LegalizeOp(Node->getOperand(1));
829      Tmp3 = LegalizeOp(Node->getOperand(2));
830      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
831    } else {
832      SmallVector<SDOperand, 8> Ops;
833      // Legalize the operands.
834      for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
835        Ops.push_back(LegalizeOp(Node->getOperand(i)));
836      Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
837    }
838    break;
839
840  case ISD::FORMAL_ARGUMENTS:
841  case ISD::CALL:
842    // The only option for this is to custom lower it.
843    Tmp3 = TLI.LowerOperation(Result.getValue(0), DAG);
844    assert(Tmp3.Val && "Target didn't custom lower this node!");
845    assert(Tmp3.Val->getNumValues() == Result.Val->getNumValues() &&
846           "Lowering call/formal_arguments produced unexpected # results!");
847
848    // Since CALL/FORMAL_ARGUMENTS nodes produce multiple values, make sure to
849    // remember that we legalized all of them, so it doesn't get relegalized.
850    for (unsigned i = 0, e = Tmp3.Val->getNumValues(); i != e; ++i) {
851      Tmp1 = LegalizeOp(Tmp3.getValue(i));
852      if (Op.ResNo == i)
853        Tmp2 = Tmp1;
854      AddLegalizedOperand(SDOperand(Node, i), Tmp1);
855    }
856    return Tmp2;
857
858  case ISD::BUILD_VECTOR:
859    switch (TLI.getOperationAction(ISD::BUILD_VECTOR, Node->getValueType(0))) {
860    default: assert(0 && "This action is not supported yet!");
861    case TargetLowering::Custom:
862      Tmp3 = TLI.LowerOperation(Result, DAG);
863      if (Tmp3.Val) {
864        Result = Tmp3;
865        break;
866      }
867      // FALLTHROUGH
868    case TargetLowering::Expand:
869      Result = ExpandBUILD_VECTOR(Result.Val);
870      break;
871    }
872    break;
873  case ISD::INSERT_VECTOR_ELT:
874    Tmp1 = LegalizeOp(Node->getOperand(0));  // InVec
875    Tmp2 = LegalizeOp(Node->getOperand(1));  // InVal
876    Tmp3 = LegalizeOp(Node->getOperand(2));  // InEltNo
877    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
878
879    switch (TLI.getOperationAction(ISD::INSERT_VECTOR_ELT,
880                                   Node->getValueType(0))) {
881    default: assert(0 && "This action is not supported yet!");
882    case TargetLowering::Legal:
883      break;
884    case TargetLowering::Custom:
885      Tmp3 = TLI.LowerOperation(Result, DAG);
886      if (Tmp3.Val) {
887        Result = Tmp3;
888        break;
889      }
890      // FALLTHROUGH
891    case TargetLowering::Expand: {
892      // If the insert index is a constant, codegen this as a scalar_to_vector,
893      // then a shuffle that inserts it into the right position in the vector.
894      if (ConstantSDNode *InsertPos = dyn_cast<ConstantSDNode>(Tmp3)) {
895        SDOperand ScVec = DAG.getNode(ISD::SCALAR_TO_VECTOR,
896                                      Tmp1.getValueType(), Tmp2);
897
898        unsigned NumElts = MVT::getVectorNumElements(Tmp1.getValueType());
899        MVT::ValueType ShufMaskVT = MVT::getIntVectorWithNumElements(NumElts);
900        MVT::ValueType ShufMaskEltVT = MVT::getVectorBaseType(ShufMaskVT);
901
902        // We generate a shuffle of InVec and ScVec, so the shuffle mask should
903        // be 0,1,2,3,4,5... with the appropriate element replaced with elt 0 of
904        // the RHS.
905        SmallVector<SDOperand, 8> ShufOps;
906        for (unsigned i = 0; i != NumElts; ++i) {
907          if (i != InsertPos->getValue())
908            ShufOps.push_back(DAG.getConstant(i, ShufMaskEltVT));
909          else
910            ShufOps.push_back(DAG.getConstant(NumElts, ShufMaskEltVT));
911        }
912        SDOperand ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMaskVT,
913                                         &ShufOps[0], ShufOps.size());
914
915        Result = DAG.getNode(ISD::VECTOR_SHUFFLE, Tmp1.getValueType(),
916                             Tmp1, ScVec, ShufMask);
917        Result = LegalizeOp(Result);
918        break;
919      }
920
921      // If the target doesn't support this, we have to spill the input vector
922      // to a temporary stack slot, update the element, then reload it.  This is
923      // badness.  We could also load the value into a vector register (either
924      // with a "move to register" or "extload into register" instruction, then
925      // permute it into place, if the idx is a constant and if the idx is
926      // supported by the target.
927      MVT::ValueType VT    = Tmp1.getValueType();
928      MVT::ValueType EltVT = Tmp2.getValueType();
929      MVT::ValueType IdxVT = Tmp3.getValueType();
930      MVT::ValueType PtrVT = TLI.getPointerTy();
931      SDOperand StackPtr = CreateStackTemporary(VT);
932      // Store the vector.
933      SDOperand Ch = DAG.getStore(DAG.getEntryNode(), Tmp1, StackPtr, NULL, 0);
934
935      // Truncate or zero extend offset to target pointer type.
936      unsigned CastOpc = (IdxVT > PtrVT) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
937      Tmp3 = DAG.getNode(CastOpc, PtrVT, Tmp3);
938      // Add the offset to the index.
939      unsigned EltSize = MVT::getSizeInBits(EltVT)/8;
940      Tmp3 = DAG.getNode(ISD::MUL, IdxVT, Tmp3,DAG.getConstant(EltSize, IdxVT));
941      SDOperand StackPtr2 = DAG.getNode(ISD::ADD, IdxVT, Tmp3, StackPtr);
942      // Store the scalar value.
943      Ch = DAG.getStore(Ch, Tmp2, StackPtr2, NULL, 0);
944      // Load the updated vector.
945      Result = DAG.getLoad(VT, Ch, StackPtr, NULL, 0);
946      break;
947    }
948    }
949    break;
950  case ISD::SCALAR_TO_VECTOR:
951    if (!TLI.isTypeLegal(Node->getOperand(0).getValueType())) {
952      Result = LegalizeOp(ExpandSCALAR_TO_VECTOR(Node));
953      break;
954    }
955
956    Tmp1 = LegalizeOp(Node->getOperand(0));  // InVal
957    Result = DAG.UpdateNodeOperands(Result, Tmp1);
958    switch (TLI.getOperationAction(ISD::SCALAR_TO_VECTOR,
959                                   Node->getValueType(0))) {
960    default: assert(0 && "This action is not supported yet!");
961    case TargetLowering::Legal:
962      break;
963    case TargetLowering::Custom:
964      Tmp3 = TLI.LowerOperation(Result, DAG);
965      if (Tmp3.Val) {
966        Result = Tmp3;
967        break;
968      }
969      // FALLTHROUGH
970    case TargetLowering::Expand:
971      Result = LegalizeOp(ExpandSCALAR_TO_VECTOR(Node));
972      break;
973    }
974    break;
975  case ISD::VECTOR_SHUFFLE:
976    Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the input vectors,
977    Tmp2 = LegalizeOp(Node->getOperand(1));   // but not the shuffle mask.
978    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
979
980    // Allow targets to custom lower the SHUFFLEs they support.
981    switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE,Result.getValueType())) {
982    default: assert(0 && "Unknown operation action!");
983    case TargetLowering::Legal:
984      assert(isShuffleLegal(Result.getValueType(), Node->getOperand(2)) &&
985             "vector shuffle should not be created if not legal!");
986      break;
987    case TargetLowering::Custom:
988      Tmp3 = TLI.LowerOperation(Result, DAG);
989      if (Tmp3.Val) {
990        Result = Tmp3;
991        break;
992      }
993      // FALLTHROUGH
994    case TargetLowering::Expand: {
995      MVT::ValueType VT = Node->getValueType(0);
996      MVT::ValueType EltVT = MVT::getVectorBaseType(VT);
997      MVT::ValueType PtrVT = TLI.getPointerTy();
998      SDOperand Mask = Node->getOperand(2);
999      unsigned NumElems = Mask.getNumOperands();
1000      SmallVector<SDOperand,8> Ops;
1001      for (unsigned i = 0; i != NumElems; ++i) {
1002        SDOperand Arg = Mask.getOperand(i);
1003        if (Arg.getOpcode() == ISD::UNDEF) {
1004          Ops.push_back(DAG.getNode(ISD::UNDEF, EltVT));
1005        } else {
1006          assert(isa<ConstantSDNode>(Arg) && "Invalid VECTOR_SHUFFLE mask!");
1007          unsigned Idx = cast<ConstantSDNode>(Arg)->getValue();
1008          if (Idx < NumElems)
1009            Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp1,
1010                                      DAG.getConstant(Idx, PtrVT)));
1011          else
1012            Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp2,
1013                                      DAG.getConstant(Idx - NumElems, PtrVT)));
1014        }
1015      }
1016      Result = DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
1017      break;
1018    }
1019    case TargetLowering::Promote: {
1020      // Change base type to a different vector type.
1021      MVT::ValueType OVT = Node->getValueType(0);
1022      MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
1023
1024      // Cast the two input vectors.
1025      Tmp1 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp1);
1026      Tmp2 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp2);
1027
1028      // Convert the shuffle mask to the right # elements.
1029      Tmp3 = SDOperand(isShuffleLegal(OVT, Node->getOperand(2)), 0);
1030      assert(Tmp3.Val && "Shuffle not legal?");
1031      Result = DAG.getNode(ISD::VECTOR_SHUFFLE, NVT, Tmp1, Tmp2, Tmp3);
1032      Result = DAG.getNode(ISD::BIT_CONVERT, OVT, Result);
1033      break;
1034    }
1035    }
1036    break;
1037
1038  case ISD::EXTRACT_VECTOR_ELT:
1039    Tmp1 = LegalizeOp(Node->getOperand(0));
1040    Tmp2 = LegalizeOp(Node->getOperand(1));
1041    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1042
1043    switch (TLI.getOperationAction(ISD::EXTRACT_VECTOR_ELT,
1044                                   Tmp1.getValueType())) {
1045    default: assert(0 && "This action is not supported yet!");
1046    case TargetLowering::Legal:
1047      break;
1048    case TargetLowering::Custom:
1049      Tmp3 = TLI.LowerOperation(Result, DAG);
1050      if (Tmp3.Val) {
1051        Result = Tmp3;
1052        break;
1053      }
1054      // FALLTHROUGH
1055    case TargetLowering::Expand:
1056      Result = ExpandEXTRACT_VECTOR_ELT(Result);
1057      break;
1058    }
1059    break;
1060
1061  case ISD::VEXTRACT_VECTOR_ELT:
1062    Result = LegalizeOp(LowerVEXTRACT_VECTOR_ELT(Op));
1063    break;
1064
1065  case ISD::CALLSEQ_START: {
1066    SDNode *CallEnd = FindCallEndFromCallStart(Node);
1067
1068    // Recursively Legalize all of the inputs of the call end that do not lead
1069    // to this call start.  This ensures that any libcalls that need be inserted
1070    // are inserted *before* the CALLSEQ_START.
1071    {std::set<SDNode*> NodesLeadingTo;
1072    for (unsigned i = 0, e = CallEnd->getNumOperands(); i != e; ++i)
1073      LegalizeAllNodesNotLeadingTo(CallEnd->getOperand(i).Val, Node,
1074                                   NodesLeadingTo);
1075    }
1076
1077    // Now that we legalized all of the inputs (which may have inserted
1078    // libcalls) create the new CALLSEQ_START node.
1079    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1080
1081    // Merge in the last call, to ensure that this call start after the last
1082    // call ended.
1083    if (LastCALLSEQ_END.getOpcode() != ISD::EntryToken) {
1084      Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1085      Tmp1 = LegalizeOp(Tmp1);
1086    }
1087
1088    // Do not try to legalize the target-specific arguments (#1+).
1089    if (Tmp1 != Node->getOperand(0)) {
1090      SmallVector<SDOperand, 8> Ops(Node->op_begin(), Node->op_end());
1091      Ops[0] = Tmp1;
1092      Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1093    }
1094
1095    // Remember that the CALLSEQ_START is legalized.
1096    AddLegalizedOperand(Op.getValue(0), Result);
1097    if (Node->getNumValues() == 2)    // If this has a flag result, remember it.
1098      AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1099
1100    // Now that the callseq_start and all of the non-call nodes above this call
1101    // sequence have been legalized, legalize the call itself.  During this
1102    // process, no libcalls can/will be inserted, guaranteeing that no calls
1103    // can overlap.
1104    assert(!IsLegalizingCall && "Inconsistent sequentialization of calls!");
1105    SDOperand InCallSEQ = LastCALLSEQ_END;
1106    // Note that we are selecting this call!
1107    LastCALLSEQ_END = SDOperand(CallEnd, 0);
1108    IsLegalizingCall = true;
1109
1110    // Legalize the call, starting from the CALLSEQ_END.
1111    LegalizeOp(LastCALLSEQ_END);
1112    assert(!IsLegalizingCall && "CALLSEQ_END should have cleared this!");
1113    return Result;
1114  }
1115  case ISD::CALLSEQ_END:
1116    // If the CALLSEQ_START node hasn't been legalized first, legalize it.  This
1117    // will cause this node to be legalized as well as handling libcalls right.
1118    if (LastCALLSEQ_END.Val != Node) {
1119      LegalizeOp(SDOperand(FindCallStartFromCallEnd(Node), 0));
1120      std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
1121      assert(I != LegalizedNodes.end() &&
1122             "Legalizing the call start should have legalized this node!");
1123      return I->second;
1124    }
1125
1126    // Otherwise, the call start has been legalized and everything is going
1127    // according to plan.  Just legalize ourselves normally here.
1128    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1129    // Do not try to legalize the target-specific arguments (#1+), except for
1130    // an optional flag input.
1131    if (Node->getOperand(Node->getNumOperands()-1).getValueType() != MVT::Flag){
1132      if (Tmp1 != Node->getOperand(0)) {
1133        SmallVector<SDOperand, 8> Ops(Node->op_begin(), Node->op_end());
1134        Ops[0] = Tmp1;
1135        Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1136      }
1137    } else {
1138      Tmp2 = LegalizeOp(Node->getOperand(Node->getNumOperands()-1));
1139      if (Tmp1 != Node->getOperand(0) ||
1140          Tmp2 != Node->getOperand(Node->getNumOperands()-1)) {
1141        SmallVector<SDOperand, 8> Ops(Node->op_begin(), Node->op_end());
1142        Ops[0] = Tmp1;
1143        Ops.back() = Tmp2;
1144        Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1145      }
1146    }
1147    assert(IsLegalizingCall && "Call sequence imbalance between start/end?");
1148    // This finishes up call legalization.
1149    IsLegalizingCall = false;
1150
1151    // If the CALLSEQ_END node has a flag, remember that we legalized it.
1152    AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1153    if (Node->getNumValues() == 2)
1154      AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1155    return Result.getValue(Op.ResNo);
1156  case ISD::DYNAMIC_STACKALLOC: {
1157    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1158    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
1159    Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
1160    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1161
1162    Tmp1 = Result.getValue(0);
1163    Tmp2 = Result.getValue(1);
1164    switch (TLI.getOperationAction(Node->getOpcode(),
1165                                   Node->getValueType(0))) {
1166    default: assert(0 && "This action is not supported yet!");
1167    case TargetLowering::Expand: {
1168      unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore();
1169      assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and"
1170             " not tell us which reg is the stack pointer!");
1171      SDOperand Chain = Tmp1.getOperand(0);
1172      SDOperand Size  = Tmp2.getOperand(1);
1173      SDOperand SP = DAG.getCopyFromReg(Chain, SPReg, Node->getValueType(0));
1174      Tmp1 = DAG.getNode(ISD::SUB, Node->getValueType(0), SP, Size);    // Value
1175      Tmp2 = DAG.getCopyToReg(SP.getValue(1), SPReg, Tmp1);      // Output chain
1176      Tmp1 = LegalizeOp(Tmp1);
1177      Tmp2 = LegalizeOp(Tmp2);
1178      break;
1179    }
1180    case TargetLowering::Custom:
1181      Tmp3 = TLI.LowerOperation(Tmp1, DAG);
1182      if (Tmp3.Val) {
1183        Tmp1 = LegalizeOp(Tmp3);
1184        Tmp2 = LegalizeOp(Tmp3.getValue(1));
1185      }
1186      break;
1187    case TargetLowering::Legal:
1188      break;
1189    }
1190    // Since this op produce two values, make sure to remember that we
1191    // legalized both of them.
1192    AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1193    AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1194    return Op.ResNo ? Tmp2 : Tmp1;
1195  }
1196  case ISD::INLINEASM: {
1197    SmallVector<SDOperand, 8> Ops(Node->op_begin(), Node->op_end());
1198    bool Changed = false;
1199    // Legalize all of the operands of the inline asm, in case they are nodes
1200    // that need to be expanded or something.  Note we skip the asm string and
1201    // all of the TargetConstant flags.
1202    SDOperand Op = LegalizeOp(Ops[0]);
1203    Changed = Op != Ops[0];
1204    Ops[0] = Op;
1205
1206    bool HasInFlag = Ops.back().getValueType() == MVT::Flag;
1207    for (unsigned i = 2, e = Ops.size()-HasInFlag; i < e; ) {
1208      unsigned NumVals = cast<ConstantSDNode>(Ops[i])->getValue() >> 3;
1209      for (++i; NumVals; ++i, --NumVals) {
1210        SDOperand Op = LegalizeOp(Ops[i]);
1211        if (Op != Ops[i]) {
1212          Changed = true;
1213          Ops[i] = Op;
1214        }
1215      }
1216    }
1217
1218    if (HasInFlag) {
1219      Op = LegalizeOp(Ops.back());
1220      Changed |= Op != Ops.back();
1221      Ops.back() = Op;
1222    }
1223
1224    if (Changed)
1225      Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
1226
1227    // INLINE asm returns a chain and flag, make sure to add both to the map.
1228    AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1229    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1230    return Result.getValue(Op.ResNo);
1231  }
1232  case ISD::BR:
1233    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1234    // Ensure that libcalls are emitted before a branch.
1235    Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1236    Tmp1 = LegalizeOp(Tmp1);
1237    LastCALLSEQ_END = DAG.getEntryNode();
1238
1239    Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
1240    break;
1241  case ISD::BRIND:
1242    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1243    // Ensure that libcalls are emitted before a branch.
1244    Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1245    Tmp1 = LegalizeOp(Tmp1);
1246    LastCALLSEQ_END = DAG.getEntryNode();
1247
1248    switch (getTypeAction(Node->getOperand(1).getValueType())) {
1249    default: assert(0 && "Indirect target must be legal type (pointer)!");
1250    case Legal:
1251      Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
1252      break;
1253    }
1254    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1255    break;
1256  case ISD::BR_JT:
1257    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1258    // Ensure that libcalls are emitted before a branch.
1259    Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1260    Tmp1 = LegalizeOp(Tmp1);
1261    LastCALLSEQ_END = DAG.getEntryNode();
1262
1263    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the jumptable node.
1264    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1265
1266    switch (TLI.getOperationAction(ISD::BR_JT, MVT::Other)) {
1267    default: assert(0 && "This action is not supported yet!");
1268    case TargetLowering::Legal: break;
1269    case TargetLowering::Custom:
1270      Tmp1 = TLI.LowerOperation(Result, DAG);
1271      if (Tmp1.Val) Result = Tmp1;
1272      break;
1273    case TargetLowering::Expand: {
1274      SDOperand Chain = Result.getOperand(0);
1275      SDOperand Table = Result.getOperand(1);
1276      SDOperand Index = Result.getOperand(2);
1277
1278      MVT::ValueType PTy = TLI.getPointerTy();
1279      MachineFunction &MF = DAG.getMachineFunction();
1280      unsigned EntrySize = MF.getJumpTableInfo()->getEntrySize();
1281      Index= DAG.getNode(ISD::MUL, PTy, Index, DAG.getConstant(EntrySize, PTy));
1282      SDOperand Addr = DAG.getNode(ISD::ADD, PTy, Index, Table);
1283
1284      SDOperand LD;
1285      switch (EntrySize) {
1286      default: assert(0 && "Size of jump table not supported yet."); break;
1287      case 4: LD = DAG.getLoad(MVT::i32, Chain, Addr, NULL, 0); break;
1288      case 8: LD = DAG.getLoad(MVT::i64, Chain, Addr, NULL, 0); break;
1289      }
1290
1291      if (TLI.getTargetMachine().getRelocationModel() == Reloc::PIC_) {
1292        // For PIC, the sequence is:
1293        // BRIND(load(Jumptable + index) + RelocBase)
1294        // RelocBase is the JumpTable on PPC and X86, GOT on Alpha
1295        SDOperand Reloc;
1296        if (TLI.usesGlobalOffsetTable())
1297          Reloc = DAG.getNode(ISD::GLOBAL_OFFSET_TABLE, PTy);
1298        else
1299          Reloc = Table;
1300        Addr = (PTy != MVT::i32) ? DAG.getNode(ISD::SIGN_EXTEND, PTy, LD) : LD;
1301        Addr = DAG.getNode(ISD::ADD, PTy, Addr, Reloc);
1302        Result = DAG.getNode(ISD::BRIND, MVT::Other, LD.getValue(1), Addr);
1303      } else {
1304        Result = DAG.getNode(ISD::BRIND, MVT::Other, LD.getValue(1), LD);
1305      }
1306    }
1307    }
1308    break;
1309  case ISD::BRCOND:
1310    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1311    // Ensure that libcalls are emitted before a return.
1312    Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1313    Tmp1 = LegalizeOp(Tmp1);
1314    LastCALLSEQ_END = DAG.getEntryNode();
1315
1316    switch (getTypeAction(Node->getOperand(1).getValueType())) {
1317    case Expand: assert(0 && "It's impossible to expand bools");
1318    case Legal:
1319      Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
1320      break;
1321    case Promote:
1322      Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
1323
1324      // The top bits of the promoted condition are not necessarily zero, ensure
1325      // that the value is properly zero extended.
1326      if (!TLI.MaskedValueIsZero(Tmp2,
1327                                 MVT::getIntVTBitMask(Tmp2.getValueType())^1))
1328        Tmp2 = DAG.getZeroExtendInReg(Tmp2, MVT::i1);
1329      break;
1330    }
1331
1332    // Basic block destination (Op#2) is always legal.
1333    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
1334
1335    switch (TLI.getOperationAction(ISD::BRCOND, MVT::Other)) {
1336    default: assert(0 && "This action is not supported yet!");
1337    case TargetLowering::Legal: break;
1338    case TargetLowering::Custom:
1339      Tmp1 = TLI.LowerOperation(Result, DAG);
1340      if (Tmp1.Val) Result = Tmp1;
1341      break;
1342    case TargetLowering::Expand:
1343      // Expand brcond's setcc into its constituent parts and create a BR_CC
1344      // Node.
1345      if (Tmp2.getOpcode() == ISD::SETCC) {
1346        Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2),
1347                             Tmp2.getOperand(0), Tmp2.getOperand(1),
1348                             Node->getOperand(2));
1349      } else {
1350        Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1,
1351                             DAG.getCondCode(ISD::SETNE), Tmp2,
1352                             DAG.getConstant(0, Tmp2.getValueType()),
1353                             Node->getOperand(2));
1354      }
1355      break;
1356    }
1357    break;
1358  case ISD::BR_CC:
1359    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1360    // Ensure that libcalls are emitted before a branch.
1361    Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1362    Tmp1 = LegalizeOp(Tmp1);
1363    LastCALLSEQ_END = DAG.getEntryNode();
1364
1365    Tmp2 = Node->getOperand(2);              // LHS
1366    Tmp3 = Node->getOperand(3);              // RHS
1367    Tmp4 = Node->getOperand(1);              // CC
1368
1369    LegalizeSetCCOperands(Tmp2, Tmp3, Tmp4);
1370
1371    // If we didn't get both a LHS and RHS back from LegalizeSetCCOperands,
1372    // the LHS is a legal SETCC itself.  In this case, we need to compare
1373    // the result against zero to select between true and false values.
1374    if (Tmp3.Val == 0) {
1375      Tmp3 = DAG.getConstant(0, Tmp2.getValueType());
1376      Tmp4 = DAG.getCondCode(ISD::SETNE);
1377    }
1378
1379    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp4, Tmp2, Tmp3,
1380                                    Node->getOperand(4));
1381
1382    switch (TLI.getOperationAction(ISD::BR_CC, Tmp3.getValueType())) {
1383    default: assert(0 && "Unexpected action for BR_CC!");
1384    case TargetLowering::Legal: break;
1385    case TargetLowering::Custom:
1386      Tmp4 = TLI.LowerOperation(Result, DAG);
1387      if (Tmp4.Val) Result = Tmp4;
1388      break;
1389    }
1390    break;
1391  case ISD::LOAD: {
1392    LoadSDNode *LD = cast<LoadSDNode>(Node);
1393    Tmp1 = LegalizeOp(LD->getChain());   // Legalize the chain.
1394    Tmp2 = LegalizeOp(LD->getBasePtr()); // Legalize the base pointer.
1395
1396    ISD::LoadExtType ExtType = LD->getExtensionType();
1397    if (ExtType == ISD::NON_EXTLOAD) {
1398      MVT::ValueType VT = Node->getValueType(0);
1399      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, LD->getOffset());
1400      Tmp3 = Result.getValue(0);
1401      Tmp4 = Result.getValue(1);
1402
1403      switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
1404      default: assert(0 && "This action is not supported yet!");
1405      case TargetLowering::Legal: break;
1406      case TargetLowering::Custom:
1407        Tmp1 = TLI.LowerOperation(Tmp3, DAG);
1408        if (Tmp1.Val) {
1409          Tmp3 = LegalizeOp(Tmp1);
1410          Tmp4 = LegalizeOp(Tmp1.getValue(1));
1411        }
1412        break;
1413      case TargetLowering::Promote: {
1414        // Only promote a load of vector type to another.
1415        assert(MVT::isVector(VT) && "Cannot promote this load!");
1416        // Change base type to a different vector type.
1417        MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), VT);
1418
1419        Tmp1 = DAG.getLoad(NVT, Tmp1, Tmp2, LD->getSrcValue(),
1420                           LD->getSrcValueOffset());
1421        Tmp3 = LegalizeOp(DAG.getNode(ISD::BIT_CONVERT, VT, Tmp1));
1422        Tmp4 = LegalizeOp(Tmp1.getValue(1));
1423        break;
1424      }
1425      }
1426      // Since loads produce two values, make sure to remember that we
1427      // legalized both of them.
1428      AddLegalizedOperand(SDOperand(Node, 0), Tmp3);
1429      AddLegalizedOperand(SDOperand(Node, 1), Tmp4);
1430      return Op.ResNo ? Tmp4 : Tmp3;
1431    } else {
1432      MVT::ValueType SrcVT = LD->getLoadedVT();
1433      switch (TLI.getLoadXAction(ExtType, SrcVT)) {
1434      default: assert(0 && "This action is not supported yet!");
1435      case TargetLowering::Promote:
1436        assert(SrcVT == MVT::i1 &&
1437               "Can only promote extending LOAD from i1 -> i8!");
1438        Result = DAG.getExtLoad(ExtType, Node->getValueType(0), Tmp1, Tmp2,
1439                                LD->getSrcValue(), LD->getSrcValueOffset(),
1440                                MVT::i8);
1441      Tmp1 = Result.getValue(0);
1442      Tmp2 = Result.getValue(1);
1443      break;
1444      case TargetLowering::Custom:
1445        isCustom = true;
1446        // FALLTHROUGH
1447      case TargetLowering::Legal:
1448        Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, LD->getOffset());
1449        Tmp1 = Result.getValue(0);
1450        Tmp2 = Result.getValue(1);
1451
1452        if (isCustom) {
1453          Tmp3 = TLI.LowerOperation(Result, DAG);
1454          if (Tmp3.Val) {
1455            Tmp1 = LegalizeOp(Tmp3);
1456            Tmp2 = LegalizeOp(Tmp3.getValue(1));
1457          }
1458        }
1459        break;
1460      case TargetLowering::Expand:
1461        // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND
1462        if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) {
1463          SDOperand Load = DAG.getLoad(SrcVT, Tmp1, Tmp2, LD->getSrcValue(),
1464                                       LD->getSrcValueOffset());
1465          Result = DAG.getNode(ISD::FP_EXTEND, Node->getValueType(0), Load);
1466          Tmp1 = LegalizeOp(Result);  // Relegalize new nodes.
1467          Tmp2 = LegalizeOp(Load.getValue(1));
1468          break;
1469        }
1470        assert(ExtType != ISD::EXTLOAD && "EXTLOAD should always be supported!");
1471        // Turn the unsupported load into an EXTLOAD followed by an explicit
1472        // zero/sign extend inreg.
1473        Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
1474                                Tmp1, Tmp2, LD->getSrcValue(),
1475                                LD->getSrcValueOffset(), SrcVT);
1476        SDOperand ValRes;
1477        if (ExtType == ISD::SEXTLOAD)
1478          ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1479                               Result, DAG.getValueType(SrcVT));
1480        else
1481          ValRes = DAG.getZeroExtendInReg(Result, SrcVT);
1482        Tmp1 = LegalizeOp(ValRes);  // Relegalize new nodes.
1483        Tmp2 = LegalizeOp(Result.getValue(1));  // Relegalize new nodes.
1484        break;
1485      }
1486      // Since loads produce two values, make sure to remember that we legalized
1487      // both of them.
1488      AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1489      AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1490      return Op.ResNo ? Tmp2 : Tmp1;
1491    }
1492  }
1493  case ISD::EXTRACT_ELEMENT: {
1494    MVT::ValueType OpTy = Node->getOperand(0).getValueType();
1495    switch (getTypeAction(OpTy)) {
1496    default: assert(0 && "EXTRACT_ELEMENT action for type unimplemented!");
1497    case Legal:
1498      if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) {
1499        // 1 -> Hi
1500        Result = DAG.getNode(ISD::SRL, OpTy, Node->getOperand(0),
1501                             DAG.getConstant(MVT::getSizeInBits(OpTy)/2,
1502                                             TLI.getShiftAmountTy()));
1503        Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Result);
1504      } else {
1505        // 0 -> Lo
1506        Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0),
1507                             Node->getOperand(0));
1508      }
1509      break;
1510    case Expand:
1511      // Get both the low and high parts.
1512      ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
1513      if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
1514        Result = Tmp2;  // 1 -> Hi
1515      else
1516        Result = Tmp1;  // 0 -> Lo
1517      break;
1518    }
1519    break;
1520  }
1521
1522  case ISD::CopyToReg:
1523    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1524
1525    assert(isTypeLegal(Node->getOperand(2).getValueType()) &&
1526           "Register type must be legal!");
1527    // Legalize the incoming value (must be a legal type).
1528    Tmp2 = LegalizeOp(Node->getOperand(2));
1529    if (Node->getNumValues() == 1) {
1530      Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2);
1531    } else {
1532      assert(Node->getNumValues() == 2 && "Unknown CopyToReg");
1533      if (Node->getNumOperands() == 4) {
1534        Tmp3 = LegalizeOp(Node->getOperand(3));
1535        Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1), Tmp2,
1536                                        Tmp3);
1537      } else {
1538        Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1),Tmp2);
1539      }
1540
1541      // Since this produces two values, make sure to remember that we legalized
1542      // both of them.
1543      AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
1544      AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
1545      return Result;
1546    }
1547    break;
1548
1549  case ISD::RET:
1550    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1551
1552    // Ensure that libcalls are emitted before a return.
1553    Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
1554    Tmp1 = LegalizeOp(Tmp1);
1555    LastCALLSEQ_END = DAG.getEntryNode();
1556
1557    switch (Node->getNumOperands()) {
1558    case 3:  // ret val
1559      Tmp2 = Node->getOperand(1);
1560      Tmp3 = Node->getOperand(2);  // Signness
1561      switch (getTypeAction(Tmp2.getValueType())) {
1562      case Legal:
1563        Result = DAG.UpdateNodeOperands(Result, Tmp1, LegalizeOp(Tmp2), Tmp3);
1564        break;
1565      case Expand:
1566        if (Tmp2.getValueType() != MVT::Vector) {
1567          SDOperand Lo, Hi;
1568          ExpandOp(Tmp2, Lo, Hi);
1569          if (Hi.Val)
1570            Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Tmp3, Hi,Tmp3);
1571          else
1572            Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Tmp3);
1573          Result = LegalizeOp(Result);
1574        } else {
1575          SDNode *InVal = Tmp2.Val;
1576          unsigned NumElems =
1577            cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
1578          MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
1579
1580          // Figure out if there is a Packed type corresponding to this Vector
1581          // type.  If so, convert to the packed type.
1582          MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1583          if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
1584            // Turn this into a return of the packed type.
1585            Tmp2 = PackVectorOp(Tmp2, TVT);
1586            Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1587          } else if (NumElems == 1) {
1588            // Turn this into a return of the scalar type.
1589            Tmp2 = PackVectorOp(Tmp2, EVT);
1590            Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1591
1592            // FIXME: Returns of gcc generic vectors smaller than a legal type
1593            // should be returned in integer registers!
1594
1595            // The scalarized value type may not be legal, e.g. it might require
1596            // promotion or expansion.  Relegalize the return.
1597            Result = LegalizeOp(Result);
1598          } else {
1599            // FIXME: Returns of gcc generic vectors larger than a legal vector
1600            // type should be returned by reference!
1601            SDOperand Lo, Hi;
1602            SplitVectorOp(Tmp2, Lo, Hi);
1603            Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Tmp3, Hi, Tmp3);
1604            Result = LegalizeOp(Result);
1605          }
1606        }
1607        break;
1608      case Promote:
1609        Tmp2 = PromoteOp(Node->getOperand(1));
1610        Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1611        Result = LegalizeOp(Result);
1612        break;
1613      }
1614      break;
1615    case 1:  // ret void
1616      Result = DAG.UpdateNodeOperands(Result, Tmp1);
1617      break;
1618    default: { // ret <values>
1619      SmallVector<SDOperand, 8> NewValues;
1620      NewValues.push_back(Tmp1);
1621      for (unsigned i = 1, e = Node->getNumOperands(); i < e; i += 2)
1622        switch (getTypeAction(Node->getOperand(i).getValueType())) {
1623        case Legal:
1624          NewValues.push_back(LegalizeOp(Node->getOperand(i)));
1625          NewValues.push_back(Node->getOperand(i+1));
1626          break;
1627        case Expand: {
1628          SDOperand Lo, Hi;
1629          assert(Node->getOperand(i).getValueType() != MVT::Vector &&
1630                 "FIXME: TODO: implement returning non-legal vector types!");
1631          ExpandOp(Node->getOperand(i), Lo, Hi);
1632          NewValues.push_back(Lo);
1633          NewValues.push_back(Node->getOperand(i+1));
1634          if (Hi.Val) {
1635            NewValues.push_back(Hi);
1636            NewValues.push_back(Node->getOperand(i+1));
1637          }
1638          break;
1639        }
1640        case Promote:
1641          assert(0 && "Can't promote multiple return value yet!");
1642        }
1643
1644      if (NewValues.size() == Node->getNumOperands())
1645        Result = DAG.UpdateNodeOperands(Result, &NewValues[0],NewValues.size());
1646      else
1647        Result = DAG.getNode(ISD::RET, MVT::Other,
1648                             &NewValues[0], NewValues.size());
1649      break;
1650    }
1651    }
1652
1653    if (Result.getOpcode() == ISD::RET) {
1654      switch (TLI.getOperationAction(Result.getOpcode(), MVT::Other)) {
1655      default: assert(0 && "This action is not supported yet!");
1656      case TargetLowering::Legal: break;
1657      case TargetLowering::Custom:
1658        Tmp1 = TLI.LowerOperation(Result, DAG);
1659        if (Tmp1.Val) Result = Tmp1;
1660        break;
1661      }
1662    }
1663    break;
1664  case ISD::STORE: {
1665    StoreSDNode *ST = cast<StoreSDNode>(Node);
1666    Tmp1 = LegalizeOp(ST->getChain());    // Legalize the chain.
1667    Tmp2 = LegalizeOp(ST->getBasePtr());  // Legalize the pointer.
1668
1669    if (!ST->isTruncatingStore()) {
1670      // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
1671      // FIXME: We shouldn't do this for TargetConstantFP's.
1672      // FIXME: move this to the DAG Combiner!  Note that we can't regress due
1673      // to phase ordering between legalized code and the dag combiner.  This
1674      // probably means that we need to integrate dag combiner and legalizer
1675      // together.
1676      if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(ST->getValue())) {
1677        if (CFP->getValueType(0) == MVT::f32) {
1678          Tmp3 = DAG.getConstant(FloatToBits(CFP->getValue()), MVT::i32);
1679        } else {
1680          assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
1681          Tmp3 = DAG.getConstant(DoubleToBits(CFP->getValue()), MVT::i64);
1682        }
1683        Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1684                              ST->getSrcValueOffset());
1685        break;
1686      }
1687
1688      switch (getTypeAction(ST->getStoredVT())) {
1689      case Legal: {
1690        Tmp3 = LegalizeOp(ST->getValue());
1691        Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1692                                        ST->getOffset());
1693
1694        MVT::ValueType VT = Tmp3.getValueType();
1695        switch (TLI.getOperationAction(ISD::STORE, VT)) {
1696        default: assert(0 && "This action is not supported yet!");
1697        case TargetLowering::Legal:  break;
1698        case TargetLowering::Custom:
1699          Tmp1 = TLI.LowerOperation(Result, DAG);
1700          if (Tmp1.Val) Result = Tmp1;
1701          break;
1702        case TargetLowering::Promote:
1703          assert(MVT::isVector(VT) && "Unknown legal promote case!");
1704          Tmp3 = DAG.getNode(ISD::BIT_CONVERT,
1705                             TLI.getTypeToPromoteTo(ISD::STORE, VT), Tmp3);
1706          Result = DAG.getStore(Tmp1, Tmp3, Tmp2,
1707                                ST->getSrcValue(), ST->getSrcValueOffset());
1708          break;
1709        }
1710        break;
1711      }
1712      case Promote:
1713        // Truncate the value and store the result.
1714        Tmp3 = PromoteOp(ST->getValue());
1715        Result = DAG.getTruncStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1716                                   ST->getSrcValueOffset(), ST->getStoredVT());
1717        break;
1718
1719      case Expand:
1720        unsigned IncrementSize = 0;
1721        SDOperand Lo, Hi;
1722
1723        // If this is a vector type, then we have to calculate the increment as
1724        // the product of the element size in bytes, and the number of elements
1725        // in the high half of the vector.
1726        if (ST->getValue().getValueType() == MVT::Vector) {
1727          SDNode *InVal = ST->getValue().Val;
1728          unsigned NumElems =
1729            cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
1730          MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
1731
1732          // Figure out if there is a Packed type corresponding to this Vector
1733          // type.  If so, convert to the packed type.
1734          MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
1735          if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
1736            // Turn this into a normal store of the packed type.
1737            Tmp3 = PackVectorOp(Node->getOperand(1), TVT);
1738            Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1739                                  ST->getSrcValueOffset());
1740            Result = LegalizeOp(Result);
1741            break;
1742          } else if (NumElems == 1) {
1743            // Turn this into a normal store of the scalar type.
1744            Tmp3 = PackVectorOp(Node->getOperand(1), EVT);
1745            Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1746                                  ST->getSrcValueOffset());
1747            // The scalarized value type may not be legal, e.g. it might require
1748            // promotion or expansion.  Relegalize the scalar store.
1749            Result = LegalizeOp(Result);
1750            break;
1751          } else {
1752            SplitVectorOp(Node->getOperand(1), Lo, Hi);
1753            IncrementSize = NumElems/2 * MVT::getSizeInBits(EVT)/8;
1754          }
1755        } else {
1756          ExpandOp(Node->getOperand(1), Lo, Hi);
1757          IncrementSize = Hi.Val ? MVT::getSizeInBits(Hi.getValueType())/8 : 0;
1758
1759          if (!TLI.isLittleEndian())
1760            std::swap(Lo, Hi);
1761        }
1762
1763        Lo = DAG.getStore(Tmp1, Lo, Tmp2, ST->getSrcValue(),
1764                          ST->getSrcValueOffset());
1765
1766        if (Hi.Val == NULL) {
1767          // Must be int <-> float one-to-one expansion.
1768          Result = Lo;
1769          break;
1770        }
1771
1772        Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
1773                           getIntPtrConstant(IncrementSize));
1774        assert(isTypeLegal(Tmp2.getValueType()) &&
1775               "Pointers must be legal!");
1776        // FIXME: This sets the srcvalue of both halves to be the same, which is
1777        // wrong.
1778        Hi = DAG.getStore(Tmp1, Hi, Tmp2, ST->getSrcValue(),
1779                          ST->getSrcValueOffset());
1780        Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
1781        break;
1782      }
1783    } else {
1784      // Truncating store
1785      assert(isTypeLegal(ST->getValue().getValueType()) &&
1786             "Cannot handle illegal TRUNCSTORE yet!");
1787      Tmp3 = LegalizeOp(ST->getValue());
1788
1789      // The only promote case we handle is TRUNCSTORE:i1 X into
1790      //   -> TRUNCSTORE:i8 (and X, 1)
1791      if (ST->getStoredVT() == MVT::i1 &&
1792          TLI.getStoreXAction(MVT::i1) == TargetLowering::Promote) {
1793        // Promote the bool to a mask then store.
1794        Tmp3 = DAG.getNode(ISD::AND, Tmp3.getValueType(), Tmp3,
1795                           DAG.getConstant(1, Tmp3.getValueType()));
1796        Result = DAG.getTruncStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(),
1797                                   ST->getSrcValueOffset(), MVT::i8);
1798      } else if (Tmp1 != ST->getChain() || Tmp3 != ST->getValue() ||
1799                 Tmp2 != ST->getBasePtr()) {
1800        Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp3, Tmp2,
1801                                        ST->getOffset());
1802      }
1803
1804      MVT::ValueType StVT = cast<StoreSDNode>(Result.Val)->getStoredVT();
1805      switch (TLI.getStoreXAction(StVT)) {
1806      default: assert(0 && "This action is not supported yet!");
1807      case TargetLowering::Legal: break;
1808      case TargetLowering::Custom:
1809        Tmp1 = TLI.LowerOperation(Result, DAG);
1810        if (Tmp1.Val) Result = Tmp1;
1811        break;
1812      }
1813    }
1814    break;
1815  }
1816  case ISD::PCMARKER:
1817    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1818    Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
1819    break;
1820  case ISD::STACKSAVE:
1821    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1822    Result = DAG.UpdateNodeOperands(Result, Tmp1);
1823    Tmp1 = Result.getValue(0);
1824    Tmp2 = Result.getValue(1);
1825
1826    switch (TLI.getOperationAction(ISD::STACKSAVE, MVT::Other)) {
1827    default: assert(0 && "This action is not supported yet!");
1828    case TargetLowering::Legal: break;
1829    case TargetLowering::Custom:
1830      Tmp3 = TLI.LowerOperation(Result, DAG);
1831      if (Tmp3.Val) {
1832        Tmp1 = LegalizeOp(Tmp3);
1833        Tmp2 = LegalizeOp(Tmp3.getValue(1));
1834      }
1835      break;
1836    case TargetLowering::Expand:
1837      // Expand to CopyFromReg if the target set
1838      // StackPointerRegisterToSaveRestore.
1839      if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
1840        Tmp1 = DAG.getCopyFromReg(Result.getOperand(0), SP,
1841                                  Node->getValueType(0));
1842        Tmp2 = Tmp1.getValue(1);
1843      } else {
1844        Tmp1 = DAG.getNode(ISD::UNDEF, Node->getValueType(0));
1845        Tmp2 = Node->getOperand(0);
1846      }
1847      break;
1848    }
1849
1850    // Since stacksave produce two values, make sure to remember that we
1851    // legalized both of them.
1852    AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1853    AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1854    return Op.ResNo ? Tmp2 : Tmp1;
1855
1856  case ISD::STACKRESTORE:
1857    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1858    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1859    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
1860
1861    switch (TLI.getOperationAction(ISD::STACKRESTORE, MVT::Other)) {
1862    default: assert(0 && "This action is not supported yet!");
1863    case TargetLowering::Legal: break;
1864    case TargetLowering::Custom:
1865      Tmp1 = TLI.LowerOperation(Result, DAG);
1866      if (Tmp1.Val) Result = Tmp1;
1867      break;
1868    case TargetLowering::Expand:
1869      // Expand to CopyToReg if the target set
1870      // StackPointerRegisterToSaveRestore.
1871      if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
1872        Result = DAG.getCopyToReg(Tmp1, SP, Tmp2);
1873      } else {
1874        Result = Tmp1;
1875      }
1876      break;
1877    }
1878    break;
1879
1880  case ISD::READCYCLECOUNTER:
1881    Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain
1882    Result = DAG.UpdateNodeOperands(Result, Tmp1);
1883    switch (TLI.getOperationAction(ISD::READCYCLECOUNTER,
1884                                   Node->getValueType(0))) {
1885    default: assert(0 && "This action is not supported yet!");
1886    case TargetLowering::Legal:
1887      Tmp1 = Result.getValue(0);
1888      Tmp2 = Result.getValue(1);
1889      break;
1890    case TargetLowering::Custom:
1891      Result = TLI.LowerOperation(Result, DAG);
1892      Tmp1 = LegalizeOp(Result.getValue(0));
1893      Tmp2 = LegalizeOp(Result.getValue(1));
1894      break;
1895    }
1896
1897    // Since rdcc produce two values, make sure to remember that we legalized
1898    // both of them.
1899    AddLegalizedOperand(SDOperand(Node, 0), Tmp1);
1900    AddLegalizedOperand(SDOperand(Node, 1), Tmp2);
1901    return Result;
1902
1903  case ISD::SELECT:
1904    switch (getTypeAction(Node->getOperand(0).getValueType())) {
1905    case Expand: assert(0 && "It's impossible to expand bools");
1906    case Legal:
1907      Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
1908      break;
1909    case Promote:
1910      Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
1911      // Make sure the condition is either zero or one.
1912      if (!TLI.MaskedValueIsZero(Tmp1,
1913                                 MVT::getIntVTBitMask(Tmp1.getValueType())^1))
1914        Tmp1 = DAG.getZeroExtendInReg(Tmp1, MVT::i1);
1915      break;
1916    }
1917    Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
1918    Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
1919
1920    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
1921
1922    switch (TLI.getOperationAction(ISD::SELECT, Tmp2.getValueType())) {
1923    default: assert(0 && "This action is not supported yet!");
1924    case TargetLowering::Legal: break;
1925    case TargetLowering::Custom: {
1926      Tmp1 = TLI.LowerOperation(Result, DAG);
1927      if (Tmp1.Val) Result = Tmp1;
1928      break;
1929    }
1930    case TargetLowering::Expand:
1931      if (Tmp1.getOpcode() == ISD::SETCC) {
1932        Result = DAG.getSelectCC(Tmp1.getOperand(0), Tmp1.getOperand(1),
1933                              Tmp2, Tmp3,
1934                              cast<CondCodeSDNode>(Tmp1.getOperand(2))->get());
1935      } else {
1936        Result = DAG.getSelectCC(Tmp1,
1937                                 DAG.getConstant(0, Tmp1.getValueType()),
1938                                 Tmp2, Tmp3, ISD::SETNE);
1939      }
1940      break;
1941    case TargetLowering::Promote: {
1942      MVT::ValueType NVT =
1943        TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
1944      unsigned ExtOp, TruncOp;
1945      if (MVT::isVector(Tmp2.getValueType())) {
1946        ExtOp   = ISD::BIT_CONVERT;
1947        TruncOp = ISD::BIT_CONVERT;
1948      } else if (MVT::isInteger(Tmp2.getValueType())) {
1949        ExtOp   = ISD::ANY_EXTEND;
1950        TruncOp = ISD::TRUNCATE;
1951      } else {
1952        ExtOp   = ISD::FP_EXTEND;
1953        TruncOp = ISD::FP_ROUND;
1954      }
1955      // Promote each of the values to the new type.
1956      Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
1957      Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
1958      // Perform the larger operation, then round down.
1959      Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
1960      Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
1961      break;
1962    }
1963    }
1964    break;
1965  case ISD::SELECT_CC: {
1966    Tmp1 = Node->getOperand(0);               // LHS
1967    Tmp2 = Node->getOperand(1);               // RHS
1968    Tmp3 = LegalizeOp(Node->getOperand(2));   // True
1969    Tmp4 = LegalizeOp(Node->getOperand(3));   // False
1970    SDOperand CC = Node->getOperand(4);
1971
1972    LegalizeSetCCOperands(Tmp1, Tmp2, CC);
1973
1974    // If we didn't get both a LHS and RHS back from LegalizeSetCCOperands,
1975    // the LHS is a legal SETCC itself.  In this case, we need to compare
1976    // the result against zero to select between true and false values.
1977    if (Tmp2.Val == 0) {
1978      Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
1979      CC = DAG.getCondCode(ISD::SETNE);
1980    }
1981    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4, CC);
1982
1983    // Everything is legal, see if we should expand this op or something.
1984    switch (TLI.getOperationAction(ISD::SELECT_CC, Tmp3.getValueType())) {
1985    default: assert(0 && "This action is not supported yet!");
1986    case TargetLowering::Legal: break;
1987    case TargetLowering::Custom:
1988      Tmp1 = TLI.LowerOperation(Result, DAG);
1989      if (Tmp1.Val) Result = Tmp1;
1990      break;
1991    }
1992    break;
1993  }
1994  case ISD::SETCC:
1995    Tmp1 = Node->getOperand(0);
1996    Tmp2 = Node->getOperand(1);
1997    Tmp3 = Node->getOperand(2);
1998    LegalizeSetCCOperands(Tmp1, Tmp2, Tmp3);
1999
2000    // If we had to Expand the SetCC operands into a SELECT node, then it may
2001    // not always be possible to return a true LHS & RHS.  In this case, just
2002    // return the value we legalized, returned in the LHS
2003    if (Tmp2.Val == 0) {
2004      Result = Tmp1;
2005      break;
2006    }
2007
2008    switch (TLI.getOperationAction(ISD::SETCC, Tmp1.getValueType())) {
2009    default: assert(0 && "Cannot handle this action for SETCC yet!");
2010    case TargetLowering::Custom:
2011      isCustom = true;
2012      // FALLTHROUGH.
2013    case TargetLowering::Legal:
2014      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2015      if (isCustom) {
2016        Tmp4 = TLI.LowerOperation(Result, DAG);
2017        if (Tmp4.Val) Result = Tmp4;
2018      }
2019      break;
2020    case TargetLowering::Promote: {
2021      // First step, figure out the appropriate operation to use.
2022      // Allow SETCC to not be supported for all legal data types
2023      // Mostly this targets FP
2024      MVT::ValueType NewInTy = Node->getOperand(0).getValueType();
2025      MVT::ValueType OldVT = NewInTy;
2026
2027      // Scan for the appropriate larger type to use.
2028      while (1) {
2029        NewInTy = (MVT::ValueType)(NewInTy+1);
2030
2031        assert(MVT::isInteger(NewInTy) == MVT::isInteger(OldVT) &&
2032               "Fell off of the edge of the integer world");
2033        assert(MVT::isFloatingPoint(NewInTy) == MVT::isFloatingPoint(OldVT) &&
2034               "Fell off of the edge of the floating point world");
2035
2036        // If the target supports SETCC of this type, use it.
2037        if (TLI.isOperationLegal(ISD::SETCC, NewInTy))
2038          break;
2039      }
2040      if (MVT::isInteger(NewInTy))
2041        assert(0 && "Cannot promote Legal Integer SETCC yet");
2042      else {
2043        Tmp1 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp1);
2044        Tmp2 = DAG.getNode(ISD::FP_EXTEND, NewInTy, Tmp2);
2045      }
2046      Tmp1 = LegalizeOp(Tmp1);
2047      Tmp2 = LegalizeOp(Tmp2);
2048      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2049      Result = LegalizeOp(Result);
2050      break;
2051    }
2052    case TargetLowering::Expand:
2053      // Expand a setcc node into a select_cc of the same condition, lhs, and
2054      // rhs that selects between const 1 (true) and const 0 (false).
2055      MVT::ValueType VT = Node->getValueType(0);
2056      Result = DAG.getNode(ISD::SELECT_CC, VT, Tmp1, Tmp2,
2057                           DAG.getConstant(1, VT), DAG.getConstant(0, VT),
2058                           Tmp3);
2059      break;
2060    }
2061    break;
2062  case ISD::MEMSET:
2063  case ISD::MEMCPY:
2064  case ISD::MEMMOVE: {
2065    Tmp1 = LegalizeOp(Node->getOperand(0));      // Chain
2066    Tmp2 = LegalizeOp(Node->getOperand(1));      // Pointer
2067
2068    if (Node->getOpcode() == ISD::MEMSET) {      // memset = ubyte
2069      switch (getTypeAction(Node->getOperand(2).getValueType())) {
2070      case Expand: assert(0 && "Cannot expand a byte!");
2071      case Legal:
2072        Tmp3 = LegalizeOp(Node->getOperand(2));
2073        break;
2074      case Promote:
2075        Tmp3 = PromoteOp(Node->getOperand(2));
2076        break;
2077      }
2078    } else {
2079      Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer,
2080    }
2081
2082    SDOperand Tmp4;
2083    switch (getTypeAction(Node->getOperand(3).getValueType())) {
2084    case Expand: {
2085      // Length is too big, just take the lo-part of the length.
2086      SDOperand HiPart;
2087      ExpandOp(Node->getOperand(3), Tmp4, HiPart);
2088      break;
2089    }
2090    case Legal:
2091      Tmp4 = LegalizeOp(Node->getOperand(3));
2092      break;
2093    case Promote:
2094      Tmp4 = PromoteOp(Node->getOperand(3));
2095      break;
2096    }
2097
2098    SDOperand Tmp5;
2099    switch (getTypeAction(Node->getOperand(4).getValueType())) {  // uint
2100    case Expand: assert(0 && "Cannot expand this yet!");
2101    case Legal:
2102      Tmp5 = LegalizeOp(Node->getOperand(4));
2103      break;
2104    case Promote:
2105      Tmp5 = PromoteOp(Node->getOperand(4));
2106      break;
2107    }
2108
2109    switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
2110    default: assert(0 && "This action not implemented for this operation!");
2111    case TargetLowering::Custom:
2112      isCustom = true;
2113      // FALLTHROUGH
2114    case TargetLowering::Legal:
2115      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3, Tmp4, Tmp5);
2116      if (isCustom) {
2117        Tmp1 = TLI.LowerOperation(Result, DAG);
2118        if (Tmp1.Val) Result = Tmp1;
2119      }
2120      break;
2121    case TargetLowering::Expand: {
2122      // Otherwise, the target does not support this operation.  Lower the
2123      // operation to an explicit libcall as appropriate.
2124      MVT::ValueType IntPtr = TLI.getPointerTy();
2125      const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType();
2126      std::vector<std::pair<SDOperand, const Type*> > Args;
2127
2128      const char *FnName = 0;
2129      if (Node->getOpcode() == ISD::MEMSET) {
2130        Args.push_back(std::make_pair(Tmp2, IntPtrTy));
2131        // Extend the (previously legalized) ubyte argument to be an int value
2132        // for the call.
2133        if (Tmp3.getValueType() > MVT::i32)
2134          Tmp3 = DAG.getNode(ISD::TRUNCATE, MVT::i32, Tmp3);
2135        else
2136          Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
2137        Args.push_back(std::make_pair(Tmp3, Type::IntTy));
2138        Args.push_back(std::make_pair(Tmp4, IntPtrTy));
2139
2140        FnName = "memset";
2141      } else if (Node->getOpcode() == ISD::MEMCPY ||
2142                 Node->getOpcode() == ISD::MEMMOVE) {
2143        Args.push_back(std::make_pair(Tmp2, IntPtrTy));
2144        Args.push_back(std::make_pair(Tmp3, IntPtrTy));
2145        Args.push_back(std::make_pair(Tmp4, IntPtrTy));
2146        FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
2147      } else {
2148        assert(0 && "Unknown op!");
2149      }
2150
2151      std::pair<SDOperand,SDOperand> CallResult =
2152        TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false,
2153                        DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
2154      Result = CallResult.second;
2155      break;
2156    }
2157    }
2158    break;
2159  }
2160
2161  case ISD::SHL_PARTS:
2162  case ISD::SRA_PARTS:
2163  case ISD::SRL_PARTS: {
2164    SmallVector<SDOperand, 8> Ops;
2165    bool Changed = false;
2166    for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
2167      Ops.push_back(LegalizeOp(Node->getOperand(i)));
2168      Changed |= Ops.back() != Node->getOperand(i);
2169    }
2170    if (Changed)
2171      Result = DAG.UpdateNodeOperands(Result, &Ops[0], Ops.size());
2172
2173    switch (TLI.getOperationAction(Node->getOpcode(),
2174                                   Node->getValueType(0))) {
2175    default: assert(0 && "This action is not supported yet!");
2176    case TargetLowering::Legal: break;
2177    case TargetLowering::Custom:
2178      Tmp1 = TLI.LowerOperation(Result, DAG);
2179      if (Tmp1.Val) {
2180        SDOperand Tmp2, RetVal(0, 0);
2181        for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) {
2182          Tmp2 = LegalizeOp(Tmp1.getValue(i));
2183          AddLegalizedOperand(SDOperand(Node, i), Tmp2);
2184          if (i == Op.ResNo)
2185            RetVal = Tmp2;
2186        }
2187        assert(RetVal.Val && "Illegal result number");
2188        return RetVal;
2189      }
2190      break;
2191    }
2192
2193    // Since these produce multiple values, make sure to remember that we
2194    // legalized all of them.
2195    for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
2196      AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
2197    return Result.getValue(Op.ResNo);
2198  }
2199
2200    // Binary operators
2201  case ISD::ADD:
2202  case ISD::SUB:
2203  case ISD::MUL:
2204  case ISD::MULHS:
2205  case ISD::MULHU:
2206  case ISD::UDIV:
2207  case ISD::SDIV:
2208  case ISD::AND:
2209  case ISD::OR:
2210  case ISD::XOR:
2211  case ISD::SHL:
2212  case ISD::SRL:
2213  case ISD::SRA:
2214  case ISD::FADD:
2215  case ISD::FSUB:
2216  case ISD::FMUL:
2217  case ISD::FDIV:
2218    Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2219    switch (getTypeAction(Node->getOperand(1).getValueType())) {
2220    case Expand: assert(0 && "Not possible");
2221    case Legal:
2222      Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
2223      break;
2224    case Promote:
2225      Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
2226      break;
2227    }
2228
2229    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2230
2231    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2232    default: assert(0 && "BinOp legalize operation not supported");
2233    case TargetLowering::Legal: break;
2234    case TargetLowering::Custom:
2235      Tmp1 = TLI.LowerOperation(Result, DAG);
2236      if (Tmp1.Val) Result = Tmp1;
2237      break;
2238    case TargetLowering::Expand: {
2239      if (Node->getValueType(0) == MVT::i32) {
2240        switch (Node->getOpcode()) {
2241        default:  assert(0 && "Do not know how to expand this integer BinOp!");
2242        case ISD::UDIV:
2243        case ISD::SDIV:
2244          const char *FnName = Node->getOpcode() == ISD::UDIV
2245            ? "__udivsi3" : "__divsi3";
2246          SDOperand Dummy;
2247          Result = ExpandLibCall(FnName, Node, Dummy);
2248        };
2249        break;
2250      }
2251
2252      assert(MVT::isVector(Node->getValueType(0)) &&
2253             "Cannot expand this binary operator!");
2254      // Expand the operation into a bunch of nasty scalar code.
2255      SmallVector<SDOperand, 8> Ops;
2256      MVT::ValueType EltVT = MVT::getVectorBaseType(Node->getValueType(0));
2257      MVT::ValueType PtrVT = TLI.getPointerTy();
2258      for (unsigned i = 0, e = MVT::getVectorNumElements(Node->getValueType(0));
2259           i != e; ++i) {
2260        SDOperand Idx = DAG.getConstant(i, PtrVT);
2261        SDOperand LHS = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp1, Idx);
2262        SDOperand RHS = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, EltVT, Tmp2, Idx);
2263        Ops.push_back(DAG.getNode(Node->getOpcode(), EltVT, LHS, RHS));
2264      }
2265      Result = DAG.getNode(ISD::BUILD_VECTOR, Node->getValueType(0),
2266                           &Ops[0], Ops.size());
2267      break;
2268    }
2269    case TargetLowering::Promote: {
2270      switch (Node->getOpcode()) {
2271      default:  assert(0 && "Do not know how to promote this BinOp!");
2272      case ISD::AND:
2273      case ISD::OR:
2274      case ISD::XOR: {
2275        MVT::ValueType OVT = Node->getValueType(0);
2276        MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2277        assert(MVT::isVector(OVT) && "Cannot promote this BinOp!");
2278        // Bit convert each of the values to the new type.
2279        Tmp1 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp1);
2280        Tmp2 = DAG.getNode(ISD::BIT_CONVERT, NVT, Tmp2);
2281        Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
2282        // Bit convert the result back the original type.
2283        Result = DAG.getNode(ISD::BIT_CONVERT, OVT, Result);
2284        break;
2285      }
2286      }
2287    }
2288    }
2289    break;
2290
2291  case ISD::FCOPYSIGN:  // FCOPYSIGN does not require LHS/RHS to match type!
2292    Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2293    switch (getTypeAction(Node->getOperand(1).getValueType())) {
2294      case Expand: assert(0 && "Not possible");
2295      case Legal:
2296        Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS.
2297        break;
2298      case Promote:
2299        Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the RHS.
2300        break;
2301    }
2302
2303    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2304
2305    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2306    default: assert(0 && "Operation not supported");
2307    case TargetLowering::Custom:
2308      Tmp1 = TLI.LowerOperation(Result, DAG);
2309      if (Tmp1.Val) Result = Tmp1;
2310      break;
2311    case TargetLowering::Legal: break;
2312    case TargetLowering::Expand:
2313      // If this target supports fabs/fneg natively, do this efficiently.
2314      if (TLI.isOperationLegal(ISD::FABS, Tmp1.getValueType()) &&
2315          TLI.isOperationLegal(ISD::FNEG, Tmp1.getValueType())) {
2316        // Get the sign bit of the RHS.
2317        MVT::ValueType IVT =
2318          Tmp2.getValueType() == MVT::f32 ? MVT::i32 : MVT::i64;
2319        SDOperand SignBit = DAG.getNode(ISD::BIT_CONVERT, IVT, Tmp2);
2320        SignBit = DAG.getSetCC(TLI.getSetCCResultTy(),
2321                               SignBit, DAG.getConstant(0, IVT), ISD::SETLT);
2322        // Get the absolute value of the result.
2323        SDOperand AbsVal = DAG.getNode(ISD::FABS, Tmp1.getValueType(), Tmp1);
2324        // Select between the nabs and abs value based on the sign bit of
2325        // the input.
2326        Result = DAG.getNode(ISD::SELECT, AbsVal.getValueType(), SignBit,
2327                             DAG.getNode(ISD::FNEG, AbsVal.getValueType(),
2328                                         AbsVal),
2329                             AbsVal);
2330        Result = LegalizeOp(Result);
2331        break;
2332      }
2333
2334      // Otherwise, do bitwise ops!
2335
2336      // copysign -> copysignf/copysign libcall.
2337      const char *FnName;
2338      if (Node->getValueType(0) == MVT::f32) {
2339        FnName = "copysignf";
2340        if (Tmp2.getValueType() != MVT::f32)  // Force operands to match type.
2341          Result = DAG.UpdateNodeOperands(Result, Tmp1,
2342                                    DAG.getNode(ISD::FP_ROUND, MVT::f32, Tmp2));
2343      } else {
2344        FnName = "copysign";
2345        if (Tmp2.getValueType() != MVT::f64)  // Force operands to match type.
2346          Result = DAG.UpdateNodeOperands(Result, Tmp1,
2347                                   DAG.getNode(ISD::FP_EXTEND, MVT::f64, Tmp2));
2348      }
2349      SDOperand Dummy;
2350      Result = ExpandLibCall(FnName, Node, Dummy);
2351      break;
2352    }
2353    break;
2354
2355  case ISD::ADDC:
2356  case ISD::SUBC:
2357    Tmp1 = LegalizeOp(Node->getOperand(0));
2358    Tmp2 = LegalizeOp(Node->getOperand(1));
2359    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2360    // Since this produces two values, make sure to remember that we legalized
2361    // both of them.
2362    AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
2363    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
2364    return Result;
2365
2366  case ISD::ADDE:
2367  case ISD::SUBE:
2368    Tmp1 = LegalizeOp(Node->getOperand(0));
2369    Tmp2 = LegalizeOp(Node->getOperand(1));
2370    Tmp3 = LegalizeOp(Node->getOperand(2));
2371    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3);
2372    // Since this produces two values, make sure to remember that we legalized
2373    // both of them.
2374    AddLegalizedOperand(SDOperand(Node, 0), Result.getValue(0));
2375    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
2376    return Result;
2377
2378  case ISD::BUILD_PAIR: {
2379    MVT::ValueType PairTy = Node->getValueType(0);
2380    // TODO: handle the case where the Lo and Hi operands are not of legal type
2381    Tmp1 = LegalizeOp(Node->getOperand(0));   // Lo
2382    Tmp2 = LegalizeOp(Node->getOperand(1));   // Hi
2383    switch (TLI.getOperationAction(ISD::BUILD_PAIR, PairTy)) {
2384    case TargetLowering::Promote:
2385    case TargetLowering::Custom:
2386      assert(0 && "Cannot promote/custom this yet!");
2387    case TargetLowering::Legal:
2388      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
2389        Result = DAG.getNode(ISD::BUILD_PAIR, PairTy, Tmp1, Tmp2);
2390      break;
2391    case TargetLowering::Expand:
2392      Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, PairTy, Tmp1);
2393      Tmp2 = DAG.getNode(ISD::ANY_EXTEND, PairTy, Tmp2);
2394      Tmp2 = DAG.getNode(ISD::SHL, PairTy, Tmp2,
2395                         DAG.getConstant(MVT::getSizeInBits(PairTy)/2,
2396                                         TLI.getShiftAmountTy()));
2397      Result = DAG.getNode(ISD::OR, PairTy, Tmp1, Tmp2);
2398      break;
2399    }
2400    break;
2401  }
2402
2403  case ISD::UREM:
2404  case ISD::SREM:
2405  case ISD::FREM:
2406    Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2407    Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2408
2409    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2410    case TargetLowering::Promote: assert(0 && "Cannot promote this yet!");
2411    case TargetLowering::Custom:
2412      isCustom = true;
2413      // FALLTHROUGH
2414    case TargetLowering::Legal:
2415      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2416      if (isCustom) {
2417        Tmp1 = TLI.LowerOperation(Result, DAG);
2418        if (Tmp1.Val) Result = Tmp1;
2419      }
2420      break;
2421    case TargetLowering::Expand:
2422      unsigned DivOpc= (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV;
2423      if (MVT::isInteger(Node->getValueType(0))) {
2424        if (TLI.getOperationAction(DivOpc, Node->getValueType(0)) ==
2425            TargetLowering::Legal) {
2426          // X % Y -> X-X/Y*Y
2427          MVT::ValueType VT = Node->getValueType(0);
2428          Result = DAG.getNode(DivOpc, VT, Tmp1, Tmp2);
2429          Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
2430          Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
2431        } else {
2432          assert(Node->getValueType(0) == MVT::i32 &&
2433                 "Cannot expand this binary operator!");
2434          const char *FnName = Node->getOpcode() == ISD::UREM
2435            ? "__umodsi3" : "__modsi3";
2436          SDOperand Dummy;
2437          Result = ExpandLibCall(FnName, Node, Dummy);
2438        }
2439      } else {
2440        // Floating point mod -> fmod libcall.
2441        const char *FnName = Node->getValueType(0) == MVT::f32 ? "fmodf":"fmod";
2442        SDOperand Dummy;
2443        Result = ExpandLibCall(FnName, Node, Dummy);
2444      }
2445      break;
2446    }
2447    break;
2448  case ISD::VAARG: {
2449    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2450    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2451
2452    MVT::ValueType VT = Node->getValueType(0);
2453    switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
2454    default: assert(0 && "This action is not supported yet!");
2455    case TargetLowering::Custom:
2456      isCustom = true;
2457      // FALLTHROUGH
2458    case TargetLowering::Legal:
2459      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2460      Result = Result.getValue(0);
2461      Tmp1 = Result.getValue(1);
2462
2463      if (isCustom) {
2464        Tmp2 = TLI.LowerOperation(Result, DAG);
2465        if (Tmp2.Val) {
2466          Result = LegalizeOp(Tmp2);
2467          Tmp1 = LegalizeOp(Tmp2.getValue(1));
2468        }
2469      }
2470      break;
2471    case TargetLowering::Expand: {
2472      SrcValueSDNode *SV = cast<SrcValueSDNode>(Node->getOperand(2));
2473      SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
2474                                     SV->getValue(), SV->getOffset());
2475      // Increment the pointer, VAList, to the next vaarg
2476      Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
2477                         DAG.getConstant(MVT::getSizeInBits(VT)/8,
2478                                         TLI.getPointerTy()));
2479      // Store the incremented VAList to the legalized pointer
2480      Tmp3 = DAG.getStore(VAList.getValue(1), Tmp3, Tmp2, SV->getValue(),
2481                          SV->getOffset());
2482      // Load the actual argument out of the pointer VAList
2483      Result = DAG.getLoad(VT, Tmp3, VAList, NULL, 0);
2484      Tmp1 = LegalizeOp(Result.getValue(1));
2485      Result = LegalizeOp(Result);
2486      break;
2487    }
2488    }
2489    // Since VAARG produces two values, make sure to remember that we
2490    // legalized both of them.
2491    AddLegalizedOperand(SDOperand(Node, 0), Result);
2492    AddLegalizedOperand(SDOperand(Node, 1), Tmp1);
2493    return Op.ResNo ? Tmp1 : Result;
2494  }
2495
2496  case ISD::VACOPY:
2497    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2498    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the dest pointer.
2499    Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the source pointer.
2500
2501    switch (TLI.getOperationAction(ISD::VACOPY, MVT::Other)) {
2502    default: assert(0 && "This action is not supported yet!");
2503    case TargetLowering::Custom:
2504      isCustom = true;
2505      // FALLTHROUGH
2506    case TargetLowering::Legal:
2507      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Tmp3,
2508                                      Node->getOperand(3), Node->getOperand(4));
2509      if (isCustom) {
2510        Tmp1 = TLI.LowerOperation(Result, DAG);
2511        if (Tmp1.Val) Result = Tmp1;
2512      }
2513      break;
2514    case TargetLowering::Expand:
2515      // This defaults to loading a pointer from the input and storing it to the
2516      // output, returning the chain.
2517      SrcValueSDNode *SVD = cast<SrcValueSDNode>(Node->getOperand(3));
2518      SrcValueSDNode *SVS = cast<SrcValueSDNode>(Node->getOperand(4));
2519      Tmp4 = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp3, SVD->getValue(),
2520                         SVD->getOffset());
2521      Result = DAG.getStore(Tmp4.getValue(1), Tmp4, Tmp2, SVS->getValue(),
2522                            SVS->getOffset());
2523      break;
2524    }
2525    break;
2526
2527  case ISD::VAEND:
2528    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2529    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2530
2531    switch (TLI.getOperationAction(ISD::VAEND, MVT::Other)) {
2532    default: assert(0 && "This action is not supported yet!");
2533    case TargetLowering::Custom:
2534      isCustom = true;
2535      // FALLTHROUGH
2536    case TargetLowering::Legal:
2537      Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2538      if (isCustom) {
2539        Tmp1 = TLI.LowerOperation(Tmp1, DAG);
2540        if (Tmp1.Val) Result = Tmp1;
2541      }
2542      break;
2543    case TargetLowering::Expand:
2544      Result = Tmp1; // Default to a no-op, return the chain
2545      break;
2546    }
2547    break;
2548
2549  case ISD::VASTART:
2550    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
2551    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
2552
2553    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
2554
2555    switch (TLI.getOperationAction(ISD::VASTART, MVT::Other)) {
2556    default: assert(0 && "This action is not supported yet!");
2557    case TargetLowering::Legal: break;
2558    case TargetLowering::Custom:
2559      Tmp1 = TLI.LowerOperation(Result, DAG);
2560      if (Tmp1.Val) Result = Tmp1;
2561      break;
2562    }
2563    break;
2564
2565  case ISD::ROTL:
2566  case ISD::ROTR:
2567    Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
2568    Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
2569
2570    assert(TLI.isOperationLegal(Node->getOpcode(), Node->getValueType(0)) &&
2571           "Cannot handle this yet!");
2572    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
2573    break;
2574
2575  case ISD::BSWAP:
2576    Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2577    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2578    case TargetLowering::Custom:
2579      assert(0 && "Cannot custom legalize this yet!");
2580    case TargetLowering::Legal:
2581      Result = DAG.UpdateNodeOperands(Result, Tmp1);
2582      break;
2583    case TargetLowering::Promote: {
2584      MVT::ValueType OVT = Tmp1.getValueType();
2585      MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2586      unsigned DiffBits = getSizeInBits(NVT) - getSizeInBits(OVT);
2587
2588      Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2589      Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
2590      Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
2591                           DAG.getConstant(DiffBits, TLI.getShiftAmountTy()));
2592      break;
2593    }
2594    case TargetLowering::Expand:
2595      Result = ExpandBSWAP(Tmp1);
2596      break;
2597    }
2598    break;
2599
2600  case ISD::CTPOP:
2601  case ISD::CTTZ:
2602  case ISD::CTLZ:
2603    Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
2604    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2605    case TargetLowering::Custom: assert(0 && "Cannot custom handle this yet!");
2606    case TargetLowering::Legal:
2607      Result = DAG.UpdateNodeOperands(Result, Tmp1);
2608      break;
2609    case TargetLowering::Promote: {
2610      MVT::ValueType OVT = Tmp1.getValueType();
2611      MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
2612
2613      // Zero extend the argument.
2614      Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
2615      // Perform the larger operation, then subtract if needed.
2616      Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
2617      switch (Node->getOpcode()) {
2618      case ISD::CTPOP:
2619        Result = Tmp1;
2620        break;
2621      case ISD::CTTZ:
2622        //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
2623        Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
2624                            DAG.getConstant(getSizeInBits(NVT), NVT),
2625                            ISD::SETEQ);
2626        Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
2627                           DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
2628        break;
2629      case ISD::CTLZ:
2630        // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
2631        Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
2632                             DAG.getConstant(getSizeInBits(NVT) -
2633                                             getSizeInBits(OVT), NVT));
2634        break;
2635      }
2636      break;
2637    }
2638    case TargetLowering::Expand:
2639      Result = ExpandBitCount(Node->getOpcode(), Tmp1);
2640      break;
2641    }
2642    break;
2643
2644    // Unary operators
2645  case ISD::FABS:
2646  case ISD::FNEG:
2647  case ISD::FSQRT:
2648  case ISD::FSIN:
2649  case ISD::FCOS:
2650    Tmp1 = LegalizeOp(Node->getOperand(0));
2651    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
2652    case TargetLowering::Promote:
2653    case TargetLowering::Custom:
2654     isCustom = true;
2655     // FALLTHROUGH
2656    case TargetLowering::Legal:
2657      Result = DAG.UpdateNodeOperands(Result, Tmp1);
2658      if (isCustom) {
2659        Tmp1 = TLI.LowerOperation(Result, DAG);
2660        if (Tmp1.Val) Result = Tmp1;
2661      }
2662      break;
2663    case TargetLowering::Expand:
2664      switch (Node->getOpcode()) {
2665      default: assert(0 && "Unreachable!");
2666      case ISD::FNEG:
2667        // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
2668        Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
2669        Result = DAG.getNode(ISD::FSUB, Node->getValueType(0), Tmp2, Tmp1);
2670        break;
2671      case ISD::FABS: {
2672        // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
2673        MVT::ValueType VT = Node->getValueType(0);
2674        Tmp2 = DAG.getConstantFP(0.0, VT);
2675        Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, Tmp2, ISD::SETUGT);
2676        Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
2677        Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
2678        break;
2679      }
2680      case ISD::FSQRT:
2681      case ISD::FSIN:
2682      case ISD::FCOS: {
2683        MVT::ValueType VT = Node->getValueType(0);
2684        const char *FnName = 0;
2685        switch(Node->getOpcode()) {
2686        case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
2687        case ISD::FSIN:  FnName = VT == MVT::f32 ? "sinf"  : "sin"; break;
2688        case ISD::FCOS:  FnName = VT == MVT::f32 ? "cosf"  : "cos"; break;
2689        default: assert(0 && "Unreachable!");
2690        }
2691        SDOperand Dummy;
2692        Result = ExpandLibCall(FnName, Node, Dummy);
2693        break;
2694      }
2695      }
2696      break;
2697    }
2698    break;
2699  case ISD::FPOWI: {
2700    // We always lower FPOWI into a libcall.  No target support it yet.
2701    const char *FnName = Node->getValueType(0) == MVT::f32
2702                            ? "__powisf2" : "__powidf2";
2703    SDOperand Dummy;
2704    Result = ExpandLibCall(FnName, Node, Dummy);
2705    break;
2706  }
2707  case ISD::BIT_CONVERT:
2708    if (!isTypeLegal(Node->getOperand(0).getValueType())) {
2709      Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2710    } else {
2711      switch (TLI.getOperationAction(ISD::BIT_CONVERT,
2712                                     Node->getOperand(0).getValueType())) {
2713      default: assert(0 && "Unknown operation action!");
2714      case TargetLowering::Expand:
2715        Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
2716        break;
2717      case TargetLowering::Legal:
2718        Tmp1 = LegalizeOp(Node->getOperand(0));
2719        Result = DAG.UpdateNodeOperands(Result, Tmp1);
2720        break;
2721      }
2722    }
2723    break;
2724  case ISD::VBIT_CONVERT: {
2725    assert(Op.getOperand(0).getValueType() == MVT::Vector &&
2726           "Can only have VBIT_CONVERT where input or output is MVT::Vector!");
2727
2728    // The input has to be a vector type, we have to either scalarize it, pack
2729    // it, or convert it based on whether the input vector type is legal.
2730    SDNode *InVal = Node->getOperand(0).Val;
2731    unsigned NumElems =
2732      cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
2733    MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
2734
2735    // Figure out if there is a Packed type corresponding to this Vector
2736    // type.  If so, convert to the packed type.
2737    MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
2738    if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
2739      // Turn this into a bit convert of the packed input.
2740      Result = DAG.getNode(ISD::BIT_CONVERT, Node->getValueType(0),
2741                           PackVectorOp(Node->getOperand(0), TVT));
2742      break;
2743    } else if (NumElems == 1) {
2744      // Turn this into a bit convert of the scalar input.
2745      Result = DAG.getNode(ISD::BIT_CONVERT, Node->getValueType(0),
2746                           PackVectorOp(Node->getOperand(0), EVT));
2747      break;
2748    } else {
2749      // FIXME: UNIMP!  Store then reload
2750      assert(0 && "Cast from unsupported vector type not implemented yet!");
2751    }
2752  }
2753
2754    // Conversion operators.  The source and destination have different types.
2755  case ISD::SINT_TO_FP:
2756  case ISD::UINT_TO_FP: {
2757    bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP;
2758    switch (getTypeAction(Node->getOperand(0).getValueType())) {
2759    case Legal:
2760      switch (TLI.getOperationAction(Node->getOpcode(),
2761                                     Node->getOperand(0).getValueType())) {
2762      default: assert(0 && "Unknown operation action!");
2763      case TargetLowering::Custom:
2764        isCustom = true;
2765        // FALLTHROUGH
2766      case TargetLowering::Legal:
2767        Tmp1 = LegalizeOp(Node->getOperand(0));
2768        Result = DAG.UpdateNodeOperands(Result, Tmp1);
2769        if (isCustom) {
2770          Tmp1 = TLI.LowerOperation(Result, DAG);
2771          if (Tmp1.Val) Result = Tmp1;
2772        }
2773        break;
2774      case TargetLowering::Expand:
2775        Result = ExpandLegalINT_TO_FP(isSigned,
2776                                      LegalizeOp(Node->getOperand(0)),
2777                                      Node->getValueType(0));
2778        break;
2779      case TargetLowering::Promote:
2780        Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)),
2781                                       Node->getValueType(0),
2782                                       isSigned);
2783        break;
2784      }
2785      break;
2786    case Expand:
2787      Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
2788                             Node->getValueType(0), Node->getOperand(0));
2789      break;
2790    case Promote:
2791      Tmp1 = PromoteOp(Node->getOperand(0));
2792      if (isSigned) {
2793        Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, Tmp1.getValueType(),
2794                 Tmp1, DAG.getValueType(Node->getOperand(0).getValueType()));
2795      } else {
2796        Tmp1 = DAG.getZeroExtendInReg(Tmp1,
2797                                      Node->getOperand(0).getValueType());
2798      }
2799      Result = DAG.UpdateNodeOperands(Result, Tmp1);
2800      Result = LegalizeOp(Result);  // The 'op' is not necessarily legal!
2801      break;
2802    }
2803    break;
2804  }
2805  case ISD::TRUNCATE:
2806    switch (getTypeAction(Node->getOperand(0).getValueType())) {
2807    case Legal:
2808      Tmp1 = LegalizeOp(Node->getOperand(0));
2809      Result = DAG.UpdateNodeOperands(Result, Tmp1);
2810      break;
2811    case Expand:
2812      ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
2813
2814      // Since the result is legal, we should just be able to truncate the low
2815      // part of the source.
2816      Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
2817      break;
2818    case Promote:
2819      Result = PromoteOp(Node->getOperand(0));
2820      Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
2821      break;
2822    }
2823    break;
2824
2825  case ISD::FP_TO_SINT:
2826  case ISD::FP_TO_UINT:
2827    switch (getTypeAction(Node->getOperand(0).getValueType())) {
2828    case Legal:
2829      Tmp1 = LegalizeOp(Node->getOperand(0));
2830
2831      switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){
2832      default: assert(0 && "Unknown operation action!");
2833      case TargetLowering::Custom:
2834        isCustom = true;
2835        // FALLTHROUGH
2836      case TargetLowering::Legal:
2837        Result = DAG.UpdateNodeOperands(Result, Tmp1);
2838        if (isCustom) {
2839          Tmp1 = TLI.LowerOperation(Result, DAG);
2840          if (Tmp1.Val) Result = Tmp1;
2841        }
2842        break;
2843      case TargetLowering::Promote:
2844        Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0),
2845                                       Node->getOpcode() == ISD::FP_TO_SINT);
2846        break;
2847      case TargetLowering::Expand:
2848        if (Node->getOpcode() == ISD::FP_TO_UINT) {
2849          SDOperand True, False;
2850          MVT::ValueType VT =  Node->getOperand(0).getValueType();
2851          MVT::ValueType NVT = Node->getValueType(0);
2852          unsigned ShiftAmt = MVT::getSizeInBits(Node->getValueType(0))-1;
2853          Tmp2 = DAG.getConstantFP((double)(1ULL << ShiftAmt), VT);
2854          Tmp3 = DAG.getSetCC(TLI.getSetCCResultTy(),
2855                            Node->getOperand(0), Tmp2, ISD::SETLT);
2856          True = DAG.getNode(ISD::FP_TO_SINT, NVT, Node->getOperand(0));
2857          False = DAG.getNode(ISD::FP_TO_SINT, NVT,
2858                              DAG.getNode(ISD::FSUB, VT, Node->getOperand(0),
2859                                          Tmp2));
2860          False = DAG.getNode(ISD::XOR, NVT, False,
2861                              DAG.getConstant(1ULL << ShiftAmt, NVT));
2862          Result = DAG.getNode(ISD::SELECT, NVT, Tmp3, True, False);
2863          break;
2864        } else {
2865          assert(0 && "Do not know how to expand FP_TO_SINT yet!");
2866        }
2867        break;
2868      }
2869      break;
2870    case Expand: {
2871      // Convert f32 / f64 to i32 / i64.
2872      MVT::ValueType VT = Op.getValueType();
2873      const char *FnName = 0;
2874      switch (Node->getOpcode()) {
2875      case ISD::FP_TO_SINT:
2876        if (Node->getOperand(0).getValueType() == MVT::f32)
2877          FnName = (VT == MVT::i32) ? "__fixsfsi" : "__fixsfdi";
2878        else
2879          FnName = (VT == MVT::i32) ? "__fixdfsi" : "__fixdfdi";
2880        break;
2881      case ISD::FP_TO_UINT:
2882        if (Node->getOperand(0).getValueType() == MVT::f32)
2883          FnName = (VT == MVT::i32) ? "__fixunssfsi" : "__fixunssfdi";
2884        else
2885          FnName = (VT == MVT::i32) ? "__fixunsdfsi" : "__fixunsdfdi";
2886        break;
2887      default: assert(0 && "Unreachable!");
2888      }
2889      SDOperand Dummy;
2890      Result = ExpandLibCall(FnName, Node, Dummy);
2891      break;
2892    }
2893    case Promote:
2894      Tmp1 = PromoteOp(Node->getOperand(0));
2895      Result = DAG.UpdateNodeOperands(Result, LegalizeOp(Tmp1));
2896      Result = LegalizeOp(Result);
2897      break;
2898    }
2899    break;
2900
2901  case ISD::ANY_EXTEND:
2902  case ISD::ZERO_EXTEND:
2903  case ISD::SIGN_EXTEND:
2904  case ISD::FP_EXTEND:
2905  case ISD::FP_ROUND:
2906    switch (getTypeAction(Node->getOperand(0).getValueType())) {
2907    case Expand: assert(0 && "Shouldn't need to expand other operators here!");
2908    case Legal:
2909      Tmp1 = LegalizeOp(Node->getOperand(0));
2910      Result = DAG.UpdateNodeOperands(Result, Tmp1);
2911      break;
2912    case Promote:
2913      switch (Node->getOpcode()) {
2914      case ISD::ANY_EXTEND:
2915        Tmp1 = PromoteOp(Node->getOperand(0));
2916        Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Tmp1);
2917        break;
2918      case ISD::ZERO_EXTEND:
2919        Result = PromoteOp(Node->getOperand(0));
2920        Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2921        Result = DAG.getZeroExtendInReg(Result,
2922                                        Node->getOperand(0).getValueType());
2923        break;
2924      case ISD::SIGN_EXTEND:
2925        Result = PromoteOp(Node->getOperand(0));
2926        Result = DAG.getNode(ISD::ANY_EXTEND, Op.getValueType(), Result);
2927        Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
2928                             Result,
2929                          DAG.getValueType(Node->getOperand(0).getValueType()));
2930        break;
2931      case ISD::FP_EXTEND:
2932        Result = PromoteOp(Node->getOperand(0));
2933        if (Result.getValueType() != Op.getValueType())
2934          // Dynamically dead while we have only 2 FP types.
2935          Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
2936        break;
2937      case ISD::FP_ROUND:
2938        Result = PromoteOp(Node->getOperand(0));
2939        Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
2940        break;
2941      }
2942    }
2943    break;
2944  case ISD::FP_ROUND_INREG:
2945  case ISD::SIGN_EXTEND_INREG: {
2946    Tmp1 = LegalizeOp(Node->getOperand(0));
2947    MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
2948
2949    // If this operation is not supported, convert it to a shl/shr or load/store
2950    // pair.
2951    switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
2952    default: assert(0 && "This action not supported for this op yet!");
2953    case TargetLowering::Legal:
2954      Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
2955      break;
2956    case TargetLowering::Expand:
2957      // If this is an integer extend and shifts are supported, do that.
2958      if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
2959        // NOTE: we could fall back on load/store here too for targets without
2960        // SAR.  However, it is doubtful that any exist.
2961        unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
2962                            MVT::getSizeInBits(ExtraVT);
2963        SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy());
2964        Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
2965                             Node->getOperand(0), ShiftCst);
2966        Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
2967                             Result, ShiftCst);
2968      } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
2969        // The only way we can lower this is to turn it into a TRUNCSTORE,
2970        // EXTLOAD pair, targetting a temporary location (a stack slot).
2971
2972        // NOTE: there is a choice here between constantly creating new stack
2973        // slots and always reusing the same one.  We currently always create
2974        // new ones, as reuse may inhibit scheduling.
2975        const Type *Ty = MVT::getTypeForValueType(ExtraVT);
2976        unsigned TySize = (unsigned)TLI.getTargetData()->getTypeSize(Ty);
2977        unsigned Align  = TLI.getTargetData()->getTypeAlignment(Ty);
2978        MachineFunction &MF = DAG.getMachineFunction();
2979        int SSFI =
2980          MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
2981        SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
2982        Result = DAG.getTruncStore(DAG.getEntryNode(), Node->getOperand(0),
2983                                   StackSlot, NULL, 0, ExtraVT);
2984        Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0),
2985                                Result, StackSlot, NULL, 0, ExtraVT);
2986      } else {
2987        assert(0 && "Unknown op");
2988      }
2989      break;
2990    }
2991    break;
2992  }
2993  }
2994
2995  assert(Result.getValueType() == Op.getValueType() &&
2996         "Bad legalization!");
2997
2998  // Make sure that the generated code is itself legal.
2999  if (Result != Op)
3000    Result = LegalizeOp(Result);
3001
3002  // Note that LegalizeOp may be reentered even from single-use nodes, which
3003  // means that we always must cache transformed nodes.
3004  AddLegalizedOperand(Op, Result);
3005  return Result;
3006}
3007
3008/// PromoteOp - Given an operation that produces a value in an invalid type,
3009/// promote it to compute the value into a larger type.  The produced value will
3010/// have the correct bits for the low portion of the register, but no guarantee
3011/// is made about the top bits: it may be zero, sign-extended, or garbage.
3012SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
3013  MVT::ValueType VT = Op.getValueType();
3014  MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
3015  assert(getTypeAction(VT) == Promote &&
3016         "Caller should expand or legalize operands that are not promotable!");
3017  assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
3018         "Cannot promote to smaller type!");
3019
3020  SDOperand Tmp1, Tmp2, Tmp3;
3021  SDOperand Result;
3022  SDNode *Node = Op.Val;
3023
3024  std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
3025  if (I != PromotedNodes.end()) return I->second;
3026
3027  switch (Node->getOpcode()) {
3028  case ISD::CopyFromReg:
3029    assert(0 && "CopyFromReg must be legal!");
3030  default:
3031#ifndef NDEBUG
3032    cerr << "NODE: "; Node->dump(); cerr << "\n";
3033#endif
3034    assert(0 && "Do not know how to promote this operator!");
3035    abort();
3036  case ISD::UNDEF:
3037    Result = DAG.getNode(ISD::UNDEF, NVT);
3038    break;
3039  case ISD::Constant:
3040    if (VT != MVT::i1)
3041      Result = DAG.getNode(ISD::SIGN_EXTEND, NVT, Op);
3042    else
3043      Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
3044    assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
3045    break;
3046  case ISD::ConstantFP:
3047    Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
3048    assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
3049    break;
3050
3051  case ISD::SETCC:
3052    assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??");
3053    Result = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),Node->getOperand(0),
3054                         Node->getOperand(1), Node->getOperand(2));
3055    break;
3056
3057  case ISD::TRUNCATE:
3058    switch (getTypeAction(Node->getOperand(0).getValueType())) {
3059    case Legal:
3060      Result = LegalizeOp(Node->getOperand(0));
3061      assert(Result.getValueType() >= NVT &&
3062             "This truncation doesn't make sense!");
3063      if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
3064        Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
3065      break;
3066    case Promote:
3067      // The truncation is not required, because we don't guarantee anything
3068      // about high bits anyway.
3069      Result = PromoteOp(Node->getOperand(0));
3070      break;
3071    case Expand:
3072      ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
3073      // Truncate the low part of the expanded value to the result type
3074      Result = DAG.getNode(ISD::TRUNCATE, NVT, Tmp1);
3075    }
3076    break;
3077  case ISD::SIGN_EXTEND:
3078  case ISD::ZERO_EXTEND:
3079  case ISD::ANY_EXTEND:
3080    switch (getTypeAction(Node->getOperand(0).getValueType())) {
3081    case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
3082    case Legal:
3083      // Input is legal?  Just do extend all the way to the larger type.
3084      Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
3085      break;
3086    case Promote:
3087      // Promote the reg if it's smaller.
3088      Result = PromoteOp(Node->getOperand(0));
3089      // The high bits are not guaranteed to be anything.  Insert an extend.
3090      if (Node->getOpcode() == ISD::SIGN_EXTEND)
3091        Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
3092                         DAG.getValueType(Node->getOperand(0).getValueType()));
3093      else if (Node->getOpcode() == ISD::ZERO_EXTEND)
3094        Result = DAG.getZeroExtendInReg(Result,
3095                                        Node->getOperand(0).getValueType());
3096      break;
3097    }
3098    break;
3099  case ISD::BIT_CONVERT:
3100    Result = ExpandBIT_CONVERT(Node->getValueType(0), Node->getOperand(0));
3101    Result = PromoteOp(Result);
3102    break;
3103
3104  case ISD::FP_EXTEND:
3105    assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
3106  case ISD::FP_ROUND:
3107    switch (getTypeAction(Node->getOperand(0).getValueType())) {
3108    case Expand: assert(0 && "BUG: Cannot expand FP regs!");
3109    case Promote:  assert(0 && "Unreachable with 2 FP types!");
3110    case Legal:
3111      // Input is legal?  Do an FP_ROUND_INREG.
3112      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Node->getOperand(0),
3113                           DAG.getValueType(VT));
3114      break;
3115    }
3116    break;
3117
3118  case ISD::SINT_TO_FP:
3119  case ISD::UINT_TO_FP:
3120    switch (getTypeAction(Node->getOperand(0).getValueType())) {
3121    case Legal:
3122      // No extra round required here.
3123      Result = DAG.getNode(Node->getOpcode(), NVT, Node->getOperand(0));
3124      break;
3125
3126    case Promote:
3127      Result = PromoteOp(Node->getOperand(0));
3128      if (Node->getOpcode() == ISD::SINT_TO_FP)
3129        Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
3130                             Result,
3131                         DAG.getValueType(Node->getOperand(0).getValueType()));
3132      else
3133        Result = DAG.getZeroExtendInReg(Result,
3134                                        Node->getOperand(0).getValueType());
3135      // No extra round required here.
3136      Result = DAG.getNode(Node->getOpcode(), NVT, Result);
3137      break;
3138    case Expand:
3139      Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
3140                             Node->getOperand(0));
3141      // Round if we cannot tolerate excess precision.
3142      if (NoExcessFPPrecision)
3143        Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3144                             DAG.getValueType(VT));
3145      break;
3146    }
3147    break;
3148
3149  case ISD::SIGN_EXTEND_INREG:
3150    Result = PromoteOp(Node->getOperand(0));
3151    Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
3152                         Node->getOperand(1));
3153    break;
3154  case ISD::FP_TO_SINT:
3155  case ISD::FP_TO_UINT:
3156    switch (getTypeAction(Node->getOperand(0).getValueType())) {
3157    case Legal:
3158    case Expand:
3159      Tmp1 = Node->getOperand(0);
3160      break;
3161    case Promote:
3162      // The input result is prerounded, so we don't have to do anything
3163      // special.
3164      Tmp1 = PromoteOp(Node->getOperand(0));
3165      break;
3166    }
3167    // If we're promoting a UINT to a larger size, check to see if the new node
3168    // will be legal.  If it isn't, check to see if FP_TO_SINT is legal, since
3169    // we can use that instead.  This allows us to generate better code for
3170    // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not
3171    // legal, such as PowerPC.
3172    if (Node->getOpcode() == ISD::FP_TO_UINT &&
3173        !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
3174        (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) ||
3175         TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom)){
3176      Result = DAG.getNode(ISD::FP_TO_SINT, NVT, Tmp1);
3177    } else {
3178      Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
3179    }
3180    break;
3181
3182  case ISD::FABS:
3183  case ISD::FNEG:
3184    Tmp1 = PromoteOp(Node->getOperand(0));
3185    assert(Tmp1.getValueType() == NVT);
3186    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
3187    // NOTE: we do not have to do any extra rounding here for
3188    // NoExcessFPPrecision, because we know the input will have the appropriate
3189    // precision, and these operations don't modify precision at all.
3190    break;
3191
3192  case ISD::FSQRT:
3193  case ISD::FSIN:
3194  case ISD::FCOS:
3195    Tmp1 = PromoteOp(Node->getOperand(0));
3196    assert(Tmp1.getValueType() == NVT);
3197    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
3198    if (NoExcessFPPrecision)
3199      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3200                           DAG.getValueType(VT));
3201    break;
3202
3203  case ISD::AND:
3204  case ISD::OR:
3205  case ISD::XOR:
3206  case ISD::ADD:
3207  case ISD::SUB:
3208  case ISD::MUL:
3209    // The input may have strange things in the top bits of the registers, but
3210    // these operations don't care.  They may have weird bits going out, but
3211    // that too is okay if they are integer operations.
3212    Tmp1 = PromoteOp(Node->getOperand(0));
3213    Tmp2 = PromoteOp(Node->getOperand(1));
3214    assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
3215    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3216    break;
3217  case ISD::FADD:
3218  case ISD::FSUB:
3219  case ISD::FMUL:
3220    Tmp1 = PromoteOp(Node->getOperand(0));
3221    Tmp2 = PromoteOp(Node->getOperand(1));
3222    assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
3223    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3224
3225    // Floating point operations will give excess precision that we may not be
3226    // able to tolerate.  If we DO allow excess precision, just leave it,
3227    // otherwise excise it.
3228    // FIXME: Why would we need to round FP ops more than integer ones?
3229    //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
3230    if (NoExcessFPPrecision)
3231      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3232                           DAG.getValueType(VT));
3233    break;
3234
3235  case ISD::SDIV:
3236  case ISD::SREM:
3237    // These operators require that their input be sign extended.
3238    Tmp1 = PromoteOp(Node->getOperand(0));
3239    Tmp2 = PromoteOp(Node->getOperand(1));
3240    if (MVT::isInteger(NVT)) {
3241      Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
3242                         DAG.getValueType(VT));
3243      Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
3244                         DAG.getValueType(VT));
3245    }
3246    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3247
3248    // Perform FP_ROUND: this is probably overly pessimistic.
3249    if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
3250      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3251                           DAG.getValueType(VT));
3252    break;
3253  case ISD::FDIV:
3254  case ISD::FREM:
3255  case ISD::FCOPYSIGN:
3256    // These operators require that their input be fp extended.
3257    switch (getTypeAction(Node->getOperand(0).getValueType())) {
3258      case Legal:
3259        Tmp1 = LegalizeOp(Node->getOperand(0));
3260        break;
3261      case Promote:
3262        Tmp1 = PromoteOp(Node->getOperand(0));
3263        break;
3264      case Expand:
3265        assert(0 && "not implemented");
3266    }
3267    switch (getTypeAction(Node->getOperand(1).getValueType())) {
3268      case Legal:
3269        Tmp2 = LegalizeOp(Node->getOperand(1));
3270        break;
3271      case Promote:
3272        Tmp2 = PromoteOp(Node->getOperand(1));
3273        break;
3274      case Expand:
3275        assert(0 && "not implemented");
3276    }
3277    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3278
3279    // Perform FP_ROUND: this is probably overly pessimistic.
3280    if (NoExcessFPPrecision && Node->getOpcode() != ISD::FCOPYSIGN)
3281      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result,
3282                           DAG.getValueType(VT));
3283    break;
3284
3285  case ISD::UDIV:
3286  case ISD::UREM:
3287    // These operators require that their input be zero extended.
3288    Tmp1 = PromoteOp(Node->getOperand(0));
3289    Tmp2 = PromoteOp(Node->getOperand(1));
3290    assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
3291    Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
3292    Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
3293    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
3294    break;
3295
3296  case ISD::SHL:
3297    Tmp1 = PromoteOp(Node->getOperand(0));
3298    Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Node->getOperand(1));
3299    break;
3300  case ISD::SRA:
3301    // The input value must be properly sign extended.
3302    Tmp1 = PromoteOp(Node->getOperand(0));
3303    Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
3304                       DAG.getValueType(VT));
3305    Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Node->getOperand(1));
3306    break;
3307  case ISD::SRL:
3308    // The input value must be properly zero extended.
3309    Tmp1 = PromoteOp(Node->getOperand(0));
3310    Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
3311    Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Node->getOperand(1));
3312    break;
3313
3314  case ISD::VAARG:
3315    Tmp1 = Node->getOperand(0);   // Get the chain.
3316    Tmp2 = Node->getOperand(1);   // Get the pointer.
3317    if (TLI.getOperationAction(ISD::VAARG, VT) == TargetLowering::Custom) {
3318      Tmp3 = DAG.getVAArg(VT, Tmp1, Tmp2, Node->getOperand(2));
3319      Result = TLI.CustomPromoteOperation(Tmp3, DAG);
3320    } else {
3321      SrcValueSDNode *SV = cast<SrcValueSDNode>(Node->getOperand(2));
3322      SDOperand VAList = DAG.getLoad(TLI.getPointerTy(), Tmp1, Tmp2,
3323                                     SV->getValue(), SV->getOffset());
3324      // Increment the pointer, VAList, to the next vaarg
3325      Tmp3 = DAG.getNode(ISD::ADD, TLI.getPointerTy(), VAList,
3326                         DAG.getConstant(MVT::getSizeInBits(VT)/8,
3327                                         TLI.getPointerTy()));
3328      // Store the incremented VAList to the legalized pointer
3329      Tmp3 = DAG.getStore(VAList.getValue(1), Tmp3, Tmp2, SV->getValue(),
3330                          SV->getOffset());
3331      // Load the actual argument out of the pointer VAList
3332      Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp3, VAList, NULL, 0, VT);
3333    }
3334    // Remember that we legalized the chain.
3335    AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
3336    break;
3337
3338  case ISD::LOAD: {
3339    LoadSDNode *LD = cast<LoadSDNode>(Node);
3340    ISD::LoadExtType ExtType = ISD::isNON_EXTLoad(Node)
3341      ? ISD::EXTLOAD : LD->getExtensionType();
3342    Result = DAG.getExtLoad(ExtType, NVT,
3343                            LD->getChain(), LD->getBasePtr(),
3344                            LD->getSrcValue(), LD->getSrcValueOffset(),
3345                            LD->getLoadedVT());
3346    // Remember that we legalized the chain.
3347    AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
3348    break;
3349  }
3350  case ISD::SELECT:
3351    Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
3352    Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
3353    Result = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), Tmp2, Tmp3);
3354    break;
3355  case ISD::SELECT_CC:
3356    Tmp2 = PromoteOp(Node->getOperand(2));   // True
3357    Tmp3 = PromoteOp(Node->getOperand(3));   // False
3358    Result = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
3359                         Node->getOperand(1), Tmp2, Tmp3, Node->getOperand(4));
3360    break;
3361  case ISD::BSWAP:
3362    Tmp1 = Node->getOperand(0);
3363    Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
3364    Tmp1 = DAG.getNode(ISD::BSWAP, NVT, Tmp1);
3365    Result = DAG.getNode(ISD::SRL, NVT, Tmp1,
3366                         DAG.getConstant(getSizeInBits(NVT) - getSizeInBits(VT),
3367                                         TLI.getShiftAmountTy()));
3368    break;
3369  case ISD::CTPOP:
3370  case ISD::CTTZ:
3371  case ISD::CTLZ:
3372    // Zero extend the argument
3373    Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
3374    // Perform the larger operation, then subtract if needed.
3375    Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
3376    switch(Node->getOpcode()) {
3377    case ISD::CTPOP:
3378      Result = Tmp1;
3379      break;
3380    case ISD::CTTZ:
3381      // if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
3382      Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1,
3383                          DAG.getConstant(getSizeInBits(NVT), NVT), ISD::SETEQ);
3384      Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
3385                           DAG.getConstant(getSizeInBits(VT), NVT), Tmp1);
3386      break;
3387    case ISD::CTLZ:
3388      //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
3389      Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
3390                           DAG.getConstant(getSizeInBits(NVT) -
3391                                           getSizeInBits(VT), NVT));
3392      break;
3393    }
3394    break;
3395  case ISD::VEXTRACT_VECTOR_ELT:
3396    Result = PromoteOp(LowerVEXTRACT_VECTOR_ELT(Op));
3397    break;
3398  case ISD::EXTRACT_VECTOR_ELT:
3399    Result = PromoteOp(ExpandEXTRACT_VECTOR_ELT(Op));
3400    break;
3401  }
3402
3403  assert(Result.Val && "Didn't set a result!");
3404
3405  // Make sure the result is itself legal.
3406  Result = LegalizeOp(Result);
3407
3408  // Remember that we promoted this!
3409  AddPromotedOperand(Op, Result);
3410  return Result;
3411}
3412
3413/// LowerVEXTRACT_VECTOR_ELT - Lower a VEXTRACT_VECTOR_ELT operation into a
3414/// EXTRACT_VECTOR_ELT operation, to memory operations, or to scalar code based
3415/// on the vector type.  The return type of this matches the element type of the
3416/// vector, which may not be legal for the target.
3417SDOperand SelectionDAGLegalize::LowerVEXTRACT_VECTOR_ELT(SDOperand Op) {
3418  // We know that operand #0 is the Vec vector.  If the index is a constant
3419  // or if the invec is a supported hardware type, we can use it.  Otherwise,
3420  // lower to a store then an indexed load.
3421  SDOperand Vec = Op.getOperand(0);
3422  SDOperand Idx = LegalizeOp(Op.getOperand(1));
3423
3424  SDNode *InVal = Vec.Val;
3425  unsigned NumElems = cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
3426  MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
3427
3428  // Figure out if there is a Packed type corresponding to this Vector
3429  // type.  If so, convert to the packed type.
3430  MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
3431  if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
3432    // Turn this into a packed extract_vector_elt operation.
3433    Vec = PackVectorOp(Vec, TVT);
3434    return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, Op.getValueType(), Vec, Idx);
3435  } else if (NumElems == 1) {
3436    // This must be an access of the only element.  Return it.
3437    return PackVectorOp(Vec, EVT);
3438  } else if (ConstantSDNode *CIdx = dyn_cast<ConstantSDNode>(Idx)) {
3439    SDOperand Lo, Hi;
3440    SplitVectorOp(Vec, Lo, Hi);
3441    if (CIdx->getValue() < NumElems/2) {
3442      Vec = Lo;
3443    } else {
3444      Vec = Hi;
3445      Idx = DAG.getConstant(CIdx->getValue() - NumElems/2, Idx.getValueType());
3446    }
3447
3448    // It's now an extract from the appropriate high or low part.  Recurse.
3449    Op = DAG.UpdateNodeOperands(Op, Vec, Idx);
3450    return LowerVEXTRACT_VECTOR_ELT(Op);
3451  } else {
3452    // Variable index case for extract element.
3453    // FIXME: IMPLEMENT STORE/LOAD lowering.  Need alignment of stack slot!!
3454    assert(0 && "unimp!");
3455    return SDOperand();
3456  }
3457}
3458
3459/// ExpandEXTRACT_VECTOR_ELT - Expand an EXTRACT_VECTOR_ELT operation into
3460/// memory traffic.
3461SDOperand SelectionDAGLegalize::ExpandEXTRACT_VECTOR_ELT(SDOperand Op) {
3462  SDOperand Vector = Op.getOperand(0);
3463  SDOperand Idx    = Op.getOperand(1);
3464
3465  // If the target doesn't support this, store the value to a temporary
3466  // stack slot, then LOAD the scalar element back out.
3467  SDOperand StackPtr = CreateStackTemporary(Vector.getValueType());
3468  SDOperand Ch = DAG.getStore(DAG.getEntryNode(), Vector, StackPtr, NULL, 0);
3469
3470  // Add the offset to the index.
3471  unsigned EltSize = MVT::getSizeInBits(Op.getValueType())/8;
3472  Idx = DAG.getNode(ISD::MUL, Idx.getValueType(), Idx,
3473                    DAG.getConstant(EltSize, Idx.getValueType()));
3474  StackPtr = DAG.getNode(ISD::ADD, Idx.getValueType(), Idx, StackPtr);
3475
3476  return DAG.getLoad(Op.getValueType(), Ch, StackPtr, NULL, 0);
3477}
3478
3479
3480/// LegalizeSetCCOperands - Attempts to create a legal LHS and RHS for a SETCC
3481/// with condition CC on the current target.  This usually involves legalizing
3482/// or promoting the arguments.  In the case where LHS and RHS must be expanded,
3483/// there may be no choice but to create a new SetCC node to represent the
3484/// legalized value of setcc lhs, rhs.  In this case, the value is returned in
3485/// LHS, and the SDOperand returned in RHS has a nil SDNode value.
3486void SelectionDAGLegalize::LegalizeSetCCOperands(SDOperand &LHS,
3487                                                 SDOperand &RHS,
3488                                                 SDOperand &CC) {
3489  SDOperand Tmp1, Tmp2, Result;
3490
3491  switch (getTypeAction(LHS.getValueType())) {
3492  case Legal:
3493    Tmp1 = LegalizeOp(LHS);   // LHS
3494    Tmp2 = LegalizeOp(RHS);   // RHS
3495    break;
3496  case Promote:
3497    Tmp1 = PromoteOp(LHS);   // LHS
3498    Tmp2 = PromoteOp(RHS);   // RHS
3499
3500    // If this is an FP compare, the operands have already been extended.
3501    if (MVT::isInteger(LHS.getValueType())) {
3502      MVT::ValueType VT = LHS.getValueType();
3503      MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
3504
3505      // Otherwise, we have to insert explicit sign or zero extends.  Note
3506      // that we could insert sign extends for ALL conditions, but zero extend
3507      // is cheaper on many machines (an AND instead of two shifts), so prefer
3508      // it.
3509      switch (cast<CondCodeSDNode>(CC)->get()) {
3510      default: assert(0 && "Unknown integer comparison!");
3511      case ISD::SETEQ:
3512      case ISD::SETNE:
3513      case ISD::SETUGE:
3514      case ISD::SETUGT:
3515      case ISD::SETULE:
3516      case ISD::SETULT:
3517        // ALL of these operations will work if we either sign or zero extend
3518        // the operands (including the unsigned comparisons!).  Zero extend is
3519        // usually a simpler/cheaper operation, so prefer it.
3520        Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
3521        Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
3522        break;
3523      case ISD::SETGE:
3524      case ISD::SETGT:
3525      case ISD::SETLT:
3526      case ISD::SETLE:
3527        Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1,
3528                           DAG.getValueType(VT));
3529        Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2,
3530                           DAG.getValueType(VT));
3531        break;
3532      }
3533    }
3534    break;
3535  case Expand: {
3536    MVT::ValueType VT = LHS.getValueType();
3537    if (VT == MVT::f32 || VT == MVT::f64) {
3538      // Expand into one or more soft-fp libcall(s).
3539      const char *FnName1 = NULL, *FnName2 = NULL;
3540      ISD::CondCode CC1, CC2 = ISD::SETCC_INVALID;
3541      switch (cast<CondCodeSDNode>(CC)->get()) {
3542      case ISD::SETEQ:
3543      case ISD::SETOEQ:
3544        FnName1 = (VT == MVT::f32) ? "__eqsf2" : "__eqdf2";
3545        CC1 = ISD::SETEQ;
3546        break;
3547      case ISD::SETNE:
3548      case ISD::SETUNE:
3549        FnName1 = (VT == MVT::f32) ? "__nesf2" : "__nedf2";
3550        CC1 = ISD::SETNE;
3551        break;
3552      case ISD::SETGE:
3553      case ISD::SETOGE:
3554        FnName1 = (VT == MVT::f32) ? "__gesf2" : "__gedf2";
3555        CC1 = ISD::SETGE;
3556        break;
3557      case ISD::SETLT:
3558      case ISD::SETOLT:
3559        FnName1 = (VT == MVT::f32) ? "__ltsf2" : "__ltdf2";
3560        CC1 = ISD::SETLT;
3561        break;
3562      case ISD::SETLE:
3563      case ISD::SETOLE:
3564        FnName1 = (VT == MVT::f32) ? "__lesf2" : "__ledf2";
3565        CC1 = ISD::SETLE;
3566        break;
3567      case ISD::SETGT:
3568      case ISD::SETOGT:
3569        FnName1 = (VT == MVT::f32) ? "__gtsf2" : "__gtdf2";
3570        CC1 = ISD::SETGT;
3571        break;
3572      case ISD::SETUO:
3573      case ISD::SETO:
3574        FnName1 = (VT == MVT::f32) ? "__unordsf2" : "__unorddf2";
3575        CC1 = cast<CondCodeSDNode>(CC)->get() == ISD::SETO
3576          ? ISD::SETEQ : ISD::SETNE;
3577        break;
3578      default:
3579        FnName1 = (VT == MVT::f32) ? "__unordsf2" : "__unorddf2";
3580        CC1 = ISD::SETNE;
3581        switch (cast<CondCodeSDNode>(CC)->get()) {
3582        case ISD::SETONE:
3583          // SETONE = SETOLT | SETOGT
3584          FnName1 = (VT == MVT::f32) ? "__ltsf2" : "__ltdf2";
3585          CC1 = ISD::SETLT;
3586          // Fallthrough
3587        case ISD::SETUGT:
3588          FnName2 = (VT == MVT::f32) ? "__gtsf2" : "__gtdf2";
3589          CC2 = ISD::SETGT;
3590          break;
3591        case ISD::SETUGE:
3592          FnName2 = (VT == MVT::f32) ? "__gesf2" : "__gedf2";
3593          CC2 = ISD::SETGE;
3594          break;
3595        case ISD::SETULT:
3596          FnName2 = (VT == MVT::f32) ? "__ltsf2" : "__ltdf2";
3597          CC2 = ISD::SETLT;
3598          break;
3599        case ISD::SETULE:
3600          FnName2 = (VT == MVT::f32) ? "__lesf2" : "__ledf2";
3601          CC2 = ISD::SETLE;
3602          break;
3603          case ISD::SETUEQ:
3604            FnName2 = (VT == MVT::f32) ? "__eqsf2" : "__eqdf2";
3605            CC2 = ISD::SETEQ;
3606            break;
3607        default: assert(0 && "Unsupported FP setcc!");
3608        }
3609      }
3610
3611      SDOperand Dummy;
3612      Tmp1 = ExpandLibCall(FnName1,
3613                       DAG.getNode(ISD::MERGE_VALUES, VT, LHS, RHS).Val, Dummy);
3614      Tmp2 = DAG.getConstant(0, MVT::i32);
3615      CC = DAG.getCondCode(CC1);
3616      if (FnName2) {
3617        Tmp1 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), Tmp1, Tmp2, CC);
3618        LHS = ExpandLibCall(FnName2,
3619                       DAG.getNode(ISD::MERGE_VALUES, VT, LHS, RHS).Val, Dummy);
3620        Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHS, Tmp2,
3621                           DAG.getCondCode(CC2));
3622        Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
3623        Tmp2 = SDOperand();
3624      }
3625      LHS = Tmp1;
3626      RHS = Tmp2;
3627      return;
3628    }
3629
3630    SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
3631    ExpandOp(LHS, LHSLo, LHSHi);
3632    ExpandOp(RHS, RHSLo, RHSHi);
3633    switch (cast<CondCodeSDNode>(CC)->get()) {
3634    case ISD::SETEQ:
3635    case ISD::SETNE:
3636      if (RHSLo == RHSHi)
3637        if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
3638          if (RHSCST->isAllOnesValue()) {
3639            // Comparison to -1.
3640            Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
3641            Tmp2 = RHSLo;
3642            break;
3643          }
3644
3645      Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
3646      Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
3647      Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
3648      Tmp2 = DAG.getConstant(0, Tmp1.getValueType());
3649      break;
3650    default:
3651      // If this is a comparison of the sign bit, just look at the top part.
3652      // X > -1,  x < 0
3653      if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(RHS))
3654        if ((cast<CondCodeSDNode>(CC)->get() == ISD::SETLT &&
3655             CST->getValue() == 0) ||             // X < 0
3656            (cast<CondCodeSDNode>(CC)->get() == ISD::SETGT &&
3657             CST->isAllOnesValue())) {            // X > -1
3658          Tmp1 = LHSHi;
3659          Tmp2 = RHSHi;
3660          break;
3661        }
3662
3663      // FIXME: This generated code sucks.
3664      ISD::CondCode LowCC;
3665      switch (cast<CondCodeSDNode>(CC)->get()) {
3666      default: assert(0 && "Unknown integer setcc!");
3667      case ISD::SETLT:
3668      case ISD::SETULT: LowCC = ISD::SETULT; break;
3669      case ISD::SETGT:
3670      case ISD::SETUGT: LowCC = ISD::SETUGT; break;
3671      case ISD::SETLE:
3672      case ISD::SETULE: LowCC = ISD::SETULE; break;
3673      case ISD::SETGE:
3674      case ISD::SETUGE: LowCC = ISD::SETUGE; break;
3675      }
3676
3677      // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
3678      // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
3679      // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
3680
3681      // NOTE: on targets without efficient SELECT of bools, we can always use
3682      // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
3683      Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC);
3684      Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi, CC);
3685      Result = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ);
3686      Result = LegalizeOp(DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
3687                                      Result, Tmp1, Tmp2));
3688      Tmp1 = Result;
3689      Tmp2 = SDOperand();
3690    }
3691  }
3692  }
3693  LHS = Tmp1;
3694  RHS = Tmp2;
3695}
3696
3697/// ExpandBIT_CONVERT - Expand a BIT_CONVERT node into a store/load combination.
3698/// The resultant code need not be legal.  Note that SrcOp is the input operand
3699/// to the BIT_CONVERT, not the BIT_CONVERT node itself.
3700SDOperand SelectionDAGLegalize::ExpandBIT_CONVERT(MVT::ValueType DestVT,
3701                                                  SDOperand SrcOp) {
3702  // Create the stack frame object.
3703  SDOperand FIPtr = CreateStackTemporary(DestVT);
3704
3705  // Emit a store to the stack slot.
3706  SDOperand Store = DAG.getStore(DAG.getEntryNode(), SrcOp, FIPtr, NULL, 0);
3707  // Result is a load from the stack slot.
3708  return DAG.getLoad(DestVT, Store, FIPtr, NULL, 0);
3709}
3710
3711SDOperand SelectionDAGLegalize::ExpandSCALAR_TO_VECTOR(SDNode *Node) {
3712  // Create a vector sized/aligned stack slot, store the value to element #0,
3713  // then load the whole vector back out.
3714  SDOperand StackPtr = CreateStackTemporary(Node->getValueType(0));
3715  SDOperand Ch = DAG.getStore(DAG.getEntryNode(), Node->getOperand(0), StackPtr,
3716                              NULL, 0);
3717  return DAG.getLoad(Node->getValueType(0), Ch, StackPtr, NULL, 0);
3718}
3719
3720
3721/// ExpandBUILD_VECTOR - Expand a BUILD_VECTOR node on targets that don't
3722/// support the operation, but do support the resultant packed vector type.
3723SDOperand SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
3724
3725  // If the only non-undef value is the low element, turn this into a
3726  // SCALAR_TO_VECTOR node.  If this is { X, X, X, X }, determine X.
3727  unsigned NumElems = Node->getNumOperands();
3728  bool isOnlyLowElement = true;
3729  SDOperand SplatValue = Node->getOperand(0);
3730  std::map<SDOperand, std::vector<unsigned> > Values;
3731  Values[SplatValue].push_back(0);
3732  bool isConstant = true;
3733  if (!isa<ConstantFPSDNode>(SplatValue) && !isa<ConstantSDNode>(SplatValue) &&
3734      SplatValue.getOpcode() != ISD::UNDEF)
3735    isConstant = false;
3736
3737  for (unsigned i = 1; i < NumElems; ++i) {
3738    SDOperand V = Node->getOperand(i);
3739    Values[V].push_back(i);
3740    if (V.getOpcode() != ISD::UNDEF)
3741      isOnlyLowElement = false;
3742    if (SplatValue != V)
3743      SplatValue = SDOperand(0,0);
3744
3745    // If this isn't a constant element or an undef, we can't use a constant
3746    // pool load.
3747    if (!isa<ConstantFPSDNode>(V) && !isa<ConstantSDNode>(V) &&
3748        V.getOpcode() != ISD::UNDEF)
3749      isConstant = false;
3750  }
3751
3752  if (isOnlyLowElement) {
3753    // If the low element is an undef too, then this whole things is an undef.
3754    if (Node->getOperand(0).getOpcode() == ISD::UNDEF)
3755      return DAG.getNode(ISD::UNDEF, Node->getValueType(0));
3756    // Otherwise, turn this into a scalar_to_vector node.
3757    return DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0),
3758                       Node->getOperand(0));
3759  }
3760
3761  // If all elements are constants, create a load from the constant pool.
3762  if (isConstant) {
3763    MVT::ValueType VT = Node->getValueType(0);
3764    const Type *OpNTy =
3765      MVT::getTypeForValueType(Node->getOperand(0).getValueType());
3766    std::vector<Constant*> CV;
3767    for (unsigned i = 0, e = NumElems; i != e; ++i) {
3768      if (ConstantFPSDNode *V =
3769          dyn_cast<ConstantFPSDNode>(Node->getOperand(i))) {
3770        CV.push_back(ConstantFP::get(OpNTy, V->getValue()));
3771      } else if (ConstantSDNode *V =
3772                 dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
3773        CV.push_back(ConstantInt::get(OpNTy, V->getValue()));
3774      } else {
3775        assert(Node->getOperand(i).getOpcode() == ISD::UNDEF);
3776        CV.push_back(UndefValue::get(OpNTy));
3777      }
3778    }
3779    Constant *CP = ConstantPacked::get(CV);
3780    SDOperand CPIdx = DAG.getConstantPool(CP, TLI.getPointerTy());
3781    return DAG.getLoad(VT, DAG.getEntryNode(), CPIdx, NULL, 0);
3782  }
3783
3784  if (SplatValue.Val) {   // Splat of one value?
3785    // Build the shuffle constant vector: <0, 0, 0, 0>
3786    MVT::ValueType MaskVT =
3787      MVT::getIntVectorWithNumElements(NumElems);
3788    SDOperand Zero = DAG.getConstant(0, MVT::getVectorBaseType(MaskVT));
3789    std::vector<SDOperand> ZeroVec(NumElems, Zero);
3790    SDOperand SplatMask = DAG.getNode(ISD::BUILD_VECTOR, MaskVT,
3791                                      &ZeroVec[0], ZeroVec.size());
3792
3793    // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
3794    if (isShuffleLegal(Node->getValueType(0), SplatMask)) {
3795      // Get the splatted value into the low element of a vector register.
3796      SDOperand LowValVec =
3797        DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0), SplatValue);
3798
3799      // Return shuffle(LowValVec, undef, <0,0,0,0>)
3800      return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0), LowValVec,
3801                         DAG.getNode(ISD::UNDEF, Node->getValueType(0)),
3802                         SplatMask);
3803    }
3804  }
3805
3806  // If there are only two unique elements, we may be able to turn this into a
3807  // vector shuffle.
3808  if (Values.size() == 2) {
3809    // Build the shuffle constant vector: e.g. <0, 4, 0, 4>
3810    MVT::ValueType MaskVT =
3811      MVT::getIntVectorWithNumElements(NumElems);
3812    std::vector<SDOperand> MaskVec(NumElems);
3813    unsigned i = 0;
3814    for (std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
3815           E = Values.end(); I != E; ++I) {
3816      for (std::vector<unsigned>::iterator II = I->second.begin(),
3817             EE = I->second.end(); II != EE; ++II)
3818        MaskVec[*II] = DAG.getConstant(i, MVT::getVectorBaseType(MaskVT));
3819      i += NumElems;
3820    }
3821    SDOperand ShuffleMask = DAG.getNode(ISD::BUILD_VECTOR, MaskVT,
3822                                        &MaskVec[0], MaskVec.size());
3823
3824    // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
3825    if (TLI.isOperationLegal(ISD::SCALAR_TO_VECTOR, Node->getValueType(0)) &&
3826        isShuffleLegal(Node->getValueType(0), ShuffleMask)) {
3827      SmallVector<SDOperand, 8> Ops;
3828      for(std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
3829            E = Values.end(); I != E; ++I) {
3830        SDOperand Op = DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0),
3831                                   I->first);
3832        Ops.push_back(Op);
3833      }
3834      Ops.push_back(ShuffleMask);
3835
3836      // Return shuffle(LoValVec, HiValVec, <0,1,0,1>)
3837      return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0),
3838                         &Ops[0], Ops.size());
3839    }
3840  }
3841
3842  // Otherwise, we can't handle this case efficiently.  Allocate a sufficiently
3843  // aligned object on the stack, store each element into it, then load
3844  // the result as a vector.
3845  MVT::ValueType VT = Node->getValueType(0);
3846  // Create the stack frame object.
3847  SDOperand FIPtr = CreateStackTemporary(VT);
3848
3849  // Emit a store of each element to the stack slot.
3850  SmallVector<SDOperand, 8> Stores;
3851  unsigned TypeByteSize =
3852    MVT::getSizeInBits(Node->getOperand(0).getValueType())/8;
3853  // Store (in the right endianness) the elements to memory.
3854  for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
3855    // Ignore undef elements.
3856    if (Node->getOperand(i).getOpcode() == ISD::UNDEF) continue;
3857
3858    unsigned Offset = TypeByteSize*i;
3859
3860    SDOperand Idx = DAG.getConstant(Offset, FIPtr.getValueType());
3861    Idx = DAG.getNode(ISD::ADD, FIPtr.getValueType(), FIPtr, Idx);
3862
3863    Stores.push_back(DAG.getStore(DAG.getEntryNode(), Node->getOperand(i), Idx,
3864                                  NULL, 0));
3865  }
3866
3867  SDOperand StoreChain;
3868  if (!Stores.empty())    // Not all undef elements?
3869    StoreChain = DAG.getNode(ISD::TokenFactor, MVT::Other,
3870                             &Stores[0], Stores.size());
3871  else
3872    StoreChain = DAG.getEntryNode();
3873
3874  // Result is a load from the stack slot.
3875  return DAG.getLoad(VT, StoreChain, FIPtr, NULL, 0);
3876}
3877
3878/// CreateStackTemporary - Create a stack temporary, suitable for holding the
3879/// specified value type.
3880SDOperand SelectionDAGLegalize::CreateStackTemporary(MVT::ValueType VT) {
3881  MachineFrameInfo *FrameInfo = DAG.getMachineFunction().getFrameInfo();
3882  unsigned ByteSize = MVT::getSizeInBits(VT)/8;
3883  int FrameIdx = FrameInfo->CreateStackObject(ByteSize, ByteSize);
3884  return DAG.getFrameIndex(FrameIdx, TLI.getPointerTy());
3885}
3886
3887void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
3888                                            SDOperand Op, SDOperand Amt,
3889                                            SDOperand &Lo, SDOperand &Hi) {
3890  // Expand the subcomponents.
3891  SDOperand LHSL, LHSH;
3892  ExpandOp(Op, LHSL, LHSH);
3893
3894  SDOperand Ops[] = { LHSL, LHSH, Amt };
3895  MVT::ValueType VT = LHSL.getValueType();
3896  Lo = DAG.getNode(NodeOp, DAG.getNodeValueTypes(VT, VT), 2, Ops, 3);
3897  Hi = Lo.getValue(1);
3898}
3899
3900
3901/// ExpandShift - Try to find a clever way to expand this shift operation out to
3902/// smaller elements.  If we can't find a way that is more efficient than a
3903/// libcall on this target, return false.  Otherwise, return true with the
3904/// low-parts expanded into Lo and Hi.
3905bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
3906                                       SDOperand &Lo, SDOperand &Hi) {
3907  assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
3908         "This is not a shift!");
3909
3910  MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
3911  SDOperand ShAmt = LegalizeOp(Amt);
3912  MVT::ValueType ShTy = ShAmt.getValueType();
3913  unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
3914  unsigned NVTBits = MVT::getSizeInBits(NVT);
3915
3916  // Handle the case when Amt is an immediate.  Other cases are currently broken
3917  // and are disabled.
3918  if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
3919    unsigned Cst = CN->getValue();
3920    // Expand the incoming operand to be shifted, so that we have its parts
3921    SDOperand InL, InH;
3922    ExpandOp(Op, InL, InH);
3923    switch(Opc) {
3924    case ISD::SHL:
3925      if (Cst > VTBits) {
3926        Lo = DAG.getConstant(0, NVT);
3927        Hi = DAG.getConstant(0, NVT);
3928      } else if (Cst > NVTBits) {
3929        Lo = DAG.getConstant(0, NVT);
3930        Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
3931      } else if (Cst == NVTBits) {
3932        Lo = DAG.getConstant(0, NVT);
3933        Hi = InL;
3934      } else {
3935        Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
3936        Hi = DAG.getNode(ISD::OR, NVT,
3937           DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
3938           DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
3939      }
3940      return true;
3941    case ISD::SRL:
3942      if (Cst > VTBits) {
3943        Lo = DAG.getConstant(0, NVT);
3944        Hi = DAG.getConstant(0, NVT);
3945      } else if (Cst > NVTBits) {
3946        Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
3947        Hi = DAG.getConstant(0, NVT);
3948      } else if (Cst == NVTBits) {
3949        Lo = InH;
3950        Hi = DAG.getConstant(0, NVT);
3951      } else {
3952        Lo = DAG.getNode(ISD::OR, NVT,
3953           DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
3954           DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
3955        Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
3956      }
3957      return true;
3958    case ISD::SRA:
3959      if (Cst > VTBits) {
3960        Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
3961                              DAG.getConstant(NVTBits-1, ShTy));
3962      } else if (Cst > NVTBits) {
3963        Lo = DAG.getNode(ISD::SRA, NVT, InH,
3964                           DAG.getConstant(Cst-NVTBits, ShTy));
3965        Hi = DAG.getNode(ISD::SRA, NVT, InH,
3966                              DAG.getConstant(NVTBits-1, ShTy));
3967      } else if (Cst == NVTBits) {
3968        Lo = InH;
3969        Hi = DAG.getNode(ISD::SRA, NVT, InH,
3970                              DAG.getConstant(NVTBits-1, ShTy));
3971      } else {
3972        Lo = DAG.getNode(ISD::OR, NVT,
3973           DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
3974           DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
3975        Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
3976      }
3977      return true;
3978    }
3979  }
3980
3981  // Okay, the shift amount isn't constant.  However, if we can tell that it is
3982  // >= 32 or < 32, we can still simplify it, without knowing the actual value.
3983  uint64_t Mask = NVTBits, KnownZero, KnownOne;
3984  TLI.ComputeMaskedBits(Amt, Mask, KnownZero, KnownOne);
3985
3986  // If we know that the high bit of the shift amount is one, then we can do
3987  // this as a couple of simple shifts.
3988  if (KnownOne & Mask) {
3989    // Mask out the high bit, which we know is set.
3990    Amt = DAG.getNode(ISD::AND, Amt.getValueType(), Amt,
3991                      DAG.getConstant(NVTBits-1, Amt.getValueType()));
3992
3993    // Expand the incoming operand to be shifted, so that we have its parts
3994    SDOperand InL, InH;
3995    ExpandOp(Op, InL, InH);
3996    switch(Opc) {
3997    case ISD::SHL:
3998      Lo = DAG.getConstant(0, NVT);              // Low part is zero.
3999      Hi = DAG.getNode(ISD::SHL, NVT, InL, Amt); // High part from Lo part.
4000      return true;
4001    case ISD::SRL:
4002      Hi = DAG.getConstant(0, NVT);              // Hi part is zero.
4003      Lo = DAG.getNode(ISD::SRL, NVT, InH, Amt); // Lo part from Hi part.
4004      return true;
4005    case ISD::SRA:
4006      Hi = DAG.getNode(ISD::SRA, NVT, InH,       // Sign extend high part.
4007                       DAG.getConstant(NVTBits-1, Amt.getValueType()));
4008      Lo = DAG.getNode(ISD::SRA, NVT, InH, Amt); // Lo part from Hi part.
4009      return true;
4010    }
4011  }
4012
4013  // If we know that the high bit of the shift amount is zero, then we can do
4014  // this as a couple of simple shifts.
4015  if (KnownZero & Mask) {
4016    // Compute 32-amt.
4017    SDOperand Amt2 = DAG.getNode(ISD::SUB, Amt.getValueType(),
4018                                 DAG.getConstant(NVTBits, Amt.getValueType()),
4019                                 Amt);
4020
4021    // Expand the incoming operand to be shifted, so that we have its parts
4022    SDOperand InL, InH;
4023    ExpandOp(Op, InL, InH);
4024    switch(Opc) {
4025    case ISD::SHL:
4026      Lo = DAG.getNode(ISD::SHL, NVT, InL, Amt);
4027      Hi = DAG.getNode(ISD::OR, NVT,
4028                       DAG.getNode(ISD::SHL, NVT, InH, Amt),
4029                       DAG.getNode(ISD::SRL, NVT, InL, Amt2));
4030      return true;
4031    case ISD::SRL:
4032      Hi = DAG.getNode(ISD::SRL, NVT, InH, Amt);
4033      Lo = DAG.getNode(ISD::OR, NVT,
4034                       DAG.getNode(ISD::SRL, NVT, InL, Amt),
4035                       DAG.getNode(ISD::SHL, NVT, InH, Amt2));
4036      return true;
4037    case ISD::SRA:
4038      Hi = DAG.getNode(ISD::SRA, NVT, InH, Amt);
4039      Lo = DAG.getNode(ISD::OR, NVT,
4040                       DAG.getNode(ISD::SRL, NVT, InL, Amt),
4041                       DAG.getNode(ISD::SHL, NVT, InH, Amt2));
4042      return true;
4043    }
4044  }
4045
4046  return false;
4047}
4048
4049
4050// ExpandLibCall - Expand a node into a call to a libcall.  If the result value
4051// does not fit into a register, return the lo part and set the hi part to the
4052// by-reg argument.  If it does fit into a single register, return the result
4053// and leave the Hi part unset.
4054SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
4055                                              SDOperand &Hi) {
4056  assert(!IsLegalizingCall && "Cannot overlap legalization of calls!");
4057  // The input chain to this libcall is the entry node of the function.
4058  // Legalizing the call will automatically add the previous call to the
4059  // dependence.
4060  SDOperand InChain = DAG.getEntryNode();
4061
4062  TargetLowering::ArgListTy Args;
4063  for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
4064    MVT::ValueType ArgVT = Node->getOperand(i).getValueType();
4065    const Type *ArgTy = MVT::getTypeForValueType(ArgVT);
4066    Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
4067  }
4068  SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
4069
4070  // Splice the libcall in wherever FindInputOutputChains tells us to.
4071  const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
4072  std::pair<SDOperand,SDOperand> CallInfo =
4073    TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false,
4074                    Callee, Args, DAG);
4075
4076  // Legalize the call sequence, starting with the chain.  This will advance
4077  // the LastCALLSEQ_END to the legalized version of the CALLSEQ_END node that
4078  // was added by LowerCallTo (guaranteeing proper serialization of calls).
4079  LegalizeOp(CallInfo.second);
4080  SDOperand Result;
4081  switch (getTypeAction(CallInfo.first.getValueType())) {
4082  default: assert(0 && "Unknown thing");
4083  case Legal:
4084    Result = CallInfo.first;
4085    break;
4086  case Expand:
4087    ExpandOp(CallInfo.first, Result, Hi);
4088    break;
4089  }
4090  return Result;
4091}
4092
4093
4094/// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the
4095/// destination type is legal.
4096SDOperand SelectionDAGLegalize::
4097ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
4098  assert(isTypeLegal(DestTy) && "Destination type is not legal!");
4099  assert(getTypeAction(Source.getValueType()) == Expand &&
4100         "This is not an expansion!");
4101  assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
4102
4103  if (!isSigned) {
4104    assert(Source.getValueType() == MVT::i64 &&
4105           "This only works for 64-bit -> FP");
4106    // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
4107    // incoming integer is set.  To handle this, we dynamically test to see if
4108    // it is set, and, if so, add a fudge factor.
4109    SDOperand Lo, Hi;
4110    ExpandOp(Source, Lo, Hi);
4111
4112    // If this is unsigned, and not supported, first perform the conversion to
4113    // signed, then adjust the result if the sign bit is set.
4114    SDOperand SignedConv = ExpandIntToFP(true, DestTy,
4115                   DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi));
4116
4117    SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
4118                                     DAG.getConstant(0, Hi.getValueType()),
4119                                     ISD::SETLT);
4120    SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
4121    SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
4122                                      SignSet, Four, Zero);
4123    uint64_t FF = 0x5f800000ULL;
4124    if (TLI.isLittleEndian()) FF <<= 32;
4125    static Constant *FudgeFactor = ConstantInt::get(Type::ULongTy, FF);
4126
4127    SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
4128    CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
4129    SDOperand FudgeInReg;
4130    if (DestTy == MVT::f32)
4131      FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, NULL, 0);
4132    else {
4133      assert(DestTy == MVT::f64 && "Unexpected conversion");
4134      FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
4135                                  CPIdx, NULL, 0, MVT::f32);
4136    }
4137    return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg);
4138  }
4139
4140  // Check to see if the target has a custom way to lower this.  If so, use it.
4141  switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) {
4142  default: assert(0 && "This action not implemented for this operation!");
4143  case TargetLowering::Legal:
4144  case TargetLowering::Expand:
4145    break;   // This case is handled below.
4146  case TargetLowering::Custom: {
4147    SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy,
4148                                                  Source), DAG);
4149    if (NV.Val)
4150      return LegalizeOp(NV);
4151    break;   // The target decided this was legal after all
4152  }
4153  }
4154
4155  // Expand the source, then glue it back together for the call.  We must expand
4156  // the source in case it is shared (this pass of legalize must traverse it).
4157  SDOperand SrcLo, SrcHi;
4158  ExpandOp(Source, SrcLo, SrcHi);
4159  Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
4160
4161  const char *FnName = 0;
4162  if (DestTy == MVT::f32)
4163    FnName = "__floatdisf";
4164  else {
4165    assert(DestTy == MVT::f64 && "Unknown fp value type!");
4166    FnName = "__floatdidf";
4167  }
4168
4169  Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source);
4170  SDOperand UnusedHiPart;
4171  return ExpandLibCall(FnName, Source.Val, UnusedHiPart);
4172}
4173
4174/// ExpandLegalINT_TO_FP - This function is responsible for legalizing a
4175/// INT_TO_FP operation of the specified operand when the target requests that
4176/// we expand it.  At this point, we know that the result and operand types are
4177/// legal for the target.
4178SDOperand SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
4179                                                     SDOperand Op0,
4180                                                     MVT::ValueType DestVT) {
4181  if (Op0.getValueType() == MVT::i32) {
4182    // simple 32-bit [signed|unsigned] integer to float/double expansion
4183
4184    // get the stack frame index of a 8 byte buffer
4185    MachineFunction &MF = DAG.getMachineFunction();
4186    int SSFI = MF.getFrameInfo()->CreateStackObject(8, 8);
4187    // get address of 8 byte buffer
4188    SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
4189    // word offset constant for Hi/Lo address computation
4190    SDOperand WordOff = DAG.getConstant(sizeof(int), TLI.getPointerTy());
4191    // set up Hi and Lo (into buffer) address based on endian
4192    SDOperand Hi = StackSlot;
4193    SDOperand Lo = DAG.getNode(ISD::ADD, TLI.getPointerTy(), StackSlot,WordOff);
4194    if (TLI.isLittleEndian())
4195      std::swap(Hi, Lo);
4196
4197    // if signed map to unsigned space
4198    SDOperand Op0Mapped;
4199    if (isSigned) {
4200      // constant used to invert sign bit (signed to unsigned mapping)
4201      SDOperand SignBit = DAG.getConstant(0x80000000u, MVT::i32);
4202      Op0Mapped = DAG.getNode(ISD::XOR, MVT::i32, Op0, SignBit);
4203    } else {
4204      Op0Mapped = Op0;
4205    }
4206    // store the lo of the constructed double - based on integer input
4207    SDOperand Store1 = DAG.getStore(DAG.getEntryNode(),
4208                                    Op0Mapped, Lo, NULL, 0);
4209    // initial hi portion of constructed double
4210    SDOperand InitialHi = DAG.getConstant(0x43300000u, MVT::i32);
4211    // store the hi of the constructed double - biased exponent
4212    SDOperand Store2=DAG.getStore(Store1, InitialHi, Hi, NULL, 0);
4213    // load the constructed double
4214    SDOperand Load = DAG.getLoad(MVT::f64, Store2, StackSlot, NULL, 0);
4215    // FP constant to bias correct the final result
4216    SDOperand Bias = DAG.getConstantFP(isSigned ?
4217                                            BitsToDouble(0x4330000080000000ULL)
4218                                          : BitsToDouble(0x4330000000000000ULL),
4219                                     MVT::f64);
4220    // subtract the bias
4221    SDOperand Sub = DAG.getNode(ISD::FSUB, MVT::f64, Load, Bias);
4222    // final result
4223    SDOperand Result;
4224    // handle final rounding
4225    if (DestVT == MVT::f64) {
4226      // do nothing
4227      Result = Sub;
4228    } else {
4229     // if f32 then cast to f32
4230      Result = DAG.getNode(ISD::FP_ROUND, MVT::f32, Sub);
4231    }
4232    return Result;
4233  }
4234  assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
4235  SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0);
4236
4237  SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Op0,
4238                                   DAG.getConstant(0, Op0.getValueType()),
4239                                   ISD::SETLT);
4240  SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
4241  SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
4242                                    SignSet, Four, Zero);
4243
4244  // If the sign bit of the integer is set, the large number will be treated
4245  // as a negative number.  To counteract this, the dynamic code adds an
4246  // offset depending on the data type.
4247  uint64_t FF;
4248  switch (Op0.getValueType()) {
4249  default: assert(0 && "Unsupported integer type!");
4250  case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
4251  case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
4252  case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
4253  case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
4254  }
4255  if (TLI.isLittleEndian()) FF <<= 32;
4256  static Constant *FudgeFactor = ConstantInt::get(Type::ULongTy, FF);
4257
4258  SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy());
4259  CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
4260  SDOperand FudgeInReg;
4261  if (DestVT == MVT::f32)
4262    FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, NULL, 0);
4263  else {
4264    assert(DestVT == MVT::f64 && "Unexpected conversion");
4265    FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64,
4266                                           DAG.getEntryNode(), CPIdx,
4267                                           NULL, 0, MVT::f32));
4268  }
4269
4270  return DAG.getNode(ISD::FADD, DestVT, Tmp1, FudgeInReg);
4271}
4272
4273/// PromoteLegalINT_TO_FP - This function is responsible for legalizing a
4274/// *INT_TO_FP operation of the specified operand when the target requests that
4275/// we promote it.  At this point, we know that the result and operand types are
4276/// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
4277/// operation that takes a larger input.
4278SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp,
4279                                                      MVT::ValueType DestVT,
4280                                                      bool isSigned) {
4281  // First step, figure out the appropriate *INT_TO_FP operation to use.
4282  MVT::ValueType NewInTy = LegalOp.getValueType();
4283
4284  unsigned OpToUse = 0;
4285
4286  // Scan for the appropriate larger type to use.
4287  while (1) {
4288    NewInTy = (MVT::ValueType)(NewInTy+1);
4289    assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!");
4290
4291    // If the target supports SINT_TO_FP of this type, use it.
4292    switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) {
4293      default: break;
4294      case TargetLowering::Legal:
4295        if (!TLI.isTypeLegal(NewInTy))
4296          break;  // Can't use this datatype.
4297        // FALL THROUGH.
4298      case TargetLowering::Custom:
4299        OpToUse = ISD::SINT_TO_FP;
4300        break;
4301    }
4302    if (OpToUse) break;
4303    if (isSigned) continue;
4304
4305    // If the target supports UINT_TO_FP of this type, use it.
4306    switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) {
4307      default: break;
4308      case TargetLowering::Legal:
4309        if (!TLI.isTypeLegal(NewInTy))
4310          break;  // Can't use this datatype.
4311        // FALL THROUGH.
4312      case TargetLowering::Custom:
4313        OpToUse = ISD::UINT_TO_FP;
4314        break;
4315    }
4316    if (OpToUse) break;
4317
4318    // Otherwise, try a larger type.
4319  }
4320
4321  // Okay, we found the operation and type to use.  Zero extend our input to the
4322  // desired type then run the operation on it.
4323  return DAG.getNode(OpToUse, DestVT,
4324                     DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
4325                                 NewInTy, LegalOp));
4326}
4327
4328/// PromoteLegalFP_TO_INT - This function is responsible for legalizing a
4329/// FP_TO_*INT operation of the specified operand when the target requests that
4330/// we promote it.  At this point, we know that the result and operand types are
4331/// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
4332/// operation that returns a larger result.
4333SDOperand SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDOperand LegalOp,
4334                                                      MVT::ValueType DestVT,
4335                                                      bool isSigned) {
4336  // First step, figure out the appropriate FP_TO*INT operation to use.
4337  MVT::ValueType NewOutTy = DestVT;
4338
4339  unsigned OpToUse = 0;
4340
4341  // Scan for the appropriate larger type to use.
4342  while (1) {
4343    NewOutTy = (MVT::ValueType)(NewOutTy+1);
4344    assert(MVT::isInteger(NewOutTy) && "Ran out of possibilities!");
4345
4346    // If the target supports FP_TO_SINT returning this type, use it.
4347    switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) {
4348    default: break;
4349    case TargetLowering::Legal:
4350      if (!TLI.isTypeLegal(NewOutTy))
4351        break;  // Can't use this datatype.
4352      // FALL THROUGH.
4353    case TargetLowering::Custom:
4354      OpToUse = ISD::FP_TO_SINT;
4355      break;
4356    }
4357    if (OpToUse) break;
4358
4359    // If the target supports FP_TO_UINT of this type, use it.
4360    switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) {
4361    default: break;
4362    case TargetLowering::Legal:
4363      if (!TLI.isTypeLegal(NewOutTy))
4364        break;  // Can't use this datatype.
4365      // FALL THROUGH.
4366    case TargetLowering::Custom:
4367      OpToUse = ISD::FP_TO_UINT;
4368      break;
4369    }
4370    if (OpToUse) break;
4371
4372    // Otherwise, try a larger type.
4373  }
4374
4375  // Okay, we found the operation and type to use.  Truncate the result of the
4376  // extended FP_TO_*INT operation to the desired size.
4377  return DAG.getNode(ISD::TRUNCATE, DestVT,
4378                     DAG.getNode(OpToUse, NewOutTy, LegalOp));
4379}
4380
4381/// ExpandBSWAP - Open code the operations for BSWAP of the specified operation.
4382///
4383SDOperand SelectionDAGLegalize::ExpandBSWAP(SDOperand Op) {
4384  MVT::ValueType VT = Op.getValueType();
4385  MVT::ValueType SHVT = TLI.getShiftAmountTy();
4386  SDOperand Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8;
4387  switch (VT) {
4388  default: assert(0 && "Unhandled Expand type in BSWAP!"); abort();
4389  case MVT::i16:
4390    Tmp2 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
4391    Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
4392    return DAG.getNode(ISD::OR, VT, Tmp1, Tmp2);
4393  case MVT::i32:
4394    Tmp4 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
4395    Tmp3 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
4396    Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
4397    Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
4398    Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(0xFF0000, VT));
4399    Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(0xFF00, VT));
4400    Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
4401    Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
4402    return DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
4403  case MVT::i64:
4404    Tmp8 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(56, SHVT));
4405    Tmp7 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(40, SHVT));
4406    Tmp6 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(24, SHVT));
4407    Tmp5 = DAG.getNode(ISD::SHL, VT, Op, DAG.getConstant(8, SHVT));
4408    Tmp4 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(8, SHVT));
4409    Tmp3 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(24, SHVT));
4410    Tmp2 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(40, SHVT));
4411    Tmp1 = DAG.getNode(ISD::SRL, VT, Op, DAG.getConstant(56, SHVT));
4412    Tmp7 = DAG.getNode(ISD::AND, VT, Tmp7, DAG.getConstant(255ULL<<48, VT));
4413    Tmp6 = DAG.getNode(ISD::AND, VT, Tmp6, DAG.getConstant(255ULL<<40, VT));
4414    Tmp5 = DAG.getNode(ISD::AND, VT, Tmp5, DAG.getConstant(255ULL<<32, VT));
4415    Tmp4 = DAG.getNode(ISD::AND, VT, Tmp4, DAG.getConstant(255ULL<<24, VT));
4416    Tmp3 = DAG.getNode(ISD::AND, VT, Tmp3, DAG.getConstant(255ULL<<16, VT));
4417    Tmp2 = DAG.getNode(ISD::AND, VT, Tmp2, DAG.getConstant(255ULL<<8 , VT));
4418    Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp7);
4419    Tmp6 = DAG.getNode(ISD::OR, VT, Tmp6, Tmp5);
4420    Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp3);
4421    Tmp2 = DAG.getNode(ISD::OR, VT, Tmp2, Tmp1);
4422    Tmp8 = DAG.getNode(ISD::OR, VT, Tmp8, Tmp6);
4423    Tmp4 = DAG.getNode(ISD::OR, VT, Tmp4, Tmp2);
4424    return DAG.getNode(ISD::OR, VT, Tmp8, Tmp4);
4425  }
4426}
4427
4428/// ExpandBitCount - Expand the specified bitcount instruction into operations.
4429///
4430SDOperand SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDOperand Op) {
4431  switch (Opc) {
4432  default: assert(0 && "Cannot expand this yet!");
4433  case ISD::CTPOP: {
4434    static const uint64_t mask[6] = {
4435      0x5555555555555555ULL, 0x3333333333333333ULL,
4436      0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
4437      0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
4438    };
4439    MVT::ValueType VT = Op.getValueType();
4440    MVT::ValueType ShVT = TLI.getShiftAmountTy();
4441    unsigned len = getSizeInBits(VT);
4442    for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
4443      //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
4444      SDOperand Tmp2 = DAG.getConstant(mask[i], VT);
4445      SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
4446      Op = DAG.getNode(ISD::ADD, VT, DAG.getNode(ISD::AND, VT, Op, Tmp2),
4447                       DAG.getNode(ISD::AND, VT,
4448                                   DAG.getNode(ISD::SRL, VT, Op, Tmp3),Tmp2));
4449    }
4450    return Op;
4451  }
4452  case ISD::CTLZ: {
4453    // for now, we do this:
4454    // x = x | (x >> 1);
4455    // x = x | (x >> 2);
4456    // ...
4457    // x = x | (x >>16);
4458    // x = x | (x >>32); // for 64-bit input
4459    // return popcount(~x);
4460    //
4461    // but see also: http://www.hackersdelight.org/HDcode/nlz.cc
4462    MVT::ValueType VT = Op.getValueType();
4463    MVT::ValueType ShVT = TLI.getShiftAmountTy();
4464    unsigned len = getSizeInBits(VT);
4465    for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
4466      SDOperand Tmp3 = DAG.getConstant(1ULL << i, ShVT);
4467      Op = DAG.getNode(ISD::OR, VT, Op, DAG.getNode(ISD::SRL, VT, Op, Tmp3));
4468    }
4469    Op = DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(~0ULL, VT));
4470    return DAG.getNode(ISD::CTPOP, VT, Op);
4471  }
4472  case ISD::CTTZ: {
4473    // for now, we use: { return popcount(~x & (x - 1)); }
4474    // unless the target has ctlz but not ctpop, in which case we use:
4475    // { return 32 - nlz(~x & (x-1)); }
4476    // see also http://www.hackersdelight.org/HDcode/ntz.cc
4477    MVT::ValueType VT = Op.getValueType();
4478    SDOperand Tmp2 = DAG.getConstant(~0ULL, VT);
4479    SDOperand Tmp3 = DAG.getNode(ISD::AND, VT,
4480                       DAG.getNode(ISD::XOR, VT, Op, Tmp2),
4481                       DAG.getNode(ISD::SUB, VT, Op, DAG.getConstant(1, VT)));
4482    // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
4483    if (!TLI.isOperationLegal(ISD::CTPOP, VT) &&
4484        TLI.isOperationLegal(ISD::CTLZ, VT))
4485      return DAG.getNode(ISD::SUB, VT,
4486                         DAG.getConstant(getSizeInBits(VT), VT),
4487                         DAG.getNode(ISD::CTLZ, VT, Tmp3));
4488    return DAG.getNode(ISD::CTPOP, VT, Tmp3);
4489  }
4490  }
4491}
4492
4493/// ExpandOp - Expand the specified SDOperand into its two component pieces
4494/// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
4495/// LegalizeNodes map is filled in for any results that are not expanded, the
4496/// ExpandedNodes map is filled in for any results that are expanded, and the
4497/// Lo/Hi values are returned.
4498void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
4499  MVT::ValueType VT = Op.getValueType();
4500  MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
4501  SDNode *Node = Op.Val;
4502  assert(getTypeAction(VT) == Expand && "Not an expanded type!");
4503  assert(((MVT::isInteger(NVT) && NVT < VT) || MVT::isFloatingPoint(VT) ||
4504         VT == MVT::Vector) &&
4505         "Cannot expand to FP value or to larger int value!");
4506
4507  // See if we already expanded it.
4508  std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
4509    = ExpandedNodes.find(Op);
4510  if (I != ExpandedNodes.end()) {
4511    Lo = I->second.first;
4512    Hi = I->second.second;
4513    return;
4514  }
4515
4516  switch (Node->getOpcode()) {
4517  case ISD::CopyFromReg:
4518    assert(0 && "CopyFromReg must be legal!");
4519  default:
4520#ifndef NDEBUG
4521    cerr << "NODE: "; Node->dump(); cerr << "\n";
4522#endif
4523    assert(0 && "Do not know how to expand this operator!");
4524    abort();
4525  case ISD::UNDEF:
4526    NVT = TLI.getTypeToExpandTo(VT);
4527    Lo = DAG.getNode(ISD::UNDEF, NVT);
4528    Hi = DAG.getNode(ISD::UNDEF, NVT);
4529    break;
4530  case ISD::Constant: {
4531    uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
4532    Lo = DAG.getConstant(Cst, NVT);
4533    Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
4534    break;
4535  }
4536  case ISD::ConstantFP: {
4537    ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
4538    Lo = ExpandConstantFP(CFP, false, DAG, TLI);
4539    if (getTypeAction(Lo.getValueType()) == Expand)
4540      ExpandOp(Lo, Lo, Hi);
4541    break;
4542  }
4543  case ISD::BUILD_PAIR:
4544    // Return the operands.
4545    Lo = Node->getOperand(0);
4546    Hi = Node->getOperand(1);
4547    break;
4548
4549  case ISD::SIGN_EXTEND_INREG:
4550    ExpandOp(Node->getOperand(0), Lo, Hi);
4551    // sext_inreg the low part if needed.
4552    Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Lo, Node->getOperand(1));
4553
4554    // The high part gets the sign extension from the lo-part.  This handles
4555    // things like sextinreg V:i64 from i8.
4556    Hi = DAG.getNode(ISD::SRA, NVT, Lo,
4557                     DAG.getConstant(MVT::getSizeInBits(NVT)-1,
4558                                     TLI.getShiftAmountTy()));
4559    break;
4560
4561  case ISD::BSWAP: {
4562    ExpandOp(Node->getOperand(0), Lo, Hi);
4563    SDOperand TempLo = DAG.getNode(ISD::BSWAP, NVT, Hi);
4564    Hi = DAG.getNode(ISD::BSWAP, NVT, Lo);
4565    Lo = TempLo;
4566    break;
4567  }
4568
4569  case ISD::CTPOP:
4570    ExpandOp(Node->getOperand(0), Lo, Hi);
4571    Lo = DAG.getNode(ISD::ADD, NVT,          // ctpop(HL) -> ctpop(H)+ctpop(L)
4572                     DAG.getNode(ISD::CTPOP, NVT, Lo),
4573                     DAG.getNode(ISD::CTPOP, NVT, Hi));
4574    Hi = DAG.getConstant(0, NVT);
4575    break;
4576
4577  case ISD::CTLZ: {
4578    // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
4579    ExpandOp(Node->getOperand(0), Lo, Hi);
4580    SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
4581    SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
4582    SDOperand TopNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), HLZ, BitsC,
4583                                        ISD::SETNE);
4584    SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
4585    LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
4586
4587    Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
4588    Hi = DAG.getConstant(0, NVT);
4589    break;
4590  }
4591
4592  case ISD::CTTZ: {
4593    // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
4594    ExpandOp(Node->getOperand(0), Lo, Hi);
4595    SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
4596    SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
4597    SDOperand BotNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), LTZ, BitsC,
4598                                        ISD::SETNE);
4599    SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
4600    HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
4601
4602    Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
4603    Hi = DAG.getConstant(0, NVT);
4604    break;
4605  }
4606
4607  case ISD::VAARG: {
4608    SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
4609    SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
4610    Lo = DAG.getVAArg(NVT, Ch, Ptr, Node->getOperand(2));
4611    Hi = DAG.getVAArg(NVT, Lo.getValue(1), Ptr, Node->getOperand(2));
4612
4613    // Remember that we legalized the chain.
4614    Hi = LegalizeOp(Hi);
4615    AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
4616    if (!TLI.isLittleEndian())
4617      std::swap(Lo, Hi);
4618    break;
4619  }
4620
4621  case ISD::LOAD: {
4622    LoadSDNode *LD = cast<LoadSDNode>(Node);
4623    SDOperand Ch  = LD->getChain();    // Legalize the chain.
4624    SDOperand Ptr = LD->getBasePtr();  // Legalize the pointer.
4625    ISD::LoadExtType ExtType = LD->getExtensionType();
4626
4627    if (ExtType == ISD::NON_EXTLOAD) {
4628      Lo = DAG.getLoad(NVT, Ch, Ptr, LD->getSrcValue(), LD->getSrcValueOffset());
4629      if (VT == MVT::f32 || VT == MVT::f64) {
4630        // f32->i32 or f64->i64 one to one expansion.
4631        // Remember that we legalized the chain.
4632        AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4633        // Recursively expand the new load.
4634        if (getTypeAction(NVT) == Expand)
4635          ExpandOp(Lo, Lo, Hi);
4636        break;
4637      }
4638
4639      // Increment the pointer to the other half.
4640      unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
4641      Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
4642                        getIntPtrConstant(IncrementSize));
4643      // FIXME: This creates a bogus srcvalue!
4644      Hi = DAG.getLoad(NVT, Ch, Ptr, LD->getSrcValue(), LD->getSrcValueOffset());
4645
4646      // Build a factor node to remember that this load is independent of the
4647      // other one.
4648      SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
4649                                 Hi.getValue(1));
4650
4651      // Remember that we legalized the chain.
4652      AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
4653      if (!TLI.isLittleEndian())
4654        std::swap(Lo, Hi);
4655    } else {
4656      MVT::ValueType EVT = LD->getLoadedVT();
4657
4658      if (VT == MVT::f64 && EVT == MVT::f32) {
4659        // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND
4660        SDOperand Load = DAG.getLoad(EVT, Ch, Ptr, LD->getSrcValue(),
4661                                     LD->getSrcValueOffset());
4662        // Remember that we legalized the chain.
4663        AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Load.getValue(1)));
4664        ExpandOp(DAG.getNode(ISD::FP_EXTEND, VT, Load), Lo, Hi);
4665        break;
4666      }
4667
4668      if (EVT == NVT)
4669        Lo = DAG.getLoad(NVT, Ch, Ptr, LD->getSrcValue(),
4670                         LD->getSrcValueOffset());
4671      else
4672        Lo = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, LD->getSrcValue(),
4673                            LD->getSrcValueOffset(), EVT);
4674
4675      // Remember that we legalized the chain.
4676      AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1)));
4677
4678      if (ExtType == ISD::SEXTLOAD) {
4679        // The high part is obtained by SRA'ing all but one of the bits of the
4680        // lo part.
4681        unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
4682        Hi = DAG.getNode(ISD::SRA, NVT, Lo,
4683                         DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
4684      } else if (ExtType == ISD::ZEXTLOAD) {
4685        // The high part is just a zero.
4686        Hi = DAG.getConstant(0, NVT);
4687      } else /* if (ExtType == ISD::EXTLOAD) */ {
4688        // The high part is undefined.
4689        Hi = DAG.getNode(ISD::UNDEF, NVT);
4690      }
4691    }
4692    break;
4693  }
4694  case ISD::AND:
4695  case ISD::OR:
4696  case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
4697    SDOperand LL, LH, RL, RH;
4698    ExpandOp(Node->getOperand(0), LL, LH);
4699    ExpandOp(Node->getOperand(1), RL, RH);
4700    Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
4701    Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
4702    break;
4703  }
4704  case ISD::SELECT: {
4705    SDOperand LL, LH, RL, RH;
4706    ExpandOp(Node->getOperand(1), LL, LH);
4707    ExpandOp(Node->getOperand(2), RL, RH);
4708    if (getTypeAction(NVT) == Expand)
4709      NVT = TLI.getTypeToExpandTo(NVT);
4710    Lo = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LL, RL);
4711    if (VT != MVT::f32)
4712      Hi = DAG.getNode(ISD::SELECT, NVT, Node->getOperand(0), LH, RH);
4713    break;
4714  }
4715  case ISD::SELECT_CC: {
4716    SDOperand TL, TH, FL, FH;
4717    ExpandOp(Node->getOperand(2), TL, TH);
4718    ExpandOp(Node->getOperand(3), FL, FH);
4719    if (getTypeAction(NVT) == Expand)
4720      NVT = TLI.getTypeToExpandTo(NVT);
4721    Lo = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
4722                     Node->getOperand(1), TL, FL, Node->getOperand(4));
4723    if (VT != MVT::f32)
4724      Hi = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0),
4725                       Node->getOperand(1), TH, FH, Node->getOperand(4));
4726    break;
4727  }
4728  case ISD::ANY_EXTEND:
4729    // The low part is any extension of the input (which degenerates to a copy).
4730    Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Node->getOperand(0));
4731    // The high part is undefined.
4732    Hi = DAG.getNode(ISD::UNDEF, NVT);
4733    break;
4734  case ISD::SIGN_EXTEND: {
4735    // The low part is just a sign extension of the input (which degenerates to
4736    // a copy).
4737    Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, Node->getOperand(0));
4738
4739    // The high part is obtained by SRA'ing all but one of the bits of the lo
4740    // part.
4741    unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
4742    Hi = DAG.getNode(ISD::SRA, NVT, Lo,
4743                     DAG.getConstant(LoSize-1, TLI.getShiftAmountTy()));
4744    break;
4745  }
4746  case ISD::ZERO_EXTEND:
4747    // The low part is just a zero extension of the input (which degenerates to
4748    // a copy).
4749    Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, Node->getOperand(0));
4750
4751    // The high part is just a zero.
4752    Hi = DAG.getConstant(0, NVT);
4753    break;
4754
4755  case ISD::BIT_CONVERT: {
4756    SDOperand Tmp;
4757    if (TLI.getOperationAction(ISD::BIT_CONVERT, VT) == TargetLowering::Custom){
4758      // If the target wants to, allow it to lower this itself.
4759      switch (getTypeAction(Node->getOperand(0).getValueType())) {
4760      case Expand: assert(0 && "cannot expand FP!");
4761      case Legal:   Tmp = LegalizeOp(Node->getOperand(0)); break;
4762      case Promote: Tmp = PromoteOp (Node->getOperand(0)); break;
4763      }
4764      Tmp = TLI.LowerOperation(DAG.getNode(ISD::BIT_CONVERT, VT, Tmp), DAG);
4765    }
4766
4767    // f32 / f64 must be expanded to i32 / i64.
4768    if (VT == MVT::f32 || VT == MVT::f64) {
4769      Lo = DAG.getNode(ISD::BIT_CONVERT, NVT, Node->getOperand(0));
4770      if (getTypeAction(NVT) == Expand)
4771        ExpandOp(Lo, Lo, Hi);
4772      break;
4773    }
4774
4775    // If source operand will be expanded to the same type as VT, i.e.
4776    // i64 <- f64, i32 <- f32, expand the source operand instead.
4777    MVT::ValueType VT0 = Node->getOperand(0).getValueType();
4778    if (getTypeAction(VT0) == Expand && TLI.getTypeToTransformTo(VT0) == VT) {
4779      ExpandOp(Node->getOperand(0), Lo, Hi);
4780      break;
4781    }
4782
4783    // Turn this into a load/store pair by default.
4784    if (Tmp.Val == 0)
4785      Tmp = ExpandBIT_CONVERT(VT, Node->getOperand(0));
4786
4787    ExpandOp(Tmp, Lo, Hi);
4788    break;
4789  }
4790
4791  case ISD::READCYCLECOUNTER:
4792    assert(TLI.getOperationAction(ISD::READCYCLECOUNTER, VT) ==
4793                 TargetLowering::Custom &&
4794           "Must custom expand ReadCycleCounter");
4795    Lo = TLI.LowerOperation(Op, DAG);
4796    assert(Lo.Val && "Node must be custom expanded!");
4797    Hi = Lo.getValue(1);
4798    AddLegalizedOperand(SDOperand(Node, 1), // Remember we legalized the chain.
4799                        LegalizeOp(Lo.getValue(2)));
4800    break;
4801
4802    // These operators cannot be expanded directly, emit them as calls to
4803    // library functions.
4804  case ISD::FP_TO_SINT:
4805    if (TLI.getOperationAction(ISD::FP_TO_SINT, VT) == TargetLowering::Custom) {
4806      SDOperand Op;
4807      switch (getTypeAction(Node->getOperand(0).getValueType())) {
4808      case Expand: assert(0 && "cannot expand FP!");
4809      case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
4810      case Promote: Op = PromoteOp (Node->getOperand(0)); break;
4811      }
4812
4813      Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_SINT, VT, Op), DAG);
4814
4815      // Now that the custom expander is done, expand the result, which is still
4816      // VT.
4817      if (Op.Val) {
4818        ExpandOp(Op, Lo, Hi);
4819        break;
4820      }
4821    }
4822
4823    if (Node->getOperand(0).getValueType() == MVT::f32)
4824      Lo = ExpandLibCall("__fixsfdi", Node, Hi);
4825    else
4826      Lo = ExpandLibCall("__fixdfdi", Node, Hi);
4827    break;
4828
4829  case ISD::FP_TO_UINT:
4830    if (TLI.getOperationAction(ISD::FP_TO_UINT, VT) == TargetLowering::Custom) {
4831      SDOperand Op;
4832      switch (getTypeAction(Node->getOperand(0).getValueType())) {
4833        case Expand: assert(0 && "cannot expand FP!");
4834        case Legal:   Op = LegalizeOp(Node->getOperand(0)); break;
4835        case Promote: Op = PromoteOp (Node->getOperand(0)); break;
4836      }
4837
4838      Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_UINT, VT, Op), DAG);
4839
4840      // Now that the custom expander is done, expand the result.
4841      if (Op.Val) {
4842        ExpandOp(Op, Lo, Hi);
4843        break;
4844      }
4845    }
4846
4847    if (Node->getOperand(0).getValueType() == MVT::f32)
4848      Lo = ExpandLibCall("__fixunssfdi", Node, Hi);
4849    else
4850      Lo = ExpandLibCall("__fixunsdfdi", Node, Hi);
4851    break;
4852
4853  case ISD::SHL: {
4854    // If the target wants custom lowering, do so.
4855    SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4856    if (TLI.getOperationAction(ISD::SHL, VT) == TargetLowering::Custom) {
4857      SDOperand Op = DAG.getNode(ISD::SHL, VT, Node->getOperand(0), ShiftAmt);
4858      Op = TLI.LowerOperation(Op, DAG);
4859      if (Op.Val) {
4860        // Now that the custom expander is done, expand the result, which is
4861        // still VT.
4862        ExpandOp(Op, Lo, Hi);
4863        break;
4864      }
4865    }
4866
4867    // If ADDC/ADDE are supported and if the shift amount is a constant 1, emit
4868    // this X << 1 as X+X.
4869    if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(ShiftAmt)) {
4870      if (ShAmt->getValue() == 1 && TLI.isOperationLegal(ISD::ADDC, NVT) &&
4871          TLI.isOperationLegal(ISD::ADDE, NVT)) {
4872        SDOperand LoOps[2], HiOps[3];
4873        ExpandOp(Node->getOperand(0), LoOps[0], HiOps[0]);
4874        SDVTList VTList = DAG.getVTList(LoOps[0].getValueType(), MVT::Flag);
4875        LoOps[1] = LoOps[0];
4876        Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
4877
4878        HiOps[1] = HiOps[0];
4879        HiOps[2] = Lo.getValue(1);
4880        Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
4881        break;
4882      }
4883    }
4884
4885    // If we can emit an efficient shift operation, do so now.
4886    if (ExpandShift(ISD::SHL, Node->getOperand(0), ShiftAmt, Lo, Hi))
4887      break;
4888
4889    // If this target supports SHL_PARTS, use it.
4890    TargetLowering::LegalizeAction Action =
4891      TLI.getOperationAction(ISD::SHL_PARTS, NVT);
4892    if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4893        Action == TargetLowering::Custom) {
4894      ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4895      break;
4896    }
4897
4898    // Otherwise, emit a libcall.
4899    Lo = ExpandLibCall("__ashldi3", Node, Hi);
4900    break;
4901  }
4902
4903  case ISD::SRA: {
4904    // If the target wants custom lowering, do so.
4905    SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4906    if (TLI.getOperationAction(ISD::SRA, VT) == TargetLowering::Custom) {
4907      SDOperand Op = DAG.getNode(ISD::SRA, VT, Node->getOperand(0), ShiftAmt);
4908      Op = TLI.LowerOperation(Op, DAG);
4909      if (Op.Val) {
4910        // Now that the custom expander is done, expand the result, which is
4911        // still VT.
4912        ExpandOp(Op, Lo, Hi);
4913        break;
4914      }
4915    }
4916
4917    // If we can emit an efficient shift operation, do so now.
4918    if (ExpandShift(ISD::SRA, Node->getOperand(0), ShiftAmt, Lo, Hi))
4919      break;
4920
4921    // If this target supports SRA_PARTS, use it.
4922    TargetLowering::LegalizeAction Action =
4923      TLI.getOperationAction(ISD::SRA_PARTS, NVT);
4924    if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4925        Action == TargetLowering::Custom) {
4926      ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4927      break;
4928    }
4929
4930    // Otherwise, emit a libcall.
4931    Lo = ExpandLibCall("__ashrdi3", Node, Hi);
4932    break;
4933  }
4934
4935  case ISD::SRL: {
4936    // If the target wants custom lowering, do so.
4937    SDOperand ShiftAmt = LegalizeOp(Node->getOperand(1));
4938    if (TLI.getOperationAction(ISD::SRL, VT) == TargetLowering::Custom) {
4939      SDOperand Op = DAG.getNode(ISD::SRL, VT, Node->getOperand(0), ShiftAmt);
4940      Op = TLI.LowerOperation(Op, DAG);
4941      if (Op.Val) {
4942        // Now that the custom expander is done, expand the result, which is
4943        // still VT.
4944        ExpandOp(Op, Lo, Hi);
4945        break;
4946      }
4947    }
4948
4949    // If we can emit an efficient shift operation, do so now.
4950    if (ExpandShift(ISD::SRL, Node->getOperand(0), ShiftAmt, Lo, Hi))
4951      break;
4952
4953    // If this target supports SRL_PARTS, use it.
4954    TargetLowering::LegalizeAction Action =
4955      TLI.getOperationAction(ISD::SRL_PARTS, NVT);
4956    if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
4957        Action == TargetLowering::Custom) {
4958      ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), ShiftAmt, Lo, Hi);
4959      break;
4960    }
4961
4962    // Otherwise, emit a libcall.
4963    Lo = ExpandLibCall("__lshrdi3", Node, Hi);
4964    break;
4965  }
4966
4967  case ISD::ADD:
4968  case ISD::SUB: {
4969    // If the target wants to custom expand this, let them.
4970    if (TLI.getOperationAction(Node->getOpcode(), VT) ==
4971            TargetLowering::Custom) {
4972      Op = TLI.LowerOperation(Op, DAG);
4973      if (Op.Val) {
4974        ExpandOp(Op, Lo, Hi);
4975        break;
4976      }
4977    }
4978
4979    // Expand the subcomponents.
4980    SDOperand LHSL, LHSH, RHSL, RHSH;
4981    ExpandOp(Node->getOperand(0), LHSL, LHSH);
4982    ExpandOp(Node->getOperand(1), RHSL, RHSH);
4983    SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
4984    SDOperand LoOps[2], HiOps[3];
4985    LoOps[0] = LHSL;
4986    LoOps[1] = RHSL;
4987    HiOps[0] = LHSH;
4988    HiOps[1] = RHSH;
4989    if (Node->getOpcode() == ISD::ADD) {
4990      Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2);
4991      HiOps[2] = Lo.getValue(1);
4992      Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3);
4993    } else {
4994      Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2);
4995      HiOps[2] = Lo.getValue(1);
4996      Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3);
4997    }
4998    break;
4999  }
5000  case ISD::MUL: {
5001    // If the target wants to custom expand this, let them.
5002    if (TLI.getOperationAction(ISD::MUL, VT) == TargetLowering::Custom) {
5003      SDOperand New = TLI.LowerOperation(Op, DAG);
5004      if (New.Val) {
5005        ExpandOp(New, Lo, Hi);
5006        break;
5007      }
5008    }
5009
5010    bool HasMULHS = TLI.isOperationLegal(ISD::MULHS, NVT);
5011    bool HasMULHU = TLI.isOperationLegal(ISD::MULHU, NVT);
5012    if (HasMULHS || HasMULHU) {
5013      SDOperand LL, LH, RL, RH;
5014      ExpandOp(Node->getOperand(0), LL, LH);
5015      ExpandOp(Node->getOperand(1), RL, RH);
5016      unsigned SH = MVT::getSizeInBits(RH.getValueType())-1;
5017      // FIXME: Move this to the dag combiner.
5018      // MULHS implicitly sign extends its inputs.  Check to see if ExpandOp
5019      // extended the sign bit of the low half through the upper half, and if so
5020      // emit a MULHS instead of the alternate sequence that is valid for any
5021      // i64 x i64 multiply.
5022      if (HasMULHS &&
5023          // is RH an extension of the sign bit of RL?
5024          RH.getOpcode() == ISD::SRA && RH.getOperand(0) == RL &&
5025          RH.getOperand(1).getOpcode() == ISD::Constant &&
5026          cast<ConstantSDNode>(RH.getOperand(1))->getValue() == SH &&
5027          // is LH an extension of the sign bit of LL?
5028          LH.getOpcode() == ISD::SRA && LH.getOperand(0) == LL &&
5029          LH.getOperand(1).getOpcode() == ISD::Constant &&
5030          cast<ConstantSDNode>(LH.getOperand(1))->getValue() == SH) {
5031        // Low part:
5032        Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
5033        // High part:
5034        Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL);
5035        break;
5036      } else if (HasMULHU) {
5037        // Low part:
5038        Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
5039
5040        // High part:
5041        Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
5042        RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
5043        LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
5044        Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
5045        Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
5046        break;
5047      }
5048    }
5049
5050    Lo = ExpandLibCall("__muldi3" , Node, Hi);
5051    break;
5052  }
5053  case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
5054  case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
5055  case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;
5056  case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break;
5057
5058  case ISD::FADD:
5059    Lo = ExpandLibCall(((VT == MVT::f32) ? "__addsf3" : "__adddf3"), Node, Hi);
5060    break;
5061  case ISD::FSUB:
5062    Lo = ExpandLibCall(((VT == MVT::f32) ? "__subsf3" : "__subdf3"), Node, Hi);
5063    break;
5064  case ISD::FMUL:
5065    Lo = ExpandLibCall(((VT == MVT::f32) ? "__mulsf3" : "__muldf3"), Node, Hi);
5066    break;
5067  case ISD::FDIV:
5068    Lo = ExpandLibCall(((VT == MVT::f32) ? "__divsf3" : "__divdf3"), Node, Hi);
5069    break;
5070  case ISD::FP_EXTEND:
5071    Lo = ExpandLibCall("__extendsfdf2", Node, Hi);
5072    break;
5073  case ISD::FP_ROUND:
5074    Lo = ExpandLibCall("__truncdfsf2", Node, Hi);
5075    break;
5076  case ISD::SINT_TO_FP: {
5077    const char *FnName = 0;
5078    if (Node->getOperand(0).getValueType() == MVT::i64)
5079      FnName = (VT == MVT::f32) ? "__floatdisf" : "__floatdidf";
5080    else
5081      FnName = (VT == MVT::f32) ? "__floatsisf" : "__floatsidf";
5082    Lo = ExpandLibCall(FnName, Node, Hi);
5083    break;
5084  }
5085  case ISD::UINT_TO_FP: {
5086    const char *FnName = 0;
5087    if (Node->getOperand(0).getValueType() == MVT::i64)
5088      FnName = (VT == MVT::f32) ? "__floatundisf" : "__floatundidf";
5089    else
5090      FnName = (VT == MVT::f32) ? "__floatunsisf" : "__floatunsidf";
5091    Lo = ExpandLibCall(FnName, Node, Hi);
5092    break;
5093  }
5094  case ISD::FSQRT:
5095  case ISD::FSIN:
5096  case ISD::FCOS: {
5097    const char *FnName = 0;
5098    switch(Node->getOpcode()) {
5099    case ISD::FSQRT: FnName = (VT == MVT::f32) ? "sqrtf" : "sqrt"; break;
5100    case ISD::FSIN:  FnName = (VT == MVT::f32) ? "sinf"  : "sin";  break;
5101    case ISD::FCOS:  FnName = (VT == MVT::f32) ? "cosf"  : "cos";  break;
5102    default: assert(0 && "Unreachable!");
5103    }
5104    Lo = ExpandLibCall(FnName, Node, Hi);
5105    break;
5106  }
5107  case ISD::FABS: {
5108    SDOperand Mask = (VT == MVT::f64)
5109      ? DAG.getConstantFP(BitsToDouble(~(1ULL << 63)), VT)
5110      : DAG.getConstantFP(BitsToFloat(~(1U << 31)), VT);
5111    Mask = DAG.getNode(ISD::BIT_CONVERT, NVT, Mask);
5112    Lo = DAG.getNode(ISD::BIT_CONVERT, NVT, Node->getOperand(0));
5113    Lo = DAG.getNode(ISD::AND, NVT, Lo, Mask);
5114    if (getTypeAction(NVT) == Expand)
5115      ExpandOp(Lo, Lo, Hi);
5116    break;
5117  }
5118  case ISD::FNEG: {
5119    SDOperand Mask = (VT == MVT::f64)
5120      ? DAG.getConstantFP(BitsToDouble(1ULL << 63), VT)
5121      : DAG.getConstantFP(BitsToFloat(1U << 31), VT);
5122    Mask = DAG.getNode(ISD::BIT_CONVERT, NVT, Mask);
5123    Lo = DAG.getNode(ISD::BIT_CONVERT, NVT, Node->getOperand(0));
5124    Lo = DAG.getNode(ISD::XOR, NVT, Lo, Mask);
5125    if (getTypeAction(NVT) == Expand)
5126      ExpandOp(Lo, Lo, Hi);
5127    break;
5128  }
5129  }
5130
5131  // Make sure the resultant values have been legalized themselves, unless this
5132  // is a type that requires multi-step expansion.
5133  if (getTypeAction(NVT) != Expand && NVT != MVT::isVoid) {
5134    Lo = LegalizeOp(Lo);
5135    if (Hi.Val)
5136      // Don't legalize the high part if it is expanded to a single node.
5137      Hi = LegalizeOp(Hi);
5138  }
5139
5140  // Remember in a map if the values will be reused later.
5141  bool isNew =
5142    ExpandedNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second;
5143  assert(isNew && "Value already expanded?!?");
5144}
5145
5146/// SplitVectorOp - Given an operand of MVT::Vector type, break it down into
5147/// two smaller values of MVT::Vector type.
5148void SelectionDAGLegalize::SplitVectorOp(SDOperand Op, SDOperand &Lo,
5149                                         SDOperand &Hi) {
5150  assert(Op.getValueType() == MVT::Vector && "Cannot split non-vector type!");
5151  SDNode *Node = Op.Val;
5152  unsigned NumElements = cast<ConstantSDNode>(*(Node->op_end()-2))->getValue();
5153  assert(NumElements > 1 && "Cannot split a single element vector!");
5154  unsigned NewNumElts = NumElements/2;
5155  SDOperand NewNumEltsNode = DAG.getConstant(NewNumElts, MVT::i32);
5156  SDOperand TypeNode = *(Node->op_end()-1);
5157
5158  // See if we already split it.
5159  std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
5160    = SplitNodes.find(Op);
5161  if (I != SplitNodes.end()) {
5162    Lo = I->second.first;
5163    Hi = I->second.second;
5164    return;
5165  }
5166
5167  switch (Node->getOpcode()) {
5168  default:
5169#ifndef NDEBUG
5170    Node->dump();
5171#endif
5172    assert(0 && "Unhandled operation in SplitVectorOp!");
5173  case ISD::VBUILD_VECTOR: {
5174    SmallVector<SDOperand, 8> LoOps(Node->op_begin(),
5175                                    Node->op_begin()+NewNumElts);
5176    LoOps.push_back(NewNumEltsNode);
5177    LoOps.push_back(TypeNode);
5178    Lo = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &LoOps[0], LoOps.size());
5179
5180    SmallVector<SDOperand, 8> HiOps(Node->op_begin()+NewNumElts,
5181                                    Node->op_end()-2);
5182    HiOps.push_back(NewNumEltsNode);
5183    HiOps.push_back(TypeNode);
5184    Hi = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &HiOps[0], HiOps.size());
5185    break;
5186  }
5187  case ISD::VADD:
5188  case ISD::VSUB:
5189  case ISD::VMUL:
5190  case ISD::VSDIV:
5191  case ISD::VUDIV:
5192  case ISD::VAND:
5193  case ISD::VOR:
5194  case ISD::VXOR: {
5195    SDOperand LL, LH, RL, RH;
5196    SplitVectorOp(Node->getOperand(0), LL, LH);
5197    SplitVectorOp(Node->getOperand(1), RL, RH);
5198
5199    Lo = DAG.getNode(Node->getOpcode(), MVT::Vector, LL, RL,
5200                     NewNumEltsNode, TypeNode);
5201    Hi = DAG.getNode(Node->getOpcode(), MVT::Vector, LH, RH,
5202                     NewNumEltsNode, TypeNode);
5203    break;
5204  }
5205  case ISD::VLOAD: {
5206    SDOperand Ch = Node->getOperand(0);   // Legalize the chain.
5207    SDOperand Ptr = Node->getOperand(1);  // Legalize the pointer.
5208    MVT::ValueType EVT = cast<VTSDNode>(TypeNode)->getVT();
5209
5210    Lo = DAG.getVecLoad(NewNumElts, EVT, Ch, Ptr, Node->getOperand(2));
5211    unsigned IncrementSize = NewNumElts * MVT::getSizeInBits(EVT)/8;
5212    Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
5213                      getIntPtrConstant(IncrementSize));
5214    // FIXME: This creates a bogus srcvalue!
5215    Hi = DAG.getVecLoad(NewNumElts, EVT, Ch, Ptr, Node->getOperand(2));
5216
5217    // Build a factor node to remember that this load is independent of the
5218    // other one.
5219    SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
5220                               Hi.getValue(1));
5221
5222    // Remember that we legalized the chain.
5223    AddLegalizedOperand(Op.getValue(1), LegalizeOp(TF));
5224    break;
5225  }
5226  case ISD::VBIT_CONVERT: {
5227    // We know the result is a vector.  The input may be either a vector or a
5228    // scalar value.
5229    if (Op.getOperand(0).getValueType() != MVT::Vector) {
5230      // Lower to a store/load.  FIXME: this could be improved probably.
5231      SDOperand Ptr = CreateStackTemporary(Op.getOperand(0).getValueType());
5232
5233      SDOperand St = DAG.getStore(DAG.getEntryNode(),
5234                                  Op.getOperand(0), Ptr, NULL, 0);
5235      MVT::ValueType EVT = cast<VTSDNode>(TypeNode)->getVT();
5236      St = DAG.getVecLoad(NumElements, EVT, St, Ptr, DAG.getSrcValue(0));
5237      SplitVectorOp(St, Lo, Hi);
5238    } else {
5239      // If the input is a vector type, we have to either scalarize it, pack it
5240      // or convert it based on whether the input vector type is legal.
5241      SDNode *InVal = Node->getOperand(0).Val;
5242      unsigned NumElems =
5243        cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
5244      MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
5245
5246      // If the input is from a single element vector, scalarize the vector,
5247      // then treat like a scalar.
5248      if (NumElems == 1) {
5249        SDOperand Scalar = PackVectorOp(Op.getOperand(0), EVT);
5250        Scalar = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Scalar,
5251                             Op.getOperand(1), Op.getOperand(2));
5252        SplitVectorOp(Scalar, Lo, Hi);
5253      } else {
5254        // Split the input vector.
5255        SplitVectorOp(Op.getOperand(0), Lo, Hi);
5256
5257        // Convert each of the pieces now.
5258        Lo = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Lo,
5259                         NewNumEltsNode, TypeNode);
5260        Hi = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Hi,
5261                         NewNumEltsNode, TypeNode);
5262      }
5263      break;
5264    }
5265  }
5266  }
5267
5268  // Remember in a map if the values will be reused later.
5269  bool isNew =
5270    SplitNodes.insert(std::make_pair(Op, std::make_pair(Lo, Hi))).second;
5271  assert(isNew && "Value already expanded?!?");
5272}
5273
5274
5275/// PackVectorOp - Given an operand of MVT::Vector type, convert it into the
5276/// equivalent operation that returns a scalar (e.g. F32) or packed value
5277/// (e.g. MVT::V4F32).  When this is called, we know that PackedVT is the right
5278/// type for the result.
5279SDOperand SelectionDAGLegalize::PackVectorOp(SDOperand Op,
5280                                             MVT::ValueType NewVT) {
5281  assert(Op.getValueType() == MVT::Vector && "Bad PackVectorOp invocation!");
5282  SDNode *Node = Op.Val;
5283
5284  // See if we already packed it.
5285  std::map<SDOperand, SDOperand>::iterator I = PackedNodes.find(Op);
5286  if (I != PackedNodes.end()) return I->second;
5287
5288  SDOperand Result;
5289  switch (Node->getOpcode()) {
5290  default:
5291#ifndef NDEBUG
5292    Node->dump(); cerr << "\n";
5293#endif
5294    assert(0 && "Unknown vector operation in PackVectorOp!");
5295  case ISD::VADD:
5296  case ISD::VSUB:
5297  case ISD::VMUL:
5298  case ISD::VSDIV:
5299  case ISD::VUDIV:
5300  case ISD::VAND:
5301  case ISD::VOR:
5302  case ISD::VXOR:
5303    Result = DAG.getNode(getScalarizedOpcode(Node->getOpcode(), NewVT),
5304                         NewVT,
5305                         PackVectorOp(Node->getOperand(0), NewVT),
5306                         PackVectorOp(Node->getOperand(1), NewVT));
5307    break;
5308  case ISD::VLOAD: {
5309    SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
5310    SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
5311
5312    SrcValueSDNode *SV = cast<SrcValueSDNode>(Node->getOperand(2));
5313    Result = DAG.getLoad(NewVT, Ch, Ptr, SV->getValue(), SV->getOffset());
5314
5315    // Remember that we legalized the chain.
5316    AddLegalizedOperand(Op.getValue(1), LegalizeOp(Result.getValue(1)));
5317    break;
5318  }
5319  case ISD::VBUILD_VECTOR:
5320    if (Node->getOperand(0).getValueType() == NewVT) {
5321      // Returning a scalar?
5322      Result = Node->getOperand(0);
5323    } else {
5324      // Returning a BUILD_VECTOR?
5325
5326      // If all elements of the build_vector are undefs, return an undef.
5327      bool AllUndef = true;
5328      for (unsigned i = 0, e = Node->getNumOperands()-2; i != e; ++i)
5329        if (Node->getOperand(i).getOpcode() != ISD::UNDEF) {
5330          AllUndef = false;
5331          break;
5332        }
5333      if (AllUndef) {
5334        Result = DAG.getNode(ISD::UNDEF, NewVT);
5335      } else {
5336        Result = DAG.getNode(ISD::BUILD_VECTOR, NewVT, Node->op_begin(),
5337                             Node->getNumOperands()-2);
5338      }
5339    }
5340    break;
5341  case ISD::VINSERT_VECTOR_ELT:
5342    if (!MVT::isVector(NewVT)) {
5343      // Returning a scalar?  Must be the inserted element.
5344      Result = Node->getOperand(1);
5345    } else {
5346      Result = DAG.getNode(ISD::INSERT_VECTOR_ELT, NewVT,
5347                           PackVectorOp(Node->getOperand(0), NewVT),
5348                           Node->getOperand(1), Node->getOperand(2));
5349    }
5350    break;
5351  case ISD::VVECTOR_SHUFFLE:
5352    if (!MVT::isVector(NewVT)) {
5353      // Returning a scalar?  Figure out if it is the LHS or RHS and return it.
5354      SDOperand EltNum = Node->getOperand(2).getOperand(0);
5355      if (cast<ConstantSDNode>(EltNum)->getValue())
5356        Result = PackVectorOp(Node->getOperand(1), NewVT);
5357      else
5358        Result = PackVectorOp(Node->getOperand(0), NewVT);
5359    } else {
5360      // Otherwise, return a VECTOR_SHUFFLE node.  First convert the index
5361      // vector from a VBUILD_VECTOR to a BUILD_VECTOR.
5362      std::vector<SDOperand> BuildVecIdx(Node->getOperand(2).Val->op_begin(),
5363                                         Node->getOperand(2).Val->op_end()-2);
5364      MVT::ValueType BVT = MVT::getIntVectorWithNumElements(BuildVecIdx.size());
5365      SDOperand BV = DAG.getNode(ISD::BUILD_VECTOR, BVT,
5366                                 Node->getOperand(2).Val->op_begin(),
5367                                 Node->getOperand(2).Val->getNumOperands()-2);
5368
5369      Result = DAG.getNode(ISD::VECTOR_SHUFFLE, NewVT,
5370                           PackVectorOp(Node->getOperand(0), NewVT),
5371                           PackVectorOp(Node->getOperand(1), NewVT), BV);
5372    }
5373    break;
5374  case ISD::VBIT_CONVERT:
5375    if (Op.getOperand(0).getValueType() != MVT::Vector)
5376      Result = DAG.getNode(ISD::BIT_CONVERT, NewVT, Op.getOperand(0));
5377    else {
5378      // If the input is a vector type, we have to either scalarize it, pack it
5379      // or convert it based on whether the input vector type is legal.
5380      SDNode *InVal = Node->getOperand(0).Val;
5381      unsigned NumElems =
5382        cast<ConstantSDNode>(*(InVal->op_end()-2))->getValue();
5383      MVT::ValueType EVT = cast<VTSDNode>(*(InVal->op_end()-1))->getVT();
5384
5385      // Figure out if there is a Packed type corresponding to this Vector
5386      // type.  If so, convert to the packed type.
5387      MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems);
5388      if (TVT != MVT::Other && TLI.isTypeLegal(TVT)) {
5389        // Turn this into a bit convert of the packed input.
5390        Result = DAG.getNode(ISD::BIT_CONVERT, NewVT,
5391                             PackVectorOp(Node->getOperand(0), TVT));
5392        break;
5393      } else if (NumElems == 1) {
5394        // Turn this into a bit convert of the scalar input.
5395        Result = DAG.getNode(ISD::BIT_CONVERT, NewVT,
5396                             PackVectorOp(Node->getOperand(0), EVT));
5397        break;
5398      } else {
5399        // FIXME: UNIMP!
5400        assert(0 && "Cast from unsupported vector type not implemented yet!");
5401      }
5402    }
5403    break;
5404  case ISD::VSELECT:
5405    Result = DAG.getNode(ISD::SELECT, NewVT, Op.getOperand(0),
5406                         PackVectorOp(Op.getOperand(1), NewVT),
5407                         PackVectorOp(Op.getOperand(2), NewVT));
5408    break;
5409  }
5410
5411  if (TLI.isTypeLegal(NewVT))
5412    Result = LegalizeOp(Result);
5413  bool isNew = PackedNodes.insert(std::make_pair(Op, Result)).second;
5414  assert(isNew && "Value already packed?");
5415  return Result;
5416}
5417
5418
5419// SelectionDAG::Legalize - This is the entry point for the file.
5420//
5421void SelectionDAG::Legalize() {
5422  if (ViewLegalizeDAGs) viewGraph();
5423
5424  /// run - This is the main entry point to this class.
5425  ///
5426  SelectionDAGLegalize(*this).LegalizeDAG();
5427}
5428
5429