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