include/llvm/CodeGen/DAGISelHeader.h

   1 //==-llvm/CodeGen/DAGISelHeader.h - Common DAG ISel definitions  -*- C++ -*-==//
   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 provides definitions of the common, target-independent methods and
  11 // data, which is used by SelectionDAG-based instruction selectors.
  12 //
  13 // *** NOTE: This file is #included into the middle of the target
  14 // instruction selector class.  These functions are really methods.
  15 // This is a little awkward, but it allows this code to be shared
  16 // by all the targets while still being able to call into
  17 // target-specific code without using a virtual function call.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
  22 #define LLVM_CODEGEN_DAGISEL_HEADER_H
  23
  24 /// ISelPosition - Node iterator marking the current position of
  25 /// instruction selection as it procedes through the topologically-sorted
  26 /// node list.
  27 SelectionDAG::allnodes_iterator ISelPosition;
  28
  29 /// IsChainCompatible - Returns true if Chain is Op or Chain does
  30 /// not reach Op.
  31 static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
  32   if (Chain->getOpcode() == ISD::EntryToken)
  33     return true;
  34   if (Chain->getOpcode() == ISD::TokenFactor)
  35     return false;
  36   if (Chain->getNumOperands() > 0) {
  37     SDValue C0 = Chain->getOperand(0);
  38     if (C0.getValueType() == MVT::Other)
  39       return C0.getNode() != Op && IsChainCompatible(C0.getNode(), Op);
  40   }
  41   return true;
  42 }
  43
  44 /// ISelUpdater - helper class to handle updates of the
  45 /// instruciton selection graph.
  46 class VISIBILITY_HIDDEN ISelUpdater : public SelectionDAG::DAGUpdateListener {
  47   SelectionDAG::allnodes_iterator &ISelPosition;
  48 public:
  49   explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
  50     : ISelPosition(isp) {}
  51
  52   /// NodeDeleted - Handle nodes deleted from the graph. If the
  53   /// node being deleted is the current ISelPosition node, update
  54   /// ISelPosition.
  55   ///
  56   virtual void NodeDeleted(SDNode *N, SDNode *E) {
  57     if (ISelPosition == SelectionDAG::allnodes_iterator(N))
  58       ++ISelPosition;
  59   }
  60
  61   /// NodeUpdated - Ignore updates for now.
  62   virtual void NodeUpdated(SDNode *N) {}
  63 };
  64
  65 /// ReplaceUses - replace all uses of the old node F with the use
  66 /// of the new node T.
  67 DISABLE_INLINE void ReplaceUses(SDValue F, SDValue T) {
  68   ISelUpdater ISU(ISelPosition);
  69   CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
  70 }
  71
  72 /// ReplaceUses - replace all uses of the old nodes F with the use
  73 /// of the new nodes T.
  74 DISABLE_INLINE void ReplaceUses(const SDValue *F, const SDValue *T,
  75                                 unsigned Num) {
  76   ISelUpdater ISU(ISelPosition);
  77   CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
  78 }
  79
  80 /// ReplaceUses - replace all uses of the old node F with the use
  81 /// of the new node T.
  82 DISABLE_INLINE void ReplaceUses(SDNode *F, SDNode *T) {
  83   ISelUpdater ISU(ISelPosition);
  84   CurDAG->ReplaceAllUsesWith(F, T, &ISU);
  85 }
  86
  87 /// SelectRoot - Top level entry to DAG instruction selector.
  88 /// Selects instructions starting at the root of the current DAG.
  89 void SelectRoot(SelectionDAG &DAG) {
  90   SelectRootInit();
  91
  92   // Create a dummy node (which is not added to allnodes), that adds
  93   // a reference to the root node, preventing it from being deleted,
  94   // and tracking any changes of the root.
  95   HandleSDNode Dummy(CurDAG->getRoot());
  96   ISelPosition = llvm::next(SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode()));
  97
  98   // The AllNodes list is now topological-sorted. Visit the
  99   // nodes by starting at the end of the list (the root of the
 100   // graph) and preceding back toward the beginning (the entry
 101   // node).
 102   while (ISelPosition != CurDAG->allnodes_begin()) {
 103     SDNode *Node = --ISelPosition;
 104     // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
 105     // but there are currently some corner cases that it misses. Also, this
 106     // makes it theoretically possible to disable the DAGCombiner.
 107     if (Node->use_empty())
 108       continue;
 109 #if 0
 110     DAG.setSubgraphColor(Node, "red");
 111 #endif
 112     SDNode *ResNode = Select(Node);
 113     // If node should not be replaced, continue with the next one.
 114     if (ResNode == Node)
 115       continue;
 116     // Replace node.
 117     if (ResNode) {
 118 #if 0
 119       DAG.setSubgraphColor(ResNode, "yellow");
 120       DAG.setSubgraphColor(ResNode, "black");
 121 #endif
 122       ReplaceUses(Node, ResNode);
 123     }
 124     // If after the replacement this node is not used any more,
 125     // remove this dead node.
 126     if (Node->use_empty()) { // Don't delete EntryToken, etc.
 127       ISelUpdater ISU(ISelPosition);
 128       CurDAG->RemoveDeadNode(Node, &ISU);
 129     }
 130   }
 131
 132   CurDAG->setRoot(Dummy.getValue());
 133 }
 134
 135
 136 /// CheckInteger - Return true if the specified node is not a ConstantSDNode or
 137 /// if it doesn't have the specified value.
 138 static bool CheckInteger(SDValue V, int64_t Val) {
 139   ConstantSDNode *C = dyn_cast<ConstantSDNode>(V);
 140   return C == 0 || C->getSExtValue() != Val;
 141 }
 142
 143 /// CheckAndImmediate - Check to see if the specified node is an and with an
 144 /// immediate returning true on failure.
 145 ///
 146 /// FIXME: Inline this gunk into CheckAndMask.
 147 bool CheckAndImmediate(SDValue V, int64_t Val) {
 148   if (V->getOpcode() == ISD::AND)
 149     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
 150       if (CheckAndMask(V.getOperand(0), C, Val))
 151         return false;
 152   return true;
 153 }
 154
 155 /// CheckOrImmediate - Check to see if the specified node is an or with an
 156 /// immediate returning true on failure.
 157 ///
 158 /// FIXME: Inline this gunk into CheckOrMask.
 159 bool CheckOrImmediate(SDValue V, int64_t Val) {
 160   if (V->getOpcode() == ISD::OR)
 161     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(V->getOperand(1)))
 162       if (CheckOrMask(V.getOperand(0), C, Val))
 163         return false;
 164   return true;
 165 }
 166
 167 // These functions are marked always inline so that Idx doesn't get pinned to
 168 // the stack.
 169 ALWAYS_INLINE static int8_t
 170 GetInt1(const unsigned char *MatcherTable, unsigned &Idx) {
 171   return MatcherTable[Idx++];
 172 }
 173
 174 ALWAYS_INLINE static int16_t
 175 GetInt2(const unsigned char *MatcherTable, unsigned &Idx) {
 176   int16_t Val = GetInt1(MatcherTable, Idx);
 177   Val |= int16_t(GetInt1(MatcherTable, Idx)) << 8;
 178   return Val;
 179 }
 180
 181 ALWAYS_INLINE static int32_t
 182 GetInt4(const unsigned char *MatcherTable, unsigned &Idx) {
 183   int32_t Val = GetInt2(MatcherTable, Idx);
 184   Val |= int32_t(GetInt2(MatcherTable, Idx)) << 16;
 185   return Val;
 186 }
 187
 188 ALWAYS_INLINE static int64_t
 189 GetInt8(const unsigned char *MatcherTable, unsigned &Idx) {
 190   int64_t Val = GetInt4(MatcherTable, Idx);
 191   Val |= int64_t(GetInt4(MatcherTable, Idx)) << 32;
 192   return Val;
 193 }
 194
 195 enum BuiltinOpcodes {
 196   OPC_Emit,
 197   OPC_Push,
 198   OPC_Record,
 199   OPC_MoveChild,
 200   OPC_MoveParent,
 201   OPC_CheckSame,
 202   OPC_CheckPatternPredicate,
 203   OPC_CheckPredicate,
 204   OPC_CheckOpcode,
 205   OPC_CheckType,
 206   OPC_CheckInteger1, OPC_CheckInteger2, OPC_CheckInteger4, OPC_CheckInteger8,
 207   OPC_CheckCondCode,
 208   OPC_CheckValueType,
 209   OPC_CheckComplexPat,
 210   OPC_CheckAndImm1, OPC_CheckAndImm2, OPC_CheckAndImm4, OPC_CheckAndImm8,
 211   OPC_CheckOrImm1, OPC_CheckOrImm2, OPC_CheckOrImm4, OPC_CheckOrImm8,
 212   OPC_IsProfitableToFold,
 213   OPC_IsLegalToFold
 214 };
 215
 216 struct MatchScope {
 217   /// FailIndex - If this match fails, this is the index to continue with.
 218   unsigned FailIndex;
 219
 220   /// NodeStackSize - The size of the node stack when the scope was formed.
 221   unsigned NodeStackSize;
 222
 223   /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
 224   unsigned NumRecordedNodes;
 225 };
 226
 227 SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
 228                          unsigned TableSize) {
 229   switch (NodeToMatch->getOpcode()) {
 230   default:
 231     break;
 232   case ISD::EntryToken:       // These nodes remain the same.
 233   case ISD::BasicBlock:
 234   case ISD::Register:
 235   case ISD::HANDLENODE:
 236   case ISD::TargetConstant:
 237   case ISD::TargetConstantFP:
 238   case ISD::TargetConstantPool:
 239   case ISD::TargetFrameIndex:
 240   case ISD::TargetExternalSymbol:
 241   case ISD::TargetBlockAddress:
 242   case ISD::TargetJumpTable:
 243   case ISD::TargetGlobalTLSAddress:
 244   case ISD::TargetGlobalAddress:
 245   case ISD::TokenFactor:
 246   case ISD::CopyFromReg:
 247   case ISD::CopyToReg:
 248     return 0;
 249   case ISD::AssertSext:
 250   case ISD::AssertZext:
 251     ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
 252     return 0;
 253   case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
 254   case ISD::EH_LABEL:  return Select_EH_LABEL(NodeToMatch);
 255   case ISD::UNDEF:     return Select_UNDEF(NodeToMatch);
 256   }
 257
 258   assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
 259
 260   SmallVector<MatchScope, 8> MatchScopes;
 261
 262   // RecordedNodes - This is the set of nodes that have been recorded by the
 263   // state machine.
 264   SmallVector<SDValue, 8> RecordedNodes;
 265
 266   // Set up the node stack with NodeToMatch as the only node on the stack.
 267   SmallVector<SDValue, 8> NodeStack;
 268   SDValue N = SDValue(NodeToMatch, 0);
 269   NodeStack.push_back(N);
 270
 271   // Interpreter starts at opcode #0.
 272   unsigned MatcherIndex = 0;
 273   while (1) {
 274     assert(MatcherIndex < TableSize && "Invalid index");
 275     switch ((BuiltinOpcodes)MatcherTable[MatcherIndex++]) {
 276     case OPC_Emit: {
 277       errs() << "EMIT NODE\n";
 278       return 0;
 279     }
 280     case OPC_Push: {
 281       unsigned NumToSkip = MatcherTable[MatcherIndex++];
 282       MatchScope NewEntry;
 283       NewEntry.FailIndex = MatcherIndex+NumToSkip;
 284       NewEntry.NodeStackSize = NodeStack.size();
 285       NewEntry.NumRecordedNodes = RecordedNodes.size();
 286       MatchScopes.push_back(NewEntry);
 287       continue;
 288     }
 289     case OPC_Record:
 290       // Remember this node, it may end up being an operand in the pattern.
 291       RecordedNodes.push_back(N);
 292       continue;
 293
 294     case OPC_MoveChild: {
 295       unsigned Child = MatcherTable[MatcherIndex++];
 296       if (Child >= N.getNumOperands())
 297         break;  // Match fails if out of range child #.
 298       N = N.getOperand(Child);
 299       NodeStack.push_back(N);
 300       continue;
 301     }
 302
 303     case OPC_MoveParent:
 304       // Pop the current node off the NodeStack.
 305       NodeStack.pop_back();
 306       assert(!NodeStack.empty() && "Node stack imbalance!");
 307       N = NodeStack.back();
 308       continue;
 309
 310     case OPC_CheckSame: {
 311       // Accept if it is exactly the same as a previously recorded node.
 312       unsigned RecNo = MatcherTable[MatcherIndex++];
 313       assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
 314       if (N != RecordedNodes[RecNo]) break;
 315       continue;
 316     }
 317     case OPC_CheckPatternPredicate:
 318       if (!CheckPatternPredicate(MatcherTable[MatcherIndex++])) break;
 319       continue;
 320     case OPC_CheckPredicate:
 321       if (!CheckNodePredicate(N.getNode(), MatcherTable[MatcherIndex++])) break;
 322       continue;
 323     case OPC_CheckComplexPat: {
 324       unsigned PatNo = MatcherTable[MatcherIndex++];
 325       (void)PatNo;
 326       // FIXME: CHECK IT.
 327       continue;
 328     }
 329
 330     case OPC_CheckOpcode:
 331       if (N->getOpcode() != MatcherTable[MatcherIndex++]) break;
 332       continue;
 333     case OPC_CheckType:
 334       if (N.getValueType() !=
 335           (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
 336       continue;
 337     case OPC_CheckCondCode:
 338       if (cast<CondCodeSDNode>(N)->get() !=
 339           (ISD::CondCode)MatcherTable[MatcherIndex++]) break;
 340       continue;
 341     case OPC_CheckValueType:
 342       if (cast<VTSDNode>(N)->getVT() !=
 343           (MVT::SimpleValueType)MatcherTable[MatcherIndex++]) break;
 344       continue;
 345
 346     case OPC_CheckInteger1:
 347       if (CheckInteger(N, GetInt1(MatcherTable, MatcherIndex))) break;
 348       continue;
 349     case OPC_CheckInteger2:
 350       if (CheckInteger(N, GetInt2(MatcherTable, MatcherIndex))) break;
 351       continue;
 352     case OPC_CheckInteger4:
 353       if (CheckInteger(N, GetInt4(MatcherTable, MatcherIndex))) break;
 354       continue;
 355     case OPC_CheckInteger8:
 356       if (CheckInteger(N, GetInt8(MatcherTable, MatcherIndex))) break;
 357       continue;
 358
 359     case OPC_CheckAndImm1:
 360       if (CheckAndImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
 361       continue;
 362     case OPC_CheckAndImm2:
 363       if (CheckAndImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
 364       continue;
 365     case OPC_CheckAndImm4:
 366       if (CheckAndImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
 367       continue;
 368     case OPC_CheckAndImm8:
 369       if (CheckAndImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
 370       continue;
 371
 372     case OPC_CheckOrImm1:
 373       if (CheckOrImmediate(N, GetInt1(MatcherTable, MatcherIndex))) break;
 374       continue;
 375     case OPC_CheckOrImm2:
 376       if (CheckOrImmediate(N, GetInt2(MatcherTable, MatcherIndex))) break;
 377       continue;
 378     case OPC_CheckOrImm4:
 379       if (CheckOrImmediate(N, GetInt4(MatcherTable, MatcherIndex))) break;
 380       continue;
 381     case OPC_CheckOrImm8:
 382       if (CheckOrImmediate(N, GetInt8(MatcherTable, MatcherIndex))) break;
 383       continue;
 384
 385     case OPC_IsProfitableToFold:
 386       assert(!NodeStack.size() == 1 && "No parent node");
 387       if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
 388                               NodeToMatch))
 389         break;
 390       continue;
 391     case OPC_IsLegalToFold:
 392       assert(!NodeStack.size() == 1 && "No parent node");
 393       if (!IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
 394                          NodeToMatch))
 395         break;
 396       continue;
 397     }
 398
 399     // If the code reached this point, then the match failed pop out to the next
 400     // match scope.
 401     if (MatchScopes.empty()) {
 402       CannotYetSelect(NodeToMatch);
 403       return 0;
 404     }
 405
 406     RecordedNodes.resize(MatchScopes.back().NumRecordedNodes);
 407     NodeStack.resize(MatchScopes.back().NodeStackSize);
 408     MatcherIndex = MatchScopes.back().FailIndex;
 409     MatchScopes.pop_back();
 410   }
 411 }
 412
 413
 414 #endif /* LLVM_CODEGEN_DAGISEL_HEADER_H */