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 #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 }
    155