LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - LegalizeTypes.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 480 520 92.3 %
Date: 2017-09-14 15:23:50 Functions: 38 40 95.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/CodeGen/MachineModuleInfo.h"
      21             : #include "llvm/IR/CallingConv.h"
      22             : #include "llvm/IR/DataLayout.h"
      23             : #include "llvm/IR/DebugInfoMetadata.h"
      24             : #include "llvm/Support/CommandLine.h"
      25             : #include "llvm/Support/ErrorHandling.h"
      26             : #include "llvm/Support/raw_ostream.h"
      27             : using namespace llvm;
      28             : 
      29             : #define DEBUG_TYPE "legalize-types"
      30             : 
      31             : static cl::opt<bool>
      32       72306 : EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden);
      33             : 
      34             : /// Do extensive, expensive, sanity checking.
      35        3033 : void DAGTypeLegalizer::PerformExpensiveChecks() {
      36             :   // If a node is not processed, then none of its values should be mapped by any
      37             :   // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
      38             : 
      39             :   // If a node is processed, then each value with an illegal type must be mapped
      40             :   // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues.
      41             :   // Values with a legal type may be mapped by ReplacedValues, but not by any of
      42             :   // the other maps.
      43             : 
      44             :   // Note that these invariants may not hold momentarily when processing a node:
      45             :   // the node being processed may be put in a map before being marked Processed.
      46             : 
      47             :   // Note that it is possible to have nodes marked NewNode in the DAG.  This can
      48             :   // occur in two ways.  Firstly, a node may be created during legalization but
      49             :   // never passed to the legalization core.  This is usually due to the implicit
      50             :   // folding that occurs when using the DAG.getNode operators.  Secondly, a new
      51             :   // node may be passed to the legalization core, but when analyzed may morph
      52             :   // into a different node, leaving the original node as a NewNode in the DAG.
      53             :   // A node may morph if one of its operands changes during analysis.  Whether
      54             :   // it actually morphs or not depends on whether, after updating its operands,
      55             :   // it is equivalent to an existing node: if so, it morphs into that existing
      56             :   // node (CSE).  An operand can change during analysis if the operand is a new
      57             :   // node that morphs, or it is a processed value that was mapped to some other
      58             :   // value (as recorded in ReplacedValues) in which case the operand is turned
      59             :   // into that other value.  If a node morphs then the node it morphed into will
      60             :   // be used instead of it for legalization, however the original node continues
      61             :   // to live on in the DAG.
      62             :   // The conclusion is that though there may be nodes marked NewNode in the DAG,
      63             :   // all uses of such nodes are also marked NewNode: the result is a fungus of
      64             :   // NewNodes growing on top of the useful nodes, and perhaps using them, but
      65             :   // not used by them.
      66             : 
      67             :   // If a value is mapped by ReplacedValues, then it must have no uses, except
      68             :   // by nodes marked NewNode (see above).
      69             : 
      70             :   // The final node obtained by mapping by ReplacedValues is not marked NewNode.
      71             :   // Note that ReplacedValues should be applied iteratively.
      72             : 
      73             :   // Note that the ReplacedValues map may also map deleted nodes (by iterating
      74             :   // over the DAG we never dereference deleted nodes).  This means that it may
      75             :   // also map nodes marked NewNode if the deallocated memory was reallocated as
      76             :   // another node, and that new node was not seen by the LegalizeTypes machinery
      77             :   // (for example because it was created but not used).  In general, we cannot
      78             :   // distinguish between new nodes and deleted nodes.
      79        6066 :   SmallVector<SDNode*, 16> NewNodes;
      80       77373 :   for (SDNode &Node : DAG.allnodes()) {
      81             :     // Remember nodes marked NewNode - they are subject to extra checking below.
      82       71307 :     if (Node.getNodeId() == NewNode)
      83        1085 :       NewNodes.push_back(&Node);
      84             : 
      85      230764 :     for (unsigned i = 0, e = Node.getNumValues(); i != e; ++i) {
      86       88150 :       SDValue Res(&Node, i);
      87      176300 :       EVT VT = Res.getValueType();
      88       88150 :       bool Failed = false;
      89             : 
      90       88150 :       unsigned Mapped = 0;
      91      264450 :       if (ReplacedValues.find(Res) != ReplacedValues.end()) {
      92        2734 :         Mapped |= 1;
      93             :         // Check that remapped values are only used by nodes marked NewNode.
      94             :         for (SDNode::use_iterator UI = Node.use_begin(), UE = Node.use_end();
      95        3050 :              UI != UE; ++UI)
      96         632 :           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        5468 :         SDValue NewVal = ReplacedValues[Res];
     103        2734 :         DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(NewVal);
     104        8594 :         while (I != ReplacedValues.end()) {
     105          98 :           NewVal = I->second;
     106          98 :           I = ReplacedValues.find(NewVal);
     107             :         }
     108             :         assert(NewVal.getNode()->getNodeId() != NewNode &&
     109             :                "ReplacedValues maps to a new node!");
     110             :       }
     111      264450 :       if (PromotedIntegers.find(Res) != PromotedIntegers.end())
     112         867 :         Mapped |= 2;
     113      264450 :       if (SoftenedFloats.find(Res) != SoftenedFloats.end())
     114        4765 :         Mapped |= 4;
     115      264450 :       if (ScalarizedVectors.find(Res) != ScalarizedVectors.end())
     116         810 :         Mapped |= 8;
     117      264450 :       if (ExpandedIntegers.find(Res) != ExpandedIntegers.end())
     118        2334 :         Mapped |= 16;
     119      264450 :       if (ExpandedFloats.find(Res) != ExpandedFloats.end())
     120           0 :         Mapped |= 32;
     121      264450 :       if (SplitVectors.find(Res) != SplitVectors.end())
     122        1471 :         Mapped |= 64;
     123      264450 :       if (WidenedVectors.find(Res) != WidenedVectors.end())
     124           0 :         Mapped |= 128;
     125      264450 :       if (PromotedFloats.find(Res) != PromotedFloats.end())
     126           0 :         Mapped |= 256;
     127             : 
     128       88150 :       if (Node.getNodeId() != Processed) {
     129             :         // Since we allow ReplacedValues to map deleted nodes, it may map nodes
     130             :         // marked NewNode too, since a deleted node may have been reallocated as
     131             :         // another node that has not been seen by the LegalizeTypes machinery.
     132       33495 :         if ((Node.getNodeId() == NewNode && Mapped > 1) ||
     133       32410 :             (Node.getNodeId() != NewNode && Mapped != 0)) {
     134           0 :           dbgs() << "Unprocessed value in a map!";
     135           0 :           Failed = true;
     136             :         }
     137      123810 :       } else if (isTypeLegal(VT) || IgnoreNodeResults(&Node)) {
     138       40155 :         if (Mapped > 1) {
     139           0 :           dbgs() << "Value with legal type was transformed!";
     140           0 :           Failed = true;
     141             :         }
     142             :       } else {
     143             :         // If the value can be kept in HW registers, softening machinery can
     144             :         // leave it unchanged and don't put it to any map.
     145       18351 :         if (Mapped == 0 &&
     146        7702 :             !(getTypeAction(VT) == TargetLowering::TypeSoftenFloat &&
     147        3851 :               isLegalInHWReg(VT))) {
     148           0 :           dbgs() << "Processed value not in any map!";
     149           0 :           Failed = true;
     150       14500 :         } else if (Mapped & (Mapped - 1)) {
     151           0 :           dbgs() << "Value in multiple maps!";
     152           0 :           Failed = true;
     153             :         }
     154             :       }
     155             : 
     156             :       if (Failed) {
     157           0 :         if (Mapped & 1)
     158           0 :           dbgs() << " ReplacedValues";
     159           0 :         if (Mapped & 2)
     160           0 :           dbgs() << " PromotedIntegers";
     161           0 :         if (Mapped & 4)
     162           0 :           dbgs() << " SoftenedFloats";
     163           0 :         if (Mapped & 8)
     164           0 :           dbgs() << " ScalarizedVectors";
     165           0 :         if (Mapped & 16)
     166           0 :           dbgs() << " ExpandedIntegers";
     167           0 :         if (Mapped & 32)
     168           0 :           dbgs() << " ExpandedFloats";
     169           0 :         if (Mapped & 64)
     170           0 :           dbgs() << " SplitVectors";
     171           0 :         if (Mapped & 128)
     172           0 :           dbgs() << " WidenedVectors";
     173           0 :         if (Mapped & 256)
     174           0 :           dbgs() << " PromotedFloats";
     175           0 :         dbgs() << "\n";
     176           0 :         llvm_unreachable(nullptr);
     177             :       }
     178             :     }
     179             :   }
     180             : 
     181             :   // Checked that NewNodes are only used by other NewNodes.
     182        7151 :   for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) {
     183        2170 :     SDNode *N = NewNodes[i];
     184        1085 :     for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
     185        1085 :          UI != UE; ++UI)
     186             :       assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!");
     187             :   }
     188        3033 : }
     189             : 
     190             : /// This is the main entry point for the type legalizer. This does a top-down
     191             : /// traversal of the dag, legalizing types as it goes. Returns "true" if it made
     192             : /// any changes.
     193      296481 : bool DAGTypeLegalizer::run() {
     194      296481 :   bool Changed = false;
     195             : 
     196             :   // Create a dummy node (which is not added to allnodes), that adds a reference
     197             :   // to the root node, preventing it from being deleted, and tracking any
     198             :   // changes of the root.
     199      889443 :   HandleSDNode Dummy(DAG.getRoot());
     200      592962 :   Dummy.setNodeId(Unanalyzed);
     201             : 
     202             :   // The root of the dag may dangle to deleted nodes until the type legalizer is
     203             :   // done.  Set it to null to avoid confusion.
     204      296481 :   DAG.setRoot(SDValue());
     205             : 
     206             :   // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess'
     207             :   // (and remembering them) if they are leaves and assigning 'Unanalyzed' if
     208             :   // non-leaves.
     209     8322118 :   for (SDNode &Node : DAG.allnodes()) {
     210     7729156 :     if (Node.getNumOperands() == 0) {
     211             :       AddToWorklist(&Node);
     212             :     } else {
     213     4316878 :       Node.setNodeId(Unanalyzed);
     214             :     }
     215             :   }
     216             : 
     217             :   // Now that we have a set of nodes to process, handle them all.
     218    10258346 :   while (!Worklist.empty()) {
     219             : #ifndef EXPENSIVE_CHECKS
     220     9961865 :     if (EnableExpensiveChecks)
     221             : #endif
     222        2904 :       PerformExpensiveChecks();
     223             : 
     224    19923730 :     SDNode *N = Worklist.back();
     225    19923730 :     Worklist.pop_back();
     226             :     assert(N->getNodeId() == ReadyToProcess &&
     227             :            "Node should be ready if on worklist!");
     228             : 
     229    19923730 :     if (IgnoreNodeResults(N))
     230             :       goto ScanOperands;
     231             : 
     232             :     // Scan the values produced by the node, checking to see if any result
     233             :     // types are illegal.
     234    30652457 :     for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) {
     235    23676050 :       EVT ResultVT = N->getValueType(i);
     236    23676050 :       switch (getTypeAction(ResultVT)) {
     237             :       case TargetLowering::TypeLegal:
     238             :         break;
     239             :       // The following calls must take care of *all* of the node's results,
     240             :       // not just the illegal result they were passed (this includes results
     241             :       // with a legal type).  Results can be remapped using ReplaceValueWith,
     242             :       // or their promoted/expanded/etc values registered in PromotedIntegers,
     243             :       // ExpandedIntegers etc.
     244      157569 :       case TargetLowering::TypePromoteInteger:
     245      157569 :         PromoteIntegerResult(N, i);
     246      157569 :         Changed = true;
     247      157569 :         goto NodeDone;
     248      327034 :       case TargetLowering::TypeExpandInteger:
     249      327034 :         ExpandIntegerResult(N, i);
     250      327034 :         Changed = true;
     251      327034 :         goto NodeDone;
     252        3362 :       case TargetLowering::TypeSoftenFloat:
     253        3362 :         Changed = SoftenFloatResult(N, i);
     254        3362 :         if (Changed)
     255             :           goto NodeDone;
     256             :         // If not changed, the result type should be legally in register.
     257             :         assert(isLegalInHWReg(ResultVT) &&
     258             :                "Unchanged SoftenFloatResult should be legal in register!");
     259             :         goto ScanOperands;
     260         254 :       case TargetLowering::TypeExpandFloat:
     261         254 :         ExpandFloatResult(N, i);
     262         254 :         Changed = true;
     263         254 :         goto NodeDone;
     264       52778 :       case TargetLowering::TypeScalarizeVector:
     265       52778 :         ScalarizeVectorResult(N, i);
     266       52778 :         Changed = true;
     267       52778 :         goto NodeDone;
     268       63866 :       case TargetLowering::TypeSplitVector:
     269       63866 :         SplitVectorResult(N, i);
     270       63866 :         Changed = true;
     271       63866 :         goto NodeDone;
     272        5914 :       case TargetLowering::TypeWidenVector:
     273        5914 :         WidenVectorResult(N, i);
     274        5914 :         Changed = true;
     275        5914 :         goto NodeDone;
     276        4341 :       case TargetLowering::TypePromoteFloat:
     277        4341 :         PromoteFloatResult(N, i);
     278        4341 :         Changed = true;
     279        4341 :         goto NodeDone;
     280             :       }
     281             :     }
     282             : 
     283     9346747 : ScanOperands:
     284             :     // Scan the operand list for the node, handling any nodes with operands that
     285             :     // are illegal.
     286             :     {
     287    18694638 :     unsigned NumOperands = N->getNumOperands();
     288     9347319 :     bool NeedsReanalyzing = false;
     289             :     unsigned i;
     290    24369009 :     for (i = 0; i != NumOperands; ++i) {
     291    30970502 :       if (IgnoreNodeResults(N->getOperand(i).getNode()))
     292    15936901 :         continue;
     293             : 
     294    43710120 :       EVT OpVT = N->getOperand(i).getValueType();
     295    43246559 :       switch (getTypeAction(OpVT)) {
     296    14106479 :       case TargetLowering::TypeLegal:
     297    14106479 :         continue;
     298             :       // The following calls must either replace all of the node's results
     299             :       // using ReplaceValueWith, and return "false"; or update the node's
     300             :       // operands in place, and return "true".
     301      176323 :       case TargetLowering::TypePromoteInteger:
     302      176323 :         NeedsReanalyzing = PromoteIntegerOperand(N, i);
     303      176323 :         Changed = true;
     304      176323 :         break;
     305      200617 :       case TargetLowering::TypeExpandInteger:
     306      200617 :         NeedsReanalyzing = ExpandIntegerOperand(N, i);
     307      200617 :         Changed = true;
     308      200617 :         break;
     309        1828 :       case TargetLowering::TypeSoftenFloat:
     310        1828 :         NeedsReanalyzing = SoftenFloatOperand(N, i);
     311        1828 :         Changed = true;
     312        1828 :         break;
     313          92 :       case TargetLowering::TypeExpandFloat:
     314          92 :         NeedsReanalyzing = ExpandFloatOperand(N, i);
     315          92 :         Changed = true;
     316          92 :         break;
     317       16627 :       case TargetLowering::TypeScalarizeVector:
     318       16627 :         NeedsReanalyzing = ScalarizeVectorOperand(N, i);
     319       16627 :         Changed = true;
     320       16627 :         break;
     321       60853 :       case TargetLowering::TypeSplitVector:
     322       60853 :         NeedsReanalyzing = SplitVectorOperand(N, i);
     323       60853 :         Changed = true;
     324       60853 :         break;
     325        5387 :       case TargetLowering::TypeWidenVector:
     326        5387 :         NeedsReanalyzing = WidenVectorOperand(N, i);
     327        5387 :         Changed = true;
     328        5387 :         break;
     329        1834 :       case TargetLowering::TypePromoteFloat:
     330        1834 :         NeedsReanalyzing = PromoteFloatOperand(N, i);
     331        1834 :         Changed = true;
     332        1834 :         break;
     333             :       }
     334             :       break;
     335             :     }
     336             : 
     337             :     // The sub-method updated N in place.  Check to see if any operands are new,
     338             :     // and if so, mark them.  If the node needs revisiting, don't add all users
     339             :     // to the worklist etc.
     340     9347319 :     if (NeedsReanalyzing) {
     341             :       assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
     342             : 
     343      132042 :       N->setNodeId(NewNode);
     344             :       // Recompute the NodeId and correct processed operands, adding the node to
     345             :       // the worklist if ready.
     346       66021 :       SDNode *M = AnalyzeNewNode(N);
     347       66021 :       if (M == N)
     348             :         // The node didn't morph - nothing special to do, it will be revisited.
     349       66019 :         continue;
     350             : 
     351             :       // The node morphed - this is equivalent to legalizing by replacing every
     352             :       // value of N with the corresponding value of M.  So do that now.
     353             :       assert(N->getNumValues() == M->getNumValues() &&
     354             :              "Node morphing changed the number of results!");
     355           8 :       for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
     356             :         // Replacing the value takes care of remapping the new value.
     357           8 :         ReplaceValueWith(SDValue(N, i), SDValue(M, i));
     358             :       assert(N->getNodeId() == NewNode && "Unexpected node state!");
     359             :       // The node continues to live on as part of the NewNode fungus that
     360             :       // grows on top of the useful nodes.  Nothing more needs to be done
     361             :       // with it - move on to the next node.
     362           2 :       continue;
     363             :     }
     364             : 
     365             :     if (i == NumOperands) {
     366             :       DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); dbgs() << "\n");
     367             :     }
     368             :     }
     369     9895844 : NodeDone:
     370             : 
     371             :     // If we reach here, the node was processed, potentially creating new nodes.
     372             :     // Mark it as processed and add its users to the worklist as appropriate.
     373             :     assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
     374    19791688 :     N->setNodeId(Processed);
     375             : 
     376     9895844 :     for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
     377    24690287 :          UI != E; ++UI) {
     378    14794443 :       SDNode *User = *UI;
     379    14794443 :       int NodeId = User->getNodeId();
     380             : 
     381             :       // This node has two options: it can either be a new node or its Node ID
     382             :       // may be a count of the number of operands it has that are not ready.
     383    25171627 :       if (NodeId > 0) {
     384    20754368 :         User->setNodeId(NodeId-1);
     385             : 
     386             :         // If this was the last use it was waiting on, add it to the ready list.
     387    10377184 :         if (NodeId-1 == ReadyToProcess)
     388     5247914 :           Worklist.push_back(User);
     389    20757264 :         continue;
     390             :       }
     391             : 
     392             :       // If this is an unreachable new node, then ignore it.  If it ever becomes
     393             :       // reachable by being used by a newly created node then it will be handled
     394             :       // by AnalyzeNewNode.
     395     4417259 :       if (NodeId == NewNode)
     396        2896 :         continue;
     397             : 
     398             :       // Otherwise, this node is new: this is the first operand of it that
     399             :       // became ready.  Its new NodeId is the number of operands it has minus 1
     400             :       // (as this node is now processed).
     401             :       assert(NodeId == Unanalyzed && "Unknown node ID!");
     402    13243089 :       User->setNodeId(User->getNumOperands() - 1);
     403             : 
     404             :       // If the node only has a single operand, it is now ready.
     405     4414363 :       if (User->getNumOperands() == 1)
     406      570785 :         Worklist.push_back(User);
     407             :     }
     408             :   }
     409             : 
     410             : #ifndef EXPENSIVE_CHECKS
     411      296481 :   if (EnableExpensiveChecks)
     412             : #endif
     413         129 :     PerformExpensiveChecks();
     414             : 
     415             :   // If the root changed (e.g. it was a dead load) update the root.
     416      592962 :   DAG.setRoot(Dummy.getValue());
     417             : 
     418             :   // Remove dead nodes.  This is important to do for cleanliness but also before
     419             :   // the checking loop below.  Implicit folding by the DAG.getNode operators and
     420             :   // node morphing can cause unreachable nodes to be around with their flags set
     421             :   // to new.
     422      296481 :   DAG.RemoveDeadNodes();
     423             : 
     424             :   // In a debug build, scan all the nodes to make sure we found them all.  This
     425             :   // ensures that there are no cycles and that everything got processed.
     426             : #ifndef NDEBUG
     427             :   for (SDNode &Node : DAG.allnodes()) {
     428             :     bool Failed = false;
     429             : 
     430             :     // Check that all result types are legal.
     431             :     // A value type is illegal if its TypeAction is not TypeLegal,
     432             :     // and TLI.RegClassForVT does not have a register class for this type.
     433             :     // For example, the x86_64 target has f128 that is not TypeLegal,
     434             :     // to have softened operators, but it also has FR128 register class to
     435             :     // pass and return f128 values. Hence a legalized node can have f128 type.
     436             :     if (!IgnoreNodeResults(&Node))
     437             :       for (unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i)
     438             :         if (!isTypeLegal(Node.getValueType(i)) &&
     439             :             !TLI.isTypeLegal(Node.getValueType(i))) {
     440             :           dbgs() << "Result type " << i << " illegal: ";
     441             :           Node.dump();
     442             :           Failed = true;
     443             :         }
     444             : 
     445             :     // Check that all operand types are legal.
     446             :     for (unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i)
     447             :       if (!IgnoreNodeResults(Node.getOperand(i).getNode()) &&
     448             :           !isTypeLegal(Node.getOperand(i).getValueType()) &&
     449             :           !TLI.isTypeLegal(Node.getOperand(i).getValueType())) {
     450             :         dbgs() << "Operand type " << i << " illegal: ";
     451             :         Node.getOperand(i).dump();
     452             :         Failed = true;
     453             :       }
     454             : 
     455             :     if (Node.getNodeId() != Processed) {
     456             :        if (Node.getNodeId() == NewNode)
     457             :          dbgs() << "New node not analyzed?\n";
     458             :        else if (Node.getNodeId() == Unanalyzed)
     459             :          dbgs() << "Unanalyzed node not noticed?\n";
     460             :        else if (Node.getNodeId() > 0)
     461             :          dbgs() << "Operand not processed?\n";
     462             :        else if (Node.getNodeId() == ReadyToProcess)
     463             :          dbgs() << "Not added to worklist?\n";
     464             :        Failed = true;
     465             :     }
     466             : 
     467             :     if (Failed) {
     468             :       Node.dump(&DAG); dbgs() << "\n";
     469             :       llvm_unreachable(nullptr);
     470             :     }
     471             :   }
     472             : #endif
     473             : 
     474      296481 :   return Changed;
     475             : }
     476             : 
     477             : /// The specified node is the root of a subtree of potentially new nodes.
     478             : /// Correct any processed operands (this may change the node) and calculate the
     479             : /// NodeId. If the node itself changes to a processed node, it is not remapped -
     480             : /// the caller needs to take care of this. Returns the potentially changed node.
     481     8420307 : SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) {
     482             :   // If this was an existing node that is already done, we're done.
     483     8420307 :   if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed)
     484             :     return N;
     485             : 
     486             :   // Remove any stale map entries.
     487     2577600 :   ExpungeNode(N);
     488             : 
     489             :   // Okay, we know that this node is new.  Recursively walk all of its operands
     490             :   // to see if they are new also.  The depth of this walk is bounded by the size
     491             :   // of the new tree that was constructed (usually 2-3 nodes), so we don't worry
     492             :   // about revisiting of nodes.
     493             :   //
     494             :   // As we walk the operands, keep track of the number of nodes that are
     495             :   // processed.  If non-zero, this will become the new nodeid of this node.
     496             :   // Operands may morph when they are analyzed.  If so, the node will be
     497             :   // updated after all operands have been analyzed.  Since this is rare,
     498             :   // the code tries to minimize overhead in the non-morphing case.
     499             : 
     500     2577600 :   std::vector<SDValue> NewOps;
     501     2577600 :   unsigned NumProcessed = 0;
     502    11536268 :   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
     503    12762136 :     SDValue OrigOp = N->getOperand(i);
     504     6381068 :     SDValue Op = OrigOp;
     505             : 
     506     6381068 :     AnalyzeNewValue(Op); // Op may morph.
     507             : 
     508     6381068 :     if (Op.getNode()->getNodeId() == Processed)
     509     3071423 :       ++NumProcessed;
     510             : 
     511     6381068 :     if (!NewOps.empty()) {
     512             :       // Some previous operand changed.  Add this one to the list.
     513        3786 :       NewOps.push_back(Op);
     514        2401 :     } else if (Op != OrigOp) {
     515             :       // This is the first operand to change - add all operands so far.
     516        9604 :       NewOps.insert(NewOps.end(), N->op_begin(), N->op_begin() + i);
     517        2401 :       NewOps.push_back(Op);
     518             :     }
     519             :   }
     520             : 
     521             :   // Some operands changed - update the node.
     522     2577600 :   if (!NewOps.empty()) {
     523        4802 :     SDNode *M = DAG.UpdateNodeOperands(N, NewOps);
     524        2401 :     if (M != N) {
     525             :       // The node morphed into a different node.  Normally for this to happen
     526             :       // the original node would have to be marked NewNode.  However this can
     527             :       // in theory momentarily not be the case while ReplaceValueWith is doing
     528             :       // its stuff.  Mark the original node NewNode to help sanity checking.
     529         604 :       N->setNodeId(NewNode);
     530         302 :       if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed)
     531             :         // It morphed into a previously analyzed node - nothing more to do.
     532             :         return M;
     533             : 
     534             :       // It morphed into a different new node.  Do the equivalent of passing
     535             :       // it to AnalyzeNewNode: expunge it and calculate the NodeId.  No need
     536             :       // to remap the operands, since they are the same as the operands we
     537             :       // remapped above.
     538           0 :       N = M;
     539           0 :       ExpungeNode(N);
     540             :     }
     541             :   }
     542             : 
     543             :   // Calculate the NodeId.
     544     7731894 :   N->setNodeId(N->getNumOperands() - NumProcessed);
     545     2577298 :   if (N->getNodeId() == ReadyToProcess)
     546      730881 :     Worklist.push_back(N);
     547             : 
     548     2577298 :   return N;
     549             : }
     550             : 
     551             : /// Call AnalyzeNewNode, updating the node in Val if needed.
     552             : /// If the node changes to a processed node, then remap it.
     553     7870923 : void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) {
     554    15741846 :   Val.setNode(AnalyzeNewNode(Val.getNode()));
     555     7870923 :   if (Val.getNode()->getNodeId() == Processed)
     556             :     // We were passed a processed node, or it morphed into one - remap it.
     557     3304318 :     RemapValue(Val);
     558     7870923 : }
     559             : 
     560             : /// If N has a bogus mapping in ReplacedValues, eliminate it.
     561             : /// This can occur when a node is deleted then reallocated as a new node -
     562             : /// the mapping in ReplacedValues applies to the deleted node, not the new
     563             : /// one.
     564             : /// The only map that can have a deleted node as a source is ReplacedValues.
     565             : /// Other maps can have deleted nodes as targets, but since their looked-up
     566             : /// values are always immediately remapped using RemapValue, resulting in a
     567             : /// not-deleted node, this is harmless as long as ReplacedValues/RemapValue
     568             : /// always performs correct mappings.  In order to keep the mapping correct,
     569             : /// ExpungeNode should be called on any new nodes *before* adding them as
     570             : /// either source or target to ReplacedValues (which typically means calling
     571             : /// Expunge when a new node is first seen, since it may no longer be marked
     572             : /// NewNode by the time it is added to ReplacedValues).
     573     3067958 : void DAGTypeLegalizer::ExpungeNode(SDNode *N) {
     574     3067958 :   if (N->getNodeId() != NewNode)
     575             :     return;
     576             : 
     577             :   // If N is not remapped by ReplacedValues then there is nothing to do.
     578             :   unsigned i, e;
     579     7656246 :   for (i = 0, e = N->getNumValues(); i != e; ++i)
     580    11211068 :     if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end())
     581             :       break;
     582             : 
     583     2427582 :   if (i == e)
     584             :     return;
     585             : 
     586             :   // Remove N from all maps - this is expensive but rare.
     587             : 
     588       60306 :   for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(),
     589       63676 :        E = PromotedIntegers.end(); I != E; ++I) {
     590             :     assert(I->first.getNode() != N);
     591       58621 :     RemapValue(I->second);
     592             :   }
     593             : 
     594        1685 :   for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(),
     595        5055 :        E = SoftenedFloats.end(); I != E; ++I) {
     596             :     assert(I->first.getNode() != N);
     597           0 :     RemapValue(I->second);
     598             :   }
     599             : 
     600       33044 :   for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(),
     601       36414 :        E = ScalarizedVectors.end(); I != E; ++I) {
     602             :     assert(I->first.getNode() != N);
     603       31359 :     RemapValue(I->second);
     604             :   }
     605             : 
     606        3047 :   for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(),
     607        6417 :        E = WidenedVectors.end(); I != E; ++I) {
     608             :     assert(I->first.getNode() != N);
     609        1362 :     RemapValue(I->second);
     610             :   }
     611             : 
     612       61890 :   for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
     613       66945 :        I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){
     614             :     assert(I->first.getNode() != N);
     615       61890 :     RemapValue(I->second.first);
     616       61890 :     RemapValue(I->second.second);
     617             :   }
     618             : 
     619          30 :   for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
     620        5085 :        I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) {
     621             :     assert(I->first.getNode() != N);
     622          30 :     RemapValue(I->second.first);
     623          30 :     RemapValue(I->second.second);
     624             :   }
     625             : 
     626       64022 :   for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
     627       69077 :        I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) {
     628             :     assert(I->first.getNode() != N);
     629       64022 :     RemapValue(I->second.first);
     630       64022 :     RemapValue(I->second.second);
     631             :   }
     632             : 
     633      136308 :   for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(),
     634      139678 :        E = ReplacedValues.end(); I != E; ++I)
     635      134623 :     RemapValue(I->second);
     636             : 
     637        5061 :   for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
     638        3382 :     ReplacedValues.erase(SDValue(N, i));
     639             : }
     640             : 
     641             : /// If the specified value was already legalized to another value,
     642             : /// replace it by that value.
     643     5201225 : void DAGTypeLegalizer::RemapValue(SDValue &N) {
     644     5201225 :   DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N);
     645    15603675 :   if (I != ReplacedValues.end()) {
     646             :     // Use path compression to speed up future lookups if values get multiply
     647             :     // replaced with other values.
     648       37213 :     RemapValue(I->second);
     649       37213 :     N = I->second;
     650             : 
     651             :     // Note that it is possible to have N.getNode()->getNodeId() == NewNode at
     652             :     // this point because it is possible for a node to be put in the map before
     653             :     // being processed.
     654             :   }
     655     5201225 : }
     656             : 
     657             : namespace {
     658             :   /// This class is a DAGUpdateListener that listens for updates to nodes and
     659             :   /// recomputes their ready state.
     660      973828 :   class NodeUpdateListener : public SelectionDAG::DAGUpdateListener {
     661             :     DAGTypeLegalizer &DTL;
     662             :     SmallSetVector<SDNode*, 16> &NodesToAnalyze;
     663             :   public:
     664             :     explicit NodeUpdateListener(DAGTypeLegalizer &dtl,
     665             :                                 SmallSetVector<SDNode*, 16> &nta)
     666      486914 :       : SelectionDAG::DAGUpdateListener(dtl.getDAG()),
     667      973828 :         DTL(dtl), NodesToAnalyze(nta) {}
     668             : 
     669        1722 :     void NodeDeleted(SDNode *N, SDNode *E) override {
     670             :       assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
     671             :              N->getNodeId() != DAGTypeLegalizer::Processed &&
     672             :              "Invalid node ID for RAUW deletion!");
     673             :       // It is possible, though rare, for the deleted node N to occur as a
     674             :       // target in a map, so note the replacement N -> E in ReplacedValues.
     675             :       assert(E && "Node not replaced?");
     676        1722 :       DTL.NoteDeletion(N, E);
     677             : 
     678             :       // In theory the deleted node could also have been scheduled for analysis.
     679             :       // So remove it from the set of nodes which will be analyzed.
     680        1722 :       NodesToAnalyze.remove(N);
     681             : 
     682             :       // In general nothing needs to be done for E, since it didn't change but
     683             :       // only gained new uses.  However N -> E was just added to ReplacedValues,
     684             :       // and the result of a ReplacedValues mapping is not allowed to be marked
     685             :       // NewNode.  So if E is marked NewNode, then it needs to be analyzed.
     686        1722 :       if (E->getNodeId() == DAGTypeLegalizer::NewNode)
     687         148 :         NodesToAnalyze.insert(E);
     688        1722 :     }
     689             : 
     690      489285 :     void NodeUpdated(SDNode *N) override {
     691             :       // Node updates can mean pretty much anything.  It is possible that an
     692             :       // operand was set to something already processed (f.e.) in which case
     693             :       // this node could become ready.  Recompute its flags.
     694             :       assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
     695             :              N->getNodeId() != DAGTypeLegalizer::Processed &&
     696             :              "Invalid node ID for RAUW deletion!");
     697      978570 :       N->setNodeId(DAGTypeLegalizer::NewNode);
     698      489285 :       NodesToAnalyze.insert(N);
     699      489285 :     }
     700             :   };
     701             : }
     702             : 
     703             : 
     704             : /// The specified value was legalized to the specified other value.
     705             : /// Update the DAG and NodeIds replacing any uses of From to use To instead.
     706      486914 : void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
     707             :   assert(From.getNode() != To.getNode() && "Potential legalization loop!");
     708             : 
     709             :   // If expansion produced new nodes, make sure they are properly marked.
     710      486914 :   ExpungeNode(From.getNode());
     711      486914 :   AnalyzeNewValue(To); // Expunges To.
     712             : 
     713             :   // Anything that used the old node should now use the new one.  Note that this
     714             :   // can potentially cause recursive merging.
     715      973828 :   SmallSetVector<SDNode*, 16> NodesToAnalyze;
     716      486914 :   NodeUpdateListener NUL(*this, NodesToAnalyze);
     717             :   do {
     718      486923 :     DAG.ReplaceAllUsesOfValueWith(From, To);
     719             : 
     720             :     // The old node may still be present in a map like ExpandedIntegers or
     721             :     // PromotedIntegers.  Inform maps about the replacement.
     722      973846 :     ReplacedValues[From] = To;
     723             : 
     724             :     // Process the list of nodes that need to be reanalyzed.
     725      976205 :     while (!NodesToAnalyze.empty()) {
     726      489282 :       SDNode *N = NodesToAnalyze.back();
     727      489282 :       NodesToAnalyze.pop_back();
     728      489282 :       if (N->getNodeId() != DAGTypeLegalizer::NewNode)
     729             :         // The node was analyzed while reanalyzing an earlier node - it is safe
     730             :         // to skip.  Note that this is not a morphing node - otherwise it would
     731             :         // still be marked NewNode.
     732        5919 :         continue;
     733             : 
     734             :       // Analyze the node's operands and recalculate the node ID.
     735      483363 :       SDNode *M = AnalyzeNewNode(N);
     736      483363 :       if (M != N) {
     737             :         // The node morphed into a different node.  Make everyone use the new
     738             :         // node instead.
     739             :         assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!");
     740             :         assert(N->getNumValues() == M->getNumValues() &&
     741             :                "Node morphing changed the number of results!");
     742         516 :         for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
     743         172 :           SDValue OldVal(N, i);
     744         172 :           SDValue NewVal(M, i);
     745         172 :           if (M->getNodeId() == Processed)
     746         172 :             RemapValue(NewVal);
     747         172 :           DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal);
     748             :           // OldVal may be a target of the ReplacedValues map which was marked
     749             :           // NewNode to force reanalysis because it was updated.  Ensure that
     750             :           // anything that ReplacedValues mapped to OldVal will now be mapped
     751             :           // all the way to NewVal.
     752         344 :           ReplacedValues[OldVal] = NewVal;
     753             :         }
     754             :         // The original node continues to exist in the DAG, marked NewNode.
     755             :       }
     756             :     }
     757             :     // When recursively update nodes with new nodes, it is possible to have
     758             :     // new uses of From due to CSE. If this happens, replace the new uses of
     759             :     // From with To.
     760      973846 :   } while (!From.use_empty());
     761      486914 : }
     762             : 
     763      157393 : void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) {
     764             :   assert(Result.getValueType() ==
     765             :          TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
     766             :          "Invalid type for promoted integer");
     767      157393 :   AnalyzeNewValue(Result);
     768             : 
     769      314786 :   SDValue &OpEntry = PromotedIntegers[Op];
     770             :   assert(!OpEntry.getNode() && "Node is already promoted!");
     771      157393 :   OpEntry = Result;
     772      157393 : }
     773             : 
     774        2790 : void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) {
     775             :   // f128 of x86_64 could be kept in SSE registers,
     776             :   // but sometimes softened to i128.
     777             :   assert((Result.getValueType() ==
     778             :           TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) ||
     779             :           Op.getValueType() ==
     780             :           TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) &&
     781             :          "Invalid type for softened float");
     782        2790 :   AnalyzeNewValue(Result);
     783             : 
     784        5580 :   SDValue &OpEntry = SoftenedFloats[Op];
     785             :   // Allow repeated calls to save f128 type nodes
     786             :   // or any node with type that transforms to itself.
     787             :   // Many operations on these types are not softened.
     788             :   assert((!OpEntry.getNode()||
     789             :           Op.getValueType() ==
     790             :           TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) &&
     791             :          "Node is already converted to integer!");
     792        2790 :   OpEntry = Result;
     793        2790 : }
     794             : 
     795        3608 : void DAGTypeLegalizer::SetPromotedFloat(SDValue Op, SDValue Result) {
     796             :   assert(Result.getValueType() ==
     797             :          TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
     798             :          "Invalid type for promoted float");
     799        3608 :   AnalyzeNewValue(Result);
     800             : 
     801        7216 :   SDValue &OpEntry = PromotedFloats[Op];
     802             :   assert(!OpEntry.getNode() && "Node is already promoted!");
     803        3608 :   OpEntry = Result;
     804        3608 : }
     805             : 
     806       52778 : void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) {
     807             :   // Note that in some cases vector operation operands may be greater than
     808             :   // the vector element type. For example BUILD_VECTOR of type <1 x i1> with
     809             :   // a constant i8 operand.
     810             :   assert(Result.getValueSizeInBits() >= Op.getScalarValueSizeInBits() &&
     811             :          "Invalid type for scalarized vector");
     812       52778 :   AnalyzeNewValue(Result);
     813             : 
     814      105556 :   SDValue &OpEntry = ScalarizedVectors[Op];
     815             :   assert(!OpEntry.getNode() && "Node is already scalarized!");
     816       52778 :   OpEntry = Result;
     817       52778 : }
     818             : 
     819      447137 : void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo,
     820             :                                           SDValue &Hi) {
     821      894274 :   std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
     822      447137 :   RemapValue(Entry.first);
     823      447137 :   RemapValue(Entry.second);
     824             :   assert(Entry.first.getNode() && "Operand isn't expanded");
     825      447137 :   Lo = Entry.first;
     826      447137 :   Hi = Entry.second;
     827      447137 : }
     828             : 
     829             : /// Transfer debug values by generating fragment expressions for split-up
     830             : /// values.
     831      652804 : static void transferDbgValues(SelectionDAG &DAG, SDValue From, SDValue To,
     832             :                               unsigned OffsetInBits) {
     833      652804 :   SDNode *FromNode = From.getNode();
     834      652804 :   SDNode *ToNode = To.getNode();
     835             :   assert(FromNode != ToNode);
     836             : 
     837     1305608 :   SmallVector<SDDbgValue *, 2> ClonedDVs;
     838     1958428 :   for (SDDbgValue *Dbg : DAG.GetDbgValues(FromNode)) {
     839          16 :     if (Dbg->getKind() != SDDbgValue::SDNODE)
     840             :       break;
     841             : 
     842          16 :     DIVariable *Var = Dbg->getVariable();
     843          16 :     auto *Fragment = DIExpression::createFragmentExpression(
     844          16 :         Dbg->getExpression(), OffsetInBits, To.getValueSizeInBits());
     845             :     SDDbgValue *Clone =
     846          32 :         DAG.getDbgValue(Var, Fragment, ToNode, To.getResNo(), Dbg->isIndirect(),
     847          48 :                         Dbg->getDebugLoc(), Dbg->getOrder());
     848          16 :     Dbg->setIsInvalidated();
     849          16 :     ClonedDVs.push_back(Clone);
     850             :   }
     851             : 
     852     1958428 :   for (SDDbgValue *Dbg : ClonedDVs)
     853          16 :     DAG.AddDbgValue(Dbg, ToNode, false);
     854      652804 : }
     855             : 
     856      326402 : void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo,
     857             :                                           SDValue Hi) {
     858             :   assert(Lo.getValueType() ==
     859             :          TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
     860             :          Hi.getValueType() == Lo.getValueType() &&
     861             :          "Invalid type for expanded integer");
     862             :   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
     863      326402 :   AnalyzeNewValue(Lo);
     864      326402 :   AnalyzeNewValue(Hi);
     865             : 
     866             :   // Transfer debug values.
     867      326402 :   transferDbgValues(DAG, Op, Lo, 0);
     868      326402 :   transferDbgValues(DAG, Op, Hi, Lo.getValueSizeInBits());
     869             : 
     870             :   // Remember that this is the result of the node.
     871      652804 :   std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
     872             :   assert(!Entry.first.getNode() && "Node already expanded");
     873      326402 :   Entry.first = Lo;
     874      326402 :   Entry.second = Hi;
     875      326402 : }
     876             : 
     877         271 : void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo,
     878             :                                         SDValue &Hi) {
     879         542 :   std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
     880         271 :   RemapValue(Entry.first);
     881         271 :   RemapValue(Entry.second);
     882             :   assert(Entry.first.getNode() && "Operand isn't expanded");
     883         271 :   Lo = Entry.first;
     884         271 :   Hi = Entry.second;
     885         271 : }
     886             : 
     887         246 : void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo,
     888             :                                         SDValue Hi) {
     889             :   assert(Lo.getValueType() ==
     890             :          TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
     891             :          Hi.getValueType() == Lo.getValueType() &&
     892             :          "Invalid type for expanded float");
     893             :   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
     894         246 :   AnalyzeNewValue(Lo);
     895         246 :   AnalyzeNewValue(Hi);
     896             : 
     897             :   // Remember that this is the result of the node.
     898         492 :   std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
     899             :   assert(!Entry.first.getNode() && "Node already expanded");
     900         246 :   Entry.first = Lo;
     901         246 :   Entry.second = Hi;
     902         246 : }
     903             : 
     904       89793 : void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo,
     905             :                                       SDValue &Hi) {
     906      179586 :   std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
     907       89793 :   RemapValue(Entry.first);
     908       89793 :   RemapValue(Entry.second);
     909             :   assert(Entry.first.getNode() && "Operand isn't split");
     910       89793 :   Lo = Entry.first;
     911       89793 :   Hi = Entry.second;
     912       89793 : }
     913             : 
     914       63581 : void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo,
     915             :                                       SDValue Hi) {
     916             :   assert(Lo.getValueType().getVectorElementType() ==
     917             :          Op.getValueType().getVectorElementType() &&
     918             :          2*Lo.getValueType().getVectorNumElements() ==
     919             :          Op.getValueType().getVectorNumElements() &&
     920             :          Hi.getValueType() == Lo.getValueType() &&
     921             :          "Invalid type for split vector");
     922             :   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
     923       63581 :   AnalyzeNewValue(Lo);
     924       63581 :   AnalyzeNewValue(Hi);
     925             : 
     926             :   // Remember that this is the result of the node.
     927      127162 :   std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
     928             :   assert(!Entry.first.getNode() && "Node already split");
     929       63581 :   Entry.first = Lo;
     930       63581 :   Entry.second = Hi;
     931       63581 : }
     932             : 
     933        5914 : void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) {
     934             :   assert(Result.getValueType() ==
     935             :          TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
     936             :          "Invalid type for widened vector");
     937        5914 :   AnalyzeNewValue(Result);
     938             : 
     939       11828 :   SDValue &OpEntry = WidenedVectors[Op];
     940             :   assert(!OpEntry.getNode() && "Node already widened!");
     941        5914 :   OpEntry = Result;
     942        5914 : }
     943             : 
     944             : 
     945             : //===----------------------------------------------------------------------===//
     946             : // Utilities.
     947             : //===----------------------------------------------------------------------===//
     948             : 
     949             : /// Convert to an integer of the same size.
     950       30825 : SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) {
     951       30825 :   unsigned BitWidth = Op.getValueSizeInBits();
     952       92475 :   return DAG.getNode(ISD::BITCAST, SDLoc(Op),
     953       92475 :                      EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op);
     954             : }
     955             : 
     956             : /// Convert to a vector of integers of the same size.
     957          32 : SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) {
     958             :   assert(Op.getValueType().isVector() && "Only applies to vectors!");
     959          32 :   unsigned EltWidth = Op.getScalarValueSizeInBits();
     960          32 :   EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth);
     961          64 :   auto EltCnt = Op.getValueType().getVectorElementCount();
     962          96 :   return DAG.getNode(ISD::BITCAST, SDLoc(Op),
     963          96 :                      EVT::getVectorVT(*DAG.getContext(), EltNVT, EltCnt), Op);
     964             : }
     965             : 
     966        3684 : SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op,
     967             :                                                EVT DestVT) {
     968        7368 :   SDLoc dl(Op);
     969             :   // Create the stack frame object.  Make sure it is aligned for both
     970             :   // the source and destination types.
     971        7368 :   SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT);
     972             :   // Emit a store to the stack slot.
     973             :   SDValue Store =
     974       14736 :       DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, MachinePointerInfo());
     975             :   // Result is a load from the stack slot.
     976       14736 :   return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo());
     977             : }
     978             : 
     979             : /// Replace the node's results with custom code provided by the target and
     980             : /// return "true", or do nothing and return "false".
     981             : /// The last parameter is FALSE if we are dealing with a node with legal
     982             : /// result types and illegal operand. The second parameter denotes the type of
     983             : /// illegal OperandNo in that case.
     984             : /// The last parameter being TRUE means we are dealing with a
     985             : /// node with illegal result types. The second parameter denotes the type of
     986             : /// illegal ResNo in that case.
     987      992124 : bool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) {
     988             :   // See if the target wants to custom lower this node.
     989     2875288 :   if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom)
     990             :     return false;
     991             : 
     992        4120 :   SmallVector<SDValue, 8> Results;
     993        4120 :   if (LegalizeResult)
     994        2343 :     TLI.ReplaceNodeResults(N, Results, DAG);
     995             :   else
     996        1777 :     TLI.LowerOperationWrapper(N, Results, DAG);
     997             : 
     998        4120 :   if (Results.empty())
     999             :     // The target didn't want to custom lower it after all.
    1000             :     return false;
    1001             : 
    1002             :   // When called from DAGTypeLegalizer::ExpandIntegerResult, we might need to
    1003             :   // provide the same kind of custom splitting behavior.
    1004        4910 :   if (Results.size() == N->getNumValues() + 1 && LegalizeResult) {
    1005             :     // We've legalized a return type by splitting it. If there is a chain,
    1006             :     // replace that too.
    1007         117 :     SetExpandedInteger(SDValue(N, 0), Results[0], Results[1]);
    1008          39 :     if (N->getNumValues() > 1)
    1009          22 :       ReplaceValueWith(SDValue(N, 1), Results[2]);
    1010             :     return true;
    1011             :   }
    1012             : 
    1013             :   // Make everything that once used N's values now use those in Results instead.
    1014             :   assert(Results.size() == N->getNumValues() &&
    1015             :          "Custom lowering returned the wrong number of results!");
    1016       13472 :   for (unsigned i = 0, e = Results.size(); i != e; ++i) {
    1017        9336 :     ReplaceValueWith(SDValue(N, i), Results[i]);
    1018             :   }
    1019             :   return true;
    1020             : }
    1021             : 
    1022             : 
    1023             : /// Widen the node's results with custom code provided by the target and return
    1024             : /// "true", or do nothing and return "false".
    1025        5914 : bool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) {
    1026             :   // See if the target wants to custom lower this node.
    1027       16021 :   if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom)
    1028             :     return false;
    1029             : 
    1030         260 :   SmallVector<SDValue, 8> Results;
    1031         260 :   TLI.ReplaceNodeResults(N, Results, DAG);
    1032             : 
    1033         260 :   if (Results.empty())
    1034             :     // The target didn't want to custom widen lower its result after all.
    1035             :     return false;
    1036             : 
    1037             :   // Update the widening map.
    1038             :   assert(Results.size() == N->getNumValues() &&
    1039             :          "Custom lowering returned the wrong number of results!");
    1040         237 :   for (unsigned i = 0, e = Results.size(); i != e; ++i)
    1041         237 :     SetWidenedVector(SDValue(N, i), Results[i]);
    1042             :   return true;
    1043             : }
    1044             : 
    1045          40 : SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) {
    1046         160 :   for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
    1047          80 :     if (i != ResNo)
    1048         120 :       ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i)));
    1049          80 :   return SDValue(N->getOperand(ResNo));
    1050             : }
    1051             : 
    1052             : /// Use ISD::EXTRACT_ELEMENT nodes to extract the low and high parts of the
    1053             : /// given value.
    1054        2783 : void DAGTypeLegalizer::GetPairElements(SDValue Pair,
    1055             :                                        SDValue &Lo, SDValue &Hi) {
    1056        5566 :   SDLoc dl(Pair);
    1057        8349 :   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType());
    1058        5566 :   Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
    1059        5566 :                    DAG.getIntPtrConstant(0, dl));
    1060        5566 :   Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair,
    1061        5566 :                    DAG.getIntPtrConstant(1, dl));
    1062        2783 : }
    1063             : 
    1064             : /// Build an integer with low bits Lo and high bits Hi.
    1065        5718 : SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) {
    1066             :   // Arbitrarily use dlHi for result SDLoc
    1067       11436 :   SDLoc dlHi(Hi);
    1068       11436 :   SDLoc dlLo(Lo);
    1069       11436 :   EVT LVT = Lo.getValueType();
    1070       11436 :   EVT HVT = Hi.getValueType();
    1071        5718 :   EVT NVT = EVT::getIntegerVT(*DAG.getContext(),
    1072       11436 :                               LVT.getSizeInBits() + HVT.getSizeInBits());
    1073             : 
    1074       11436 :   Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo);
    1075       11436 :   Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi);
    1076       11436 :   Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi,
    1077        5718 :                    DAG.getConstant(LVT.getSizeInBits(), dlHi,
    1078       34308 :                                    TLI.getPointerTy(DAG.getDataLayout())));
    1079       17154 :   return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi);
    1080             : }
    1081             : 
    1082             : /// Convert the node into a libcall with the same prototype.
    1083          26 : SDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N,
    1084             :                                      bool isSigned) {
    1085          52 :   unsigned NumOps = N->getNumOperands();
    1086          52 :   SDLoc dl(N);
    1087          26 :   if (NumOps == 0) {
    1088           0 :     return TLI.makeLibCall(DAG, LC, N->getValueType(0), None, isSigned,
    1089           0 :                            dl).first;
    1090          26 :   } else if (NumOps == 1) {
    1091           2 :     SDValue Op = N->getOperand(0);
    1092           3 :     return TLI.makeLibCall(DAG, LC, N->getValueType(0), Op, isSigned,
    1093           5 :                            dl).first;
    1094          25 :   } else if (NumOps == 2) {
    1095          75 :     SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
    1096          75 :     return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, isSigned,
    1097         125 :                            dl).first;
    1098             :   }
    1099           0 :   SmallVector<SDValue, 8> Ops(NumOps);
    1100           0 :   for (unsigned i = 0; i < NumOps; ++i)
    1101           0 :     Ops[i] = N->getOperand(i);
    1102             : 
    1103           0 :   return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, isSigned, dl).first;
    1104             : }
    1105             : 
    1106             : /// Expand a node into a call to a libcall. Similar to ExpandLibCall except that
    1107             : /// the first operand is the in-chain.
    1108             : std::pair<SDValue, SDValue>
    1109          41 : DAGTypeLegalizer::ExpandChainLibCall(RTLIB::Libcall LC, SDNode *Node,
    1110             :                                      bool isSigned) {
    1111          82 :   SDValue InChain = Node->getOperand(0);
    1112             : 
    1113          82 :   TargetLowering::ArgListTy Args;
    1114          41 :   TargetLowering::ArgListEntry Entry;
    1115         180 :   for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) {
    1116         294 :     EVT ArgVT = Node->getOperand(i).getValueType();
    1117          98 :     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
    1118         196 :     Entry.Node = Node->getOperand(i);
    1119          98 :     Entry.Ty = ArgTy;
    1120          98 :     Entry.IsSExt = isSigned;
    1121          98 :     Entry.IsZExt = !isSigned;
    1122          98 :     Args.push_back(Entry);
    1123             :   }
    1124          82 :   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
    1125         246 :                                          TLI.getPointerTy(DAG.getDataLayout()));
    1126             : 
    1127          82 :   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
    1128             : 
    1129          82 :   TargetLowering::CallLoweringInfo CLI(DAG);
    1130         123 :   CLI.setDebugLoc(SDLoc(Node))
    1131          41 :       .setChain(InChain)
    1132          41 :       .setLibCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee,
    1133         123 :                     std::move(Args))
    1134          82 :       .setSExtResult(isSigned)
    1135          82 :       .setZExtResult(!isSigned);
    1136             : 
    1137          41 :   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
    1138             : 
    1139          41 :   return CallInfo;
    1140             : }
    1141             : 
    1142             : /// Promote the given target boolean to a target boolean of the given type.
    1143             : /// A target boolean is an integer value, not necessarily of type i1, the bits
    1144             : /// of which conform to getBooleanContents.
    1145             : ///
    1146             : /// ValVT is the type of values that produced the boolean.
    1147       38371 : SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT ValVT) {
    1148       76742 :   SDLoc dl(Bool);
    1149       38371 :   EVT BoolVT = getSetCCResultType(ValVT);
    1150             :   ISD::NodeType ExtendCode =
    1151       76742 :       TargetLowering::getExtendForContent(TLI.getBooleanContents(ValVT));
    1152      115113 :   return DAG.getNode(ExtendCode, dl, BoolVT, Bool);
    1153             : }
    1154             : 
    1155             : /// Widen the given target boolean to a target boolean of the given type.
    1156             : /// The boolean vector is widened and then promoted to match the target boolean
    1157             : /// type of the given ValVT.
    1158          20 : SDValue DAGTypeLegalizer::WidenTargetBoolean(SDValue Bool, EVT ValVT,
    1159             :                                              bool WithZeroes) {
    1160          40 :   SDLoc dl(Bool);
    1161          40 :   EVT BoolVT = Bool.getValueType();
    1162             : 
    1163             :   assert(ValVT.getVectorNumElements() > BoolVT.getVectorNumElements() &&
    1164             :          TLI.isTypeLegal(ValVT) &&
    1165             :          "Unexpected types in WidenTargetBoolean");
    1166          20 :   EVT WideVT = EVT::getVectorVT(*DAG.getContext(), BoolVT.getScalarType(),
    1167          40 :                                 ValVT.getVectorNumElements());
    1168          20 :   Bool = ModifyToType(Bool, WideVT, WithZeroes);
    1169          40 :   return PromoteTargetBoolean(Bool, ValVT);
    1170             : }
    1171             : 
    1172             : /// Return the lower LoVT bits of Op in Lo and the upper HiVT bits in Hi.
    1173       35001 : void DAGTypeLegalizer::SplitInteger(SDValue Op,
    1174             :                                     EVT LoVT, EVT HiVT,
    1175             :                                     SDValue &Lo, SDValue &Hi) {
    1176       70002 :   SDLoc dl(Op);
    1177             :   assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() ==
    1178             :          Op.getValueSizeInBits() && "Invalid integer splitting!");
    1179       70002 :   Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op);
    1180       70002 :   Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op,
    1181       35001 :                    DAG.getConstant(LoVT.getSizeInBits(), dl,
    1182      210006 :                                    TLI.getPointerTy(DAG.getDataLayout())));
    1183       70002 :   Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi);
    1184       35001 : }
    1185             : 
    1186             : /// Return the lower and upper halves of Op's bits in a value type half the
    1187             : /// size of Op's.
    1188       21383 : void DAGTypeLegalizer::SplitInteger(SDValue Op,
    1189             :                                     SDValue &Lo, SDValue &Hi) {
    1190             :   EVT HalfVT =
    1191       21383 :       EVT::getIntegerVT(*DAG.getContext(), Op.getValueSizeInBits() / 2);
    1192       21383 :   SplitInteger(Op, HalfVT, HalfVT, Lo, Hi);
    1193       21383 : }
    1194             : 
    1195             : 
    1196             : //===----------------------------------------------------------------------===//
    1197             : //  Entry Point
    1198             : //===----------------------------------------------------------------------===//
    1199             : 
    1200             : /// This transforms the SelectionDAG into a SelectionDAG that only uses types
    1201             : /// natively supported by the target. Returns "true" if it made any changes.
    1202             : ///
    1203             : /// Note that this is an involved process that may invalidate pointers into
    1204             : /// the graph.
    1205      296481 : bool SelectionDAG::LegalizeTypes() {
    1206      296481 :   return DAGTypeLegalizer(*this).run();
    1207      216918 : }

Generated by: LCOV version 1.13