contrib/llvm/lib/Target/Mips/MipsAnalyzeImmediate.cpp

   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 }