LegalizeTypes.h revision 7d0d8460646d1a06ff561775d40123a4cf65bf4d
1//===-- LegalizeTypes.h - Definition of the DAG Type Legalizer class ------===// 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 defines the DAGTypeLegalizer class. This is a private interface 11// shared between the code that implements the SelectionDAG::LegalizeTypes 12// method. 13// 14//===----------------------------------------------------------------------===// 15 16#ifndef SELECTIONDAG_LEGALIZETYPES_H 17#define SELECTIONDAG_LEGALIZETYPES_H 18 19#define DEBUG_TYPE "legalize-types" 20#include "llvm/CodeGen/SelectionDAG.h" 21#include "llvm/Target/TargetLowering.h" 22#include "llvm/ADT/DenseMap.h" 23#include "llvm/Support/Compiler.h" 24#include "llvm/Support/Debug.h" 25 26namespace llvm { 27 28//===----------------------------------------------------------------------===// 29/// DAGTypeLegalizer - This takes an arbitrary SelectionDAG as input and 30/// hacks on it until the target machine can handle it. This involves 31/// eliminating value sizes the machine cannot handle (promoting small sizes to 32/// large sizes or splitting up large values into small values) as well as 33/// eliminating operations the machine cannot handle. 34/// 35/// This code also does a small amount of optimization and recognition of idioms 36/// as part of its processing. For example, if a target does not support a 37/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this 38/// will attempt merge setcc and brc instructions into brcc's. 39/// 40class VISIBILITY_HIDDEN DAGTypeLegalizer { 41 TargetLowering &TLI; 42 SelectionDAG &DAG; 43public: 44 // NodeIDFlags - This pass uses the NodeID on the SDNodes to hold information 45 // about the state of the node. The enum has all the values. 46 enum NodeIDFlags { 47 /// ReadyToProcess - All operands have been processed, so this node is ready 48 /// to be handled. 49 ReadyToProcess = 0, 50 51 /// NewNode - This is a new node that was created in the process of 52 /// legalizing some other node. 53 NewNode = -1, 54 55 /// Processed - This is a node that has already been processed. 56 Processed = -2 57 58 // 1+ - This is a node which has this many unlegalized operands. 59 }; 60private: 61 enum LegalizeAction { 62 Legal, // The target natively supports this type. 63 Promote, // This type should be executed in a larger type. 64 Expand, // This type should be split into two types of half the size. 65 FloatToInt, // Convert a floating point type to an integer of the same size. 66 Scalarize, // Replace this one-element vector type with its element type. 67 Split // This vector type should be split into smaller vectors. 68 }; 69 70 /// ValueTypeActions - This is a bitvector that contains two bits for each 71 /// simple value type, where the two bits correspond to the LegalizeAction 72 /// enum from TargetLowering. This can be queried with "getTypeAction(VT)". 73 TargetLowering::ValueTypeActionImpl ValueTypeActions; 74 75 /// getTypeAction - Return how we should legalize values of this type, either 76 /// it is already legal, or we need to promote it to a larger integer type, or 77 /// we need to expand it into multiple registers of a smaller integer type, or 78 /// we need to scalarize a one-element vector type into the element type, or 79 /// we need to split a vector type into smaller vector types. 80 LegalizeAction getTypeAction(MVT VT) const { 81 switch (ValueTypeActions.getTypeAction(VT)) { 82 default: 83 assert(false && "Unknown legalize action!"); 84 case TargetLowering::Legal: 85 return Legal; 86 case TargetLowering::Promote: 87 return Promote; 88 case TargetLowering::Expand: 89 // Expand can mean 90 // 1) split scalar in half, 2) convert a float to an integer, 91 // 3) scalarize a single-element vector, 4) split a vector in two. 92 if (!VT.isVector()) { 93 if (VT.getSizeInBits() == TLI.getTypeToTransformTo(VT).getSizeInBits()) 94 return FloatToInt; 95 else 96 return Expand; 97 } else if (VT.getVectorNumElements() == 1) { 98 return Scalarize; 99 } else { 100 return Split; 101 } 102 } 103 } 104 105 /// isTypeLegal - Return true if this type is legal on this target. 106 bool isTypeLegal(MVT VT) const { 107 return ValueTypeActions.getTypeAction(VT) == TargetLowering::Legal; 108 } 109 110 /// PromotedNodes - For nodes that are below legal width, this map indicates 111 /// what promoted value to use. 112 DenseMap<SDOperand, SDOperand> PromotedNodes; 113 114 /// ExpandedNodes - For nodes that need to be expanded this map indicates 115 /// which operands are the expanded version of the input. 116 DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; 117 118 /// FloatToIntedNodes - For floating point nodes converted to integers of 119 /// the same size, this map indicates the converted value to use. 120 DenseMap<SDOperand, SDOperand> FloatToIntedNodes; 121 122 /// ScalarizedNodes - For nodes that are <1 x ty>, this map indicates the 123 /// scalar value of type 'ty' to use. 124 DenseMap<SDOperand, SDOperand> ScalarizedNodes; 125 126 /// SplitNodes - For nodes that need to be split this map indicates 127 /// which operands are the expanded version of the input. 128 DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > SplitNodes; 129 130 /// ReplacedNodes - For nodes that have been replaced with another, 131 /// indicates the replacement node to use. 132 DenseMap<SDOperand, SDOperand> ReplacedNodes; 133 134 /// Worklist - This defines a worklist of nodes to process. In order to be 135 /// pushed onto this worklist, all operands of a node must have already been 136 /// processed. 137 SmallVector<SDNode*, 128> Worklist; 138 139public: 140 explicit DAGTypeLegalizer(SelectionDAG &dag) 141 : TLI(dag.getTargetLoweringInfo()), DAG(dag), 142 ValueTypeActions(TLI.getValueTypeActions()) { 143 assert(MVT::LAST_VALUETYPE <= 32 && 144 "Too many value types for ValueTypeActions to hold!"); 145 } 146 147 void run(); 148 149 /// ReanalyzeNode - Recompute the NodeID and correct processed operands 150 /// for the specified node, adding it to the worklist if ready. 151 void ReanalyzeNode(SDNode *N) { 152 N->setNodeId(NewNode); 153 AnalyzeNewNode(N); 154 } 155 156 void NoteReplacement(SDOperand From, SDOperand To) { 157 ExpungeNode(From); 158 ExpungeNode(To); 159 ReplacedNodes[From] = To; 160 } 161 162private: 163 void AnalyzeNewNode(SDNode *&N); 164 165 void ReplaceValueWith(SDOperand From, SDOperand To); 166 void ReplaceNodeWith(SDNode *From, SDNode *To); 167 168 void RemapNode(SDOperand &N); 169 void ExpungeNode(SDOperand N); 170 171 // Common routines. 172 SDOperand CreateStackStoreLoad(SDOperand Op, MVT DestVT); 173 SDOperand MakeLibCall(RTLIB::Libcall LC, MVT RetVT, 174 const SDOperand *Ops, unsigned NumOps, bool isSigned); 175 176 SDOperand BitConvertToInteger(SDOperand Op); 177 SDOperand JoinIntegers(SDOperand Lo, SDOperand Hi); 178 void SplitInteger(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 179 void SplitInteger(SDOperand Op, MVT LoVT, MVT HiVT, 180 SDOperand &Lo, SDOperand &Hi); 181 182 SDOperand GetVectorElementPointer(SDOperand VecPtr, MVT EltVT, 183 SDOperand Index); 184 185 //===--------------------------------------------------------------------===// 186 // Promotion Support: LegalizeTypesPromote.cpp 187 //===--------------------------------------------------------------------===// 188 189 SDOperand GetPromotedOp(SDOperand Op) { 190 SDOperand &PromotedOp = PromotedNodes[Op]; 191 RemapNode(PromotedOp); 192 assert(PromotedOp.Val && "Operand wasn't promoted?"); 193 return PromotedOp; 194 } 195 void SetPromotedOp(SDOperand Op, SDOperand Result); 196 197 /// GetPromotedZExtOp - Get a promoted operand and zero extend it to the final 198 /// size. 199 SDOperand GetPromotedZExtOp(SDOperand Op) { 200 MVT OldVT = Op.getValueType(); 201 Op = GetPromotedOp(Op); 202 return DAG.getZeroExtendInReg(Op, OldVT); 203 } 204 205 // Result Promotion. 206 void PromoteResult(SDNode *N, unsigned ResNo); 207 SDOperand PromoteResult_BIT_CONVERT(SDNode *N); 208 SDOperand PromoteResult_BUILD_PAIR(SDNode *N); 209 SDOperand PromoteResult_Constant(SDNode *N); 210 SDOperand PromoteResult_CTLZ(SDNode *N); 211 SDOperand PromoteResult_CTPOP(SDNode *N); 212 SDOperand PromoteResult_CTTZ(SDNode *N); 213 SDOperand PromoteResult_EXTRACT_VECTOR_ELT(SDNode *N); 214 SDOperand PromoteResult_FP_ROUND(SDNode *N); 215 SDOperand PromoteResult_FP_TO_XINT(SDNode *N); 216 SDOperand PromoteResult_INT_EXTEND(SDNode *N); 217 SDOperand PromoteResult_LOAD(LoadSDNode *N); 218 SDOperand PromoteResult_SDIV(SDNode *N); 219 SDOperand PromoteResult_SELECT (SDNode *N); 220 SDOperand PromoteResult_SELECT_CC(SDNode *N); 221 SDOperand PromoteResult_SETCC(SDNode *N); 222 SDOperand PromoteResult_SHL(SDNode *N); 223 SDOperand PromoteResult_SimpleIntBinOp(SDNode *N); 224 SDOperand PromoteResult_SRA(SDNode *N); 225 SDOperand PromoteResult_SRL(SDNode *N); 226 SDOperand PromoteResult_TRUNCATE(SDNode *N); 227 SDOperand PromoteResult_UDIV(SDNode *N); 228 SDOperand PromoteResult_UNDEF(SDNode *N); 229 230 // Operand Promotion. 231 bool PromoteOperand(SDNode *N, unsigned OperandNo); 232 SDOperand PromoteOperand_ANY_EXTEND(SDNode *N); 233 SDOperand PromoteOperand_BUILD_PAIR(SDNode *N); 234 SDOperand PromoteOperand_BR_CC(SDNode *N, unsigned OpNo); 235 SDOperand PromoteOperand_BRCOND(SDNode *N, unsigned OpNo); 236 SDOperand PromoteOperand_BUILD_VECTOR(SDNode *N); 237 SDOperand PromoteOperand_FP_EXTEND(SDNode *N); 238 SDOperand PromoteOperand_FP_ROUND(SDNode *N); 239 SDOperand PromoteOperand_INT_TO_FP(SDNode *N); 240 SDOperand PromoteOperand_INSERT_VECTOR_ELT(SDNode *N, unsigned OpNo); 241 SDOperand PromoteOperand_MEMBARRIER(SDNode *N); 242 SDOperand PromoteOperand_RET(SDNode *N, unsigned OpNo); 243 SDOperand PromoteOperand_SELECT(SDNode *N, unsigned OpNo); 244 SDOperand PromoteOperand_SETCC(SDNode *N, unsigned OpNo); 245 SDOperand PromoteOperand_SIGN_EXTEND(SDNode *N); 246 SDOperand PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo); 247 SDOperand PromoteOperand_TRUNCATE(SDNode *N); 248 SDOperand PromoteOperand_ZERO_EXTEND(SDNode *N); 249 250 void PromoteSetCCOperands(SDOperand &LHS,SDOperand &RHS, ISD::CondCode Code); 251 252 //===--------------------------------------------------------------------===// 253 // Expansion Support: LegalizeTypesExpand.cpp 254 //===--------------------------------------------------------------------===// 255 256 void GetExpandedOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 257 void SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi); 258 259 // Result Expansion. 260 void ExpandResult(SDNode *N, unsigned ResNo); 261 void ExpandResult_ANY_EXTEND (SDNode *N, SDOperand &Lo, SDOperand &Hi); 262 void ExpandResult_AssertZext (SDNode *N, SDOperand &Lo, SDOperand &Hi); 263 void ExpandResult_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 264 void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi); 265 void ExpandResult_Constant (SDNode *N, SDOperand &Lo, SDOperand &Hi); 266 void ExpandResult_CTLZ (SDNode *N, SDOperand &Lo, SDOperand &Hi); 267 void ExpandResult_CTPOP (SDNode *N, SDOperand &Lo, SDOperand &Hi); 268 void ExpandResult_CTTZ (SDNode *N, SDOperand &Lo, SDOperand &Hi); 269 void ExpandResult_EXTRACT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 270 void ExpandResult_LOAD (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); 271 void ExpandResult_MERGE_VALUES(SDNode *N, SDOperand &Lo, SDOperand &Hi); 272 void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); 273 void ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi); 274 void ExpandResult_TRUNCATE (SDNode *N, SDOperand &Lo, SDOperand &Hi); 275 void ExpandResult_UNDEF (SDNode *N, SDOperand &Lo, SDOperand &Hi); 276 void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); 277 void ExpandResult_FP_TO_SINT (SDNode *N, SDOperand &Lo, SDOperand &Hi); 278 void ExpandResult_FP_TO_UINT (SDNode *N, SDOperand &Lo, SDOperand &Hi); 279 280 void ExpandResult_Logical (SDNode *N, SDOperand &Lo, SDOperand &Hi); 281 void ExpandResult_BSWAP (SDNode *N, SDOperand &Lo, SDOperand &Hi); 282 void ExpandResult_ADDSUB (SDNode *N, SDOperand &Lo, SDOperand &Hi); 283 void ExpandResult_ADDSUBC (SDNode *N, SDOperand &Lo, SDOperand &Hi); 284 void ExpandResult_ADDSUBE (SDNode *N, SDOperand &Lo, SDOperand &Hi); 285 void ExpandResult_SELECT (SDNode *N, SDOperand &Lo, SDOperand &Hi); 286 void ExpandResult_SELECT_CC (SDNode *N, SDOperand &Lo, SDOperand &Hi); 287 void ExpandResult_MUL (SDNode *N, SDOperand &Lo, SDOperand &Hi); 288 void ExpandResult_SDIV (SDNode *N, SDOperand &Lo, SDOperand &Hi); 289 void ExpandResult_SREM (SDNode *N, SDOperand &Lo, SDOperand &Hi); 290 void ExpandResult_UDIV (SDNode *N, SDOperand &Lo, SDOperand &Hi); 291 void ExpandResult_UREM (SDNode *N, SDOperand &Lo, SDOperand &Hi); 292 void ExpandResult_Shift (SDNode *N, SDOperand &Lo, SDOperand &Hi); 293 294 void ExpandShiftByConstant(SDNode *N, unsigned Amt, 295 SDOperand &Lo, SDOperand &Hi); 296 bool ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi); 297 298 // Operand Expansion. 299 bool ExpandOperand(SDNode *N, unsigned OperandNo); 300 SDOperand ExpandOperand_BIT_CONVERT(SDNode *N); 301 SDOperand ExpandOperand_BR_CC(SDNode *N); 302 SDOperand ExpandOperand_BUILD_VECTOR(SDNode *N); 303 SDOperand ExpandOperand_EXTRACT_ELEMENT(SDNode *N); 304 SDOperand ExpandOperand_SETCC(SDNode *N); 305 SDOperand ExpandOperand_SINT_TO_FP(SDOperand Source, MVT DestTy); 306 SDOperand ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo); 307 SDOperand ExpandOperand_TRUNCATE(SDNode *N); 308 SDOperand ExpandOperand_UINT_TO_FP(SDOperand Source, MVT DestTy); 309 310 void ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS, 311 ISD::CondCode &CCCode); 312 313 //===--------------------------------------------------------------------===// 314 // Float to Integer Conversion Support: LegalizeTypesFloatToInt.cpp 315 //===--------------------------------------------------------------------===// 316 317 SDOperand GetIntegerOp(SDOperand Op) { 318 SDOperand &IntegerOp = FloatToIntedNodes[Op]; 319 RemapNode(IntegerOp); 320 assert(IntegerOp.Val && "Operand wasn't converted to integer?"); 321 return IntegerOp; 322 } 323 void SetIntegerOp(SDOperand Op, SDOperand Result); 324 325 // Result Float to Integer Conversion. 326 void FloatToIntResult(SDNode *N, unsigned OpNo); 327 SDOperand FloatToIntRes_BIT_CONVERT(SDNode *N); 328 SDOperand FloatToIntRes_BUILD_PAIR(SDNode *N); 329 SDOperand FloatToIntRes_ConstantFP(ConstantFPSDNode *N); 330 SDOperand FloatToIntRes_FADD(SDNode *N); 331 SDOperand FloatToIntRes_FCOPYSIGN(SDNode *N); 332 SDOperand FloatToIntRes_FMUL(SDNode *N); 333 SDOperand FloatToIntRes_FSUB(SDNode *N); 334 SDOperand FloatToIntRes_LOAD(SDNode *N); 335 SDOperand FloatToIntRes_XINT_TO_FP(SDNode *N); 336 337 // Operand Float to Integer Conversion. 338 bool FloatToIntOperand(SDNode *N, unsigned OpNo); 339 SDOperand FloatToIntOp_BIT_CONVERT(SDNode *N); 340 341 //===--------------------------------------------------------------------===// 342 // Scalarization Support: LegalizeTypesScalarize.cpp 343 //===--------------------------------------------------------------------===// 344 345 SDOperand GetScalarizedOp(SDOperand Op) { 346 SDOperand &ScalarOp = ScalarizedNodes[Op]; 347 RemapNode(ScalarOp); 348 assert(ScalarOp.Val && "Operand wasn't scalarized?"); 349 return ScalarOp; 350 } 351 void SetScalarizedOp(SDOperand Op, SDOperand Result); 352 353 // Result Vector Scalarization: <1 x ty> -> ty. 354 void ScalarizeResult(SDNode *N, unsigned OpNo); 355 SDOperand ScalarizeRes_BinOp(SDNode *N); 356 SDOperand ScalarizeRes_UnaryOp(SDNode *N); 357 358 SDOperand ScalarizeRes_BIT_CONVERT(SDNode *N); 359 SDOperand ScalarizeRes_FPOWI(SDNode *N); 360 SDOperand ScalarizeRes_INSERT_VECTOR_ELT(SDNode *N); 361 SDOperand ScalarizeRes_LOAD(LoadSDNode *N); 362 SDOperand ScalarizeRes_SELECT(SDNode *N); 363 SDOperand ScalarizeRes_UNDEF(SDNode *N); 364 SDOperand ScalarizeRes_VECTOR_SHUFFLE(SDNode *N); 365 366 // Operand Vector Scalarization: <1 x ty> -> ty. 367 bool ScalarizeOperand(SDNode *N, unsigned OpNo); 368 SDOperand ScalarizeOp_BIT_CONVERT(SDNode *N); 369 SDOperand ScalarizeOp_EXTRACT_VECTOR_ELT(SDNode *N); 370 SDOperand ScalarizeOp_STORE(StoreSDNode *N, unsigned OpNo); 371 372 //===--------------------------------------------------------------------===// 373 // Vector Splitting Support: LegalizeTypesSplit.cpp 374 //===--------------------------------------------------------------------===// 375 376 void GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 377 void SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi); 378 379 // Result Vector Splitting: <128 x ty> -> 2 x <64 x ty>. 380 void SplitResult(SDNode *N, unsigned OpNo); 381 382 void SplitRes_UNDEF(SDNode *N, SDOperand &Lo, SDOperand &Hi); 383 void SplitRes_LOAD(LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); 384 void SplitRes_BUILD_PAIR(SDNode *N, SDOperand &Lo, SDOperand &Hi); 385 void SplitRes_INSERT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 386 void SplitRes_VECTOR_SHUFFLE(SDNode *N, SDOperand &Lo, SDOperand &Hi); 387 388 void SplitRes_BUILD_VECTOR(SDNode *N, SDOperand &Lo, SDOperand &Hi); 389 void SplitRes_CONCAT_VECTORS(SDNode *N, SDOperand &Lo, SDOperand &Hi); 390 void SplitRes_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 391 void SplitRes_UnOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); 392 void SplitRes_BinOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); 393 void SplitRes_FPOWI(SDNode *N, SDOperand &Lo, SDOperand &Hi); 394 void SplitRes_SELECT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 395 396 // Operand Vector Splitting: <128 x ty> -> 2 x <64 x ty>. 397 bool SplitOperand(SDNode *N, unsigned OpNo); 398 399 SDOperand SplitOp_BIT_CONVERT(SDNode *N); 400 SDOperand SplitOp_EXTRACT_SUBVECTOR(SDNode *N); 401 SDOperand SplitOp_EXTRACT_VECTOR_ELT(SDNode *N); 402 SDOperand SplitOp_RET(SDNode *N, unsigned OpNo); 403 SDOperand SplitOp_STORE(StoreSDNode *N, unsigned OpNo); 404 SDOperand SplitOp_VECTOR_SHUFFLE(SDNode *N, unsigned OpNo); 405}; 406 407} // end namespace llvm. 408 409#endif 410