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