Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/AArch64/AArch64ExpandImm.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- AArch64ExpandImm.h - AArch64 Immediate Expansion -------------------===//
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
// This file implements the AArch64ExpandImm stuff.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "AArch64.h"
14
#include "AArch64ExpandImm.h"
15
#include "MCTargetDesc/AArch64AddressingModes.h"
16
17
namespace llvm {
18
19
namespace AArch64_IMM {
20
21
/// Helper function which extracts the specified 16-bit chunk from a
22
/// 64-bit value.
23
133k
static uint64_t getChunk(uint64_t Imm, unsigned ChunkIdx) {
24
133k
  assert(ChunkIdx < 4 && "Out of range chunk index specified!");
25
133k
26
133k
  return (Imm >> (ChunkIdx * 16)) & 0xFFFF;
27
133k
}
28
29
/// Check whether the given 16-bit chunk replicated to full 64-bit width
30
/// can be materialized with an ORR instruction.
31
8.33k
static bool canUseOrr(uint64_t Chunk, uint64_t &Encoding) {
32
8.33k
  Chunk = (Chunk << 48) | (Chunk << 32) | (Chunk << 16) | Chunk;
33
8.33k
34
8.33k
  return AArch64_AM::processLogicalImmediate(Chunk, 64, Encoding);
35
8.33k
}
36
37
/// Check for identical 16-bit chunks within the constant and if so
38
/// materialize them with a single ORR instruction. The remaining one or two
39
/// 16-bit chunks will be materialized with MOVK instructions.
40
///
41
/// This allows us to materialize constants like |A|B|A|A| or |A|B|C|A| (order
42
/// of the chunks doesn't matter), assuming |A|A|A|A| can be materialized with
43
/// an ORR instruction.
44
static bool tryToreplicateChunks(uint64_t UImm,
45
20.1k
         SmallVectorImpl<ImmInsnModel> &Insn) {
46
20.1k
  using CountMap = DenseMap<uint64_t, unsigned>;
47
20.1k
48
20.1k
  CountMap Counts;
49
20.1k
50
20.1k
  // Scan the constant and count how often every chunk occurs.
51
100k
  for (unsigned Idx = 0; Idx < 4; 
++Idx80.7k
)
52
80.7k
    ++Counts[getChunk(UImm, Idx)];
53
20.1k
54
20.1k
  // Traverse the chunks to find one which occurs more than once.
55
20.1k
  for (CountMap::const_iterator Chunk = Counts.begin(), End = Counts.end();
56
80.6k
       Chunk != End; 
++Chunk60.4k
) {
57
68.6k
    const uint64_t ChunkVal = Chunk->first;
58
68.6k
    const unsigned Count = Chunk->second;
59
68.6k
60
68.6k
    uint64_t Encoding = 0;
61
68.6k
62
68.6k
    // We are looking for chunks which have two or three instances and can be
63
68.6k
    // materialized with an ORR instruction.
64
68.6k
    if ((Count != 2 && 
Count != 360.3k
) ||
!canUseOrr(ChunkVal, Encoding)8.33k
)
65
60.4k
      continue;
66
8.26k
67
8.26k
    const bool CountThree = Count == 3;
68
8.26k
69
8.26k
    Insn.push_back({ AArch64::ORRXri, 0, Encoding });
70
8.26k
71
8.26k
    unsigned ShiftAmt = 0;
72
8.26k
    uint64_t Imm16 = 0;
73
8.26k
    // Find the first chunk not materialized with the ORR instruction.
74
8.69k
    for (; ShiftAmt < 64; 
ShiftAmt += 16431
) {
75
8.69k
      Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
76
8.69k
77
8.69k
      if (Imm16 != ChunkVal)
78
8.26k
        break;
79
8.69k
    }
80
8.26k
81
8.26k
    // Create the first MOVK instruction.
82
8.26k
    Insn.push_back({ AArch64::MOVKXi, Imm16,
83
8.26k
         AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt) });
84
8.26k
85
8.26k
    // In case we have three instances the whole constant is now materialized
86
8.26k
    // and we can exit.
87
8.26k
    if (CountThree)
88
0
      return true;
89
8.26k
90
8.26k
    // Find the remaining chunk which needs to be materialized.
91
24.0k
    
for (ShiftAmt += 16; 8.26k
ShiftAmt < 64;
ShiftAmt += 1615.7k
) {
92
24.0k
      Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
93
24.0k
94
24.0k
      if (Imm16 != ChunkVal)
95
8.26k
        break;
96
24.0k
    }
97
8.26k
    Insn.push_back({ AArch64::MOVKXi, Imm16,
98
8.26k
                     AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt) });
99
8.26k
    return true;
100
8.26k
  }
101
20.1k
102
20.1k
  
return false11.9k
;
103
20.1k
}
104
105
/// Check whether this chunk matches the pattern '1...0...'. This pattern
106
/// starts a contiguous sequence of ones if we look at the bits from the LSB
107
/// towards the MSB.
108
47.7k
static bool isStartChunk(uint64_t Chunk) {
109
47.7k
  if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())
