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