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