158 lines · cpp
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-exception6//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 16using namespace llvm;17 18MipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {}19 20// Add I to the instruction sequences.21void 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 (auto &S : SeqLs)29 S.push_back(I);30}31 32void 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 38void 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 44void MipsAnalyzeImmediate::GetInstSeqLsSLL(uint64_t Imm, unsigned RemSize,45 InstSeqLs &SeqLs) {46 unsigned Shamt = llvm::countr_zero(Imm);47 GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs);48 AddInstr(SeqLs, Inst(SLL, Shamt));49}50 51void 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 last74 // 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 instructions85// ADDiu 0x011186// SLL 1887// are replaced with88// LUi 0x44489void MipsAnalyzeImmediate::ReplaceADDiuSLLWithLUi(InstSeq &Seq) {90 // Check if the first two instructions are ADDiu and SLL and the shift amount91 // 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 109void 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 128const MipsAnalyzeImmediate::InstSeq129&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 else151 GetInstSeqLs(Imm, Size, SeqLs);152 153 // Set Insts to the shortest instruction sequence.154 GetShortestSeq(SeqLs, Insts);155 156 return Insts;157}158