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