LegalizeTypes.cpp revision 0493715f4b23233bb29562cbd7b750b0d9ad346d
1//===-- LegalizeDAGTypes.cpp - Implement SelectionDAG::LegalizeTypes ------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner 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::LegalizeTypes method. It transforms 11// an arbitrary well-formed SelectionDAG to only consist of legal types. 12// 13//===----------------------------------------------------------------------===// 14 15#include "LegalizeTypes.h" 16#include "llvm/Constants.h" 17#include "llvm/DerivedTypes.h" 18#include "llvm/Support/MathExtras.h" 19using namespace llvm; 20 21/// run - This is the main entry point for the type legalizer. This does a 22/// top-down traversal of the dag, legalizing types as it goes. 23void DAGTypeLegalizer::run() { 24 // Create a dummy node (which is not added to allnodes), that adds a reference 25 // to the root node, preventing it from being deleted, and tracking any 26 // changes of the root. 27 HandleSDNode Dummy(DAG.getRoot()); 28 29 // The root of the dag may dangle to deleted nodes until the type legalizer is 30 // done. Set it to null to avoid confusion. 31 DAG.setRoot(SDOperand()); 32 33 // Walk all nodes in the graph, assigning them a NodeID of 'ReadyToProcess' 34 // (and remembering them) if they are leaves and assigning 'NewNode' if 35 // non-leaves. 36 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 37 E = DAG.allnodes_end(); I != E; ++I) { 38 if (I->getNumOperands() == 0) { 39 I->setNodeId(ReadyToProcess); 40 Worklist.push_back(I); 41 } else { 42 I->setNodeId(NewNode); 43 } 44 } 45 46 // Now that we have a set of nodes to process, handle them all. 47 while (!Worklist.empty()) { 48 SDNode *N = Worklist.back(); 49 Worklist.pop_back(); 50 assert(N->getNodeId() == ReadyToProcess && 51 "Node should be ready if on worklist!"); 52 53 // Scan the values produced by the node, checking to see if any result 54 // types are illegal. 55 unsigned i = 0; 56 unsigned NumResults = N->getNumValues(); 57 do { 58 MVT::ValueType ResultVT = N->getValueType(i); 59 LegalizeAction Action = getTypeAction(ResultVT); 60 if (Action == Promote) { 61 PromoteResult(N, i); 62 goto NodeDone; 63 } else if (Action == Expand) { 64 // Expand can mean 1) split integer in half 2) scalarize single-element 65 // vector 3) split vector in half. 66 if (!MVT::isVector(ResultVT)) 67 ExpandResult(N, i); 68 else if (MVT::getVectorNumElements(ResultVT) == 1) 69 ScalarizeResult(N, i); // Scalarize the single-element vector. 70 else // Split the vector in half. 71 assert(0 && "Vector splitting not implemented"); 72 goto NodeDone; 73 } else { 74 assert(Action == Legal && "Unknown action!"); 75 } 76 } while (++i < NumResults); 77 78 // Scan the operand list for the node, handling any nodes with operands that 79 // are illegal. 80 { 81 unsigned NumOperands = N->getNumOperands(); 82 bool NeedsRevisit = false; 83 for (i = 0; i != NumOperands; ++i) { 84 MVT::ValueType OpVT = N->getOperand(i).getValueType(); 85 LegalizeAction Action = getTypeAction(OpVT); 86 if (Action == Promote) { 87 NeedsRevisit = PromoteOperand(N, i); 88 break; 89 } else if (Action == Expand) { 90 // Expand can mean 1) split integer in half 2) scalarize single-element 91 // vector 3) split vector in half. 92 if (!MVT::isVector(OpVT)) { 93 NeedsRevisit = ExpandOperand(N, i); 94 } else if (MVT::getVectorNumElements(OpVT) == 1) { 95 // Scalarize the single-element vector. 96 NeedsRevisit = ScalarizeOperand(N, i); 97 } else { 98 // Split the vector in half. 99 assert(0 && "Vector splitting not implemented"); 100 } 101 break; 102 } else { 103 assert(Action == Legal && "Unknown action!"); 104 } 105 } 106 107 // If the node needs revisiting, don't add all users to the worklist etc. 108 if (NeedsRevisit) 109 continue; 110 111 if (i == NumOperands) 112 DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n"); 113 } 114NodeDone: 115 116 // If we reach here, the node was processed, potentially creating new nodes. 117 // Mark it as processed and add its users to the worklist as appropriate. 118 N->setNodeId(Processed); 119 120 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 121 UI != E; ++UI) { 122 SDNode *User = *UI; 123 int NodeID = User->getNodeId(); 124 assert(NodeID != ReadyToProcess && NodeID != Processed && 125 "Invalid node id for user of unprocessed node!"); 126 127 // This node has two options: it can either be a new node or its Node ID 128 // may be a count of the number of operands it has that are not ready. 129 if (NodeID > 0) { 130 User->setNodeId(NodeID-1); 131 132 // If this was the last use it was waiting on, add it to the ready list. 133 if (NodeID-1 == ReadyToProcess) 134 Worklist.push_back(User); 135 continue; 136 } 137 138 // Otherwise, this node is new: this is the first operand of it that 139 // became ready. Its new NodeID is the number of operands it has minus 1 140 // (as this node is now processed). 141 assert(NodeID == NewNode && "Unknown node ID!"); 142 User->setNodeId(User->getNumOperands()-1); 143 144 // If the node only has a single operand, it is now ready. 145 if (User->getNumOperands() == 1) 146 Worklist.push_back(User); 147 } 148 } 149 150 // If the root changed (e.g. it was a dead load, update the root). 151 DAG.setRoot(Dummy.getValue()); 152 153 //DAG.viewGraph(); 154 155 // Remove dead nodes. This is important to do for cleanliness but also before 156 // the checking loop below. Implicit folding by the DAG.getNode operators can 157 // cause unreachable nodes to be around with their flags set to new. 158 DAG.RemoveDeadNodes(); 159 160 // In a debug build, scan all the nodes to make sure we found them all. This 161 // ensures that there are no cycles and that everything got processed. 162#ifndef NDEBUG 163 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 164 E = DAG.allnodes_end(); I != E; ++I) { 165 if (I->getNodeId() == Processed) 166 continue; 167 cerr << "Unprocessed node: "; 168 I->dump(&DAG); cerr << "\n"; 169 170 if (I->getNodeId() == NewNode) 171 cerr << "New node not 'noticed'?\n"; 172 else if (I->getNodeId() > 0) 173 cerr << "Operand not processed?\n"; 174 else if (I->getNodeId() == ReadyToProcess) 175 cerr << "Not added to worklist?\n"; 176 abort(); 177 } 178#endif 179} 180 181/// MarkNewNodes - The specified node is the root of a subtree of potentially 182/// new nodes. Add the correct NodeId to mark it. 183void DAGTypeLegalizer::MarkNewNodes(SDNode *N) { 184 // If this was an existing node that is already done, we're done. 185 if (N->getNodeId() != NewNode) 186 return; 187 188 // Okay, we know that this node is new. Recursively walk all of its operands 189 // to see if they are new also. The depth of this walk is bounded by the size 190 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 191 // about revisiting of nodes. 192 // 193 // As we walk the operands, keep track of the number of nodes that are 194 // processed. If non-zero, this will become the new nodeid of this node. 195 unsigned NumProcessed = 0; 196 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 197 int OpId = N->getOperand(i).Val->getNodeId(); 198 if (OpId == NewNode) 199 MarkNewNodes(N->getOperand(i).Val); 200 else if (OpId == Processed) 201 ++NumProcessed; 202 } 203 204 N->setNodeId(N->getNumOperands()-NumProcessed); 205 if (N->getNodeId() == ReadyToProcess) 206 Worklist.push_back(N); 207} 208 209/// ReplaceValueWith - The specified value was legalized to the specified other 210/// value. If they are different, update the DAG and NodeIDs replacing any uses 211/// of From to use To instead. 212void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) { 213 if (From == To) return; 214 215 // If expansion produced new nodes, make sure they are properly marked. 216 if (To.Val->getNodeId() == NewNode) 217 MarkNewNodes(To.Val); 218 219 // Anything that used the old node should now use the new one. Note that this 220 // can potentially cause recursive merging. 221 DAG.ReplaceAllUsesOfValueWith(From, To); 222 223 // The old node may still be present in ExpandedNodes or PromotedNodes. 224 // Inform them about the replacement. 225 ReplacedNodes[From] = To; 226 227 // Since we just made an unstructured update to the DAG, which could wreak 228 // general havoc on anything that once used From and now uses To, walk all 229 // users of the result, updating their flags. 230 for (SDNode::use_iterator I = To.Val->use_begin(), E = To.Val->use_end(); 231 I != E; ++I) { 232 SDNode *User = *I; 233 // If the node isn't already processed or in the worklist, mark it as new, 234 // then use MarkNewNodes to recompute its ID. 235 int NodeId = User->getNodeId(); 236 if (NodeId != ReadyToProcess && NodeId != Processed) { 237 User->setNodeId(NewNode); 238 MarkNewNodes(User); 239 } 240 } 241} 242 243/// ReplaceNodeWith - Replace uses of the 'from' node's results with the 'to' 244/// node's results. The from and to node must define identical result types. 245void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) { 246 if (From == To) return; 247 assert(From->getNumValues() == To->getNumValues() && 248 "Node results don't match"); 249 250 // If expansion produced new nodes, make sure they are properly marked. 251 if (To->getNodeId() == NewNode) 252 MarkNewNodes(To); 253 254 // Anything that used the old node should now use the new one. Note that this 255 // can potentially cause recursive merging. 256 DAG.ReplaceAllUsesWith(From, To); 257 258 // The old node may still be present in ExpandedNodes or PromotedNodes. 259 // Inform them about the replacement. 260 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) { 261 assert(From->getValueType(i) == To->getValueType(i) && 262 "Node results don't match"); 263 ReplacedNodes[SDOperand(From, i)] = SDOperand(To, i); 264 } 265 266 // Since we just made an unstructured update to the DAG, which could wreak 267 // general havoc on anything that once used From and now uses To, walk all 268 // users of the result, updating their flags. 269 for (SDNode::use_iterator I = To->use_begin(), E = To->use_end();I != E; ++I){ 270 SDNode *User = *I; 271 // If the node isn't already processed or in the worklist, mark it as new, 272 // then use MarkNewNodes to recompute its ID. 273 int NodeId = User->getNodeId(); 274 if (NodeId != ReadyToProcess && NodeId != Processed) { 275 User->setNodeId(NewNode); 276 MarkNewNodes(User); 277 } 278 } 279} 280 281 282/// RemapNode - If the specified value was already legalized to another value, 283/// replace it by that value. 284void DAGTypeLegalizer::RemapNode(SDOperand &N) { 285 DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.find(N); 286 if (I != ReplacedNodes.end()) { 287 // Use path compression to speed up future lookups if values get multiply 288 // replaced with other values. 289 RemapNode(I->second); 290 N = I->second; 291 } 292} 293 294void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) { 295 if (Result.Val->getNodeId() == NewNode) 296 MarkNewNodes(Result.Val); 297 298 SDOperand &OpEntry = PromotedNodes[Op]; 299 assert(OpEntry.Val == 0 && "Node is already promoted!"); 300 OpEntry = Result; 301} 302 303void DAGTypeLegalizer::SetScalarizedOp(SDOperand Op, SDOperand Result) { 304 if (Result.Val->getNodeId() == NewNode) 305 MarkNewNodes(Result.Val); 306 307 SDOperand &OpEntry = ScalarizedNodes[Op]; 308 assert(OpEntry.Val == 0 && "Node is already scalarized!"); 309 OpEntry = Result; 310} 311 312 313void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo, 314 SDOperand &Hi) { 315 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; 316 RemapNode(Entry.first); 317 RemapNode(Entry.second); 318 assert(Entry.first.Val && "Operand isn't expanded"); 319 Lo = Entry.first; 320 Hi = Entry.second; 321} 322 323void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo, 324 SDOperand Hi) { 325 // Remember that this is the result of the node. 326 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; 327 assert(Entry.first.Val == 0 && "Node already expanded"); 328 Entry.first = Lo; 329 Entry.second = Hi; 330 331 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 332 if (Lo.Val->getNodeId() == NewNode) 333 MarkNewNodes(Lo.Val); 334 if (Hi.Val->getNodeId() == NewNode) 335 MarkNewNodes(Hi.Val); 336} 337 338SDOperand DAGTypeLegalizer::CreateStackStoreLoad(SDOperand Op, 339 MVT::ValueType DestVT) { 340 // Create the stack frame object. 341 SDOperand FIPtr = DAG.CreateStackTemporary(DestVT); 342 343 // Emit a store to the stack slot. 344 SDOperand Store = DAG.getStore(DAG.getEntryNode(), Op, FIPtr, NULL, 0); 345 // Result is a load from the stack slot. 346 return DAG.getLoad(DestVT, Store, FIPtr, NULL, 0); 347} 348 349/// HandleMemIntrinsic - This handles memcpy/memset/memmove with invalid 350/// operands. This promotes or expands the operands as required. 351SDOperand DAGTypeLegalizer::HandleMemIntrinsic(SDNode *N) { 352 // The chain and pointer [operands #0 and #1] are always valid types. 353 SDOperand Chain = N->getOperand(0); 354 SDOperand Ptr = N->getOperand(1); 355 SDOperand Op2 = N->getOperand(2); 356 357 // Op #2 is either a value (memset) or a pointer. Promote it if required. 358 switch (getTypeAction(Op2.getValueType())) { 359 default: assert(0 && "Unknown action for pointer/value operand"); 360 case Legal: break; 361 case Promote: Op2 = GetPromotedOp(Op2); break; 362 } 363 364 // The length could have any action required. 365 SDOperand Length = N->getOperand(3); 366 switch (getTypeAction(Length.getValueType())) { 367 default: assert(0 && "Unknown action for memop operand"); 368 case Legal: break; 369 case Promote: Length = GetPromotedZExtOp(Length); break; 370 case Expand: 371 SDOperand Dummy; // discard the high part. 372 GetExpandedOp(Length, Length, Dummy); 373 break; 374 } 375 376 SDOperand Align = N->getOperand(4); 377 switch (getTypeAction(Align.getValueType())) { 378 default: assert(0 && "Unknown action for memop operand"); 379 case Legal: break; 380 case Promote: Align = GetPromotedZExtOp(Align); break; 381 } 382 383 SDOperand AlwaysInline = N->getOperand(5); 384 switch (getTypeAction(AlwaysInline.getValueType())) { 385 default: assert(0 && "Unknown action for memop operand"); 386 case Legal: break; 387 case Promote: AlwaysInline = GetPromotedZExtOp(AlwaysInline); break; 388 } 389 390 SDOperand Ops[] = { Chain, Ptr, Op2, Length, Align, AlwaysInline }; 391 return DAG.UpdateNodeOperands(SDOperand(N, 0), Ops, 6); 392} 393 394/// SplitOp - Return the lower and upper halves of Op's bits in a value type 395/// half the size of Op's. 396void DAGTypeLegalizer::SplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) { 397 unsigned NVTBits = MVT::getSizeInBits(Op.getValueType())/2; 398 assert(MVT::getSizeInBits(Op.getValueType()) == 2*NVTBits && 399 "Cannot split odd sized integer type"); 400 MVT::ValueType NVT = MVT::getIntegerType(NVTBits); 401 Lo = DAG.getNode(ISD::TRUNCATE, NVT, Op); 402 Hi = DAG.getNode(ISD::SRL, Op.getValueType(), Op, 403 DAG.getConstant(NVTBits, TLI.getShiftAmountTy())); 404 Hi = DAG.getNode(ISD::TRUNCATE, NVT, Hi); 405} 406 407 408//===----------------------------------------------------------------------===// 409// Result Promotion 410//===----------------------------------------------------------------------===// 411 412/// PromoteResult - This method is called when a result of a node is found to be 413/// in need of promotion to a larger type. At this point, the node may also 414/// have invalid operands or may have other results that need expansion, we just 415/// know that (at least) one result needs promotion. 416void DAGTypeLegalizer::PromoteResult(SDNode *N, unsigned ResNo) { 417 DEBUG(cerr << "Promote node result: "; N->dump(&DAG); cerr << "\n"); 418 SDOperand Result = SDOperand(); 419 420 switch (N->getOpcode()) { 421 default: 422#ifndef NDEBUG 423 cerr << "PromoteResult #" << ResNo << ": "; 424 N->dump(&DAG); cerr << "\n"; 425#endif 426 assert(0 && "Do not know how to promote this operator!"); 427 abort(); 428 case ISD::UNDEF: Result = PromoteResult_UNDEF(N); break; 429 case ISD::Constant: Result = PromoteResult_Constant(N); break; 430 431 case ISD::TRUNCATE: Result = PromoteResult_TRUNCATE(N); break; 432 case ISD::SIGN_EXTEND: 433 case ISD::ZERO_EXTEND: 434 case ISD::ANY_EXTEND: Result = PromoteResult_INT_EXTEND(N); break; 435 case ISD::FP_ROUND: Result = PromoteResult_FP_ROUND(N); break; 436 case ISD::FP_TO_SINT: 437 case ISD::FP_TO_UINT: Result = PromoteResult_FP_TO_XINT(N); break; 438 case ISD::SETCC: Result = PromoteResult_SETCC(N); break; 439 case ISD::LOAD: Result = PromoteResult_LOAD(cast<LoadSDNode>(N)); break; 440 441 case ISD::AND: 442 case ISD::OR: 443 case ISD::XOR: 444 case ISD::ADD: 445 case ISD::SUB: 446 case ISD::MUL: Result = PromoteResult_SimpleIntBinOp(N); break; 447 448 case ISD::SDIV: 449 case ISD::SREM: Result = PromoteResult_SDIV(N); break; 450 451 case ISD::UDIV: 452 case ISD::UREM: Result = PromoteResult_UDIV(N); break; 453 454 case ISD::SHL: Result = PromoteResult_SHL(N); break; 455 case ISD::SRA: Result = PromoteResult_SRA(N); break; 456 case ISD::SRL: Result = PromoteResult_SRL(N); break; 457 458 case ISD::SELECT: Result = PromoteResult_SELECT(N); break; 459 case ISD::SELECT_CC: Result = PromoteResult_SELECT_CC(N); break; 460 461 } 462 463 // If Result is null, the sub-method took care of registering the result. 464 if (Result.Val) 465 SetPromotedOp(SDOperand(N, ResNo), Result); 466} 467 468SDOperand DAGTypeLegalizer::PromoteResult_UNDEF(SDNode *N) { 469 return DAG.getNode(ISD::UNDEF, TLI.getTypeToTransformTo(N->getValueType(0))); 470} 471 472SDOperand DAGTypeLegalizer::PromoteResult_Constant(SDNode *N) { 473 MVT::ValueType VT = N->getValueType(0); 474 // Zero extend things like i1, sign extend everything else. It shouldn't 475 // matter in theory which one we pick, but this tends to give better code? 476 unsigned Opc = VT != MVT::i1 ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND; 477 SDOperand Result = DAG.getNode(Opc, TLI.getTypeToTransformTo(VT), 478 SDOperand(N, 0)); 479 assert(isa<ConstantSDNode>(Result) && "Didn't constant fold ext?"); 480 return Result; 481} 482 483SDOperand DAGTypeLegalizer::PromoteResult_TRUNCATE(SDNode *N) { 484 SDOperand Res; 485 486 switch (getTypeAction(N->getOperand(0).getValueType())) { 487 default: assert(0 && "Unknown type action!"); 488 case Legal: 489 case Expand: 490 Res = N->getOperand(0); 491 break; 492 case Promote: 493 Res = GetPromotedOp(N->getOperand(0)); 494 break; 495 } 496 497 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 498 assert(MVT::getSizeInBits(Res.getValueType()) >= MVT::getSizeInBits(NVT) && 499 "Truncation doesn't make sense!"); 500 if (Res.getValueType() == NVT) 501 return Res; 502 503 // Truncate to NVT instead of VT 504 return DAG.getNode(ISD::TRUNCATE, NVT, Res); 505} 506 507SDOperand DAGTypeLegalizer::PromoteResult_INT_EXTEND(SDNode *N) { 508 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 509 510 if (getTypeAction(N->getOperand(0).getValueType()) == Promote) { 511 SDOperand Res = GetPromotedOp(N->getOperand(0)); 512 assert(MVT::getSizeInBits(Res.getValueType()) <= MVT::getSizeInBits(NVT) && 513 "Extension doesn't make sense!"); 514 515 // If the result and operand types are the same after promotion, simplify 516 // to an in-register extension. 517 if (NVT == Res.getValueType()) { 518 // The high bits are not guaranteed to be anything. Insert an extend. 519 if (N->getOpcode() == ISD::SIGN_EXTEND) 520 return DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Res, 521 DAG.getValueType(N->getOperand(0).getValueType())); 522 if (N->getOpcode() == ISD::ZERO_EXTEND) 523 return DAG.getZeroExtendInReg(Res, N->getOperand(0).getValueType()); 524 assert(N->getOpcode() == ISD::ANY_EXTEND && "Unknown integer extension!"); 525 return Res; 526 } 527 } 528 529 // Otherwise, just extend the original operand all the way to the larger type. 530 return DAG.getNode(N->getOpcode(), NVT, N->getOperand(0)); 531} 532 533SDOperand DAGTypeLegalizer::PromoteResult_FP_ROUND(SDNode *N) { 534 // NOTE: Assumes input is legal. 535 return DAG.getNode(ISD::FP_ROUND_INREG, N->getOperand(0).getValueType(), 536 N->getOperand(0), DAG.getValueType(N->getValueType(0))); 537} 538 539SDOperand DAGTypeLegalizer::PromoteResult_FP_TO_XINT(SDNode *N) { 540 SDOperand Op = N->getOperand(0); 541 // If the operand needed to be promoted, do so now. 542 if (getTypeAction(Op.getValueType()) == Promote) 543 // The input result is prerounded, so we don't have to do anything special. 544 Op = GetPromotedOp(Op); 545 546 unsigned NewOpc = N->getOpcode(); 547 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 548 549 // If we're promoting a UINT to a larger size, check to see if the new node 550 // will be legal. If it isn't, check to see if FP_TO_SINT is legal, since 551 // we can use that instead. This allows us to generate better code for 552 // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not 553 // legal, such as PowerPC. 554 if (N->getOpcode() == ISD::FP_TO_UINT) { 555 if (!TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) && 556 (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) || 557 TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom)) 558 NewOpc = ISD::FP_TO_SINT; 559 } 560 561 return DAG.getNode(NewOpc, NVT, Op); 562} 563 564SDOperand DAGTypeLegalizer::PromoteResult_SETCC(SDNode *N) { 565 assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??"); 566 return DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), N->getOperand(0), 567 N->getOperand(1), N->getOperand(2)); 568} 569 570SDOperand DAGTypeLegalizer::PromoteResult_LOAD(LoadSDNode *N) { 571 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 572 ISD::LoadExtType ExtType = 573 ISD::isNON_EXTLoad(N) ? ISD::EXTLOAD : N->getExtensionType(); 574 SDOperand Res = DAG.getExtLoad(ExtType, NVT, N->getChain(), N->getBasePtr(), 575 N->getSrcValue(), N->getSrcValueOffset(), 576 N->getLoadedVT(), N->isVolatile(), 577 N->getAlignment()); 578 579 // Legalized the chain result - switch anything that used the old chain to 580 // use the new one. 581 ReplaceValueWith(SDOperand(N, 1), Res.getValue(1)); 582 return Res; 583} 584 585SDOperand DAGTypeLegalizer::PromoteResult_SimpleIntBinOp(SDNode *N) { 586 // The input may have strange things in the top bits of the registers, but 587 // these operations don't care. They may have weird bits going out, but 588 // that too is okay if they are integer operations. 589 SDOperand LHS = GetPromotedOp(N->getOperand(0)); 590 SDOperand RHS = GetPromotedOp(N->getOperand(1)); 591 return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS); 592} 593 594SDOperand DAGTypeLegalizer::PromoteResult_SDIV(SDNode *N) { 595 // Sign extend the input. 596 SDOperand LHS = GetPromotedOp(N->getOperand(0)); 597 SDOperand RHS = GetPromotedOp(N->getOperand(1)); 598 MVT::ValueType VT = N->getValueType(0); 599 LHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, LHS.getValueType(), LHS, 600 DAG.getValueType(VT)); 601 RHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, RHS.getValueType(), RHS, 602 DAG.getValueType(VT)); 603 604 return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS); 605} 606 607SDOperand DAGTypeLegalizer::PromoteResult_UDIV(SDNode *N) { 608 // Zero extend the input. 609 SDOperand LHS = GetPromotedOp(N->getOperand(0)); 610 SDOperand RHS = GetPromotedOp(N->getOperand(1)); 611 MVT::ValueType VT = N->getValueType(0); 612 LHS = DAG.getZeroExtendInReg(LHS, VT); 613 RHS = DAG.getZeroExtendInReg(RHS, VT); 614 615 return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS); 616} 617 618SDOperand DAGTypeLegalizer::PromoteResult_SHL(SDNode *N) { 619 return DAG.getNode(ISD::SHL, TLI.getTypeToTransformTo(N->getValueType(0)), 620 GetPromotedOp(N->getOperand(0)), N->getOperand(1)); 621} 622 623SDOperand DAGTypeLegalizer::PromoteResult_SRA(SDNode *N) { 624 // The input value must be properly sign extended. 625 MVT::ValueType VT = N->getValueType(0); 626 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 627 SDOperand Res = GetPromotedOp(N->getOperand(0)); 628 Res = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Res, DAG.getValueType(VT)); 629 return DAG.getNode(ISD::SRA, NVT, Res, N->getOperand(1)); 630} 631 632SDOperand DAGTypeLegalizer::PromoteResult_SRL(SDNode *N) { 633 // The input value must be properly zero extended. 634 MVT::ValueType VT = N->getValueType(0); 635 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 636 SDOperand Res = GetPromotedZExtOp(N->getOperand(0)); 637 return DAG.getNode(ISD::SRL, NVT, Res, N->getOperand(1)); 638} 639 640SDOperand DAGTypeLegalizer::PromoteResult_SELECT(SDNode *N) { 641 SDOperand LHS = GetPromotedOp(N->getOperand(1)); 642 SDOperand RHS = GetPromotedOp(N->getOperand(2)); 643 return DAG.getNode(ISD::SELECT, LHS.getValueType(), N->getOperand(0),LHS,RHS); 644} 645 646SDOperand DAGTypeLegalizer::PromoteResult_SELECT_CC(SDNode *N) { 647 SDOperand LHS = GetPromotedOp(N->getOperand(2)); 648 SDOperand RHS = GetPromotedOp(N->getOperand(3)); 649 return DAG.getNode(ISD::SELECT_CC, LHS.getValueType(), N->getOperand(0), 650 N->getOperand(1), LHS, RHS, N->getOperand(4)); 651} 652 653 654//===----------------------------------------------------------------------===// 655// Result Expansion 656//===----------------------------------------------------------------------===// 657 658/// ExpandResult - This method is called when the specified result of the 659/// specified node is found to need expansion. At this point, the node may also 660/// have invalid operands or may have other results that need promotion, we just 661/// know that (at least) one result needs expansion. 662void DAGTypeLegalizer::ExpandResult(SDNode *N, unsigned ResNo) { 663 DEBUG(cerr << "Expand node result: "; N->dump(&DAG); cerr << "\n"); 664 SDOperand Lo, Hi; 665 Lo = Hi = SDOperand(); 666 667 // See if the target wants to custom expand this node. 668 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) == 669 TargetLowering::Custom) { 670 // If the target wants to, allow it to lower this itself. 671 if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) { 672 // Everything that once used N now uses P. We are guaranteed that the 673 // result value types of N and the result value types of P match. 674 ReplaceNodeWith(N, P); 675 return; 676 } 677 } 678 679 switch (N->getOpcode()) { 680 default: 681#ifndef NDEBUG 682 cerr << "ExpandResult #" << ResNo << ": "; 683 N->dump(&DAG); cerr << "\n"; 684#endif 685 assert(0 && "Do not know how to expand the result of this operator!"); 686 abort(); 687 688 case ISD::UNDEF: ExpandResult_UNDEF(N, Lo, Hi); break; 689 case ISD::Constant: ExpandResult_Constant(N, Lo, Hi); break; 690 case ISD::BUILD_PAIR: ExpandResult_BUILD_PAIR(N, Lo, Hi); break; 691 case ISD::MERGE_VALUES: ExpandResult_MERGE_VALUES(N, Lo, Hi); break; 692 case ISD::ANY_EXTEND: ExpandResult_ANY_EXTEND(N, Lo, Hi); break; 693 case ISD::ZERO_EXTEND: ExpandResult_ZERO_EXTEND(N, Lo, Hi); break; 694 case ISD::SIGN_EXTEND: ExpandResult_SIGN_EXTEND(N, Lo, Hi); break; 695 case ISD::BIT_CONVERT: ExpandResult_BIT_CONVERT(N, Lo, Hi); break; 696 case ISD::SIGN_EXTEND_INREG: ExpandResult_SIGN_EXTEND_INREG(N, Lo, Hi); break; 697 case ISD::LOAD: ExpandResult_LOAD(cast<LoadSDNode>(N), Lo, Hi); break; 698 699 case ISD::AND: 700 case ISD::OR: 701 case ISD::XOR: ExpandResult_Logical(N, Lo, Hi); break; 702 case ISD::BSWAP: ExpandResult_BSWAP(N, Lo, Hi); break; 703 case ISD::ADD: 704 case ISD::SUB: ExpandResult_ADDSUB(N, Lo, Hi); break; 705 case ISD::ADDC: 706 case ISD::SUBC: ExpandResult_ADDSUBC(N, Lo, Hi); break; 707 case ISD::ADDE: 708 case ISD::SUBE: ExpandResult_ADDSUBE(N, Lo, Hi); break; 709 case ISD::SELECT: ExpandResult_SELECT(N, Lo, Hi); break; 710 case ISD::SELECT_CC: ExpandResult_SELECT_CC(N, Lo, Hi); break; 711 case ISD::MUL: ExpandResult_MUL(N, Lo, Hi); break; 712 case ISD::SHL: 713 case ISD::SRA: 714 case ISD::SRL: ExpandResult_Shift(N, Lo, Hi); break; 715 } 716 717 // If Lo/Hi is null, the sub-method took care of registering results etc. 718 if (Lo.Val) 719 SetExpandedOp(SDOperand(N, ResNo), Lo, Hi); 720} 721 722void DAGTypeLegalizer::ExpandResult_UNDEF(SDNode *N, 723 SDOperand &Lo, SDOperand &Hi) { 724 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 725 Lo = Hi = DAG.getNode(ISD::UNDEF, NVT); 726} 727 728void DAGTypeLegalizer::ExpandResult_Constant(SDNode *N, 729 SDOperand &Lo, SDOperand &Hi) { 730 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 731 uint64_t Cst = cast<ConstantSDNode>(N)->getValue(); 732 Lo = DAG.getConstant(Cst, NVT); 733 Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); 734} 735 736void DAGTypeLegalizer::ExpandResult_BUILD_PAIR(SDNode *N, 737 SDOperand &Lo, SDOperand &Hi) { 738 // Return the operands. 739 Lo = N->getOperand(0); 740 Hi = N->getOperand(1); 741} 742 743void DAGTypeLegalizer::ExpandResult_MERGE_VALUES(SDNode *N, 744 SDOperand &Lo, SDOperand &Hi) { 745 // A MERGE_VALUES node can produce any number of values. We know that the 746 // first illegal one needs to be expanded into Lo/Hi. 747 unsigned i; 748 749 // The string of legal results gets turns into the input operands, which have 750 // the same type. 751 for (i = 0; isTypeLegal(N->getValueType(i)); ++i) 752 ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i))); 753 754 // The first illegal result must be the one that needs to be expanded. 755 GetExpandedOp(N->getOperand(i), Lo, Hi); 756 757 // Legalize the rest of the results into the input operands whether they are 758 // legal or not. 759 unsigned e = N->getNumValues(); 760 for (++i; i != e; ++i) 761 ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i))); 762} 763 764void DAGTypeLegalizer::ExpandResult_ANY_EXTEND(SDNode *N, 765 SDOperand &Lo, SDOperand &Hi) { 766 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 767 SDOperand Op = N->getOperand(0); 768 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) { 769 // The low part is any extension of the input (which degenerates to a copy). 770 Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Op); 771 Hi = DAG.getNode(ISD::UNDEF, NVT); // The high part is undefined. 772 } else { 773 // For example, extension of an i48 to an i64. The operand type necessarily 774 // promotes to the result type, so will end up being expanded too. 775 assert(getTypeAction(Op.getValueType()) == Promote && 776 "Don't know how to expand this result!"); 777 SDOperand Res = GetPromotedOp(Op); 778 assert(Res.getValueType() == N->getValueType(0) && 779 "Operand over promoted?"); 780 // Split the promoted operand. This will simplify when it is expanded. 781 SplitOp(Res, Lo, Hi); 782 } 783} 784 785void DAGTypeLegalizer::ExpandResult_ZERO_EXTEND(SDNode *N, 786 SDOperand &Lo, SDOperand &Hi) { 787 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 788 SDOperand Op = N->getOperand(0); 789 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) { 790 // The low part is zero extension of the input (which degenerates to a copy). 791 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, N->getOperand(0)); 792 Hi = DAG.getConstant(0, NVT); // The high part is just a zero. 793 } else { 794 // For example, extension of an i48 to an i64. The operand type necessarily 795 // promotes to the result type, so will end up being expanded too. 796 assert(getTypeAction(Op.getValueType()) == Promote && 797 "Don't know how to expand this result!"); 798 SDOperand Res = GetPromotedOp(Op); 799 assert(Res.getValueType() == N->getValueType(0) && 800 "Operand over promoted?"); 801 // Split the promoted operand. This will simplify when it is expanded. 802 SplitOp(Res, Lo, Hi); 803 unsigned ExcessBits = 804 MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT); 805 Hi = DAG.getZeroExtendInReg(Hi, MVT::getIntegerType(ExcessBits)); 806 } 807} 808 809void DAGTypeLegalizer::ExpandResult_SIGN_EXTEND(SDNode *N, 810 SDOperand &Lo, SDOperand &Hi) { 811 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 812 SDOperand Op = N->getOperand(0); 813 if (MVT::getSizeInBits(Op.getValueType()) <= MVT::getSizeInBits(NVT)) { 814 // The low part is sign extension of the input (which degenerates to a copy). 815 Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, N->getOperand(0)); 816 // The high part is obtained by SRA'ing all but one of the bits of low part. 817 unsigned LoSize = MVT::getSizeInBits(NVT); 818 Hi = DAG.getNode(ISD::SRA, NVT, Lo, 819 DAG.getConstant(LoSize-1, TLI.getShiftAmountTy())); 820 } else { 821 // For example, extension of an i48 to an i64. The operand type necessarily 822 // promotes to the result type, so will end up being expanded too. 823 assert(getTypeAction(Op.getValueType()) == Promote && 824 "Don't know how to expand this result!"); 825 SDOperand Res = GetPromotedOp(Op); 826 assert(Res.getValueType() == N->getValueType(0) && 827 "Operand over promoted?"); 828 // Split the promoted operand. This will simplify when it is expanded. 829 SplitOp(Res, Lo, Hi); 830 unsigned ExcessBits = 831 MVT::getSizeInBits(Op.getValueType()) - MVT::getSizeInBits(NVT); 832 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi, 833 DAG.getValueType(MVT::getIntegerType(ExcessBits))); 834 } 835} 836 837void DAGTypeLegalizer::ExpandResult_BIT_CONVERT(SDNode *N, 838 SDOperand &Lo, SDOperand &Hi) { 839 // Lower the bit-convert to a store/load from the stack, then expand the load. 840 SDOperand Op = CreateStackStoreLoad(N->getOperand(0), N->getValueType(0)); 841 ExpandResult_LOAD(cast<LoadSDNode>(Op.Val), Lo, Hi); 842} 843 844void DAGTypeLegalizer:: 845ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi) { 846 GetExpandedOp(N->getOperand(0), Lo, Hi); 847 MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT(); 848 849 if (MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(Lo.getValueType())) { 850 // sext_inreg the low part if needed. 851 Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, Lo.getValueType(), Lo, 852 N->getOperand(1)); 853 854 // The high part gets the sign extension from the lo-part. This handles 855 // things like sextinreg V:i64 from i8. 856 Hi = DAG.getNode(ISD::SRA, Hi.getValueType(), Lo, 857 DAG.getConstant(MVT::getSizeInBits(Hi.getValueType())-1, 858 TLI.getShiftAmountTy())); 859 } else { 860 // For example, extension of an i48 to an i64. Leave the low part alone, 861 // sext_inreg the high part. 862 unsigned ExcessBits = 863 MVT::getSizeInBits(EVT) - MVT::getSizeInBits(Lo.getValueType()); 864 Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, Hi.getValueType(), Hi, 865 DAG.getValueType(MVT::getIntegerType(ExcessBits))); 866 } 867} 868 869void DAGTypeLegalizer::ExpandResult_LOAD(LoadSDNode *N, 870 SDOperand &Lo, SDOperand &Hi) { 871 MVT::ValueType VT = N->getValueType(0); 872 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 873 SDOperand Ch = N->getChain(); // Legalize the chain. 874 SDOperand Ptr = N->getBasePtr(); // Legalize the pointer. 875 ISD::LoadExtType ExtType = N->getExtensionType(); 876 int SVOffset = N->getSrcValueOffset(); 877 unsigned Alignment = N->getAlignment(); 878 bool isVolatile = N->isVolatile(); 879 880 assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!"); 881 882 if (ExtType == ISD::NON_EXTLOAD) { 883 Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset, 884 isVolatile, Alignment); 885 // Increment the pointer to the other half. 886 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8; 887 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 888 getIntPtrConstant(IncrementSize)); 889 Hi = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset+IncrementSize, 890 isVolatile, MinAlign(Alignment, IncrementSize)); 891 892 // Build a factor node to remember that this load is independent of the 893 // other one. 894 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 895 Hi.getValue(1)); 896 897 // Handle endianness of the load. 898 if (!TLI.isLittleEndian()) 899 std::swap(Lo, Hi); 900 } else if (MVT::getSizeInBits(N->getLoadedVT()) <= MVT::getSizeInBits(NVT)) { 901 MVT::ValueType EVT = N->getLoadedVT(); 902 903 Lo = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset, EVT, 904 isVolatile, Alignment); 905 906 // Remember the chain. 907 Ch = Lo.getValue(1); 908 909 if (ExtType == ISD::SEXTLOAD) { 910 // The high part is obtained by SRA'ing all but one of the bits of the 911 // lo part. 912 unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); 913 Hi = DAG.getNode(ISD::SRA, NVT, Lo, 914 DAG.getConstant(LoSize-1, TLI.getShiftAmountTy())); 915 } else if (ExtType == ISD::ZEXTLOAD) { 916 // The high part is just a zero. 917 Hi = DAG.getConstant(0, NVT); 918 } else { 919 assert(ExtType == ISD::EXTLOAD && "Unknown extload!"); 920 // The high part is undefined. 921 Hi = DAG.getNode(ISD::UNDEF, NVT); 922 } 923 } else if (TLI.isLittleEndian()) { 924 // Little-endian - low bits are at low addresses. 925 Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset, 926 isVolatile, Alignment); 927 928 unsigned ExcessBits = 929 MVT::getSizeInBits(N->getLoadedVT()) - MVT::getSizeInBits(NVT); 930 MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits); 931 932 // Increment the pointer to the other half. 933 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8; 934 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 935 getIntPtrConstant(IncrementSize)); 936 Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), 937 SVOffset+IncrementSize, NEVT, 938 isVolatile, MinAlign(Alignment, IncrementSize)); 939 940 // Build a factor node to remember that this load is independent of the 941 // other one. 942 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 943 Hi.getValue(1)); 944 } else { 945 // Big-endian - high bits are at low addresses. Favor aligned loads at 946 // the cost of some bit-fiddling. 947 MVT::ValueType EVT = N->getLoadedVT(); 948 unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8; 949 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8; 950 unsigned ExcessBits = (EBytes - IncrementSize)*8; 951 952 // Load both the high bits and maybe some of the low bits. 953 Hi = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), SVOffset, 954 MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits), 955 isVolatile, Alignment); 956 957 // Increment the pointer to the other half. 958 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 959 getIntPtrConstant(IncrementSize)); 960 // Load the rest of the low bits. 961 Lo = DAG.getExtLoad(ISD::ZEXTLOAD, NVT, Ch, Ptr, N->getSrcValue(), 962 SVOffset+IncrementSize, MVT::getIntegerType(ExcessBits), 963 isVolatile, MinAlign(Alignment, IncrementSize)); 964 965 // Build a factor node to remember that this load is independent of the 966 // other one. 967 Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), 968 Hi.getValue(1)); 969 970 if (ExcessBits < MVT::getSizeInBits(NVT)) { 971 // Transfer low bits from the bottom of Hi to the top of Lo. 972 Lo = DAG.getNode(ISD::OR, NVT, Lo, 973 DAG.getNode(ISD::SHL, NVT, Hi, 974 DAG.getConstant(ExcessBits, 975 TLI.getShiftAmountTy()))); 976 // Move high bits to the right position in Hi. 977 Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, NVT, Hi, 978 DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits, 979 TLI.getShiftAmountTy())); 980 } 981 } 982 983 // Legalized the chain result - switch anything that used the old chain to 984 // use the new one. 985 ReplaceValueWith(SDOperand(N, 1), Ch); 986} 987 988void DAGTypeLegalizer::ExpandResult_Logical(SDNode *N, 989 SDOperand &Lo, SDOperand &Hi) { 990 SDOperand LL, LH, RL, RH; 991 GetExpandedOp(N->getOperand(0), LL, LH); 992 GetExpandedOp(N->getOperand(1), RL, RH); 993 Lo = DAG.getNode(N->getOpcode(), LL.getValueType(), LL, RL); 994 Hi = DAG.getNode(N->getOpcode(), LL.getValueType(), LH, RH); 995} 996 997void DAGTypeLegalizer::ExpandResult_BSWAP(SDNode *N, 998 SDOperand &Lo, SDOperand &Hi) { 999 GetExpandedOp(N->getOperand(0), Hi, Lo); // Note swapped operands. 1000 Lo = DAG.getNode(ISD::BSWAP, Lo.getValueType(), Lo); 1001 Hi = DAG.getNode(ISD::BSWAP, Hi.getValueType(), Hi); 1002} 1003 1004void DAGTypeLegalizer::ExpandResult_SELECT(SDNode *N, 1005 SDOperand &Lo, SDOperand &Hi) { 1006 SDOperand LL, LH, RL, RH; 1007 GetExpandedOp(N->getOperand(1), LL, LH); 1008 GetExpandedOp(N->getOperand(2), RL, RH); 1009 Lo = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LL, RL); 1010 1011 assert(N->getOperand(0).getValueType() != MVT::f32 && 1012 "FIXME: softfp shouldn't use expand!"); 1013 Hi = DAG.getNode(ISD::SELECT, LL.getValueType(), N->getOperand(0), LH, RH); 1014} 1015 1016void DAGTypeLegalizer::ExpandResult_SELECT_CC(SDNode *N, 1017 SDOperand &Lo, SDOperand &Hi) { 1018 SDOperand LL, LH, RL, RH; 1019 GetExpandedOp(N->getOperand(2), LL, LH); 1020 GetExpandedOp(N->getOperand(3), RL, RH); 1021 Lo = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0), 1022 N->getOperand(1), LL, RL, N->getOperand(4)); 1023 1024 assert(N->getOperand(0).getValueType() != MVT::f32 && 1025 "FIXME: softfp shouldn't use expand!"); 1026 Hi = DAG.getNode(ISD::SELECT_CC, LL.getValueType(), N->getOperand(0), 1027 N->getOperand(1), LH, RH, N->getOperand(4)); 1028} 1029 1030void DAGTypeLegalizer::ExpandResult_ADDSUB(SDNode *N, 1031 SDOperand &Lo, SDOperand &Hi) { 1032 // Expand the subcomponents. 1033 SDOperand LHSL, LHSH, RHSL, RHSH; 1034 GetExpandedOp(N->getOperand(0), LHSL, LHSH); 1035 GetExpandedOp(N->getOperand(1), RHSL, RHSH); 1036 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag); 1037 SDOperand LoOps[2] = { LHSL, RHSL }; 1038 SDOperand HiOps[3] = { LHSH, RHSH }; 1039 1040 if (N->getOpcode() == ISD::ADD) { 1041 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2); 1042 HiOps[2] = Lo.getValue(1); 1043 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3); 1044 } else { 1045 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2); 1046 HiOps[2] = Lo.getValue(1); 1047 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3); 1048 } 1049} 1050 1051void DAGTypeLegalizer::ExpandResult_ADDSUBC(SDNode *N, 1052 SDOperand &Lo, SDOperand &Hi) { 1053 // Expand the subcomponents. 1054 SDOperand LHSL, LHSH, RHSL, RHSH; 1055 GetExpandedOp(N->getOperand(0), LHSL, LHSH); 1056 GetExpandedOp(N->getOperand(1), RHSL, RHSH); 1057 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag); 1058 SDOperand LoOps[2] = { LHSL, RHSL }; 1059 SDOperand HiOps[3] = { LHSH, RHSH }; 1060 1061 if (N->getOpcode() == ISD::ADDC) { 1062 Lo = DAG.getNode(ISD::ADDC, VTList, LoOps, 2); 1063 HiOps[2] = Lo.getValue(1); 1064 Hi = DAG.getNode(ISD::ADDE, VTList, HiOps, 3); 1065 } else { 1066 Lo = DAG.getNode(ISD::SUBC, VTList, LoOps, 2); 1067 HiOps[2] = Lo.getValue(1); 1068 Hi = DAG.getNode(ISD::SUBE, VTList, HiOps, 3); 1069 } 1070 1071 // Legalized the flag result - switch anything that used the old flag to 1072 // use the new one. 1073 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1)); 1074} 1075 1076void DAGTypeLegalizer::ExpandResult_ADDSUBE(SDNode *N, 1077 SDOperand &Lo, SDOperand &Hi) { 1078 // Expand the subcomponents. 1079 SDOperand LHSL, LHSH, RHSL, RHSH; 1080 GetExpandedOp(N->getOperand(0), LHSL, LHSH); 1081 GetExpandedOp(N->getOperand(1), RHSL, RHSH); 1082 SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag); 1083 SDOperand LoOps[3] = { LHSL, RHSL, N->getOperand(2) }; 1084 SDOperand HiOps[3] = { LHSH, RHSH }; 1085 1086 Lo = DAG.getNode(N->getOpcode(), VTList, LoOps, 3); 1087 HiOps[2] = Lo.getValue(1); 1088 Hi = DAG.getNode(N->getOpcode(), VTList, HiOps, 3); 1089 1090 // Legalized the flag result - switch anything that used the old flag to 1091 // use the new one. 1092 ReplaceValueWith(SDOperand(N, 1), Hi.getValue(1)); 1093} 1094 1095void DAGTypeLegalizer::ExpandResult_MUL(SDNode *N, 1096 SDOperand &Lo, SDOperand &Hi) { 1097 MVT::ValueType VT = N->getValueType(0); 1098 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1099 1100 bool HasMULHS = TLI.isOperationLegal(ISD::MULHS, NVT); 1101 bool HasMULHU = TLI.isOperationLegal(ISD::MULHU, NVT); 1102 bool HasSMUL_LOHI = TLI.isOperationLegal(ISD::SMUL_LOHI, NVT); 1103 bool HasUMUL_LOHI = TLI.isOperationLegal(ISD::UMUL_LOHI, NVT); 1104 if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) { 1105 SDOperand LL, LH, RL, RH; 1106 GetExpandedOp(N->getOperand(0), LL, LH); 1107 GetExpandedOp(N->getOperand(1), RL, RH); 1108 unsigned BitSize = MVT::getSizeInBits(NVT); 1109 unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0)); 1110 unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1)); 1111 1112 // FIXME: generalize this to handle other bit sizes 1113 if (LHSSB == 32 && RHSSB == 32 && 1114 DAG.MaskedValueIsZero(N->getOperand(0), 0xFFFFFFFF00000000ULL) && 1115 DAG.MaskedValueIsZero(N->getOperand(1), 0xFFFFFFFF00000000ULL)) { 1116 // The inputs are both zero-extended. 1117 if (HasUMUL_LOHI) { 1118 // We can emit a umul_lohi. 1119 Lo = DAG.getNode(ISD::UMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL); 1120 Hi = SDOperand(Lo.Val, 1); 1121 return; 1122 } 1123 if (HasMULHU) { 1124 // We can emit a mulhu+mul. 1125 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL); 1126 Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL); 1127 return; 1128 } 1129 } 1130 if (LHSSB > BitSize && RHSSB > BitSize) { 1131 // The input values are both sign-extended. 1132 if (HasSMUL_LOHI) { 1133 // We can emit a smul_lohi. 1134 Lo = DAG.getNode(ISD::SMUL_LOHI, DAG.getVTList(NVT, NVT), LL, RL); 1135 Hi = SDOperand(Lo.Val, 1); 1136 return; 1137 } 1138 if (HasMULHS) { 1139 // We can emit a mulhs+mul. 1140 Lo = DAG.getNode(ISD::MUL, NVT, LL, RL); 1141 Hi = DAG.getNode(ISD::MULHS, NVT, LL, RL); 1142 return; 1143 } 1144 } 1145 if (HasUMUL_LOHI) { 1146 // Lo,Hi = umul LHS, RHS. 1147 SDOperand UMulLOHI = DAG.getNode(ISD::UMUL_LOHI, 1148 DAG.getVTList(NVT, NVT), LL, RL); 1149 Lo = UMulLOHI; 1150 Hi = UMulLOHI.getValue(1); 1151 RH = DAG.getNode(ISD::MUL, NVT, LL, RH); 1152 LH = DAG.getNode(ISD::MUL, NVT, LH, RL); 1153 Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH); 1154 Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH); 1155 return; 1156 } 1157 } 1158 1159 abort(); 1160#if 0 // FIXME! 1161 // If nothing else, we can make a libcall. 1162 Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::MUL_I64), N, 1163 false/*sign irrelevant*/, Hi); 1164#endif 1165} 1166 1167 1168void DAGTypeLegalizer::ExpandResult_Shift(SDNode *N, 1169 SDOperand &Lo, SDOperand &Hi) { 1170 MVT::ValueType VT = N->getValueType(0); 1171 1172 // If we can emit an efficient shift operation, do so now. Check to see if 1173 // the RHS is a constant. 1174 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1))) 1175 return ExpandShiftByConstant(N, CN->getValue(), Lo, Hi); 1176 1177 // If we can determine that the high bit of the shift is zero or one, even if 1178 // the low bits are variable, emit this shift in an optimized form. 1179 if (ExpandShiftWithKnownAmountBit(N, Lo, Hi)) 1180 return; 1181 1182 // If this target supports shift_PARTS, use it. First, map to the _PARTS opc. 1183 unsigned PartsOpc; 1184 if (N->getOpcode() == ISD::SHL) 1185 PartsOpc = ISD::SHL_PARTS; 1186 else if (N->getOpcode() == ISD::SRL) 1187 PartsOpc = ISD::SRL_PARTS; 1188 else { 1189 assert(N->getOpcode() == ISD::SRA && "Unknown shift!"); 1190 PartsOpc = ISD::SRA_PARTS; 1191 } 1192 1193 // Next check to see if the target supports this SHL_PARTS operation or if it 1194 // will custom expand it. 1195 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 1196 TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT); 1197 if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) || 1198 Action == TargetLowering::Custom) { 1199 // Expand the subcomponents. 1200 SDOperand LHSL, LHSH; 1201 GetExpandedOp(N->getOperand(0), LHSL, LHSH); 1202 1203 SDOperand Ops[] = { LHSL, LHSH, N->getOperand(1) }; 1204 MVT::ValueType VT = LHSL.getValueType(); 1205 Lo = DAG.getNode(PartsOpc, DAG.getNodeValueTypes(VT, VT), 2, Ops, 3); 1206 Hi = Lo.getValue(1); 1207 return; 1208 } 1209 1210 abort(); 1211#if 0 // FIXME! 1212 // Otherwise, emit a libcall. 1213 unsigned RuntimeCode = ; // SRL -> SRL_I64 etc. 1214 bool Signed = ; 1215 Lo = ExpandLibCall(TLI.getLibcallName(RTLIB::SRL_I64), N, 1216 false/*lshr is unsigned*/, Hi); 1217#endif 1218} 1219 1220 1221/// ExpandShiftByConstant - N is a shift by a value that needs to be expanded, 1222/// and the shift amount is a constant 'Amt'. Expand the operation. 1223void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, unsigned Amt, 1224 SDOperand &Lo, SDOperand &Hi) { 1225 // Expand the incoming operand to be shifted, so that we have its parts 1226 SDOperand InL, InH; 1227 GetExpandedOp(N->getOperand(0), InL, InH); 1228 1229 MVT::ValueType NVT = InL.getValueType(); 1230 unsigned VTBits = MVT::getSizeInBits(N->getValueType(0)); 1231 unsigned NVTBits = MVT::getSizeInBits(NVT); 1232 MVT::ValueType ShTy = N->getOperand(1).getValueType(); 1233 1234 if (N->getOpcode() == ISD::SHL) { 1235 if (Amt > VTBits) { 1236 Lo = Hi = DAG.getConstant(0, NVT); 1237 } else if (Amt > NVTBits) { 1238 Lo = DAG.getConstant(0, NVT); 1239 Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt-NVTBits,ShTy)); 1240 } else if (Amt == NVTBits) { 1241 Lo = DAG.getConstant(0, NVT); 1242 Hi = InL; 1243 } else { 1244 Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Amt, ShTy)); 1245 Hi = DAG.getNode(ISD::OR, NVT, 1246 DAG.getNode(ISD::SHL, NVT, InH, 1247 DAG.getConstant(Amt, ShTy)), 1248 DAG.getNode(ISD::SRL, NVT, InL, 1249 DAG.getConstant(NVTBits-Amt, ShTy))); 1250 } 1251 return; 1252 } 1253 1254 if (N->getOpcode() == ISD::SRL) { 1255 if (Amt > VTBits) { 1256 Lo = DAG.getConstant(0, NVT); 1257 Hi = DAG.getConstant(0, NVT); 1258 } else if (Amt > NVTBits) { 1259 Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt-NVTBits,ShTy)); 1260 Hi = DAG.getConstant(0, NVT); 1261 } else if (Amt == NVTBits) { 1262 Lo = InH; 1263 Hi = DAG.getConstant(0, NVT); 1264 } else { 1265 Lo = DAG.getNode(ISD::OR, NVT, 1266 DAG.getNode(ISD::SRL, NVT, InL, 1267 DAG.getConstant(Amt, ShTy)), 1268 DAG.getNode(ISD::SHL, NVT, InH, 1269 DAG.getConstant(NVTBits-Amt, ShTy))); 1270 Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Amt, ShTy)); 1271 } 1272 return; 1273 } 1274 1275 assert(N->getOpcode() == ISD::SRA && "Unknown shift!"); 1276 if (Amt > VTBits) { 1277 Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH, 1278 DAG.getConstant(NVTBits-1, ShTy)); 1279 } else if (Amt > NVTBits) { 1280 Lo = DAG.getNode(ISD::SRA, NVT, InH, 1281 DAG.getConstant(Amt-NVTBits, ShTy)); 1282 Hi = DAG.getNode(ISD::SRA, NVT, InH, 1283 DAG.getConstant(NVTBits-1, ShTy)); 1284 } else if (Amt == NVTBits) { 1285 Lo = InH; 1286 Hi = DAG.getNode(ISD::SRA, NVT, InH, 1287 DAG.getConstant(NVTBits-1, ShTy)); 1288 } else { 1289 Lo = DAG.getNode(ISD::OR, NVT, 1290 DAG.getNode(ISD::SRL, NVT, InL, 1291 DAG.getConstant(Amt, ShTy)), 1292 DAG.getNode(ISD::SHL, NVT, InH, 1293 DAG.getConstant(NVTBits-Amt, ShTy))); 1294 Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Amt, ShTy)); 1295 } 1296} 1297 1298/// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify 1299/// this shift based on knowledge of the high bit of the shift amount. If we 1300/// can tell this, we know that it is >= 32 or < 32, without knowing the actual 1301/// shift amount. 1302bool DAGTypeLegalizer:: 1303ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi) { 1304 MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); 1305 unsigned NVTBits = MVT::getSizeInBits(NVT); 1306 assert(!(NVTBits & (NVTBits - 1)) && 1307 "Expanded integer type size not a power of two!"); 1308 1309 uint64_t HighBitMask = NVTBits, KnownZero, KnownOne; 1310 DAG.ComputeMaskedBits(N->getOperand(1), HighBitMask, KnownZero, KnownOne); 1311 1312 // If we don't know anything about the high bit, exit. 1313 if (((KnownZero|KnownOne) & HighBitMask) == 0) 1314 return false; 1315 1316 // Get the incoming operand to be shifted. 1317 SDOperand InL, InH; 1318 GetExpandedOp(N->getOperand(0), InL, InH); 1319 SDOperand Amt = N->getOperand(1); 1320 1321 // If we know that the high bit of the shift amount is one, then we can do 1322 // this as a couple of simple shifts. 1323 if (KnownOne & HighBitMask) { 1324 // Mask out the high bit, which we know is set. 1325 Amt = DAG.getNode(ISD::AND, Amt.getValueType(), Amt, 1326 DAG.getConstant(NVTBits-1, Amt.getValueType())); 1327 1328 switch (N->getOpcode()) { 1329 default: assert(0 && "Unknown shift"); 1330 case ISD::SHL: 1331 Lo = DAG.getConstant(0, NVT); // Low part is zero. 1332 Hi = DAG.getNode(ISD::SHL, NVT, InL, Amt); // High part from Lo part. 1333 return true; 1334 case ISD::SRL: 1335 Hi = DAG.getConstant(0, NVT); // Hi part is zero. 1336 Lo = DAG.getNode(ISD::SRL, NVT, InH, Amt); // Lo part from Hi part. 1337 return true; 1338 case ISD::SRA: 1339 Hi = DAG.getNode(ISD::SRA, NVT, InH, // Sign extend high part. 1340 DAG.getConstant(NVTBits-1, Amt.getValueType())); 1341 Lo = DAG.getNode(ISD::SRA, NVT, InH, Amt); // Lo part from Hi part. 1342 return true; 1343 } 1344 } 1345 1346 // If we know that the high bit of the shift amount is zero, then we can do 1347 // this as a couple of simple shifts. 1348 assert((KnownZero & HighBitMask) && "Bad mask computation above"); 1349 1350 // Compute 32-amt. 1351 SDOperand Amt2 = DAG.getNode(ISD::SUB, Amt.getValueType(), 1352 DAG.getConstant(NVTBits, Amt.getValueType()), 1353 Amt); 1354 unsigned Op1, Op2; 1355 switch (N->getOpcode()) { 1356 default: assert(0 && "Unknown shift"); 1357 case ISD::SHL: Op1 = ISD::SHL; Op2 = ISD::SRL; break; 1358 case ISD::SRL: 1359 case ISD::SRA: Op1 = ISD::SRL; Op2 = ISD::SHL; break; 1360 } 1361 1362 Lo = DAG.getNode(N->getOpcode(), NVT, InL, Amt); 1363 Hi = DAG.getNode(ISD::OR, NVT, 1364 DAG.getNode(Op1, NVT, InH, Amt), 1365 DAG.getNode(Op2, NVT, InL, Amt2)); 1366 return true; 1367} 1368 1369//===----------------------------------------------------------------------===// 1370// Result Vector Scalarization: <1 x ty> -> ty. 1371//===----------------------------------------------------------------------===// 1372 1373 1374void DAGTypeLegalizer::ScalarizeResult(SDNode *N, unsigned ResNo) { 1375 DEBUG(cerr << "Scalarize node result " << ResNo << ": "; N->dump(&DAG); 1376 cerr << "\n"); 1377 SDOperand R = SDOperand(); 1378 1379 // FIXME: Custom lowering for scalarization? 1380#if 0 1381 // See if the target wants to custom expand this node. 1382 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) == 1383 TargetLowering::Custom) { 1384 // If the target wants to, allow it to lower this itself. 1385 if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) { 1386 // Everything that once used N now uses P. We are guaranteed that the 1387 // result value types of N and the result value types of P match. 1388 ReplaceNodeWith(N, P); 1389 return; 1390 } 1391 } 1392#endif 1393 1394 switch (N->getOpcode()) { 1395 default: 1396#ifndef NDEBUG 1397 cerr << "ScalarizeResult #" << ResNo << ": "; 1398 N->dump(&DAG); cerr << "\n"; 1399#endif 1400 assert(0 && "Do not know how to scalarize the result of this operator!"); 1401 abort(); 1402 1403 case ISD::UNDEF: R = ScalarizeRes_UNDEF(N); break; 1404 case ISD::LOAD: R = ScalarizeRes_LOAD(cast<LoadSDNode>(N)); break; 1405 case ISD::ADD: 1406 case ISD::FADD: 1407 case ISD::SUB: 1408 case ISD::FSUB: 1409 case ISD::MUL: 1410 case ISD::FMUL: 1411 case ISD::SDIV: 1412 case ISD::UDIV: 1413 case ISD::FDIV: 1414 case ISD::SREM: 1415 case ISD::UREM: 1416 case ISD::FREM: 1417 case ISD::FPOW: 1418 case ISD::AND: 1419 case ISD::OR: 1420 case ISD::XOR: R = ScalarizeRes_BinOp(N); break; 1421 case ISD::FNEG: 1422 case ISD::FABS: 1423 case ISD::FSQRT: 1424 case ISD::FSIN: 1425 case ISD::FCOS: R = ScalarizeRes_UnaryOp(N); break; 1426 case ISD::FPOWI: R = ScalarizeRes_FPOWI(N); break; 1427 case ISD::BUILD_VECTOR: R = N->getOperand(0); break; 1428 case ISD::INSERT_VECTOR_ELT: R = N->getOperand(1); break; 1429 case ISD::VECTOR_SHUFFLE: R = ScalarizeRes_VECTOR_SHUFFLE(N); break; 1430 case ISD::BIT_CONVERT: R = ScalarizeRes_BIT_CONVERT(N); break; 1431 case ISD::SELECT: R = ScalarizeRes_SELECT(N); break; 1432 } 1433 1434 // If R is null, the sub-method took care of registering the resul. 1435 if (R.Val) 1436 SetScalarizedOp(SDOperand(N, ResNo), R); 1437} 1438 1439SDOperand DAGTypeLegalizer::ScalarizeRes_UNDEF(SDNode *N) { 1440 return DAG.getNode(ISD::UNDEF, MVT::getVectorElementType(N->getValueType(0))); 1441} 1442 1443SDOperand DAGTypeLegalizer::ScalarizeRes_LOAD(LoadSDNode *N) { 1444 SDOperand Result = DAG.getLoad(MVT::getVectorElementType(N->getValueType(0)), 1445 N->getChain(), N->getBasePtr(), 1446 N->getSrcValue(), N->getSrcValueOffset(), 1447 N->isVolatile(), N->getAlignment()); 1448 1449 // Legalized the chain result - switch anything that used the old chain to 1450 // use the new one. 1451 ReplaceValueWith(SDOperand(N, 1), Result.getValue(1)); 1452 return Result; 1453} 1454 1455SDOperand DAGTypeLegalizer::ScalarizeRes_BinOp(SDNode *N) { 1456 SDOperand LHS = GetScalarizedOp(N->getOperand(0)); 1457 SDOperand RHS = GetScalarizedOp(N->getOperand(1)); 1458 return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS); 1459} 1460 1461SDOperand DAGTypeLegalizer::ScalarizeRes_UnaryOp(SDNode *N) { 1462 SDOperand Op = GetScalarizedOp(N->getOperand(0)); 1463 return DAG.getNode(N->getOpcode(), Op.getValueType(), Op); 1464} 1465 1466SDOperand DAGTypeLegalizer::ScalarizeRes_FPOWI(SDNode *N) { 1467 SDOperand Op = GetScalarizedOp(N->getOperand(0)); 1468 return DAG.getNode(ISD::FPOWI, Op.getValueType(), Op, N->getOperand(1)); 1469} 1470 1471SDOperand DAGTypeLegalizer::ScalarizeRes_VECTOR_SHUFFLE(SDNode *N) { 1472 // Figure out if the scalar is the LHS or RHS and return it. 1473 SDOperand EltNum = N->getOperand(2).getOperand(0); 1474 unsigned Op = cast<ConstantSDNode>(EltNum)->getValue() != 0; 1475 return GetScalarizedOp(N->getOperand(Op)); 1476} 1477 1478SDOperand DAGTypeLegalizer::ScalarizeRes_BIT_CONVERT(SDNode *N) { 1479 MVT::ValueType NewVT = MVT::getVectorElementType(N->getValueType(0)); 1480 return DAG.getNode(ISD::BIT_CONVERT, NewVT, N->getOperand(0)); 1481} 1482 1483SDOperand DAGTypeLegalizer::ScalarizeRes_SELECT(SDNode *N) { 1484 SDOperand LHS = GetScalarizedOp(N->getOperand(1)); 1485 return DAG.getNode(ISD::SELECT, LHS.getValueType(), N->getOperand(0), LHS, 1486 GetScalarizedOp(N->getOperand(2))); 1487} 1488 1489 1490//===----------------------------------------------------------------------===// 1491// Operand Promotion 1492//===----------------------------------------------------------------------===// 1493 1494/// PromoteOperand - This method is called when the specified operand of the 1495/// specified node is found to need promotion. At this point, all of the result 1496/// types of the node are known to be legal, but other operands of the node may 1497/// need promotion or expansion as well as the specified one. 1498bool DAGTypeLegalizer::PromoteOperand(SDNode *N, unsigned OpNo) { 1499 DEBUG(cerr << "Promote node operand: "; N->dump(&DAG); cerr << "\n"); 1500 SDOperand Res; 1501 switch (N->getOpcode()) { 1502 default: 1503#ifndef NDEBUG 1504 cerr << "PromoteOperand Op #" << OpNo << ": "; 1505 N->dump(&DAG); cerr << "\n"; 1506#endif 1507 assert(0 && "Do not know how to promote this operator's operand!"); 1508 abort(); 1509 1510 case ISD::ANY_EXTEND: Res = PromoteOperand_ANY_EXTEND(N); break; 1511 case ISD::ZERO_EXTEND: Res = PromoteOperand_ZERO_EXTEND(N); break; 1512 case ISD::SIGN_EXTEND: Res = PromoteOperand_SIGN_EXTEND(N); break; 1513 case ISD::TRUNCATE: Res = PromoteOperand_TRUNCATE(N); break; 1514 case ISD::FP_EXTEND: Res = PromoteOperand_FP_EXTEND(N); break; 1515 case ISD::FP_ROUND: Res = PromoteOperand_FP_ROUND(N); break; 1516 case ISD::SINT_TO_FP: 1517 case ISD::UINT_TO_FP: Res = PromoteOperand_INT_TO_FP(N); break; 1518 1519 case ISD::SELECT: Res = PromoteOperand_SELECT(N, OpNo); break; 1520 case ISD::BRCOND: Res = PromoteOperand_BRCOND(N, OpNo); break; 1521 case ISD::BR_CC: Res = PromoteOperand_BR_CC(N, OpNo); break; 1522 case ISD::SETCC: Res = PromoteOperand_SETCC(N, OpNo); break; 1523 1524 case ISD::STORE: Res = PromoteOperand_STORE(cast<StoreSDNode>(N), 1525 OpNo); break; 1526 case ISD::MEMSET: 1527 case ISD::MEMCPY: 1528 case ISD::MEMMOVE: Res = HandleMemIntrinsic(N); break; 1529 } 1530 1531 // If the result is null, the sub-method took care of registering results etc. 1532 if (!Res.Val) return false; 1533 // If the result is N, the sub-method updated N in place. 1534 if (Res.Val == N) { 1535 // Mark N as new and remark N and its operands. This allows us to correctly 1536 // revisit N if it needs another step of promotion and allows us to visit 1537 // any new operands to N. 1538 N->setNodeId(NewNode); 1539 MarkNewNodes(N); 1540 return true; 1541 } 1542 1543 assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 && 1544 "Invalid operand expansion"); 1545 1546 ReplaceValueWith(SDOperand(N, 0), Res); 1547 return false; 1548} 1549 1550SDOperand DAGTypeLegalizer::PromoteOperand_ANY_EXTEND(SDNode *N) { 1551 SDOperand Op = GetPromotedOp(N->getOperand(0)); 1552 return DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op); 1553} 1554 1555SDOperand DAGTypeLegalizer::PromoteOperand_ZERO_EXTEND(SDNode *N) { 1556 SDOperand Op = GetPromotedOp(N->getOperand(0)); 1557 Op = DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op); 1558 return DAG.getZeroExtendInReg(Op, N->getOperand(0).getValueType()); 1559} 1560 1561SDOperand DAGTypeLegalizer::PromoteOperand_SIGN_EXTEND(SDNode *N) { 1562 SDOperand Op = GetPromotedOp(N->getOperand(0)); 1563 Op = DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op); 1564 return DAG.getNode(ISD::SIGN_EXTEND_INREG, Op.getValueType(), 1565 Op, DAG.getValueType(N->getOperand(0).getValueType())); 1566} 1567 1568SDOperand DAGTypeLegalizer::PromoteOperand_TRUNCATE(SDNode *N) { 1569 SDOperand Op = GetPromotedOp(N->getOperand(0)); 1570 return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), Op); 1571} 1572 1573SDOperand DAGTypeLegalizer::PromoteOperand_FP_EXTEND(SDNode *N) { 1574 SDOperand Op = GetPromotedOp(N->getOperand(0)); 1575 return DAG.getNode(ISD::FP_EXTEND, N->getValueType(0), Op); 1576} 1577 1578SDOperand DAGTypeLegalizer::PromoteOperand_FP_ROUND(SDNode *N) { 1579 SDOperand Op = GetPromotedOp(N->getOperand(0)); 1580 return DAG.getNode(ISD::FP_ROUND, N->getValueType(0), Op); 1581} 1582 1583SDOperand DAGTypeLegalizer::PromoteOperand_INT_TO_FP(SDNode *N) { 1584 SDOperand In = GetPromotedOp(N->getOperand(0)); 1585 MVT::ValueType OpVT = N->getOperand(0).getValueType(); 1586 if (N->getOpcode() == ISD::UINT_TO_FP) 1587 In = DAG.getZeroExtendInReg(In, OpVT); 1588 else 1589 In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), 1590 In, DAG.getValueType(OpVT)); 1591 1592 return DAG.UpdateNodeOperands(SDOperand(N, 0), In); 1593} 1594 1595SDOperand DAGTypeLegalizer::PromoteOperand_SELECT(SDNode *N, unsigned OpNo) { 1596 assert(OpNo == 0 && "Only know how to promote condition"); 1597 SDOperand Cond = GetPromotedOp(N->getOperand(0)); // Promote the condition. 1598 1599 // The top bits of the promoted condition are not necessarily zero, ensure 1600 // that the value is properly zero extended. 1601 if (!DAG.MaskedValueIsZero(Cond, 1602 MVT::getIntVTBitMask(Cond.getValueType())^1)) { 1603 Cond = DAG.getZeroExtendInReg(Cond, MVT::i1); 1604 MarkNewNodes(Cond.Val); 1605 } 1606 1607 // The chain (Op#0) and basic block destination (Op#2) are always legal types. 1608 return DAG.UpdateNodeOperands(SDOperand(N, 0), Cond, N->getOperand(1), 1609 N->getOperand(2)); 1610} 1611 1612SDOperand DAGTypeLegalizer::PromoteOperand_BRCOND(SDNode *N, unsigned OpNo) { 1613 assert(OpNo == 1 && "only know how to promote condition"); 1614 SDOperand Cond = GetPromotedOp(N->getOperand(1)); // Promote the condition. 1615 1616 // The top bits of the promoted condition are not necessarily zero, ensure 1617 // that the value is properly zero extended. 1618 if (!DAG.MaskedValueIsZero(Cond, 1619 MVT::getIntVTBitMask(Cond.getValueType())^1)) { 1620 Cond = DAG.getZeroExtendInReg(Cond, MVT::i1); 1621 MarkNewNodes(Cond.Val); 1622 } 1623 1624 // The chain (Op#0) and basic block destination (Op#2) are always legal types. 1625 return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0), Cond, 1626 N->getOperand(2)); 1627} 1628 1629SDOperand DAGTypeLegalizer::PromoteOperand_BR_CC(SDNode *N, unsigned OpNo) { 1630 assert(OpNo == 2 && "Don't know how to promote this operand"); 1631 1632 SDOperand LHS = N->getOperand(2); 1633 SDOperand RHS = N->getOperand(3); 1634 PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(1))->get()); 1635 1636 // The chain (Op#0), CC (#1) and basic block destination (Op#4) are always 1637 // legal types. 1638 return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0), 1639 N->getOperand(1), LHS, RHS, N->getOperand(4)); 1640} 1641 1642SDOperand DAGTypeLegalizer::PromoteOperand_SETCC(SDNode *N, unsigned OpNo) { 1643 assert(OpNo == 0 && "Don't know how to promote this operand"); 1644 1645 SDOperand LHS = N->getOperand(0); 1646 SDOperand RHS = N->getOperand(1); 1647 PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(2))->get()); 1648 1649 // The CC (#2) is always legal. 1650 return DAG.UpdateNodeOperands(SDOperand(N, 0), LHS, RHS, N->getOperand(2)); 1651} 1652 1653/// PromoteSetCCOperands - Promote the operands of a comparison. This code is 1654/// shared among BR_CC, SELECT_CC, and SETCC handlers. 1655void DAGTypeLegalizer::PromoteSetCCOperands(SDOperand &NewLHS,SDOperand &NewRHS, 1656 ISD::CondCode CCCode) { 1657 MVT::ValueType VT = NewLHS.getValueType(); 1658 1659 // Get the promoted values. 1660 NewLHS = GetPromotedOp(NewLHS); 1661 NewRHS = GetPromotedOp(NewRHS); 1662 1663 // If this is an FP compare, the operands have already been extended. 1664 if (!MVT::isInteger(NewLHS.getValueType())) 1665 return; 1666 1667 // Otherwise, we have to insert explicit sign or zero extends. Note 1668 // that we could insert sign extends for ALL conditions, but zero extend 1669 // is cheaper on many machines (an AND instead of two shifts), so prefer 1670 // it. 1671 switch (CCCode) { 1672 default: assert(0 && "Unknown integer comparison!"); 1673 case ISD::SETEQ: 1674 case ISD::SETNE: 1675 case ISD::SETUGE: 1676 case ISD::SETUGT: 1677 case ISD::SETULE: 1678 case ISD::SETULT: 1679 // ALL of these operations will work if we either sign or zero extend 1680 // the operands (including the unsigned comparisons!). Zero extend is 1681 // usually a simpler/cheaper operation, so prefer it. 1682 NewLHS = DAG.getZeroExtendInReg(NewLHS, VT); 1683 NewRHS = DAG.getZeroExtendInReg(NewRHS, VT); 1684 return; 1685 case ISD::SETGE: 1686 case ISD::SETGT: 1687 case ISD::SETLT: 1688 case ISD::SETLE: 1689 NewLHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, NewLHS.getValueType(), NewLHS, 1690 DAG.getValueType(VT)); 1691 NewRHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, NewRHS.getValueType(), NewRHS, 1692 DAG.getValueType(VT)); 1693 return; 1694 } 1695} 1696 1697SDOperand DAGTypeLegalizer::PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo){ 1698 SDOperand Ch = N->getChain(), Ptr = N->getBasePtr(); 1699 int SVOffset = N->getSrcValueOffset(); 1700 unsigned Alignment = N->getAlignment(); 1701 bool isVolatile = N->isVolatile(); 1702 1703 SDOperand Val = GetPromotedOp(N->getValue()); // Get promoted value. 1704 1705 assert(!N->isTruncatingStore() && "Cannot promote this store operand!"); 1706 1707 // Truncate the value and store the result. 1708 return DAG.getTruncStore(Ch, Val, Ptr, N->getSrcValue(), 1709 SVOffset, N->getStoredVT(), 1710 isVolatile, Alignment); 1711} 1712 1713 1714//===----------------------------------------------------------------------===// 1715// Operand Expansion 1716//===----------------------------------------------------------------------===// 1717 1718/// ExpandOperand - This method is called when the specified operand of the 1719/// specified node is found to need expansion. At this point, all of the result 1720/// types of the node are known to be legal, but other operands of the node may 1721/// need promotion or expansion as well as the specified one. 1722bool DAGTypeLegalizer::ExpandOperand(SDNode *N, unsigned OpNo) { 1723 DEBUG(cerr << "Expand node operand: "; N->dump(&DAG); cerr << "\n"); 1724 SDOperand Res(0, 0); 1725 1726 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) == 1727 TargetLowering::Custom) 1728 Res = TLI.LowerOperation(SDOperand(N, 0), DAG); 1729 1730 if (Res.Val == 0) { 1731 switch (N->getOpcode()) { 1732 default: 1733 #ifndef NDEBUG 1734 cerr << "ExpandOperand Op #" << OpNo << ": "; 1735 N->dump(&DAG); cerr << "\n"; 1736 #endif 1737 assert(0 && "Do not know how to expand this operator's operand!"); 1738 abort(); 1739 1740 case ISD::TRUNCATE: Res = ExpandOperand_TRUNCATE(N); break; 1741 case ISD::BIT_CONVERT: Res = ExpandOperand_BIT_CONVERT(N); break; 1742 1743 case ISD::SINT_TO_FP: 1744 Res = ExpandOperand_SINT_TO_FP(N->getOperand(0), N->getValueType(0)); 1745 break; 1746 case ISD::UINT_TO_FP: 1747 Res = ExpandOperand_UINT_TO_FP(N->getOperand(0), N->getValueType(0)); 1748 break; 1749 case ISD::EXTRACT_ELEMENT: Res = ExpandOperand_EXTRACT_ELEMENT(N); break; 1750 case ISD::SETCC: Res = ExpandOperand_SETCC(N); break; 1751 1752 case ISD::STORE: 1753 Res = ExpandOperand_STORE(cast<StoreSDNode>(N), OpNo); 1754 break; 1755 case ISD::MEMSET: 1756 case ISD::MEMCPY: 1757 case ISD::MEMMOVE: Res = HandleMemIntrinsic(N); break; 1758 } 1759 } 1760 1761 // If the result is null, the sub-method took care of registering results etc. 1762 if (!Res.Val) return false; 1763 // If the result is N, the sub-method updated N in place. Check to see if any 1764 // operands are new, and if so, mark them. 1765 if (Res.Val == N) { 1766 // Mark N as new and remark N and its operands. This allows us to correctly 1767 // revisit N if it needs another step of promotion and allows us to visit 1768 // any new operands to N. 1769 N->setNodeId(NewNode); 1770 MarkNewNodes(N); 1771 return true; 1772 } 1773 1774 assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 && 1775 "Invalid operand expansion"); 1776 1777 ReplaceValueWith(SDOperand(N, 0), Res); 1778 return false; 1779} 1780 1781SDOperand DAGTypeLegalizer::ExpandOperand_TRUNCATE(SDNode *N) { 1782 SDOperand InL, InH; 1783 GetExpandedOp(N->getOperand(0), InL, InH); 1784 // Just truncate the low part of the source. 1785 return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), InL); 1786} 1787 1788SDOperand DAGTypeLegalizer::ExpandOperand_BIT_CONVERT(SDNode *N) { 1789 return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0)); 1790} 1791 1792SDOperand DAGTypeLegalizer::ExpandOperand_SINT_TO_FP(SDOperand Source, 1793 MVT::ValueType DestTy) { 1794 // We know the destination is legal, but that the input needs to be expanded. 1795 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!"); 1796 1797 // Check to see if the target has a custom way to lower this. If so, use it. 1798 switch (TLI.getOperationAction(ISD::SINT_TO_FP, Source.getValueType())) { 1799 default: assert(0 && "This action not implemented for this operation!"); 1800 case TargetLowering::Legal: 1801 case TargetLowering::Expand: 1802 break; // This case is handled below. 1803 case TargetLowering::Custom: 1804 SDOperand NV = TLI.LowerOperation(DAG.getNode(ISD::SINT_TO_FP, DestTy, 1805 Source), DAG); 1806 if (NV.Val) return NV; 1807 break; // The target lowered this. 1808 } 1809 1810 RTLIB::Libcall LC; 1811 if (DestTy == MVT::f32) 1812 LC = RTLIB::SINTTOFP_I64_F32; 1813 else { 1814 assert(DestTy == MVT::f64 && "Unknown fp value type!"); 1815 LC = RTLIB::SINTTOFP_I64_F64; 1816 } 1817 1818 assert(0 && "FIXME: no libcalls yet!"); 1819 abort(); 1820#if 0 1821 assert(TLI.getLibcallName(LC) && "Don't know how to expand this SINT_TO_FP!"); 1822 Source = DAG.getNode(ISD::SINT_TO_FP, DestTy, Source); 1823 SDOperand UnusedHiPart; 1824 return ExpandLibCall(TLI.getLibcallName(LC), Source.Val, true, UnusedHiPart); 1825#endif 1826} 1827 1828SDOperand DAGTypeLegalizer::ExpandOperand_UINT_TO_FP(SDOperand Source, 1829 MVT::ValueType DestTy) { 1830 // We know the destination is legal, but that the input needs to be expanded. 1831 assert(getTypeAction(Source.getValueType()) == Expand && 1832 "This is not an expansion!"); 1833 assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!"); 1834 1835 // If this is unsigned, and not supported, first perform the conversion to 1836 // signed, then adjust the result if the sign bit is set. 1837 SDOperand SignedConv = ExpandOperand_SINT_TO_FP(Source, DestTy); 1838 1839 // The 64-bit value loaded will be incorrectly if the 'sign bit' of the 1840 // incoming integer is set. To handle this, we dynamically test to see if 1841 // it is set, and, if so, add a fudge factor. 1842 SDOperand Lo, Hi; 1843 GetExpandedOp(Source, Lo, Hi); 1844 1845 SDOperand SignSet = DAG.getSetCC(TLI.getSetCCResultTy(), Hi, 1846 DAG.getConstant(0, Hi.getValueType()), 1847 ISD::SETLT); 1848 SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4); 1849 SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(), 1850 SignSet, Four, Zero); 1851 uint64_t FF = 0x5f800000ULL; 1852 if (TLI.isLittleEndian()) FF <<= 32; 1853 Constant *FudgeFactor = ConstantInt::get(Type::Int64Ty, FF); 1854 1855 SDOperand CPIdx = DAG.getConstantPool(FudgeFactor, TLI.getPointerTy()); 1856 CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset); 1857 SDOperand FudgeInReg; 1858 if (DestTy == MVT::f32) 1859 FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, NULL, 0); 1860 else if (MVT::getSizeInBits(DestTy) > MVT::getSizeInBits(MVT::f32)) 1861 // FIXME: Avoid the extend by construction the right constantpool? 1862 FudgeInReg = DAG.getExtLoad(ISD::EXTLOAD, DestTy, DAG.getEntryNode(), 1863 CPIdx, NULL, 0, MVT::f32); 1864 else 1865 assert(0 && "Unexpected conversion"); 1866 1867 return DAG.getNode(ISD::FADD, DestTy, SignedConv, FudgeInReg); 1868} 1869 1870SDOperand DAGTypeLegalizer::ExpandOperand_EXTRACT_ELEMENT(SDNode *N) { 1871 SDOperand Lo, Hi; 1872 GetExpandedOp(N->getOperand(0), Lo, Hi); 1873 return cast<ConstantSDNode>(N->getOperand(1))->getValue() ? Hi : Lo; 1874} 1875 1876SDOperand DAGTypeLegalizer::ExpandOperand_SETCC(SDNode *N) { 1877 SDOperand NewLHS = N->getOperand(0), NewRHS = N->getOperand(1); 1878 ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get(); 1879 ExpandSetCCOperands(NewLHS, NewRHS, CCCode); 1880 1881 // If ExpandSetCCOperands returned a scalar, use it. 1882 if (NewRHS.Val == 0) return NewLHS; 1883 1884 // Otherwise, update N to have the operands specified. 1885 return DAG.UpdateNodeOperands(SDOperand(N, 0), NewLHS, NewRHS, 1886 DAG.getCondCode(CCCode)); 1887} 1888 1889/// ExpandSetCCOperands - Expand the operands of a comparison. This code is 1890/// shared among BR_CC, SELECT_CC, and SETCC handlers. 1891void DAGTypeLegalizer::ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS, 1892 ISD::CondCode &CCCode) { 1893 SDOperand LHSLo, LHSHi, RHSLo, RHSHi; 1894 GetExpandedOp(NewLHS, LHSLo, LHSHi); 1895 GetExpandedOp(NewRHS, RHSLo, RHSHi); 1896 1897 MVT::ValueType VT = NewLHS.getValueType(); 1898 if (VT == MVT::f32 || VT == MVT::f64) { 1899 assert(0 && "FIXME: softfp not implemented yet! should be promote not exp"); 1900 } 1901 1902 if (VT == MVT::ppcf128) { 1903 // FIXME: This generated code sucks. We want to generate 1904 // FCMP crN, hi1, hi2 1905 // BNE crN, L: 1906 // FCMP crN, lo1, lo2 1907 // The following can be improved, but not that much. 1908 SDOperand Tmp1, Tmp2, Tmp3; 1909 Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ); 1910 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, CCCode); 1911 Tmp3 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2); 1912 Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETNE); 1913 Tmp2 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, CCCode); 1914 Tmp1 = DAG.getNode(ISD::AND, Tmp1.getValueType(), Tmp1, Tmp2); 1915 NewLHS = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp3); 1916 NewRHS = SDOperand(); // LHS is the result, not a compare. 1917 return; 1918 } 1919 1920 1921 if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) { 1922 if (RHSLo == RHSHi) 1923 if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) 1924 if (RHSCST->isAllOnesValue()) { 1925 // Equality comparison to -1. 1926 NewLHS = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi); 1927 NewRHS = RHSLo; 1928 return; 1929 } 1930 1931 NewLHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); 1932 NewRHS = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); 1933 NewLHS = DAG.getNode(ISD::OR, NewLHS.getValueType(), NewLHS, NewRHS); 1934 NewRHS = DAG.getConstant(0, NewLHS.getValueType()); 1935 return; 1936 } 1937 1938 // If this is a comparison of the sign bit, just look at the top part. 1939 // X > -1, x < 0 1940 if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS)) 1941 if ((CCCode == ISD::SETLT && CST->getValue() == 0) || // X < 0 1942 (CCCode == ISD::SETGT && CST->isAllOnesValue())) { // X > -1 1943 NewLHS = LHSHi; 1944 NewRHS = RHSHi; 1945 return; 1946 } 1947 1948 // FIXME: This generated code sucks. 1949 ISD::CondCode LowCC; 1950 switch (CCCode) { 1951 default: assert(0 && "Unknown integer setcc!"); 1952 case ISD::SETLT: 1953 case ISD::SETULT: LowCC = ISD::SETULT; break; 1954 case ISD::SETGT: 1955 case ISD::SETUGT: LowCC = ISD::SETUGT; break; 1956 case ISD::SETLE: 1957 case ISD::SETULE: LowCC = ISD::SETULE; break; 1958 case ISD::SETGE: 1959 case ISD::SETUGE: LowCC = ISD::SETUGE; break; 1960 } 1961 1962 // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison 1963 // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands 1964 // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; 1965 1966 // NOTE: on targets without efficient SELECT of bools, we can always use 1967 // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3) 1968 TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, false, true, NULL); 1969 SDOperand Tmp1, Tmp2; 1970 Tmp1 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC, 1971 false, DagCombineInfo); 1972 if (!Tmp1.Val) 1973 Tmp1 = DAG.getSetCC(TLI.getSetCCResultTy(), LHSLo, RHSLo, LowCC); 1974 Tmp2 = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, 1975 CCCode, false, DagCombineInfo); 1976 if (!Tmp2.Val) 1977 Tmp2 = DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), LHSHi, RHSHi, 1978 DAG.getCondCode(CCCode)); 1979 1980 ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.Val); 1981 ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.Val); 1982 if ((Tmp1C && Tmp1C->getValue() == 0) || 1983 (Tmp2C && Tmp2C->getValue() == 0 && 1984 (CCCode == ISD::SETLE || CCCode == ISD::SETGE || 1985 CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) || 1986 (Tmp2C && Tmp2C->getValue() == 1 && 1987 (CCCode == ISD::SETLT || CCCode == ISD::SETGT || 1988 CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) { 1989 // low part is known false, returns high part. 1990 // For LE / GE, if high part is known false, ignore the low part. 1991 // For LT / GT, if high part is known true, ignore the low part. 1992 NewLHS = Tmp2; 1993 NewRHS = SDOperand(); 1994 return; 1995 } 1996 1997 NewLHS = TLI.SimplifySetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, 1998 ISD::SETEQ, false, DagCombineInfo); 1999 if (!NewLHS.Val) 2000 NewLHS = DAG.getSetCC(TLI.getSetCCResultTy(), LHSHi, RHSHi, ISD::SETEQ); 2001 NewLHS = DAG.getNode(ISD::SELECT, Tmp1.getValueType(), 2002 NewLHS, Tmp1, Tmp2); 2003 NewRHS = SDOperand(); 2004} 2005 2006SDOperand DAGTypeLegalizer::ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo) { 2007 assert(OpNo == 1 && "Can only expand the stored value so far"); 2008 2009 MVT::ValueType VT = N->getOperand(1).getValueType(); 2010 MVT::ValueType NVT = TLI.getTypeToTransformTo(VT); 2011 SDOperand Ch = N->getChain(); 2012 SDOperand Ptr = N->getBasePtr(); 2013 int SVOffset = N->getSrcValueOffset(); 2014 unsigned Alignment = N->getAlignment(); 2015 bool isVolatile = N->isVolatile(); 2016 SDOperand Lo, Hi; 2017 2018 assert(!(MVT::getSizeInBits(NVT) & 7) && "Expanded type not byte sized!"); 2019 2020 if (!N->isTruncatingStore()) { 2021 unsigned IncrementSize = 0; 2022 2023 // If this is a vector type, then we have to calculate the increment as 2024 // the product of the element size in bytes, and the number of elements 2025 // in the high half of the vector. 2026 if (MVT::isVector(N->getValue().getValueType())) { 2027 assert(0 && "Vectors not supported yet"); 2028 #if 0 2029 SDNode *InVal = ST->getValue().Val; 2030 unsigned NumElems = MVT::getVectorNumElements(InVal->getValueType(0)); 2031 MVT::ValueType EVT = MVT::getVectorElementType(InVal->getValueType(0)); 2032 2033 // Figure out if there is a simple type corresponding to this Vector 2034 // type. If so, convert to the vector type. 2035 MVT::ValueType TVT = MVT::getVectorType(EVT, NumElems); 2036 if (TLI.isTypeLegal(TVT)) { 2037 // Turn this into a normal store of the vector type. 2038 Tmp3 = LegalizeOp(Node->getOperand(1)); 2039 Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(), 2040 SVOffset, isVolatile, Alignment); 2041 Result = LegalizeOp(Result); 2042 break; 2043 } else if (NumElems == 1) { 2044 // Turn this into a normal store of the scalar type. 2045 Tmp3 = ScalarizeVectorOp(Node->getOperand(1)); 2046 Result = DAG.getStore(Tmp1, Tmp3, Tmp2, ST->getSrcValue(), 2047 SVOffset, isVolatile, Alignment); 2048 // The scalarized value type may not be legal, e.g. it might require 2049 // promotion or expansion. Relegalize the scalar store. 2050 return LegalizeOp(Result); 2051 } else { 2052 SplitVectorOp(Node->getOperand(1), Lo, Hi); 2053 IncrementSize = NumElems/2 * MVT::getSizeInBits(EVT)/8; 2054 } 2055 #endif 2056 } else { 2057 GetExpandedOp(N->getValue(), Lo, Hi); 2058 IncrementSize = Hi.Val ? MVT::getSizeInBits(Hi.getValueType())/8 : 0; 2059 2060 if (!TLI.isLittleEndian()) 2061 std::swap(Lo, Hi); 2062 } 2063 2064 Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(), 2065 SVOffset, isVolatile, Alignment); 2066 2067 assert(Hi.Val && "FIXME: int <-> float should be handled with promote!"); 2068 #if 0 2069 if (Hi.Val == NULL) { 2070 // Must be int <-> float one-to-one expansion. 2071 return Lo; 2072 } 2073 #endif 2074 2075 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 2076 getIntPtrConstant(IncrementSize)); 2077 assert(isTypeLegal(Ptr.getValueType()) && "Pointers must be legal!"); 2078 Hi = DAG.getStore(Ch, Hi, Ptr, N->getSrcValue(), SVOffset+IncrementSize, 2079 isVolatile, MinAlign(Alignment, IncrementSize)); 2080 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 2081 } else if (MVT::getSizeInBits(N->getStoredVT()) <= MVT::getSizeInBits(NVT)) { 2082 GetExpandedOp(N->getValue(), Lo, Hi); 2083 return DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset, 2084 N->getStoredVT(), isVolatile, Alignment); 2085 } else if (TLI.isLittleEndian()) { 2086 // Little-endian - low bits are at low addresses. 2087 GetExpandedOp(N->getValue(), Lo, Hi); 2088 2089 Lo = DAG.getStore(Ch, Lo, Ptr, N->getSrcValue(), SVOffset, 2090 isVolatile, Alignment); 2091 2092 unsigned ExcessBits = 2093 MVT::getSizeInBits(N->getStoredVT()) - MVT::getSizeInBits(NVT); 2094 MVT::ValueType NEVT = MVT::getIntegerType(ExcessBits); 2095 2096 // Increment the pointer to the other half. 2097 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8; 2098 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 2099 getIntPtrConstant(IncrementSize)); 2100 Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(), 2101 SVOffset+IncrementSize, NEVT, 2102 isVolatile, MinAlign(Alignment, IncrementSize)); 2103 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 2104 } else { 2105 // Big-endian - high bits are at low addresses. Favor aligned stores at 2106 // the cost of some bit-fiddling. 2107 GetExpandedOp(N->getValue(), Lo, Hi); 2108 2109 MVT::ValueType EVT = N->getStoredVT(); 2110 unsigned EBytes = MVT::getStoreSizeInBits(EVT)/8; 2111 unsigned IncrementSize = MVT::getSizeInBits(NVT)/8; 2112 unsigned ExcessBits = (EBytes - IncrementSize)*8; 2113 MVT::ValueType HiVT = 2114 MVT::getIntegerType(MVT::getSizeInBits(EVT)-ExcessBits); 2115 2116 if (ExcessBits < MVT::getSizeInBits(NVT)) { 2117 // Transfer high bits from the top of Lo to the bottom of Hi. 2118 Hi = DAG.getNode(ISD::SHL, NVT, Hi, 2119 DAG.getConstant(MVT::getSizeInBits(NVT) - ExcessBits, 2120 TLI.getShiftAmountTy())); 2121 Hi = DAG.getNode(ISD::OR, NVT, Hi, 2122 DAG.getNode(ISD::SRL, NVT, Lo, 2123 DAG.getConstant(ExcessBits, 2124 TLI.getShiftAmountTy()))); 2125 } 2126 2127 // Store both the high bits and maybe some of the low bits. 2128 Hi = DAG.getTruncStore(Ch, Hi, Ptr, N->getSrcValue(), 2129 SVOffset, HiVT, isVolatile, Alignment); 2130 2131 // Increment the pointer to the other half. 2132 Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, 2133 getIntPtrConstant(IncrementSize)); 2134 // Store the lowest ExcessBits bits in the second half. 2135 Lo = DAG.getTruncStore(Ch, Lo, Ptr, N->getSrcValue(), 2136 SVOffset+IncrementSize, 2137 MVT::getIntegerType(ExcessBits), 2138 isVolatile, MinAlign(Alignment, IncrementSize)); 2139 return DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); 2140 } 2141} 2142 2143//===----------------------------------------------------------------------===// 2144// Operand Vector Scalarization <1 x ty> -> ty. 2145//===----------------------------------------------------------------------===// 2146 2147bool DAGTypeLegalizer::ScalarizeOperand(SDNode *N, unsigned OpNo) { 2148 DEBUG(cerr << "Scalarize node operand " << OpNo << ": "; N->dump(&DAG); 2149 cerr << "\n"); 2150 SDOperand Res(0, 0); 2151 2152 // FIXME: Should we support custom lowering for scalarization? 2153#if 0 2154 if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) == 2155 TargetLowering::Custom) 2156 Res = TLI.LowerOperation(SDOperand(N, 0), DAG); 2157#endif 2158 2159 if (Res.Val == 0) { 2160 switch (N->getOpcode()) { 2161 default: 2162#ifndef NDEBUG 2163 cerr << "ScalarizeOperand Op #" << OpNo << ": "; 2164 N->dump(&DAG); cerr << "\n"; 2165#endif 2166 assert(0 && "Do not know how to scalarize this operator's operand!"); 2167 abort(); 2168 2169 case ISD::EXTRACT_VECTOR_ELT: 2170 Res = ScalarizeOp_EXTRACT_VECTOR_ELT(N, OpNo); 2171 break; 2172 } 2173 } 2174 2175 // If the result is null, the sub-method took care of registering results etc. 2176 if (!Res.Val) return false; 2177 2178 // If the result is N, the sub-method updated N in place. Check to see if any 2179 // operands are new, and if so, mark them. 2180 if (Res.Val == N) { 2181 // Mark N as new and remark N and its operands. This allows us to correctly 2182 // revisit N if it needs another step of promotion and allows us to visit 2183 // any new operands to N. 2184 N->setNodeId(NewNode); 2185 MarkNewNodes(N); 2186 return true; 2187 } 2188 2189 assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 && 2190 "Invalid operand expansion"); 2191 2192 ReplaceValueWith(SDOperand(N, 0), Res); 2193 return false; 2194} 2195 2196/// ScalarizeOp_EXTRACT_VECTOR_ELT - If the input is a vector that needs to be 2197/// scalarized, it must be <1 x ty>, just return the operand, ignoring the 2198/// index. 2199SDOperand DAGTypeLegalizer::ScalarizeOp_EXTRACT_VECTOR_ELT(SDNode *N, 2200 unsigned OpNo) { 2201 return GetScalarizedOp(N->getOperand(0)); 2202} 2203 2204 2205//===----------------------------------------------------------------------===// 2206// Entry Point 2207//===----------------------------------------------------------------------===// 2208 2209/// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 2210/// only uses types natively supported by the target. 2211/// 2212/// Note that this is an involved process that may invalidate pointers into 2213/// the graph. 2214void SelectionDAG::LegalizeTypes() { 2215 DAGTypeLegalizer(*this).run(); 2216} 2217