LegalizeDAG.cpp revision d5d0f9bd20d9df07d6b4d41b7e8ed6d33b6a649d
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/CallingConv.h" 22#include "llvm/Constants.h" 23#include <iostream> 24#include <set> 25using namespace llvm; 26 27//===----------------------------------------------------------------------===// 28/// SelectionDAGLegalize - This takes an arbitrary SelectionDAG as input and 29/// hacks on it until the target machine can handle it. This involves 30/// eliminating value sizes the machine cannot handle (promoting small sizes to 31/// large sizes or splitting up large values into small values) as well as 32/// eliminating operations the machine cannot handle. 33/// 34/// This code also does a small amount of optimization and recognition of idioms 35/// as part of its processing. For example, if a target does not support a 36/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 37/// will attempt merge setcc and brc instructions into brcc's. 38/// 39namespace { 40class SelectionDAGLegalize { 41 TargetLowering &TLI; 42 SelectionDAG &DAG; 43 44 /// LegalizeAction - This enum indicates what action we should take for each 45 /// value type the can occur in the program. 46 enum LegalizeAction { 47 Legal, // The target natively supports this value type. 48 Promote, // This should be promoted to the next larger type. 49 Expand, // This integer type should be broken into smaller pieces. 50 }; 51 52 /// ValueTypeActions - This is a bitvector that contains two bits for each 53 /// value type, where the two bits correspond to the LegalizeAction enum. 54 /// This can be queried with "getTypeAction(VT)". 55 unsigned ValueTypeActions; 56 57 /// NeedsAnotherIteration - This is set when we expand a large integer 58 /// operation into smaller integer operations, but the smaller operations are 59 /// not set. This occurs only rarely in practice, for targets that don't have 60 /// 32-bit or larger integer registers. 61 bool NeedsAnotherIteration; 62 63 /// LegalizedNodes - For nodes that are of legal width, and that have more 64 /// than one use, this map indicates what regularized operand to use. This 65 /// allows us to avoid legalizing the same thing more than once. 66 std::map<SDOperand, SDOperand> LegalizedNodes; 67 68 /// PromotedNodes - For nodes that are below legal width, and that have more 69 /// than one use, this map indicates what promoted value to use. This allows 70 /// us to avoid promoting the same thing more than once. 71 std::map<SDOperand, SDOperand> PromotedNodes; 72 73 /// ExpandedNodes - For nodes that need to be expanded, and which have more 74 /// than one use, this map indicates which which operands are the expanded 75 /// version of the input. This allows us to avoid expanding the same node 76 /// more than once. 77 std::map<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; 78 79 void AddLegalizedOperand(SDOperand From, SDOperand To) { 80 bool isNew = LegalizedNodes.insert(std::make_pair(From, To)).second; 81 assert(isNew && "Got into the map somehow?"); 82 } 83 void AddPromotedOperand(SDOperand From, SDOperand To) { 84 bool isNew = PromotedNodes.insert(std::make_pair(From, To)).second; 85 assert(isNew && "Got into the map somehow?"); 86 } 87 88public: 89 90 SelectionDAGLegalize(SelectionDAG &DAG); 91 92 /// Run - While there is still lowering to do, perform a pass over the DAG. 93 /// Most regularization can be done in a single pass, but targets that require 94 /// large values to be split into registers multiple times (e.g. i64 -> 4x 95 /// i16) require iteration for these values (the first iteration will demote 96 /// to i32, the second will demote to i16). 97 void Run() { 98 do { 99 NeedsAnotherIteration = false; 100 LegalizeDAG(); 101 } while (NeedsAnotherIteration); 102 } 103 104 /// getTypeAction - Return how we should legalize values of this type, either 105 /// it is already legal or we need to expand it into multiple registers of 106 /// smaller integer type, or we need to promote it to a larger type. 107 LegalizeAction getTypeAction(MVT::ValueType VT) const { 108 return (LegalizeAction)((ValueTypeActions >> (2*VT)) & 3); 109 } 110 111 /// isTypeLegal - Return true if this type is legal on this target. 112 /// 113 bool isTypeLegal(MVT::ValueType VT) const { 114 return getTypeAction(VT) == Legal; 115 } 116 117private: 118 void LegalizeDAG(); 119 120 SDOperand LegalizeOp(SDOperand O); 121 void ExpandOp(SDOperand O, SDOperand &Lo, SDOperand &Hi); 122 SDOperand PromoteOp(SDOperand O); 123 124 SDOperand ExpandLibCall(const char *Name, SDNode *Node, 125 SDOperand &Hi); 126 SDOperand ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, 127 SDOperand Source); 128 129 SDOperand ExpandLegalUINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT); 130 SDOperand PromoteLegalINT_TO_FP(SDOperand LegalOp, MVT::ValueType DestVT, 131 bool isSigned); 132 SDOperand PromoteLegalFP_TO_INT(SDOperand LegalOp, MVT::ValueType DestVT, 133 bool isSigned); 134 135 bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt, 136 SDOperand &Lo, SDOperand &Hi); 137 void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt, 138 SDOperand &Lo, SDOperand &Hi); 139 void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS, 140 SDOperand &Lo, SDOperand &Hi); 141 142 void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain); 143 144 SDOperand getIntPtrConstant(uint64_t Val) { 145 return DAG.getConstant(Val, TLI.getPointerTy()); 146 } 147}; 148} 149 150 151SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag) 152 : TLI(dag.getTargetLoweringInfo()), DAG(dag), 153 ValueTypeActions(TLI.getValueTypeActions()) { 154 assert(MVT::LAST_VALUETYPE <= 16 && 155 "Too many value types for ValueTypeActions to hold!"); 156} 157 158/// ExpandLegalUINT_TO_FP - This function is responsible for legalizing a 159/// UINT_TO_FP operation of the specified operand when the target requests that 160/// we expand it. At this point, we know that the result and operand types are 161/// legal for the target. 162SDOperand SelectionDAGLegalize::ExpandLegalUINT_TO_FP(SDOperand Op0, 163 MVT::ValueType DestVT) { 164 SDOperand Tmp1 = DAG.getNode(ISD::SINT_TO_FP, DestVT, Op0); 165 166 SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Op0, 167 DAG.getConstant(0, Op0.getValueType()), 168 ISD::SETLT); 169 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4); 170 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(), 171 SignSet, Four, Zero); 172 173 // If the sign bit of the integer is set, the large number will be treated as 174 // a negative number. To counteract this, the dynamic code adds an offset 175 // depending on the data type. 176 uint64_t FF; 177 switch (Op0.getValueType()) { 178 default: assert(0 && "Unsupported integer type!"); 179 case MVT::i8 : FF = 0x43800000ULL; break; // 2^8 (as a float) 180 case MVT::i16: FF = 0x47800000ULL; break; // 2^16 (as a float) 181 case MVT::i32: FF = 0x4F800000ULL; break; // 2^32 (as a float) 182 case MVT::i64: FF = 0x5F800000ULL; break; // 2^64 (as a float) 183 } 184 if (TLI.isLittleEndian()) FF <<= 32; 185 static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF); 186 187 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 188 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor), 189 TLI.getPointerTy()); 190 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset); 191 SDOperand FudgeInReg; 192 if (DestVT == MVT::f32) 193 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, 194 DAG.getSrcValue(NULL)); 195 else { 196 assert(DestVT == MVT::f64 && "Unexpected conversion"); 197 FudgeInReg = LegalizeOp(DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, 198 DAG.getEntryNode(), CPIdx, 199 DAG.getSrcValue(NULL), MVT::f32)); 200 } 201 202 NeedsAnotherIteration = true; 203 return DAG.getNode(ISD::ADD, DestVT, Tmp1, FudgeInReg); 204} 205 206/// PromoteLegalINT_TO_FP - This function is responsible for legalizing a 207/// *INT_TO_FP operation of the specified operand when the target requests that 208/// we promote it. At this point, we know that the result and operand types are 209/// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP 210/// operation that takes a larger input. 211SDOperand SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDOperand LegalOp, 212 MVT::ValueType DestVT, 213 bool isSigned) { 214 // First step, figure out the appropriate *INT_TO_FP operation to use. 215 MVT::ValueType NewInTy = LegalOp.getValueType(); 216 217 unsigned OpToUse = 0; 218 219 // Scan for the appropriate larger type to use. 220 while (1) { 221 NewInTy = (MVT::ValueType)(NewInTy+1); 222 assert(MVT::isInteger(NewInTy) && "Ran out of possibilities!"); 223 224 // If the target supports SINT_TO_FP of this type, use it. 225 switch (TLI.getOperationAction(ISD::SINT_TO_FP, NewInTy)) { 226 default: break; 227 case TargetLowering::Legal: 228 if (!TLI.hasNativeSupportFor(NewInTy)) 229 break; // Can't use this datatype. 230 // FALL THROUGH. 231 case TargetLowering::Custom: 232 OpToUse = ISD::SINT_TO_FP; 233 break; 234 } 235 if (OpToUse) break; 236 if (isSigned) continue; 237 238 // If the target supports UINT_TO_FP of this type, use it. 239 switch (TLI.getOperationAction(ISD::UINT_TO_FP, NewInTy)) { 240 default: break; 241 case TargetLowering::Legal: 242 if (!TLI.hasNativeSupportFor(NewInTy)) 243 break; // Can't use this datatype. 244 // FALL THROUGH. 245 case TargetLowering::Custom: 246 OpToUse = ISD::UINT_TO_FP; 247 break; 248 } 249 if (OpToUse) break; 250 251 // Otherwise, try a larger type. 252 } 253 254 // Make sure to legalize any nodes we create here in the next pass. 255 NeedsAnotherIteration = true; 256 257 // Okay, we found the operation and type to use. Zero extend our input to the 258 // desired type then run the operation on it. 259 return DAG.getNode(OpToUse, DestVT, 260 DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND, 261 NewInTy, LegalOp)); 262} 263 264/// PromoteLegalFP_TO_INT - This function is responsible for legalizing a 265/// FP_TO_*INT operation of the specified operand when the target requests that 266/// we promote it. At this point, we know that the result and operand types are 267/// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT 268/// operation that returns a larger result. 269SDOperand SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDOperand LegalOp, 270 MVT::ValueType DestVT, 271 bool isSigned) { 272 // First step, figure out the appropriate FP_TO*INT operation to use. 273 MVT::ValueType NewOutTy = DestVT; 274 275 unsigned OpToUse = 0; 276 277 // Scan for the appropriate larger type to use. 278 while (1) { 279 NewOutTy = (MVT::ValueType)(NewOutTy+1); 280 assert(MVT::isInteger(NewOutTy) && "Ran out of possibilities!"); 281 282 // If the target supports FP_TO_SINT returning this type, use it. 283 switch (TLI.getOperationAction(ISD::FP_TO_SINT, NewOutTy)) { 284 default: break; 285 case TargetLowering::Legal: 286 if (!TLI.hasNativeSupportFor(NewOutTy)) 287 break; // Can't use this datatype. 288 // FALL THROUGH. 289 case TargetLowering::Custom: 290 OpToUse = ISD::FP_TO_SINT; 291 break; 292 } 293 if (OpToUse) break; 294 295 // If the target supports FP_TO_UINT of this type, use it. 296 switch (TLI.getOperationAction(ISD::FP_TO_UINT, NewOutTy)) { 297 default: break; 298 case TargetLowering::Legal: 299 if (!TLI.hasNativeSupportFor(NewOutTy)) 300 break; // Can't use this datatype. 301 // FALL THROUGH. 302 case TargetLowering::Custom: 303 OpToUse = ISD::FP_TO_UINT; 304 break; 305 } 306 if (OpToUse) break; 307 308 // Otherwise, try a larger type. 309 } 310 311 // Make sure to legalize any nodes we create here in the next pass. 312 NeedsAnotherIteration = true; 313 314 // Okay, we found the operation and type to use. Truncate the result of the 315 // extended FP_TO_*INT operation to the desired size. 316 return DAG.getNode(ISD::TRUNCATE, DestVT, 317 DAG.getNode(OpToUse, NewOutTy, LegalOp)); 318} 319 320 321void SelectionDAGLegalize::LegalizeDAG() { 322 SDOperand OldRoot = DAG.getRoot(); 323 SDOperand NewRoot = LegalizeOp(OldRoot); 324 DAG.setRoot(NewRoot); 325 326 ExpandedNodes.clear(); 327 LegalizedNodes.clear(); 328 PromotedNodes.clear(); 329 330 // Remove dead nodes now. 331 DAG.RemoveDeadNodes(OldRoot.Val); 332} 333 334SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { 335 assert(getTypeAction(Op.getValueType()) == Legal && 336 "Caller should expand or promote operands that are not legal!"); 337 SDNode *Node = Op.Val; 338 339 // If this operation defines any values that cannot be represented in a 340 // register on this target, make sure to expand or promote them. 341 if (Node->getNumValues() > 1) { 342 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 343 switch (getTypeAction(Node->getValueType(i))) { 344 case Legal: break; // Nothing to do. 345 case Expand: { 346 SDOperand T1, T2; 347 ExpandOp(Op.getValue(i), T1, T2); 348 assert(LegalizedNodes.count(Op) && 349 "Expansion didn't add legal operands!"); 350 return LegalizedNodes[Op]; 351 } 352 case Promote: 353 PromoteOp(Op.getValue(i)); 354 assert(LegalizedNodes.count(Op) && 355 "Expansion didn't add legal operands!"); 356 return LegalizedNodes[Op]; 357 } 358 } 359 360 // Note that LegalizeOp may be reentered even from single-use nodes, which 361 // means that we always must cache transformed nodes. 362 std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op); 363 if (I != LegalizedNodes.end()) return I->second; 364 365 SDOperand Tmp1, Tmp2, Tmp3, Tmp4; 366 367 SDOperand Result = Op; 368 369 switch (Node->getOpcode()) { 370 default: 371 if (Node->getOpcode() >= ISD::BUILTIN_OP_END) { 372 // If this is a target node, legalize it by legalizing the operands then 373 // passing it through. 374 std::vector<SDOperand> Ops; 375 bool Changed = false; 376 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 377 Ops.push_back(LegalizeOp(Node->getOperand(i))); 378 Changed = Changed || Node->getOperand(i) != Ops.back(); 379 } 380 if (Changed) 381 if (Node->getNumValues() == 1) 382 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops); 383 else { 384 std::vector<MVT::ValueType> VTs(Node->value_begin(), 385 Node->value_end()); 386 Result = DAG.getNode(Node->getOpcode(), VTs, Ops); 387 } 388 389 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 390 AddLegalizedOperand(Op.getValue(i), Result.getValue(i)); 391 return Result.getValue(Op.ResNo); 392 } 393 // Otherwise this is an unhandled builtin node. splat. 394 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 395 assert(0 && "Do not know how to legalize this operator!"); 396 abort(); 397 case ISD::EntryToken: 398 case ISD::FrameIndex: 399 case ISD::GlobalAddress: 400 case ISD::ExternalSymbol: 401 case ISD::ConstantPool: // Nothing to do. 402 assert(getTypeAction(Node->getValueType(0)) == Legal && 403 "This must be legal!"); 404 break; 405 case ISD::CopyFromReg: 406 Tmp1 = LegalizeOp(Node->getOperand(0)); 407 if (Tmp1 != Node->getOperand(0)) 408 Result = DAG.getCopyFromReg(Tmp1, 409 cast<RegisterSDNode>(Node->getOperand(1))->getReg(), 410 Node->getValueType(0)); 411 else 412 Result = Op.getValue(0); 413 414 // Since CopyFromReg produces two values, make sure to remember that we 415 // legalized both of them. 416 AddLegalizedOperand(Op.getValue(0), Result); 417 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 418 return Result.getValue(Op.ResNo); 419 case ISD::ImplicitDef: 420 Tmp1 = LegalizeOp(Node->getOperand(0)); 421 if (Tmp1 != Node->getOperand(0)) 422 Result = DAG.getNode(ISD::ImplicitDef, MVT::Other, 423 Tmp1, Node->getOperand(1)); 424 break; 425 case ISD::UNDEF: { 426 MVT::ValueType VT = Op.getValueType(); 427 switch (TLI.getOperationAction(ISD::UNDEF, VT)) { 428 default: assert(0 && "This action is not supported yet!"); 429 case TargetLowering::Expand: 430 case TargetLowering::Promote: 431 if (MVT::isInteger(VT)) 432 Result = DAG.getConstant(0, VT); 433 else if (MVT::isFloatingPoint(VT)) 434 Result = DAG.getConstantFP(0, VT); 435 else 436 assert(0 && "Unknown value type!"); 437 break; 438 case TargetLowering::Legal: 439 break; 440 } 441 break; 442 } 443 case ISD::Constant: 444 // We know we don't need to expand constants here, constants only have one 445 // value and we check that it is fine above. 446 447 // FIXME: Maybe we should handle things like targets that don't support full 448 // 32-bit immediates? 449 break; 450 case ISD::ConstantFP: { 451 // Spill FP immediates to the constant pool if the target cannot directly 452 // codegen them. Targets often have some immediate values that can be 453 // efficiently generated into an FP register without a load. We explicitly 454 // leave these constants as ConstantFP nodes for the target to deal with. 455 456 ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node); 457 458 // Check to see if this FP immediate is already legal. 459 bool isLegal = false; 460 for (TargetLowering::legal_fpimm_iterator I = TLI.legal_fpimm_begin(), 461 E = TLI.legal_fpimm_end(); I != E; ++I) 462 if (CFP->isExactlyValue(*I)) { 463 isLegal = true; 464 break; 465 } 466 467 if (!isLegal) { 468 // Otherwise we need to spill the constant to memory. 469 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 470 471 bool Extend = false; 472 473 // If a FP immediate is precise when represented as a float, we put it 474 // into the constant pool as a float, even if it's is statically typed 475 // as a double. 476 MVT::ValueType VT = CFP->getValueType(0); 477 bool isDouble = VT == MVT::f64; 478 ConstantFP *LLVMC = ConstantFP::get(isDouble ? Type::DoubleTy : 479 Type::FloatTy, CFP->getValue()); 480 if (isDouble && CFP->isExactlyValue((float)CFP->getValue()) && 481 // Only do this if the target has a native EXTLOAD instruction from 482 // f32. 483 TLI.getOperationAction(ISD::EXTLOAD, 484 MVT::f32) == TargetLowering::Legal) { 485 LLVMC = cast<ConstantFP>(ConstantExpr::getCast(LLVMC, Type::FloatTy)); 486 VT = MVT::f32; 487 Extend = true; 488 } 489 490 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC), 491 TLI.getPointerTy()); 492 if (Extend) { 493 Result = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), 494 CPIdx, DAG.getSrcValue(NULL), MVT::f32); 495 } else { 496 Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx, 497 DAG.getSrcValue(NULL)); 498 } 499 } 500 break; 501 } 502 case ISD::TokenFactor: { 503 std::vector<SDOperand> Ops; 504 bool Changed = false; 505 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 506 SDOperand Op = Node->getOperand(i); 507 // Fold single-use TokenFactor nodes into this token factor as we go. 508 // FIXME: This is something that the DAGCombiner should do!! 509 if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) { 510 Changed = true; 511 for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j) 512 Ops.push_back(LegalizeOp(Op.getOperand(j))); 513 } else { 514 Ops.push_back(LegalizeOp(Op)); // Legalize the operands 515 Changed |= Ops[i] != Op; 516 } 517 } 518 if (Changed) 519 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Ops); 520 break; 521 } 522 523 case ISD::CALLSEQ_START: 524 case ISD::CALLSEQ_END: 525 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 526 // Do not try to legalize the target-specific arguments (#1+) 527 Tmp2 = Node->getOperand(0); 528 if (Tmp1 != Tmp2) { 529 Node->setAdjCallChain(Tmp1); 530 531 // If moving the operand from pointing to Tmp2 dropped its use count to 1, 532 // this will cause the maps used to memoize results to get confused. 533 // Create and add a dummy use, just to increase its use count. This will 534 // be removed at the end of legalize when dead nodes are removed. 535 if (Tmp2.Val->hasOneUse()) 536 DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp2, 537 DAG.getConstant(0, MVT::i32)); 538 } 539 // Note that we do not create new CALLSEQ_DOWN/UP nodes here. These 540 // nodes are treated specially and are mutated in place. This makes the dag 541 // legalization process more efficient and also makes libcall insertion 542 // easier. 543 break; 544 case ISD::DYNAMIC_STACKALLOC: 545 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 546 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the size. 547 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the alignment. 548 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 549 Tmp3 != Node->getOperand(2)) { 550 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 551 std::vector<SDOperand> Ops; 552 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 553 Result = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops); 554 } else 555 Result = Op.getValue(0); 556 557 // Since this op produces two values, make sure to remember that we 558 // legalized both of them. 559 AddLegalizedOperand(SDOperand(Node, 0), Result); 560 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 561 return Result.getValue(Op.ResNo); 562 563 case ISD::TAILCALL: 564 case ISD::CALL: { 565 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 566 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 567 568 bool Changed = false; 569 std::vector<SDOperand> Ops; 570 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 571 Ops.push_back(LegalizeOp(Node->getOperand(i))); 572 Changed |= Ops.back() != Node->getOperand(i); 573 } 574 575 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Changed) { 576 std::vector<MVT::ValueType> RetTyVTs; 577 RetTyVTs.reserve(Node->getNumValues()); 578 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 579 RetTyVTs.push_back(Node->getValueType(i)); 580 Result = SDOperand(DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops, 581 Node->getOpcode() == ISD::TAILCALL), 0); 582 } else { 583 Result = Result.getValue(0); 584 } 585 // Since calls produce multiple values, make sure to remember that we 586 // legalized all of them. 587 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 588 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 589 return Result.getValue(Op.ResNo); 590 } 591 case ISD::BR: 592 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 593 if (Tmp1 != Node->getOperand(0)) 594 Result = DAG.getNode(ISD::BR, MVT::Other, Tmp1, Node->getOperand(1)); 595 break; 596 597 case ISD::BRCOND: 598 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 599 600 switch (getTypeAction(Node->getOperand(1).getValueType())) { 601 case Expand: assert(0 && "It's impossible to expand bools"); 602 case Legal: 603 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 604 break; 605 case Promote: 606 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 607 break; 608 } 609 610 switch (TLI.getOperationAction(ISD::BRCOND, MVT::Other)) { 611 default: assert(0 && "This action is not supported yet!"); 612 case TargetLowering::Expand: 613 // Expand brcond's setcc into its constituent parts and create a BR_CC 614 // Node. 615 if (Tmp2.getOpcode() == ISD::SETCC) { 616 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2), 617 Tmp2.getOperand(0), Tmp2.getOperand(1), 618 Node->getOperand(2)); 619 } else { 620 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, 621 DAG.getCondCode(ISD::SETNE), Tmp2, 622 DAG.getConstant(0, Tmp2.getValueType()), 623 Node->getOperand(2)); 624 } 625 break; 626 case TargetLowering::Legal: 627 // Basic block destination (Op#2) is always legal. 628 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 629 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 630 Node->getOperand(2)); 631 break; 632 } 633 break; 634 case ISD::BR_CC: 635 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 636 637 if (getTypeAction(Node->getOperand(2).getValueType()) == Legal) { 638 Tmp2 = LegalizeOp(Node->getOperand(2)); // LHS 639 Tmp3 = LegalizeOp(Node->getOperand(3)); // RHS 640 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2) || 641 Tmp3 != Node->getOperand(3)) { 642 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Node->getOperand(1), 643 Tmp2, Tmp3, Node->getOperand(4)); 644 } 645 break; 646 } else { 647 Tmp2 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), 648 Node->getOperand(2), // LHS 649 Node->getOperand(3), // RHS 650 Node->getOperand(1))); 651 // If we get a SETCC back from legalizing the SETCC node we just 652 // created, then use its LHS, RHS, and CC directly in creating a new 653 // node. Otherwise, select between the true and false value based on 654 // comparing the result of the legalized with zero. 655 if (Tmp2.getOpcode() == ISD::SETCC) { 656 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, Tmp2.getOperand(2), 657 Tmp2.getOperand(0), Tmp2.getOperand(1), 658 Node->getOperand(4)); 659 } else { 660 Result = DAG.getNode(ISD::BR_CC, MVT::Other, Tmp1, 661 DAG.getCondCode(ISD::SETNE), 662 Tmp2, DAG.getConstant(0, Tmp2.getValueType()), 663 Node->getOperand(4)); 664 } 665 } 666 break; 667 case ISD::BRCONDTWOWAY: 668 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 669 switch (getTypeAction(Node->getOperand(1).getValueType())) { 670 case Expand: assert(0 && "It's impossible to expand bools"); 671 case Legal: 672 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition. 673 break; 674 case Promote: 675 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the condition. 676 break; 677 } 678 // If this target does not support BRCONDTWOWAY, lower it to a BRCOND/BR 679 // pair. 680 switch (TLI.getOperationAction(ISD::BRCONDTWOWAY, MVT::Other)) { 681 case TargetLowering::Promote: 682 default: assert(0 && "This action is not supported yet!"); 683 case TargetLowering::Legal: 684 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 685 std::vector<SDOperand> Ops; 686 Ops.push_back(Tmp1); 687 Ops.push_back(Tmp2); 688 Ops.push_back(Node->getOperand(2)); 689 Ops.push_back(Node->getOperand(3)); 690 Result = DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops); 691 } 692 break; 693 case TargetLowering::Expand: 694 // If BRTWOWAY_CC is legal for this target, then simply expand this node 695 // to that. Otherwise, skip BRTWOWAY_CC and expand directly to a 696 // BRCOND/BR pair. 697 if (TLI.getOperationAction(ISD::BRTWOWAY_CC, MVT::Other) == 698 TargetLowering::Legal) { 699 if (Tmp2.getOpcode() == ISD::SETCC) { 700 Result = DAG.getBR2Way_CC(Tmp1, Tmp2.getOperand(2), 701 Tmp2.getOperand(0), Tmp2.getOperand(1), 702 Node->getOperand(2), Node->getOperand(3)); 703 } else { 704 Result = DAG.getBR2Way_CC(Tmp1, DAG.getCondCode(ISD::SETNE), Tmp2, 705 DAG.getConstant(0, Tmp2.getValueType()), 706 Node->getOperand(2), Node->getOperand(3)); 707 } 708 } else { 709 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 710 Node->getOperand(2)); 711 Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(3)); 712 } 713 break; 714 } 715 break; 716 case ISD::BRTWOWAY_CC: 717 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 718 if (getTypeAction(Node->getOperand(2).getValueType()) == Legal) { 719 Tmp2 = LegalizeOp(Node->getOperand(2)); // LHS 720 Tmp3 = LegalizeOp(Node->getOperand(3)); // RHS 721 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2) || 722 Tmp3 != Node->getOperand(3)) { 723 Result = DAG.getBR2Way_CC(Tmp1, Node->getOperand(1), Tmp2, Tmp3, 724 Node->getOperand(4), Node->getOperand(5)); 725 } 726 break; 727 } else { 728 Tmp2 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), 729 Node->getOperand(2), // LHS 730 Node->getOperand(3), // RHS 731 Node->getOperand(1))); 732 // If this target does not support BRTWOWAY_CC, lower it to a BRCOND/BR 733 // pair. 734 switch (TLI.getOperationAction(ISD::BRTWOWAY_CC, MVT::Other)) { 735 default: assert(0 && "This action is not supported yet!"); 736 case TargetLowering::Legal: 737 // If we get a SETCC back from legalizing the SETCC node we just 738 // created, then use its LHS, RHS, and CC directly in creating a new 739 // node. Otherwise, select between the true and false value based on 740 // comparing the result of the legalized with zero. 741 if (Tmp2.getOpcode() == ISD::SETCC) { 742 Result = DAG.getBR2Way_CC(Tmp1, Tmp2.getOperand(2), 743 Tmp2.getOperand(0), Tmp2.getOperand(1), 744 Node->getOperand(4), Node->getOperand(5)); 745 } else { 746 Result = DAG.getBR2Way_CC(Tmp1, DAG.getCondCode(ISD::SETNE), Tmp2, 747 DAG.getConstant(0, Tmp2.getValueType()), 748 Node->getOperand(4), Node->getOperand(5)); 749 } 750 break; 751 case TargetLowering::Expand: 752 Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2, 753 Node->getOperand(4)); 754 Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(5)); 755 break; 756 } 757 } 758 break; 759 case ISD::LOAD: 760 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 761 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 762 763 if (Tmp1 != Node->getOperand(0) || 764 Tmp2 != Node->getOperand(1)) 765 Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2, 766 Node->getOperand(2)); 767 else 768 Result = SDOperand(Node, 0); 769 770 // Since loads produce two values, make sure to remember that we legalized 771 // both of them. 772 AddLegalizedOperand(SDOperand(Node, 0), Result); 773 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 774 return Result.getValue(Op.ResNo); 775 776 case ISD::EXTLOAD: 777 case ISD::SEXTLOAD: 778 case ISD::ZEXTLOAD: { 779 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 780 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 781 782 MVT::ValueType SrcVT = cast<VTSDNode>(Node->getOperand(3))->getVT(); 783 switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) { 784 default: assert(0 && "This action is not supported yet!"); 785 case TargetLowering::Promote: 786 assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!"); 787 Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0), 788 Tmp1, Tmp2, Node->getOperand(2), MVT::i8); 789 // Since loads produce two values, make sure to remember that we legalized 790 // both of them. 791 AddLegalizedOperand(SDOperand(Node, 0), Result); 792 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 793 return Result.getValue(Op.ResNo); 794 795 case TargetLowering::Legal: 796 if (Tmp1 != Node->getOperand(0) || 797 Tmp2 != Node->getOperand(1)) 798 Result = DAG.getExtLoad(Node->getOpcode(), Node->getValueType(0), 799 Tmp1, Tmp2, Node->getOperand(2), SrcVT); 800 else 801 Result = SDOperand(Node, 0); 802 803 // Since loads produce two values, make sure to remember that we legalized 804 // both of them. 805 AddLegalizedOperand(SDOperand(Node, 0), Result); 806 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 807 return Result.getValue(Op.ResNo); 808 case TargetLowering::Expand: 809 //f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND 810 if (SrcVT == MVT::f32 && Node->getValueType(0) == MVT::f64) { 811 SDOperand Load = DAG.getLoad(SrcVT, Tmp1, Tmp2, Node->getOperand(2)); 812 Result = DAG.getNode(ISD::FP_EXTEND, Node->getValueType(0), Load); 813 if (Op.ResNo) 814 return Load.getValue(1); 815 return Result; 816 } 817 assert(Node->getOpcode() != ISD::EXTLOAD && 818 "EXTLOAD should always be supported!"); 819 // Turn the unsupported load into an EXTLOAD followed by an explicit 820 // zero/sign extend inreg. 821 Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0), 822 Tmp1, Tmp2, Node->getOperand(2), SrcVT); 823 SDOperand ValRes; 824 if (Node->getOpcode() == ISD::SEXTLOAD) 825 ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 826 Result, DAG.getValueType(SrcVT)); 827 else 828 ValRes = DAG.getZeroExtendInReg(Result, SrcVT); 829 AddLegalizedOperand(SDOperand(Node, 0), ValRes); 830 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 831 if (Op.ResNo) 832 return Result.getValue(1); 833 return ValRes; 834 } 835 assert(0 && "Unreachable"); 836 } 837 case ISD::EXTRACT_ELEMENT: 838 // Get both the low and high parts. 839 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 840 if (cast<ConstantSDNode>(Node->getOperand(1))->getValue()) 841 Result = Tmp2; // 1 -> Hi 842 else 843 Result = Tmp1; // 0 -> Lo 844 break; 845 846 case ISD::CopyToReg: 847 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 848 849 assert(getTypeAction(Node->getOperand(2).getValueType()) == Legal && 850 "Register type must be legal!"); 851 // Legalize the incoming value (must be legal). 852 Tmp2 = LegalizeOp(Node->getOperand(2)); 853 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2)) 854 Result = DAG.getNode(ISD::CopyToReg, MVT::Other, Tmp1, 855 Node->getOperand(1), Tmp2); 856 break; 857 858 case ISD::RET: 859 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 860 switch (Node->getNumOperands()) { 861 case 2: // ret val 862 switch (getTypeAction(Node->getOperand(1).getValueType())) { 863 case Legal: 864 Tmp2 = LegalizeOp(Node->getOperand(1)); 865 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 866 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 867 break; 868 case Expand: { 869 SDOperand Lo, Hi; 870 ExpandOp(Node->getOperand(1), Lo, Hi); 871 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); 872 break; 873 } 874 case Promote: 875 Tmp2 = PromoteOp(Node->getOperand(1)); 876 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Tmp2); 877 break; 878 } 879 break; 880 case 1: // ret void 881 if (Tmp1 != Node->getOperand(0)) 882 Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1); 883 break; 884 default: { // ret <values> 885 std::vector<SDOperand> NewValues; 886 NewValues.push_back(Tmp1); 887 for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) 888 switch (getTypeAction(Node->getOperand(i).getValueType())) { 889 case Legal: 890 NewValues.push_back(LegalizeOp(Node->getOperand(i))); 891 break; 892 case Expand: { 893 SDOperand Lo, Hi; 894 ExpandOp(Node->getOperand(i), Lo, Hi); 895 NewValues.push_back(Lo); 896 NewValues.push_back(Hi); 897 break; 898 } 899 case Promote: 900 assert(0 && "Can't promote multiple return value yet!"); 901 } 902 Result = DAG.getNode(ISD::RET, MVT::Other, NewValues); 903 break; 904 } 905 } 906 break; 907 case ISD::STORE: 908 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 909 Tmp2 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 910 911 // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr' 912 if (ConstantFPSDNode *CFP =dyn_cast<ConstantFPSDNode>(Node->getOperand(1))){ 913 if (CFP->getValueType(0) == MVT::f32) { 914 union { 915 unsigned I; 916 float F; 917 } V; 918 V.F = CFP->getValue(); 919 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 920 DAG.getConstant(V.I, MVT::i32), Tmp2, 921 Node->getOperand(3)); 922 } else { 923 assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); 924 union { 925 uint64_t I; 926 double F; 927 } V; 928 V.F = CFP->getValue(); 929 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 930 DAG.getConstant(V.I, MVT::i64), Tmp2, 931 Node->getOperand(3)); 932 } 933 Node = Result.Val; 934 } 935 936 switch (getTypeAction(Node->getOperand(1).getValueType())) { 937 case Legal: { 938 SDOperand Val = LegalizeOp(Node->getOperand(1)); 939 if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || 940 Tmp2 != Node->getOperand(2)) 941 Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2, 942 Node->getOperand(3)); 943 break; 944 } 945 case Promote: 946 // Truncate the value and store the result. 947 Tmp3 = PromoteOp(Node->getOperand(1)); 948 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2, 949 Node->getOperand(3), 950 DAG.getValueType(Node->getOperand(1).getValueType())); 951 break; 952 953 case Expand: 954 SDOperand Lo, Hi; 955 ExpandOp(Node->getOperand(1), Lo, Hi); 956 957 if (!TLI.isLittleEndian()) 958 std::swap(Lo, Hi); 959 960 Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2, 961 Node->getOperand(3)); 962 unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8; 963 Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, 964 getIntPtrConstant(IncrementSize)); 965 assert(isTypeLegal(Tmp2.getValueType()) && 966 "Pointers must be legal!"); 967 //Again, claiming both parts of the store came form the same Instr 968 Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2, 969 Node->getOperand(3)); 970 Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 971 break; 972 } 973 break; 974 case ISD::PCMARKER: 975 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 976 if (Tmp1 != Node->getOperand(0)) 977 Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1)); 978 break; 979 case ISD::TRUNCSTORE: 980 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 981 Tmp3 = LegalizeOp(Node->getOperand(2)); // Legalize the pointer. 982 983 switch (getTypeAction(Node->getOperand(1).getValueType())) { 984 case Legal: 985 Tmp2 = LegalizeOp(Node->getOperand(1)); 986 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 987 Tmp3 != Node->getOperand(2)) 988 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3, 989 Node->getOperand(3), Node->getOperand(4)); 990 break; 991 case Promote: 992 case Expand: 993 assert(0 && "Cannot handle illegal TRUNCSTORE yet!"); 994 } 995 break; 996 case ISD::SELECT: 997 switch (getTypeAction(Node->getOperand(0).getValueType())) { 998 case Expand: assert(0 && "It's impossible to expand bools"); 999 case Legal: 1000 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 1001 break; 1002 case Promote: 1003 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 1004 break; 1005 } 1006 Tmp2 = LegalizeOp(Node->getOperand(1)); // TrueVal 1007 Tmp3 = LegalizeOp(Node->getOperand(2)); // FalseVal 1008 1009 switch (TLI.getOperationAction(Node->getOpcode(), Tmp2.getValueType())) { 1010 default: assert(0 && "This action is not supported yet!"); 1011 case TargetLowering::Expand: 1012 if (Tmp1.getOpcode() == ISD::SETCC) { 1013 Result = DAG.getSelectCC(Tmp1.getOperand(0), Tmp1.getOperand(1), 1014 Tmp2, Tmp3, 1015 cast<CondCodeSDNode>(Tmp1.getOperand(2))->get()); 1016 } else { 1017 Result = DAG.getSelectCC(Tmp1, 1018 DAG.getConstant(0, Tmp1.getValueType()), 1019 Tmp2, Tmp3, ISD::SETNE); 1020 } 1021 break; 1022 case TargetLowering::Legal: 1023 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1024 Tmp3 != Node->getOperand(2)) 1025 Result = DAG.getNode(ISD::SELECT, Node->getValueType(0), 1026 Tmp1, Tmp2, Tmp3); 1027 break; 1028 case TargetLowering::Promote: { 1029 MVT::ValueType NVT = 1030 TLI.getTypeToPromoteTo(ISD::SELECT, Tmp2.getValueType()); 1031 unsigned ExtOp, TruncOp; 1032 if (MVT::isInteger(Tmp2.getValueType())) { 1033 ExtOp = ISD::ZERO_EXTEND; 1034 TruncOp = ISD::TRUNCATE; 1035 } else { 1036 ExtOp = ISD::FP_EXTEND; 1037 TruncOp = ISD::FP_ROUND; 1038 } 1039 // Promote each of the values to the new type. 1040 Tmp2 = DAG.getNode(ExtOp, NVT, Tmp2); 1041 Tmp3 = DAG.getNode(ExtOp, NVT, Tmp3); 1042 // Perform the larger operation, then round down. 1043 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2,Tmp3); 1044 Result = DAG.getNode(TruncOp, Node->getValueType(0), Result); 1045 break; 1046 } 1047 } 1048 break; 1049 case ISD::SELECT_CC: 1050 Tmp3 = LegalizeOp(Node->getOperand(2)); // True 1051 Tmp4 = LegalizeOp(Node->getOperand(3)); // False 1052 1053 if (getTypeAction(Node->getOperand(0).getValueType()) == Legal) { 1054 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1055 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 1056 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1057 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3)) { 1058 Result = DAG.getNode(ISD::SELECT_CC, Node->getValueType(0), Tmp1, Tmp2, 1059 Tmp3, Tmp4, Node->getOperand(4)); 1060 } 1061 break; 1062 } else { 1063 Tmp1 = LegalizeOp(DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), 1064 Node->getOperand(0), // LHS 1065 Node->getOperand(1), // RHS 1066 Node->getOperand(4))); 1067 // If we get a SETCC back from legalizing the SETCC node we just 1068 // created, then use its LHS, RHS, and CC directly in creating a new 1069 // node. Otherwise, select between the true and false value based on 1070 // comparing the result of the legalized with zero. 1071 if (Tmp1.getOpcode() == ISD::SETCC) { 1072 Result = DAG.getNode(ISD::SELECT_CC, Tmp3.getValueType(), 1073 Tmp1.getOperand(0), Tmp1.getOperand(1), 1074 Tmp3, Tmp4, Tmp1.getOperand(2)); 1075 } else { 1076 Result = DAG.getSelectCC(Tmp1, 1077 DAG.getConstant(0, Tmp1.getValueType()), 1078 Tmp3, Tmp4, ISD::SETNE); 1079 } 1080 } 1081 break; 1082 case ISD::SETCC: 1083 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1084 case Legal: 1085 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1086 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 1087 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) 1088 Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, Tmp2, 1089 Node->getOperand(2)); 1090 break; 1091 case Promote: 1092 Tmp1 = PromoteOp(Node->getOperand(0)); // LHS 1093 Tmp2 = PromoteOp(Node->getOperand(1)); // RHS 1094 1095 // If this is an FP compare, the operands have already been extended. 1096 if (MVT::isInteger(Node->getOperand(0).getValueType())) { 1097 MVT::ValueType VT = Node->getOperand(0).getValueType(); 1098 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1099 1100 // Otherwise, we have to insert explicit sign or zero extends. Note 1101 // that we could insert sign extends for ALL conditions, but zero extend 1102 // is cheaper on many machines (an AND instead of two shifts), so prefer 1103 // it. 1104 switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) { 1105 default: assert(0 && "Unknown integer comparison!"); 1106 case ISD::SETEQ: 1107 case ISD::SETNE: 1108 case ISD::SETUGE: 1109 case ISD::SETUGT: 1110 case ISD::SETULE: 1111 case ISD::SETULT: 1112 // ALL of these operations will work if we either sign or zero extend 1113 // the operands (including the unsigned comparisons!). Zero extend is 1114 // usually a simpler/cheaper operation, so prefer it. 1115 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 1116 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT); 1117 break; 1118 case ISD::SETGE: 1119 case ISD::SETGT: 1120 case ISD::SETLT: 1121 case ISD::SETLE: 1122 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, 1123 DAG.getValueType(VT)); 1124 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, 1125 DAG.getValueType(VT)); 1126 break; 1127 } 1128 1129 } 1130 Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, Tmp2, 1131 Node->getOperand(2)); 1132 break; 1133 case Expand: 1134 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 1135 ExpandOp(Node->getOperand(0), LHSLo, LHSHi); 1136 ExpandOp(Node->getOperand(1), RHSLo, RHSHi); 1137 switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) { 1138 case ISD::SETEQ: 1139 case ISD::SETNE: 1140 if (RHSLo == RHSHi) 1141 if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) 1142 if (RHSCST->isAllOnesValue()) { 1143 // Comparison to -1. 1144 Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi); 1145 Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, 1146 RHSLo, Node->getOperand(2)); 1147 break; 1148 } 1149 1150 Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 1151 Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 1152 Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); 1153 Result = DAG.getNode(ISD::SETCC, Node->getValueType(0), Tmp1, 1154 DAG.getConstant(0, Tmp1.getValueType()), 1155 Node->getOperand(2)); 1156 break; 1157 default: 1158 // If this is a comparison of the sign bit, just look at the top part. 1159 // X > -1, x < 0 1160 if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(Node->getOperand(1))) 1161 if ((cast<CondCodeSDNode>(Node->getOperand(2))->get() == ISD::SETLT && 1162 CST->getValue() == 0) || // X < 0 1163 (cast<CondCodeSDNode>(Node->getOperand(2))->get() == ISD::SETGT && 1164 (CST->isAllOnesValue()))) // X > -1 1165 return DAG.getNode(ISD::SETCC, Node->getValueType(0), LHSHi, RHSHi, 1166 Node->getOperand(2)); 1167 1168 // FIXME: This generated code sucks. 1169 ISD::CondCode LowCC; 1170 switch (cast<CondCodeSDNode>(Node->getOperand(2))->get()) { 1171 default: assert(0 && "Unknown integer setcc!"); 1172 case ISD::SETLT: 1173 case ISD::SETULT: LowCC = ISD::SETULT; break; 1174 case ISD::SETGT: 1175 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 1176 case ISD::SETLE: 1177 case ISD::SETULE: LowCC = ISD::SETULE; break; 1178 case ISD::SETGE: 1179 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 1180 } 1181 1182 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 1183 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 1184 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 1185 1186 // NOTE: on targets without efficient SELECT of bools, we can always use 1187 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 1188 Tmp1 = DAG.getSetCC(Node->getValueType(0), LHSLo, RHSLo, LowCC); 1189 Tmp2 = DAG.getNode(ISD::SETCC, Node->getValueType(0), LHSHi, RHSHi, 1190 Node->getOperand(2)); 1191 Result = DAG.getSetCC(Node->getValueType(0), LHSHi, RHSHi, ISD::SETEQ); 1192 Result = DAG.getNode(ISD::SELECT, Tmp1.getValueType(), 1193 Result, Tmp1, Tmp2); 1194 break; 1195 } 1196 } 1197 break; 1198 1199 case ISD::MEMSET: 1200 case ISD::MEMCPY: 1201 case ISD::MEMMOVE: { 1202 Tmp1 = LegalizeOp(Node->getOperand(0)); // Chain 1203 Tmp2 = LegalizeOp(Node->getOperand(1)); // Pointer 1204 1205 if (Node->getOpcode() == ISD::MEMSET) { // memset = ubyte 1206 switch (getTypeAction(Node->getOperand(2).getValueType())) { 1207 case Expand: assert(0 && "Cannot expand a byte!"); 1208 case Legal: 1209 Tmp3 = LegalizeOp(Node->getOperand(2)); 1210 break; 1211 case Promote: 1212 Tmp3 = PromoteOp(Node->getOperand(2)); 1213 break; 1214 } 1215 } else { 1216 Tmp3 = LegalizeOp(Node->getOperand(2)); // memcpy/move = pointer, 1217 } 1218 1219 SDOperand Tmp4; 1220 switch (getTypeAction(Node->getOperand(3).getValueType())) { 1221 case Expand: { 1222 // Length is too big, just take the lo-part of the length. 1223 SDOperand HiPart; 1224 ExpandOp(Node->getOperand(3), HiPart, Tmp4); 1225 break; 1226 } 1227 case Legal: 1228 Tmp4 = LegalizeOp(Node->getOperand(3)); 1229 break; 1230 case Promote: 1231 Tmp4 = PromoteOp(Node->getOperand(3)); 1232 break; 1233 } 1234 1235 SDOperand Tmp5; 1236 switch (getTypeAction(Node->getOperand(4).getValueType())) { // uint 1237 case Expand: assert(0 && "Cannot expand this yet!"); 1238 case Legal: 1239 Tmp5 = LegalizeOp(Node->getOperand(4)); 1240 break; 1241 case Promote: 1242 Tmp5 = PromoteOp(Node->getOperand(4)); 1243 break; 1244 } 1245 1246 switch (TLI.getOperationAction(Node->getOpcode(), MVT::Other)) { 1247 default: assert(0 && "This action not implemented for this operation!"); 1248 case TargetLowering::Legal: 1249 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1250 Tmp3 != Node->getOperand(2) || Tmp4 != Node->getOperand(3) || 1251 Tmp5 != Node->getOperand(4)) { 1252 std::vector<SDOperand> Ops; 1253 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 1254 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 1255 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 1256 } 1257 break; 1258 case TargetLowering::Expand: { 1259 // Otherwise, the target does not support this operation. Lower the 1260 // operation to an explicit libcall as appropriate. 1261 MVT::ValueType IntPtr = TLI.getPointerTy(); 1262 const Type *IntPtrTy = TLI.getTargetData().getIntPtrType(); 1263 std::vector<std::pair<SDOperand, const Type*> > Args; 1264 1265 const char *FnName = 0; 1266 if (Node->getOpcode() == ISD::MEMSET) { 1267 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 1268 // Extend the ubyte argument to be an int value for the call. 1269 Tmp3 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Tmp3); 1270 Args.push_back(std::make_pair(Tmp3, Type::IntTy)); 1271 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 1272 1273 FnName = "memset"; 1274 } else if (Node->getOpcode() == ISD::MEMCPY || 1275 Node->getOpcode() == ISD::MEMMOVE) { 1276 Args.push_back(std::make_pair(Tmp2, IntPtrTy)); 1277 Args.push_back(std::make_pair(Tmp3, IntPtrTy)); 1278 Args.push_back(std::make_pair(Tmp4, IntPtrTy)); 1279 FnName = Node->getOpcode() == ISD::MEMMOVE ? "memmove" : "memcpy"; 1280 } else { 1281 assert(0 && "Unknown op!"); 1282 } 1283 1284 std::pair<SDOperand,SDOperand> CallResult = 1285 TLI.LowerCallTo(Tmp1, Type::VoidTy, false, CallingConv::C, false, 1286 DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); 1287 Result = CallResult.second; 1288 NeedsAnotherIteration = true; 1289 break; 1290 } 1291 case TargetLowering::Custom: 1292 std::vector<SDOperand> Ops; 1293 Ops.push_back(Tmp1); Ops.push_back(Tmp2); Ops.push_back(Tmp3); 1294 Ops.push_back(Tmp4); Ops.push_back(Tmp5); 1295 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Ops); 1296 Result = TLI.LowerOperation(Result, DAG); 1297 Result = LegalizeOp(Result); 1298 break; 1299 } 1300 break; 1301 } 1302 1303 case ISD::READPORT: 1304 Tmp1 = LegalizeOp(Node->getOperand(0)); 1305 Tmp2 = LegalizeOp(Node->getOperand(1)); 1306 1307 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 1308 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 1309 std::vector<SDOperand> Ops; 1310 Ops.push_back(Tmp1); 1311 Ops.push_back(Tmp2); 1312 Result = DAG.getNode(ISD::READPORT, VTs, Ops); 1313 } else 1314 Result = SDOperand(Node, 0); 1315 // Since these produce two values, make sure to remember that we legalized 1316 // both of them. 1317 AddLegalizedOperand(SDOperand(Node, 0), Result); 1318 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1319 return Result.getValue(Op.ResNo); 1320 case ISD::WRITEPORT: 1321 Tmp1 = LegalizeOp(Node->getOperand(0)); 1322 Tmp2 = LegalizeOp(Node->getOperand(1)); 1323 Tmp3 = LegalizeOp(Node->getOperand(2)); 1324 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1325 Tmp3 != Node->getOperand(2)) 1326 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); 1327 break; 1328 1329 case ISD::READIO: 1330 Tmp1 = LegalizeOp(Node->getOperand(0)); 1331 Tmp2 = LegalizeOp(Node->getOperand(1)); 1332 1333 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1334 case TargetLowering::Custom: 1335 default: assert(0 && "This action not implemented for this operation!"); 1336 case TargetLowering::Legal: 1337 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) { 1338 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 1339 std::vector<SDOperand> Ops; 1340 Ops.push_back(Tmp1); 1341 Ops.push_back(Tmp2); 1342 Result = DAG.getNode(ISD::READPORT, VTs, Ops); 1343 } else 1344 Result = SDOperand(Node, 0); 1345 break; 1346 case TargetLowering::Expand: 1347 // Replace this with a load from memory. 1348 Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0), 1349 Node->getOperand(1), DAG.getSrcValue(NULL)); 1350 Result = LegalizeOp(Result); 1351 break; 1352 } 1353 1354 // Since these produce two values, make sure to remember that we legalized 1355 // both of them. 1356 AddLegalizedOperand(SDOperand(Node, 0), Result); 1357 AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); 1358 return Result.getValue(Op.ResNo); 1359 1360 case ISD::WRITEIO: 1361 Tmp1 = LegalizeOp(Node->getOperand(0)); 1362 Tmp2 = LegalizeOp(Node->getOperand(1)); 1363 Tmp3 = LegalizeOp(Node->getOperand(2)); 1364 1365 switch (TLI.getOperationAction(Node->getOpcode(), 1366 Node->getOperand(1).getValueType())) { 1367 case TargetLowering::Custom: 1368 default: assert(0 && "This action not implemented for this operation!"); 1369 case TargetLowering::Legal: 1370 if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || 1371 Tmp3 != Node->getOperand(2)) 1372 Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); 1373 break; 1374 case TargetLowering::Expand: 1375 // Replace this with a store to memory. 1376 Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0), 1377 Node->getOperand(1), Node->getOperand(2), 1378 DAG.getSrcValue(NULL)); 1379 Result = LegalizeOp(Result); 1380 break; 1381 } 1382 break; 1383 1384 case ISD::ADD_PARTS: 1385 case ISD::SUB_PARTS: 1386 case ISD::SHL_PARTS: 1387 case ISD::SRA_PARTS: 1388 case ISD::SRL_PARTS: { 1389 std::vector<SDOperand> Ops; 1390 bool Changed = false; 1391 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 1392 Ops.push_back(LegalizeOp(Node->getOperand(i))); 1393 Changed |= Ops.back() != Node->getOperand(i); 1394 } 1395 if (Changed) { 1396 std::vector<MVT::ValueType> VTs(Node->value_begin(), Node->value_end()); 1397 Result = DAG.getNode(Node->getOpcode(), VTs, Ops); 1398 } 1399 1400 // Since these produce multiple values, make sure to remember that we 1401 // legalized all of them. 1402 for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) 1403 AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i)); 1404 return Result.getValue(Op.ResNo); 1405 } 1406 1407 // Binary operators 1408 case ISD::ADD: 1409 case ISD::SUB: 1410 case ISD::MUL: 1411 case ISD::MULHS: 1412 case ISD::MULHU: 1413 case ISD::UDIV: 1414 case ISD::SDIV: 1415 case ISD::AND: 1416 case ISD::OR: 1417 case ISD::XOR: 1418 case ISD::SHL: 1419 case ISD::SRL: 1420 case ISD::SRA: 1421 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1422 switch (getTypeAction(Node->getOperand(1).getValueType())) { 1423 case Expand: assert(0 && "Not possible"); 1424 case Legal: 1425 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the RHS. 1426 break; 1427 case Promote: 1428 Tmp2 = PromoteOp(Node->getOperand(1)); // Promote the RHS. 1429 break; 1430 } 1431 if (Tmp1 != Node->getOperand(0) || 1432 Tmp2 != Node->getOperand(1)) 1433 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); 1434 break; 1435 1436 case ISD::UREM: 1437 case ISD::SREM: 1438 Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS 1439 Tmp2 = LegalizeOp(Node->getOperand(1)); // RHS 1440 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1441 case TargetLowering::Legal: 1442 if (Tmp1 != Node->getOperand(0) || 1443 Tmp2 != Node->getOperand(1)) 1444 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 1445 Tmp2); 1446 break; 1447 case TargetLowering::Promote: 1448 case TargetLowering::Custom: 1449 assert(0 && "Cannot promote/custom handle this yet!"); 1450 case TargetLowering::Expand: 1451 if (MVT::isInteger(Node->getValueType(0))) { 1452 MVT::ValueType VT = Node->getValueType(0); 1453 unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV; 1454 Result = DAG.getNode(Opc, VT, Tmp1, Tmp2); 1455 Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2); 1456 Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result); 1457 } else { 1458 // Floating point mod -> fmod libcall. 1459 const char *FnName = Node->getValueType(0) == MVT::f32 ? "fmodf":"fmod"; 1460 SDOperand Dummy; 1461 Result = ExpandLibCall(FnName, Node, Dummy); 1462 } 1463 break; 1464 } 1465 break; 1466 1467 case ISD::CTPOP: 1468 case ISD::CTTZ: 1469 case ISD::CTLZ: 1470 Tmp1 = LegalizeOp(Node->getOperand(0)); // Op 1471 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1472 case TargetLowering::Legal: 1473 if (Tmp1 != Node->getOperand(0)) 1474 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1475 break; 1476 case TargetLowering::Promote: { 1477 MVT::ValueType OVT = Tmp1.getValueType(); 1478 MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT); 1479 1480 // Zero extend the argument. 1481 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 1482 // Perform the larger operation, then subtract if needed. 1483 Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1484 switch(Node->getOpcode()) 1485 { 1486 case ISD::CTPOP: 1487 Result = Tmp1; 1488 break; 1489 case ISD::CTTZ: 1490 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) 1491 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, 1492 DAG.getConstant(getSizeInBits(NVT), NVT), 1493 ISD::SETEQ); 1494 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 1495 DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1); 1496 break; 1497 case ISD::CTLZ: 1498 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) 1499 Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 1500 DAG.getConstant(getSizeInBits(NVT) - 1501 getSizeInBits(OVT), NVT)); 1502 break; 1503 } 1504 break; 1505 } 1506 case TargetLowering::Custom: 1507 assert(0 && "Cannot custom handle this yet!"); 1508 case TargetLowering::Expand: 1509 switch(Node->getOpcode()) 1510 { 1511 case ISD::CTPOP: { 1512 static const uint64_t mask[6] = { 1513 0x5555555555555555ULL, 0x3333333333333333ULL, 1514 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL, 1515 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL 1516 }; 1517 MVT::ValueType VT = Tmp1.getValueType(); 1518 MVT::ValueType ShVT = TLI.getShiftAmountTy(); 1519 unsigned len = getSizeInBits(VT); 1520 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 1521 //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8]) 1522 Tmp2 = DAG.getConstant(mask[i], VT); 1523 Tmp3 = DAG.getConstant(1ULL << i, ShVT); 1524 Tmp1 = DAG.getNode(ISD::ADD, VT, 1525 DAG.getNode(ISD::AND, VT, Tmp1, Tmp2), 1526 DAG.getNode(ISD::AND, VT, 1527 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3), 1528 Tmp2)); 1529 } 1530 Result = Tmp1; 1531 break; 1532 } 1533 case ISD::CTLZ: { 1534 /* for now, we do this: 1535 x = x | (x >> 1); 1536 x = x | (x >> 2); 1537 ... 1538 x = x | (x >>16); 1539 x = x | (x >>32); // for 64-bit input 1540 return popcount(~x); 1541 1542 but see also: http://www.hackersdelight.org/HDcode/nlz.cc */ 1543 MVT::ValueType VT = Tmp1.getValueType(); 1544 MVT::ValueType ShVT = TLI.getShiftAmountTy(); 1545 unsigned len = getSizeInBits(VT); 1546 for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { 1547 Tmp3 = DAG.getConstant(1ULL << i, ShVT); 1548 Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1, 1549 DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3)); 1550 } 1551 Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT)); 1552 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); 1553 break; 1554 } 1555 case ISD::CTTZ: { 1556 // for now, we use: { return popcount(~x & (x - 1)); } 1557 // unless the target has ctlz but not ctpop, in which case we use: 1558 // { return 32 - nlz(~x & (x-1)); } 1559 // see also http://www.hackersdelight.org/HDcode/ntz.cc 1560 MVT::ValueType VT = Tmp1.getValueType(); 1561 Tmp2 = DAG.getConstant(~0ULL, VT); 1562 Tmp3 = DAG.getNode(ISD::AND, VT, 1563 DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2), 1564 DAG.getNode(ISD::SUB, VT, Tmp1, 1565 DAG.getConstant(1, VT))); 1566 // If ISD::CTLZ is legal and CTPOP isn't, then do that instead 1567 if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal && 1568 TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) { 1569 Result = LegalizeOp(DAG.getNode(ISD::SUB, VT, 1570 DAG.getConstant(getSizeInBits(VT), VT), 1571 DAG.getNode(ISD::CTLZ, VT, Tmp3))); 1572 } else { 1573 Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); 1574 } 1575 break; 1576 } 1577 default: 1578 assert(0 && "Cannot expand this yet!"); 1579 break; 1580 } 1581 break; 1582 } 1583 break; 1584 1585 // Unary operators 1586 case ISD::FABS: 1587 case ISD::FNEG: 1588 case ISD::FSQRT: 1589 case ISD::FSIN: 1590 case ISD::FCOS: 1591 Tmp1 = LegalizeOp(Node->getOperand(0)); 1592 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { 1593 case TargetLowering::Legal: 1594 if (Tmp1 != Node->getOperand(0)) 1595 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1596 break; 1597 case TargetLowering::Promote: 1598 case TargetLowering::Custom: 1599 assert(0 && "Cannot promote/custom handle this yet!"); 1600 case TargetLowering::Expand: 1601 switch(Node->getOpcode()) { 1602 case ISD::FNEG: { 1603 // Expand Y = FNEG(X) -> Y = SUB -0.0, X 1604 Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0)); 1605 Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0), 1606 Tmp2, Tmp1)); 1607 break; 1608 } 1609 case ISD::FABS: { 1610 // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X). 1611 MVT::ValueType VT = Node->getValueType(0); 1612 Tmp2 = DAG.getConstantFP(0.0, VT); 1613 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, Tmp2, ISD::SETUGT); 1614 Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1); 1615 Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3); 1616 Result = LegalizeOp(Result); 1617 break; 1618 } 1619 case ISD::FSQRT: 1620 case ISD::FSIN: 1621 case ISD::FCOS: { 1622 MVT::ValueType VT = Node->getValueType(0); 1623 const char *FnName = 0; 1624 switch(Node->getOpcode()) { 1625 case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break; 1626 case ISD::FSIN: FnName = VT == MVT::f32 ? "sinf" : "sin"; break; 1627 case ISD::FCOS: FnName = VT == MVT::f32 ? "cosf" : "cos"; break; 1628 default: assert(0 && "Unreachable!"); 1629 } 1630 SDOperand Dummy; 1631 Result = ExpandLibCall(FnName, Node, Dummy); 1632 break; 1633 } 1634 default: 1635 assert(0 && "Unreachable!"); 1636 } 1637 break; 1638 } 1639 break; 1640 1641 // Conversion operators. The source and destination have different types. 1642 case ISD::SINT_TO_FP: 1643 case ISD::UINT_TO_FP: { 1644 bool isSigned = Node->getOpcode() == ISD::SINT_TO_FP; 1645 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1646 case Legal: 1647 switch (TLI.getOperationAction(Node->getOpcode(), 1648 Node->getOperand(0).getValueType())) { 1649 default: assert(0 && "Unknown operation action!"); 1650 case TargetLowering::Expand: 1651 assert(!isSigned && "Legalize cannot Expand SINT_TO_FP yet"); 1652 Result = ExpandLegalUINT_TO_FP(LegalizeOp(Node->getOperand(0)), 1653 Node->getValueType(0)); 1654 AddLegalizedOperand(Op, Result); 1655 return Result; 1656 case TargetLowering::Promote: 1657 Result = PromoteLegalINT_TO_FP(LegalizeOp(Node->getOperand(0)), 1658 Node->getValueType(0), 1659 isSigned); 1660 AddLegalizedOperand(Op, Result); 1661 return Result; 1662 case TargetLowering::Legal: 1663 break; 1664 } 1665 1666 Tmp1 = LegalizeOp(Node->getOperand(0)); 1667 if (Tmp1 != Node->getOperand(0)) 1668 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1669 break; 1670 case Expand: 1671 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, 1672 Node->getValueType(0), Node->getOperand(0)); 1673 break; 1674 case Promote: 1675 if (isSigned) { 1676 Result = PromoteOp(Node->getOperand(0)); 1677 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1678 Result, DAG.getValueType(Node->getOperand(0).getValueType())); 1679 Result = DAG.getNode(ISD::SINT_TO_FP, Op.getValueType(), Result); 1680 } else { 1681 Result = PromoteOp(Node->getOperand(0)); 1682 Result = DAG.getZeroExtendInReg(Result, 1683 Node->getOperand(0).getValueType()); 1684 Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result); 1685 } 1686 break; 1687 } 1688 break; 1689 } 1690 case ISD::TRUNCATE: 1691 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1692 case Legal: 1693 Tmp1 = LegalizeOp(Node->getOperand(0)); 1694 if (Tmp1 != Node->getOperand(0)) 1695 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1696 break; 1697 case Expand: 1698 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 1699 1700 // Since the result is legal, we should just be able to truncate the low 1701 // part of the source. 1702 Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); 1703 break; 1704 case Promote: 1705 Result = PromoteOp(Node->getOperand(0)); 1706 Result = DAG.getNode(ISD::TRUNCATE, Op.getValueType(), Result); 1707 break; 1708 } 1709 break; 1710 1711 case ISD::FP_TO_SINT: 1712 case ISD::FP_TO_UINT: 1713 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1714 case Legal: 1715 Tmp1 = LegalizeOp(Node->getOperand(0)); 1716 1717 switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))){ 1718 default: assert(0 && "Unknown operation action!"); 1719 case TargetLowering::Expand: 1720 if (Node->getOpcode() == ISD::FP_TO_UINT) { 1721 SDOperand True, False; 1722 MVT::ValueType VT = Node->getOperand(0).getValueType(); 1723 MVT::ValueType NVT = Node->getValueType(0); 1724 unsigned ShiftAmt = MVT::getSizeInBits(Node->getValueType(0))-1; 1725 Tmp2 = DAG.getConstantFP((double)(1ULL << ShiftAmt), VT); 1726 Tmp3 = DAG.getSetCC(TLI.getSetCCResultTy(), 1727 Node->getOperand(0), Tmp2, ISD::SETLT); 1728 True = DAG.getNode(ISD::FP_TO_SINT, NVT, Node->getOperand(0)); 1729 False = DAG.getNode(ISD::FP_TO_SINT, NVT, 1730 DAG.getNode(ISD::SUB, VT, Node->getOperand(0), 1731 Tmp2)); 1732 False = DAG.getNode(ISD::XOR, NVT, False, 1733 DAG.getConstant(1ULL << ShiftAmt, NVT)); 1734 Result = LegalizeOp(DAG.getNode(ISD::SELECT, NVT, Tmp3, True, False)); 1735 return Result; 1736 } else { 1737 assert(0 && "Do not know how to expand FP_TO_SINT yet!"); 1738 } 1739 break; 1740 case TargetLowering::Promote: 1741 Result = PromoteLegalFP_TO_INT(Tmp1, Node->getValueType(0), 1742 Node->getOpcode() == ISD::FP_TO_SINT); 1743 AddLegalizedOperand(Op, Result); 1744 return Result; 1745 case TargetLowering::Legal: 1746 break; 1747 case TargetLowering::Custom: 1748 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1749 Result = TLI.LowerOperation(Result, DAG); 1750 AddLegalizedOperand(Op, Result); 1751 NeedsAnotherIteration = true; 1752 return Result; 1753 } 1754 1755 if (Tmp1 != Node->getOperand(0)) 1756 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1757 break; 1758 case Expand: 1759 assert(0 && "Shouldn't need to expand other operators here!"); 1760 case Promote: 1761 Result = PromoteOp(Node->getOperand(0)); 1762 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result); 1763 break; 1764 } 1765 break; 1766 1767 case ISD::ZERO_EXTEND: 1768 case ISD::SIGN_EXTEND: 1769 case ISD::FP_EXTEND: 1770 case ISD::FP_ROUND: 1771 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1772 case Legal: 1773 Tmp1 = LegalizeOp(Node->getOperand(0)); 1774 if (Tmp1 != Node->getOperand(0)) 1775 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); 1776 break; 1777 case Expand: 1778 assert(0 && "Shouldn't need to expand other operators here!"); 1779 1780 case Promote: 1781 switch (Node->getOpcode()) { 1782 case ISD::ZERO_EXTEND: 1783 Result = PromoteOp(Node->getOperand(0)); 1784 // NOTE: Any extend would work here... 1785 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 1786 Result = DAG.getZeroExtendInReg(Result, 1787 Node->getOperand(0).getValueType()); 1788 break; 1789 case ISD::SIGN_EXTEND: 1790 Result = PromoteOp(Node->getOperand(0)); 1791 // NOTE: Any extend would work here... 1792 Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result); 1793 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1794 Result, 1795 DAG.getValueType(Node->getOperand(0).getValueType())); 1796 break; 1797 case ISD::FP_EXTEND: 1798 Result = PromoteOp(Node->getOperand(0)); 1799 if (Result.getValueType() != Op.getValueType()) 1800 // Dynamically dead while we have only 2 FP types. 1801 Result = DAG.getNode(ISD::FP_EXTEND, Op.getValueType(), Result); 1802 break; 1803 case ISD::FP_ROUND: 1804 Result = PromoteOp(Node->getOperand(0)); 1805 Result = DAG.getNode(Node->getOpcode(), Op.getValueType(), Result); 1806 break; 1807 } 1808 } 1809 break; 1810 case ISD::FP_ROUND_INREG: 1811 case ISD::SIGN_EXTEND_INREG: { 1812 Tmp1 = LegalizeOp(Node->getOperand(0)); 1813 MVT::ValueType ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT(); 1814 1815 // If this operation is not supported, convert it to a shl/shr or load/store 1816 // pair. 1817 switch (TLI.getOperationAction(Node->getOpcode(), ExtraVT)) { 1818 default: assert(0 && "This action not supported for this op yet!"); 1819 case TargetLowering::Legal: 1820 if (Tmp1 != Node->getOperand(0)) 1821 Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, 1822 DAG.getValueType(ExtraVT)); 1823 break; 1824 case TargetLowering::Expand: 1825 // If this is an integer extend and shifts are supported, do that. 1826 if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) { 1827 // NOTE: we could fall back on load/store here too for targets without 1828 // SAR. However, it is doubtful that any exist. 1829 unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) - 1830 MVT::getSizeInBits(ExtraVT); 1831 SDOperand ShiftCst = DAG.getConstant(BitsDiff, TLI.getShiftAmountTy()); 1832 Result = DAG.getNode(ISD::SHL, Node->getValueType(0), 1833 Node->getOperand(0), ShiftCst); 1834 Result = DAG.getNode(ISD::SRA, Node->getValueType(0), 1835 Result, ShiftCst); 1836 } else if (Node->getOpcode() == ISD::FP_ROUND_INREG) { 1837 // The only way we can lower this is to turn it into a STORETRUNC, 1838 // EXTLOAD pair, targetting a temporary location (a stack slot). 1839 1840 // NOTE: there is a choice here between constantly creating new stack 1841 // slots and always reusing the same one. We currently always create 1842 // new ones, as reuse may inhibit scheduling. 1843 const Type *Ty = MVT::getTypeForValueType(ExtraVT); 1844 unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty); 1845 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 1846 MachineFunction &MF = DAG.getMachineFunction(); 1847 int SSFI = 1848 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 1849 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 1850 Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(), 1851 Node->getOperand(0), StackSlot, 1852 DAG.getSrcValue(NULL), DAG.getValueType(ExtraVT)); 1853 Result = DAG.getExtLoad(ISD::EXTLOAD, Node->getValueType(0), 1854 Result, StackSlot, DAG.getSrcValue(NULL), 1855 ExtraVT); 1856 } else { 1857 assert(0 && "Unknown op"); 1858 } 1859 Result = LegalizeOp(Result); 1860 break; 1861 } 1862 break; 1863 } 1864 } 1865 1866 // Note that LegalizeOp may be reentered even from single-use nodes, which 1867 // means that we always must cache transformed nodes. 1868 AddLegalizedOperand(Op, Result); 1869 return Result; 1870} 1871 1872/// PromoteOp - Given an operation that produces a value in an invalid type, 1873/// promote it to compute the value into a larger type. The produced value will 1874/// have the correct bits for the low portion of the register, but no guarantee 1875/// is made about the top bits: it may be zero, sign-extended, or garbage. 1876SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { 1877 MVT::ValueType VT = Op.getValueType(); 1878 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1879 assert(getTypeAction(VT) == Promote && 1880 "Caller should expand or legalize operands that are not promotable!"); 1881 assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) && 1882 "Cannot promote to smaller type!"); 1883 1884 SDOperand Tmp1, Tmp2, Tmp3; 1885 1886 SDOperand Result; 1887 SDNode *Node = Op.Val; 1888 1889 if (!Node->hasOneUse()) { 1890 std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op); 1891 if (I != PromotedNodes.end()) return I->second; 1892 } else { 1893 assert(!PromotedNodes.count(Op) && "Repromoted this node??"); 1894 } 1895 1896 // Promotion needs an optimization step to clean up after it, and is not 1897 // careful to avoid operations the target does not support. Make sure that 1898 // all generated operations are legalized in the next iteration. 1899 NeedsAnotherIteration = true; 1900 1901 switch (Node->getOpcode()) { 1902 case ISD::CopyFromReg: 1903 assert(0 && "CopyFromReg must be legal!"); 1904 default: 1905 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 1906 assert(0 && "Do not know how to promote this operator!"); 1907 abort(); 1908 case ISD::UNDEF: 1909 Result = DAG.getNode(ISD::UNDEF, NVT); 1910 break; 1911 case ISD::Constant: 1912 Result = DAG.getNode(ISD::ZERO_EXTEND, NVT, Op); 1913 assert(isa<ConstantSDNode>(Result) && "Didn't constant fold zext?"); 1914 break; 1915 case ISD::ConstantFP: 1916 Result = DAG.getNode(ISD::FP_EXTEND, NVT, Op); 1917 assert(isa<ConstantFPSDNode>(Result) && "Didn't constant fold fp_extend?"); 1918 break; 1919 1920 case ISD::SETCC: 1921 assert(getTypeAction(TLI.getSetCCResultTy()) == Legal && 1922 "SetCC type is not legal??"); 1923 Result = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(),Node->getOperand(0), 1924 Node->getOperand(1), Node->getOperand(2)); 1925 Result = LegalizeOp(Result); 1926 break; 1927 1928 case ISD::TRUNCATE: 1929 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1930 case Legal: 1931 Result = LegalizeOp(Node->getOperand(0)); 1932 assert(Result.getValueType() >= NVT && 1933 "This truncation doesn't make sense!"); 1934 if (Result.getValueType() > NVT) // Truncate to NVT instead of VT 1935 Result = DAG.getNode(ISD::TRUNCATE, NVT, Result); 1936 break; 1937 case Promote: 1938 // The truncation is not required, because we don't guarantee anything 1939 // about high bits anyway. 1940 Result = PromoteOp(Node->getOperand(0)); 1941 break; 1942 case Expand: 1943 ExpandOp(Node->getOperand(0), Tmp1, Tmp2); 1944 // Truncate the low part of the expanded value to the result type 1945 Result = DAG.getNode(ISD::TRUNCATE, NVT, Tmp1); 1946 } 1947 break; 1948 case ISD::SIGN_EXTEND: 1949 case ISD::ZERO_EXTEND: 1950 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1951 case Expand: assert(0 && "BUG: Smaller reg should have been promoted!"); 1952 case Legal: 1953 // Input is legal? Just do extend all the way to the larger type. 1954 Result = LegalizeOp(Node->getOperand(0)); 1955 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1956 break; 1957 case Promote: 1958 // Promote the reg if it's smaller. 1959 Result = PromoteOp(Node->getOperand(0)); 1960 // The high bits are not guaranteed to be anything. Insert an extend. 1961 if (Node->getOpcode() == ISD::SIGN_EXTEND) 1962 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result, 1963 DAG.getValueType(Node->getOperand(0).getValueType())); 1964 else 1965 Result = DAG.getZeroExtendInReg(Result, 1966 Node->getOperand(0).getValueType()); 1967 break; 1968 } 1969 break; 1970 1971 case ISD::FP_EXTEND: 1972 assert(0 && "Case not implemented. Dynamically dead with 2 FP types!"); 1973 case ISD::FP_ROUND: 1974 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1975 case Expand: assert(0 && "BUG: Cannot expand FP regs!"); 1976 case Promote: assert(0 && "Unreachable with 2 FP types!"); 1977 case Legal: 1978 // Input is legal? Do an FP_ROUND_INREG. 1979 Result = LegalizeOp(Node->getOperand(0)); 1980 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 1981 DAG.getValueType(VT)); 1982 break; 1983 } 1984 break; 1985 1986 case ISD::SINT_TO_FP: 1987 case ISD::UINT_TO_FP: 1988 switch (getTypeAction(Node->getOperand(0).getValueType())) { 1989 case Legal: 1990 Result = LegalizeOp(Node->getOperand(0)); 1991 // No extra round required here. 1992 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 1993 break; 1994 1995 case Promote: 1996 Result = PromoteOp(Node->getOperand(0)); 1997 if (Node->getOpcode() == ISD::SINT_TO_FP) 1998 Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), 1999 Result, 2000 DAG.getValueType(Node->getOperand(0).getValueType())); 2001 else 2002 Result = DAG.getZeroExtendInReg(Result, 2003 Node->getOperand(0).getValueType()); 2004 // No extra round required here. 2005 Result = DAG.getNode(Node->getOpcode(), NVT, Result); 2006 break; 2007 case Expand: 2008 Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT, 2009 Node->getOperand(0)); 2010 // Round if we cannot tolerate excess precision. 2011 if (NoExcessFPPrecision) 2012 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 2013 DAG.getValueType(VT)); 2014 break; 2015 } 2016 break; 2017 2018 case ISD::FP_TO_SINT: 2019 case ISD::FP_TO_UINT: 2020 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2021 case Legal: 2022 Tmp1 = LegalizeOp(Node->getOperand(0)); 2023 break; 2024 case Promote: 2025 // The input result is prerounded, so we don't have to do anything 2026 // special. 2027 Tmp1 = PromoteOp(Node->getOperand(0)); 2028 break; 2029 case Expand: 2030 assert(0 && "not implemented"); 2031 } 2032 // If we're promoting a UINT to a larger size, check to see if the new node 2033 // will be legal. If it isn't, check to see if FP_TO_SINT is legal, since 2034 // we can use that instead. This allows us to generate better code for 2035 // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not 2036 // legal, such as PowerPC. 2037 if (Node->getOpcode() == ISD::FP_TO_UINT && 2038 TargetLowering::Legal != TLI.getOperationAction(ISD::FP_TO_UINT, NVT) && 2039 TargetLowering::Legal == TLI.getOperationAction(ISD::FP_TO_SINT, NVT)) { 2040 Result = DAG.getNode(ISD::FP_TO_SINT, NVT, Tmp1); 2041 } else { 2042 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 2043 } 2044 break; 2045 2046 case ISD::FABS: 2047 case ISD::FNEG: 2048 Tmp1 = PromoteOp(Node->getOperand(0)); 2049 assert(Tmp1.getValueType() == NVT); 2050 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 2051 // NOTE: we do not have to do any extra rounding here for 2052 // NoExcessFPPrecision, because we know the input will have the appropriate 2053 // precision, and these operations don't modify precision at all. 2054 break; 2055 2056 case ISD::FSQRT: 2057 case ISD::FSIN: 2058 case ISD::FCOS: 2059 Tmp1 = PromoteOp(Node->getOperand(0)); 2060 assert(Tmp1.getValueType() == NVT); 2061 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 2062 if(NoExcessFPPrecision) 2063 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 2064 DAG.getValueType(VT)); 2065 break; 2066 2067 case ISD::AND: 2068 case ISD::OR: 2069 case ISD::XOR: 2070 case ISD::ADD: 2071 case ISD::SUB: 2072 case ISD::MUL: 2073 // The input may have strange things in the top bits of the registers, but 2074 // these operations don't care. They may have wierd bits going out, but 2075 // that too is okay if they are integer operations. 2076 Tmp1 = PromoteOp(Node->getOperand(0)); 2077 Tmp2 = PromoteOp(Node->getOperand(1)); 2078 assert(Tmp1.getValueType() == NVT && Tmp2.getValueType() == NVT); 2079 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 2080 2081 // However, if this is a floating point operation, they will give excess 2082 // precision that we may not be able to tolerate. If we DO allow excess 2083 // precision, just leave it, otherwise excise it. 2084 // FIXME: Why would we need to round FP ops more than integer ones? 2085 // Is Round(Add(Add(A,B),C)) != Round(Add(Round(Add(A,B)), C)) 2086 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 2087 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 2088 DAG.getValueType(VT)); 2089 break; 2090 2091 case ISD::SDIV: 2092 case ISD::SREM: 2093 // These operators require that their input be sign extended. 2094 Tmp1 = PromoteOp(Node->getOperand(0)); 2095 Tmp2 = PromoteOp(Node->getOperand(1)); 2096 if (MVT::isInteger(NVT)) { 2097 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, 2098 DAG.getValueType(VT)); 2099 Tmp2 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp2, 2100 DAG.getValueType(VT)); 2101 } 2102 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 2103 2104 // Perform FP_ROUND: this is probably overly pessimistic. 2105 if (MVT::isFloatingPoint(NVT) && NoExcessFPPrecision) 2106 Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, 2107 DAG.getValueType(VT)); 2108 break; 2109 2110 case ISD::UDIV: 2111 case ISD::UREM: 2112 // These operators require that their input be zero extended. 2113 Tmp1 = PromoteOp(Node->getOperand(0)); 2114 Tmp2 = PromoteOp(Node->getOperand(1)); 2115 assert(MVT::isInteger(NVT) && "Operators don't apply to FP!"); 2116 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 2117 Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT); 2118 Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2); 2119 break; 2120 2121 case ISD::SHL: 2122 Tmp1 = PromoteOp(Node->getOperand(0)); 2123 Tmp2 = LegalizeOp(Node->getOperand(1)); 2124 Result = DAG.getNode(ISD::SHL, NVT, Tmp1, Tmp2); 2125 break; 2126 case ISD::SRA: 2127 // The input value must be properly sign extended. 2128 Tmp1 = PromoteOp(Node->getOperand(0)); 2129 Tmp1 = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Tmp1, 2130 DAG.getValueType(VT)); 2131 Tmp2 = LegalizeOp(Node->getOperand(1)); 2132 Result = DAG.getNode(ISD::SRA, NVT, Tmp1, Tmp2); 2133 break; 2134 case ISD::SRL: 2135 // The input value must be properly zero extended. 2136 Tmp1 = PromoteOp(Node->getOperand(0)); 2137 Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT); 2138 Tmp2 = LegalizeOp(Node->getOperand(1)); 2139 Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2); 2140 break; 2141 case ISD::LOAD: 2142 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 2143 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 2144 // FIXME: When the DAG combiner exists, change this to use EXTLOAD! 2145 if (MVT::isInteger(NVT)) 2146 Result = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2, 2147 Node->getOperand(2), VT); 2148 else 2149 Result = DAG.getExtLoad(ISD::EXTLOAD, NVT, Tmp1, Tmp2, 2150 Node->getOperand(2), VT); 2151 2152 // Remember that we legalized the chain. 2153 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 2154 break; 2155 case ISD::SELECT: 2156 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2157 case Expand: assert(0 && "It's impossible to expand bools"); 2158 case Legal: 2159 Tmp1 = LegalizeOp(Node->getOperand(0));// Legalize the condition. 2160 break; 2161 case Promote: 2162 Tmp1 = PromoteOp(Node->getOperand(0)); // Promote the condition. 2163 break; 2164 } 2165 Tmp2 = PromoteOp(Node->getOperand(1)); // Legalize the op0 2166 Tmp3 = PromoteOp(Node->getOperand(2)); // Legalize the op1 2167 Result = DAG.getNode(ISD::SELECT, NVT, Tmp1, Tmp2, Tmp3); 2168 break; 2169 case ISD::SELECT_CC: 2170 Tmp2 = PromoteOp(Node->getOperand(2)); // True 2171 Tmp3 = PromoteOp(Node->getOperand(3)); // False 2172 Result = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0), 2173 Node->getOperand(1), Tmp2, Tmp3, 2174 Node->getOperand(4)); 2175 break; 2176 case ISD::TAILCALL: 2177 case ISD::CALL: { 2178 Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 2179 Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 2180 2181 std::vector<SDOperand> Ops; 2182 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) 2183 Ops.push_back(LegalizeOp(Node->getOperand(i))); 2184 2185 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 2186 "Can only promote single result calls"); 2187 std::vector<MVT::ValueType> RetTyVTs; 2188 RetTyVTs.reserve(2); 2189 RetTyVTs.push_back(NVT); 2190 RetTyVTs.push_back(MVT::Other); 2191 SDNode *NC = DAG.getCall(RetTyVTs, Tmp1, Tmp2, Ops, 2192 Node->getOpcode() == ISD::TAILCALL); 2193 Result = SDOperand(NC, 0); 2194 2195 // Insert the new chain mapping. 2196 AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); 2197 break; 2198 } 2199 case ISD::CTPOP: 2200 case ISD::CTTZ: 2201 case ISD::CTLZ: 2202 Tmp1 = Node->getOperand(0); 2203 //Zero extend the argument 2204 Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); 2205 // Perform the larger operation, then subtract if needed. 2206 Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1); 2207 switch(Node->getOpcode()) 2208 { 2209 case ISD::CTPOP: 2210 Result = Tmp1; 2211 break; 2212 case ISD::CTTZ: 2213 //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) 2214 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), Tmp1, 2215 DAG.getConstant(getSizeInBits(NVT), NVT), ISD::SETEQ); 2216 Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 2217 DAG.getConstant(getSizeInBits(VT),NVT), Tmp1); 2218 break; 2219 case ISD::CTLZ: 2220 //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) 2221 Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 2222 DAG.getConstant(getSizeInBits(NVT) - 2223 getSizeInBits(VT), NVT)); 2224 break; 2225 } 2226 break; 2227 } 2228 2229 assert(Result.Val && "Didn't set a result!"); 2230 AddPromotedOperand(Op, Result); 2231 return Result; 2232} 2233 2234/// ExpandAddSub - Find a clever way to expand this add operation into 2235/// subcomponents. 2236void SelectionDAGLegalize:: 2237ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS, 2238 SDOperand &Lo, SDOperand &Hi) { 2239 // Expand the subcomponents. 2240 SDOperand LHSL, LHSH, RHSL, RHSH; 2241 ExpandOp(LHS, LHSL, LHSH); 2242 ExpandOp(RHS, RHSL, RHSH); 2243 2244 // FIXME: this should be moved to the dag combiner someday. 2245 assert(NodeOp == ISD::ADD_PARTS || NodeOp == ISD::SUB_PARTS); 2246 if (LHSL.getValueType() == MVT::i32) { 2247 SDOperand LowEl; 2248 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(LHSL)) 2249 if (C->getValue() == 0) 2250 LowEl = RHSL; 2251 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHSL)) 2252 if (C->getValue() == 0) 2253 LowEl = LHSL; 2254 if (LowEl.Val) { 2255 // Turn this into an add/sub of the high part only. 2256 SDOperand HiEl = 2257 DAG.getNode(NodeOp == ISD::ADD_PARTS ? ISD::ADD : ISD::SUB, 2258 LowEl.getValueType(), LHSH, RHSH); 2259 Lo = LowEl; 2260 Hi = HiEl; 2261 return; 2262 } 2263 } 2264 2265 std::vector<SDOperand> Ops; 2266 Ops.push_back(LHSL); 2267 Ops.push_back(LHSH); 2268 Ops.push_back(RHSL); 2269 Ops.push_back(RHSH); 2270 2271 std::vector<MVT::ValueType> VTs(2, LHSL.getValueType()); 2272 Lo = DAG.getNode(NodeOp, VTs, Ops); 2273 Hi = Lo.getValue(1); 2274} 2275 2276void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp, 2277 SDOperand Op, SDOperand Amt, 2278 SDOperand &Lo, SDOperand &Hi) { 2279 // Expand the subcomponents. 2280 SDOperand LHSL, LHSH; 2281 ExpandOp(Op, LHSL, LHSH); 2282 2283 std::vector<SDOperand> Ops; 2284 Ops.push_back(LHSL); 2285 Ops.push_back(LHSH); 2286 Ops.push_back(Amt); 2287 std::vector<MVT::ValueType> VTs; 2288 VTs.push_back(LHSL.getValueType()); 2289 VTs.push_back(LHSH.getValueType()); 2290 VTs.push_back(Amt.getValueType()); 2291 Lo = DAG.getNode(NodeOp, VTs, Ops); 2292 Hi = Lo.getValue(1); 2293} 2294 2295 2296/// ExpandShift - Try to find a clever way to expand this shift operation out to 2297/// smaller elements. If we can't find a way that is more efficient than a 2298/// libcall on this target, return false. Otherwise, return true with the 2299/// low-parts expanded into Lo and Hi. 2300bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt, 2301 SDOperand &Lo, SDOperand &Hi) { 2302 assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) && 2303 "This is not a shift!"); 2304 2305 MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType()); 2306 SDOperand ShAmt = LegalizeOp(Amt); 2307 MVT::ValueType ShTy = ShAmt.getValueType(); 2308 unsigned VTBits = MVT::getSizeInBits(Op.getValueType()); 2309 unsigned NVTBits = MVT::getSizeInBits(NVT); 2310 2311 // Handle the case when Amt is an immediate. Other cases are currently broken 2312 // and are disabled. 2313 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) { 2314 unsigned Cst = CN->getValue(); 2315 // Expand the incoming operand to be shifted, so that we have its parts 2316 SDOperand InL, InH; 2317 ExpandOp(Op, InL, InH); 2318 switch(Opc) { 2319 case ISD::SHL: 2320 if (Cst > VTBits) { 2321 Lo = DAG.getConstant(0, NVT); 2322 Hi = DAG.getConstant(0, NVT); 2323 } else if (Cst > NVTBits) { 2324 Lo = DAG.getConstant(0, NVT); 2325 Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy)); 2326 } else if (Cst == NVTBits) { 2327 Lo = DAG.getConstant(0, NVT); 2328 Hi = InL; 2329 } else { 2330 Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy)); 2331 Hi = DAG.getNode(ISD::OR, NVT, 2332 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)), 2333 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy))); 2334 } 2335 return true; 2336 case ISD::SRL: 2337 if (Cst > VTBits) { 2338 Lo = DAG.getConstant(0, NVT); 2339 Hi = DAG.getConstant(0, NVT); 2340 } else if (Cst > NVTBits) { 2341 Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy)); 2342 Hi = DAG.getConstant(0, NVT); 2343 } else if (Cst == NVTBits) { 2344 Lo = InH; 2345 Hi = DAG.getConstant(0, NVT); 2346 } else { 2347 Lo = DAG.getNode(ISD::OR, NVT, 2348 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)), 2349 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy))); 2350 Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy)); 2351 } 2352 return true; 2353 case ISD::SRA: 2354 if (Cst > VTBits) { 2355 Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH, 2356 DAG.getConstant(NVTBits-1, ShTy)); 2357 } else if (Cst > NVTBits) { 2358 Lo = DAG.getNode(ISD::SRA, NVT, InH, 2359 DAG.getConstant(Cst-NVTBits, ShTy)); 2360 Hi = DAG.getNode(ISD::SRA, NVT, InH, 2361 DAG.getConstant(NVTBits-1, ShTy)); 2362 } else if (Cst == NVTBits) { 2363 Lo = InH; 2364 Hi = DAG.getNode(ISD::SRA, NVT, InH, 2365 DAG.getConstant(NVTBits-1, ShTy)); 2366 } else { 2367 Lo = DAG.getNode(ISD::OR, NVT, 2368 DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)), 2369 DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy))); 2370 Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy)); 2371 } 2372 return true; 2373 } 2374 } 2375 // FIXME: The following code for expanding shifts using ISD::SELECT is buggy, 2376 // so disable it for now. Currently targets are handling this via SHL_PARTS 2377 // and friends. 2378 return false; 2379 2380 // If we have an efficient select operation (or if the selects will all fold 2381 // away), lower to some complex code, otherwise just emit the libcall. 2382 if (TLI.getOperationAction(ISD::SELECT, NVT) != TargetLowering::Legal && 2383 !isa<ConstantSDNode>(Amt)) 2384 return false; 2385 2386 SDOperand InL, InH; 2387 ExpandOp(Op, InL, InH); 2388 SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy, // NAmt = 32-ShAmt 2389 DAG.getConstant(NVTBits, ShTy), ShAmt); 2390 2391 // Compare the unmasked shift amount against 32. 2392 SDOperand Cond = DAG.getSetCC(TLI.getSetCCResultTy(), ShAmt, 2393 DAG.getConstant(NVTBits, ShTy), ISD::SETGE); 2394 2395 if (TLI.getShiftAmountFlavor() != TargetLowering::Mask) { 2396 ShAmt = DAG.getNode(ISD::AND, ShTy, ShAmt, // ShAmt &= 31 2397 DAG.getConstant(NVTBits-1, ShTy)); 2398 NAmt = DAG.getNode(ISD::AND, ShTy, NAmt, // NAmt &= 31 2399 DAG.getConstant(NVTBits-1, ShTy)); 2400 } 2401 2402 if (Opc == ISD::SHL) { 2403 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << Amt) | (Lo >> NAmt) 2404 DAG.getNode(ISD::SHL, NVT, InH, ShAmt), 2405 DAG.getNode(ISD::SRL, NVT, InL, NAmt)); 2406 SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31 2407 2408 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 2409 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2); 2410 } else { 2411 SDOperand HiLoPart = DAG.getNode(ISD::SELECT, NVT, 2412 DAG.getSetCC(TLI.getSetCCResultTy(), NAmt, 2413 DAG.getConstant(32, ShTy), 2414 ISD::SETEQ), 2415 DAG.getConstant(0, NVT), 2416 DAG.getNode(ISD::SHL, NVT, InH, NAmt)); 2417 SDOperand T1 = DAG.getNode(ISD::OR, NVT,// T1 = (Hi << NAmt) | (Lo >> Amt) 2418 HiLoPart, 2419 DAG.getNode(ISD::SRL, NVT, InL, ShAmt)); 2420 SDOperand T2 = DAG.getNode(Opc, NVT, InH, ShAmt); // T2 = InH >> ShAmt&31 2421 2422 SDOperand HiPart; 2423 if (Opc == ISD::SRA) 2424 HiPart = DAG.getNode(ISD::SRA, NVT, InH, 2425 DAG.getConstant(NVTBits-1, ShTy)); 2426 else 2427 HiPart = DAG.getConstant(0, NVT); 2428 Lo = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); 2429 Hi = DAG.getNode(ISD::SELECT, NVT, Cond, HiPart, T2); 2430 } 2431 return true; 2432} 2433 2434/// FindLatestCallSeqStart - Scan up the dag to find the latest (highest 2435/// NodeDepth) node that is an CallSeqStart operation and occurs later than 2436/// Found. 2437static void FindLatestCallSeqStart(SDNode *Node, SDNode *&Found) { 2438 if (Node->getNodeDepth() <= Found->getNodeDepth()) return; 2439 2440 // If we found an CALLSEQ_START, we already know this node occurs later 2441 // than the Found node. Just remember this node and return. 2442 if (Node->getOpcode() == ISD::CALLSEQ_START) { 2443 Found = Node; 2444 return; 2445 } 2446 2447 // Otherwise, scan the operands of Node to see if any of them is a call. 2448 assert(Node->getNumOperands() != 0 && 2449 "All leaves should have depth equal to the entry node!"); 2450 for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i) 2451 FindLatestCallSeqStart(Node->getOperand(i).Val, Found); 2452 2453 // Tail recurse for the last iteration. 2454 FindLatestCallSeqStart(Node->getOperand(Node->getNumOperands()-1).Val, 2455 Found); 2456} 2457 2458 2459/// FindEarliestCallSeqEnd - Scan down the dag to find the earliest (lowest 2460/// NodeDepth) node that is an CallSeqEnd operation and occurs more recent 2461/// than Found. 2462static void FindEarliestCallSeqEnd(SDNode *Node, SDNode *&Found, 2463 std::set<SDNode*> &Visited) { 2464 if ((Found && Node->getNodeDepth() >= Found->getNodeDepth()) || 2465 !Visited.insert(Node).second) return; 2466 2467 // If we found an CALLSEQ_END, we already know this node occurs earlier 2468 // than the Found node. Just remember this node and return. 2469 if (Node->getOpcode() == ISD::CALLSEQ_END) { 2470 Found = Node; 2471 return; 2472 } 2473 2474 // Otherwise, scan the operands of Node to see if any of them is a call. 2475 SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); 2476 if (UI == E) return; 2477 for (--E; UI != E; ++UI) 2478 FindEarliestCallSeqEnd(*UI, Found, Visited); 2479 2480 // Tail recurse for the last iteration. 2481 FindEarliestCallSeqEnd(*UI, Found, Visited); 2482} 2483 2484/// FindCallSeqEnd - Given a chained node that is part of a call sequence, 2485/// find the CALLSEQ_END node that terminates the call sequence. 2486static SDNode *FindCallSeqEnd(SDNode *Node) { 2487 if (Node->getOpcode() == ISD::CALLSEQ_END) 2488 return Node; 2489 if (Node->use_empty()) 2490 return 0; // No CallSeqEnd 2491 2492 if (Node->hasOneUse()) // Simple case, only has one user to check. 2493 return FindCallSeqEnd(*Node->use_begin()); 2494 2495 SDOperand TheChain(Node, Node->getNumValues()-1); 2496 if (TheChain.getValueType() != MVT::Other) 2497 TheChain = SDOperand(Node, 0); 2498 assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!"); 2499 2500 for (SDNode::use_iterator UI = Node->use_begin(), 2501 E = Node->use_end(); UI != E; ++UI) { 2502 2503 // Make sure to only follow users of our token chain. 2504 SDNode *User = *UI; 2505 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 2506 if (User->getOperand(i) == TheChain) 2507 if (SDNode *Result = FindCallSeqEnd(User)) 2508 return Result; 2509 } 2510 return 0; 2511} 2512 2513/// FindCallSeqStart - Given a chained node that is part of a call sequence, 2514/// find the CALLSEQ_START node that initiates the call sequence. 2515static SDNode *FindCallSeqStart(SDNode *Node) { 2516 assert(Node && "Didn't find callseq_start for a call??"); 2517 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node; 2518 2519 assert(Node->getOperand(0).getValueType() == MVT::Other && 2520 "Node doesn't have a token chain argument!"); 2521 return FindCallSeqStart(Node->getOperand(0).Val); 2522} 2523 2524 2525/// FindInputOutputChains - If we are replacing an operation with a call we need 2526/// to find the call that occurs before and the call that occurs after it to 2527/// properly serialize the calls in the block. The returned operand is the 2528/// input chain value for the new call (e.g. the entry node or the previous 2529/// call), and OutChain is set to be the chain node to update to point to the 2530/// end of the call chain. 2531static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain, 2532 SDOperand Entry) { 2533 SDNode *LatestCallSeqStart = Entry.Val; 2534 SDNode *LatestCallSeqEnd = 0; 2535 FindLatestCallSeqStart(OpNode, LatestCallSeqStart); 2536 //std::cerr<<"Found node: "; LatestCallSeqStart->dump(); std::cerr <<"\n"; 2537 2538 // It is possible that no ISD::CALLSEQ_START was found because there is no 2539 // previous call in the function. LatestCallStackDown may in that case be 2540 // the entry node itself. Do not attempt to find a matching CALLSEQ_END 2541 // unless LatestCallStackDown is an CALLSEQ_START. 2542 if (LatestCallSeqStart->getOpcode() == ISD::CALLSEQ_START) 2543 LatestCallSeqEnd = FindCallSeqEnd(LatestCallSeqStart); 2544 else 2545 LatestCallSeqEnd = Entry.Val; 2546 assert(LatestCallSeqEnd && "NULL return from FindCallSeqEnd"); 2547 2548 // Finally, find the first call that this must come before, first we find the 2549 // CallSeqEnd that ends the call. 2550 OutChain = 0; 2551 std::set<SDNode*> Visited; 2552 FindEarliestCallSeqEnd(OpNode, OutChain, Visited); 2553 2554 // If we found one, translate from the adj up to the callseq_start. 2555 if (OutChain) 2556 OutChain = FindCallSeqStart(OutChain); 2557 2558 return SDOperand(LatestCallSeqEnd, 0); 2559} 2560 2561/// SpliceCallInto - Given the result chain of a libcall (CallResult), and a 2562void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult, 2563 SDNode *OutChain) { 2564 // Nothing to splice it into? 2565 if (OutChain == 0) return; 2566 2567 assert(OutChain->getOperand(0).getValueType() == MVT::Other); 2568 //OutChain->dump(); 2569 2570 // Form a token factor node merging the old inval and the new inval. 2571 SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult, 2572 OutChain->getOperand(0)); 2573 // Change the node to refer to the new token. 2574 OutChain->setAdjCallChain(InToken); 2575} 2576 2577 2578// ExpandLibCall - Expand a node into a call to a libcall. If the result value 2579// does not fit into a register, return the lo part and set the hi part to the 2580// by-reg argument. If it does fit into a single register, return the result 2581// and leave the Hi part unset. 2582SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node, 2583 SDOperand &Hi) { 2584 SDNode *OutChain; 2585 SDOperand InChain = FindInputOutputChains(Node, OutChain, 2586 DAG.getEntryNode()); 2587 if (InChain.Val == 0) 2588 InChain = DAG.getEntryNode(); 2589 2590 TargetLowering::ArgListTy Args; 2591 for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { 2592 MVT::ValueType ArgVT = Node->getOperand(i).getValueType(); 2593 const Type *ArgTy = MVT::getTypeForValueType(ArgVT); 2594 Args.push_back(std::make_pair(Node->getOperand(i), ArgTy)); 2595 } 2596 SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy()); 2597 2598 // Splice the libcall in wherever FindInputOutputChains tells us to. 2599 const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0)); 2600 std::pair<SDOperand,SDOperand> CallInfo = 2601 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, false, 2602 Callee, Args, DAG); 2603 SpliceCallInto(CallInfo.second, OutChain); 2604 2605 NeedsAnotherIteration = true; 2606 2607 switch (getTypeAction(CallInfo.first.getValueType())) { 2608 default: assert(0 && "Unknown thing"); 2609 case Legal: 2610 return CallInfo.first; 2611 case Promote: 2612 assert(0 && "Cannot promote this yet!"); 2613 case Expand: 2614 SDOperand Lo; 2615 ExpandOp(CallInfo.first, Lo, Hi); 2616 return Lo; 2617 } 2618} 2619 2620 2621/// ExpandIntToFP - Expand a [US]INT_TO_FP operation, assuming that the 2622/// destination type is legal. 2623SDOperand SelectionDAGLegalize:: 2624ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) { 2625 assert(getTypeAction(DestTy) == Legal && "Destination type is not legal!"); 2626 assert(getTypeAction(Source.getValueType()) == Expand && 2627 "This is not an expansion!"); 2628 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!"); 2629 2630 if (!isSigned) { 2631 assert(Source.getValueType() == MVT::i64 && 2632 "This only works for 64-bit -> FP"); 2633 // The 64-bit value loaded will be incorrectly if the 'sign bit' of the 2634 // incoming integer is set. To handle this, we dynamically test to see if 2635 // it is set, and, if so, add a fudge factor. 2636 SDOperand Lo, Hi; 2637 ExpandOp(Source, Lo, Hi); 2638 2639 // If this is unsigned, and not supported, first perform the conversion to 2640 // signed, then adjust the result if the sign bit is set. 2641 SDOperand SignedConv = ExpandIntToFP(true, DestTy, 2642 DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi)); 2643 2644 SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi, 2645 DAG.getConstant(0, Hi.getValueType()), 2646 ISD::SETLT); 2647 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4); 2648 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(), 2649 SignSet, Four, Zero); 2650 uint64_t FF = 0x5f800000ULL; 2651 if (TLI.isLittleEndian()) FF <<= 32; 2652 static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF); 2653 2654 MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); 2655 SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor), 2656 TLI.getPointerTy()); 2657 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset); 2658 SDOperand FudgeInReg; 2659 if (DestTy == MVT::f32) 2660 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, 2661 DAG.getSrcValue(NULL)); 2662 else { 2663 assert(DestTy == MVT::f64 && "Unexpected conversion"); 2664 FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), 2665 CPIdx, DAG.getSrcValue(NULL), MVT::f32); 2666 } 2667 return DAG.getNode(ISD::ADD, DestTy, SignedConv, FudgeInReg); 2668 } 2669 2670 // Check to see if the target has a custom way to lower this. If so, use it. 2671 switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) { 2672 default: assert(0 && "This action not implemented for this operation!"); 2673 case TargetLowering::Legal: 2674 case TargetLowering::Expand: 2675 break; // This case is handled below. 2676 case TargetLowering::Custom: 2677 Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source); 2678 return LegalizeOp(TLI.LowerOperation(Source, DAG)); 2679 } 2680 2681 // Expand the source, then glue it back together for the call. We must expand 2682 // the source in case it is shared (this pass of legalize must traverse it). 2683 SDOperand SrcLo, SrcHi; 2684 ExpandOp(Source, SrcLo, SrcHi); 2685 Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi); 2686 2687 SDNode *OutChain = 0; 2688 SDOperand InChain = FindInputOutputChains(Source.Val, OutChain, 2689 DAG.getEntryNode()); 2690 const char *FnName = 0; 2691 if (DestTy == MVT::f32) 2692 FnName = "__floatdisf"; 2693 else { 2694 assert(DestTy == MVT::f64 && "Unknown fp value type!"); 2695 FnName = "__floatdidf"; 2696 } 2697 2698 SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy()); 2699 2700 TargetLowering::ArgListTy Args; 2701 const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType()); 2702 2703 Args.push_back(std::make_pair(Source, ArgTy)); 2704 2705 // We don't care about token chains for libcalls. We just use the entry 2706 // node as our input and ignore the output chain. This allows us to place 2707 // calls wherever we need them to satisfy data dependences. 2708 const Type *RetTy = MVT::getTypeForValueType(DestTy); 2709 2710 std::pair<SDOperand,SDOperand> CallResult = 2711 TLI.LowerCallTo(InChain, RetTy, false, CallingConv::C, true, 2712 Callee, Args, DAG); 2713 2714 SpliceCallInto(CallResult.second, OutChain); 2715 return CallResult.first; 2716} 2717 2718 2719 2720/// ExpandOp - Expand the specified SDOperand into its two component pieces 2721/// Lo&Hi. Note that the Op MUST be an expanded type. As a result of this, the 2722/// LegalizeNodes map is filled in for any results that are not expanded, the 2723/// ExpandedNodes map is filled in for any results that are expanded, and the 2724/// Lo/Hi values are returned. 2725void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ 2726 MVT::ValueType VT = Op.getValueType(); 2727 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 2728 SDNode *Node = Op.Val; 2729 assert(getTypeAction(VT) == Expand && "Not an expanded type!"); 2730 assert(MVT::isInteger(VT) && "Cannot expand FP values!"); 2731 assert(MVT::isInteger(NVT) && NVT < VT && 2732 "Cannot expand to FP value or to larger int value!"); 2733 2734 // If there is more than one use of this, see if we already expanded it. 2735 // There is no use remembering values that only have a single use, as the map 2736 // entries will never be reused. 2737 if (!Node->hasOneUse()) { 2738 std::map<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I 2739 = ExpandedNodes.find(Op); 2740 if (I != ExpandedNodes.end()) { 2741 Lo = I->second.first; 2742 Hi = I->second.second; 2743 return; 2744 } 2745 } else { 2746 assert(!ExpandedNodes.count(Op) && "Re-expanding a node!"); 2747 } 2748 2749 // Expanding to multiple registers needs to perform an optimization step, and 2750 // is not careful to avoid operations the target does not support. Make sure 2751 // that all generated operations are legalized in the next iteration. 2752 NeedsAnotherIteration = true; 2753 2754 switch (Node->getOpcode()) { 2755 case ISD::CopyFromReg: 2756 assert(0 && "CopyFromReg must be legal!"); 2757 default: 2758 std::cerr << "NODE: "; Node->dump(); std::cerr << "\n"; 2759 assert(0 && "Do not know how to expand this operator!"); 2760 abort(); 2761 case ISD::UNDEF: 2762 Lo = DAG.getNode(ISD::UNDEF, NVT); 2763 Hi = DAG.getNode(ISD::UNDEF, NVT); 2764 break; 2765 case ISD::Constant: { 2766 uint64_t Cst = cast<ConstantSDNode>(Node)->getValue(); 2767 Lo = DAG.getConstant(Cst, NVT); 2768 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 2769 break; 2770 } 2771 2772 case ISD::BUILD_PAIR: 2773 // Legalize both operands. FIXME: in the future we should handle the case 2774 // where the two elements are not legal. 2775 assert(isTypeLegal(NVT) && "Cannot expand this multiple times yet!"); 2776 Lo = LegalizeOp(Node->getOperand(0)); 2777 Hi = LegalizeOp(Node->getOperand(1)); 2778 break; 2779 2780 case ISD::CTPOP: 2781 ExpandOp(Node->getOperand(0), Lo, Hi); 2782 Lo = DAG.getNode(ISD::ADD, NVT, // ctpop(HL) -> ctpop(H)+ctpop(L) 2783 DAG.getNode(ISD::CTPOP, NVT, Lo), 2784 DAG.getNode(ISD::CTPOP, NVT, Hi)); 2785 Hi = DAG.getConstant(0, NVT); 2786 break; 2787 2788 case ISD::CTLZ: { 2789 // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32) 2790 ExpandOp(Node->getOperand(0), Lo, Hi); 2791 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); 2792 SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi); 2793 SDOperand TopNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), HLZ, BitsC, 2794 ISD::SETNE); 2795 SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo); 2796 LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC); 2797 2798 Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart); 2799 Hi = DAG.getConstant(0, NVT); 2800 break; 2801 } 2802 2803 case ISD::CTTZ: { 2804 // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32) 2805 ExpandOp(Node->getOperand(0), Lo, Hi); 2806 SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); 2807 SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo); 2808 SDOperand BotNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), LTZ, BitsC, 2809 ISD::SETNE); 2810 SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi); 2811 HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC); 2812 2813 Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart); 2814 Hi = DAG.getConstant(0, NVT); 2815 break; 2816 } 2817 2818 case ISD::LOAD: { 2819 SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 2820 SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. 2821 Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); 2822 2823 // Increment the pointer to the other half. 2824 unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; 2825 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 2826 getIntPtrConstant(IncrementSize)); 2827 //Is this safe? declaring that the two parts of the split load 2828 //are from the same instruction? 2829 Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); 2830 2831 // Build a factor node to remember that this load is independent of the 2832 // other one. 2833 SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 2834 Hi.getValue(1)); 2835 2836 // Remember that we legalized the chain. 2837 AddLegalizedOperand(Op.getValue(1), TF); 2838 if (!TLI.isLittleEndian()) 2839 std::swap(Lo, Hi); 2840 break; 2841 } 2842 case ISD::TAILCALL: 2843 case ISD::CALL: { 2844 SDOperand Chain = LegalizeOp(Node->getOperand(0)); // Legalize the chain. 2845 SDOperand Callee = LegalizeOp(Node->getOperand(1)); // Legalize the callee. 2846 2847 bool Changed = false; 2848 std::vector<SDOperand> Ops; 2849 for (unsigned i = 2, e = Node->getNumOperands(); i != e; ++i) { 2850 Ops.push_back(LegalizeOp(Node->getOperand(i))); 2851 Changed |= Ops.back() != Node->getOperand(i); 2852 } 2853 2854 assert(Node->getNumValues() == 2 && Op.ResNo == 0 && 2855 "Can only expand a call once so far, not i64 -> i16!"); 2856 2857 std::vector<MVT::ValueType> RetTyVTs; 2858 RetTyVTs.reserve(3); 2859 RetTyVTs.push_back(NVT); 2860 RetTyVTs.push_back(NVT); 2861 RetTyVTs.push_back(MVT::Other); 2862 SDNode *NC = DAG.getCall(RetTyVTs, Chain, Callee, Ops, 2863 Node->getOpcode() == ISD::TAILCALL); 2864 Lo = SDOperand(NC, 0); 2865 Hi = SDOperand(NC, 1); 2866 2867 // Insert the new chain mapping. 2868 AddLegalizedOperand(Op.getValue(1), Hi.getValue(2)); 2869 break; 2870 } 2871 case ISD::AND: 2872 case ISD::OR: 2873 case ISD::XOR: { // Simple logical operators -> two trivial pieces. 2874 SDOperand LL, LH, RL, RH; 2875 ExpandOp(Node->getOperand(0), LL, LH); 2876 ExpandOp(Node->getOperand(1), RL, RH); 2877 Lo = DAG.getNode(Node->getOpcode(), NVT, LL, RL); 2878 Hi = DAG.getNode(Node->getOpcode(), NVT, LH, RH); 2879 break; 2880 } 2881 case ISD::SELECT: { 2882 SDOperand C, LL, LH, RL, RH; 2883 2884 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2885 case Expand: assert(0 && "It's impossible to expand bools"); 2886 case Legal: 2887 C = LegalizeOp(Node->getOperand(0)); // Legalize the condition. 2888 break; 2889 case Promote: 2890 C = PromoteOp(Node->getOperand(0)); // Promote the condition. 2891 break; 2892 } 2893 ExpandOp(Node->getOperand(1), LL, LH); 2894 ExpandOp(Node->getOperand(2), RL, RH); 2895 Lo = DAG.getNode(ISD::SELECT, NVT, C, LL, RL); 2896 Hi = DAG.getNode(ISD::SELECT, NVT, C, LH, RH); 2897 break; 2898 } 2899 case ISD::SELECT_CC: { 2900 SDOperand TL, TH, FL, FH; 2901 ExpandOp(Node->getOperand(2), TL, TH); 2902 ExpandOp(Node->getOperand(3), FL, FH); 2903 Lo = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0), 2904 Node->getOperand(1), TL, FL, Node->getOperand(4)); 2905 Hi = DAG.getNode(ISD::SELECT_CC, NVT, Node->getOperand(0), 2906 Node->getOperand(1), TH, FH, Node->getOperand(4)); 2907 Lo = LegalizeOp(Lo); 2908 Hi = LegalizeOp(Hi); 2909 break; 2910 } 2911 case ISD::SIGN_EXTEND: { 2912 SDOperand In; 2913 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2914 case Expand: assert(0 && "expand-expand not implemented yet!"); 2915 case Legal: In = LegalizeOp(Node->getOperand(0)); break; 2916 case Promote: 2917 In = PromoteOp(Node->getOperand(0)); 2918 // Emit the appropriate sign_extend_inreg to get the value we want. 2919 In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In, 2920 DAG.getValueType(Node->getOperand(0).getValueType())); 2921 break; 2922 } 2923 2924 // The low part is just a sign extension of the input (which degenerates to 2925 // a copy). 2926 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In); 2927 2928 // The high part is obtained by SRA'ing all but one of the bits of the lo 2929 // part. 2930 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 2931 Hi = DAG.getNode(ISD::SRA, NVT, Lo, DAG.getConstant(LoSize-1, 2932 TLI.getShiftAmountTy())); 2933 break; 2934 } 2935 case ISD::ZERO_EXTEND: { 2936 SDOperand In; 2937 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2938 case Expand: assert(0 && "expand-expand not implemented yet!"); 2939 case Legal: In = LegalizeOp(Node->getOperand(0)); break; 2940 case Promote: 2941 In = PromoteOp(Node->getOperand(0)); 2942 // Emit the appropriate zero_extend_inreg to get the value we want. 2943 In = DAG.getZeroExtendInReg(In, Node->getOperand(0).getValueType()); 2944 break; 2945 } 2946 2947 // The low part is just a zero extension of the input (which degenerates to 2948 // a copy). 2949 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In); 2950 2951 // The high part is just a zero. 2952 Hi = DAG.getConstant(0, NVT); 2953 break; 2954 } 2955 // These operators cannot be expanded directly, emit them as calls to 2956 // library functions. 2957 case ISD::FP_TO_SINT: 2958 if (TLI.getOperationAction(ISD::FP_TO_SINT, VT) == TargetLowering::Custom) { 2959 SDOperand Op; 2960 switch (getTypeAction(Node->getOperand(0).getValueType())) { 2961 case Expand: assert(0 && "cannot expand FP!"); 2962 case Legal: Op = LegalizeOp(Node->getOperand(0)); break; 2963 case Promote: Op = PromoteOp(Node->getOperand(0)); break; 2964 } 2965 2966 Op = TLI.LowerOperation(DAG.getNode(ISD::FP_TO_SINT, VT, Op), DAG); 2967 2968 // Now that the custom expander is done, expand the result, which is still 2969 // VT. 2970 ExpandOp(Op, Lo, Hi); 2971 break; 2972 } 2973 2974 if (Node->getOperand(0).getValueType() == MVT::f32) 2975 Lo = ExpandLibCall("__fixsfdi", Node, Hi); 2976 else 2977 Lo = ExpandLibCall("__fixdfdi", Node, Hi); 2978 break; 2979 2980 case ISD::FP_TO_UINT: 2981 if (TLI.getOperationAction(ISD::FP_TO_UINT, VT) == TargetLowering::Custom) { 2982 SDOperand Op = DAG.getNode(ISD::FP_TO_UINT, VT, 2983 LegalizeOp(Node->getOperand(0))); 2984 // Now that the custom expander is done, expand the result, which is still 2985 // VT. 2986 ExpandOp(TLI.LowerOperation(Op, DAG), Lo, Hi); 2987 break; 2988 } 2989 2990 if (Node->getOperand(0).getValueType() == MVT::f32) 2991 Lo = ExpandLibCall("__fixunssfdi", Node, Hi); 2992 else 2993 Lo = ExpandLibCall("__fixunsdfdi", Node, Hi); 2994 break; 2995 2996 case ISD::SHL: 2997 // If we can emit an efficient shift operation, do so now. 2998 if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 2999 break; 3000 3001 // If this target supports SHL_PARTS, use it. 3002 if (TLI.getOperationAction(ISD::SHL_PARTS, NVT) == TargetLowering::Legal) { 3003 ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1), 3004 Lo, Hi); 3005 break; 3006 } 3007 3008 // Otherwise, emit a libcall. 3009 Lo = ExpandLibCall("__ashldi3", Node, Hi); 3010 break; 3011 3012 case ISD::SRA: 3013 // If we can emit an efficient shift operation, do so now. 3014 if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 3015 break; 3016 3017 // If this target supports SRA_PARTS, use it. 3018 if (TLI.getOperationAction(ISD::SRA_PARTS, NVT) == TargetLowering::Legal) { 3019 ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1), 3020 Lo, Hi); 3021 break; 3022 } 3023 3024 // Otherwise, emit a libcall. 3025 Lo = ExpandLibCall("__ashrdi3", Node, Hi); 3026 break; 3027 case ISD::SRL: 3028 // If we can emit an efficient shift operation, do so now. 3029 if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi)) 3030 break; 3031 3032 // If this target supports SRL_PARTS, use it. 3033 if (TLI.getOperationAction(ISD::SRL_PARTS, NVT) == TargetLowering::Legal) { 3034 ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1), 3035 Lo, Hi); 3036 break; 3037 } 3038 3039 // Otherwise, emit a libcall. 3040 Lo = ExpandLibCall("__lshrdi3", Node, Hi); 3041 break; 3042 3043 case ISD::ADD: 3044 ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1), 3045 Lo, Hi); 3046 break; 3047 case ISD::SUB: 3048 ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1), 3049 Lo, Hi); 3050 break; 3051 case ISD::MUL: { 3052 if (TLI.getOperationAction(ISD::MULHU, NVT) == TargetLowering::Legal) { 3053 SDOperand LL, LH, RL, RH; 3054 ExpandOp(Node->getOperand(0), LL, LH); 3055 ExpandOp(Node->getOperand(1), RL, RH); 3056 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL); 3057 RH = DAG.getNode(ISD::MUL, NVT, LL, RH); 3058 LH = DAG.getNode(ISD::MUL, NVT, LH, RL); 3059 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH); 3060 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH); 3061 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL); 3062 } else { 3063 Lo = ExpandLibCall("__muldi3" , Node, Hi); break; 3064 } 3065 break; 3066 } 3067 case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break; 3068 case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break; 3069 case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break; 3070 case ISD::UREM: Lo = ExpandLibCall("__umoddi3", Node, Hi); break; 3071 } 3072 3073 // Remember in a map if the values will be reused later. 3074 if (!Node->hasOneUse()) { 3075 bool isNew = ExpandedNodes.insert(std::make_pair(Op, 3076 std::make_pair(Lo, Hi))).second; 3077 assert(isNew && "Value already expanded?!?"); 3078 } 3079} 3080 3081 3082// SelectionDAG::Legalize - This is the entry point for the file. 3083// 3084void SelectionDAG::Legalize() { 3085 /// run - This is the main entry point to this class. 3086 /// 3087 SelectionDAGLegalize(*this).Run(); 3088} 3089 3090