10b57cec5SDimitry Andric //===- MipsAnalyzeImmediate.cpp - Analyze Immediates ----------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric
90b57cec5SDimitry Andric #include "MipsAnalyzeImmediate.h"
100b57cec5SDimitry Andric #include "Mips.h"
110b57cec5SDimitry Andric #include "llvm/Support/MathExtras.h"
120b57cec5SDimitry Andric #include <cassert>
130b57cec5SDimitry Andric #include <cstdint>
140b57cec5SDimitry Andric #include <iterator>
150b57cec5SDimitry Andric
160b57cec5SDimitry Andric using namespace llvm;
170b57cec5SDimitry Andric
Inst(unsigned O,unsigned I)180b57cec5SDimitry Andric MipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {}
190b57cec5SDimitry Andric
200b57cec5SDimitry Andric // Add I to the instruction sequences.
AddInstr(InstSeqLs & SeqLs,const Inst & I)210b57cec5SDimitry Andric void MipsAnalyzeImmediate::AddInstr(InstSeqLs &SeqLs, const Inst &I) {
220b57cec5SDimitry Andric // Add an instruction seqeunce consisting of just I.
230b57cec5SDimitry Andric if (SeqLs.empty()) {
240b57cec5SDimitry Andric SeqLs.push_back(InstSeq(1, I));
250b57cec5SDimitry Andric return;
260b57cec5SDimitry Andric }
270b57cec5SDimitry Andric
2804eeddc0SDimitry Andric for (auto &S : SeqLs)
2904eeddc0SDimitry Andric S.push_back(I);
300b57cec5SDimitry Andric }
310b57cec5SDimitry Andric
GetInstSeqLsADDiu(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)320b57cec5SDimitry Andric void MipsAnalyzeImmediate::GetInstSeqLsADDiu(uint64_t Imm, unsigned RemSize,
330b57cec5SDimitry Andric InstSeqLs &SeqLs) {
340b57cec5SDimitry Andric GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs);
350b57cec5SDimitry Andric AddInstr(SeqLs, Inst(ADDiu, Imm & 0xffffULL));
360b57cec5SDimitry Andric }
370b57cec5SDimitry Andric
GetInstSeqLsORi(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)380b57cec5SDimitry Andric void MipsAnalyzeImmediate::GetInstSeqLsORi(uint64_t Imm, unsigned RemSize,
390b57cec5SDimitry Andric InstSeqLs &SeqLs) {
400b57cec5SDimitry Andric GetInstSeqLs(Imm & 0xffffffffffff0000ULL, RemSize, SeqLs);
410b57cec5SDimitry Andric AddInstr(SeqLs, Inst(ORi, Imm & 0xffffULL));
420b57cec5SDimitry Andric }
430b57cec5SDimitry Andric
GetInstSeqLsSLL(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)440b57cec5SDimitry Andric void MipsAnalyzeImmediate::GetInstSeqLsSLL(uint64_t Imm, unsigned RemSize,
450b57cec5SDimitry Andric InstSeqLs &SeqLs) {
46*06c3fb27SDimitry Andric unsigned Shamt = llvm::countr_zero(Imm);
470b57cec5SDimitry Andric GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs);
480b57cec5SDimitry Andric AddInstr(SeqLs, Inst(SLL, Shamt));
490b57cec5SDimitry Andric }
500b57cec5SDimitry Andric
GetInstSeqLs(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)510b57cec5SDimitry Andric void MipsAnalyzeImmediate::GetInstSeqLs(uint64_t Imm, unsigned RemSize,
520b57cec5SDimitry Andric InstSeqLs &SeqLs) {
530b57cec5SDimitry Andric uint64_t MaskedImm = Imm & (0xffffffffffffffffULL >> (64 - Size));
540b57cec5SDimitry Andric
550b57cec5SDimitry Andric // Do nothing if Imm is 0.
560b57cec5SDimitry Andric if (!MaskedImm)
570b57cec5SDimitry Andric return;
580b57cec5SDimitry Andric
590b57cec5SDimitry Andric // A single ADDiu will do if RemSize <= 16.
600b57cec5SDimitry Andric if (RemSize <= 16) {
610b57cec5SDimitry Andric AddInstr(SeqLs, Inst(ADDiu, MaskedImm));
620b57cec5SDimitry Andric return;
630b57cec5SDimitry Andric }
640b57cec5SDimitry Andric
650b57cec5SDimitry Andric // Shift if the lower 16-bit is cleared.
660b57cec5SDimitry Andric if (!(Imm & 0xffff)) {
670b57cec5SDimitry Andric GetInstSeqLsSLL(Imm, RemSize, SeqLs);
680b57cec5SDimitry Andric return;
690b57cec5SDimitry Andric }
700b57cec5SDimitry Andric
710b57cec5SDimitry Andric GetInstSeqLsADDiu(Imm, RemSize, SeqLs);
720b57cec5SDimitry Andric
730b57cec5SDimitry Andric // If bit 15 is cleared, it doesn't make a difference whether the last
740b57cec5SDimitry Andric // instruction is an ADDiu or ORi. In that case, do not call GetInstSeqLsORi.
750b57cec5SDimitry Andric if (Imm & 0x8000) {
760b57cec5SDimitry Andric InstSeqLs SeqLsORi;
770b57cec5SDimitry Andric GetInstSeqLsORi(Imm, RemSize, SeqLsORi);
780b57cec5SDimitry Andric SeqLs.append(std::make_move_iterator(SeqLsORi.begin()),
790b57cec5SDimitry Andric std::make_move_iterator(SeqLsORi.end()));
800b57cec5SDimitry Andric }
810b57cec5SDimitry Andric }
820b57cec5SDimitry Andric
830b57cec5SDimitry Andric // Replace a ADDiu & SLL pair with a LUi.
840b57cec5SDimitry Andric // e.g. the following two instructions
850b57cec5SDimitry Andric // ADDiu 0x0111
860b57cec5SDimitry Andric // SLL 18
870b57cec5SDimitry Andric // are replaced with
880b57cec5SDimitry Andric // LUi 0x444
ReplaceADDiuSLLWithLUi(InstSeq & Seq)890b57cec5SDimitry Andric void MipsAnalyzeImmediate::ReplaceADDiuSLLWithLUi(InstSeq &Seq) {
900b57cec5SDimitry Andric // Check if the first two instructions are ADDiu and SLL and the shift amount
910b57cec5SDimitry Andric // is at least 16.
920b57cec5SDimitry Andric if ((Seq.size() < 2) || (Seq[0].Opc != ADDiu) ||
930b57cec5SDimitry Andric (Seq[1].Opc != SLL) || (Seq[1].ImmOpnd < 16))
940b57cec5SDimitry Andric return;
950b57cec5SDimitry Andric
960b57cec5SDimitry Andric // Sign-extend and shift operand of ADDiu and see if it still fits in 16-bit.
970b57cec5SDimitry Andric int64_t Imm = SignExtend64<16>(Seq[0].ImmOpnd);
980b57cec5SDimitry Andric int64_t ShiftedImm = (uint64_t)Imm << (Seq[1].ImmOpnd - 16);
990b57cec5SDimitry Andric
1000b57cec5SDimitry Andric if (!isInt<16>(ShiftedImm))
1010b57cec5SDimitry Andric return;
1020b57cec5SDimitry Andric
1030b57cec5SDimitry Andric // Replace the first instruction and erase the second.
1040b57cec5SDimitry Andric Seq[0].Opc = LUi;
1050b57cec5SDimitry Andric Seq[0].ImmOpnd = (unsigned)(ShiftedImm & 0xffff);
1060b57cec5SDimitry Andric Seq.erase(Seq.begin() + 1);
1070b57cec5SDimitry Andric }
1080b57cec5SDimitry Andric
GetShortestSeq(InstSeqLs & SeqLs,InstSeq & Insts)1090b57cec5SDimitry Andric void MipsAnalyzeImmediate::GetShortestSeq(InstSeqLs &SeqLs, InstSeq &Insts) {
1100b57cec5SDimitry Andric InstSeqLs::iterator ShortestSeq = SeqLs.end();
1110b57cec5SDimitry Andric // The length of an instruction sequence is at most 7.
1120b57cec5SDimitry Andric unsigned ShortestLength = 8;
1130b57cec5SDimitry Andric
1140b57cec5SDimitry Andric for (InstSeqLs::iterator S = SeqLs.begin(); S != SeqLs.end(); ++S) {
1150b57cec5SDimitry Andric ReplaceADDiuSLLWithLUi(*S);
1160b57cec5SDimitry Andric assert(S->size() <= 7);
1170b57cec5SDimitry Andric
1180b57cec5SDimitry Andric if (S->size() < ShortestLength) {
1190b57cec5SDimitry Andric ShortestSeq = S;
1200b57cec5SDimitry Andric ShortestLength = S->size();
1210b57cec5SDimitry Andric }
1220b57cec5SDimitry Andric }
1230b57cec5SDimitry Andric
1240b57cec5SDimitry Andric Insts.clear();
1250b57cec5SDimitry Andric Insts.append(ShortestSeq->begin(), ShortestSeq->end());
1260b57cec5SDimitry Andric }
1270b57cec5SDimitry Andric
1280b57cec5SDimitry Andric const MipsAnalyzeImmediate::InstSeq
Analyze(uint64_t Imm,unsigned Size,bool LastInstrIsADDiu)1290b57cec5SDimitry Andric &MipsAnalyzeImmediate::Analyze(uint64_t Imm, unsigned Size,
1300b57cec5SDimitry Andric bool LastInstrIsADDiu) {
1310b57cec5SDimitry Andric this->Size = Size;
1320b57cec5SDimitry Andric
1330b57cec5SDimitry Andric if (Size == 32) {
1340b57cec5SDimitry Andric ADDiu = Mips::ADDiu;
1350b57cec5SDimitry Andric ORi = Mips::ORi;
1360b57cec5SDimitry Andric SLL = Mips::SLL;
1370b57cec5SDimitry Andric LUi = Mips::LUi;
1380b57cec5SDimitry Andric } else {
1390b57cec5SDimitry Andric ADDiu = Mips::DADDiu;
1400b57cec5SDimitry Andric ORi = Mips::ORi64;
1410b57cec5SDimitry Andric SLL = Mips::DSLL;
1420b57cec5SDimitry Andric LUi = Mips::LUi64;
1430b57cec5SDimitry Andric }
1440b57cec5SDimitry Andric
1450b57cec5SDimitry Andric InstSeqLs SeqLs;
1460b57cec5SDimitry Andric
1470b57cec5SDimitry Andric // Get the list of instruction sequences.
1480b57cec5SDimitry Andric if (LastInstrIsADDiu | !Imm)
1490b57cec5SDimitry Andric GetInstSeqLsADDiu(Imm, Size, SeqLs);
1500b57cec5SDimitry Andric else
1510b57cec5SDimitry Andric GetInstSeqLs(Imm, Size, SeqLs);
1520b57cec5SDimitry Andric
1530b57cec5SDimitry Andric // Set Insts to the shortest instruction sequence.
1540b57cec5SDimitry Andric GetShortestSeq(SeqLs, Insts);
1550b57cec5SDimitry Andric
1560b57cec5SDimitry Andric return Insts;
1570b57cec5SDimitry Andric }
158