LLVM  9.0.0svn
MipsAnalyzeImmediate.cpp
Go to the documentation of this file.
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"
12 #include <cassert>
13 #include <cstdint>
14 #include <iterator>
15 
16 using namespace llvm;
17 
18 MipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {}
19 
20 // Add I to the instruction sequences.
21 void MipsAnalyzeImmediate::AddInstr(InstSeqLs &SeqLs, const Inst &I) {
22  // Add an instruction seqeunce consisting of just I.
23  if (SeqLs.empty()) {
24  SeqLs.push_back(InstSeq(1, I));
25  return;
26  }
27 
28  for (InstSeqLs::iterator Iter = SeqLs.begin(); Iter != SeqLs.end(); ++Iter)
29  Iter->push_back(I);
30 }
31 
32 void MipsAnalyzeImmediate::GetInstSeqLsADDiu(uint64_t Imm, unsigned RemSize,
33  InstSeqLs &SeqLs) {
34  GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs);
35  AddInstr(SeqLs, Inst(ADDiu, Imm & 0xffffULL));
36 }
37 
38 void MipsAnalyzeImmediate::GetInstSeqLsORi(uint64_t Imm, unsigned RemSize,
39  InstSeqLs &SeqLs) {
40  GetInstSeqLs(Imm & 0xffffffffffff0000ULL, RemSize, SeqLs);
41  AddInstr(SeqLs, Inst(ORi, Imm & 0xffffULL));
42 }
43 
44 void MipsAnalyzeImmediate::GetInstSeqLsSLL(uint64_t Imm, unsigned RemSize,
45  InstSeqLs &SeqLs) {
46  unsigned Shamt = countTrailingZeros(Imm);
47  GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs);
48  AddInstr(SeqLs, Inst(SLL, Shamt));
49 }
50 
51 void MipsAnalyzeImmediate::GetInstSeqLs(uint64_t Imm, unsigned RemSize,
52  InstSeqLs &SeqLs) {
53  uint64_t MaskedImm = Imm & (0xffffffffffffffffULL >> (64 - Size));
54 
55  // Do nothing if Imm is 0.
56  if (!MaskedImm)
57  return;
58 
59  // A single ADDiu will do if RemSize <= 16.
60  if (RemSize <= 16) {
61  AddInstr(SeqLs, Inst(ADDiu, MaskedImm));
62  return;
63  }
64 
65  // Shift if the lower 16-bit is cleared.
66  if (!(Imm & 0xffff)) {
67  GetInstSeqLsSLL(Imm, RemSize, SeqLs);
68  return;
69  }
70 
71  GetInstSeqLsADDiu(Imm, RemSize, SeqLs);
72 
73  // If bit 15 is cleared, it doesn't make a difference whether the last
74  // instruction is an ADDiu or ORi. In that case, do not call GetInstSeqLsORi.
75  if (Imm & 0x8000) {
76  InstSeqLs SeqLsORi;
77  GetInstSeqLsORi(Imm, RemSize, SeqLsORi);
78  SeqLs.append(std::make_move_iterator(SeqLsORi.begin()),
79  std::make_move_iterator(SeqLsORi.end()));
80  }
81 }
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 void MipsAnalyzeImmediate::ReplaceADDiuSLLWithLUi(InstSeq &Seq) {
90  // Check if the first two instructions are ADDiu and SLL and the shift amount
91  // is at least 16.
92  if ((Seq.size() < 2) || (Seq[0].Opc != ADDiu) ||
93  (Seq[1].Opc != SLL) || (Seq[1].ImmOpnd < 16))
94  return;
95 
96  // Sign-extend and shift operand of ADDiu and see if it still fits in 16-bit.
97  int64_t Imm = SignExtend64<16>(Seq[0].ImmOpnd);
98  int64_t ShiftedImm = (uint64_t)Imm << (Seq[1].ImmOpnd - 16);
99 
100  if (!isInt<16>(ShiftedImm))
101  return;
102 
103  // Replace the first instruction and erase the second.
104  Seq[0].Opc = LUi;
105  Seq[0].ImmOpnd = (unsigned)(ShiftedImm & 0xffff);
106  Seq.erase(Seq.begin() + 1);
107 }
108 
109 void MipsAnalyzeImmediate::GetShortestSeq(InstSeqLs &SeqLs, InstSeq &Insts) {
110  InstSeqLs::iterator ShortestSeq = SeqLs.end();
111  // The length of an instruction sequence is at most 7.
112  unsigned ShortestLength = 8;
113 
114  for (InstSeqLs::iterator S = SeqLs.begin(); S != SeqLs.end(); ++S) {
115  ReplaceADDiuSLLWithLUi(*S);
116  assert(S->size() <= 7);
117 
118  if (S->size() < ShortestLength) {
119  ShortestSeq = S;
120  ShortestLength = S->size();
121  }
122  }
123 
124  Insts.clear();
125  Insts.append(ShortestSeq->begin(), ShortestSeq->end());
126 }
127 
129 &MipsAnalyzeImmediate::Analyze(uint64_t Imm, unsigned Size,
130  bool LastInstrIsADDiu) {
131  this->Size = Size;
132 
133  if (Size == 32) {
134  ADDiu = Mips::ADDiu;
135  ORi = Mips::ORi;
136  SLL = Mips::SLL;
137  LUi = Mips::LUi;
138  } else {
139  ADDiu = Mips::DADDiu;
140  ORi = Mips::ORi64;
141  SLL = Mips::DSLL;
142  LUi = Mips::LUi64;
143  }
144 
145  InstSeqLs SeqLs;
146 
147  // Get the list of instruction sequences.
148  if (LastInstrIsADDiu | !Imm)
149  GetInstSeqLsADDiu(Imm, Size, SeqLs);
150  else
151  GetInstSeqLs(Imm, Size, SeqLs);
152 
153  // Set Insts to the shortest instruction sequence.
154  GetShortestSeq(SeqLs, Insts);
155 
156  return Insts;
157 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void push_back(const T &Elt)
Definition: SmallVector.h:211
constexpr bool isInt< 16 >(int64_t x)
Definition: MathExtras.h:305
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:119
SmallVector< Inst, 7 > InstSeq
const InstSeq & Analyze(uint64_t Imm, unsigned Size, bool LastInstrIsADDiu)
Analyze - Get an instruction sequence to load immediate Imm.
iterator erase(const_iterator CI)
Definition: SmallVector.h:434
size_t size() const
Definition: SmallVector.h:52
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
typename SuperClass::iterator iterator
Definition: SmallVector.h:319
Inst(unsigned Opc, unsigned ImmOpnd)
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())