lib/Target/Mips/MipsAnalyzeImmediate.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-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 }