LLVM API Documentation
00001 //===-- AlphaISelDAGToDAG.cpp - Alpha pattern matching inst selector ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines a pattern matching instruction selector for Alpha, 00011 // converting from a legalized dag to a Alpha dag. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "Alpha.h" 00016 #include "AlphaTargetMachine.h" 00017 #include "AlphaISelLowering.h" 00018 #include "llvm/CodeGen/MachineInstrBuilder.h" 00019 #include "llvm/CodeGen/MachineFrameInfo.h" 00020 #include "llvm/CodeGen/MachineFunction.h" 00021 #include "llvm/CodeGen/MachineRegisterInfo.h" 00022 #include "llvm/CodeGen/SelectionDAG.h" 00023 #include "llvm/CodeGen/SelectionDAGISel.h" 00024 #include "llvm/Target/TargetOptions.h" 00025 #include "llvm/Constants.h" 00026 #include "llvm/DerivedTypes.h" 00027 #include "llvm/GlobalValue.h" 00028 #include "llvm/Intrinsics.h" 00029 #include "llvm/LLVMContext.h" 00030 #include "llvm/Support/Compiler.h" 00031 #include "llvm/Support/Debug.h" 00032 #include "llvm/Support/ErrorHandling.h" 00033 #include "llvm/Support/MathExtras.h" 00034 #include "llvm/Support/raw_ostream.h" 00035 #include <algorithm> 00036 using namespace llvm; 00037 00038 namespace { 00039 00040 //===--------------------------------------------------------------------===// 00041 /// AlphaDAGToDAGISel - Alpha specific code to select Alpha machine 00042 /// instructions for SelectionDAG operations. 00043 class AlphaDAGToDAGISel : public SelectionDAGISel { 00044 static const int64_t IMM_LOW = -32768; 00045 static const int64_t IMM_HIGH = 32767; 00046 static const int64_t IMM_MULT = 65536; 00047 static const int64_t IMM_FULLHIGH = IMM_HIGH + IMM_HIGH * IMM_MULT; 00048 static const int64_t IMM_FULLLOW = IMM_LOW + IMM_LOW * IMM_MULT; 00049 00050 static int64_t get_ldah16(int64_t x) { 00051 int64_t y = x / IMM_MULT; 00052 if (x % IMM_MULT > IMM_HIGH) 00053 ++y; 00054 return y; 00055 } 00056 00057 static int64_t get_lda16(int64_t x) { 00058 return x - get_ldah16(x) * IMM_MULT; 00059 } 00060 00061 /// get_zapImm - Return a zap mask if X is a valid immediate for a zapnot 00062 /// instruction (if not, return 0). Note that this code accepts partial 00063 /// zap masks. For example (and LHS, 1) is a valid zap, as long we know 00064 /// that the bits 1-7 of LHS are already zero. If LHS is non-null, we are 00065 /// in checking mode. If LHS is null, we assume that the mask has already 00066 /// been validated before. 00067 uint64_t get_zapImm(SDValue LHS, uint64_t Constant) { 00068 uint64_t BitsToCheck = 0; 00069 unsigned Result = 0; 00070 for (unsigned i = 0; i != 8; ++i) { 00071 if (((Constant >> 8*i) & 0xFF) == 0) { 00072 // nothing to do. 00073 } else { 00074 Result |= 1 << i; 00075 if (((Constant >> 8*i) & 0xFF) == 0xFF) { 00076 // If the entire byte is set, zapnot the byte. 00077 } else if (LHS.getNode() == 0) { 00078 // Otherwise, if the mask was previously validated, we know its okay 00079 // to zapnot this entire byte even though all the bits aren't set. 00080 } else { 00081 // Otherwise we don't know that the it's okay to zapnot this entire 00082 // byte. Only do this iff we can prove that the missing bits are 00083 // already null, so the bytezap doesn't need to really null them. 00084 BitsToCheck |= ~Constant & (0xFF << 8*i); 00085 } 00086 } 00087 } 00088 00089 // If there are missing bits in a byte (for example, X & 0xEF00), check to 00090 // see if the missing bits (0x1000) are already known zero if not, the zap 00091 // isn't okay to do, as it won't clear all the required bits. 00092 if (BitsToCheck && 00093 !CurDAG->MaskedValueIsZero(LHS, 00094 APInt(LHS.getValueSizeInBits(), 00095 BitsToCheck))) 00096 return 0; 00097 00098 return Result; 00099 } 00100 00101 static uint64_t get_zapImm(uint64_t x) { 00102 unsigned build = 0; 00103 for(int i = 0; i != 8; ++i) { 00104 if ((x & 0x00FF) == 0x00FF) 00105 build |= 1 << i; 00106 else if ((x & 0x00FF) != 0) 00107 return 0; 00108 x >>= 8; 00109 } 00110 return build; 00111 } 00112 00113 00114 static uint64_t getNearPower2(uint64_t x) { 00115 if (!x) return 0; 00116 unsigned at = CountLeadingZeros_64(x); 00117 uint64_t complow = 1 << (63 - at); 00118 uint64_t comphigh = 1 << (64 - at); 00119 //cerr << x << ":" << complow << ":" << comphigh << "\n"; 00120 if (abs64(complow - x) <= abs64(comphigh - x)) 00121 return complow; 00122 else 00123 return comphigh; 00124 } 00125 00126 static bool chkRemNearPower2(uint64_t x, uint64_t r, bool swap) { 00127 uint64_t y = getNearPower2(x); 00128 if (swap) 00129 return (y - x) == r; 00130 else 00131 return (x - y) == r; 00132 } 00133 00134 static bool isFPZ(SDValue N) { 00135 ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N); 00136 return (CN && (CN->getValueAPF().isZero())); 00137 } 00138 static bool isFPZn(SDValue N) { 00139 ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N); 00140 return (CN && CN->getValueAPF().isNegZero()); 00141 } 00142 static bool isFPZp(SDValue N) { 00143 ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N); 00144 return (CN && CN->getValueAPF().isPosZero()); 00145 } 00146 00147 public: 00148 explicit AlphaDAGToDAGISel(AlphaTargetMachine &TM) 00149 : SelectionDAGISel(TM) 00150 {} 00151 00152 /// getI64Imm - Return a target constant with the specified value, of type 00153 /// i64. 00154 inline SDValue getI64Imm(int64_t Imm) { 00155 return CurDAG->getTargetConstant(Imm, MVT::i64); 00156 } 00157 00158 // Select - Convert the specified operand from a target-independent to a 00159 // target-specific node if it hasn't already been changed. 00160 SDNode *Select(SDValue Op); 00161 00162 /// InstructionSelect - This callback is invoked by 00163 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 00164 virtual void InstructionSelect(); 00165 00166 virtual const char *getPassName() const { 00167 return "Alpha DAG->DAG Pattern Instruction Selection"; 00168 } 00169 00170 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for 00171 /// inline asm expressions. 00172 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, 00173 char ConstraintCode, 00174 std::vector<SDValue> &OutOps) { 00175 SDValue Op0; 00176 switch (ConstraintCode) { 00177 default: return true; 00178 case 'm': // memory 00179 Op0 = Op; 00180 break; 00181 } 00182 00183 OutOps.push_back(Op0); 00184 return false; 00185 } 00186 00187 // Include the pieces autogenerated from the target description. 00188 #include "AlphaGenDAGISel.inc" 00189 00190 private: 00191 /// getTargetMachine - Return a reference to the TargetMachine, casted 00192 /// to the target-specific type. 00193 const AlphaTargetMachine &getTargetMachine() { 00194 return static_cast<const AlphaTargetMachine &>(TM); 00195 } 00196 00197 /// getInstrInfo - Return a reference to the TargetInstrInfo, casted 00198 /// to the target-specific type. 00199 const AlphaInstrInfo *getInstrInfo() { 00200 return getTargetMachine().getInstrInfo(); 00201 } 00202 00203 SDNode *getGlobalBaseReg(); 00204 SDNode *getGlobalRetAddr(); 00205 void SelectCALL(SDValue Op); 00206 00207 }; 00208 } 00209 00210 /// getGlobalBaseReg - Output the instructions required to put the 00211 /// GOT address into a register. 00212 /// 00213 SDNode *AlphaDAGToDAGISel::getGlobalBaseReg() { 00214 unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF); 00215 return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode(); 00216 } 00217 00218 /// getGlobalRetAddr - Grab the return address. 00219 /// 00220 SDNode *AlphaDAGToDAGISel::getGlobalRetAddr() { 00221 unsigned GlobalRetAddr = getInstrInfo()->getGlobalRetAddr(MF); 00222 return CurDAG->getRegister(GlobalRetAddr, TLI.getPointerTy()).getNode(); 00223 } 00224 00225 /// InstructionSelect - This callback is invoked by 00226 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 00227 void AlphaDAGToDAGISel::InstructionSelect() { 00228 DEBUG(BB->dump()); 00229 00230 // Select target instructions for the DAG. 00231 SelectRoot(*CurDAG); 00232 CurDAG->RemoveDeadNodes(); 00233 } 00234 00235 // Select - Convert the specified operand from a target-independent to a 00236 // target-specific node if it hasn't already been changed. 00237 SDNode *AlphaDAGToDAGISel::Select(SDValue Op) { 00238 SDNode *N = Op.getNode(); 00239 if (N->isMachineOpcode()) { 00240 return NULL; // Already selected. 00241 } 00242 DebugLoc dl = N->getDebugLoc(); 00243 00244 switch (N->getOpcode()) { 00245 default: break; 00246 case AlphaISD::CALL: 00247 SelectCALL(Op); 00248 return NULL; 00249 00250 case ISD::FrameIndex: { 00251 int FI = cast<FrameIndexSDNode>(N)->getIndex(); 00252 return CurDAG->SelectNodeTo(N, Alpha::LDA, MVT::i64, 00253 CurDAG->getTargetFrameIndex(FI, MVT::i32), 00254 getI64Imm(0)); 00255 } 00256 case ISD::GLOBAL_OFFSET_TABLE: 00257 return getGlobalBaseReg(); 00258 case AlphaISD::GlobalRetAddr: 00259 return getGlobalRetAddr(); 00260 00261 case AlphaISD::DivCall: { 00262 SDValue Chain = CurDAG->getEntryNode(); 00263 SDValue N0 = Op.getOperand(0); 00264 SDValue N1 = Op.getOperand(1); 00265 SDValue N2 = Op.getOperand(2); 00266 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R24, N1, 00267 SDValue(0,0)); 00268 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R25, N2, 00269 Chain.getValue(1)); 00270 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R27, N0, 00271 Chain.getValue(1)); 00272 SDNode *CNode = 00273 CurDAG->getTargetNode(Alpha::JSRs, dl, MVT::Other, MVT::Flag, 00274 Chain, Chain.getValue(1)); 00275 Chain = CurDAG->getCopyFromReg(Chain, dl, Alpha::R27, MVT::i64, 00276 SDValue(CNode, 1)); 00277 return CurDAG->SelectNodeTo(N, Alpha::BISr, MVT::i64, Chain, Chain); 00278 } 00279 00280 case ISD::READCYCLECOUNTER: { 00281 SDValue Chain = N->getOperand(0); 00282 return CurDAG->getTargetNode(Alpha::RPCC, dl, MVT::i64, MVT::Other, 00283 Chain); 00284 } 00285 00286 case ISD::Constant: { 00287 uint64_t uval = cast<ConstantSDNode>(N)->getZExtValue(); 00288 00289 if (uval == 0) { 00290 SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, 00291 Alpha::R31, MVT::i64); 00292 ReplaceUses(Op, Result); 00293 return NULL; 00294 } 00295 00296 int64_t val = (int64_t)uval; 00297 int32_t val32 = (int32_t)val; 00298 if (val <= IMM_HIGH + IMM_HIGH * IMM_MULT && 00299 val >= IMM_LOW + IMM_LOW * IMM_MULT) 00300 break; //(LDAH (LDA)) 00301 if ((uval >> 32) == 0 && //empty upper bits 00302 val32 <= IMM_HIGH + IMM_HIGH * IMM_MULT) 00303 // val32 >= IMM_LOW + IMM_LOW * IMM_MULT) //always true 00304 break; //(zext (LDAH (LDA))) 00305 //Else use the constant pool 00306 ConstantInt *C = ConstantInt::get( 00307 Type::getInt64Ty(*CurDAG->getContext()), uval); 00308 SDValue CPI = CurDAG->getTargetConstantPool(C, MVT::i64); 00309 SDNode *Tmp = CurDAG->getTargetNode(Alpha::LDAHr, dl, MVT::i64, CPI, 00310 SDValue(getGlobalBaseReg(), 0)); 00311 return CurDAG->SelectNodeTo(N, Alpha::LDQr, MVT::i64, MVT::Other, 00312 CPI, SDValue(Tmp, 0), CurDAG->getEntryNode()); 00313 } 00314 case ISD::TargetConstantFP: 00315 case ISD::ConstantFP: { 00316 ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N); 00317 bool isDouble = N->getValueType(0) == MVT::f64; 00318 EVT T = isDouble ? MVT::f64 : MVT::f32; 00319 if (CN->getValueAPF().isPosZero()) { 00320 return CurDAG->SelectNodeTo(N, isDouble ? Alpha::CPYST : Alpha::CPYSS, 00321 T, CurDAG->getRegister(Alpha::F31, T), 00322 CurDAG->getRegister(Alpha::F31, T)); 00323 } else if (CN->getValueAPF().isNegZero()) { 00324 return CurDAG->SelectNodeTo(N, isDouble ? Alpha::CPYSNT : Alpha::CPYSNS, 00325 T, CurDAG->getRegister(Alpha::F31, T), 00326 CurDAG->getRegister(Alpha::F31, T)); 00327 } else { 00328 llvm_report_error("Unhandled FP constant type"); 00329 } 00330 break; 00331 } 00332 00333 case ISD::SETCC: 00334 if (N->getOperand(0).getNode()->getValueType(0).isFloatingPoint()) { 00335 ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get(); 00336 00337 unsigned Opc = Alpha::WTF; 00338 bool rev = false; 00339 bool inv = false; 00340 switch(CC) { 00341 default: DEBUG(N->dump(CurDAG)); llvm_unreachable("Unknown FP comparison!"); 00342 case ISD::SETEQ: case ISD::SETOEQ: case ISD::SETUEQ: 00343 Opc = Alpha::CMPTEQ; break; 00344 case ISD::SETLT: case ISD::SETOLT: case ISD::SETULT: 00345 Opc = Alpha::CMPTLT; break; 00346 case ISD::SETLE: case ISD::SETOLE: case ISD::SETULE: 00347 Opc = Alpha::CMPTLE; break; 00348 case ISD::SETGT: case ISD::SETOGT: case ISD::SETUGT: 00349 Opc = Alpha::CMPTLT; rev = true; break; 00350 case ISD::SETGE: case ISD::SETOGE: case ISD::SETUGE: 00351 Opc = Alpha::CMPTLE; rev = true; break; 00352 case ISD::SETNE: case ISD::SETONE: case ISD::SETUNE: 00353 Opc = Alpha::CMPTEQ; inv = true; break; 00354 case ISD::SETO: 00355 Opc = Alpha::CMPTUN; inv = true; break; 00356 case ISD::SETUO: 00357 Opc = Alpha::CMPTUN; break; 00358 }; 00359 SDValue tmp1 = N->getOperand(rev?1:0); 00360 SDValue tmp2 = N->getOperand(rev?0:1); 00361 SDNode *cmp = CurDAG->getTargetNode(Opc, dl, MVT::f64, tmp1, tmp2); 00362 if (inv) 00363 cmp = CurDAG->getTargetNode(Alpha::CMPTEQ, dl, 00364 MVT::f64, SDValue(cmp, 0), 00365 CurDAG->getRegister(Alpha::F31, MVT::f64)); 00366 switch(CC) { 00367 case ISD::SETUEQ: case ISD::SETULT: case ISD::SETULE: 00368 case ISD::SETUNE: case ISD::SETUGT: case ISD::SETUGE: 00369 { 00370 SDNode* cmp2 = CurDAG->getTargetNode(Alpha::CMPTUN, dl, MVT::f64, 00371 tmp1, tmp2); 00372 cmp = CurDAG->getTargetNode(Alpha::ADDT, dl, MVT::f64, 00373 SDValue(cmp2, 0), SDValue(cmp, 0)); 00374 break; 00375 } 00376 default: break; 00377 } 00378 00379 SDNode* LD = CurDAG->getTargetNode(Alpha::FTOIT, dl, 00380 MVT::i64, SDValue(cmp, 0)); 00381 return CurDAG->getTargetNode(Alpha::CMPULT, dl, MVT::i64, 00382 CurDAG->getRegister(Alpha::R31, MVT::i64), 00383 SDValue(LD,0)); 00384 } 00385 break; 00386 00387 case ISD::AND: { 00388 ConstantSDNode* SC = NULL; 00389 ConstantSDNode* MC = NULL; 00390 if (N->getOperand(0).getOpcode() == ISD::SRL && 00391 (MC = dyn_cast<ConstantSDNode>(N->getOperand(1))) && 00392 (SC = dyn_cast<ConstantSDNode>(N->getOperand(0).getOperand(1)))) { 00393 uint64_t sval = SC->getZExtValue(); 00394 uint64_t mval = MC->getZExtValue(); 00395 // If the result is a zap, let the autogened stuff handle it. 00396 if (get_zapImm(N->getOperand(0), mval)) 00397 break; 00398 // given mask X, and shift S, we want to see if there is any zap in the 00399 // mask if we play around with the botton S bits 00400 uint64_t dontcare = (~0ULL) >> (64 - sval); 00401 uint64_t mask = mval << sval; 00402 00403 if (get_zapImm(mask | dontcare)) 00404 mask = mask | dontcare; 00405 00406 if (get_zapImm(mask)) { 00407 SDValue Z = 00408 SDValue(CurDAG->getTargetNode(Alpha::ZAPNOTi, dl, MVT::i64, 00409 N->getOperand(0).getOperand(0), 00410 getI64Imm(get_zapImm(mask))), 0); 00411 return CurDAG->getTargetNode(Alpha::SRLr, dl, MVT::i64, Z, 00412 getI64Imm(sval)); 00413 } 00414 } 00415 break; 00416 } 00417 00418 } 00419 00420 return SelectCode(Op); 00421 } 00422 00423 void AlphaDAGToDAGISel::SelectCALL(SDValue Op) { 00424 //TODO: add flag stuff to prevent nondeturministic breakage! 00425 00426 SDNode *N = Op.getNode(); 00427 SDValue Chain = N->getOperand(0); 00428 SDValue Addr = N->getOperand(1); 00429 SDValue InFlag = N->getOperand(N->getNumOperands() - 1); 00430 DebugLoc dl = N->getDebugLoc(); 00431 00432 if (Addr.getOpcode() == AlphaISD::GPRelLo) { 00433 SDValue GOT = SDValue(getGlobalBaseReg(), 0); 00434 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R29, GOT, InFlag); 00435 InFlag = Chain.getValue(1); 00436 Chain = SDValue(CurDAG->getTargetNode(Alpha::BSR, dl, MVT::Other, 00437 MVT::Flag, Addr.getOperand(0), 00438 Chain, InFlag), 0); 00439 } else { 00440 Chain = CurDAG->getCopyToReg(Chain, dl, Alpha::R27, Addr, InFlag); 00441 InFlag = Chain.getValue(1); 00442 Chain = SDValue(CurDAG->getTargetNode(Alpha::JSR, dl, MVT::Other, 00443 MVT::Flag, Chain, InFlag), 0); 00444 } 00445 InFlag = Chain.getValue(1); 00446 00447 ReplaceUses(Op.getValue(0), Chain); 00448 ReplaceUses(Op.getValue(1), InFlag); 00449 } 00450 00451 00452 /// createAlphaISelDag - This pass converts a legalized DAG into a 00453 /// Alpha-specific DAG, ready for instruction scheduling. 00454 /// 00455 FunctionPass *llvm::createAlphaISelDag(AlphaTargetMachine &TM) { 00456 return new AlphaDAGToDAGISel(TM); 00457 }