110
0
    return false;
111
47.7k
112
47.7k
  return isMask_64(~Chunk);
113
47.7k
}
114
115
/// Check whether this chunk matches the pattern '0...1...' This pattern
116
/// ends a contiguous sequence of ones if we look at the bits from the LSB
117
/// towards the MSB.
118
47.0k
static bool isEndChunk(uint64_t Chunk) {
119
47.0k
  if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())
120
0
    return false;
121
47.0k
122
47.0k
  return isMask_64(Chunk);
123
47.0k
}
124
125
/// Clear or set all bits in the chunk at the given index.
126
626
static uint64_t updateImm(uint64_t Imm, unsigned Idx, bool Clear) {
127
626
  const uint64_t Mask = 0xFFFF;
128
626
129
626
  if (Clear)
130
357
    // Clear chunk in the immediate.
131
357
    Imm &= ~(Mask << (Idx * 16));
132
269
  else
133
269
    // Set all bits in the immediate for the particular chunk.
134
269
    Imm |= Mask << (Idx * 16);
135
626
136
626
  return Imm;
137
626
}
138
139
/// Check whether the constant contains a sequence of contiguous ones,
140
/// which might be interrupted by one or two chunks. If so, materialize the
141
/// sequence of contiguous ones with an ORR instruction.
142
/// Materialize the chunks which are either interrupting the sequence or outside
143
/// of the sequence with a MOVK instruction.
144
///
145
/// Assuming S is a chunk which starts the sequence (1...0...), E is a chunk
146
/// which ends the sequence (0...1...). Then we are looking for constants which
147
/// contain at least one S and E chunk.
148
/// E.g. |E|A|B|S|, |A|E|B|S| or |A|B|E|S|.
149
///
150
/// We are also looking for constants like |S|A|B|E| where the contiguous
151
/// sequence of ones wraps around the MSB into the LSB.
152
static bool trySequenceOfOnes(uint64_t UImm,
153
11.9k
                              SmallVectorImpl<ImmInsnModel> &Insn) {
154
11.9k
  const int NotSet = -1;
155
11.9k
  const uint64_t Mask = 0xFFFF;
156
11.9k
157
11.9k
  int StartIdx = NotSet;
158
11.9k
  int EndIdx = NotSet;
159
11.9k
  // Try to find the chunks which start/end a contiguous sequence of ones.
160
59.6k
  for (int Idx = 0; Idx < 4; 
++Idx47.7k
) {
161
47.7k
    int64_t Chunk = getChunk(UImm, Idx);
162
47.7k
    // Sign extend the 16-bit chunk to 64-bit.
163
47.7k
    Chunk = (Chunk << 48) >> 48;
164
47.7k
165
47.7k
    if (isStartChunk(Chunk))
166
707
      StartIdx = Idx;
167
47.0k
    else if (isEndChunk(Chunk))
168
992
      EndIdx = Idx;
169
47.7k
  }
170
11.9k
171
11.9k
  // Early exit in case we can't find a start/end chunk.
172
11.9k
  if (StartIdx == NotSet || 
EndIdx == NotSet636
)
173
11.6k
    return false;
174
313
175
313
  // Outside of the contiguous sequence of ones everything needs to be zero.
176
313
  uint64_t Outside = 0;
177
313
  // Chunks between the start and end chunk need to have all their bits set.
178
313
  uint64_t Inside = Mask;
179
313
180
313
  // If our contiguous sequence of ones wraps around from the MSB into the LSB,
181
313
  // just swap indices and pretend we are materializing a contiguous sequence
182
313
  // of zeros surrounded by a contiguous sequence of ones.
183
313
  if (StartIdx > EndIdx) {
184
83
    std::swap(StartIdx, EndIdx);
185
83
    std::swap(Outside, Inside);
186
83
  }
187
313
188
313
  uint64_t OrrImm = UImm;
189
313
  int FirstMovkIdx = NotSet;
190
313
  int SecondMovkIdx = NotSet;
191
313
192
313
  // Find out which chunks we need to patch up to obtain a contiguous sequence
193
313
  // of ones.
194
1.56k
  for (int Idx = 0; Idx < 4; 
++Idx1.25k
) {
195
1.25k
    const uint64_t Chunk = getChunk(UImm, Idx);
196
1.25k
197
1.25k
    // Check whether we are looking at a chunk which is not part of the
198
1.25k
    // contiguous sequence of ones.
199
1.25k
    if ((Idx < StartIdx || 
EndIdx < Idx1.00k
) &&
Chunk != Outside399
) {
200
399
      OrrImm = updateImm(OrrImm, Idx, Outside == 0);
201
399
202
399
      // Remember the index we need to patch.
203
399
      if (FirstMovkIdx == NotSet)
204
214
        FirstMovkIdx = Idx;
205
185
      else
206
185
        SecondMovkIdx = Idx;
207
399
208
399
      // Check whether we are looking a chunk which is part of the contiguous
209
399
      // sequence of ones.
210
853
    } else if (Idx > StartIdx && 
Idx < EndIdx540
&&
Chunk != Inside227
) {
211
227
      OrrImm = updateImm(OrrImm, Idx, Inside != Mask);
212
227
213
227
      // Remember the index we need to patch.
214
227
      if (FirstMovkIdx == NotSet)
215
99
        FirstMovkIdx = Idx;
216
128
      else
217
128
        SecondMovkIdx = Idx;
218
227
    }
219
1.25k
  }
220
313
  assert(FirstMovkIdx != NotSet && "Constant materializable with single ORR!");
221
313
222
313
  // Create the ORR-immediate instruction.
223
313
  uint64_t Encoding = 0;
224
313
  AArch64_AM::processLogicalImmediate(OrrImm, 64, Encoding);
225
313
  Insn.push_back({ AArch64::ORRXri, 0, Encoding });
226
313
227
313
  const bool SingleMovk = SecondMovkIdx == NotSet;
228
313
  Insn.push_back({ AArch64::MOVKXi, getChunk(UImm, FirstMovkIdx),
229
313
                   AArch64_AM::getShifterImm(AArch64_AM::LSL,
230
313
                                             FirstMovkIdx * 16) });
231
313
232
313
  // Early exit in case we only need to emit a single MOVK instruction.
233
313
  if (SingleMovk)
234
0
    return true;
235
313
236
313
  // Create the second MOVK instruction.
237
313
  Insn.push_back({ AArch64::MOVKXi, getChunk(UImm, SecondMovkIdx),
238
313
             AArch64_AM::getShifterImm(AArch64_AM::LSL,
239
313
                                             SecondMovkIdx * 16) });
240
313
241
313
  return true;
242
313
}
243
244
/// \brief Expand a MOVi32imm or MOVi64imm pseudo instruction to a
245
/// MOVZ or MOVN of width BitSize followed by up to 3 MOVK instructions.
246
static inline void expandMOVImmSimple(uint64_t Imm, unsigned BitSize,
247
              unsigned OneChunks, unsigned ZeroChunks,
248
1.70M
              SmallVectorImpl<ImmInsnModel> &Insn) {
249
1.70M
  const unsigned Mask = 0xFFFF;
250
1.70M
251
1.70M
  // Use a MOVZ or MOVN instruction to set the high bits, followed by one or
252
1.70M
  // more MOVK instructions to insert additional 16-bit portions into the
253
1.70M
  // lower bits.
254
1.70M
  bool isNeg = false;
255
1.70M
256
1.70M
  // Use MOVN to materialize the high bits if we have more all one chunks
257
1.70M
  // than all zero chunks.
258
1.70M
  if (OneChunks > ZeroChunks) {
259
175k
    isNeg = true;
260
175k
    Imm = ~Imm;
261
175k
  }
262
1.70M
263
1.70M
  unsigned FirstOpc;
264
1.70M
  if (BitSize == 32) {
265
750k
    Imm &= (1LL << 32) - 1;
266
750k
    FirstOpc = (isNeg ? 
AArch64::MOVNWi108k
:
AArch64::MOVZWi641k
);
267
952k
  } else {
268
952k
    FirstOpc = (isNeg ? 
AArch64::MOVNXi66.9k
:
AArch64::MOVZXi885k
);
269
952k
  }
270
1.70M
  unsigned Shift = 0;     // LSL amount for high bits with MOVZ/MOVN
271
1.70M
  unsigned LastShift = 0; // LSL amount for last MOVK
272
1.70M
  if (Imm != 0) {
273
1.18M
    unsigned LZ = countLeadingZeros(Imm);
274
1.18M
    unsigned TZ = countTrailingZeros(Imm);
275
1.18M
    Shift = (TZ / 16) * 16;
276
1.18M
    LastShift = ((63 - LZ) / 16) * 16;
277
1.18M
  }
278
1.70M
  unsigned Imm16 = (Imm >> Shift) & Mask;
279
1.70M
280
1.70M
  Insn.push_back({ FirstOpc, Imm16,
281
1.70M
                   AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) });
