• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
Inst(unsigned O,unsigned I)15 MipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {}
16 
17 // Add I to the instruction sequences.
AddInstr(InstSeqLs & SeqLs,const Inst & I)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 
GetInstSeqLsADDiu(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)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 
GetInstSeqLsORi(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)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 
GetInstSeqLsSLL(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)41 void 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 
GetInstSeqLs(uint64_t Imm,unsigned RemSize,InstSeqLs & SeqLs)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.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
ReplaceADDiuSLLWithLUi(InstSeq & Seq)85 void 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 
GetShortestSeq(InstSeqLs & SeqLs,InstSeq & Insts)105 void 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 
124 const MipsAnalyzeImmediate::InstSeq
Analyze(uint64_t Imm,unsigned Size,bool LastInstrIsADDiu)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