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