282
1.70M
283
1.70M
  if (Shift == LastShift)
284
1.61M
    return;
285
88.0k
286
88.0k
  // If a MOVN was used for the high bits of a negative value, flip the rest
287
88.0k
  // of the bits back for use with MOVK.
288
88.0k
  if (isNeg)
289
2.76k
    Imm = ~Imm;
290
88.0k
291
88.0k
  unsigned Opc = (BitSize == 32 ? 
AArch64::MOVKWi38.7k
:
AArch64::MOVKXi49.3k
);
292
204k
  while (Shift < LastShift) {
293
116k
    Shift += 16;
294
116k
    Imm16 = (Imm >> Shift) & Mask;
295
116k
    if (Imm16 == (isNeg ? 
Mask4.33k
:
0112k
))
296
2.59k
      continue; // This 16-bit portion is already set correctly.
297
114k
298
114k
    Insn.push_back({ Opc, Imm16,
299
114k
                     AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) });
300
114k
  }
301
88.0k
}
302
303
/// Expand a MOVi32imm or MOVi64imm pseudo instruction to one or more
304
/// real move-immediate instructions to synthesize the immediate.
305
void expandMOVImm(uint64_t Imm, unsigned BitSize,
306
1.72M
      SmallVectorImpl<ImmInsnModel> &Insn) {
307
1.72M
  const unsigned Mask = 0xFFFF;
308
1.72M
309
1.72M
  // Scan the immediate and count the number of 16-bit chunks which are either
310
1.72M
  // all ones or all zeros.
311
1.72M
  unsigned OneChunks = 0;
312
1.72M
  unsigned ZeroChunks = 0;
313
7.09M
  for (unsigned Shift = 0; Shift < BitSize; 
Shift += 165.37M
) {
314
5.37M
    const unsigned Chunk = (Imm >> Shift) & Mask;
315
5.37M
    if (Chunk == Mask)
316
401k
      OneChunks++;
317
4.97M
    else if (Chunk == 0)
318
3.63M
      ZeroChunks++;
319
5.37M
  }
320
1.72M
321
1.72M
  // Prefer MOVZ/MOVN over ORR because of the rules for the "mov" alias.
322
1.72M
  if ((BitSize / 16) - OneChunks <= 1 || 
(BitSize / 16) - ZeroChunks <= 11.53M
) {
323
1.61M
    expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
324
1.61M
    return;
325
1.61M
  }
326
105k
327
105k
  // Try a single ORR.
328
105k
  uint64_t UImm = Imm << (64 - BitSize) >> (64 - BitSize);
329
105k
  uint64_t Encoding;
330
105k
  if (AArch64_AM::processLogicalImmediate(UImm, BitSize, Encoding)) {
331
5.41k
    unsigned Opc = (BitSize == 32 ? 
AArch64::ORRWri551
:
AArch64::ORRXri4.85k
);
332
5.41k
    Insn.push_back({ Opc, 0, Encoding });
333
5.41k
    return;
334
5.41k
  }
335
99.6k
336
99.6k
  // One to up three instruction sequences.
337
99.6k
  //
338
99.6k
  // Prefer MOVZ/MOVN followed by MOVK; it's more readable, and possibly the
339
99.6k
  // fastest sequence with fast literal generation.
340
99.6k
  if (OneChunks >= (BitSize / 16) - 2 || 
ZeroChunks >= (BitSize / 16) - 258.8k
) {
341
73.7k
    expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
342
73.7k
    return;
343
73.7k
  }
344
25.9k
345
25.9k
  assert(BitSize == 64 && "All 32-bit immediates can be expanded with a"
346
25.9k
                          "MOVZ/MOVK pair");
347
25.9k
348
25.9k
  // Try other two-instruction sequences.
349
25.9k
350
25.9k
  // 64-bit ORR followed by MOVK.
351
25.9k
  // We try to construct the ORR immediate in three different ways: either we
352
25.9k
  // zero out the chunk which will be replaced, we fill the chunk which will
353
25.9k
  // be replaced with ones, or we take the bit pattern from the other half of
354
25.9k
  // the 64-bit immediate. This is comprehensive because of the way ORR
355
25.9k
  // immediates are constructed.
356
123k
  for (unsigned Shift = 0; Shift < BitSize; 
Shift += 1697.4k
) {
357
100k
    uint64_t ShiftedMask = (0xFFFFULL << Shift);
358
100k
    uint64_t ZeroChunk = UImm & ~ShiftedMask;
359
100k
    uint64_t OneChunk = UImm | ShiftedMask;
360
100k
    uint64_t RotatedImm = (UImm << 32) | (UImm >> 32);
361
100k
    uint64_t ReplicateChunk = ZeroChunk | (RotatedImm & ShiftedMask);
362
100k
    if (AArch64_AM::processLogicalImmediate(ZeroChunk, BitSize, Encoding) ||
363
100k
        
AArch64_AM::processLogicalImmediate(OneChunk, BitSize, Encoding)99.8k
||
364
100k
        AArch64_AM::processLogicalImmediate(ReplicateChunk, BitSize,
365
99.4k
                                            Encoding)) {
366
3.04k
      // Create the ORR-immediate instruction.
367
3.04k
      Insn.push_back({ AArch64::ORRXri, 0, Encoding });
368
3.04k
369
3.04k
      // Create the MOVK instruction.
370
3.04k
      const unsigned Imm16 = getChunk(UImm, Shift / 16);
371
3.04k
      Insn.push_back({ AArch64::MOVKXi, Imm16,
372
3.04k
           AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) });
373
3.04k
      return;
374
3.04k
    }
375
100k
  }
