LegalizeTypes.cpp revision 0c97f1da6784c4097fd6c9d1a15813ad9802cc5b
1//===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/CallingConv.h" 18#include "llvm/Support/CommandLine.h" 19#include "llvm/Target/TargetData.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 if (IgnoreNodeResults(N)) 55 goto ScanOperands; 56 57 // Scan the values produced by the node, checking to see if any result 58 // types are illegal. 59 for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) { 60 MVT ResultVT = N->getValueType(i); 61 switch (getTypeAction(ResultVT)) { 62 default: 63 assert(false && "Unknown action!"); 64 case Legal: 65 break; 66 case PromoteInteger: 67 PromoteIntegerResult(N, i); 68 goto NodeDone; 69 case ExpandInteger: 70 ExpandIntegerResult(N, i); 71 goto NodeDone; 72 case SoftenFloat: 73 SoftenFloatResult(N, i); 74 goto NodeDone; 75 case ExpandFloat: 76 ExpandFloatResult(N, i); 77 goto NodeDone; 78 case ScalarizeVector: 79 ScalarizeVectorResult(N, i); 80 goto NodeDone; 81 case SplitVector: 82 SplitVectorResult(N, i); 83 goto NodeDone; 84 } 85 } 86 87ScanOperands: 88 // Scan the operand list for the node, handling any nodes with operands that 89 // are illegal. 90 { 91 unsigned NumOperands = N->getNumOperands(); 92 bool NeedsRevisit = false; 93 unsigned i; 94 for (i = 0; i != NumOperands; ++i) { 95 if (IgnoreNodeResults(N->getOperand(i).Val)) 96 continue; 97 98 MVT OpVT = N->getOperand(i).getValueType(); 99 switch (getTypeAction(OpVT)) { 100 default: 101 assert(false && "Unknown action!"); 102 case Legal: 103 continue; 104 case PromoteInteger: 105 NeedsRevisit = PromoteIntegerOperand(N, i); 106 break; 107 case ExpandInteger: 108 NeedsRevisit = ExpandIntegerOperand(N, i); 109 break; 110 case SoftenFloat: 111 NeedsRevisit = SoftenFloatOperand(N, i); 112 break; 113 case ExpandFloat: 114 NeedsRevisit = ExpandFloatOperand(N, i); 115 break; 116 case ScalarizeVector: 117 NeedsRevisit = ScalarizeVectorOperand(N, i); 118 break; 119 case SplitVector: 120 NeedsRevisit = SplitVectorOperand(N, i); 121 break; 122 } 123 break; 124 } 125 126 // If the node needs revisiting, don't add all users to the worklist etc. 127 if (NeedsRevisit) 128 continue; 129 130 if (i == NumOperands) 131 DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n"); 132 } 133NodeDone: 134 135 // If we reach here, the node was processed, potentially creating new nodes. 136 // Mark it as processed and add its users to the worklist as appropriate. 137 N->setNodeId(Processed); 138 139 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 140 UI != E; ++UI) { 141 SDNode *User = *UI; 142 int NodeID = User->getNodeId(); 143 assert(NodeID != ReadyToProcess && NodeID != Processed && 144 "Invalid node id for user of unprocessed node!"); 145 146 // This node has two options: it can either be a new node or its Node ID 147 // may be a count of the number of operands it has that are not ready. 148 if (NodeID > 0) { 149 User->setNodeId(NodeID-1); 150 151 // If this was the last use it was waiting on, add it to the ready list. 152 if (NodeID-1 == ReadyToProcess) 153 Worklist.push_back(User); 154 continue; 155 } 156 157 // Otherwise, this node is new: this is the first operand of it that 158 // became ready. Its new NodeID is the number of operands it has minus 1 159 // (as this node is now processed). 160 assert(NodeID == NewNode && "Unknown node ID!"); 161 User->setNodeId(User->getNumOperands()-1); 162 163 // If the node only has a single operand, it is now ready. 164 if (User->getNumOperands() == 1) 165 Worklist.push_back(User); 166 } 167 } 168 169 // If the root changed (e.g. it was a dead load, update the root). 170 DAG.setRoot(Dummy.getValue()); 171 172 //DAG.viewGraph(); 173 174 // Remove dead nodes. This is important to do for cleanliness but also before 175 // the checking loop below. Implicit folding by the DAG.getNode operators can 176 // cause unreachable nodes to be around with their flags set to new. 177 DAG.RemoveDeadNodes(); 178 179 // In a debug build, scan all the nodes to make sure we found them all. This 180 // ensures that there are no cycles and that everything got processed. 181#ifndef NDEBUG 182 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 183 E = DAG.allnodes_end(); I != E; ++I) { 184 bool Failed = false; 185 186 // Check that all result types are legal. 187 if (!IgnoreNodeResults(I)) 188 for (unsigned i = 0, NumVals = I->getNumValues(); i < NumVals; ++i) 189 if (!isTypeLegal(I->getValueType(i))) { 190 cerr << "Result type " << i << " illegal!\n"; 191 Failed = true; 192 } 193 194 // Check that all operand types are legal. 195 for (unsigned i = 0, NumOps = I->getNumOperands(); i < NumOps; ++i) 196 if (!IgnoreNodeResults(I->getOperand(i).Val) && 197 !isTypeLegal(I->getOperand(i).getValueType())) { 198 cerr << "Operand type " << i << " illegal!\n"; 199 Failed = true; 200 } 201 202 if (I->getNodeId() != Processed) { 203 if (I->getNodeId() == NewNode) 204 cerr << "New node not 'noticed'?\n"; 205 else if (I->getNodeId() > 0) 206 cerr << "Operand not processed?\n"; 207 else if (I->getNodeId() == ReadyToProcess) 208 cerr << "Not added to worklist?\n"; 209 Failed = true; 210 } 211 212 if (Failed) { 213 I->dump(&DAG); cerr << "\n"; 214 abort(); 215 } 216 } 217#endif 218} 219 220/// AnalyzeNewNode - The specified node is the root of a subtree of potentially 221/// new nodes. Correct any processed operands (this may change the node) and 222/// calculate the NodeId. 223void DAGTypeLegalizer::AnalyzeNewNode(SDNode *&N) { 224 // If this was an existing node that is already done, we're done. 225 if (N->getNodeId() != NewNode) 226 return; 227 228 // Remove any stale map entries. 229 ExpungeNode(N); 230 231 // Okay, we know that this node is new. Recursively walk all of its operands 232 // to see if they are new also. The depth of this walk is bounded by the size 233 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 234 // about revisiting of nodes. 235 // 236 // As we walk the operands, keep track of the number of nodes that are 237 // processed. If non-zero, this will become the new nodeid of this node. 238 // Already processed operands may need to be remapped to the node that 239 // replaced them, which can result in our node changing. Since remapping 240 // is rare, the code tries to minimize overhead in the non-remapping case. 241 242 SmallVector<SDOperand, 8> NewOps; 243 unsigned NumProcessed = 0; 244 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 245 SDOperand OrigOp = N->getOperand(i); 246 SDOperand Op = OrigOp; 247 248 if (Op.Val->getNodeId() == Processed) 249 RemapNode(Op); 250 251 if (Op.Val->getNodeId() == NewNode) 252 AnalyzeNewNode(Op.Val); 253 else if (Op.Val->getNodeId() == Processed) 254 ++NumProcessed; 255 256 if (!NewOps.empty()) { 257 // Some previous operand changed. Add this one to the list. 258 NewOps.push_back(Op); 259 } else if (Op != OrigOp) { 260 // This is the first operand to change - add all operands so far. 261 for (unsigned j = 0; j < i; ++j) 262 NewOps.push_back(N->getOperand(j)); 263 NewOps.push_back(Op); 264 } 265 } 266 267 // Some operands changed - update the node. 268 if (!NewOps.empty()) 269 N = DAG.UpdateNodeOperands(SDOperand(N, 0), &NewOps[0], NewOps.size()).Val; 270 271 N->setNodeId(N->getNumOperands()-NumProcessed); 272 if (N->getNodeId() == ReadyToProcess) 273 Worklist.push_back(N); 274} 275 276namespace { 277 /// NodeUpdateListener - This class is a DAGUpdateListener that listens for 278 /// updates to nodes and recomputes their ready state. 279 class VISIBILITY_HIDDEN NodeUpdateListener : 280 public SelectionDAG::DAGUpdateListener { 281 DAGTypeLegalizer &DTL; 282 public: 283 explicit NodeUpdateListener(DAGTypeLegalizer &dtl) : DTL(dtl) {} 284 285 virtual void NodeDeleted(SDNode *N, SDNode *E) { 286 assert(N->getNodeId() != DAGTypeLegalizer::Processed && 287 N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 288 "RAUW deleted processed node!"); 289 // It is possible, though rare, for the deleted node N to occur as a 290 // target in a map, so note the replacement N -> E in ReplacedNodes. 291 assert(E && "Node not replaced?"); 292 DTL.NoteDeletion(N, E); 293 } 294 295 virtual void NodeUpdated(SDNode *N) { 296 // Node updates can mean pretty much anything. It is possible that an 297 // operand was set to something already processed (f.e.) in which case 298 // this node could become ready. Recompute its flags. 299 assert(N->getNodeId() != DAGTypeLegalizer::Processed && 300 N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 301 "RAUW updated processed node!"); 302 DTL.ReanalyzeNode(N); 303 } 304 }; 305} 306 307 308/// ReplaceValueWith - The specified value was legalized to the specified other 309/// value. If they are different, update the DAG and NodeIDs replacing any uses 310/// of From to use To instead. 311void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) { 312 if (From == To) return; 313 314 // If expansion produced new nodes, make sure they are properly marked. 315 ExpungeNode(From.Val); 316 AnalyzeNewNode(To.Val); // Expunges To. 317 318 // Anything that used the old node should now use the new one. Note that this 319 // can potentially cause recursive merging. 320 NodeUpdateListener NUL(*this); 321 DAG.ReplaceAllUsesOfValueWith(From, To, &NUL); 322 323 // The old node may still be present in a map like ExpandedIntegers or 324 // PromotedIntegers. Inform maps about the replacement. 325 ReplacedNodes[From] = To; 326} 327 328/// ReplaceNodeWith - Replace uses of the 'from' node's results with the 'to' 329/// node's results. The from and to node must define identical result types. 330void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) { 331 if (From == To) return; 332 333 // If expansion produced new nodes, make sure they are properly marked. 334 ExpungeNode(From); 335 AnalyzeNewNode(To); // Expunges To. 336 337 assert(From->getNumValues() == To->getNumValues() && 338 "Node results don't match"); 339 340 // Anything that used the old node should now use the new one. Note that this 341 // can potentially cause recursive merging. 342 NodeUpdateListener NUL(*this); 343 DAG.ReplaceAllUsesWith(From, To, &NUL); 344 345 // The old node may still be present in a map like ExpandedIntegers or 346 // PromotedIntegers. Inform maps about the replacement. 347 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) { 348 assert(From->getValueType(i) == To->getValueType(i) && 349 "Node results don't match"); 350 ReplacedNodes[SDOperand(From, i)] = SDOperand(To, i); 351 } 352} 353 354/// RemapNode - If the specified value was already legalized to another value, 355/// replace it by that value. 356void DAGTypeLegalizer::RemapNode(SDOperand &N) { 357 DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.find(N); 358 if (I != ReplacedNodes.end()) { 359 // Use path compression to speed up future lookups if values get multiply 360 // replaced with other values. 361 RemapNode(I->second); 362 N = I->second; 363 } 364} 365 366/// ExpungeNode - If N has a bogus mapping in ReplacedNodes, eliminate it. 367/// This can occur when a node is deleted then reallocated as a new node - 368/// the mapping in ReplacedNodes applies to the deleted node, not the new 369/// one. 370/// The only map that can have a deleted node as a source is ReplacedNodes. 371/// Other maps can have deleted nodes as targets, but since their looked-up 372/// values are always immediately remapped using RemapNode, resulting in a 373/// not-deleted node, this is harmless as long as ReplacedNodes/RemapNode 374/// always performs correct mappings. In order to keep the mapping correct, 375/// ExpungeNode should be called on any new nodes *before* adding them as 376/// either source or target to ReplacedNodes (which typically means calling 377/// Expunge when a new node is first seen, since it may no longer be marked 378/// NewNode by the time it is added to ReplacedNodes). 379void DAGTypeLegalizer::ExpungeNode(SDNode *N) { 380 if (N->getNodeId() != NewNode) 381 return; 382 383 // If N is not remapped by ReplacedNodes then there is nothing to do. 384 unsigned i, e; 385 for (i = 0, e = N->getNumValues(); i != e; ++i) 386 if (ReplacedNodes.find(SDOperand(N, i)) != ReplacedNodes.end()) 387 break; 388 389 if (i == e) 390 return; 391 392 // Remove N from all maps - this is expensive but rare. 393 394 for (DenseMap<SDOperand, SDOperand>::iterator I = PromotedIntegers.begin(), 395 E = PromotedIntegers.end(); I != E; ++I) { 396 assert(I->first.Val != N); 397 RemapNode(I->second); 398 } 399 400 for (DenseMap<SDOperand, SDOperand>::iterator I = SoftenedFloats.begin(), 401 E = SoftenedFloats.end(); I != E; ++I) { 402 assert(I->first.Val != N); 403 RemapNode(I->second); 404 } 405 406 for (DenseMap<SDOperand, SDOperand>::iterator I = ScalarizedVectors.begin(), 407 E = ScalarizedVectors.end(); I != E; ++I) { 408 assert(I->first.Val != N); 409 RemapNode(I->second); 410 } 411 412 for (DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator 413 I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){ 414 assert(I->first.Val != N); 415 RemapNode(I->second.first); 416 RemapNode(I->second.second); 417 } 418 419 for (DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator 420 I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) { 421 assert(I->first.Val != N); 422 RemapNode(I->second.first); 423 RemapNode(I->second.second); 424 } 425 426 for (DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator 427 I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) { 428 assert(I->first.Val != N); 429 RemapNode(I->second.first); 430 RemapNode(I->second.second); 431 } 432 433 for (DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.begin(), 434 E = ReplacedNodes.end(); I != E; ++I) 435 RemapNode(I->second); 436 437 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 438 ReplacedNodes.erase(SDOperand(N, i)); 439} 440 441void DAGTypeLegalizer::SetPromotedInteger(SDOperand Op, SDOperand Result) { 442 AnalyzeNewNode(Result.Val); 443 444 SDOperand &OpEntry = PromotedIntegers[Op]; 445 assert(OpEntry.Val == 0 && "Node is already promoted!"); 446 OpEntry = Result; 447} 448 449void DAGTypeLegalizer::SetSoftenedFloat(SDOperand Op, SDOperand Result) { 450 AnalyzeNewNode(Result.Val); 451 452 SDOperand &OpEntry = SoftenedFloats[Op]; 453 assert(OpEntry.Val == 0 && "Node is already converted to integer!"); 454 OpEntry = Result; 455} 456 457void DAGTypeLegalizer::SetScalarizedVector(SDOperand Op, SDOperand Result) { 458 AnalyzeNewNode(Result.Val); 459 460 SDOperand &OpEntry = ScalarizedVectors[Op]; 461 assert(OpEntry.Val == 0 && "Node is already scalarized!"); 462 OpEntry = Result; 463} 464 465void DAGTypeLegalizer::GetExpandedInteger(SDOperand Op, SDOperand &Lo, 466 SDOperand &Hi) { 467 std::pair<SDOperand, SDOperand> &Entry = ExpandedIntegers[Op]; 468 RemapNode(Entry.first); 469 RemapNode(Entry.second); 470 assert(Entry.first.Val && "Operand isn't expanded"); 471 Lo = Entry.first; 472 Hi = Entry.second; 473} 474 475void DAGTypeLegalizer::SetExpandedInteger(SDOperand Op, SDOperand Lo, 476 SDOperand Hi) { 477 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 478 AnalyzeNewNode(Lo.Val); 479 AnalyzeNewNode(Hi.Val); 480 481 // Remember that this is the result of the node. 482 std::pair<SDOperand, SDOperand> &Entry = ExpandedIntegers[Op]; 483 assert(Entry.first.Val == 0 && "Node already expanded"); 484 Entry.first = Lo; 485 Entry.second = Hi; 486} 487 488void DAGTypeLegalizer::GetExpandedFloat(SDOperand Op, SDOperand &Lo, 489 SDOperand &Hi) { 490 std::pair<SDOperand, SDOperand> &Entry = ExpandedFloats[Op]; 491 RemapNode(Entry.first); 492 RemapNode(Entry.second); 493 assert(Entry.first.Val && "Operand isn't expanded"); 494 Lo = Entry.first; 495 Hi = Entry.second; 496} 497 498void DAGTypeLegalizer::SetExpandedFloat(SDOperand Op, SDOperand Lo, 499 SDOperand Hi) { 500 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 501 AnalyzeNewNode(Lo.Val); 502 AnalyzeNewNode(Hi.Val); 503 504 // Remember that this is the result of the node. 505 std::pair<SDOperand, SDOperand> &Entry = ExpandedFloats[Op]; 506 assert(Entry.first.Val == 0 && "Node already expanded"); 507 Entry.first = Lo; 508 Entry.second = Hi; 509} 510 511void DAGTypeLegalizer::GetSplitVector(SDOperand Op, SDOperand &Lo, 512 SDOperand &Hi) { 513 std::pair<SDOperand, SDOperand> &Entry = SplitVectors[Op]; 514 RemapNode(Entry.first); 515 RemapNode(Entry.second); 516 assert(Entry.first.Val && "Operand isn't split"); 517 Lo = Entry.first; 518 Hi = Entry.second; 519} 520 521void DAGTypeLegalizer::SetSplitVector(SDOperand Op, SDOperand Lo, 522 SDOperand Hi) { 523 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 524 AnalyzeNewNode(Lo.Val); 525 AnalyzeNewNode(Hi.Val); 526 527 // Remember that this is the result of the node. 528 std::pair<SDOperand, SDOperand> &Entry = SplitVectors[Op]; 529 assert(Entry.first.Val == 0 && "Node already split"); 530 Entry.first = Lo; 531 Entry.second = Hi; 532} 533 534 535//===----------------------------------------------------------------------===// 536// Utilities. 537//===----------------------------------------------------------------------===// 538 539/// BitConvertToInteger - Convert to an integer of the same size. 540SDOperand DAGTypeLegalizer::BitConvertToInteger(SDOperand Op) { 541 unsigned BitWidth = Op.getValueType().getSizeInBits(); 542 return DAG.getNode(ISD::BIT_CONVERT, MVT::getIntegerVT(BitWidth), Op); 543} 544 545SDOperand DAGTypeLegalizer::CreateStackStoreLoad(SDOperand Op, 546 MVT DestVT) { 547 // Create the stack frame object. Make sure it is aligned for both 548 // the source and destination types. 549 unsigned SrcAlign = 550 TLI.getTargetData()->getPrefTypeAlignment(Op.getValueType().getTypeForMVT()); 551 SDOperand FIPtr = DAG.CreateStackTemporary(DestVT, SrcAlign); 552 553 // Emit a store to the stack slot. 554 SDOperand Store = DAG.getStore(DAG.getEntryNode(), Op, FIPtr, NULL, 0); 555 // Result is a load from the stack slot. 556 return DAG.getLoad(DestVT, Store, FIPtr, NULL, 0); 557} 558 559/// JoinIntegers - Build an integer with low bits Lo and high bits Hi. 560SDOperand DAGTypeLegalizer::JoinIntegers(SDOperand Lo, SDOperand Hi) { 561 MVT LVT = Lo.getValueType(); 562 MVT HVT = Hi.getValueType(); 563 MVT NVT = MVT::getIntegerVT(LVT.getSizeInBits() + HVT.getSizeInBits()); 564 565 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, Lo); 566 Hi = DAG.getNode(ISD::ANY_EXTEND, NVT, Hi); 567 Hi = DAG.getNode(ISD::SHL, NVT, Hi, DAG.getConstant(LVT.getSizeInBits(), 568 TLI.getShiftAmountTy())); 569 return DAG.getNode(ISD::OR, NVT, Lo, Hi); 570} 571 572/// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT 573/// bits in Hi. 574void DAGTypeLegalizer::SplitInteger(SDOperand Op, 575 MVT LoVT, MVT HiVT, 576 SDOperand &Lo, SDOperand &Hi) { 577 assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == 578 Op.getValueType().getSizeInBits() && "Invalid integer splitting!"); 579 Lo = DAG.getNode(ISD::TRUNCATE, LoVT, Op); 580 Hi = DAG.getNode(ISD::SRL, Op.getValueType(), Op, 581 DAG.getConstant(LoVT.getSizeInBits(), 582 TLI.getShiftAmountTy())); 583 Hi = DAG.getNode(ISD::TRUNCATE, HiVT, Hi); 584} 585 586/// SplitInteger - Return the lower and upper halves of Op's bits in a value type 587/// half the size of Op's. 588void DAGTypeLegalizer::SplitInteger(SDOperand Op, 589 SDOperand &Lo, SDOperand &Hi) { 590 MVT HalfVT = MVT::getIntegerVT(Op.getValueType().getSizeInBits()/2); 591 SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); 592} 593 594/// MakeLibCall - Generate a libcall taking the given operands as arguments and 595/// returning a result of type RetVT. 596SDOperand DAGTypeLegalizer::MakeLibCall(RTLIB::Libcall LC, MVT RetVT, 597 const SDOperand *Ops, unsigned NumOps, 598 bool isSigned) { 599 TargetLowering::ArgListTy Args; 600 Args.reserve(NumOps); 601 602 TargetLowering::ArgListEntry Entry; 603 for (unsigned i = 0; i != NumOps; ++i) { 604 Entry.Node = Ops[i]; 605 Entry.Ty = Entry.Node.getValueType().getTypeForMVT(); 606 Entry.isSExt = isSigned; 607 Entry.isZExt = !isSigned; 608 Args.push_back(Entry); 609 } 610 SDOperand Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC), 611 TLI.getPointerTy()); 612 613 const Type *RetTy = RetVT.getTypeForMVT(); 614 std::pair<SDOperand,SDOperand> CallInfo = 615 TLI.LowerCallTo(DAG.getEntryNode(), RetTy, isSigned, !isSigned, false, 616 CallingConv::C, false, Callee, Args, DAG); 617 return CallInfo.first; 618} 619 620SDOperand DAGTypeLegalizer::GetVectorElementPointer(SDOperand VecPtr, MVT EltVT, 621 SDOperand Index) { 622 // Make sure the index type is big enough to compute in. 623 if (Index.getValueType().bitsGT(TLI.getPointerTy())) 624 Index = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), Index); 625 else 626 Index = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), Index); 627 628 // Calculate the element offset and add it to the pointer. 629 unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size. 630 631 Index = DAG.getNode(ISD::MUL, Index.getValueType(), Index, 632 DAG.getConstant(EltSize, Index.getValueType())); 633 return DAG.getNode(ISD::ADD, Index.getValueType(), Index, VecPtr); 634} 635 636/// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type 637/// which is split into two not necessarily identical pieces. 638void DAGTypeLegalizer::GetSplitDestVTs(MVT InVT, MVT &LoVT, MVT &HiVT) { 639 if (!InVT.isVector()) { 640 LoVT = HiVT = TLI.getTypeToTransformTo(InVT); 641 } else { 642 MVT NewEltVT = InVT.getVectorElementType(); 643 unsigned NumElements = InVT.getVectorNumElements(); 644 if ((NumElements & (NumElements-1)) == 0) { // Simple power of two vector. 645 NumElements >>= 1; 646 LoVT = HiVT = MVT::getVectorVT(NewEltVT, NumElements); 647 } else { // Non-power-of-two vectors. 648 unsigned NewNumElts_Lo = 1 << Log2_32(NumElements); 649 unsigned NewNumElts_Hi = NumElements - NewNumElts_Lo; 650 LoVT = MVT::getVectorVT(NewEltVT, NewNumElts_Lo); 651 HiVT = MVT::getVectorVT(NewEltVT, NewNumElts_Hi); 652 } 653 } 654} 655 656 657//===----------------------------------------------------------------------===// 658// Entry Point 659//===----------------------------------------------------------------------===// 660 661/// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 662/// only uses types natively supported by the target. 663/// 664/// Note that this is an involved process that may invalidate pointers into 665/// the graph. 666void SelectionDAG::LegalizeTypes() { 667 DAGTypeLegalizer(*this).run(); 668} 669