LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - LegalizeTypes.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 380 415 91.6 %
Date: 2018-10-20 13:21:21 Functions: 34 34 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13