LegalizeTypes.h revision edfcf598faab9ce294712551ecf67093acd1c66e
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 BitConvertToInteger(SDOperand Op); 173 SDOperand CreateStackStoreLoad(SDOperand Op, MVT DestVT); 174 SDOperand JoinIntegers(SDOperand Lo, SDOperand Hi); 175 void SplitInteger(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 176 void SplitInteger(SDOperand Op, MVT LoVT, MVT HiVT, 177 SDOperand &Lo, SDOperand &Hi); 178 SDOperand MakeLibCall(RTLIB::Libcall LC, MVT RetVT, 179 const SDOperand *Ops, unsigned NumOps, bool isSigned); 180 181 //===--------------------------------------------------------------------===// 182 // Promotion Support: LegalizeTypesPromote.cpp 183 //===--------------------------------------------------------------------===// 184 185 SDOperand GetPromotedOp(SDOperand Op) { 186 SDOperand &PromotedOp = PromotedNodes[Op]; 187 RemapNode(PromotedOp); 188 assert(PromotedOp.Val && "Operand wasn't promoted?"); 189 return PromotedOp; 190 } 191 void SetPromotedOp(SDOperand Op, SDOperand Result); 192 193 /// GetPromotedZExtOp - Get a promoted operand and zero extend it to the final 194 /// size. 195 SDOperand GetPromotedZExtOp(SDOperand Op) { 196 MVT OldVT = Op.getValueType(); 197 Op = GetPromotedOp(Op); 198 return DAG.getZeroExtendInReg(Op, OldVT); 199 } 200 201 // Result Promotion. 202 void PromoteResult(SDNode *N, unsigned ResNo); 203 SDOperand PromoteResult_BIT_CONVERT(SDNode *N); 204 SDOperand PromoteResult_BUILD_PAIR(SDNode *N); 205 SDOperand PromoteResult_Constant(SDNode *N); 206 SDOperand PromoteResult_CTLZ(SDNode *N); 207 SDOperand PromoteResult_CTPOP(SDNode *N); 208 SDOperand PromoteResult_CTTZ(SDNode *N); 209 SDOperand PromoteResult_EXTRACT_VECTOR_ELT(SDNode *N); 210 SDOperand PromoteResult_FP_ROUND(SDNode *N); 211 SDOperand PromoteResult_FP_TO_XINT(SDNode *N); 212 SDOperand PromoteResult_INT_EXTEND(SDNode *N); 213 SDOperand PromoteResult_LOAD(LoadSDNode *N); 214 SDOperand PromoteResult_SDIV(SDNode *N); 215 SDOperand PromoteResult_SELECT (SDNode *N); 216 SDOperand PromoteResult_SELECT_CC(SDNode *N); 217 SDOperand PromoteResult_SETCC(SDNode *N); 218 SDOperand PromoteResult_SHL(SDNode *N); 219 SDOperand PromoteResult_SimpleIntBinOp(SDNode *N); 220 SDOperand PromoteResult_SRA(SDNode *N); 221 SDOperand PromoteResult_SRL(SDNode *N); 222 SDOperand PromoteResult_TRUNCATE(SDNode *N); 223 SDOperand PromoteResult_UDIV(SDNode *N); 224 SDOperand PromoteResult_UNDEF(SDNode *N); 225 226 // Operand Promotion. 227 bool PromoteOperand(SDNode *N, unsigned OperandNo); 228 SDOperand PromoteOperand_ANY_EXTEND(SDNode *N); 229 SDOperand PromoteOperand_BUILD_PAIR(SDNode *N); 230 SDOperand PromoteOperand_BR_CC(SDNode *N, unsigned OpNo); 231 SDOperand PromoteOperand_BRCOND(SDNode *N, unsigned OpNo); 232 SDOperand PromoteOperand_BUILD_VECTOR(SDNode *N); 233 SDOperand PromoteOperand_FP_EXTEND(SDNode *N); 234 SDOperand PromoteOperand_FP_ROUND(SDNode *N); 235 SDOperand PromoteOperand_INT_TO_FP(SDNode *N); 236 SDOperand PromoteOperand_INSERT_VECTOR_ELT(SDNode *N, unsigned OpNo); 237 SDOperand PromoteOperand_MEMBARRIER(SDNode *N); 238 SDOperand PromoteOperand_RET(SDNode *N, unsigned OpNo); 239 SDOperand PromoteOperand_SELECT(SDNode *N, unsigned OpNo); 240 SDOperand PromoteOperand_SETCC(SDNode *N, unsigned OpNo); 241 SDOperand PromoteOperand_SIGN_EXTEND(SDNode *N); 242 SDOperand PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo); 243 SDOperand PromoteOperand_TRUNCATE(SDNode *N); 244 SDOperand PromoteOperand_ZERO_EXTEND(SDNode *N); 245 246 void PromoteSetCCOperands(SDOperand &LHS,SDOperand &RHS, ISD::CondCode Code); 247 248 //===--------------------------------------------------------------------===// 249 // Expansion Support: LegalizeTypesExpand.cpp 250 //===--------------------------------------------------------------------===// 251 252 void GetExpandedOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 253 void SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi); 254 255 // Result Expansion. 256 void ExpandResult(SDNode *N, unsigned ResNo); 257 void ExpandResult_ANY_EXTEND (SDNode *N, SDOperand &Lo, SDOperand &Hi); 258 void ExpandResult_AssertZext (SDNode *N, SDOperand &Lo, SDOperand &Hi); 259 void ExpandResult_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 260 void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi); 261 void ExpandResult_Constant (SDNode *N, SDOperand &Lo, SDOperand &Hi); 262 void ExpandResult_CTLZ (SDNode *N, SDOperand &Lo, SDOperand &Hi); 263 void ExpandResult_CTPOP (SDNode *N, SDOperand &Lo, SDOperand &Hi); 264 void ExpandResult_CTTZ (SDNode *N, SDOperand &Lo, SDOperand &Hi); 265 void ExpandResult_EXTRACT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 266 void ExpandResult_LOAD (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); 267 void ExpandResult_MERGE_VALUES(SDNode *N, SDOperand &Lo, SDOperand &Hi); 268 void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); 269 void ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi); 270 void ExpandResult_TRUNCATE (SDNode *N, SDOperand &Lo, SDOperand &Hi); 271 void ExpandResult_UNDEF (SDNode *N, SDOperand &Lo, SDOperand &Hi); 272 void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); 273 void ExpandResult_FP_TO_SINT (SDNode *N, SDOperand &Lo, SDOperand &Hi); 274 void ExpandResult_FP_TO_UINT (SDNode *N, SDOperand &Lo, SDOperand &Hi); 275 276 void ExpandResult_Logical (SDNode *N, SDOperand &Lo, SDOperand &Hi); 277 void ExpandResult_BSWAP (SDNode *N, SDOperand &Lo, SDOperand &Hi); 278 void ExpandResult_ADDSUB (SDNode *N, SDOperand &Lo, SDOperand &Hi); 279 void ExpandResult_ADDSUBC (SDNode *N, SDOperand &Lo, SDOperand &Hi); 280 void ExpandResult_ADDSUBE (SDNode *N, SDOperand &Lo, SDOperand &Hi); 281 void ExpandResult_SELECT (SDNode *N, SDOperand &Lo, SDOperand &Hi); 282 void ExpandResult_SELECT_CC (SDNode *N, SDOperand &Lo, SDOperand &Hi); 283 void ExpandResult_MUL (SDNode *N, SDOperand &Lo, SDOperand &Hi); 284 void ExpandResult_SDIV (SDNode *N, SDOperand &Lo, SDOperand &Hi); 285 void ExpandResult_SREM (SDNode *N, SDOperand &Lo, SDOperand &Hi); 286 void ExpandResult_UDIV (SDNode *N, SDOperand &Lo, SDOperand &Hi); 287 void ExpandResult_UREM (SDNode *N, SDOperand &Lo, SDOperand &Hi); 288 void ExpandResult_Shift (SDNode *N, SDOperand &Lo, SDOperand &Hi); 289 290 void ExpandShiftByConstant(SDNode *N, unsigned Amt, 291 SDOperand &Lo, SDOperand &Hi); 292 bool ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi); 293 294 // Operand Expansion. 295 bool ExpandOperand(SDNode *N, unsigned OperandNo); 296 SDOperand ExpandOperand_BIT_CONVERT(SDNode *N); 297 SDOperand ExpandOperand_BR_CC(SDNode *N); 298 SDOperand ExpandOperand_BUILD_VECTOR(SDNode *N); 299 SDOperand ExpandOperand_EXTRACT_ELEMENT(SDNode *N); 300 SDOperand ExpandOperand_SETCC(SDNode *N); 301 SDOperand ExpandOperand_SINT_TO_FP(SDOperand Source, MVT DestTy); 302 SDOperand ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo); 303 SDOperand ExpandOperand_TRUNCATE(SDNode *N); 304 SDOperand ExpandOperand_UINT_TO_FP(SDOperand Source, MVT DestTy); 305 306 void ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS, 307 ISD::CondCode &CCCode); 308 309 //===--------------------------------------------------------------------===// 310 // Float to Integer Conversion Support: LegalizeTypesFloatToInt.cpp 311 //===--------------------------------------------------------------------===// 312 313 SDOperand GetIntegerOp(SDOperand Op) { 314 SDOperand &IntegerOp = FloatToIntedNodes[Op]; 315 RemapNode(IntegerOp); 316 assert(IntegerOp.Val && "Operand wasn't converted to integer?"); 317 return IntegerOp; 318 } 319 void SetIntegerOp(SDOperand Op, SDOperand Result); 320 321 // Result Float to Integer Conversion. 322 void FloatToIntResult(SDNode *N, unsigned OpNo); 323 SDOperand FloatToIntRes_BIT_CONVERT(SDNode *N); 324 SDOperand FloatToIntRes_BUILD_PAIR(SDNode *N); 325 SDOperand FloatToIntRes_ConstantFP(ConstantFPSDNode *N); 326 SDOperand FloatToIntRes_FADD(SDNode *N); 327 SDOperand FloatToIntRes_FCOPYSIGN(SDNode *N); 328 SDOperand FloatToIntRes_FMUL(SDNode *N); 329 SDOperand FloatToIntRes_FSUB(SDNode *N); 330 SDOperand FloatToIntRes_LOAD(SDNode *N); 331 SDOperand FloatToIntRes_XINT_TO_FP(SDNode *N); 332 333 // Operand Float to Integer Conversion. 334 bool FloatToIntOperand(SDNode *N, unsigned OpNo); 335 SDOperand FloatToIntOp_BIT_CONVERT(SDNode *N); 336 337 //===--------------------------------------------------------------------===// 338 // Scalarization Support: LegalizeTypesScalarize.cpp 339 //===--------------------------------------------------------------------===// 340 341 SDOperand GetScalarizedOp(SDOperand Op) { 342 SDOperand &ScalarOp = ScalarizedNodes[Op]; 343 RemapNode(ScalarOp); 344 assert(ScalarOp.Val && "Operand wasn't scalarized?"); 345 return ScalarOp; 346 } 347 void SetScalarizedOp(SDOperand Op, SDOperand Result); 348 349 // Result Vector Scalarization: <1 x ty> -> ty. 350 void ScalarizeResult(SDNode *N, unsigned OpNo); 351 SDOperand ScalarizeRes_BinOp(SDNode *N); 352 SDOperand ScalarizeRes_UnaryOp(SDNode *N); 353 354 SDOperand ScalarizeRes_BIT_CONVERT(SDNode *N); 355 SDOperand ScalarizeRes_FPOWI(SDNode *N); 356 SDOperand ScalarizeRes_INSERT_VECTOR_ELT(SDNode *N); 357 SDOperand ScalarizeRes_LOAD(LoadSDNode *N); 358 SDOperand ScalarizeRes_SELECT(SDNode *N); 359 SDOperand ScalarizeRes_UNDEF(SDNode *N); 360 SDOperand ScalarizeRes_VECTOR_SHUFFLE(SDNode *N); 361 362 // Operand Vector Scalarization: <1 x ty> -> ty. 363 bool ScalarizeOperand(SDNode *N, unsigned OpNo); 364 SDOperand ScalarizeOp_BIT_CONVERT(SDNode *N); 365 SDOperand ScalarizeOp_EXTRACT_VECTOR_ELT(SDNode *N); 366 SDOperand ScalarizeOp_STORE(StoreSDNode *N, unsigned OpNo); 367 368 //===--------------------------------------------------------------------===// 369 // Vector Splitting Support: LegalizeTypesSplit.cpp 370 //===--------------------------------------------------------------------===// 371 372 void GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); 373 void SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi); 374 375 // Result Vector Splitting: <128 x ty> -> 2 x <64 x ty>. 376 void SplitResult(SDNode *N, unsigned OpNo); 377 378 void SplitRes_UNDEF(SDNode *N, SDOperand &Lo, SDOperand &Hi); 379 void SplitRes_LOAD(LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); 380 void SplitRes_BUILD_PAIR(SDNode *N, SDOperand &Lo, SDOperand &Hi); 381 void SplitRes_INSERT_VECTOR_ELT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 382 void SplitRes_VECTOR_SHUFFLE(SDNode *N, SDOperand &Lo, SDOperand &Hi); 383 384 void SplitRes_BUILD_VECTOR(SDNode *N, SDOperand &Lo, SDOperand &Hi); 385 void SplitRes_CONCAT_VECTORS(SDNode *N, SDOperand &Lo, SDOperand &Hi); 386 void SplitRes_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 387 void SplitRes_UnOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); 388 void SplitRes_BinOp(SDNode *N, SDOperand &Lo, SDOperand &Hi); 389 void SplitRes_FPOWI(SDNode *N, SDOperand &Lo, SDOperand &Hi); 390 void SplitRes_SELECT(SDNode *N, SDOperand &Lo, SDOperand &Hi); 391 392 // Operand Vector Splitting: <128 x ty> -> 2 x <64 x ty>. 393 bool SplitOperand(SDNode *N, unsigned OpNo); 394 395 SDOperand SplitOp_BIT_CONVERT(SDNode *N); 396 SDOperand SplitOp_EXTRACT_SUBVECTOR(SDNode *N); 397 SDOperand SplitOp_EXTRACT_VECTOR_ELT(SDNode *N); 398 SDOperand SplitOp_RET(SDNode *N, unsigned OpNo); 399 SDOperand SplitOp_STORE(StoreSDNode *N, unsigned OpNo); 400 SDOperand SplitOp_VECTOR_SHUFFLE(SDNode *N, unsigned OpNo); 401}; 402 403} // end namespace llvm. 404 405#endif 406