Home | History | Annotate | Download | only in Mips 
      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 }
    159