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(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.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
ReplaceADDiuSLLWithLUi(InstSeq & Seq)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
GetShortestSeq(InstSeqLs & SeqLs,InstSeq & Insts)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
Analyze(uint64_t Imm,unsigned Size,bool LastInstrIsADDiu)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