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