LegalizeDAG.cpp revision e5544f851a2a3f7b06339b132e60ad2f2d53e7b8
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/MachineConstantPool.h"
16#include "llvm/CodeGen/MachineFunction.h"
17#include "llvm/CodeGen/MachineFrameInfo.h"
18#include "llvm/Target/TargetLowering.h"
19#include "llvm/Target/TargetData.h"
20#include "llvm/Target/TargetOptions.h"
21#include "llvm/Constants.h"
22#include <iostream>
23using namespace llvm;
24
25//===----------------------------------------------------------------------===//
26/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and
27/// hacks on it until the target machine can handle it.  This involves
28/// eliminating value sizes the machine cannot handle (promoting small sizes to
29/// large sizes or splitting up large values into small values) as well as
30/// eliminating operations the machine cannot handle.
31///
32/// This code also does a small amount of optimization and recognition of idioms
33/// as part of its processing.  For example, if a target does not support a
34/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
35/// will attempt merge setcc and brc instructions into brcc's.
36///
37namespace {
38class SelectionDAGLegalize {
39  TargetLowering &TLI;
40  SelectionDAG &DAG;
41
42  /// LegalizeAction - This enum indicates what action we should take for each
43  /// value type the can occur in the program.
44  enum LegalizeAction {
45    Legal,            // The target natively supports this value type.
46    Promote,          // This should be promoted to the next larger type.
47    Expand,           // This integer type should be broken into smaller pieces.
48  };
49
50  /// ValueTypeActions - This is a bitvector that contains two bits for each
51  /// value type, where the two bits correspond to the LegalizeAction enum.
52  /// This can be queried with "getTypeAction(VT)".
53  unsigned ValueTypeActions;
54
55  /// NeedsAnotherIteration - This is set when we expand a large integer
56  /// operation into smaller integer operations, but the smaller operations are
57  /// not set.  This occurs only rarely in practice, for targets that don't have
58  /// 32-bit or larger integer registers.
59  bool NeedsAnotherIteration;
60
61  /// LegalizedNodes - For nodes that are of legal width, and that have more
62  /// than one use, this map indicates what regularized operand to use.  This
63  /// allows us to avoid legalizing the same thing more than once.
64  std::map<SDOperand, SDOperand> LegalizedNodes;
65
66  /// PromotedNodes - For nodes that are below legal width, and that have more
67  /// than one use, this map indicates what promoted value to use.  This allows
68  /// us to avoid promoting the same thing more than once.
69  std::map<SDOperand, SDOperand> PromotedNodes;
70
71  /// ExpandedNodes - For nodes that need to be expanded, and which have more
72  /// than one use, this map indicates which which operands are the expanded
73  /// version of the input.  This allows us to avoid expanding the same node
74  /// more than once.
75  std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
76
77  void AddLegalizedOperand(SDOperand From, SDOperand To) {
78    bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second;
79    assert(isNew && "Got into the map somehow?");
80  }
81  void AddPromotedOperand(SDOperand From, SDOperand To) {
82    bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second;
83    assert(isNew && "Got into the map somehow?");
84  }
85
86public:
87
88  SelectionDAGLegalize(TargetLowering &TLI, SelectionDAG &DAG);
89
90  /// Run - While there is still lowering to do, perform a pass over the DAG.
91  /// Most regularization can be done in a single pass, but targets that require
92  /// large values to be split into registers multiple times (e.g. i64 -> 4x
93  /// i16) require iteration for these values (the first iteration will demote
94  /// to i32, the second will demote to i16).
95  void Run() {
96    do {
97      NeedsAnotherIteration = false;
98      LegalizeDAG();
99    } while (NeedsAnotherIteration);
100  }
101
102  /// getTypeAction - Return how we should legalize values of this type, either
103  /// it is already legal or we need to expand it into multiple registers of
104  /// smaller integer type, or we need to promote it to a larger type.
105  LegalizeAction getTypeAction(MVT::ValueType VT) const {
106    return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3);
107  }
108
109  /// isTypeLegal - Return true if this type is legal on this target.
110  ///
111  bool isTypeLegal(MVT::ValueType VT) const {
112    return getTypeAction(VT) == Legal;
113  }
114
115private:
116  void LegalizeDAG();
117
118  SDOperand LegalizeOp(SDOperand O);
119  void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi);
120  SDOperand PromoteOp(SDOperand O);
121
122  bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
123                   SDOperand &Lo, SDOperand &Hi);
124  void ExpandAddSub(bool isAdd, SDOperand Op, SDOperand Amt,
125                    SDOperand &Lo, SDOperand &Hi);
126
127  SDOperand getIntPtrConstant(uint64_t Val) {
128    return DAG.getConstant(Val, TLI.getPointerTy());
129  }
130};
131}
132
133
134SelectionDAGLegalize::SelectionDAGLegalize(TargetLowering &tli,
135                                           SelectionDAG &dag)
136  : TLI(tli), DAG(dag), ValueTypeActions(TLI.getValueTypeActions()) {
137  assert(MVT::LAST_VALUETYPE <= 16 &&
138         "Too many value types for ValueTypeActions to hold!");
139}
140
141void SelectionDAGLegalize::LegalizeDAG() {
142  SDOperand OldRoot = DAG.getRoot();
143  SDOperand NewRoot = LegalizeOp(OldRoot);
144  DAG.setRoot(NewRoot);
145
146  ExpandedNodes.clear();
147  LegalizedNodes.clear();
148  PromotedNodes.clear();
149
150  // Remove dead nodes now.
151  DAG.RemoveDeadNodes(OldRoot.Val);
152}
153
154SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
155  assert(getTypeAction(Op.getValueType()) == Legal &&
156         "Caller should expand or promote operands that are not legal!");
157
158  // If this operation defines any values that cannot be represented in a
159  // register on this target, make sure to expand or promote them.
160  if (Op.Val->getNumValues() > 1) {
161    for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i)
162      switch (getTypeAction(Op.Val->getValueType(i))) {
163      case Legal: break;  // Nothing to do.
164      case Expand: {
165        SDOperand T1, T2;
166        ExpandOp(Op.getValue(i), T1, T2);
167        assert(LegalizedNodes.count(Op) &&
168               "Expansion didn't add legal operands!");
169        return LegalizedNodes[Op];
170      }
171      case Promote:
172        PromoteOp(Op.getValue(i));
173        assert(LegalizedNodes.count(Op) &&
174               "Expansion didn't add legal operands!");
175        return LegalizedNodes[Op];
176      }
177  }
178
179  std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
180  if (I != LegalizedNodes.end()) return I->second;
181
182  SDOperand Tmp1, Tmp2, Tmp3;
183
184  SDOperand Result = Op;
185  SDNode *Node = Op.Val;
186
187  switch (Node->getOpcode()) {
188  default:
189    std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
190    assert(0 && "Do not know how to legalize this operator!");
191    abort();
192  case ISD::EntryToken:
193  case ISD::FrameIndex:
194  case ISD::GlobalAddress:
195  case ISD::ExternalSymbol:
196  case ISD::ConstantPool:           // Nothing to do.
197    assert(getTypeAction(Node->getValueType(0)) == Legal &&
198           "This must be legal!");
199    break;
200  case ISD::CopyFromReg:
201    Tmp1 = LegalizeOp(Node->getOperand(0));
202    if (Tmp1 != Node->getOperand(0))
203      Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(),
204                                  Node->getValueType(0), Tmp1);
205    break;
206  case ISD::ImplicitDef:
207    Tmp1 = LegalizeOp(Node->getOperand(0));
208    if (Tmp1 != Node->getOperand(0))
209      Result = DAG.getImplicitDef(Tmp1, cast<RegSDNode>(Node)->getReg());
210    break;
211  case ISD::Constant:
212    // We know we don't need to expand constants here, constants only have one
213    // value and we check that it is fine above.
214
215    // FIXME: Maybe we should handle things like targets that don't support full
216    // 32-bit immediates?
217    break;
218  case ISD::ConstantFP: {
219    // Spill FP immediates to the constant pool if the target cannot directly
220    // codegen them.  Targets often have some immediate values that can be
221    // efficiently generated into an FP register without a load.  We explicitly
222    // leave these constants as ConstantFP nodes for the target to deal with.
223
224    ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
225
226    // Check to see if this FP immediate is already legal.
227    bool isLegal = false;
228    for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(),
229           E = TLI.legal_fpimm_end(); I != E; ++I)
230      if (CFP->isExactlyValue(*I)) {
231        isLegal = true;
232        break;
233      }
234
235    if (!isLegal) {
236      // Otherwise we need to spill the constant to memory.
237      MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
238
239      bool Extend = false;
240
241      // If a FP immediate is precise when represented as a float, we put it
242      // into the constant pool as a float, even if it's is statically typed
243      // as a double.
244      MVT::ValueType VT = CFP->getValueType(0);
245      bool isDouble = VT == MVT::f64;
246      ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy :
247                                             Type::FloatTy, CFP->getValue());
248      if (isDouble && CFP->isExactlyValue((float)CFP->getValue())) {
249        LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy));
250        VT = MVT::f32;
251        Extend = true;
252      }
253
254      SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
255                                            TLI.getPointerTy());
256      if (Extend) {
257        Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx,
258                             MVT::f32);
259      } else {
260        Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx);
261      }
262    }
263    break;
264  }
265  case ISD::TokenFactor: {
266    std::vector<SDOperand> Ops;
267    bool Changed = false;
268    for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
269      SDOperand Op = Node->getOperand(i);
270      // Fold single-use TokenFactor nodes into this token factor as we go.
271      if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
272        Changed = true;
273        for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
274          Ops.push_back(LegalizeOp(Op.getOperand(j)));
275      } else {
276        Ops.push_back(LegalizeOp(Op));  // Legalize the operands
277        Changed |= Ops[i] != Op;
278      }
279    }
280    if (Changed)
281      Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
282    break;
283  }
284
285  case ISD::ADJCALLSTACKDOWN:
286  case ISD::ADJCALLSTACKUP:
287    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
288    // There is no need to legalize the size argument (Operand #1)
289    if (Tmp1 != Node->getOperand(0))
290      Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1,
291                           Node->getOperand(1));
292    break;
293  case ISD::DYNAMIC_STACKALLOC:
294    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
295    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the size.
296    Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the alignment.
297    if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
298        Tmp3 != Node->getOperand(2))
299      Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, Node->getValueType(0),
300                           Tmp1, Tmp2, Tmp3);
301    else
302      Result = Op.getValue(0);
303
304    // Since this op produces two values, make sure to remember that we
305    // legalized both of them.
306    AddLegalizedOperand(SDOperand(Node, 0), Result);
307    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
308    return Result.getValue(Op.ResNo);
309
310  case ISD::CALL: {
311    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
312    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
313
314    bool Changed = false;
315    std::vector<SDOperand> Ops;
316    for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
317      Ops.push_back(LegalizeOp(Node->getOperand(i)));
318      Changed |= Ops.back() != Node->getOperand(i);
319    }
320
321    if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) {
322      std::vector<MVT::ValueType> RetTyVTs;
323      RetTyVTs.reserve(Node->getNumValues());
324      for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
325        RetTyVTs.push_back(Node->getValueType(i));
326      Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops), 0);
327    } else {
328      Result = Result.getValue(0);
329    }
330    // Since calls produce multiple values, make sure to remember that we
331    // legalized all of them.
332    for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
333      AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
334    return Result.getValue(Op.ResNo);
335  }
336  case ISD::BR:
337    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
338    if (Tmp1 != Node->getOperand(0))
339      Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1));
340    break;
341
342  case ISD::BRCOND:
343    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
344
345    switch (getTypeAction(Node->getOperand(1).getValueType())) {
346    case Expand: assert(0 && "It's impossible to expand bools");
347    case Legal:
348      Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
349      break;
350    case Promote:
351      Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
352      break;
353    }
354    // Basic block destination (Op#2) is always legal.
355    if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
356      Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
357                           Node->getOperand(2));
358    break;
359
360  case ISD::LOAD:
361    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
362    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
363    if (Tmp1 != Node->getOperand(0) ||
364        Tmp2 != Node->getOperand(1))
365      Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2);
366    else
367      Result = SDOperand(Node, 0);
368
369    // Since loads produce two values, make sure to remember that we legalized
370    // both of them.
371    AddLegalizedOperand(SDOperand(Node, 0), Result);
372    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
373    return Result.getValue(Op.ResNo);
374
375  case ISD::EXTLOAD:
376  case ISD::SEXTLOAD:
377  case ISD::ZEXTLOAD:
378    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
379    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
380    if (Tmp1 != Node->getOperand(0) ||
381        Tmp2 != Node->getOperand(1))
382      Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2,
383                           cast<MVTSDNode>(Node)->getExtraValueType());
384    else
385      Result = SDOperand(Node, 0);
386
387    // Since loads produce two values, make sure to remember that we legalized
388    // both of them.
389    AddLegalizedOperand(SDOperand(Node, 0), Result);
390    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
391    return Result.getValue(Op.ResNo);
392
393  case ISD::EXTRACT_ELEMENT:
394    // Get both the low and high parts.
395    ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
396    if (cast<ConstantSDNode>(Node->getOperand(1))->getValue())
397      Result = Tmp2;  // 1 -> Hi
398    else
399      Result = Tmp1;  // 0 -> Lo
400    break;
401
402  case ISD::CopyToReg:
403    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
404
405    switch (getTypeAction(Node->getOperand(1).getValueType())) {
406    case Legal:
407      // Legalize the incoming value (must be legal).
408      Tmp2 = LegalizeOp(Node->getOperand(1));
409      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
410        Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
411      break;
412    case Promote:
413      Tmp2 = PromoteOp(Node->getOperand(1));
414      Result = DAG.getCopyToReg(Tmp1, Tmp2, cast<RegSDNode>(Node)->getReg());
415      break;
416    case Expand:
417      SDOperand Lo, Hi;
418      ExpandOp(Node->getOperand(1), Lo, Hi);
419      unsigned Reg = cast<RegSDNode>(Node)->getReg();
420      Lo = DAG.getCopyToReg(Tmp1, Lo, Reg);
421      Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1);
422      // Note that the copytoreg nodes are independent of each other.
423      Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
424      assert(isTypeLegal(Result.getValueType()) &&
425             "Cannot expand multiple times yet (i64 -> i16)");
426      break;
427    }
428    break;
429
430  case ISD::RET:
431    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
432    switch (Node->getNumOperands()) {
433    case 2:  // ret val
434      switch (getTypeAction(Node->getOperand(1).getValueType())) {
435      case Legal:
436        Tmp2 = LegalizeOp(Node->getOperand(1));
437        if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
438          Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
439        break;
440      case Expand: {
441        SDOperand Lo, Hi;
442        ExpandOp(Node->getOperand(1), Lo, Hi);
443        Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
444        break;
445      }
446      case Promote:
447        Tmp2 = PromoteOp(Node->getOperand(1));
448        Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2);
449        break;
450      }
451      break;
452    case 1:  // ret void
453      if (Tmp1 != Node->getOperand(0))
454        Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1);
455      break;
456    default: { // ret <values>
457      std::vector<SDOperand> NewValues;
458      NewValues.push_back(Tmp1);
459      for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
460        switch (getTypeAction(Node->getOperand(i).getValueType())) {
461        case Legal:
462          NewValues.push_back(LegalizeOp(Node->getOperand(i)));
463          break;
464        case Expand: {
465          SDOperand Lo, Hi;
466          ExpandOp(Node->getOperand(i), Lo, Hi);
467          NewValues.push_back(Lo);
468          NewValues.push_back(Hi);
469          break;
470        }
471        case Promote:
472          assert(0 && "Can't promote multiple return value yet!");
473        }
474      Result = DAG.getNode(ISD::RET, MVT::Other, NewValues);
475      break;
476    }
477    }
478    break;
479  case ISD::STORE:
480    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
481    Tmp2 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
482
483    // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
484    if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){
485      if (CFP->getValueType(0) == MVT::f32) {
486        union {
487          unsigned I;
488          float    F;
489        } V;
490        V.F = CFP->getValue();
491        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
492                             DAG.getConstant(V.I, MVT::i32), Tmp2);
493      } else {
494        assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
495        union {
496          uint64_t I;
497          double   F;
498        } V;
499        V.F = CFP->getValue();
500        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
501                             DAG.getConstant(V.I, MVT::i64), Tmp2);
502      }
503      Op = Result;
504      Node = Op.Val;
505    }
506
507    switch (getTypeAction(Node->getOperand(1).getValueType())) {
508    case Legal: {
509      SDOperand Val = LegalizeOp(Node->getOperand(1));
510      if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
511          Tmp2 != Node->getOperand(2))
512        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2);
513      break;
514    }
515    case Promote:
516      // Truncate the value and store the result.
517      Tmp3 = PromoteOp(Node->getOperand(1));
518      Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
519                           Node->getOperand(1).getValueType());
520      break;
521
522    case Expand:
523      SDOperand Lo, Hi;
524      ExpandOp(Node->getOperand(1), Lo, Hi);
525
526      if (!TLI.isLittleEndian())
527        std::swap(Lo, Hi);
528
529      Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2);
530
531      unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
532      Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
533                         getIntPtrConstant(IncrementSize));
534      assert(isTypeLegal(Tmp2.getValueType()) &&
535             "Pointers must be legal!");
536      Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2);
537      Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
538      break;
539    }
540    break;
541  case ISD::TRUNCSTORE:
542    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
543    Tmp3 = LegalizeOp(Node->getOperand(2));  // Legalize the pointer.
544
545    switch (getTypeAction(Node->getOperand(1).getValueType())) {
546    case Legal:
547      Tmp2 = LegalizeOp(Node->getOperand(1));
548      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
549          Tmp3 != Node->getOperand(2))
550        Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
551                             cast<MVTSDNode>(Node)->getExtraValueType());
552      break;
553    case Promote:
554    case Expand:
555      assert(0 && "Cannot handle illegal TRUNCSTORE yet!");
556    }
557    break;
558  case ISD::SELECT:
559    switch (getTypeAction(Node->getOperand(0).getValueType())) {
560    case Expand: assert(0 && "It's impossible to expand bools");
561    case Legal:
562      Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
563      break;
564    case Promote:
565      Tmp1 = PromoteOp(Node->getOperand(0));  // Promote the condition.
566      break;
567    }
568    Tmp2 = LegalizeOp(Node->getOperand(1));   // TrueVal
569    Tmp3 = LegalizeOp(Node->getOperand(2));   // FalseVal
570
571    switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) {
572    default: assert(0 && "This action is not supported yet!");
573    case TargetLowering::Legal:
574      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
575          Tmp3 != Node->getOperand(2))
576        Result = DAG.getNode(ISD::SELECT, Node->getValueType(0),
577                             Tmp1, Tmp2, Tmp3);
578      break;
579    case TargetLowering::Promote: {
580      MVT::ValueType NVT =
581        TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType());
582      unsigned ExtOp, TruncOp;
583      if (MVT::isInteger(Tmp2.getValueType())) {
584        ExtOp = ISD::ZERO_EXTEND;
585        TruncOp  = ISD::TRUNCATE;
586      } else {
587        ExtOp = ISD::FP_EXTEND;
588        TruncOp  = ISD::FP_ROUND;
589      }
590      // Promote each of the values to the new type.
591      Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2);
592      Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3);
593      // Perform the larger operation, then round down.
594      Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3);
595      Result = DAG.getNode(TruncOp, Node->getValueType(0), Result);
596      break;
597    }
598    }
599    break;
600  case ISD::SETCC:
601    switch (getTypeAction(Node->getOperand(0).getValueType())) {
602    case Legal:
603      Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
604      Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
605      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
606        Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
607                              Node->getValueType(0), Tmp1, Tmp2);
608      break;
609    case Promote:
610      Tmp1 = PromoteOp(Node->getOperand(0));   // LHS
611      Tmp2 = PromoteOp(Node->getOperand(1));   // RHS
612
613      // If this is an FP compare, the operands have already been extended.
614      if (MVT::isInteger(Node->getOperand(0).getValueType())) {
615        MVT::ValueType VT = Node->getOperand(0).getValueType();
616        MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
617
618        // Otherwise, we have to insert explicit sign or zero extends.  Note
619        // that we could insert sign extends for ALL conditions, but zero extend
620        // is cheaper on many machines (an AND instead of two shifts), so prefer
621        // it.
622        switch (cast<SetCCSDNode>(Node)->getCondition()) {
623        default: assert(0 && "Unknown integer comparison!");
624        case ISD::SETEQ:
625        case ISD::SETNE:
626        case ISD::SETUGE:
627        case ISD::SETUGT:
628        case ISD::SETULE:
629        case ISD::SETULT:
630          // ALL of these operations will work if we either sign or zero extend
631          // the operands (including the unsigned comparisons!).  Zero extend is
632          // usually a simpler/cheaper operation, so prefer it.
633          Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
634          Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
635          break;
636        case ISD::SETGE:
637        case ISD::SETGT:
638        case ISD::SETLT:
639        case ISD::SETLE:
640          Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
641          Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
642          break;
643        }
644
645      }
646      Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
647                            Node->getValueType(0), Tmp1, Tmp2);
648      break;
649    case Expand:
650      SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
651      ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
652      ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
653      switch (cast<SetCCSDNode>(Node)->getCondition()) {
654      case ISD::SETEQ:
655      case ISD::SETNE:
656        Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
657        Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
658        Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
659        Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
660                              Node->getValueType(0), Tmp1,
661                              DAG.getConstant(0, Tmp1.getValueType()));
662        break;
663      default:
664        // FIXME: This generated code sucks.
665        ISD::CondCode LowCC;
666        switch (cast<SetCCSDNode>(Node)->getCondition()) {
667        default: assert(0 && "Unknown integer setcc!");
668        case ISD::SETLT:
669        case ISD::SETULT: LowCC = ISD::SETULT; break;
670        case ISD::SETGT:
671        case ISD::SETUGT: LowCC = ISD::SETUGT; break;
672        case ISD::SETLE:
673        case ISD::SETULE: LowCC = ISD::SETULE; break;
674        case ISD::SETGE:
675        case ISD::SETUGE: LowCC = ISD::SETUGE; break;
676        }
677
678        // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
679        // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
680        // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
681
682        // NOTE: on targets without efficient SELECT of bools, we can always use
683        // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
684        Tmp1 = DAG.getSetCC(LowCC, Node->getValueType(0), LHSLo, RHSLo);
685        Tmp2 = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
686                            Node->getValueType(0), LHSHi, RHSHi);
687        Result = DAG.getSetCC(ISD::SETEQ, Node->getValueType(0), LHSHi, RHSHi);
688        Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(),
689                             Result, Tmp1, Tmp2);
690        break;
691      }
692    }
693    break;
694
695  case ISD::MEMSET:
696  case ISD::MEMCPY:
697  case ISD::MEMMOVE: {
698    Tmp1 = LegalizeOp(Node->getOperand(0));
699    Tmp2 = LegalizeOp(Node->getOperand(1));
700    Tmp3 = LegalizeOp(Node->getOperand(2));
701    SDOperand Tmp4 = LegalizeOp(Node->getOperand(3));
702    SDOperand Tmp5 = LegalizeOp(Node->getOperand(4));
703
704    switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) {
705    default: assert(0 && "This action not implemented for this operation!");
706    case TargetLowering::Legal:
707      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
708          Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) ||
709          Tmp5 != Node->getOperand(4)) {
710        std::vector<SDOperand> Ops;
711        Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
712        Ops.push_back(Tmp4); Ops.push_back(Tmp5);
713        Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
714      }
715      break;
716    case TargetLowering::Expand: {
717      // Otherwise, the target does not support this operation.  Lower the
718      // operation to an explicit libcall as appropriate.
719      MVT::ValueType IntPtr = TLI.getPointerTy();
720      const Type *IntPtrTy = TLI.getTargetData().getIntPtrType();
721      std::vector<std::pair<SDOperand, const Type*> > Args;
722
723      const char *FnName = 0;
724      if (Node->getOpcode() == ISD::MEMSET) {
725        Args.push_back(std::make_pair(Tmp2, IntPtrTy));
726        // Extend the ubyte argument to be an int value for the call.
727        Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3);
728        Args.push_back(std::make_pair(Tmp3, Type::IntTy));
729        Args.push_back(std::make_pair(Tmp4, IntPtrTy));
730
731        FnName = "memset";
732      } else if (Node->getOpcode() == ISD::MEMCPY ||
733                 Node->getOpcode() == ISD::MEMMOVE) {
734        Args.push_back(std::make_pair(Tmp2, IntPtrTy));
735        Args.push_back(std::make_pair(Tmp3, IntPtrTy));
736        Args.push_back(std::make_pair(Tmp4, IntPtrTy));
737        FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy";
738      } else {
739        assert(0 && "Unknown op!");
740      }
741      std::pair<SDOperand,SDOperand> CallResult =
742        TLI.LowerCallTo(Tmp1, Type::VoidTy,
743                        DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
744      Result = LegalizeOp(CallResult.second);
745      break;
746    }
747    case TargetLowering::Custom:
748      std::vector<SDOperand> Ops;
749      Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3);
750      Ops.push_back(Tmp4); Ops.push_back(Tmp5);
751      Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops);
752      Result = TLI.LowerOperation(Result);
753      Result = LegalizeOp(Result);
754      break;
755    }
756    break;
757  }
758  case ISD::ADD_PARTS:
759  case ISD::SUB_PARTS: {
760    std::vector<SDOperand> Ops;
761    bool Changed = false;
762    for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
763      Ops.push_back(LegalizeOp(Node->getOperand(i)));
764      Changed |= Ops.back() != Node->getOperand(i);
765    }
766    if (Changed)
767      Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
768    break;
769  }
770  case ISD::ADD:
771  case ISD::SUB:
772  case ISD::MUL:
773  case ISD::UDIV:
774  case ISD::SDIV:
775  case ISD::UREM:
776  case ISD::SREM:
777  case ISD::AND:
778  case ISD::OR:
779  case ISD::XOR:
780  case ISD::SHL:
781  case ISD::SRL:
782  case ISD::SRA:
783    Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
784    Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
785    if (Tmp1 != Node->getOperand(0) ||
786        Tmp2 != Node->getOperand(1))
787      Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
788    break;
789  case ISD::ZERO_EXTEND:
790  case ISD::SIGN_EXTEND:
791  case ISD::TRUNCATE:
792  case ISD::FP_EXTEND:
793  case ISD::FP_ROUND:
794  case ISD::FP_TO_SINT:
795  case ISD::FP_TO_UINT:
796  case ISD::SINT_TO_FP:
797  case ISD::UINT_TO_FP:
798    switch (getTypeAction(Node->getOperand(0).getValueType())) {
799    case Legal:
800      Tmp1 = LegalizeOp(Node->getOperand(0));
801      if (Tmp1 != Node->getOperand(0))
802        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
803      break;
804    case Expand:
805      assert(Node->getOpcode() != ISD::SINT_TO_FP &&
806             Node->getOpcode() != ISD::UINT_TO_FP &&
807             "Cannot lower Xint_to_fp to a call yet!");
808
809      // In the expand case, we must be dealing with a truncate, because
810      // otherwise the result would be larger than the source.
811      assert(Node->getOpcode() == ISD::TRUNCATE &&
812             "Shouldn't need to expand other operators here!");
813      ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
814
815      // Since the result is legal, we should just be able to truncate the low
816      // part of the source.
817      Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
818      break;
819
820    case Promote:
821      switch (Node->getOpcode()) {
822      case ISD::ZERO_EXTEND:
823        Result = PromoteOp(Node->getOperand(0));
824        // NOTE: Any extend would work here...
825        Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
826        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Op.getValueType(),
827                             Result, Node->getOperand(0).getValueType());
828        break;
829      case ISD::SIGN_EXTEND:
830        Result = PromoteOp(Node->getOperand(0));
831        // NOTE: Any extend would work here...
832        Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
833        Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
834                             Result, Node->getOperand(0).getValueType());
835        break;
836      case ISD::TRUNCATE:
837        Result = PromoteOp(Node->getOperand(0));
838        Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result);
839        break;
840      case ISD::FP_EXTEND:
841        Result = PromoteOp(Node->getOperand(0));
842        if (Result.getValueType() != Op.getValueType())
843          // Dynamically dead while we have only 2 FP types.
844          Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result);
845        break;
846      case ISD::FP_ROUND:
847      case ISD::FP_TO_SINT:
848      case ISD::FP_TO_UINT:
849        Result = PromoteOp(Node->getOperand(0));
850        Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result);
851        break;
852      case ISD::SINT_TO_FP:
853        Result = PromoteOp(Node->getOperand(0));
854        Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
855                             Result, Node->getOperand(0).getValueType());
856        Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result);
857        break;
858      case ISD::UINT_TO_FP:
859        Result = PromoteOp(Node->getOperand(0));
860        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
861                             Result, Node->getOperand(0).getValueType());
862        Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result);
863        break;
864      }
865    }
866    break;
867  case ISD::FP_ROUND_INREG:
868  case ISD::SIGN_EXTEND_INREG:
869  case ISD::ZERO_EXTEND_INREG: {
870    Tmp1 = LegalizeOp(Node->getOperand(0));
871    MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType();
872
873    // If this operation is not supported, convert it to a shl/shr or load/store
874    // pair.
875    switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) {
876    default: assert(0 && "This action not supported for this op yet!");
877    case TargetLowering::Legal:
878      if (Tmp1 != Node->getOperand(0))
879        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
880                             ExtraVT);
881      break;
882    case TargetLowering::Expand:
883      // If this is an integer extend and shifts are supported, do that.
884      if (Node->getOpcode() == ISD::ZERO_EXTEND_INREG) {
885        // NOTE: we could fall back on load/store here too for targets without
886        // AND.  However, it is doubtful that any exist.
887        // AND out the appropriate bits.
888        SDOperand Mask =
889          DAG.getConstant((1ULL << MVT::getSizeInBits(ExtraVT))-1,
890                          Node->getValueType(0));
891        Result = DAG.getNode(ISD::AND, Node->getValueType(0),
892                             Node->getOperand(0), Mask);
893      } else if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
894        // NOTE: we could fall back on load/store here too for targets without
895        // SAR.  However, it is doubtful that any exist.
896        unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
897                            MVT::getSizeInBits(ExtraVT);
898        SDOperand ShiftCst = DAG.getConstant(BitsDiff, MVT::i8);
899        Result = DAG.getNode(ISD::SHL, Node->getValueType(0),
900                             Node->getOperand(0), ShiftCst);
901        Result = DAG.getNode(ISD::SRA, Node->getValueType(0),
902                             Result, ShiftCst);
903      } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) {
904        // The only way we can lower this is to turn it into a STORETRUNC,
905        // EXTLOAD pair, targetting a temporary location (a stack slot).
906
907        // NOTE: there is a choice here between constantly creating new stack
908        // slots and always reusing the same one.  We currently always create
909        // new ones, as reuse may inhibit scheduling.
910        const Type *Ty = MVT::getTypeForValueType(ExtraVT);
911        unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
912        unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
913        MachineFunction &MF = DAG.getMachineFunction();
914        int SSFI =
915          MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
916        SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
917        Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
918                             Node->getOperand(0), StackSlot, ExtraVT);
919        Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
920                             Result, StackSlot, ExtraVT);
921      } else {
922        assert(0 && "Unknown op");
923      }
924      Result = LegalizeOp(Result);
925      break;
926    }
927    break;
928  }
929  }
930
931  if (!Op.Val->hasOneUse())
932    AddLegalizedOperand(Op, Result);
933
934  return Result;
935}
936
937/// PromoteOp - Given an operation that produces a value in an invalid type,
938/// promote it to compute the value into a larger type.  The produced value will
939/// have the correct bits for the low portion of the register, but no guarantee
940/// is made about the top bits: it may be zero, sign-extended, or garbage.
941SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
942  MVT::ValueType VT = Op.getValueType();
943  MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
944  assert(getTypeAction(VT) == Promote &&
945         "Caller should expand or legalize operands that are not promotable!");
946  assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
947         "Cannot promote to smaller type!");
948
949  std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
950  if (I != PromotedNodes.end()) return I->second;
951
952  SDOperand Tmp1, Tmp2, Tmp3;
953
954  SDOperand Result;
955  SDNode *Node = Op.Val;
956
957  // Promotion needs an optimization step to clean up after it, and is not
958  // careful to avoid operations the target does not support.  Make sure that
959  // all generated operations are legalized in the next iteration.
960  NeedsAnotherIteration = true;
961
962  switch (Node->getOpcode()) {
963  default:
964    std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
965    assert(0 && "Do not know how to promote this operator!");
966    abort();
967  case ISD::Constant:
968    Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op);
969    assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?");
970    break;
971  case ISD::ConstantFP:
972    Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op);
973    assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?");
974    break;
975  case ISD::CopyFromReg:
976    Result = DAG.getCopyFromReg(cast<RegSDNode>(Node)->getReg(), NVT,
977                                Node->getOperand(0));
978    // Remember that we legalized the chain.
979    AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
980    break;
981
982  case ISD::SETCC:
983    assert(getTypeAction(TLI.getSetCCResultTy()) == Legal &&
984           "SetCC type is not legal??");
985    Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
986                          TLI.getSetCCResultTy(), Node->getOperand(0),
987                          Node->getOperand(1));
988    Result = LegalizeOp(Result);
989    break;
990
991  case ISD::TRUNCATE:
992    switch (getTypeAction(Node->getOperand(0).getValueType())) {
993    case Legal:
994      Result = LegalizeOp(Node->getOperand(0));
995      assert(Result.getValueType() >= NVT &&
996             "This truncation doesn't make sense!");
997      if (Result.getValueType() > NVT)    // Truncate to NVT instead of VT
998        Result = DAG.getNode(ISD::TRUNCATE, NVT, Result);
999      break;
1000    case Expand:
1001      assert(0 && "Cannot handle expand yet");
1002    case Promote:
1003      assert(0 && "Cannot handle promote-promote yet");
1004    }
1005    break;
1006  case ISD::SIGN_EXTEND:
1007  case ISD::ZERO_EXTEND:
1008    switch (getTypeAction(Node->getOperand(0).getValueType())) {
1009    case Expand: assert(0 && "BUG: Smaller reg should have been promoted!");
1010    case Legal:
1011      // Input is legal?  Just do extend all the way to the larger type.
1012      Result = LegalizeOp(Node->getOperand(0));
1013      Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1014      break;
1015    case Promote:
1016      // Promote the reg if it's smaller.
1017      Result = PromoteOp(Node->getOperand(0));
1018      // The high bits are not guaranteed to be anything.  Insert an extend.
1019      if (Node->getOpcode() == ISD::SIGN_EXTEND)
1020        Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, VT);
1021      else
1022        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Result, VT);
1023      break;
1024    }
1025    break;
1026
1027  case ISD::FP_EXTEND:
1028    assert(0 && "Case not implemented.  Dynamically dead with 2 FP types!");
1029  case ISD::FP_ROUND:
1030    switch (getTypeAction(Node->getOperand(0).getValueType())) {
1031    case Expand: assert(0 && "BUG: Cannot expand FP regs!");
1032    case Promote:  assert(0 && "Unreachable with 2 FP types!");
1033    case Legal:
1034      // Input is legal?  Do an FP_ROUND_INREG.
1035      Result = LegalizeOp(Node->getOperand(0));
1036      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1037      break;
1038    }
1039    break;
1040
1041  case ISD::SINT_TO_FP:
1042  case ISD::UINT_TO_FP:
1043    switch (getTypeAction(Node->getOperand(0).getValueType())) {
1044    case Legal:
1045      Result = LegalizeOp(Node->getOperand(0));
1046      break;
1047
1048    case Promote:
1049      Result = PromoteOp(Node->getOperand(0));
1050      if (Node->getOpcode() == ISD::SINT_TO_FP)
1051        Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
1052                             Result, Node->getOperand(0).getValueType());
1053      else
1054        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
1055                             Result, Node->getOperand(0).getValueType());
1056      break;
1057    case Expand:
1058      assert(0 && "Unimplemented");
1059    }
1060    // No extra round required here.
1061    Result = DAG.getNode(Node->getOpcode(), NVT, Result);
1062    break;
1063
1064  case ISD::FP_TO_SINT:
1065  case ISD::FP_TO_UINT:
1066    switch (getTypeAction(Node->getOperand(0).getValueType())) {
1067    case Legal:
1068      Tmp1 = LegalizeOp(Node->getOperand(0));
1069      break;
1070    case Promote:
1071      // The input result is prerounded, so we don't have to do anything
1072      // special.
1073      Tmp1 = PromoteOp(Node->getOperand(0));
1074      break;
1075    case Expand:
1076      assert(0 && "not implemented");
1077    }
1078    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
1079    break;
1080
1081  case ISD::AND:
1082  case ISD::OR:
1083  case ISD::XOR:
1084  case ISD::ADD:
1085  case ISD::SUB:
1086  case ISD::MUL:
1087    // The input may have strange things in the top bits of the registers, but
1088    // these operations don't care.  They may have wierd bits going out, but
1089    // that too is okay if they are integer operations.
1090    Tmp1 = PromoteOp(Node->getOperand(0));
1091    Tmp2 = PromoteOp(Node->getOperand(1));
1092    assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT);
1093    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1094
1095    // However, if this is a floating point operation, they will give excess
1096    // precision that we may not be able to tolerate.  If we DO allow excess
1097    // precision, just leave it, otherwise excise it.
1098    // FIXME: Why would we need to round FP ops more than integer ones?
1099    //     Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C))
1100    if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1101      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1102    break;
1103
1104  case ISD::SDIV:
1105  case ISD::SREM:
1106    // These operators require that their input be sign extended.
1107    Tmp1 = PromoteOp(Node->getOperand(0));
1108    Tmp2 = PromoteOp(Node->getOperand(1));
1109    if (MVT::isInteger(NVT)) {
1110      Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1111      Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, VT);
1112    }
1113    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1114
1115    // Perform FP_ROUND: this is probably overly pessimistic.
1116    if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision)
1117      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
1118    break;
1119
1120  case ISD::UDIV:
1121  case ISD::UREM:
1122    // These operators require that their input be zero extended.
1123    Tmp1 = PromoteOp(Node->getOperand(0));
1124    Tmp2 = PromoteOp(Node->getOperand(1));
1125    assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
1126    Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1127    Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
1128    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
1129    break;
1130
1131  case ISD::SHL:
1132    Tmp1 = PromoteOp(Node->getOperand(0));
1133    Tmp2 = LegalizeOp(Node->getOperand(1));
1134    Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2);
1135    break;
1136  case ISD::SRA:
1137    // The input value must be properly sign extended.
1138    Tmp1 = PromoteOp(Node->getOperand(0));
1139    Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, VT);
1140    Tmp2 = LegalizeOp(Node->getOperand(1));
1141    Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2);
1142    break;
1143  case ISD::SRL:
1144    // The input value must be properly zero extended.
1145    Tmp1 = PromoteOp(Node->getOperand(0));
1146    Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
1147    Tmp2 = LegalizeOp(Node->getOperand(1));
1148    Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
1149    break;
1150  case ISD::LOAD:
1151    Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1152    Tmp2 = LegalizeOp(Node->getOperand(1));   // Legalize the pointer.
1153    Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT);
1154
1155    // Remember that we legalized the chain.
1156    AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1157    break;
1158  case ISD::SELECT:
1159    switch (getTypeAction(Node->getOperand(0).getValueType())) {
1160    case Expand: assert(0 && "It's impossible to expand bools");
1161    case Legal:
1162      Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition.
1163      break;
1164    case Promote:
1165      Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition.
1166      break;
1167    }
1168    Tmp2 = PromoteOp(Node->getOperand(1));   // Legalize the op0
1169    Tmp3 = PromoteOp(Node->getOperand(2));   // Legalize the op1
1170    Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3);
1171    break;
1172  case ISD::CALL: {
1173    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1174    Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1175
1176    std::vector<SDOperand> Ops;
1177    for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i)
1178      Ops.push_back(LegalizeOp(Node->getOperand(i)));
1179
1180    assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1181           "Can only promote single result calls");
1182    std::vector<MVT::ValueType> RetTyVTs;
1183    RetTyVTs.reserve(2);
1184    RetTyVTs.push_back(NVT);
1185    RetTyVTs.push_back(MVT::Other);
1186    SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops);
1187    Result = SDOperand(NC, 0);
1188
1189    // Insert the new chain mapping.
1190    AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
1191    break;
1192  }
1193  }
1194
1195  assert(Result.Val && "Didn't set a result!");
1196  AddPromotedOperand(Op, Result);
1197  return Result;
1198}
1199
1200/// ExpandAddSub - Find a clever way to expand this add operation into
1201/// subcomponents.
1202void SelectionDAGLegalize::ExpandAddSub(bool isAdd, SDOperand LHS,SDOperand RHS,
1203                                        SDOperand &Lo, SDOperand &Hi) {
1204  // Expand the subcomponents.
1205  SDOperand LHSL, LHSH, RHSL, RHSH;
1206  ExpandOp(LHS, LHSL, LHSH);
1207  ExpandOp(RHS, RHSL, RHSH);
1208
1209  // Convert this add to the appropriate ADDC pair.  The low part has no carry
1210  // in.
1211  unsigned Opc = isAdd ? ISD::ADD_PARTS : ISD::SUB_PARTS;
1212  std::vector<SDOperand> Ops;
1213  Ops.push_back(LHSL);
1214  Ops.push_back(LHSH);
1215  Ops.push_back(RHSL);
1216  Ops.push_back(RHSH);
1217  Lo = DAG.getNode(Opc, LHSL.getValueType(), Ops);
1218  Hi = Lo.getValue(1);
1219}
1220
1221/// ExpandShift - Try to find a clever way to expand this shift operation out to
1222/// smaller elements.  If we can't find a way that is more efficient than a
1223/// libcall on this target, return false.  Otherwise, return true with the
1224/// low-parts expanded into Lo and Hi.
1225bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
1226                                       SDOperand &Lo, SDOperand &Hi) {
1227  assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
1228         "This is not a shift!");
1229  MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
1230
1231  // If we have an efficient select operation (or if the selects will all fold
1232  // away), lower to some complex code, otherwise just emit the libcall.
1233  if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal &&
1234      !isa<ConstantSDNode>(Amt))
1235    return false;
1236
1237  SDOperand InL, InH;
1238  ExpandOp(Op, InL, InH);
1239  SDOperand ShAmt = LegalizeOp(Amt);
1240  MVT::ValueType ShTy = ShAmt.getValueType();
1241
1242  unsigned NVTBits = MVT::getSizeInBits(NVT);
1243  SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy,           // NAmt = 32-ShAmt
1244                               DAG.getConstant(NVTBits, ShTy), ShAmt);
1245
1246  // Compare the unmasked shift amount against 32.
1247  SDOperand Cond = DAG.getSetCC(ISD::SETGE, TLI.getSetCCResultTy(), ShAmt,
1248                                DAG.getConstant(NVTBits, ShTy));
1249
1250  if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) {
1251    ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt,             // ShAmt &= 31
1252                        DAG.getConstant(NVTBits-1, ShTy));
1253    NAmt  = DAG.getNode(ISD::AND, ShTy, NAmt,              // NAmt &= 31
1254                        DAG.getConstant(NVTBits-1, ShTy));
1255  }
1256
1257  if (Opc == ISD::SHL) {
1258    SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt)
1259                               DAG.getNode(ISD::SHL, NVT, InH, ShAmt),
1260                               DAG.getNode(ISD::SRL, NVT, InL, NAmt));
1261    SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31
1262
1263    Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1264    Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2);
1265  } else {
1266    SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt)
1267                               DAG.getNode(ISD::SHL, NVT, InH, NAmt),
1268                               DAG.getNode(ISD::SRL, NVT, InL, ShAmt));
1269    bool isSign = Opc == ISD::SRA;
1270    SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt);  // T2 = InH >> ShAmt&31
1271
1272    SDOperand HiPart;
1273    if (isSign)
1274      HiPart = DAG.getNode(Opc, NVT, InH, DAG.getConstant(NVTBits-1, ShTy));
1275    else
1276      HiPart = DAG.getConstant(0, NVT);
1277    Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
1278    Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2);
1279  }
1280  return true;
1281}
1282
1283
1284
1285/// ExpandOp - Expand the specified SDOperand into its two component pieces
1286/// Lo&Hi.  Note that the Op MUST be an expanded type.  As a result of this, the
1287/// LegalizeNodes map is filled in for any results that are not expanded, the
1288/// ExpandedNodes map is filled in for any results that are expanded, and the
1289/// Lo/Hi values are returned.
1290void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
1291  MVT::ValueType VT = Op.getValueType();
1292  MVT::ValueType NVT = TLI.getTypeToTransformTo(VT);
1293  SDNode *Node = Op.Val;
1294  assert(getTypeAction(VT) == Expand && "Not an expanded type!");
1295  assert(MVT::isInteger(VT) && "Cannot expand FP values!");
1296  assert(MVT::isInteger(NVT) && NVT < VT &&
1297         "Cannot expand to FP value or to larger int value!");
1298
1299  // If there is more than one use of this, see if we already expanded it.
1300  // There is no use remembering values that only have a single use, as the map
1301  // entries will never be reused.
1302  if (!Node->hasOneUse()) {
1303    std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
1304      = ExpandedNodes.find(Op);
1305    if (I != ExpandedNodes.end()) {
1306      Lo = I->second.first;
1307      Hi = I->second.second;
1308      return;
1309    }
1310  }
1311
1312  // Expanding to multiple registers needs to perform an optimization step, and
1313  // is not careful to avoid operations the target does not support.  Make sure
1314  // that all generated operations are legalized in the next iteration.
1315  NeedsAnotherIteration = true;
1316  const char *LibCallName = 0;
1317
1318  switch (Node->getOpcode()) {
1319  default:
1320    std::cerr << "NODE: "; Node->dump(); std::cerr << "\n";
1321    assert(0 && "Do not know how to expand this operator!");
1322    abort();
1323  case ISD::Constant: {
1324    uint64_t Cst = cast<ConstantSDNode>(Node)->getValue();
1325    Lo = DAG.getConstant(Cst, NVT);
1326    Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT);
1327    break;
1328  }
1329
1330  case ISD::CopyFromReg: {
1331    unsigned Reg = cast<RegSDNode>(Node)->getReg();
1332    // Aggregate register values are always in consequtive pairs.
1333    Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0));
1334    Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1));
1335
1336    // Remember that we legalized the chain.
1337    AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
1338
1339    assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!");
1340    break;
1341  }
1342
1343  case ISD::LOAD: {
1344    SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
1345    SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
1346    Lo = DAG.getLoad(NVT, Ch, Ptr);
1347
1348    // Increment the pointer to the other half.
1349    unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
1350    Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
1351                      getIntPtrConstant(IncrementSize));
1352    Hi = DAG.getLoad(NVT, Ch, Ptr);
1353
1354    // Build a factor node to remember that this load is independent of the
1355    // other one.
1356    SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
1357                               Hi.getValue(1));
1358
1359    // Remember that we legalized the chain.
1360    AddLegalizedOperand(Op.getValue(1), TF);
1361    if (!TLI.isLittleEndian())
1362      std::swap(Lo, Hi);
1363    break;
1364  }
1365  case ISD::CALL: {
1366    SDOperand Chain  = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
1367    SDOperand Callee = LegalizeOp(Node->getOperand(1));  // Legalize the callee.
1368
1369    bool Changed = false;
1370    std::vector<SDOperand> Ops;
1371    for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) {
1372      Ops.push_back(LegalizeOp(Node->getOperand(i)));
1373      Changed |= Ops.back() != Node->getOperand(i);
1374    }
1375
1376    assert(Node->getNumValues() == 2 && Op.ResNo == 0 &&
1377           "Can only expand a call once so far, not i64 -> i16!");
1378
1379    std::vector<MVT::ValueType> RetTyVTs;
1380    RetTyVTs.reserve(3);
1381    RetTyVTs.push_back(NVT);
1382    RetTyVTs.push_back(NVT);
1383    RetTyVTs.push_back(MVT::Other);
1384    SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops);
1385    Lo = SDOperand(NC, 0);
1386    Hi = SDOperand(NC, 1);
1387
1388    // Insert the new chain mapping.
1389    AddLegalizedOperand(Op.getValue(1), Hi.getValue(2));
1390    break;
1391  }
1392  case ISD::AND:
1393  case ISD::OR:
1394  case ISD::XOR: {   // Simple logical operators -> two trivial pieces.
1395    SDOperand LL, LH, RL, RH;
1396    ExpandOp(Node->getOperand(0), LL, LH);
1397    ExpandOp(Node->getOperand(1), RL, RH);
1398    Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL);
1399    Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH);
1400    break;
1401  }
1402  case ISD::SELECT: {
1403    SDOperand C, LL, LH, RL, RH;
1404
1405    switch (getTypeAction(Node->getOperand(0).getValueType())) {
1406    case Expand: assert(0 && "It's impossible to expand bools");
1407    case Legal:
1408      C = LegalizeOp(Node->getOperand(0)); // Legalize the condition.
1409      break;
1410    case Promote:
1411      C = PromoteOp(Node->getOperand(0));  // Promote the condition.
1412      break;
1413    }
1414    ExpandOp(Node->getOperand(1), LL, LH);
1415    ExpandOp(Node->getOperand(2), RL, RH);
1416    Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL);
1417    Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH);
1418    break;
1419  }
1420  case ISD::SIGN_EXTEND: {
1421    // The low part is just a sign extension of the input (which degenerates to
1422    // a copy).
1423    Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
1424
1425    // The high part is obtained by SRA'ing all but one of the bits of the lo
1426    // part.
1427    unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
1428    Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, MVT::i8));
1429    break;
1430  }
1431  case ISD::ZERO_EXTEND:
1432    // The low part is just a zero extension of the input (which degenerates to
1433    // a copy).
1434    Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
1435
1436    // The high part is just a zero.
1437    Hi = DAG.getConstant(0, NVT);
1438    break;
1439
1440    // These operators cannot be expanded directly, emit them as calls to
1441    // library functions.
1442  case ISD::FP_TO_SINT:
1443    if (Node->getOperand(0).getValueType() == MVT::f32)
1444      LibCallName = "__fixsfdi";
1445    else
1446      LibCallName = "__fixdfdi";
1447    break;
1448  case ISD::FP_TO_UINT:
1449    if (Node->getOperand(0).getValueType() == MVT::f32)
1450      LibCallName = "__fixunssfdi";
1451    else
1452      LibCallName = "__fixunsdfdi";
1453    break;
1454
1455  case ISD::SHL:
1456    // If we can emit an efficient shift operation, do so now.
1457    if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1),
1458                    Lo, Hi))
1459      break;
1460    // Otherwise, emit a libcall.
1461    LibCallName = "__ashldi3";
1462    break;
1463
1464  case ISD::SRA:
1465    // If we can emit an efficient shift operation, do so now.
1466    if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1),
1467                    Lo, Hi))
1468      break;
1469    // Otherwise, emit a libcall.
1470    LibCallName = "__ashrdi3";
1471    break;
1472  case ISD::SRL:
1473    // If we can emit an efficient shift operation, do so now.
1474    if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1),
1475                    Lo, Hi))
1476      break;
1477    // Otherwise, emit a libcall.
1478    LibCallName = "__lshrdi3";
1479    break;
1480
1481  case ISD::ADD:
1482    ExpandAddSub(true, Node->getOperand(0), Node->getOperand(1), Lo, Hi);
1483    break;
1484  case ISD::SUB:
1485    ExpandAddSub(false, Node->getOperand(0), Node->getOperand(1), Lo, Hi);
1486    break;
1487  case ISD::MUL:  LibCallName = "__muldi3"; break;
1488  case ISD::SDIV: LibCallName = "__divdi3"; break;
1489  case ISD::UDIV: LibCallName = "__udivdi3"; break;
1490  case ISD::SREM: LibCallName = "__moddi3"; break;
1491  case ISD::UREM: LibCallName = "__umoddi3"; break;
1492  }
1493
1494  // Int2FP -> __floatdisf/__floatdidf
1495
1496  // If this is to be expanded into a libcall... do so now.
1497  if (LibCallName) {
1498    TargetLowering::ArgListTy Args;
1499    for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1500      Args.push_back(std::make_pair(Node->getOperand(i),
1501                 MVT::getTypeForValueType(Node->getOperand(i).getValueType())));
1502    SDOperand Callee = DAG.getExternalSymbol(LibCallName, TLI.getPointerTy());
1503
1504    // We don't care about token chains for libcalls.  We just use the entry
1505    // node as our input and ignore the output chain.  This allows us to place
1506    // calls wherever we need them to satisfy data dependences.
1507    SDOperand Result = TLI.LowerCallTo(DAG.getEntryNode(),
1508                           MVT::getTypeForValueType(Op.getValueType()), Callee,
1509                                       Args, DAG).first;
1510    ExpandOp(Result, Lo, Hi);
1511  }
1512
1513  // Remember in a map if the values will be reused later.
1514  if (!Node->hasOneUse()) {
1515    bool isNew = ExpandedNodes.insert(std::make_pair(Op,
1516                                            std::make_pair(Lo, Hi))).second;
1517    assert(isNew && "Value already expanded?!?");
1518  }
1519}
1520
1521
1522// SelectionDAG::Legalize - This is the entry point for the file.
1523//
1524void SelectionDAG::Legalize(TargetLowering &TLI) {
1525  /// run - This is the main entry point to this class.
1526  ///
1527  SelectionDAGLegalize(TLI, *this).Run();
1528}
1529
1530