1 //===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the SelectionDAG::LegalizeTypes method. It transforms 10 // an arbitrary well-formed SelectionDAG to only consist of legal types. This 11 // is common code shared among the LegalizeTypes*.cpp files. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "LegalizeTypes.h" 16 #include "llvm/ADT/SetVector.h" 17 #include "llvm/IR/DataLayout.h" 18 #include "llvm/Support/CommandLine.h" 19 #include "llvm/Support/ErrorHandling.h" 20 #include "llvm/Support/raw_ostream.h" 21 using namespace llvm; 22 23 #define DEBUG_TYPE "legalize-types" 24 25 static cl::opt<bool> 26 EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden); 27 28 /// Do extensive, expensive, basic correctness checking. 29 void DAGTypeLegalizer::PerformExpensiveChecks() { 30 // If a node is not processed, then none of its values should be mapped by any 31 // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 32 33 // If a node is processed, then each value with an illegal type must be mapped 34 // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 35 // Values with a legal type may be mapped by ReplacedValues, but not by any of 36 // the other maps. 37 38 // Note that these invariants may not hold momentarily when processing a node: 39 // the node being processed may be put in a map before being marked Processed. 40 41 // Note that it is possible to have nodes marked NewNode in the DAG. This can 42 // occur in two ways. Firstly, a node may be created during legalization but 43 // never passed to the legalization core. This is usually due to the implicit 44 // folding that occurs when using the DAG.getNode operators. Secondly, a new 45 // node may be passed to the legalization core, but when analyzed may morph 46 // into a different node, leaving the original node as a NewNode in the DAG. 47 // A node may morph if one of its operands changes during analysis. Whether 48 // it actually morphs or not depends on whether, after updating its operands, 49 // it is equivalent to an existing node: if so, it morphs into that existing 50 // node (CSE). An operand can change during analysis if the operand is a new 51 // node that morphs, or it is a processed value that was mapped to some other 52 // value (as recorded in ReplacedValues) in which case the operand is turned 53 // into that other value. If a node morphs then the node it morphed into will 54 // be used instead of it for legalization, however the original node continues 55 // to live on in the DAG. 56 // The conclusion is that though there may be nodes marked NewNode in the DAG, 57 // all uses of such nodes are also marked NewNode: the result is a fungus of 58 // NewNodes growing on top of the useful nodes, and perhaps using them, but 59 // not used by them. 60 61 // If a value is mapped by ReplacedValues, then it must have no uses, except 62 // by nodes marked NewNode (see above). 63 64 // The final node obtained by mapping by ReplacedValues is not marked NewNode. 65 // Note that ReplacedValues should be applied iteratively. 66 67 // Note that the ReplacedValues map may also map deleted nodes (by iterating 68 // over the DAG we never dereference deleted nodes). This means that it may 69 // also map nodes marked NewNode if the deallocated memory was reallocated as 70 // another node, and that new node was not seen by the LegalizeTypes machinery 71 // (for example because it was created but not used). In general, we cannot 72 // distinguish between new nodes and deleted nodes. 73 SmallVector<SDNode*, 16> NewNodes; 74 for (SDNode &Node : DAG.allnodes()) { 75 // Remember nodes marked NewNode - they are subject to extra checking below. 76 if (Node.getNodeId() == NewNode) 77 NewNodes.push_back(&Node); 78 79 for (unsigned i = 0, e = Node.getNumValues(); i != e; ++i) { 80 SDValue Res(&Node, i); 81 bool Failed = false; 82 // Don't create a value in map. 83 auto ResId = ValueToIdMap.lookup(Res); 84 85 unsigned Mapped = 0; 86 if (ResId) { 87 auto I = ReplacedValues.find(ResId); 88 if (I != ReplacedValues.end()) { 89 Mapped |= 1; 90 // Check that remapped values are only used by nodes marked NewNode. 91 for (SDNode::use_iterator UI = Node.use_begin(), UE = Node.use_end(); 92 UI != UE; ++UI) 93 if (UI.getUse().getResNo() == i) 94 assert(UI->getNodeId() == NewNode && 95 "Remapped value has non-trivial use!"); 96 97 // Check that the final result of applying ReplacedValues is not 98 // marked NewNode. 99 auto NewValId = I->second; 100 I = ReplacedValues.find(NewValId); 101 while (I != ReplacedValues.end()) { 102 NewValId = I->second; 103 I = ReplacedValues.find(NewValId); 104 } 105 SDValue NewVal = getSDValue(NewValId); 106 (void)NewVal; 107 assert(NewVal.getNode()->getNodeId() != NewNode && 108 "ReplacedValues maps to a new node!"); 109 } 110 if (PromotedIntegers.count(ResId)) 111 Mapped |= 2; 112 if (SoftenedFloats.count(ResId)) 113 Mapped |= 4; 114 if (ScalarizedVectors.count(ResId)) 115 Mapped |= 8; 116 if (ExpandedIntegers.count(ResId)) 117 Mapped |= 16; 118 if (ExpandedFloats.count(ResId)) 119 Mapped |= 32; 120 if (SplitVectors.count(ResId)) 121 Mapped |= 64; 122 if (WidenedVectors.count(ResId)) 123 Mapped |= 128; 124 if (PromotedFloats.count(ResId)) 125 Mapped |= 256; 126 if (SoftPromotedHalfs.count(ResId)) 127 Mapped |= 512; 128 } 129 130 if (Node.getNodeId() != Processed) { 131 // Since we allow ReplacedValues to map deleted nodes, it may map nodes 132 // marked NewNode too, since a deleted node may have been reallocated as 133 // another node that has not been seen by the LegalizeTypes machinery. 134 if ((Node.getNodeId() == NewNode && Mapped > 1) || 135 (Node.getNodeId() != NewNode && Mapped != 0)) { 136 dbgs() << "Unprocessed value in a map!"; 137 Failed = true; 138 } 139 } else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(&Node)) { 140 if (Mapped > 1) { 141 dbgs() << "Value with legal type was transformed!"; 142 Failed = true; 143 } 144 } else { 145 if (Mapped == 0) { 146 SDValue NodeById = IdToValueMap.lookup(ResId); 147 // It is possible the node has been remapped to another node and had 148 // its Id updated in the Value to Id table. The node it remapped to 149 // may not have been processed yet. Look up the Id in the Id to Value 150 // table and re-check the Processed state. If the node hasn't been 151 // remapped we'll get the same state as we got earlier. 152 if (NodeById->getNodeId() == Processed) { 153 dbgs() << "Processed value not in any map!"; 154 Failed = true; 155 } 156 } else if (Mapped & (Mapped - 1)) { 157 dbgs() << "Value in multiple maps!"; 158 Failed = true; 159 } 160 } 161 162 if (Failed) { 163 if (Mapped & 1) 164 dbgs() << " ReplacedValues"; 165 if (Mapped & 2) 166 dbgs() << " PromotedIntegers"; 167 if (Mapped & 4) 168 dbgs() << " SoftenedFloats"; 169 if (Mapped & 8) 170 dbgs() << " ScalarizedVectors"; 171 if (Mapped & 16) 172 dbgs() << " ExpandedIntegers"; 173 if (Mapped & 32) 174 dbgs() << " ExpandedFloats"; 175 if (Mapped & 64) 176 dbgs() << " SplitVectors"; 177 if (Mapped & 128) 178 dbgs() << " WidenedVectors"; 179 if (Mapped & 256) 180 dbgs() << " PromotedFloats"; 181 if (Mapped & 512) 182 dbgs() << " SoftPromoteHalfs"; 183 dbgs() << "\n"; 184 llvm_unreachable(nullptr); 185 } 186 } 187 } 188 189 #ifndef NDEBUG 190 // Checked that NewNodes are only used by other NewNodes. 191 for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) { 192 SDNode *N = NewNodes[i]; 193 for (SDNode *U : N->uses()) 194 assert(U->getNodeId() == NewNode && "NewNode used by non-NewNode!"); 195 } 196 #endif 197 } 198 199 /// This is the main entry point for the type legalizer. This does a top-down 200 /// traversal of the dag, legalizing types as it goes. Returns "true" if it made 201 /// any changes. 202 bool DAGTypeLegalizer::run() { 203 bool Changed = false; 204 205 // Create a dummy node (which is not added to allnodes), that adds a reference 206 // to the root node, preventing it from being deleted, and tracking any 207 // changes of the root. 208 HandleSDNode Dummy(DAG.getRoot()); 209 Dummy.setNodeId(Unanalyzed); 210 211 // The root of the dag may dangle to deleted nodes until the type legalizer is 212 // done. Set it to null to avoid confusion. 213 DAG.setRoot(SDValue()); 214 215 // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess' 216 // (and remembering them) if they are leaves and assigning 'Unanalyzed' if 217 // non-leaves. 218 for (SDNode &Node : DAG.allnodes()) { 219 if (Node.getNumOperands() == 0) { 220 Node.setNodeId(ReadyToProcess); 221 Worklist.push_back(&Node); 222 } else { 223 Node.setNodeId(Unanalyzed); 224 } 225 } 226 227 // Now that we have a set of nodes to process, handle them all. 228 while (!Worklist.empty()) { 229 #ifndef EXPENSIVE_CHECKS 230 if (EnableExpensiveChecks) 231 #endif 232 PerformExpensiveChecks(); 233 234 SDNode *N = Worklist.pop_back_val(); 235 assert(N->getNodeId() == ReadyToProcess && 236 "Node should be ready if on worklist!"); 237 238 LLVM_DEBUG(dbgs() << "Legalizing node: "; N->dump(&DAG)); 239 if (IgnoreNodeResults(N)) { 240 LLVM_DEBUG(dbgs() << "Ignoring node results\n"); 241 goto ScanOperands; 242 } 243 244 // Scan the values produced by the node, checking to see if any result 245 // types are illegal. 246 for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) { 247 EVT ResultVT = N->getValueType(i); 248 LLVM_DEBUG(dbgs() << "Analyzing result type: " << ResultVT << "\n"); 249 switch (getTypeAction(ResultVT)) { 250 case TargetLowering::TypeLegal: 251 LLVM_DEBUG(dbgs() << "Legal result type\n"); 252 break; 253 case TargetLowering::TypeScalarizeScalableVector: 254 report_fatal_error( 255 "Scalarization of scalable vectors is not supported."); 256 // The following calls must take care of *all* of the node's results, 257 // not just the illegal result they were passed (this includes results 258 // with a legal type). Results can be remapped using ReplaceValueWith, 259 // or their promoted/expanded/etc values registered in PromotedIntegers, 260 // ExpandedIntegers etc. 261 case TargetLowering::TypePromoteInteger: 262 PromoteIntegerResult(N, i); 263 Changed = true; 264 goto NodeDone; 265 case TargetLowering::TypeExpandInteger: 266 ExpandIntegerResult(N, i); 267 Changed = true; 268 goto NodeDone; 269 case TargetLowering::TypeSoftenFloat: 270 SoftenFloatResult(N, i); 271 Changed = true; 272 goto NodeDone; 273 case TargetLowering::TypeExpandFloat: 274 ExpandFloatResult(N, i); 275 Changed = true; 276 goto NodeDone; 277 case TargetLowering::TypeScalarizeVector: 278 ScalarizeVectorResult(N, i); 279 Changed = true; 280 goto NodeDone; 281 case TargetLowering::TypeSplitVector: 282 SplitVectorResult(N, i); 283 Changed = true; 284 goto NodeDone; 285 case TargetLowering::TypeWidenVector: 286 WidenVectorResult(N, i); 287 Changed = true; 288 goto NodeDone; 289 case TargetLowering::TypePromoteFloat: 290 PromoteFloatResult(N, i); 291 Changed = true; 292 goto NodeDone; 293 case TargetLowering::TypeSoftPromoteHalf: 294 SoftPromoteHalfResult(N, i); 295 Changed = true; 296 goto NodeDone; 297 } 298 } 299 300 ScanOperands: 301 // Scan the operand list for the node, handling any nodes with operands that 302 // are illegal. 303 { 304 unsigned NumOperands = N->getNumOperands(); 305 bool NeedsReanalyzing = false; 306 unsigned i; 307 for (i = 0; i != NumOperands; ++i) { 308 if (IgnoreNodeResults(N->getOperand(i).getNode())) 309 continue; 310 311 const auto &Op = N->getOperand(i); 312 LLVM_DEBUG(dbgs() << "Analyzing operand: "; Op.dump(&DAG)); 313 EVT OpVT = Op.getValueType(); 314 switch (getTypeAction(OpVT)) { 315 case TargetLowering::TypeLegal: 316 LLVM_DEBUG(dbgs() << "Legal operand\n"); 317 continue; 318 case TargetLowering::TypeScalarizeScalableVector: 319 report_fatal_error( 320 "Scalarization of scalable vectors is not supported."); 321 // The following calls must either replace all of the node's results 322 // using ReplaceValueWith, and return "false"; or update the node's 323 // operands in place, and return "true". 324 case TargetLowering::TypePromoteInteger: 325 NeedsReanalyzing = PromoteIntegerOperand(N, i); 326 Changed = true; 327 break; 328 case TargetLowering::TypeExpandInteger: 329 NeedsReanalyzing = ExpandIntegerOperand(N, i); 330 Changed = true; 331 break; 332 case TargetLowering::TypeSoftenFloat: 333 NeedsReanalyzing = SoftenFloatOperand(N, i); 334 Changed = true; 335 break; 336 case TargetLowering::TypeExpandFloat: 337 NeedsReanalyzing = ExpandFloatOperand(N, i); 338 Changed = true; 339 break; 340 case TargetLowering::TypeScalarizeVector: 341 NeedsReanalyzing = ScalarizeVectorOperand(N, i); 342 Changed = true; 343 break; 344 case TargetLowering::TypeSplitVector: 345 NeedsReanalyzing = SplitVectorOperand(N, i); 346 Changed = true; 347 break; 348 case TargetLowering::TypeWidenVector: 349 NeedsReanalyzing = WidenVectorOperand(N, i); 350 Changed = true; 351 break; 352 case TargetLowering::TypePromoteFloat: 353 NeedsReanalyzing = PromoteFloatOperand(N, i); 354 Changed = true; 355 break; 356 case TargetLowering::TypeSoftPromoteHalf: 357 NeedsReanalyzing = SoftPromoteHalfOperand(N, i); 358 Changed = true; 359 break; 360 } 361 break; 362 } 363 364 // The sub-method updated N in place. Check to see if any operands are new, 365 // and if so, mark them. If the node needs revisiting, don't add all users 366 // to the worklist etc. 367 if (NeedsReanalyzing) { 368 assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 369 370 N->setNodeId(NewNode); 371 // Recompute the NodeId and correct processed operands, adding the node to 372 // the worklist if ready. 373 SDNode *M = AnalyzeNewNode(N); 374 if (M == N) 375 // The node didn't morph - nothing special to do, it will be revisited. 376 continue; 377 378 // The node morphed - this is equivalent to legalizing by replacing every 379 // value of N with the corresponding value of M. So do that now. 380 assert(N->getNumValues() == M->getNumValues() && 381 "Node morphing changed the number of results!"); 382 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 383 // Replacing the value takes care of remapping the new value. 384 ReplaceValueWith(SDValue(N, i), SDValue(M, i)); 385 assert(N->getNodeId() == NewNode && "Unexpected node state!"); 386 // The node continues to live on as part of the NewNode fungus that 387 // grows on top of the useful nodes. Nothing more needs to be done 388 // with it - move on to the next node. 389 continue; 390 } 391 392 if (i == NumOperands) { 393 LLVM_DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); 394 dbgs() << "\n"); 395 } 396 } 397 NodeDone: 398 399 // If we reach here, the node was processed, potentially creating new nodes. 400 // Mark it as processed and add its users to the worklist as appropriate. 401 assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 402 N->setNodeId(Processed); 403 404 for (SDNode *User : N->uses()) { 405 int NodeId = User->getNodeId(); 406 407 // This node has two options: it can either be a new node or its Node ID 408 // may be a count of the number of operands it has that are not ready. 409 if (NodeId > 0) { 410 User->setNodeId(NodeId-1); 411 412 // If this was the last use it was waiting on, add it to the ready list. 413 if (NodeId-1 == ReadyToProcess) 414 Worklist.push_back(User); 415 continue; 416 } 417 418 // If this is an unreachable new node, then ignore it. If it ever becomes 419 // reachable by being used by a newly created node then it will be handled 420 // by AnalyzeNewNode. 421 if (NodeId == NewNode) 422 continue; 423 424 // Otherwise, this node is new: this is the first operand of it that 425 // became ready. Its new NodeId is the number of operands it has minus 1 426 // (as this node is now processed). 427 assert(NodeId == Unanalyzed && "Unknown node ID!"); 428 User->setNodeId(User->getNumOperands() - 1); 429 430 // If the node only has a single operand, it is now ready. 431 if (User->getNumOperands() == 1) 432 Worklist.push_back(User); 433 } 434 } 435 436 #ifndef EXPENSIVE_CHECKS 437 if (EnableExpensiveChecks) 438 #endif 439 PerformExpensiveChecks(); 440 441 // If the root changed (e.g. it was a dead load) update the root. 442 DAG.setRoot(Dummy.getValue()); 443 444 // Remove dead nodes. This is important to do for cleanliness but also before 445 // the checking loop below. Implicit folding by the DAG.getNode operators and 446 // node morphing can cause unreachable nodes to be around with their flags set 447 // to new. 448 DAG.RemoveDeadNodes(); 449 450 // In a debug build, scan all the nodes to make sure we found them all. This 451 // ensures that there are no cycles and that everything got processed. 452 #ifndef NDEBUG 453 for (SDNode &Node : DAG.allnodes()) { 454 bool Failed = false; 455 456 // Check that all result types are legal. 457 if (!IgnoreNodeResults(&Node)) 458 for (unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i) 459 if (!isTypeLegal(Node.getValueType(i))) { 460 dbgs() << "Result type " << i << " illegal: "; 461 Node.dump(&DAG); 462 Failed = true; 463 } 464 465 // Check that all operand types are legal. 466 for (unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i) 467 if (!IgnoreNodeResults(Node.getOperand(i).getNode()) && 468 !isTypeLegal(Node.getOperand(i).getValueType())) { 469 dbgs() << "Operand type " << i << " illegal: "; 470 Node.getOperand(i).dump(&DAG); 471 Failed = true; 472 } 473 474 if (Node.getNodeId() != Processed) { 475 if (Node.getNodeId() == NewNode) 476 dbgs() << "New node not analyzed?\n"; 477 else if (Node.getNodeId() == Unanalyzed) 478 dbgs() << "Unanalyzed node not noticed?\n"; 479 else if (Node.getNodeId() > 0) 480 dbgs() << "Operand not processed?\n"; 481 else if (Node.getNodeId() == ReadyToProcess) 482 dbgs() << "Not added to worklist?\n"; 483 Failed = true; 484 } 485 486 if (Failed) { 487 Node.dump(&DAG); dbgs() << "\n"; 488 llvm_unreachable(nullptr); 489 } 490 } 491 #endif 492 493 return Changed; 494 } 495 496 /// The specified node is the root of a subtree of potentially new nodes. 497 /// Correct any processed operands (this may change the node) and calculate the 498 /// NodeId. If the node itself changes to a processed node, it is not remapped - 499 /// the caller needs to take care of this. Returns the potentially changed node. 500 SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) { 501 // If this was an existing node that is already done, we're done. 502 if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed) 503 return N; 504 505 // Okay, we know that this node is new. Recursively walk all of its operands 506 // to see if they are new also. The depth of this walk is bounded by the size 507 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 508 // about revisiting of nodes. 509 // 510 // As we walk the operands, keep track of the number of nodes that are 511 // processed. If non-zero, this will become the new nodeid of this node. 512 // Operands may morph when they are analyzed. If so, the node will be 513 // updated after all operands have been analyzed. Since this is rare, 514 // the code tries to minimize overhead in the non-morphing case. 515 516 std::vector<SDValue> NewOps; 517 unsigned NumProcessed = 0; 518 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 519 SDValue OrigOp = N->getOperand(i); 520 SDValue Op = OrigOp; 521 522 AnalyzeNewValue(Op); // Op may morph. 523 524 if (Op.getNode()->getNodeId() == Processed) 525 ++NumProcessed; 526 527 if (!NewOps.empty()) { 528 // Some previous operand changed. Add this one to the list. 529 NewOps.push_back(Op); 530 } else if (Op != OrigOp) { 531 // This is the first operand to change - add all operands so far. 532 NewOps.insert(NewOps.end(), N->op_begin(), N->op_begin() + i); 533 NewOps.push_back(Op); 534 } 535 } 536 537 // Some operands changed - update the node. 538 if (!NewOps.empty()) { 539 SDNode *M = DAG.UpdateNodeOperands(N, NewOps); 540 if (M != N) { 541 // The node morphed into a different node. Normally for this to happen 542 // the original node would have to be marked NewNode. However this can 543 // in theory momentarily not be the case while ReplaceValueWith is doing 544 // its stuff. Mark the original node NewNode to help basic correctness 545 // checking. 546 N->setNodeId(NewNode); 547 if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed) 548 // It morphed into a previously analyzed node - nothing more to do. 549 return M; 550 551 // It morphed into a different new node. Do the equivalent of passing 552 // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need 553 // to remap the operands, since they are the same as the operands we 554 // remapped above. 555 N = M; 556 } 557 } 558 559 // Calculate the NodeId. 560 N->setNodeId(N->getNumOperands() - NumProcessed); 561 if (N->getNodeId() == ReadyToProcess) 562 Worklist.push_back(N); 563 564 return N; 565 } 566 567 /// Call AnalyzeNewNode, updating the node in Val if needed. 568 /// If the node changes to a processed node, then remap it. 569 void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) { 570 Val.setNode(AnalyzeNewNode(Val.getNode())); 571 if (Val.getNode()->getNodeId() == Processed) 572 // We were passed a processed node, or it morphed into one - remap it. 573 RemapValue(Val); 574 } 575 576 /// If the specified value was already legalized to another value, 577 /// replace it by that value. 578 void DAGTypeLegalizer::RemapValue(SDValue &V) { 579 auto Id = getTableId(V); 580 V = getSDValue(Id); 581 } 582 583 void DAGTypeLegalizer::RemapId(TableId &Id) { 584 auto I = ReplacedValues.find(Id); 585 if (I != ReplacedValues.end()) { 586 assert(Id != I->second && "Id is mapped to itself."); 587 // Use path compression to speed up future lookups if values get multiply 588 // replaced with other values. 589 RemapId(I->second); 590 Id = I->second; 591 592 // Note that N = IdToValueMap[Id] it is possible to have 593 // N.getNode()->getNodeId() == NewNode at this point because it is possible 594 // for a node to be put in the map before being processed. 595 } 596 } 597 598 namespace { 599 /// This class is a DAGUpdateListener that listens for updates to nodes and 600 /// recomputes their ready state. 601 class NodeUpdateListener : public SelectionDAG::DAGUpdateListener { 602 DAGTypeLegalizer &DTL; 603 SmallSetVector<SDNode*, 16> &NodesToAnalyze; 604 public: 605 explicit NodeUpdateListener(DAGTypeLegalizer &dtl, 606 SmallSetVector<SDNode*, 16> &nta) 607 : SelectionDAG::DAGUpdateListener(dtl.getDAG()), 608 DTL(dtl), NodesToAnalyze(nta) {} 609 610 void NodeDeleted(SDNode *N, SDNode *E) override { 611 assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 612 N->getNodeId() != DAGTypeLegalizer::Processed && 613 "Invalid node ID for RAUW deletion!"); 614 // It is possible, though rare, for the deleted node N to occur as a 615 // target in a map, so note the replacement N -> E in ReplacedValues. 616 assert(E && "Node not replaced?"); 617 DTL.NoteDeletion(N, E); 618 619 // In theory the deleted node could also have been scheduled for analysis. 620 // So remove it from the set of nodes which will be analyzed. 621 NodesToAnalyze.remove(N); 622 623 // In general nothing needs to be done for E, since it didn't change but 624 // only gained new uses. However N -> E was just added to ReplacedValues, 625 // and the result of a ReplacedValues mapping is not allowed to be marked 626 // NewNode. So if E is marked NewNode, then it needs to be analyzed. 627 if (E->getNodeId() == DAGTypeLegalizer::NewNode) 628 NodesToAnalyze.insert(E); 629 } 630 631 void NodeUpdated(SDNode *N) override { 632 // Node updates can mean pretty much anything. It is possible that an 633 // operand was set to something already processed (f.e.) in which case 634 // this node could become ready. Recompute its flags. 635 assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 636 N->getNodeId() != DAGTypeLegalizer::Processed && 637 "Invalid node ID for RAUW deletion!"); 638 N->setNodeId(DAGTypeLegalizer::NewNode); 639 NodesToAnalyze.insert(N); 640 } 641 }; 642 } 643 644 645 /// The specified value was legalized to the specified other value. 646 /// Update the DAG and NodeIds replacing any uses of From to use To instead. 647 void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { 648 assert(From.getNode() != To.getNode() && "Potential legalization loop!"); 649 650 // If expansion produced new nodes, make sure they are properly marked. 651 AnalyzeNewValue(To); 652 653 // Anything that used the old node should now use the new one. Note that this 654 // can potentially cause recursive merging. 655 SmallSetVector<SDNode*, 16> NodesToAnalyze; 656 NodeUpdateListener NUL(*this, NodesToAnalyze); 657 do { 658 659 // The old node may be present in a map like ExpandedIntegers or 660 // PromotedIntegers. Inform maps about the replacement. 661 auto FromId = getTableId(From); 662 auto ToId = getTableId(To); 663 664 if (FromId != ToId) 665 ReplacedValues[FromId] = ToId; 666 DAG.ReplaceAllUsesOfValueWith(From, To); 667 668 // Process the list of nodes that need to be reanalyzed. 669 while (!NodesToAnalyze.empty()) { 670 SDNode *N = NodesToAnalyze.pop_back_val(); 671 if (N->getNodeId() != DAGTypeLegalizer::NewNode) 672 // The node was analyzed while reanalyzing an earlier node - it is safe 673 // to skip. Note that this is not a morphing node - otherwise it would 674 // still be marked NewNode. 675 continue; 676 677 // Analyze the node's operands and recalculate the node ID. 678 SDNode *M = AnalyzeNewNode(N); 679 if (M != N) { 680 // The node morphed into a different node. Make everyone use the new 681 // node instead. 682 assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!"); 683 assert(N->getNumValues() == M->getNumValues() && 684 "Node morphing changed the number of results!"); 685 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 686 SDValue OldVal(N, i); 687 SDValue NewVal(M, i); 688 if (M->getNodeId() == Processed) 689 RemapValue(NewVal); 690 // OldVal may be a target of the ReplacedValues map which was marked 691 // NewNode to force reanalysis because it was updated. Ensure that 692 // anything that ReplacedValues mapped to OldVal will now be mapped 693 // all the way to NewVal. 694 auto OldValId = getTableId(OldVal); 695 auto NewValId = getTableId(NewVal); 696 DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal); 697 if (OldValId != NewValId) 698 ReplacedValues[OldValId] = NewValId; 699 } 700 // The original node continues to exist in the DAG, marked NewNode. 701 } 702 } 703 // When recursively update nodes with new nodes, it is possible to have 704 // new uses of From due to CSE. If this happens, replace the new uses of 705 // From with To. 706 } while (!From.use_empty()); 707 } 708 709 void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) { 710 assert(Result.getValueType() == 711 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 712 "Invalid type for promoted integer"); 713 AnalyzeNewValue(Result); 714 715 auto &OpIdEntry = PromotedIntegers[getTableId(Op)]; 716 assert((OpIdEntry == 0) && "Node is already promoted!"); 717 OpIdEntry = getTableId(Result); 718 719 DAG.transferDbgValues(Op, Result); 720 } 721 722 void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) { 723 #ifndef NDEBUG 724 EVT VT = Result.getValueType(); 725 LLVMContext &Ctx = *DAG.getContext(); 726 assert((VT == EVT::getIntegerVT(Ctx, 80) || 727 VT == TLI.getTypeToTransformTo(Ctx, Op.getValueType())) && 728 "Invalid type for softened float"); 729 #endif 730 AnalyzeNewValue(Result); 731 732 auto &OpIdEntry = SoftenedFloats[getTableId(Op)]; 733 assert((OpIdEntry == 0) && "Node is already converted to integer!"); 734 OpIdEntry = getTableId(Result); 735 } 736 737 void DAGTypeLegalizer::SetPromotedFloat(SDValue Op, SDValue Result) { 738 assert(Result.getValueType() == 739 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 740 "Invalid type for promoted float"); 741 AnalyzeNewValue(Result); 742 743 auto &OpIdEntry = PromotedFloats[getTableId(Op)]; 744 assert((OpIdEntry == 0) && "Node is already promoted!"); 745 OpIdEntry = getTableId(Result); 746 } 747 748 void DAGTypeLegalizer::SetSoftPromotedHalf(SDValue Op, SDValue Result) { 749 assert(Result.getValueType() == MVT::i16 && 750 "Invalid type for soft-promoted half"); 751 AnalyzeNewValue(Result); 752 753 auto &OpIdEntry = SoftPromotedHalfs[getTableId(Op)]; 754 assert((OpIdEntry == 0) && "Node is already promoted!"); 755 OpIdEntry = getTableId(Result); 756 } 757 758 void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) { 759 // Note that in some cases vector operation operands may be greater than 760 // the vector element type. For example BUILD_VECTOR of type <1 x i1> with 761 // a constant i8 operand. 762 763 // We don't currently support the scalarization of scalable vector types. 764 assert(Result.getValueSizeInBits().getFixedValue() >= 765 Op.getScalarValueSizeInBits() && 766 "Invalid type for scalarized vector"); 767 AnalyzeNewValue(Result); 768 769 auto &OpIdEntry = ScalarizedVectors[getTableId(Op)]; 770 assert((OpIdEntry == 0) && "Node is already scalarized!"); 771 OpIdEntry = getTableId(Result); 772 } 773 774 void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo, 775 SDValue &Hi) { 776 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)]; 777 assert((Entry.first != 0) && "Operand isn't expanded"); 778 Lo = getSDValue(Entry.first); 779 Hi = getSDValue(Entry.second); 780 } 781 782 void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo, 783 SDValue Hi) { 784 assert(Lo.getValueType() == 785 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 786 Hi.getValueType() == Lo.getValueType() && 787 "Invalid type for expanded integer"); 788 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 789 AnalyzeNewValue(Lo); 790 AnalyzeNewValue(Hi); 791 792 // Transfer debug values. Don't invalidate the source debug value until it's 793 // been transferred to the high and low bits. 794 if (DAG.getDataLayout().isBigEndian()) { 795 DAG.transferDbgValues(Op, Hi, 0, Hi.getValueSizeInBits(), false); 796 DAG.transferDbgValues(Op, Lo, Hi.getValueSizeInBits(), 797 Lo.getValueSizeInBits()); 798 } else { 799 DAG.transferDbgValues(Op, Lo, 0, Lo.getValueSizeInBits(), false); 800 DAG.transferDbgValues(Op, Hi, Lo.getValueSizeInBits(), 801 Hi.getValueSizeInBits()); 802 } 803 804 // Remember that this is the result of the node. 805 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)]; 806 assert((Entry.first == 0) && "Node already expanded"); 807 Entry.first = getTableId(Lo); 808 Entry.second = getTableId(Hi); 809 } 810 811 void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo, 812 SDValue &Hi) { 813 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)]; 814 assert((Entry.first != 0) && "Operand isn't expanded"); 815 Lo = getSDValue(Entry.first); 816 Hi = getSDValue(Entry.second); 817 } 818 819 void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo, 820 SDValue Hi) { 821 assert(Lo.getValueType() == 822 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 823 Hi.getValueType() == Lo.getValueType() && 824 "Invalid type for expanded float"); 825 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 826 AnalyzeNewValue(Lo); 827 AnalyzeNewValue(Hi); 828 829 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)]; 830 assert((Entry.first == 0) && "Node already expanded"); 831 Entry.first = getTableId(Lo); 832 Entry.second = getTableId(Hi); 833 } 834 835 void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo, 836 SDValue &Hi) { 837 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)]; 838 Lo = getSDValue(Entry.first); 839 Hi = getSDValue(Entry.second); 840 assert(Lo.getNode() && "Operand isn't split"); 841 ; 842 } 843 844 void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo, 845 SDValue Hi) { 846 assert(Lo.getValueType().getVectorElementType() == 847 Op.getValueType().getVectorElementType() && 848 Lo.getValueType().getVectorElementCount() * 2 == 849 Op.getValueType().getVectorElementCount() && 850 Hi.getValueType() == Lo.getValueType() && 851 "Invalid type for split vector"); 852 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 853 AnalyzeNewValue(Lo); 854 AnalyzeNewValue(Hi); 855 856 // Remember that this is the result of the node. 857 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)]; 858 assert((Entry.first == 0) && "Node already split"); 859 Entry.first = getTableId(Lo); 860 Entry.second = getTableId(Hi); 861 } 862 863 void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { 864 assert(Result.getValueType() == 865 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 866 "Invalid type for widened vector"); 867 AnalyzeNewValue(Result); 868 869 auto &OpIdEntry = WidenedVectors[getTableId(Op)]; 870 assert((OpIdEntry == 0) && "Node already widened!"); 871 OpIdEntry = getTableId(Result); 872 } 873 874 875 //===----------------------------------------------------------------------===// 876 // Utilities. 877 //===----------------------------------------------------------------------===// 878 879 /// Convert to an integer of the same size. 880 SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) { 881 unsigned BitWidth = Op.getValueSizeInBits(); 882 return DAG.getNode(ISD::BITCAST, SDLoc(Op), 883 EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op); 884 } 885 886 /// Convert to a vector of integers of the same size. 887 SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) { 888 assert(Op.getValueType().isVector() && "Only applies to vectors!"); 889 unsigned EltWidth = Op.getScalarValueSizeInBits(); 890 EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth); 891 auto EltCnt = Op.getValueType().getVectorElementCount(); 892 return DAG.getNode(ISD::BITCAST, SDLoc(Op), 893 EVT::getVectorVT(*DAG.getContext(), EltNVT, EltCnt), Op); 894 } 895 896 SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op, 897 EVT DestVT) { 898 SDLoc dl(Op); 899 // Create the stack frame object. Make sure it is aligned for both 900 // the source and destination types. 901 902 // In cases where the vector is illegal it will be broken down into parts 903 // and stored in parts - we should use the alignment for the smallest part. 904 Align DestAlign = DAG.getReducedAlign(DestVT, /*UseABI=*/false); 905 Align OpAlign = DAG.getReducedAlign(Op.getValueType(), /*UseABI=*/false); 906 Align Align = std::max(DestAlign, OpAlign); 907 SDValue StackPtr = 908 DAG.CreateStackTemporary(Op.getValueType().getStoreSize(), Align); 909 // Emit a store to the stack slot. 910 SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, 911 MachinePointerInfo(), Align); 912 // Result is a load from the stack slot. 913 return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo(), Align); 914 } 915 916 /// Replace the node's results with custom code provided by the target and 917 /// return "true", or do nothing and return "false". 918 /// The last parameter is FALSE if we are dealing with a node with legal 919 /// result types and illegal operand. The second parameter denotes the type of 920 /// illegal OperandNo in that case. 921 /// The last parameter being TRUE means we are dealing with a 922 /// node with illegal result types. The second parameter denotes the type of 923 /// illegal ResNo in that case. 924 bool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) { 925 // See if the target wants to custom lower this node. 926 if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 927 return false; 928 929 SmallVector<SDValue, 8> Results; 930 if (LegalizeResult) 931 TLI.ReplaceNodeResults(N, Results, DAG); 932 else 933 TLI.LowerOperationWrapper(N, Results, DAG); 934 935 if (Results.empty()) 936 // The target didn't want to custom lower it after all. 937 return false; 938 939 // Make everything that once used N's values now use those in Results instead. 940 assert(Results.size() == N->getNumValues() && 941 "Custom lowering returned the wrong number of results!"); 942 for (unsigned i = 0, e = Results.size(); i != e; ++i) { 943 ReplaceValueWith(SDValue(N, i), Results[i]); 944 } 945 return true; 946 } 947 948 949 /// Widen the node's results with custom code provided by the target and return 950 /// "true", or do nothing and return "false". 951 bool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) { 952 // See if the target wants to custom lower this node. 953 if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 954 return false; 955 956 SmallVector<SDValue, 8> Results; 957 TLI.ReplaceNodeResults(N, Results, DAG); 958 959 if (Results.empty()) 960 // The target didn't want to custom widen lower its result after all. 961 return false; 962 963 // Update the widening map. 964 assert(Results.size() == N->getNumValues() && 965 "Custom lowering returned the wrong number of results!"); 966 for (unsigned i = 0, e = Results.size(); i != e; ++i) { 967 // If this is a chain output or already widened just replace it. 968 bool WasWidened = SDValue(N, i).getValueType() != Results[i].getValueType(); 969 if (WasWidened) 970 SetWidenedVector(SDValue(N, i), Results[i]); 971 else 972 ReplaceValueWith(SDValue(N, i), Results[i]); 973 } 974 return true; 975 } 976 977 SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) { 978 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 979 if (i != ResNo) 980 ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i))); 981 return SDValue(N->getOperand(ResNo)); 982 } 983 984 /// Use ISD::EXTRACT_ELEMENT nodes to extract the low and high parts of the 985 /// given value. 986 void DAGTypeLegalizer::GetPairElements(SDValue Pair, 987 SDValue &Lo, SDValue &Hi) { 988 SDLoc dl(Pair); 989 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType()); 990 std::tie(Lo, Hi) = DAG.SplitScalar(Pair, dl, NVT, NVT); 991 } 992 993 /// Build an integer with low bits Lo and high bits Hi. 994 SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) { 995 // Arbitrarily use dlHi for result SDLoc 996 SDLoc dlHi(Hi); 997 SDLoc dlLo(Lo); 998 EVT LVT = Lo.getValueType(); 999 EVT HVT = Hi.getValueType(); 1000 EVT NVT = EVT::getIntegerVT(*DAG.getContext(), 1001 LVT.getSizeInBits() + HVT.getSizeInBits()); 1002 1003 EVT ShiftAmtVT = TLI.getShiftAmountTy(NVT, DAG.getDataLayout()); 1004 Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo); 1005 Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi); 1006 Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi, 1007 DAG.getConstant(LVT.getSizeInBits(), dlHi, ShiftAmtVT)); 1008 return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi); 1009 } 1010 1011 /// Promote the given target boolean to a target boolean of the given type. 1012 /// A target boolean is an integer value, not necessarily of type i1, the bits 1013 /// of which conform to getBooleanContents. 1014 /// 1015 /// ValVT is the type of values that produced the boolean. 1016 SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT ValVT) { 1017 return TLI.promoteTargetBoolean(DAG, Bool, ValVT); 1018 } 1019 1020 /// Return the lower LoVT bits of Op in Lo and the upper HiVT bits in Hi. 1021 void DAGTypeLegalizer::SplitInteger(SDValue Op, 1022 EVT LoVT, EVT HiVT, 1023 SDValue &Lo, SDValue &Hi) { 1024 SDLoc dl(Op); 1025 assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == 1026 Op.getValueSizeInBits() && "Invalid integer splitting!"); 1027 Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op); 1028 unsigned ReqShiftAmountInBits = 1029 Log2_32_Ceil(Op.getValueType().getSizeInBits()); 1030 MVT ShiftAmountTy = 1031 TLI.getScalarShiftAmountTy(DAG.getDataLayout(), Op.getValueType()); 1032 if (ReqShiftAmountInBits > ShiftAmountTy.getSizeInBits()) 1033 ShiftAmountTy = MVT::getIntegerVT(NextPowerOf2(ReqShiftAmountInBits)); 1034 Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op, 1035 DAG.getConstant(LoVT.getSizeInBits(), dl, ShiftAmountTy)); 1036 Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi); 1037 } 1038 1039 /// Return the lower and upper halves of Op's bits in a value type half the 1040 /// size of Op's. 1041 void DAGTypeLegalizer::SplitInteger(SDValue Op, 1042 SDValue &Lo, SDValue &Hi) { 1043 EVT HalfVT = 1044 EVT::getIntegerVT(*DAG.getContext(), Op.getValueSizeInBits() / 2); 1045 SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); 1046 } 1047 1048 1049 //===----------------------------------------------------------------------===// 1050 // Entry Point 1051 //===----------------------------------------------------------------------===// 1052 1053 /// This transforms the SelectionDAG into a SelectionDAG that only uses types 1054 /// natively supported by the target. Returns "true" if it made any changes. 1055 /// 1056 /// Note that this is an involved process that may invalidate pointers into 1057 /// the graph. 1058 bool SelectionDAG::LegalizeTypes() { 1059 return DAGTypeLegalizer(*this).run(); 1060 } 1061