1 //===-- AlphaISelDAGToDAG.cpp - Alpha pattern matching inst selector ------===// 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 a pattern matching instruction selector for Alpha, 11 // converting from a legalized dag to a Alpha dag. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "Alpha.h" 16 #include "AlphaTargetMachine.h" 17 #include "llvm/CodeGen/MachineInstrBuilder.h" 18 #include "llvm/CodeGen/MachineFrameInfo.h" 19 #include "llvm/CodeGen/MachineFunction.h" 20 #include "llvm/CodeGen/MachineRegisterInfo.h" 21 #include "llvm/CodeGen/SelectionDAG.h" 22 #include "llvm/CodeGen/SelectionDAGISel.h" 23 #include "llvm/Target/TargetOptions.h" 24 #include "llvm/Constants.h" 25 #include "llvm/DerivedTypes.h" 26 #include "llvm/GlobalValue.h" 27 #include "llvm/Intrinsics.h" 28 #include "llvm/LLVMContext.h" 29 #include "llvm/Support/Compiler.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/MathExtras.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include <algorithm> 35 using namespace llvm; 36 37 namespace { 38 39 //===--------------------------------------------------------------------===// 40 /// AlphaDAGToDAGISel - Alpha specific code to select Alpha machine 41 /// instructions for SelectionDAG operations. 42 class AlphaDAGToDAGISel : public SelectionDAGISel { 43 static const int64_t IMM_LOW = -32768; 44 static const int64_t IMM_HIGH = 32767; 45 static const int64_t IMM_MULT = 65536; 46 static const int64_t IMM_FULLHIGH = IMM_HIGH + IMM_HIGH * IMM_MULT; 47 static const int64_t IMM_FULLLOW = IMM_LOW + IMM_LOW * IMM_MULT; 48 49 static int64_t get_ldah16(int64_t x) { 50 int64_t y = x / IMM_MULT; 51 if (x % IMM_MULT > IMM_HIGH) 52 ++y; 53 return y; 54 } 55 56 static int64_t get_lda16(int64_t x) { 57 return x - get_ldah16(x) * IMM_MULT; 58 } 59 60 /// get_zapImm - Return a zap mask if X is a valid immediate for a zapnot 61 /// instruction (if not, return 0). Note that this code accepts partial 62 /// zap masks. For example (and LHS, 1) is a valid zap, as long we know 63 /// that the bits 1-7 of LHS are already zero. If LHS is non-null, we are 64 /// in checking mode. If LHS is null, we assume that the mask has already 65 /// been validated before. 66 uint64_t get_zapImm(SDValue LHS, uint64_t Constant) const { 67 uint64_t BitsToCheck = 0; 68 unsigned Result = 0; 69 for (unsigned i = 0; i != 8; ++i) { 70 if (((Constant >> 8*i) & 0xFF) == 0) { 71 // nothing to do. 72 } else { 73 Result |= 1 << i; 74 if (((Constant >> 8*i) & 0xFF) == 0xFF) { 75 // If the entire byte is set, zapnot the byte. 76 } else if (LHS.getNode() == 0) { 77 // Otherwise, if the mask was previously validated, we know its okay 78 // to zapnot this entire byte even though all the bits aren't set. 79 } else { 80 // Otherwise we don't know that the it's okay to zapnot this entire 81 // byte. Only do this iff we can prove that the missing bits are 82 // already null, so the bytezap doesn't need to really null them. 83 BitsToCheck |= ~Constant & (0xFFULL << 8*i); 84 } 85 } 86 } 87 88 // If there are missing bits in a byte (for example, X & 0xEF00), check to 89 // see if the missing bits (0x1000) are already known zero if not, the zap 90 // isn't okay to do, as it won't clear all the required bits. 91 if (BitsToCheck && 92 !CurDAG->MaskedValueIsZero(LHS, 93 APInt(LHS.getValueSizeInBits(), 94 BitsToCheck))) 95 return 0; 96 97 return Result; 98 } 99 100 static uint64_t get_zapImm(uint64_t x) { 101 unsigned build = 0; 102 for(int i = 0; i != 8; ++i) { 103 if ((x & 0x00FF) == 0x00FF) 104 build |= 1 << i; 105 else if ((x & 0x00FF) != 0) 106 return 0; 107 x >>= 8; 108 } 109 return build; 110 } 111 112 113 static uint64_t getNearPower2(uint64_t x) { 114 if (!x) return 0; 115 unsigned at = CountLeadingZeros_64(x); 116 uint64_t complow = 1ULL << (63 - at); 117 uint64_t comphigh = complow << 1; 118 if (x - complow <= comphigh - x) 119 return complow; 120 else 121 return comphigh; 122 } 123 124 static bool chkRemNearPower2(uint64_t x, uint64_t r, bool swap) { 125 uint64_t y = getNearPower2(x); 126 if (swap) 127 return (y - x) == r; 128 else 129 return (x - y) == r; 130 } 131 132 public: 133 explicit AlphaDAGToDAGISel(AlphaTargetMachine &TM) 134 : SelectionDAGISel(TM) 135 {} 136 137 /// getI64Imm - Return a target constant with the specified value, of type 138 /// i64. 139 inline SDValue getI64Imm(int64_t Imm) { 140 return CurDAG->getTargetConstant(Imm, MVT::i64); 141 } 142 143 // Select - Convert the specified operand from a target-independent to a 144 // target-specific node if it hasn't already been changed. 145 SDNode *Select(SDNode *N); 146 147 virtual const char *getPassName() const { 148 return "Alpha DAG->DAG Pattern Instruction Selection"; 149 } 150 151 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for 152 /// inline asm expressions. 153 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, 154 char ConstraintCode, 155 std::vector<SDValue> &OutOps) { 156 SDValue Op0; 157 switch (ConstraintCode) { 158 default: return true; 159 case 'm': // memory 160 Op0 = Op; 161 break; 162 } 163 164 OutOps.push_back(Op0); 165 return false; 166 } 167 168 // Include the pieces autogenerated from the target description. 169 #include "AlphaGenDAGISel.inc" 170 171 private: 172 /// getTargetMachine - Return a reference to the TargetMachine, casted 173 /// to the target-specific type. 174 const AlphaTargetMachine &getTargetMachine() { 175 return static_cast<const AlphaTargetMachine &>(TM); 176 } 177 178 /// getInstrInfo - Return a reference to the TargetInstrInfo, casted 179 /// to the target-specific type. 180 const AlphaInstrInfo *getInstrInfo() { 181 return getTargetMachine().getInstrInfo(); 182 } 183 184 SDNode *getGlobalBaseReg(); 185 SDNode *getGlobalRetAddr(); 186 void SelectCALL(SDNode *Op); 187 188 }; 189 } 190 191 /// getGlobalBaseReg - Output the instructions required to put the 192 /// GOT address into a register. 193 /// 194 SDNode *AlphaDAGToDAGISel::getGlobalBaseReg() { 195 unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF); 196 return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode(); 197 } 198 199 /// getGlobalRetAddr - Grab the return address. 200 /// 201 SDNode *AlphaDAGToDAGISel::getGlobalRetAddr() { 202 unsigned GlobalRetAddr = getInstrInfo()->getGlobalRetAddr(MF); 203 return CurDAG->getRegister(GlobalRetAddr, TLI.getPointerTy()).getNode(); 204 } 205 206 // Select - Convert the specified operand from a target-independent to a 207 // target-specific node if it hasn't already been changed. 208 SDNode *AlphaDAGToDAGISel::Select(SDNode *N) { 209 if (N->isMachineOpcode()) 210 return NULL; // Already selected. 211 DebugLoc dl = N->getDebugLoc(); 212 213 switch (N->getOpcode()) { 214 default: break; 215 case AlphaISD::CALL: 216 SelectCALL(N); 217 return NULL; 218 219 case ISD::FrameIndex: { 220 int FI = cast<FrameIndexSDNode>(N)->getIndex(); 221 return CurDAG->SelectNodeTo(N, Alpha::LDA, MVT::i64, 222 CurDAG->getTargetFrameIndex(FI, MVT::i32), 223 getI64Imm(0)); 224 } 225 case ISD::GLOBAL_OFFSET_TABLE: 226 return getGlobalBaseReg(); 227 case AlphaISD::GlobalRetAddr: 228 return getGlobalRetAddr(); 229 230 case AlphaISD::DivCall: { 231 SDValue Chain = CurDAG->getEntryNode(); 232 SDValue N0 = N->getOperand(0); 233 SDValue N1 = N->getOperand(1); 234 SDValue N2 = N->getOperand(2); 235 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R24, N1, 236 SDValue(0,0)); 237 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R25, N2, 238 Chain.getValue(1)); 239 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R27, N0, 240 Chain.getValue(1)); 241 SDNode *CNode = 242 CurDAG->getMachineNode(Alpha::JSRs, dl, MVT::Other, MVT::Glue, 243 Chain, Chain.getValue(1)); 244 Chain = CurDAG->getCopyFromReg(Chain, dl, Alpha::R27, MVT::i64, 245 SDValue(CNode, 1)); 246 return CurDAG->SelectNodeTo(N, Alpha::BISr, MVT::i64, Chain, Chain); 247 } 248 249 case ISD::READCYCLECOUNTER: { 250 SDValue Chain = N->getOperand(0); 251 return CurDAG->getMachineNode(Alpha::RPCC, dl, MVT::i64, MVT::Other, 252 Chain); 253 } 254 255 case ISD::Constant: { 256 uint64_t uval = cast<ConstantSDNode>(N)->getZExtValue(); 257 258 if (uval == 0) { 259 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 260 Alpha::R31, MVT::i64); 261 ReplaceUses(SDValue(N, 0), Result); 262 return NULL; 263 } 264 265 int64_t val = (int64_t)uval; 266 int32_t val32 = (int32_t)val; 267 if (val <= IMM_HIGH + IMM_HIGH * IMM_MULT && 268 val >= IMM_LOW + IMM_LOW * IMM_MULT) 269 break; //(LDAH (LDA)) 270 if ((uval >> 32) == 0 && //empty upper bits 271 val32 <= IMM_HIGH + IMM_HIGH * IMM_MULT) 272 // val32 >= IMM_LOW + IMM_LOW * IMM_MULT) //always true 273 break; //(zext (LDAH (LDA))) 274 //Else use the constant pool 275 ConstantInt *C = ConstantInt::get( 276 Type::getInt64Ty(*CurDAG->getContext()), uval); 277 SDValue CPI = CurDAG->getTargetConstantPool(C, MVT::i64); 278 SDNode *Tmp = CurDAG->getMachineNode(Alpha::LDAHr, dl, MVT::i64, CPI, 279 SDValue(getGlobalBaseReg(), 0)); 280 return CurDAG->SelectNodeTo(N, Alpha::LDQr, MVT::i64, MVT::Other, 281 CPI, SDValue(Tmp, 0), CurDAG->getEntryNode()); 282 } 283 case ISD::TargetConstantFP: 284 case ISD::ConstantFP: { 285 ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N); 286 bool isDouble = N->getValueType(0) == MVT::f64; 287 EVT T = isDouble ? MVT::f64 : MVT::f32; 288 if (CN->getValueAPF().isPosZero()) { 289 return CurDAG->SelectNodeTo(N, isDouble ? Alpha::CPYST : Alpha::CPYSS, 290 T, CurDAG->getRegister(Alpha::F31, T), 291 CurDAG->getRegister(Alpha::F31, T)); 292 } else if (CN->getValueAPF().isNegZero()) { 293 return CurDAG->SelectNodeTo(N, isDouble ? Alpha::CPYSNT : Alpha::CPYSNS, 294 T, CurDAG->getRegister(Alpha::F31, T), 295 CurDAG->getRegister(Alpha::F31, T)); 296 } else { 297 report_fatal_error("Unhandled FP constant type"); 298 } 299 break; 300 } 301 302 case ISD::SETCC: 303 if (N->getOperand(0).getNode()->getValueType(0).isFloatingPoint()) { 304 ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get(); 305 306 unsigned Opc = Alpha::WTF; 307 bool rev = false; 308 bool inv = false; 309 switch(CC) { 310 default: DEBUG(N->dump(CurDAG)); llvm_unreachable("Unknown FP comparison!"); 311 case ISD::SETEQ: case ISD::SETOEQ: case ISD::SETUEQ: 312 Opc = Alpha::CMPTEQ; break; 313 case ISD::SETLT: case ISD::SETOLT: case ISD::SETULT: 314 Opc = Alpha::CMPTLT; break; 315 case ISD::SETLE: case ISD::SETOLE: case ISD::SETULE: 316 Opc = Alpha::CMPTLE; break; 317 case ISD::SETGT: case ISD::SETOGT: case ISD::SETUGT: 318 Opc = Alpha::CMPTLT; rev = true; break; 319 case ISD::SETGE: case ISD::SETOGE: case ISD::SETUGE: 320 Opc = Alpha::CMPTLE; rev = true; break; 321 case ISD::SETNE: case ISD::SETONE: case ISD::SETUNE: 322 Opc = Alpha::CMPTEQ; inv = true; break; 323 case ISD::SETO: 324 Opc = Alpha::CMPTUN; inv = true; break; 325 case ISD::SETUO: 326 Opc = Alpha::CMPTUN; break; 327 }; 328 SDValue tmp1 = N->getOperand(rev?1:0); 329 SDValue tmp2 = N->getOperand(rev?0:1); 330 SDNode *cmp = CurDAG->getMachineNode(Opc, dl, MVT::f64, tmp1, tmp2); 331 if (inv) 332 cmp = CurDAG->getMachineNode(Alpha::CMPTEQ, dl, 333 MVT::f64, SDValue(cmp, 0), 334 CurDAG->getRegister(Alpha::F31, MVT::f64)); 335 switch(CC) { 336 case ISD::SETUEQ: case ISD::SETULT: case ISD::SETULE: 337 case ISD::SETUNE: case ISD::SETUGT: case ISD::SETUGE: 338 { 339 SDNode* cmp2 = CurDAG->getMachineNode(Alpha::CMPTUN, dl, MVT::f64, 340 tmp1, tmp2); 341 cmp = CurDAG->getMachineNode(Alpha::ADDT, dl, MVT::f64, 342 SDValue(cmp2, 0), SDValue(cmp, 0)); 343 break; 344 } 345 default: break; 346 } 347 348 SDNode* LD = CurDAG->getMachineNode(Alpha::FTOIT, dl, 349 MVT::i64, SDValue(cmp, 0)); 350 return CurDAG->getMachineNode(Alpha::CMPULT, dl, MVT::i64, 351 CurDAG->getRegister(Alpha::R31, MVT::i64), 352 SDValue(LD,0)); 353 } 354 break; 355 356 case ISD::AND: { 357 ConstantSDNode* SC = NULL; 358 ConstantSDNode* MC = NULL; 359 if (N->getOperand(0).getOpcode() == ISD::SRL && 360 (MC = dyn_cast<ConstantSDNode>(N->getOperand(1))) && 361 (SC = dyn_cast<ConstantSDNode>(N->getOperand(0).getOperand(1)))) { 362 uint64_t sval = SC->getZExtValue(); 363 uint64_t mval = MC->getZExtValue(); 364 // If the result is a zap, let the autogened stuff handle it. 365 if (get_zapImm(N->getOperand(0), mval)) 366 break; 367 // given mask X, and shift S, we want to see if there is any zap in the 368 // mask if we play around with the botton S bits 369 uint64_t dontcare = (~0ULL) >> (64 - sval); 370 uint64_t mask = mval << sval; 371 372 if (get_zapImm(mask | dontcare)) 373 mask = mask | dontcare; 374 375 if (get_zapImm(mask)) { 376 SDValue Z = 377 SDValue(CurDAG->getMachineNode(Alpha::ZAPNOTi, dl, MVT::i64, 378 N->getOperand(0).getOperand(0), 379 getI64Imm(get_zapImm(mask))), 0); 380 return CurDAG->getMachineNode(Alpha::SRLr, dl, MVT::i64, Z, 381 getI64Imm(sval)); 382 } 383 } 384 break; 385 } 386 387 } 388 389 return SelectCode(N); 390 } 391 392 void AlphaDAGToDAGISel::SelectCALL(SDNode *N) { 393 //TODO: add flag stuff to prevent nondeturministic breakage! 394 395 SDValue Chain = N->getOperand(0); 396 SDValue Addr = N->getOperand(1); 397 SDValue InFlag = N->getOperand(N->getNumOperands() - 1); 398 DebugLoc dl = N->getDebugLoc(); 399 400 if (Addr.getOpcode() == AlphaISD::GPRelLo) { 401 SDValue GOT = SDValue(getGlobalBaseReg(), 0); 402 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R29, GOT, InFlag); 403 InFlag = Chain.getValue(1); 404 Chain = SDValue(CurDAG->getMachineNode(Alpha::BSR, dl, MVT::Other, 405 MVT::Glue, Addr.getOperand(0), 406 Chain, InFlag), 0); 407 } else { 408 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R27, Addr, InFlag); 409 InFlag = Chain.getValue(1); 410 Chain = SDValue(CurDAG->getMachineNode(Alpha::JSR, dl, MVT::Other, 411 MVT::Glue, Chain, InFlag), 0); 412 } 413 InFlag = Chain.getValue(1); 414 415 ReplaceUses(SDValue(N, 0), Chain); 416 ReplaceUses(SDValue(N, 1), InFlag); 417 } 418 419 420 /// createAlphaISelDag - This pass converts a legalized DAG into a 421 /// Alpha-specific DAG, ready for instruction scheduling. 422 /// 423 FunctionPass *llvm::createAlphaISelDag(AlphaTargetMachine &TM) { 424 return new AlphaDAGToDAGISel(TM); 425 } 426