LLVM  13.0.0git
TypePromotion.cpp
Go to the documentation of this file.
1 //===----- TypePromotion.cpp ----------------------------------------------===//
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 /// \file
10 /// This is an opcode based type promotion pass for small types that would
11 /// otherwise be promoted during legalisation. This works around the limitations
12 /// of selection dag for cyclic regions. The search begins from icmp
13 /// instructions operands where a tree, consisting of non-wrapping or safe
14 /// wrapping instructions, is built, checked and promoted if possible.
15 ///
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/StringRef.h"
21 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/IR/Attributes.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/IR/IntrinsicsARM.h"
36 #include "llvm/IR/Type.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/IR/Verifier.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
44 
45 #define DEBUG_TYPE "type-promotion"
46 #define PASS_NAME "Type Promotion"
47 
48 using namespace llvm;
49 
50 static cl::opt<bool>
51 DisablePromotion("disable-type-promotion", cl::Hidden, cl::init(false),
52  cl::desc("Disable type promotion pass"));
53 
54 // The goal of this pass is to enable more efficient code generation for
55 // operations on narrow types (i.e. types with < 32-bits) and this is a
56 // motivating IR code example:
57 //
58 // define hidden i32 @cmp(i8 zeroext) {
59 // %2 = add i8 %0, -49
60 // %3 = icmp ult i8 %2, 3
61 // ..
62 // }
63 //
64 // The issue here is that i8 is type-legalized to i32 because i8 is not a
65 // legal type. Thus, arithmetic is done in integer-precision, but then the
66 // byte value is masked out as follows:
67 //
68 // t19: i32 = add t4, Constant:i32<-49>
69 // t24: i32 = and t19, Constant:i32<255>
70 //
71 // Consequently, we generate code like this:
72 //
73 // subs r0, #49
74 // uxtb r1, r0
75 // cmp r1, #3
76 //
77 // This shows that masking out the byte value results in generation of
78 // the UXTB instruction. This is not optimal as r0 already contains the byte
79 // value we need, and so instead we can just generate:
80 //
81 // sub.w r1, r0, #49
82 // cmp r1, #3
83 //
84 // We achieve this by type promoting the IR to i32 like so for this example:
85 //
86 // define i32 @cmp(i8 zeroext %c) {
87 // %0 = zext i8 %c to i32
88 // %c.off = add i32 %0, -49
89 // %1 = icmp ult i32 %c.off, 3
90 // ..
91 // }
92 //
93 // For this to be valid and legal, we need to prove that the i32 add is
94 // producing the same value as the i8 addition, and that e.g. no overflow
95 // happens.
96 //
97 // A brief sketch of the algorithm and some terminology.
98 // We pattern match interesting IR patterns:
99 // - which have "sources": instructions producing narrow values (i8, i16), and
100 // - they have "sinks": instructions consuming these narrow values.
101 //
102 // We collect all instruction connecting sources and sinks in a worklist, so
103 // that we can mutate these instruction and perform type promotion when it is
104 // legal to do so.
105 
106 namespace {
107 class IRPromoter {
108  LLVMContext &Ctx;
109  IntegerType *OrigTy = nullptr;
110  unsigned PromotedWidth = 0;
111  SetVector<Value*> &Visited;
112  SetVector<Value*> &Sources;
115  IntegerType *ExtTy = nullptr;
116  SmallPtrSet<Value*, 8> NewInsts;
117  SmallPtrSet<Instruction*, 4> InstsToRemove;
119  SmallPtrSet<Value*, 8> Promoted;
120 
121  void ReplaceAllUsersOfWith(Value *From, Value *To);
122  void PrepareWrappingAdds(void);
123  void ExtendSources(void);
124  void ConvertTruncs(void);
125  void PromoteTree(void);
126  void TruncateSinks(void);
127  void Cleanup(void);
128 
129 public:
130  IRPromoter(LLVMContext &C, IntegerType *Ty, unsigned Width,
131  SetVector<Value*> &visited, SetVector<Value*> &sources,
134  Ctx(C), OrigTy(Ty), PromotedWidth(Width), Visited(visited),
135  Sources(sources), Sinks(sinks), SafeWrap(wrap) {
136  ExtTy = IntegerType::get(Ctx, PromotedWidth);
139  "Original type not smaller than extended type");
140  }
141 
142  void Mutate();
143 };
144 
145 class TypePromotion : public FunctionPass {
146  unsigned TypeSize = 0;
147  LLVMContext *Ctx = nullptr;
148  unsigned RegisterBitWidth = 0;
149  SmallPtrSet<Value*, 16> AllVisited;
150  SmallPtrSet<Instruction*, 8> SafeToPromote;
152 
153  // Does V have the same size result type as TypeSize.
154  bool EqualTypeSize(Value *V);
155  // Does V have the same size, or narrower, result type as TypeSize.
156  bool LessOrEqualTypeSize(Value *V);
157  // Does V have a result type that is wider than TypeSize.
158  bool GreaterThanTypeSize(Value *V);
159  // Does V have a result type that is narrower than TypeSize.
160  bool LessThanTypeSize(Value *V);
161  // Should V be a leaf in the promote tree?
162  bool isSource(Value *V);
163  // Should V be a root in the promotion tree?
164  bool isSink(Value *V);
165  // Should we change the result type of V? It will result in the users of V
166  // being visited.
167  bool shouldPromote(Value *V);
168  // Is I an add or a sub, which isn't marked as nuw, but where a wrapping
169  // result won't affect the computation?
170  bool isSafeWrap(Instruction *I);
171  // Can V have its integer type promoted, or can the type be ignored.
172  bool isSupportedType(Value *V);
173  // Is V an instruction with a supported opcode or another value that we can
174  // handle, such as constants and basic blocks.
175  bool isSupportedValue(Value *V);
176  // Is V an instruction thats result can trivially promoted, or has safe
177  // wrapping.
178  bool isLegalToPromote(Value *V);
179  bool TryToPromote(Value *V, unsigned PromotedWidth);
180 
181 public:
182  static char ID;
183 
184  TypePromotion() : FunctionPass(ID) {}
185 
186  void getAnalysisUsage(AnalysisUsage &AU) const override {
189  }
190 
191  StringRef getPassName() const override { return PASS_NAME; }
192 
193  bool runOnFunction(Function &F) override;
194 };
195 
196 }
197 
198 static bool GenerateSignBits(Value *V) {
199  if (!isa<Instruction>(V))
200  return false;
201 
202  unsigned Opc = cast<Instruction>(V)->getOpcode();
203  return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
204  Opc == Instruction::SRem || Opc == Instruction::SExt;
205 }
206 
207 bool TypePromotion::EqualTypeSize(Value *V) {
208  return V->getType()->getScalarSizeInBits() == TypeSize;
209 }
210 
211 bool TypePromotion::LessOrEqualTypeSize(Value *V) {
212  return V->getType()->getScalarSizeInBits() <= TypeSize;
213 }
214 
215 bool TypePromotion::GreaterThanTypeSize(Value *V) {
216  return V->getType()->getScalarSizeInBits() > TypeSize;
217 }
218 
219 bool TypePromotion::LessThanTypeSize(Value *V) {
220  return V->getType()->getScalarSizeInBits() < TypeSize;
221 }
222 
223 /// Return true if the given value is a source in the use-def chain, producing
224 /// a narrow 'TypeSize' value. These values will be zext to start the promotion
225 /// of the tree to i32. We guarantee that these won't populate the upper bits
226 /// of the register. ZExt on the loads will be free, and the same for call
227 /// return values because we only accept ones that guarantee a zeroext ret val.
228 /// Many arguments will have the zeroext attribute too, so those would be free
229 /// too.
230 bool TypePromotion::isSource(Value *V) {
231  if (!isa<IntegerType>(V->getType()))
232  return false;
233 
234  // TODO Allow zext to be sources.
235  if (isa<Argument>(V))
236  return true;
237  else if (isa<LoadInst>(V))
238  return true;
239  else if (isa<BitCastInst>(V))
240  return true;
241  else if (auto *Call = dyn_cast<CallInst>(V))
242  return Call->hasRetAttr(Attribute::AttrKind::ZExt);
243  else if (auto *Trunc = dyn_cast<TruncInst>(V))
244  return EqualTypeSize(Trunc);
245  return false;
246 }
247 
248 /// Return true if V will require any promoted values to be truncated for the
249 /// the IR to remain valid. We can't mutate the value type of these
250 /// instructions.
251 bool TypePromotion::isSink(Value *V) {
252  // TODO The truncate also isn't actually necessary because we would already
253  // proved that the data value is kept within the range of the original data
254  // type.
255 
256  // Sinks are:
257  // - points where the value in the register is being observed, such as an
258  // icmp, switch or store.
259  // - points where value types have to match, such as calls and returns.
260  // - zext are included to ease the transformation and are generally removed
261  // later on.
262  if (auto *Store = dyn_cast<StoreInst>(V))
263  return LessOrEqualTypeSize(Store->getValueOperand());
264  if (auto *Return = dyn_cast<ReturnInst>(V))
265  return LessOrEqualTypeSize(Return->getReturnValue());
266  if (auto *ZExt = dyn_cast<ZExtInst>(V))
267  return GreaterThanTypeSize(ZExt);
268  if (auto *Switch = dyn_cast<SwitchInst>(V))
269  return LessThanTypeSize(Switch->getCondition());
270  if (auto *ICmp = dyn_cast<ICmpInst>(V))
271  return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
272 
273  return isa<CallInst>(V);
274 }
275 
276 /// Return whether this instruction can safely wrap.
277 bool TypePromotion::isSafeWrap(Instruction *I) {
278  // We can support a, potentially, wrapping instruction (I) if:
279  // - It is only used by an unsigned icmp.
280  // - The icmp uses a constant.
281  // - The wrapping value (I) is decreasing, i.e would underflow - wrapping
282  // around zero to become a larger number than before.
283  // - The wrapping instruction (I) also uses a constant.
284  //
285  // We can then use the two constants to calculate whether the result would
286  // wrap in respect to itself in the original bitwidth. If it doesn't wrap,
287  // just underflows the range, the icmp would give the same result whether the
288  // result has been truncated or not. We calculate this by:
289  // - Zero extending both constants, if needed, to 32-bits.
290  // - Take the absolute value of I's constant, adding this to the icmp const.
291  // - Check that this value is not out of range for small type. If it is, it
292  // means that it has underflowed enough to wrap around the icmp constant.
293  //
294  // For example:
295  //
296  // %sub = sub i8 %a, 2
297  // %cmp = icmp ule i8 %sub, 254
298  //
299  // If %a = 0, %sub = -2 == FE == 254
300  // But if this is evalulated as a i32
301  // %sub = -2 == FF FF FF FE == 4294967294
302  // So the unsigned compares (i8 and i32) would not yield the same result.
303  //
304  // Another way to look at it is:
305  // %a - 2 <= 254
306  // %a + 2 <= 254 + 2
307  // %a <= 256
308  // And we can't represent 256 in the i8 format, so we don't support it.
309  //
310  // Whereas:
311  //
312  // %sub i8 %a, 1
313  // %cmp = icmp ule i8 %sub, 254
314  //
315  // If %a = 0, %sub = -1 == FF == 255
316  // As i32:
317  // %sub = -1 == FF FF FF FF == 4294967295
318  //
319  // In this case, the unsigned compare results would be the same and this
320  // would also be true for ult, uge and ugt:
321  // - (255 < 254) == (0xFFFFFFFF < 254) == false
322  // - (255 <= 254) == (0xFFFFFFFF <= 254) == false
323  // - (255 > 254) == (0xFFFFFFFF > 254) == true
324  // - (255 >= 254) == (0xFFFFFFFF >= 254) == true
325  //
326  // To demonstrate why we can't handle increasing values:
327  //
328  // %add = add i8 %a, 2
329  // %cmp = icmp ult i8 %add, 127
330  //
331  // If %a = 254, %add = 256 == (i8 1)
332  // As i32:
333  // %add = 256
334  //
335  // (1 < 127) != (256 < 127)
336 
337  unsigned Opc = I->getOpcode();
338  if (Opc != Instruction::Add && Opc != Instruction::Sub)
339  return false;
340 
341  if (!I->hasOneUse() ||
342  !isa<ICmpInst>(*I->user_begin()) ||
343  !isa<ConstantInt>(I->getOperand(1)))
344  return false;
345 
346  ConstantInt *OverflowConst = cast<ConstantInt>(I->getOperand(1));
347  bool NegImm = OverflowConst->isNegative();
348  bool IsDecreasing = ((Opc == Instruction::Sub) && !NegImm) ||
349  ((Opc == Instruction::Add) && NegImm);
350  if (!IsDecreasing)
351  return false;
352 
353  // Don't support an icmp that deals with sign bits.
354  auto *CI = cast<ICmpInst>(*I->user_begin());
355  if (CI->isSigned() || CI->isEquality())
356  return false;
357 
358  ConstantInt *ICmpConst = nullptr;
359  if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
360  ICmpConst = Const;
361  else if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
362  ICmpConst = Const;
363  else
364  return false;
365 
366  // Now check that the result can't wrap on itself.
367  APInt Total = ICmpConst->getValue().getBitWidth() < 32 ?
368  ICmpConst->getValue().zext(32) : ICmpConst->getValue();
369 
370  Total += OverflowConst->getValue().getBitWidth() < 32 ?
371  OverflowConst->getValue().abs().zext(32) : OverflowConst->getValue().abs();
372 
373  APInt Max = APInt::getAllOnesValue(TypePromotion::TypeSize);
374 
375  if (Total.getBitWidth() > Max.getBitWidth()) {
376  if (Total.ugt(Max.zext(Total.getBitWidth())))
377  return false;
378  } else if (Max.getBitWidth() > Total.getBitWidth()) {
379  if (Total.zext(Max.getBitWidth()).ugt(Max))
380  return false;
381  } else if (Total.ugt(Max))
382  return false;
383 
384  LLVM_DEBUG(dbgs() << "IR Promotion: Allowing safe overflow for "
385  << *I << "\n");
386  SafeWrap.push_back(I);
387  return true;
388 }
389 
390 bool TypePromotion::shouldPromote(Value *V) {
391  if (!isa<IntegerType>(V->getType()) || isSink(V))
392  return false;
393 
394  if (isSource(V))
395  return true;
396 
397  auto *I = dyn_cast<Instruction>(V);
398  if (!I)
399  return false;
400 
401  if (isa<ICmpInst>(I))
402  return false;
403 
404  return true;
405 }
406 
407 /// Return whether we can safely mutate V's type to ExtTy without having to be
408 /// concerned with zero extending or truncation.
409 static bool isPromotedResultSafe(Value *V) {
410  if (GenerateSignBits(V))
411  return false;
412 
413  if (!isa<Instruction>(V))
414  return true;
415 
416  if (!isa<OverflowingBinaryOperator>(V))
417  return true;
418 
419  return cast<Instruction>(V)->hasNoUnsignedWrap();
420 }
421 
422 void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) {
424  Instruction *InstTo = dyn_cast<Instruction>(To);
425  bool ReplacedAll = true;
426 
427  LLVM_DEBUG(dbgs() << "IR Promotion: Replacing " << *From << " with " << *To
428  << "\n");
429 
430  for (Use &U : From->uses()) {
431  auto *User = cast<Instruction>(U.getUser());
432  if (InstTo && User->isIdenticalTo(InstTo)) {
433  ReplacedAll = false;
434  continue;
435  }
436  Users.push_back(User);
437  }
438 
439  for (auto *U : Users)
440  U->replaceUsesOfWith(From, To);
441 
442  if (ReplacedAll)
443  if (auto *I = dyn_cast<Instruction>(From))
444  InstsToRemove.insert(I);
445 }
446 
447 void IRPromoter::PrepareWrappingAdds() {
448  LLVM_DEBUG(dbgs() << "IR Promotion: Prepare wrapping adds.\n");
449  IRBuilder<> Builder{Ctx};
450 
451  // For adds that safely wrap and use a negative immediate as operand 1, we
452  // create an equivalent instruction using a positive immediate.
453  // That positive immediate can then be zext along with all the other
454  // immediates later.
455  for (auto *I : SafeWrap) {
456  if (I->getOpcode() != Instruction::Add)
457  continue;
458 
459  LLVM_DEBUG(dbgs() << "IR Promotion: Adjusting " << *I << "\n");
460  assert((isa<ConstantInt>(I->getOperand(1)) &&
461  cast<ConstantInt>(I->getOperand(1))->isNegative()) &&
462  "Wrapping should have a negative immediate as the second operand");
463 
464  auto Const = cast<ConstantInt>(I->getOperand(1));
465  auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs());
466  Builder.SetInsertPoint(I);
467  Value *NewVal = Builder.CreateSub(I->getOperand(0), NewConst);
468  if (auto *NewInst = dyn_cast<Instruction>(NewVal)) {
469  NewInst->copyIRFlags(I);
470  NewInsts.insert(NewInst);
471  }
472  InstsToRemove.insert(I);
473  I->replaceAllUsesWith(NewVal);
474  LLVM_DEBUG(dbgs() << "IR Promotion: New equivalent: " << *NewVal << "\n");
475  }
476  for (auto *I : NewInsts)
477  Visited.insert(I);
478 }
479 
480 void IRPromoter::ExtendSources() {
481  IRBuilder<> Builder{Ctx};
482 
483  auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
484  assert(V->getType() != ExtTy && "zext already extends to i32");
485  LLVM_DEBUG(dbgs() << "IR Promotion: Inserting ZExt for " << *V << "\n");
486  Builder.SetInsertPoint(InsertPt);
487  if (auto *I = dyn_cast<Instruction>(V))
488  Builder.SetCurrentDebugLocation(I->getDebugLoc());
489 
490  Value *ZExt = Builder.CreateZExt(V, ExtTy);
491  if (auto *I = dyn_cast<Instruction>(ZExt)) {
492  if (isa<Argument>(V))
493  I->moveBefore(InsertPt);
494  else
495  I->moveAfter(InsertPt);
496  NewInsts.insert(I);
497  }
498 
499  ReplaceAllUsersOfWith(V, ZExt);
500  };
501 
502  // Now, insert extending instructions between the sources and their users.
503  LLVM_DEBUG(dbgs() << "IR Promotion: Promoting sources:\n");
504  for (auto V : Sources) {
505  LLVM_DEBUG(dbgs() << " - " << *V << "\n");
506  if (auto *I = dyn_cast<Instruction>(V))
507  InsertZExt(I, I);
508  else if (auto *Arg = dyn_cast<Argument>(V)) {
509  BasicBlock &BB = Arg->getParent()->front();
510  InsertZExt(Arg, &*BB.getFirstInsertionPt());
511  } else {
512  llvm_unreachable("unhandled source that needs extending");
513  }
514  Promoted.insert(V);
515  }
516 }
517 
518 void IRPromoter::PromoteTree() {
519  LLVM_DEBUG(dbgs() << "IR Promotion: Mutating the tree..\n");
520 
521  IRBuilder<> Builder{Ctx};
522 
523  // Mutate the types of the instructions within the tree. Here we handle
524  // constant operands.
525  for (auto *V : Visited) {
526  if (Sources.count(V))
527  continue;
528 
529  auto *I = cast<Instruction>(V);
530  if (Sinks.count(I))
531  continue;
532 
533  for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
534  Value *Op = I->getOperand(i);
535  if ((Op->getType() == ExtTy) || !isa<IntegerType>(Op->getType()))
536  continue;
537 
538  if (auto *Const = dyn_cast<ConstantInt>(Op)) {
539  Constant *NewConst = ConstantExpr::getZExt(Const, ExtTy);
540  I->setOperand(i, NewConst);
541  } else if (isa<UndefValue>(Op))
542  I->setOperand(i, UndefValue::get(ExtTy));
543  }
544 
545  // Mutate the result type, unless this is an icmp.
546  if (!isa<ICmpInst>(I)) {
547  I->mutateType(ExtTy);
548  Promoted.insert(I);
549  }
550  }
551 }
552 
553 void IRPromoter::TruncateSinks() {
554  LLVM_DEBUG(dbgs() << "IR Promotion: Fixing up the sinks:\n");
555 
556  IRBuilder<> Builder{Ctx};
557 
558  auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction* {
559  if (!isa<Instruction>(V) || !isa<IntegerType>(V->getType()))
560  return nullptr;
561 
562  if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))
563  return nullptr;
564 
565  LLVM_DEBUG(dbgs() << "IR Promotion: Creating " << *TruncTy << " Trunc for "
566  << *V << "\n");
567  Builder.SetInsertPoint(cast<Instruction>(V));
568  auto *Trunc = dyn_cast<Instruction>(Builder.CreateTrunc(V, TruncTy));
569  if (Trunc)
570  NewInsts.insert(Trunc);
571  return Trunc;
572  };
573 
574  // Fix up any stores or returns that use the results of the promoted
575  // chain.
576  for (auto I : Sinks) {
577  LLVM_DEBUG(dbgs() << "IR Promotion: For Sink: " << *I << "\n");
578 
579  // Handle calls separately as we need to iterate over arg operands.
580  if (auto *Call = dyn_cast<CallInst>(I)) {
581  for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
582  Value *Arg = Call->getArgOperand(i);
583  Type *Ty = TruncTysMap[Call][i];
584  if (Instruction *Trunc = InsertTrunc(Arg, Ty)) {
585  Trunc->moveBefore(Call);
586  Call->setArgOperand(i, Trunc);
587  }
588  }
589  continue;
590  }
591 
592  // Special case switches because we need to truncate the condition.
593  if (auto *Switch = dyn_cast<SwitchInst>(I)) {
594  Type *Ty = TruncTysMap[Switch][0];
595  if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) {
596  Trunc->moveBefore(Switch);
597  Switch->setCondition(Trunc);
598  }
599  continue;
600  }
601 
602  // Now handle the others.
603  for (unsigned i = 0; i < I->getNumOperands(); ++i) {
604  Type *Ty = TruncTysMap[I][i];
605  if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) {
606  Trunc->moveBefore(I);
607  I->setOperand(i, Trunc);
608  }
609  }
610  }
611 }
612 
613 void IRPromoter::Cleanup() {
614  LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n");
615  // Some zexts will now have become redundant, along with their trunc
616  // operands, so remove them
617  for (auto V : Visited) {
618  if (!isa<ZExtInst>(V))
619  continue;
620 
621  auto ZExt = cast<ZExtInst>(V);
622  if (ZExt->getDestTy() != ExtTy)
623  continue;
624 
625  Value *Src = ZExt->getOperand(0);
626  if (ZExt->getSrcTy() == ZExt->getDestTy()) {
627  LLVM_DEBUG(dbgs() << "IR Promotion: Removing unnecessary cast: " << *ZExt
628  << "\n");
629  ReplaceAllUsersOfWith(ZExt, Src);
630  continue;
631  }
632 
633  // Unless they produce a value that is narrower than ExtTy, we can
634  // replace the result of the zext with the input of a newly inserted
635  // trunc.
636  if (NewInsts.count(Src) && isa<TruncInst>(Src) &&
637  Src->getType() == OrigTy) {
638  auto *Trunc = cast<TruncInst>(Src);
639  assert(Trunc->getOperand(0)->getType() == ExtTy &&
640  "expected inserted trunc to be operating on i32");
641  ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));
642  }
643  }
644 
645  for (auto *I : InstsToRemove) {
646  LLVM_DEBUG(dbgs() << "IR Promotion: Removing " << *I << "\n");
647  I->dropAllReferences();
648  I->eraseFromParent();
649  }
650 }
651 
652 void IRPromoter::ConvertTruncs() {
653  LLVM_DEBUG(dbgs() << "IR Promotion: Converting truncs..\n");
654  IRBuilder<> Builder{Ctx};
655 
656  for (auto *V : Visited) {
657  if (!isa<TruncInst>(V) || Sources.count(V))
658  continue;
659 
660  auto *Trunc = cast<TruncInst>(V);
661  Builder.SetInsertPoint(Trunc);
662  IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());
663  IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);
664 
665  unsigned NumBits = DestTy->getScalarSizeInBits();
666  ConstantInt *Mask =
667  ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue());
668  Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask);
669 
670  if (auto *I = dyn_cast<Instruction>(Masked))
671  NewInsts.insert(I);
672 
673  ReplaceAllUsersOfWith(Trunc, Masked);
674  }
675 }
676 
677 void IRPromoter::Mutate() {
678  LLVM_DEBUG(dbgs() << "IR Promotion: Promoting use-def chains from "
679  << OrigTy->getBitWidth() << " to " << PromotedWidth << "-bits\n");
680 
681  // Cache original types of the values that will likely need truncating
682  for (auto *I : Sinks) {
683  if (auto *Call = dyn_cast<CallInst>(I)) {
684  for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
685  Value *Arg = Call->getArgOperand(i);
686  TruncTysMap[Call].push_back(Arg->getType());
687  }
688  } else if (auto *Switch = dyn_cast<SwitchInst>(I))
689  TruncTysMap[I].push_back(Switch->getCondition()->getType());
690  else {
691  for (unsigned i = 0; i < I->getNumOperands(); ++i)
692  TruncTysMap[I].push_back(I->getOperand(i)->getType());
693  }
694  }
695  for (auto *V : Visited) {
696  if (!isa<TruncInst>(V) || Sources.count(V))
697  continue;
698  auto *Trunc = cast<TruncInst>(V);
699  TruncTysMap[Trunc].push_back(Trunc->getDestTy());
700  }
701 
702  // Convert adds using negative immediates to equivalent instructions that use
703  // positive constants.
704  PrepareWrappingAdds();
705 
706  // Insert zext instructions between sources and their users.
707  ExtendSources();
708 
709  // Promote visited instructions, mutating their types in place.
710  PromoteTree();
711 
712  // Convert any truncs, that aren't sources, into AND masks.
713  ConvertTruncs();
714 
715  // Insert trunc instructions for use by calls, stores etc...
716  TruncateSinks();
717 
718  // Finally, remove unecessary zexts and truncs, delete old instructions and
719  // clear the data structures.
720  Cleanup();
721 
722  LLVM_DEBUG(dbgs() << "IR Promotion: Mutation complete\n");
723 }
724 
725 /// We disallow booleans to make life easier when dealing with icmps but allow
726 /// any other integer that fits in a scalar register. Void types are accepted
727 /// so we can handle switches.
729  Type *Ty = V->getType();
730 
731  // Allow voids and pointers, these won't be promoted.
732  if (Ty->isVoidTy() || Ty->isPointerTy())
733  return true;
734 
735  if (!isa<IntegerType>(Ty) ||
736  cast<IntegerType>(Ty)->getBitWidth() == 1 ||
737  cast<IntegerType>(Ty)->getBitWidth() > RegisterBitWidth)
738  return false;
739 
740  return LessOrEqualTypeSize(V);
741 }
742 
743 /// We accept most instructions, as well as Arguments and ConstantInsts. We
744 /// Disallow casts other than zext and truncs and only allow calls if their
745 /// return value is zeroext. We don't allow opcodes that can introduce sign
746 /// bits.
747 bool TypePromotion::isSupportedValue(Value *V) {
748  if (auto *I = dyn_cast<Instruction>(V)) {
749  switch (I->getOpcode()) {
750  default:
751  return isa<BinaryOperator>(I) && isSupportedType(I) &&
753  case Instruction::GetElementPtr:
754  case Instruction::Store:
755  case Instruction::Br:
756  case Instruction::Switch:
757  return true;
758  case Instruction::PHI:
759  case Instruction::Select:
760  case Instruction::Ret:
761  case Instruction::Load:
762  case Instruction::Trunc:
763  case Instruction::BitCast:
764  return isSupportedType(I);
765  case Instruction::ZExt:
766  return isSupportedType(I->getOperand(0));
767  case Instruction::ICmp:
768  // Now that we allow small types than TypeSize, only allow icmp of
769  // TypeSize because they will require a trunc to be legalised.
770  // TODO: Allow icmp of smaller types, and calculate at the end
771  // whether the transform would be beneficial.
772  if (isa<PointerType>(I->getOperand(0)->getType()))
773  return true;
774  return EqualTypeSize(I->getOperand(0));
775  case Instruction::Call: {
776  // Special cases for calls as we need to check for zeroext
777  // TODO We should accept calls even if they don't have zeroext, as they
778  // can still be sinks.
779  auto *Call = cast<CallInst>(I);
780  return isSupportedType(Call) &&
781  Call->hasRetAttr(Attribute::AttrKind::ZExt);
782  }
783  }
784  } else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
785  return isSupportedType(V);
786  } else if (isa<Argument>(V))
787  return isSupportedType(V);
788 
789  return isa<BasicBlock>(V);
790 }
791 
792 /// Check that the type of V would be promoted and that the original type is
793 /// smaller than the targeted promoted type. Check that we're not trying to
794 /// promote something larger than our base 'TypeSize' type.
796 
797  auto *I = dyn_cast<Instruction>(V);
798  if (!I)
799  return true;
800 
801  if (SafeToPromote.count(I))
802  return true;
803 
804  if (isPromotedResultSafe(V) || isSafeWrap(I)) {
805  SafeToPromote.insert(I);
806  return true;
807  }
808  return false;
809 }
810 
811 bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) {
812  Type *OrigTy = V->getType();
814  SafeToPromote.clear();
815  SafeWrap.clear();
816 
817  if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
818  return false;
819 
820  LLVM_DEBUG(dbgs() << "IR Promotion: TryToPromote: " << *V << ", from "
821  << TypeSize << " bits to " << PromotedWidth << "\n");
822 
823  SetVector<Value*> WorkList;
824  SetVector<Value*> Sources;
826  SetVector<Value*> CurrentVisited;
827  WorkList.insert(V);
828 
829  // Return true if V was added to the worklist as a supported instruction,
830  // if it was already visited, or if we don't need to explore it (e.g.
831  // pointer values and GEPs), and false otherwise.
832  auto AddLegalInst = [&](Value *V) {
833  if (CurrentVisited.count(V))
834  return true;
835 
836  // Ignore GEPs because they don't need promoting and the constant indices
837  // will prevent the transformation.
838  if (isa<GetElementPtrInst>(V))
839  return true;
840 
841  if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
842  LLVM_DEBUG(dbgs() << "IR Promotion: Can't handle: " << *V << "\n");
843  return false;
844  }
845 
846  WorkList.insert(V);
847  return true;
848  };
849 
850  // Iterate through, and add to, a tree of operands and users in the use-def.
851  while (!WorkList.empty()) {
852  Value *V = WorkList.pop_back_val();
853  if (CurrentVisited.count(V))
854  continue;
855 
856  // Ignore non-instructions, other than arguments.
857  if (!isa<Instruction>(V) && !isSource(V))
858  continue;
859 
860  // If we've already visited this value from somewhere, bail now because
861  // the tree has already been explored.
862  // TODO: This could limit the transform, ie if we try to promote something
863  // from an i8 and fail first, before trying an i16.
864  if (AllVisited.count(V))
865  return false;
866 
867  CurrentVisited.insert(V);
868  AllVisited.insert(V);
869 
870  // Calls can be both sources and sinks.
871  if (isSink(V))
872  Sinks.insert(cast<Instruction>(V));
873 
874  if (isSource(V))
875  Sources.insert(V);
876 
877  if (!isSink(V) && !isSource(V)) {
878  if (auto *I = dyn_cast<Instruction>(V)) {
879  // Visit operands of any instruction visited.
880  for (auto &U : I->operands()) {
881  if (!AddLegalInst(U))
882  return false;
883  }
884  }
885  }
886 
887  // Don't visit users of a node which isn't going to be mutated unless its a
888  // source.
889  if (isSource(V) || shouldPromote(V)) {
890  for (Use &U : V->uses()) {
891  if (!AddLegalInst(U.getUser()))
892  return false;
893  }
894  }
895  }
896 
897  LLVM_DEBUG(dbgs() << "IR Promotion: Visited nodes:\n";
898  for (auto *I : CurrentVisited)
899  I->dump();
900  );
901 
902  unsigned ToPromote = 0;
903  unsigned NonFreeArgs = 0;
905  for (auto *V : CurrentVisited) {
906  if (auto *I = dyn_cast<Instruction>(V))
907  Blocks.insert(I->getParent());
908 
909  if (Sources.count(V)) {
910  if (auto *Arg = dyn_cast<Argument>(V))
911  if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())
912  ++NonFreeArgs;
913  continue;
914  }
915 
916  if (Sinks.count(cast<Instruction>(V)))
917  continue;
918  ++ToPromote;
919  }
920 
921  // DAG optimizations should be able to handle these cases better, especially
922  // for function arguments.
923  if (ToPromote < 2 || (Blocks.size() == 1 && (NonFreeArgs > SafeWrap.size())))
924  return false;
925 
926  if (ToPromote < 2)
927  return false;
928 
929  IRPromoter Promoter(*Ctx, cast<IntegerType>(OrigTy), PromotedWidth,
930  CurrentVisited, Sources, Sinks, SafeWrap);
931  Promoter.Mutate();
932  return true;
933 }
934 
936  if (skipFunction(F) || DisablePromotion)
937  return false;
938 
939  LLVM_DEBUG(dbgs() << "IR Promotion: Running on " << F.getName() << "\n");
940 
941  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
942  if (!TPC)
943  return false;
944 
945  AllVisited.clear();
946  SafeToPromote.clear();
947  SafeWrap.clear();
948  bool MadeChange = false;
949  const DataLayout &DL = F.getParent()->getDataLayout();
950  const TargetMachine &TM = TPC->getTM<TargetMachine>();
951  const TargetSubtargetInfo *SubtargetInfo = TM.getSubtargetImpl(F);
952  const TargetLowering *TLI = SubtargetInfo->getTargetLowering();
953  const TargetTransformInfo &TII =
954  getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
955  RegisterBitWidth =
956  TII.getRegisterBitWidth(TargetTransformInfo::RGK_Scalar).getFixedSize();
957  Ctx = &F.getParent()->getContext();
958 
959  // Search up from icmps to try to promote their operands.
960  for (BasicBlock &BB : F) {
961  for (auto &I : BB) {
962  if (AllVisited.count(&I))
963  continue;
964 
965  if (!isa<ICmpInst>(&I))
966  continue;
967 
968  auto *ICmp = cast<ICmpInst>(&I);
969  // Skip signed or pointer compares
970  if (ICmp->isSigned() ||
971  !isa<IntegerType>(ICmp->getOperand(0)->getType()))
972  continue;
973 
974  LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n");
975 
976  for (auto &Op : ICmp->operands()) {
977  if (auto *I = dyn_cast<Instruction>(Op)) {
978  EVT SrcVT = TLI->getValueType(DL, I->getType());
979  if (SrcVT.isSimple() && TLI->isTypeLegal(SrcVT.getSimpleVT()))
980  break;
981 
982  if (TLI->getTypeAction(ICmp->getContext(), SrcVT) !=
984  break;
985  EVT PromotedVT = TLI->getTypeToTransformTo(ICmp->getContext(), SrcVT);
986  if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) {
987  LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register "
988  << "for promoted type\n");
989  break;
990  }
991 
992  MadeChange |= TryToPromote(I, PromotedVT.getFixedSizeInBits());
993  break;
994  }
995  }
996  }
997  LLVM_DEBUG(if (verifyFunction(F, &dbgs())) {
998  dbgs() << F;
999  report_fatal_error("Broken function after type promotion");
1000  });
1001  }
1002  if (MadeChange)
1003  LLVM_DEBUG(dbgs() << "After TypePromotion: " << F << "\n");
1004 
1005  AllVisited.clear();
1006  SafeToPromote.clear();
1007  SafeWrap.clear();
1008 
1009  return MadeChange;
1010 }
1011 
1012 INITIALIZE_PASS_BEGIN(TypePromotion, DEBUG_TYPE, PASS_NAME, false, false)
1014 
1015 char TypePromotion::ID = 0;
1016 
1018  return new TypePromotion();
1019 }
i
i
Definition: README.txt:29
isPromotedResultSafe
static bool isPromotedResultSafe(Value *V)
Return whether we can safely mutate V's type to ExtTy without having to be concerned with zero extend...
Definition: TypePromotion.cpp:409
PASS_NAME
#define PASS_NAME
Definition: TypePromotion.cpp:46
llvm
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:229
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2110
llvm::EVT::getFixedSizeInBits
uint64_t getFixedSizeInBits() const
Return the size of the specified fixed width value type in bits.
Definition: ValueTypes.h:341
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:426
llvm::Function
Definition: Function.h:61
StringRef.h
Pass.h
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:535
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::IRBuilder<>
llvm::TargetTransformInfo::RGK_Scalar
@ RGK_Scalar
Definition: TargetTransformInfo.h:929
llvm::verifyFunction
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:5782
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
DisablePromotion
static cl::opt< bool > DisablePromotion("disable-type-promotion", cl::Hidden, cl::init(false), cl::desc("Disable type promotion pass"))
llvm::coro::ABI::Switch
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1581
llvm::APInt::ugt
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1275
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
getBitWidth
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Definition: ValueTracking.cpp:88
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::EVT::isSimple
bool isSimple() const
Test if the given EVT is simple (as opposed to being extended).
Definition: ValueTypes.h:124
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
Instruction.h
CommandLine.h
TargetLowering.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
TargetMachine.h
Constants.h
llvm::User
Definition: User.h:44
llvm::EVT
Extended Value Type.
Definition: ValueTypes.h:35
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3158
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
false
Definition: StackSlotColoring.cpp:142
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MCID::Return
@ Return
Definition: MCInstrDesc.h:151
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:45
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:147
llvm::report_fatal_error
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1783
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:898
llvm::isLegalToPromote
bool isLegalToPromote(const CallBase &CB, Function *Callee, const char **FailureReason=nullptr)
Return true if the given indirect call site can be made to call Callee.
Definition: CallPromotionUtils.cpp:382
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
DEBUG_TYPE
#define DEBUG_TYPE
Definition: TypePromotion.cpp:45
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::TargetLoweringBase::getTypeToTransformTo
EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
Definition: TargetLowering.h:942
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
Passes.h
llvm::TargetPassConfig
Target-Independent Code Generator Pass Configuration Options.
Definition: TargetPassConfig.h:84
BasicBlock.h
llvm::cl::opt< bool >
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2376
llvm::TargetLoweringBase::isTypeLegal
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
Definition: TargetLowering.h:895
GenerateSignBits
static bool GenerateSignBits(Value *V)
Definition: TypePromotion.cpp:198
llvm::TargetLoweringBase::TypePromoteInteger
@ TypePromoteInteger
Definition: TargetLowering.h:207
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
TargetPassConfig.h
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::createTypePromotionPass
FunctionPass * createTypePromotionPass()
Create IR Type Promotion pass.
Definition: TypePromotion.cpp:1017
llvm::TargetMachine
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:77
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::wrap
LLVMAttributeRef wrap(Attribute Attr)
Definition: Attributes.h:239
llvm::APInt::getAllOnesValue
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:567
DataLayout.h
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:934
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
Attributes.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Verifier.h
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::TypeSize
Definition: TypeSize.h:417
Casting.h
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:403
llvm::codeview::ModifierOptions::Const
@ Const
llvm::APInt::abs
APInt abs() const
Get the absolute value;.
Definition: APInt.h:1870
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
Instructions.h
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
llvm::pdb::DbgHeaderType::Max
@ Max
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:187
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
TargetTransformInfo.h
llvm::SmallVectorImpl< Instruction * >
isSupportedType
static bool isSupportedType(const DataLayout &DL, const ARMTargetLowering &TLI, Type *T)
Definition: ARMCallLowering.cpp:55
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:269
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::cl::desc
Definition: CommandLine.h:414
llvm::TargetLoweringBase::getValueType
EVT getValueType(const DataLayout &DL, Type *Ty, bool AllowUnknown=false) const
Return the EVT corresponding to this LLVM type.
Definition: TargetLowering.h:1396
llvm::SetVector< Value * >
Value.h
InitializePasses.h
llvm::SetVector::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
SetVector.h
llvm::TargetLoweringBase::getTypeAction
LegalizeTypeAction getTypeAction(LLVMContext &Context, EVT VT) const
Return how we should legalize values of this type, either it is already legal (return 'Legal') or we ...
Definition: TargetLowering.h:929
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Type::getPrimitiveSizeInBits
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:122
llvm::EVT::getSimpleVT
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
Definition: ValueTypes.h:281
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38