contrib/llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp

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