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