1 //===-- MipsAnalyzeImmediate.cpp - Analyze Immediates ---------------------===// 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 #include "MipsAnalyzeImmediate.h" 10 #include "Mips.h" 11 #include "llvm/Support/MathExtras.h" 12 13 using namespace llvm; 14 15 MipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {} 16 17 // Add I to the instruction sequences. 18 void MipsAnalyzeImmediate::AddInstr(InstSeqLs &SeqLs, const Inst &I) { 19 // Add an instruction seqeunce consisting of just I. 20 if (SeqLs.empty()) { 21 SeqLs.push_back(InstSeq(1, I)); 22 return; 23 } 24 25 for (InstSeqLs::iterator Iter = SeqLs.begin(); Iter != SeqLs.end(); ++Iter) 26 Iter->push_back(I); 27 } 28 29 void MipsAnalyzeImmediate::GetInstSeqLsADDiu(uint64_t Imm, unsigned RemSize, 30 InstSeqLs &SeqLs) { 31 GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs); 32 AddInstr(SeqLs, Inst(ADDiu, Imm & 0xffffULL)); 33 } 34 35 void MipsAnalyzeImmediate::GetInstSeqLsORi(uint64_t Imm, unsigned RemSize, 36 InstSeqLs &SeqLs) { 37 GetInstSeqLs(Imm & 0xffffffffffff0000ULL, RemSize, SeqLs); 38 AddInstr(SeqLs, Inst(ORi, Imm & 0xffffULL)); 39 } 40 41 void MipsAnalyzeImmediate::GetInstSeqLsSLL(uint64_t Imm, unsigned RemSize, 42 InstSeqLs &SeqLs) { 43 unsigned Shamt = countTrailingZeros(Imm); 44 GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs); 45 AddInstr(SeqLs, Inst(SLL, Shamt)); 46 } 47 48 void MipsAnalyzeImmediate::GetInstSeqLs(uint64_t Imm, unsigned RemSize, 49 InstSeqLs &SeqLs) { 50 uint64_t MaskedImm = Imm & (0xffffffffffffffffULL >> (64 - Size)); 51 52 // Do nothing if Imm is 0. 53 if (!MaskedImm) 54 return; 55 56 // A single ADDiu will do if RemSize <= 16. 57 if (RemSize <= 16) { 58 AddInstr(SeqLs, Inst(ADDiu, MaskedImm)); 59 return; 60 } 61 62 // Shift if the lower 16-bit is cleared. 63 if (!(Imm & 0xffff)) { 64 GetInstSeqLsSLL(Imm, RemSize, SeqLs); 65 return; 66 } 67 68 GetInstSeqLsADDiu(Imm, RemSize, SeqLs); 69 70 // If bit 15 is cleared, it doesn't make a difference whether the last 71 // instruction is an ADDiu or ORi. In that case, do not call GetInstSeqLsORi. 72 if (Imm & 0x8000) { 73 InstSeqLs SeqLsORi; 74 GetInstSeqLsORi(Imm, RemSize, SeqLsORi); 75 SeqLs.append(std::make_move_iterator(SeqLsORi.begin()), 76 std::make_move_iterator(SeqLsORi.end())); 77 } 78 } 79 80 // Replace a ADDiu & SLL pair with a LUi. 81 // e.g. the following two instructions 82 // ADDiu 0x0111 83 // SLL 18 84 // are replaced with 85 // LUi 0x444 86 void MipsAnalyzeImmediate::ReplaceADDiuSLLWithLUi(InstSeq &Seq) { 87 // Check if the first two instructions are ADDiu and SLL and the shift amount 88 // is at least 16. 89 if ((Seq.size() < 2) || (Seq[0].Opc != ADDiu) || 90 (Seq[1].Opc != SLL) || (Seq[1].ImmOpnd < 16)) 91 return; 92 93 // Sign-extend and shift operand of ADDiu and see if it still fits in 16-bit. 94 int64_t Imm = SignExtend64<16>(Seq[0].ImmOpnd); 95 int64_t ShiftedImm = (uint64_t)Imm << (Seq[1].ImmOpnd - 16); 96 97 if (!isInt<16>(ShiftedImm)) 98 return; 99 100 // Replace the first instruction and erase the second. 101 Seq[0].Opc = LUi; 102 Seq[0].ImmOpnd = (unsigned)(ShiftedImm & 0xffff); 103 Seq.erase(Seq.begin() + 1); 104 } 105 106 void MipsAnalyzeImmediate::GetShortestSeq(InstSeqLs &SeqLs, InstSeq &Insts) { 107 InstSeqLs::iterator ShortestSeq = SeqLs.end(); 108 // The length of an instruction sequence is at most 7. 109 unsigned ShortestLength = 8; 110 111 for (InstSeqLs::iterator S = SeqLs.begin(); S != SeqLs.end(); ++S) { 112 ReplaceADDiuSLLWithLUi(*S); 113 assert(S->size() <= 7); 114 115 if (S->size() < ShortestLength) { 116 ShortestSeq = S; 117 ShortestLength = S->size(); 118 } 119 } 120 121 Insts.clear(); 122 Insts.append(ShortestSeq->begin(), ShortestSeq->end()); 123 } 124 125 const MipsAnalyzeImmediate::InstSeq 126 &MipsAnalyzeImmediate::Analyze(uint64_t Imm, unsigned Size, 127 bool LastInstrIsADDiu) { 128 this->Size = Size; 129 130 if (Size == 32) { 131 ADDiu = Mips::ADDiu; 132 ORi = Mips::ORi; 133 SLL = Mips::SLL; 134 LUi = Mips::LUi; 135 } else { 136 ADDiu = Mips::DADDiu; 137 ORi = Mips::ORi64; 138 SLL = Mips::DSLL; 139 LUi = Mips::LUi64; 140 } 141 142 InstSeqLs SeqLs; 143 144 // Get the list of instruction sequences. 145 if (LastInstrIsADDiu | !Imm) 146 GetInstSeqLsADDiu(Imm, Size, SeqLs); 147 else 148 GetInstSeqLs(Imm, Size, SeqLs); 149 150 // Set Insts to the shortest instruction sequence. 151 GetShortestSeq(SeqLs, Insts); 152 153 return Insts; 154 } 155