Coverage Report

Created: 2017-05-05 14:42

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/AArch64/AArch64AddressTypePromotion.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- AArch64AddressTypePromotion.cpp --- Promote type for addr accesses -==//
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
// This pass tries to promote the computations use to obtained a sign extended
11
// value used into memory accesses.
12
// E.g.
13
// a = add nsw i32 b, 3
14
// d = sext i32 a to i64
15
// e = getelementptr ..., i64 d
16
//
17
// =>
18
// f = sext i32 b to i64
19
// a = add nsw i64 f, 3
20
// e = getelementptr ..., i64 a
21
//
22
// This is legal to do if the computations are marked with either nsw or nuw
23
// markers. Moreover, the current heuristic is simple: it does not create new
24
// sext operations, i.e., it gives up when a sext would have forked (e.g., if a
25
// = add i32 b, c, two sexts are required to promote the computation).
26
//
27
// FIXME: This pass may be useful for other targets too.
28
// ===---------------------------------------------------------------------===//
29
30
#include "AArch64.h"
31
#include "llvm/ADT/DenseMap.h"
32
#include "llvm/ADT/SmallPtrSet.h"
33
#include "llvm/ADT/SmallVector.h"
34
#include "llvm/ADT/StringRef.h"
35
#include "llvm/IR/Constants.h"
36
#include "llvm/IR/Dominators.h"
37
#include "llvm/IR/Function.h"
38
#include "llvm/IR/InstrTypes.h"
39
#include "llvm/IR/Instruction.h"
40
#include "llvm/IR/Instructions.h"
41
#include "llvm/IR/Operator.h"
42
#include "llvm/IR/Type.h"
43
#include "llvm/IR/Use.h"
44
#include "llvm/IR/User.h"
45
#include "llvm/Pass.h"
46
#include "llvm/Support/Casting.h"
47
#include "llvm/Support/CommandLine.h"
48
#include "llvm/Support/Debug.h"
49
#include "llvm/Support/raw_ostream.h"
50
#include <cassert>
51
52
using namespace llvm;
53
54
#define DEBUG_TYPE "aarch64-type-promotion"
55
56
static cl::opt<bool>
57
EnableMerge("aarch64-type-promotion-merge", cl::Hidden,
58
            cl::desc("Enable merging of redundant sexts when one is dominating"
59
                     " the other."),
60
            cl::init(true));
61
62
0
#define AARCH64_TYPE_PROMO_NAME "AArch64 Address Type Promotion"
63
64
//===----------------------------------------------------------------------===//
65
//                       AArch64AddressTypePromotion
66
//===----------------------------------------------------------------------===//
67
68
namespace {
69
70
class AArch64AddressTypePromotion : public FunctionPass {
71
public:
72
  static char ID;
73
74
0
  AArch64AddressTypePromotion() : FunctionPass(ID) {
75
0
    initializeAArch64AddressTypePromotionPass(*PassRegistry::getPassRegistry());
76
0
  }
77
78
0
  StringRef getPassName() const override 
{ return 0
AARCH64_TYPE_PROMO_NAME0
; }
79
80
  /// Iterate over the functions and promote the computation of interesting
81
  // sext instructions.
82
  bool runOnFunction(Function &F) override;
83
84
private:
85
  /// The current function.
86
  Function *Func = nullptr;
87
88
  /// Filter out all sexts that does not have this type.
89
  /// Currently initialized with Int64Ty.
90
  Type *ConsideredSExtType = nullptr;
91
92
  // This transformation requires dominator info.
93
0
  void getAnalysisUsage(AnalysisUsage &AU) const override {
94
0
    AU.setPreservesCFG();
95
0
    AU.addRequired<DominatorTreeWrapperPass>();
96
0
    AU.addPreserved<DominatorTreeWrapperPass>();
97
0
    FunctionPass::getAnalysisUsage(AU);
98
0
  }
99
100
  typedef SmallPtrSet<Instruction *, 32> SetOfInstructions;
101
  typedef SmallVector<Instruction *, 16> Instructions;
102
  typedef DenseMap<Value *, Instructions> ValueToInsts;
103
104
  /// Check if it is profitable to move a sext through this instruction.
105
  /// Currently, we consider it is profitable if:
106
  /// - Inst is used only once (no need to insert truncate).
107
  /// - Inst has only one operand that will require a sext operation (we do
108
  ///   do not create new sext operation).
109
  bool shouldGetThrough(const Instruction *Inst);
110
111
  /// Check if it is possible and legal to move a sext through this
112
  /// instruction.
113
  /// Current heuristic considers that we can get through:
114
  /// - Arithmetic operation marked with the nsw or nuw flag.
115
  /// - Other sext operation.
116
  /// - Truncate operation if it was just dropping sign extended bits.
117
  bool canGetThrough(const Instruction *Inst);
118
119
  /// Move sext operations through safe to sext instructions.
120
  bool propagateSignExtension(Instructions &SExtInsts);
121
122
  /// Is this sext should be considered for code motion.
123
  /// We look for sext with ConsideredSExtType and uses in at least one
124
  // GetElementPtrInst.
125
  bool shouldConsiderSExt(const Instruction *SExt) const;
126
127
  /// Collect all interesting sext operations, i.e., the ones with the right
128
  /// type and used in memory accesses.
129
  /// More precisely, a sext instruction is considered as interesting if it
130
  /// is used in a "complex" getelementptr or it exits at least another
131
  /// sext instruction that sign extended the same initial value.
132
  /// A getelementptr is considered as "complex" if it has more than 2
133
  // operands.
134
  void analyzeSExtension(Instructions &SExtInsts);
135
136
  /// Merge redundant sign extension operations in common dominator.
137
  void mergeSExts(ValueToInsts &ValToSExtendedUses,
138
                  SetOfInstructions &ToRemove);
139
};
140
141
} // end anonymous namespace
142
143
char AArch64AddressTypePromotion::ID = 0;
144
145
85.0k
INITIALIZE_PASS_BEGIN85.0k
(AArch64AddressTypePromotion, "aarch64-type-promotion",85.0k
146
85.0k
                      AARCH64_TYPE_PROMO_NAME, false, false)
