MipsAnalyzeImmediate.cpp revision 1144af3c9b4da48cd581156e05b24261c8de366a 
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
13using namespace llvm;
14
15MipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {}
16
17// Add I to the instruction sequences.
18void 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
29void 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
35void 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
41void MipsAnalyzeImmediate::GetInstSeqLsSLL(uint64_t Imm, unsigned RemSize,
42                                           InstSeqLs &SeqLs) {
43  unsigned Shamt = CountTrailingZeros_64(Imm);
44  GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs);
45  AddInstr(SeqLs, Inst(SLL, Shamt));
46}
47
48void 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.insert(SeqLs.end(), SeqLsORi.begin(), SeqLsORi.end());
76  }
77}
78
79// Replace a ADDiu & SLL pair with a LUi.
80// e.g. the following two instructions
81//  ADDiu 0x0111
82//  SLL 18
83// are replaced with
84//  LUi 0x444
85void MipsAnalyzeImmediate::ReplaceADDiuSLLWithLUi(InstSeq &Seq) {
86  // Check if the first two instructions are ADDiu and SLL and the shift amount
87  // is at least 16.
88  if ((Seq.size() < 2) || (Seq[0].Opc != ADDiu) ||
89      (Seq[1].Opc != SLL) || (Seq[1].ImmOpnd < 16))
90    return;
91
92  // Sign-extend and shift operand of ADDiu and see if it still fits in 16-bit.
93  int64_t Imm = SignExtend64<16>(Seq[0].ImmOpnd);
94  int64_t ShiftedImm = (uint64_t)Imm << (Seq[1].ImmOpnd - 16);
95
96  if (!isInt<16>(ShiftedImm))
97    return;
98
99  // Replace the first instruction and erase the second.
100  Seq[0].Opc = LUi;
101  Seq[0].ImmOpnd = (unsigned)(ShiftedImm & 0xffff);
102  Seq.erase(Seq.begin() + 1);
103}
104
105void MipsAnalyzeImmediate::GetShortestSeq(InstSeqLs &SeqLs, InstSeq &Insts) {
106  InstSeqLs::iterator ShortestSeq = SeqLs.end();
107  // The length of an instruction sequence is at most 7.
108  unsigned ShortestLength = 8;
109
110  for (InstSeqLs::iterator S = SeqLs.begin(); S != SeqLs.end(); ++S) {
111    ReplaceADDiuSLLWithLUi(*S);
112    assert(S->size() <= 7);
113
114    if (S->size() < ShortestLength) {
115      ShortestSeq = S;
116      ShortestLength = S->size();
117    }
118  }
119
120  Insts.clear();
121  Insts.append(ShortestSeq->begin(), ShortestSeq->end());
122}
123
124const MipsAnalyzeImmediate::InstSeq
125&MipsAnalyzeImmediate::Analyze(uint64_t Imm, unsigned Size,
126                               bool LastInstrIsADDiu) {
127  this->Size = Size;
128
129  if (Size == 32) {
130    ADDiu = Mips::ADDiu;
131    ORi = Mips::ORi;
132    SLL = Mips::SLL;
133    LUi = Mips::LUi;
134  } else {
135    ADDiu = Mips::DADDiu;
136    ORi = Mips::ORi64;
137    SLL = Mips::DSLL;
138    LUi = Mips::LUi64;
139  }
140
141  InstSeqLs SeqLs;
142
143  // Get the list of instruction sequences.
144  if (LastInstrIsADDiu | !Imm)
145    GetInstSeqLsADDiu(Imm, Size, SeqLs);
146  else
147    GetInstSeqLs(Imm, Size, SeqLs);
148
149  // Set Insts to the shortest instruction sequence.
150  GetShortestSeq(SeqLs, Insts);
151
152  return Insts;
153}
154