1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
| //===- MipsAnalyzeImmediate.cpp - Analyze Immediates ----------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "MipsAnalyzeImmediate.h"
#include "Mips.h"
#include "llvm/Support/MathExtras.h"
#include <cassert>
#include <cstdint>
#include <iterator>
using namespace llvm;
MipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {}
// Add I to the instruction sequences.
void MipsAnalyzeImmediate::AddInstr(InstSeqLs &SeqLs, const Inst &I) {
// Add an instruction seqeunce consisting of just I.
if (SeqLs.empty()) {
SeqLs.push_back(InstSeq(1, I));
return;
}
for (InstSeqLs::iterator Iter = SeqLs.begin(); Iter != SeqLs.end(); ++Iter)
Iter->push_back(I);
}
void MipsAnalyzeImmediate::GetInstSeqLsADDiu(uint64_t Imm, unsigned RemSize,
InstSeqLs &SeqLs) {
GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs);
AddInstr(SeqLs, Inst(ADDiu, Imm & 0xffffULL));
}
void MipsAnalyzeImmediate::GetInstSeqLsORi(uint64_t Imm, unsigned RemSize,
InstSeqLs &SeqLs) {
GetInstSeqLs(Imm & 0xffffffffffff0000ULL, RemSize, SeqLs);
AddInstr(SeqLs, Inst(ORi, Imm & 0xffffULL));
}
void MipsAnalyzeImmediate::GetInstSeqLsSLL(uint64_t Imm, unsigned RemSize,
InstSeqLs &SeqLs) {
unsigned Shamt = countTrailingZeros(Imm);
GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs);
AddInstr(SeqLs, Inst(SLL, Shamt));
}
void MipsAnalyzeImmediate::GetInstSeqLs(uint64_t Imm, unsigned RemSize,
InstSeqLs &SeqLs) {
uint64_t MaskedImm = Imm & (0xffffffffffffffffULL >> (64 - Size));
// Do nothing if Imm is 0.
if (!MaskedImm)
return;
// A single ADDiu will do if RemSize <= 16.
if (RemSize <= 16) {
AddInstr(SeqLs, Inst(ADDiu, MaskedImm));
return;
}
// Shift if the lower 16-bit is cleared.
if (!(Imm & 0xffff)) {
GetInstSeqLsSLL(Imm, RemSize, SeqLs);
return;
}
GetInstSeqLsADDiu(Imm, RemSize, SeqLs);
// If bit 15 is cleared, it doesn't make a difference whether the last
// instruction is an ADDiu or ORi. In that case, do not call GetInstSeqLsORi.
if (Imm & 0x8000) {
InstSeqLs SeqLsORi;
GetInstSeqLsORi(Imm, RemSize, SeqLsORi);
SeqLs.append(std::make_move_iterator(SeqLsORi.begin()),
std::make_move_iterator(SeqLsORi.end()));
}
}
// Replace a ADDiu & SLL pair with a LUi.
// e.g. the following two instructions
// ADDiu 0x0111
// SLL 18
// are replaced with
// LUi 0x444
void MipsAnalyzeImmediate::ReplaceADDiuSLLWithLUi(InstSeq &Seq) {
// Check if the first two instructions are ADDiu and SLL and the shift amount
// is at least 16.
if ((Seq.size() < 2) || (Seq[0].Opc != ADDiu) ||
(Seq[1].Opc != SLL) || (Seq[1].ImmOpnd < 16))
return;
// Sign-extend and shift operand of ADDiu and see if it still fits in 16-bit.
int64_t Imm = SignExtend64<16>(Seq[0].ImmOpnd);
int64_t ShiftedImm = (uint64_t)Imm << (Seq[1].ImmOpnd - 16);
if (!isInt<16>(ShiftedImm))
return;
// Replace the first instruction and erase the second.
Seq[0].Opc = LUi;
Seq[0].ImmOpnd = (unsigned)(ShiftedImm & 0xffff);
Seq.erase(Seq.begin() + 1);
}
void MipsAnalyzeImmediate::GetShortestSeq(InstSeqLs &SeqLs, InstSeq &Insts) {
InstSeqLs::iterator ShortestSeq = SeqLs.end();
// The length of an instruction sequence is at most 7.
unsigned ShortestLength = 8;
for (InstSeqLs::iterator S = SeqLs.begin(); S != SeqLs.end(); ++S) {
ReplaceADDiuSLLWithLUi(*S);
assert(S->size() <= 7);
if (S->size() < ShortestLength) {
ShortestSeq = S;
ShortestLength = S->size();
}
}
Insts.clear();
Insts.append(ShortestSeq->begin(), ShortestSeq->end());
}
const MipsAnalyzeImmediate::InstSeq
&MipsAnalyzeImmediate::Analyze(uint64_t Imm, unsigned Size,
bool LastInstrIsADDiu) {
this->Size = Size;
if (Size == 32) {
ADDiu = Mips::ADDiu;
ORi = Mips::ORi;
SLL = Mips::SLL;
LUi = Mips::LUi;
} else {
ADDiu = Mips::DADDiu;
ORi = Mips::ORi64;
SLL = Mips::DSLL;
LUi = Mips::LUi64;
}
InstSeqLs SeqLs;
// Get the list of instruction sequences.
if (LastInstrIsADDiu | !Imm)
GetInstSeqLsADDiu(Imm, Size, SeqLs);
else
GetInstSeqLs(Imm, Size, SeqLs);
// Set Insts to the shortest instruction sequence.
GetShortestSeq(SeqLs, Insts);
return Insts;
}
|