376
25.9k
377
25.9k
  // FIXME: Add more two-instruction sequences.
378
25.9k
379
25.9k
  // Three instruction sequences.
380
25.9k
  //
381
25.9k
  // Prefer MOVZ/MOVN followed by two MOVK; it's more readable, and possibly
382
25.9k
  // the fastest sequence with fast literal generation. (If neither MOVK is
383
25.9k
  // part of a fast literal generation pair, it could be slower than the
384
25.9k
  // four-instruction sequence, but we won't worry about that for now.)
385
25.9k
  
if (22.8k
OneChunks22.8k
||
ZeroChunks21.8k
) {
386
2.69k
    expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
387
2.69k
    return;
388
2.69k
  }
389
20.1k
390
20.1k
  // Check for identical 16-bit chunks within the constant and if so materialize
391
20.1k
  // them with a single ORR instruction. The remaining one or two 16-bit chunks
392
20.1k
  // will be materialized with MOVK instructions.
393
20.1k
  if (BitSize == 64 && tryToreplicateChunks(UImm, Insn))
394
8.26k
    return;
395
11.9k
396
11.9k
  // Check whether the constant contains a sequence of contiguous ones, which
397
11.9k
  // might be interrupted by one or two chunks. If so, materialize the sequence
398
11.9k
  // of contiguous ones with an ORR instruction. Materialize the chunks which
399
11.9k
  // are either interrupting the sequence or outside of the sequence with a
400
11.9k
  // MOVK instruction.
401
11.9k
  if (BitSize == 64 && trySequenceOfOnes(UImm, Insn))
402
313
    return;
403
11.6k
404
11.6k
  // We found no possible two or three instruction sequence; use the general
405
11.6k
  // four-instruction sequence.
406
11.6k
  expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
407
11.6k
}
408
409
} // end namespace AArch64_AM
410
411
} // end namespace llvm