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