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