147
85.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
148
85.0k
INITIALIZE_PASS_END(AArch64AddressTypePromotion, "aarch64-type-promotion",
149
                    AARCH64_TYPE_PROMO_NAME, false, false)
150
151
0
FunctionPass *llvm::createAArch64AddressTypePromotionPass() {
152
0
  return new AArch64AddressTypePromotion();
153
0
}
154
155
0
bool AArch64AddressTypePromotion::canGetThrough(const Instruction *Inst) {
156
0
  if (isa<SExtInst>(Inst))
157
0
    return true;
158
0
159
0
  const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
160
0
  if (
BinOp && 0
isa<OverflowingBinaryOperator>(BinOp)0
&&
161
0
      
(BinOp->hasNoUnsignedWrap() || 0
BinOp->hasNoSignedWrap()0
))
162
0
    return true;
163
0
164
0
  // sext(trunc(sext)) --> sext
165
0
  
if (0
isa<TruncInst>(Inst) && 0
isa<SExtInst>(Inst->getOperand(0))0
)
{0
166
0
    const Instruction *Opnd = cast<Instruction>(Inst->getOperand(0));
167
0
    // Check that the truncate just drop sign extended bits.
168
0
    if (Inst->getType()->getIntegerBitWidth() >=
169
0
            Opnd->getOperand(0)->getType()->getIntegerBitWidth() &&
170
0
        Inst->getOperand(0)->getType()->getIntegerBitWidth() <=
171
0
            ConsideredSExtType->getIntegerBitWidth())
172
0
      return true;
173
0
  }
174
0
175
0
  return false;
176
0
}
177
178
0
bool AArch64AddressTypePromotion::shouldGetThrough(const Instruction *Inst) {
179
0
  // If the type of the sext is the same as the considered one, this sext
180
0
  // will become useless.
181
0
  // Otherwise, we will have to do something to preserve the original value,
182
0
  // unless it is used once.
183
0
  if (isa<SExtInst>(Inst) &&
184
0
      
(Inst->getType() == ConsideredSExtType || 0
Inst->hasOneUse()0
))
185
0
    return true;
186
0
187
0
  // If the Inst is used more that once, we may need to insert truncate
188
0
  // operations and we don't do that at the moment.
189
0
  
if (0
!Inst->hasOneUse()0
)
190
0
    return false;
191
0
192
0
  // This truncate is used only once, thus if we can get thourgh, it will become
193
0
  // useless.
194
0
  
if (0
isa<TruncInst>(Inst)0
)
195
0
    return true;
196
0
197
0
  // If both operands are not constant, a new sext will be created here.
198
0
  // Current heuristic is: each step should be profitable.
199
0
  // Therefore we don't allow to increase the number of sext even if it may
200
0
  // be profitable later on.
201
0
  
if (0
isa<BinaryOperator>(Inst) && 0
isa<ConstantInt>(Inst->getOperand(1))0
)
202
0
    return true;
203
0
204
0
  return false;
205
0
}
206
207
0
static bool shouldSExtOperand(const Instruction *Inst, int OpIdx) {
208
0
  return !(isa<SelectInst>(Inst) && OpIdx == 0);
209
0
}
210
211
bool
212
0
AArch64AddressTypePromotion::shouldConsiderSExt(const Instruction *SExt) const {
213
0
  if (SExt->getType() != ConsideredSExtType)
214
0
    return false;
215
0
216
0
  
for (const User *U : SExt->users()) 0
{0
217
0
    if (isa<GetElementPtrInst>(U))
218
0
      return true;
219
0
  }
220
0
221
0
  return false;
222
0
}
223
224
// Input:
225
// - SExtInsts contains all the sext instructions that are used directly in
226
//   GetElementPtrInst, i.e., access to memory.
227
// Algorithm:
228
// - For each sext operation in SExtInsts:
229
//   Let var be the operand of sext.
230
//   while it is profitable (see shouldGetThrough), legal, and safe
231
//   (see canGetThrough) to move sext through var's definition:
232
//   * promote the type of var's definition.
233
//   * fold var into sext uses.
234
//   * move sext above var's definition.
235
//   * update sext operand to use the operand of var that should be sign
236
//     extended (by construction there is only one).
237
//
238
//   E.g.,
239
//   a = ... i32 c, 3
240
//   b = sext i32 a to i64 <- is it legal/safe/profitable to get through 'a'
241
//   ...
242
//   = b
243
// => Yes, update the code
244
//   b = sext i32 c to i64
245
//   a = ... i64 b, 3
246
//   ...
247
//   = a
248
// Iterate on 'c'.
249
bool
250
0
AArch64AddressTypePromotion::propagateSignExtension(Instructions &SExtInsts) {
251
0
  DEBUG(dbgs() << "*** Propagate Sign Extension ***\n");
252
0
253
0
  bool LocalChange = false;
254
0
  SetOfInstructions ToRemove;
255
0
  ValueToInsts ValToSExtendedUses;
256
0
  while (
!SExtInsts.empty()0
)
{0
257
0
    // Get through simple chain.
258
0
    Instruction *SExt = SExtInsts.pop_back_val();
259
0
260
0
    DEBUG(dbgs() << "Consider:\n" << *SExt << '\n');
261
0
262
0
    // If this SExt has already been merged continue.
263
0
    if (
SExt->use_empty() && 0
ToRemove.count(SExt)0
)
{0
264
0
      DEBUG(dbgs() << "No uses => marked as delete\n");
265
0
      continue;
266
0
    }
267
0
268
0
    // Now try to get through the chain of definitions.
269
0
    
while (auto *0
Inst0
= dyn_cast<Instruction>(SExt->getOperand(0)))
{0
270
0
      DEBUG(dbgs() << "Try to get through:\n" << *Inst << '\n');
271
0
      if (
!canGetThrough(Inst) || 0
!shouldGetThrough(Inst)0
)
{0
272
0
        // We cannot get through something that is not an Instruction
273
0
        // or not safe to SExt.
274
0
        DEBUG(dbgs() << "Cannot get through\n");
275
0
        break;
276
0
      }
277
0
278
0
      LocalChange = true;
279
0
      // If this is a sign extend, it becomes useless.
280
0
      if (
isa<SExtInst>(Inst) || 0
isa<TruncInst>(Inst)0
)
{0
281
0
        DEBUG(dbgs() << "SExt or trunc, mark it as to remove\n");
282
0
        // We cannot use replaceAllUsesWith here because we may trigger some
283
0
        // assertion on the type as all involved sext operation may have not
284
0
        // been moved yet.
285
0
        while (
!Inst->use_empty()0
)
{0
286
0
          Use &U = *Inst->use_begin();
287
0
          Instruction *User = dyn_cast<Instruction>(U.getUser());
288
0
          assert(User && "User of sext is not an Instruction!");
289
0
          User->setOperand(U.getOperandNo(), SExt);
290
0
        }
291
0
        ToRemove.insert(Inst);
292
0
        SExt->setOperand(0, Inst->getOperand(0));
293
0
        SExt->moveBefore(Inst);
294
0
        continue;
295
0
      }
296
0
297
0
      // Get through the Instruction:
298
0
      // 1. Update its type.
299
0
      // 2. Replace the uses of SExt by Inst.
300
0
      // 3. Sign extend each operand that needs to be sign extended.
301
0
302
0
      // Step #1.
303
0
      Inst->mutateType(SExt->getType());
304
0
      // Step #2.
305
0
      SExt->replaceAllUsesWith(Inst);
306
0
      // Step #3.
307
0
      Instruction *SExtForOpnd = SExt;
308
0
309
0
      DEBUG(dbgs() << "Propagate SExt to operands\n");
310
0
      for (int OpIdx = 0, EndOpIdx = Inst->getNumOperands(); OpIdx != EndOpIdx;
311
0
           
++OpIdx0
)
{0
312
0
        DEBUG(dbgs() << "Operand:\n" << *(Inst->getOperand(OpIdx)) << '\n');
313
0
        if (Inst->getOperand(OpIdx)->getType() == SExt->getType() ||
314
0
            
!shouldSExtOperand(Inst, OpIdx)0
)
{0
315
0
          DEBUG(dbgs() << "No need to propagate\n");
316
0
          continue;
317
0
        }
318
0
        // Check if we can statically sign extend the operand.
319
0
        Value *Opnd = Inst->getOperand(OpIdx);
320
0
        if (const ConstantInt *
Cst0
= dyn_cast<ConstantInt>(Opnd))
{0
321
0
          DEBUG(dbgs() << "Statically sign extend\n");
322
0
          Inst->setOperand(OpIdx, ConstantInt::getSigned(SExt->getType(),
323
0
                                                         Cst->getSExtValue()));
324
0
          continue;
325
0
        }
326
0
        // UndefValue are typed, so we have to statically sign extend them.
327
0
        
if (0
isa<UndefValue>(Opnd)0
)
{0
328
0
          DEBUG(dbgs() << "Statically sign extend\n");
329
0
          Inst->setOperand(OpIdx, UndefValue::get(SExt->getType()));
330
0
          continue;
331
0
        }
332
0
333
0
        // Otherwise we have to explicity sign extend it.
334
0
        assert(SExtForOpnd &&
335
0
               "Only one operand should have been sign extended");
336
0
337
0
        SExtForOpnd->setOperand(0, Opnd);
338
0
339
0
        DEBUG(dbgs() << "Move before:\n" << *Inst << "\nSign extend\n");
340
0
        // Move the sign extension before the insertion point.
341
0
        SExtForOpnd->moveBefore(Inst);
342
0
        Inst->setOperand(OpIdx, SExtForOpnd);
343
0
        // If more sext are required, new instructions will have to be created.
344
0
        SExtForOpnd = nullptr;
345
0
      }
346
0
      if (
SExtForOpnd == SExt0
)
{0
347
0
        DEBUG(dbgs() << "Sign extension is useless now\n");
348
0
        ToRemove.insert(SExt);
349
0
        break;
350
0
      }
351
0
    }
352
0
353
0
    // If the use is already of the right type, connect its uses to its argument
354
0
    // and delete it.
355
0
    // This can happen for an Instruction all uses of which are sign extended.
356
0
    if (!ToRemove.count(SExt) &&
357
0
        
SExt->getType() == SExt->getOperand(0)->getType()0
)
{0
358
0
      DEBUG(dbgs() << "Sign extension is useless, attach its use to "
359
0
                      "its argument\n");
360
0
      SExt->replaceAllUsesWith(SExt->getOperand(0));
361
0
      ToRemove.insert(SExt);
362
0
    } else
363
0
      ValToSExtendedUses[SExt->getOperand(0)].push_back(SExt);
364
0
  }
365
0
366
0
  if (EnableMerge)
367
0
    mergeSExts(ValToSExtendedUses, ToRemove);
368
0
369
0
  // Remove all instructions marked as ToRemove.
370
0
  for (Instruction *I: ToRemove)
371
0
    I->eraseFromParent();
372
0
  return LocalChange;
373
0
}
374
375
void AArch64AddressTypePromotion::mergeSExts(ValueToInsts &ValToSExtendedUses,
376
0
                                             SetOfInstructions &ToRemove) {
377
0
  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
378
0
379
0
  for (auto &Entry : ValToSExtendedUses) {
380
0
    Instructions &Insts = Entry.second;
381
0
    Instructions CurPts;
382
0
    for (Instruction *Inst : Insts) {
383
0
      if (ToRemove.count(Inst))
384
0
        continue;
385
0
      bool inserted = false;
386
0
      for (auto &Pt : CurPts) {
387
0
        if (
DT.dominates(Inst, Pt)0
)
{0
388
0
          DEBUG(dbgs() << "Replace all uses of:\n" << *Pt << "\nwith:\n"
389
0
                       << *Inst << '\n');
390
0
          Pt->replaceAllUsesWith(Inst);
391
0
          ToRemove.insert(Pt);
392
0
          Pt = Inst;
393
0
          inserted = true;
394
0
          break;
395
0
        }
396
0
        
if (0
!DT.dominates(Pt, Inst)0
)
397
0
          // Give up if we need to merge in a common dominator as the
398
0
          // expermients show it is not profitable.
399
0
          continue;
400
0
401
0
        
DEBUG0
(dbgs() << "Replace all uses of:\n" << *Inst << "\nwith:\n"0
402
0
                     << *Pt << '\n');
403
0
        Inst->replaceAllUsesWith(Pt);
404
0
        ToRemove.insert(Inst);
405
0
        inserted = true;
406
0
        break;
407
0
      }
408
0
      if (!inserted)
409
0
        CurPts.push_back(Inst);
410
0
    }
411
0
  }
412
0
}
413
414
0
void AArch64AddressTypePromotion::analyzeSExtension(Instructions &SExtInsts) {
415
0
  DEBUG(dbgs() << "*** Analyze Sign Extensions ***\n");
416
0
417
0
  DenseMap<Value *, Instruction *> SeenChains;
418
0
419
0
  for (auto &BB : *Func) {
420
0
    for (auto &II : BB) {
421
0
      Instruction *SExt = &II;
422
0
423
0
      // Collect all sext operation per type.
424
0
      if (
!isa<SExtInst>(SExt) || 0
!shouldConsiderSExt(SExt)0
)
425
0
        continue;
426
0
427
0
      
DEBUG0
(dbgs() << "Found:\n" << (*SExt) << '\n');0
428
0
429
0
      // Cases where we actually perform the optimization:
430
0
      // 1. SExt is used in a getelementptr with more than 2 operand =>
431
0
      //    likely we can merge some computation if they are done on 64 bits.
432
0
      // 2. The beginning of the SExt chain is SExt several time. =>
433
0
      //    code sharing is possible.
434
0
435
0
      bool insert = false;
436
0
      // #1.
437
0
      for (const User *U : SExt->users()) {
438
0
        const Instruction *Inst = dyn_cast<GetElementPtrInst>(U);
439
0
        if (
Inst && 0
Inst->getNumOperands() > 20
)
{0
440
0
          DEBUG(dbgs() << "Interesting use in GetElementPtrInst\n" << *Inst
441
0
                       << '\n');
442
0
          insert = true;
443
0
          break;
444
0
        }
445
0
      }
446
0
447
0
      // #2.
448
0
      // Check the head of the chain.
449
0
      Instruction *Inst = SExt;
450
0
      Value *Last;
451
0
      do {
452
0
        int OpdIdx = 0;
453
0
        const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
454
0
        if (
BinOp && 0
isa<ConstantInt>(BinOp->getOperand(0))0
)
455
0
          OpdIdx = 1;
456
0
        Last = Inst->getOperand(OpdIdx);
457
0
        Inst = dyn_cast<Instruction>(Last);
458
0
      } while (
Inst && 0
canGetThrough(Inst)0
&&
shouldGetThrough(Inst)0
);
459
0
460
0
      DEBUG(dbgs() << "Head of the chain:\n" << *Last << '\n');
461
0
      DenseMap<Value *, Instruction *>::iterator AlreadySeen =
462
0
          SeenChains.find(Last);
463
0
      if (
insert || 0
AlreadySeen != SeenChains.end()0
)
{0
464
0
        DEBUG(dbgs() << "Insert\n");
465
0
        SExtInsts.push_back(SExt);
466
0
        if (
AlreadySeen != SeenChains.end() && 0
AlreadySeen->second != nullptr0
)
{0
467
0
          DEBUG(dbgs() << "Insert chain member\n");
468
0
          SExtInsts.push_back(AlreadySeen->second);
469
0
          SeenChains[Last] = nullptr;
470
0
        }
471
0
      } else {
472
0
        DEBUG(dbgs() << "Record its chain membership\n");
473
0
        SeenChains[Last] = SExt;
474
0
      }
475
0
    }
476
0
  }
477
0
}
478
479
0
bool AArch64AddressTypePromotion::runOnFunction(Function &F) {
480
0
  if (skipFunction(F))
481
0
    return false;
482
0
483
0
  
if (0
F.isDeclaration()0
)
484
0
    return false;
485
0
  Func = &F;
486
0
  ConsideredSExtType = Type::getInt64Ty(Func->getContext());
487
0
488
0
  DEBUG(dbgs() << "*** " << getPassName() << ": " << Func->getName() << '\n');
489
0
490
0
  Instructions SExtInsts;
491
0
  analyzeSExtension(SExtInsts);
492
0
  return propagateSignExtension(SExtInsts);
493
0
}