LLVM  17.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 
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/CodeGen/Passes.h"
27 #include "llvm/IR/Attributes.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/Type.h"
35 #include "llvm/IR/Value.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> DisablePromotion("disable-type-promotion", cl::Hidden,
48  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  unsigned PromotedWidth = 0;
107  SetVector<Value *> &Visited;
108  SetVector<Value *> &Sources;
111  SmallPtrSetImpl<Instruction *> &InstsToRemove;
112  IntegerType *ExtTy = nullptr;
113  SmallPtrSet<Value *, 8> NewInsts;
115  SmallPtrSet<Value *, 8> Promoted;
116 
117  void ReplaceAllUsersOfWith(Value *From, Value *To);
118  void ExtendSources();
119  void ConvertTruncs();
120  void PromoteTree();
121  void TruncateSinks();
122  void Cleanup();
123 
124 public:
125  IRPromoter(LLVMContext &C, unsigned Width, SetVector<Value *> &visited,
128  SmallPtrSetImpl<Instruction *> &instsToRemove)
129  : Ctx(C), PromotedWidth(Width), Visited(visited), Sources(sources),
130  Sinks(sinks), SafeWrap(wrap), InstsToRemove(instsToRemove) {
131  ExtTy = IntegerType::get(Ctx, PromotedWidth);
132  }
133 
134  void Mutate();
135 };
136 
137 class TypePromotionImpl {
138  unsigned TypeSize = 0;
139  LLVMContext *Ctx = nullptr;
140  unsigned RegisterBitWidth = 0;
141  SmallPtrSet<Value *, 16> AllVisited;
142  SmallPtrSet<Instruction *, 8> SafeToPromote;
144  SmallPtrSet<Instruction *, 4> InstsToRemove;
145 
146  // Does V have the same size result type as TypeSize.
147  bool EqualTypeSize(Value *V);
148  // Does V have the same size, or narrower, result type as TypeSize.
149  bool LessOrEqualTypeSize(Value *V);
150  // Does V have a result type that is wider than TypeSize.
151  bool GreaterThanTypeSize(Value *V);
152  // Does V have a result type that is narrower than TypeSize.
153  bool LessThanTypeSize(Value *V);
154  // Should V be a leaf in the promote tree?
155  bool isSource(Value *V);
156  // Should V be a root in the promotion tree?
157  bool isSink(Value *V);
158  // Should we change the result type of V? It will result in the users of V
159  // being visited.
160  bool shouldPromote(Value *V);
161  // Is I an add or a sub, which isn't marked as nuw, but where a wrapping
162  // result won't affect the computation?
163  bool isSafeWrap(Instruction *I);
164  // Can V have its integer type promoted, or can the type be ignored.
165  bool isSupportedType(Value *V);
166  // Is V an instruction with a supported opcode or another value that we can
167  // handle, such as constants and basic blocks.
168  bool isSupportedValue(Value *V);
169  // Is V an instruction thats result can trivially promoted, or has safe
170  // wrapping.
171  bool isLegalToPromote(Value *V);
172  bool TryToPromote(Value *V, unsigned PromotedWidth, const LoopInfo &LI);
173 
174 public:
175  bool run(Function &F, const TargetMachine *TM,
176  const TargetTransformInfo &TTI, const LoopInfo &LI);
177 };
178 
179 class TypePromotionLegacy : public FunctionPass {
180 public:
181  static char ID;
182 
183  TypePromotionLegacy() : FunctionPass(ID) {}
184 
185  void getAnalysisUsage(AnalysisUsage &AU) const override {
189  AU.setPreservesCFG();
191  }
192 
193  StringRef getPassName() const override { return PASS_NAME; }
194 
195  bool runOnFunction(Function &F) override;
196 };
197 
198 } // namespace
199 
201  unsigned Opc = I->getOpcode();
202  return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
203  Opc == Instruction::SRem || Opc == Instruction::SExt;
204 }
205 
206 bool TypePromotionImpl::EqualTypeSize(Value *V) {
207  return V->getType()->getScalarSizeInBits() == TypeSize;
208 }
209 
210 bool TypePromotionImpl::LessOrEqualTypeSize(Value *V) {
211  return V->getType()->getScalarSizeInBits() <= TypeSize;
212 }
213 
214 bool TypePromotionImpl::GreaterThanTypeSize(Value *V) {
215  return V->getType()->getScalarSizeInBits() > TypeSize;
216 }
217 
218 bool TypePromotionImpl::LessThanTypeSize(Value *V) {
219  return V->getType()->getScalarSizeInBits() < TypeSize;
220 }
221 
222 /// Return true if the given value is a source in the use-def chain, producing
223 /// a narrow 'TypeSize' value. These values will be zext to start the promotion
224 /// of the tree to i32. We guarantee that these won't populate the upper bits
225 /// of the register. ZExt on the loads will be free, and the same for call
226 /// return values because we only accept ones that guarantee a zeroext ret val.
227 /// Many arguments will have the zeroext attribute too, so those would be free
228 /// too.
229 bool TypePromotionImpl::isSource(Value *V) {
230  if (!isa<IntegerType>(V->getType()))
231  return false;
232 
233  // TODO Allow zext to be sources.
234  if (isa<Argument>(V))
235  return true;
236  else if (isa<LoadInst>(V))
237  return true;
238  else if (isa<BitCastInst>(V))
239  return true;
240  else if (auto *Call = dyn_cast<CallInst>(V))
241  return Call->hasRetAttr(Attribute::AttrKind::ZExt);
242  else if (auto *Trunc = dyn_cast<TruncInst>(V))
243  return EqualTypeSize(Trunc);
244  return false;
245 }
246 
247 /// Return true if V will require any promoted values to be truncated for the
248 /// the IR to remain valid. We can't mutate the value type of these
249 /// instructions.
250 bool TypePromotionImpl::isSink(Value *V) {
251  // TODO The truncate also isn't actually necessary because we would already
252  // proved that the data value is kept within the range of the original data
253  // type. We currently remove any truncs inserted for handling zext sinks.
254 
255  // Sinks are:
256  // - points where the value in the register is being observed, such as an
257  // icmp, switch or store.
258  // - points where value types have to match, such as calls and returns.
259  // - zext are included to ease the transformation and are generally removed
260  // later on.
261  if (auto *Store = dyn_cast<StoreInst>(V))
262  return LessOrEqualTypeSize(Store->getValueOperand());
263  if (auto *Return = dyn_cast<ReturnInst>(V))
264  return LessOrEqualTypeSize(Return->getReturnValue());
265  if (auto *ZExt = dyn_cast<ZExtInst>(V))
266  return GreaterThanTypeSize(ZExt);
267  if (auto *Switch = dyn_cast<SwitchInst>(V))
268  return LessThanTypeSize(Switch->getCondition());
269  if (auto *ICmp = dyn_cast<ICmpInst>(V))
270  return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
271 
272  return isa<CallInst>(V);
273 }
274 
275 /// Return whether this instruction can safely wrap.
276 bool TypePromotionImpl::isSafeWrap(Instruction *I) {
277  // We can support a potentially wrapping instruction (I) if:
278  // - It is only used by an unsigned icmp.
279  // - The icmp uses a constant.
280  // - The wrapping value (I) is decreasing, i.e would underflow - wrapping
281  // around zero to become a larger number than before.
282  // - The wrapping instruction (I) also uses a constant.
283  //
284  // We can then use the two constants to calculate whether the result would
285  // wrap in respect to itself in the original bitwidth. If it doesn't wrap,
286  // just underflows the range, the icmp would give the same result whether the
287  // result has been truncated or not. We calculate this by:
288  // - Zero extending both constants, if needed, to RegisterBitWidth.
289  // - Take the absolute value of I's constant, adding this to the icmp const.
290  // - Check that this value is not out of range for small type. If it is, it
291  // means that it has underflowed enough to wrap around the icmp constant.
292  //
293  // For example:
294  //
295  // %sub = sub i8 %a, 2
296  // %cmp = icmp ule i8 %sub, 254
297  //
298  // If %a = 0, %sub = -2 == FE == 254
299  // But if this is evalulated as a i32
300  // %sub = -2 == FF FF FF FE == 4294967294
301  // So the unsigned compares (i8 and i32) would not yield the same result.
302  //
303  // Another way to look at it is:
304  // %a - 2 <= 254
305  // %a + 2 <= 254 + 2
306  // %a <= 256
307  // And we can't represent 256 in the i8 format, so we don't support it.
308  //
309  // Whereas:
310  //
311  // %sub i8 %a, 1
312  // %cmp = icmp ule i8 %sub, 254
313  //
314  // If %a = 0, %sub = -1 == FF == 255
315  // As i32:
316  // %sub = -1 == FF FF FF FF == 4294967295
317  //
318  // In this case, the unsigned compare results would be the same and this
319  // would also be true for ult, uge and ugt:
320  // - (255 < 254) == (0xFFFFFFFF < 254) == false
321  // - (255 <= 254) == (0xFFFFFFFF <= 254) == false
322  // - (255 > 254) == (0xFFFFFFFF > 254) == true
323  // - (255 >= 254) == (0xFFFFFFFF >= 254) == true
324  //
325  // To demonstrate why we can't handle increasing values:
326  //
327  // %add = add i8 %a, 2
328  // %cmp = icmp ult i8 %add, 127
329  //
330  // If %a = 254, %add = 256 == (i8 1)
331  // As i32:
332  // %add = 256
333  //
334  // (1 < 127) != (256 < 127)
335 
336  unsigned Opc = I->getOpcode();
337  if (Opc != Instruction::Add && Opc != Instruction::Sub)
338  return false;
339 
340  if (!I->hasOneUse() || !isa<ICmpInst>(*I->user_begin()) ||
341  !isa<ConstantInt>(I->getOperand(1)))
342  return false;
343 
344  // Don't support an icmp that deals with sign bits.
345  auto *CI = cast<ICmpInst>(*I->user_begin());
346  if (CI->isSigned() || CI->isEquality())
347  return false;
348 
349  ConstantInt *ICmpConstant = nullptr;
350  if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
351  ICmpConstant = Const;
352  else if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
353  ICmpConstant = Const;
354  else
355  return false;
356 
357  const APInt &ICmpConst = ICmpConstant->getValue();
358  APInt OverflowConst = cast<ConstantInt>(I->getOperand(1))->getValue();
359  if (Opc == Instruction::Sub)
360  OverflowConst = -OverflowConst;
361  if (!OverflowConst.isNonPositive())
362  return false;
363 
364  // Using C1 = OverflowConst and C2 = ICmpConst, we can either prove that:
365  // zext(x) + sext(C1) <u zext(C2) if C1 < 0 and C1 >s C2
366  // zext(x) + sext(C1) <u sext(C2) if C1 < 0 and C1 <=s C2
367  if (OverflowConst.sgt(ICmpConst)) {
368  LLVM_DEBUG(dbgs() << "IR Promotion: Allowing safe overflow for sext "
369  << "const of " << *I << "\n");
370  SafeWrap.insert(I);
371  return true;
372  } else {
373  LLVM_DEBUG(dbgs() << "IR Promotion: Allowing safe overflow for sext "
374  << "const of " << *I << " and " << *CI << "\n");
375  SafeWrap.insert(I);
376  SafeWrap.insert(CI);
377  return true;
378  }
379  return false;
380 }
381 
382 bool TypePromotionImpl::shouldPromote(Value *V) {
383  if (!isa<IntegerType>(V->getType()) || isSink(V))
384  return false;
385 
386  if (isSource(V))
387  return true;
388 
389  auto *I = dyn_cast<Instruction>(V);
390  if (!I)
391  return false;
392 
393  if (isa<ICmpInst>(I))
394  return false;
395 
396  return true;
397 }
398 
399 /// Return whether we can safely mutate V's type to ExtTy without having to be
400 /// concerned with zero extending or truncation.
402  if (GenerateSignBits(I))
403  return false;
404 
405  if (!isa<OverflowingBinaryOperator>(I))
406  return true;
407 
408  return I->hasNoUnsignedWrap();
409 }
410 
411 void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) {
413  Instruction *InstTo = dyn_cast<Instruction>(To);
414  bool ReplacedAll = true;
415 
416  LLVM_DEBUG(dbgs() << "IR Promotion: Replacing " << *From << " with " << *To
417  << "\n");
418 
419  for (Use &U : From->uses()) {
420  auto *User = cast<Instruction>(U.getUser());
421  if (InstTo && User->isIdenticalTo(InstTo)) {
422  ReplacedAll = false;
423  continue;
424  }
425  Users.push_back(User);
426  }
427 
428  for (auto *U : Users)
429  U->replaceUsesOfWith(From, To);
430 
431  if (ReplacedAll)
432  if (auto *I = dyn_cast<Instruction>(From))
433  InstsToRemove.insert(I);
434 }
435 
436 void IRPromoter::ExtendSources() {
437  IRBuilder<> Builder{Ctx};
438 
439  auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
440  assert(V->getType() != ExtTy && "zext already extends to i32");
441  LLVM_DEBUG(dbgs() << "IR Promotion: Inserting ZExt for " << *V << "\n");
442  Builder.SetInsertPoint(InsertPt);
443  if (auto *I = dyn_cast<Instruction>(V))
444  Builder.SetCurrentDebugLocation(I->getDebugLoc());
445 
446  Value *ZExt = Builder.CreateZExt(V, ExtTy);
447  if (auto *I = dyn_cast<Instruction>(ZExt)) {
448  if (isa<Argument>(V))
449  I->moveBefore(InsertPt);
450  else
451  I->moveAfter(InsertPt);
452  NewInsts.insert(I);
453  }
454 
455  ReplaceAllUsersOfWith(V, ZExt);
456  };
457 
458  // Now, insert extending instructions between the sources and their users.
459  LLVM_DEBUG(dbgs() << "IR Promotion: Promoting sources:\n");
460  for (auto *V : Sources) {
461  LLVM_DEBUG(dbgs() << " - " << *V << "\n");
462  if (auto *I = dyn_cast<Instruction>(V))
463  InsertZExt(I, I);
464  else if (auto *Arg = dyn_cast<Argument>(V)) {
465  BasicBlock &BB = Arg->getParent()->front();
466  InsertZExt(Arg, &*BB.getFirstInsertionPt());
467  } else {
468  llvm_unreachable("unhandled source that needs extending");
469  }
470  Promoted.insert(V);
471  }
472 }
473 
474 void IRPromoter::PromoteTree() {
475  LLVM_DEBUG(dbgs() << "IR Promotion: Mutating the tree..\n");
476 
477  // Mutate the types of the instructions within the tree. Here we handle
478  // constant operands.
479  for (auto *V : Visited) {
480  if (Sources.count(V))
481  continue;
482 
483  auto *I = cast<Instruction>(V);
484  if (Sinks.count(I))
485  continue;
486 
487  for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
488  Value *Op = I->getOperand(i);
489  if ((Op->getType() == ExtTy) || !isa<IntegerType>(Op->getType()))
490  continue;
491 
492  if (auto *Const = dyn_cast<ConstantInt>(Op)) {
493  // For subtract, we don't need to sext the constant. We only put it in
494  // SafeWrap because SafeWrap.size() is used elsewhere.
495  // For cmp, we need to sign extend a constant appearing in either
496  // operand. For add, we should only sign extend the RHS.
497  Constant *NewConst = (SafeWrap.contains(I) &&
498  (I->getOpcode() == Instruction::ICmp || i == 1) &&
499  I->getOpcode() != Instruction::Sub)
500  ? ConstantExpr::getSExt(Const, ExtTy)
501  : ConstantExpr::getZExt(Const, ExtTy);
502  I->setOperand(i, NewConst);
503  } else if (isa<UndefValue>(Op))
504  I->setOperand(i, ConstantInt::get(ExtTy, 0));
505  }
506 
507  // Mutate the result type, unless this is an icmp or switch.
508  if (!isa<ICmpInst>(I) && !isa<SwitchInst>(I)) {
509  I->mutateType(ExtTy);
510  Promoted.insert(I);
511  }
512  }
513 }
514 
515 void IRPromoter::TruncateSinks() {
516  LLVM_DEBUG(dbgs() << "IR Promotion: Fixing up the sinks:\n");
517 
518  IRBuilder<> Builder{Ctx};
519 
520  auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction * {
521  if (!isa<Instruction>(V) || !isa<IntegerType>(V->getType()))
522  return nullptr;
523 
524  if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))
525  return nullptr;
526 
527  LLVM_DEBUG(dbgs() << "IR Promotion: Creating " << *TruncTy << " Trunc for "
528  << *V << "\n");
529  Builder.SetInsertPoint(cast<Instruction>(V));
530  auto *Trunc = dyn_cast<Instruction>(Builder.CreateTrunc(V, TruncTy));
531  if (Trunc)
532  NewInsts.insert(Trunc);
533  return Trunc;
534  };
535 
536  // Fix up any stores or returns that use the results of the promoted
537  // chain.
538  for (auto *I : Sinks) {
539  LLVM_DEBUG(dbgs() << "IR Promotion: For Sink: " << *I << "\n");
540 
541  // Handle calls separately as we need to iterate over arg operands.
542  if (auto *Call = dyn_cast<CallInst>(I)) {
543  for (unsigned i = 0; i < Call->arg_size(); ++i) {
544  Value *Arg = Call->getArgOperand(i);
545  Type *Ty = TruncTysMap[Call][i];
546  if (Instruction *Trunc = InsertTrunc(Arg, Ty)) {
547  Trunc->moveBefore(Call);
548  Call->setArgOperand(i, Trunc);
549  }
550  }
551  continue;
552  }
553 
554  // Special case switches because we need to truncate the condition.
555  if (auto *Switch = dyn_cast<SwitchInst>(I)) {
556  Type *Ty = TruncTysMap[Switch][0];
557  if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) {
558  Trunc->moveBefore(Switch);
559  Switch->setCondition(Trunc);
560  }
561  continue;
562  }
563 
564  // Don't insert a trunc for a zext which can still legally promote.
565  // Nor insert a trunc when the input value to that trunc has the same width
566  // as the zext we are inserting it for. When this happens the input operand
567  // for the zext will be promoted to the same width as the zext's return type
568  // rendering that zext unnecessary. This zext gets removed before the end
569  // of the pass.
570  if (auto ZExt = dyn_cast<ZExtInst>(I))
571  if (ZExt->getType()->getScalarSizeInBits() >= PromotedWidth)
572  continue;
573 
574  // Now handle the others.
575  for (unsigned i = 0; i < I->getNumOperands(); ++i) {
576  Type *Ty = TruncTysMap[I][i];
577  if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) {
578  Trunc->moveBefore(I);
579  I->setOperand(i, Trunc);
580  }
581  }
582  }
583 }
584 
585 void IRPromoter::Cleanup() {
586  LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n");
587  // Some zexts will now have become redundant, along with their trunc
588  // operands, so remove them.
589  for (auto *V : Visited) {
590  if (!isa<ZExtInst>(V))
591  continue;
592 
593  auto ZExt = cast<ZExtInst>(V);
594  if (ZExt->getDestTy() != ExtTy)
595  continue;
596 
597  Value *Src = ZExt->getOperand(0);
598  if (ZExt->getSrcTy() == ZExt->getDestTy()) {
599  LLVM_DEBUG(dbgs() << "IR Promotion: Removing unnecessary cast: " << *ZExt
600  << "\n");
601  ReplaceAllUsersOfWith(ZExt, Src);
602  continue;
603  }
604 
605  // We've inserted a trunc for a zext sink, but we already know that the
606  // input is in range, negating the need for the trunc.
607  if (NewInsts.count(Src) && isa<TruncInst>(Src)) {
608  auto *Trunc = cast<TruncInst>(Src);
609  assert(Trunc->getOperand(0)->getType() == ExtTy &&
610  "expected inserted trunc to be operating on i32");
611  ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));
612  }
613  }
614 
615  for (auto *I : InstsToRemove) {
616  LLVM_DEBUG(dbgs() << "IR Promotion: Removing " << *I << "\n");
617  I->dropAllReferences();
618  }
619 }
620 
621 void IRPromoter::ConvertTruncs() {
622  LLVM_DEBUG(dbgs() << "IR Promotion: Converting truncs..\n");
623  IRBuilder<> Builder{Ctx};
624 
625  for (auto *V : Visited) {
626  if (!isa<TruncInst>(V) || Sources.count(V))
627  continue;
628 
629  auto *Trunc = cast<TruncInst>(V);
630  Builder.SetInsertPoint(Trunc);
631  IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());
632  IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);
633 
634  unsigned NumBits = DestTy->getScalarSizeInBits();
635  ConstantInt *Mask =
636  ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue());
637  Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask);
638  if (SrcTy != ExtTy)
639  Masked = Builder.CreateTrunc(Masked, ExtTy);
640 
641  if (auto *I = dyn_cast<Instruction>(Masked))
642  NewInsts.insert(I);
643 
644  ReplaceAllUsersOfWith(Trunc, Masked);
645  }
646 }
647 
648 void IRPromoter::Mutate() {
649  LLVM_DEBUG(dbgs() << "IR Promotion: Promoting use-def chains to "
650  << PromotedWidth << "-bits\n");
651 
652  // Cache original types of the values that will likely need truncating
653  for (auto *I : Sinks) {
654  if (auto *Call = dyn_cast<CallInst>(I)) {
655  for (Value *Arg : Call->args())
656  TruncTysMap[Call].push_back(Arg->getType());
657  } else if (auto *Switch = dyn_cast<SwitchInst>(I))
658  TruncTysMap[I].push_back(Switch->getCondition()->getType());
659  else {
660  for (unsigned i = 0; i < I->getNumOperands(); ++i)
661  TruncTysMap[I].push_back(I->getOperand(i)->getType());
662  }
663  }
664  for (auto *V : Visited) {
665  if (!isa<TruncInst>(V) || Sources.count(V))
666  continue;
667  auto *Trunc = cast<TruncInst>(V);
668  TruncTysMap[Trunc].push_back(Trunc->getDestTy());
669  }
670 
671  // Insert zext instructions between sources and their users.
672  ExtendSources();
673 
674  // Promote visited instructions, mutating their types in place.
675  PromoteTree();
676 
677  // Convert any truncs, that aren't sources, into AND masks.
678  ConvertTruncs();
679 
680  // Insert trunc instructions for use by calls, stores etc...
681  TruncateSinks();
682 
683  // Finally, remove unecessary zexts and truncs, delete old instructions and
684  // clear the data structures.
685  Cleanup();
686 
687  LLVM_DEBUG(dbgs() << "IR Promotion: Mutation complete\n");
688 }
689 
690 /// We disallow booleans to make life easier when dealing with icmps but allow
691 /// any other integer that fits in a scalar register. Void types are accepted
692 /// so we can handle switches.
694  Type *Ty = V->getType();
695 
696  // Allow voids and pointers, these won't be promoted.
697  if (Ty->isVoidTy() || Ty->isPointerTy())
698  return true;
699 
700  if (!isa<IntegerType>(Ty) || cast<IntegerType>(Ty)->getBitWidth() == 1 ||
701  cast<IntegerType>(Ty)->getBitWidth() > RegisterBitWidth)
702  return false;
703 
704  return LessOrEqualTypeSize(V);
705 }
706 
707 /// We accept most instructions, as well as Arguments and ConstantInsts. We
708 /// Disallow casts other than zext and truncs and only allow calls if their
709 /// return value is zeroext. We don't allow opcodes that can introduce sign
710 /// bits.
711 bool TypePromotionImpl::isSupportedValue(Value *V) {
712  if (auto *I = dyn_cast<Instruction>(V)) {
713  switch (I->getOpcode()) {
714  default:
715  return isa<BinaryOperator>(I) && isSupportedType(I) &&
717  case Instruction::GetElementPtr:
718  case Instruction::Store:
719  case Instruction::Br:
720  case Instruction::Switch:
721  return true;
722  case Instruction::PHI:
723  case Instruction::Select:
724  case Instruction::Ret:
725  case Instruction::Load:
726  case Instruction::Trunc:
727  case Instruction::BitCast:
728  return isSupportedType(I);
729  case Instruction::ZExt:
730  return isSupportedType(I->getOperand(0));
731  case Instruction::ICmp:
732  // Now that we allow small types than TypeSize, only allow icmp of
733  // TypeSize because they will require a trunc to be legalised.
734  // TODO: Allow icmp of smaller types, and calculate at the end
735  // whether the transform would be beneficial.
736  if (isa<PointerType>(I->getOperand(0)->getType()))
737  return true;
738  return EqualTypeSize(I->getOperand(0));
739  case Instruction::Call: {
740  // Special cases for calls as we need to check for zeroext
741  // TODO We should accept calls even if they don't have zeroext, as they
742  // can still be sinks.
743  auto *Call = cast<CallInst>(I);
744  return isSupportedType(Call) &&
745  Call->hasRetAttr(Attribute::AttrKind::ZExt);
746  }
747  }
748  } else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
749  return isSupportedType(V);
750  } else if (isa<Argument>(V))
751  return isSupportedType(V);
752 
753  return isa<BasicBlock>(V);
754 }
755 
756 /// Check that the type of V would be promoted and that the original type is
757 /// smaller than the targeted promoted type. Check that we're not trying to
758 /// promote something larger than our base 'TypeSize' type.
760  auto *I = dyn_cast<Instruction>(V);
761  if (!I)
762  return true;
763 
764  if (SafeToPromote.count(I))
765  return true;
766 
767  if (isPromotedResultSafe(I) || isSafeWrap(I)) {
768  SafeToPromote.insert(I);
769  return true;
770  }
771  return false;
772 }
773 
774 bool TypePromotionImpl::TryToPromote(Value *V, unsigned PromotedWidth,
775  const LoopInfo &LI) {
776  Type *OrigTy = V->getType();
778  SafeToPromote.clear();
779  SafeWrap.clear();
780 
781  if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
782  return false;
783 
784  LLVM_DEBUG(dbgs() << "IR Promotion: TryToPromote: " << *V << ", from "
785  << TypeSize << " bits to " << PromotedWidth << "\n");
786 
787  SetVector<Value *> WorkList;
788  SetVector<Value *> Sources;
790  SetVector<Value *> CurrentVisited;
791  WorkList.insert(V);
792 
793  // Return true if V was added to the worklist as a supported instruction,
794  // if it was already visited, or if we don't need to explore it (e.g.
795  // pointer values and GEPs), and false otherwise.
796  auto AddLegalInst = [&](Value *V) {
797  if (CurrentVisited.count(V))
798  return true;
799 
800  // Ignore GEPs because they don't need promoting and the constant indices
801  // will prevent the transformation.
802  if (isa<GetElementPtrInst>(V))
803  return true;
804 
805  if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
806  LLVM_DEBUG(dbgs() << "IR Promotion: Can't handle: " << *V << "\n");
807  return false;
808  }
809 
810  WorkList.insert(V);
811  return true;
812  };
813 
814  // Iterate through, and add to, a tree of operands and users in the use-def.
815  while (!WorkList.empty()) {
816  Value *V = WorkList.pop_back_val();
817  if (CurrentVisited.count(V))
818  continue;
819 
820  // Ignore non-instructions, other than arguments.
821  if (!isa<Instruction>(V) && !isSource(V))
822  continue;
823 
824  // If we've already visited this value from somewhere, bail now because
825  // the tree has already been explored.
826  // TODO: This could limit the transform, ie if we try to promote something
827  // from an i8 and fail first, before trying an i16.
828  if (AllVisited.count(V))
829  return false;
830 
831  CurrentVisited.insert(V);
832  AllVisited.insert(V);
833 
834  // Calls can be both sources and sinks.
835  if (isSink(V))
836  Sinks.insert(cast<Instruction>(V));
837 
838  if (isSource(V))
839  Sources.insert(V);
840 
841  if (!isSink(V) && !isSource(V)) {
842  if (auto *I = dyn_cast<Instruction>(V)) {
843  // Visit operands of any instruction visited.
844  for (auto &U : I->operands()) {
845  if (!AddLegalInst(U))
846  return false;
847  }
848  }
849  }
850 
851  // Don't visit users of a node which isn't going to be mutated unless its a
852  // source.
853  if (isSource(V) || shouldPromote(V)) {
854  for (Use &U : V->uses()) {
855  if (!AddLegalInst(U.getUser()))
856  return false;
857  }
858  }
859  }
860 
861  LLVM_DEBUG({
862  dbgs() << "IR Promotion: Visited nodes:\n";
863  for (auto *I : CurrentVisited)
864  I->dump();
865  });
866 
867  unsigned ToPromote = 0;
868  unsigned NonFreeArgs = 0;
869  unsigned NonLoopSources = 0, LoopSinks = 0;
871  for (auto *CV : CurrentVisited) {
872  if (auto *I = dyn_cast<Instruction>(CV))
873  Blocks.insert(I->getParent());
874 
875  if (Sources.count(CV)) {
876  if (auto *Arg = dyn_cast<Argument>(CV))
877  if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())
878  ++NonFreeArgs;
879  if (!isa<Instruction>(CV) ||
880  !LI.getLoopFor(cast<Instruction>(CV)->getParent()))
881  ++NonLoopSources;
882  continue;
883  }
884 
885  if (isa<PHINode>(CV))
886  continue;
887  if (LI.getLoopFor(cast<Instruction>(CV)->getParent()))
888  ++LoopSinks;
889  if (Sinks.count(cast<Instruction>(CV)))
890  continue;
891  ++ToPromote;
892  }
893 
894  // DAG optimizations should be able to handle these cases better, especially
895  // for function arguments.
896  if (!isa<PHINode>(V) && !(LoopSinks && NonLoopSources) &&
897  (ToPromote < 2 || (Blocks.size() == 1 && NonFreeArgs > SafeWrap.size())))
898  return false;
899 
900  IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks,
901  SafeWrap, InstsToRemove);
902  Promoter.Mutate();
903  return true;
904 }
905 
907  const TargetTransformInfo &TTI,
908  const LoopInfo &LI) {
909  if (DisablePromotion)
910  return false;
911 
912  LLVM_DEBUG(dbgs() << "IR Promotion: Running on " << F.getName() << "\n");
913 
914  AllVisited.clear();
915  SafeToPromote.clear();
916  SafeWrap.clear();
917  bool MadeChange = false;
918  const DataLayout &DL = F.getParent()->getDataLayout();
919  const TargetSubtargetInfo *SubtargetInfo = TM->getSubtargetImpl(F);
920  const TargetLowering *TLI = SubtargetInfo->getTargetLowering();
921  RegisterBitWidth =
923  Ctx = &F.getParent()->getContext();
924 
925  // Return the preferred integer width of the instruction, or zero if we
926  // shouldn't try.
927  auto GetPromoteWidth = [&](Instruction *I) -> uint32_t {
928  if (!isa<IntegerType>(I->getType()))
929  return 0;
930 
931  EVT SrcVT = TLI->getValueType(DL, I->getType());
932  if (SrcVT.isSimple() && TLI->isTypeLegal(SrcVT.getSimpleVT()))
933  return 0;
934 
935  if (TLI->getTypeAction(*Ctx, SrcVT) != TargetLowering::TypePromoteInteger)
936  return 0;
937 
938  EVT PromotedVT = TLI->getTypeToTransformTo(*Ctx, SrcVT);
939  if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) {
940  LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register "
941  << "for promoted type\n");
942  return 0;
943  }
944 
945  // TODO: Should we prefer to use RegisterBitWidth instead?
946  return PromotedVT.getFixedSizeInBits();
947  };
948 
949  auto BBIsInLoop = [&](BasicBlock *BB) -> bool {
950  for (auto *L : LI)
951  if (L->contains(BB))
952  return true;
953  return false;
954  };
955 
956  for (BasicBlock &BB : F) {
957  for (Instruction &I : BB) {
958  if (AllVisited.count(&I))
959  continue;
960 
961  if (isa<ZExtInst>(&I) && isa<PHINode>(I.getOperand(0)) &&
962  isa<IntegerType>(I.getType()) && BBIsInLoop(&BB)) {
963  LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << I.getOperand(0)
964  << "\n");
965  EVT ZExtVT = TLI->getValueType(DL, I.getType());
966  Instruction *Phi = static_cast<Instruction *>(I.getOperand(0));
967  auto PromoteWidth = ZExtVT.getFixedSizeInBits();
968  if (RegisterBitWidth < PromoteWidth) {
969  LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target "
970  << "register for ZExt type\n");
971  continue;
972  }
973  MadeChange |= TryToPromote(Phi, PromoteWidth, LI);
974  } else if (auto *ICmp = dyn_cast<ICmpInst>(&I)) {
975  // Search up from icmps to try to promote their operands.
976  // Skip signed or pointer compares
977  if (ICmp->isSigned())
978  continue;
979 
980  LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n");
981 
982  for (auto &Op : ICmp->operands()) {
983  if (auto *OpI = dyn_cast<Instruction>(Op)) {
984  if (auto PromotedWidth = GetPromoteWidth(OpI)) {
985  MadeChange |= TryToPromote(OpI, PromotedWidth, LI);
986  break;
987  }
988  }
989  }
990  }
991  }
992  if (!InstsToRemove.empty()) {
993  for (auto *I : InstsToRemove)
994  I->eraseFromParent();
995  InstsToRemove.clear();
996  }
997  }
998 
999  AllVisited.clear();
1000  SafeToPromote.clear();
1001  SafeWrap.clear();
1002 
1003  return MadeChange;
1004 }
1005 
1006 INITIALIZE_PASS_BEGIN(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false)
1010 INITIALIZE_PASS_END(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false)
1011 
1012 char TypePromotionLegacy::ID = 0;
1013 
1014 bool TypePromotionLegacy::runOnFunction(Function &F) {
1015  if (skipFunction(F))
1016  return false;
1017 
1018  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
1019  if (!TPC)
1020  return false;
1021 
1022  auto *TM = &TPC->getTM<TargetMachine>();
1023  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1024  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1025 
1026  TypePromotionImpl TP;
1027  return TP.run(F, TM, TTI, LI);
1028 }
1029 
1031  return new TypePromotionLegacy();
1032 }
1033 
1036  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1037  auto &LI = AM.getResult<LoopAnalysis>(F);
1038  TypePromotionImpl TP;
1039 
1040  bool Changed = TP.run(F, TM, TTI, LI);
1041  if (!Changed)
1042  return PreservedAnalyses::all();
1043 
1044  PreservedAnalyses PA;
1045  PA.preserveSet<CFGAnalyses>();
1046  PA.preserve<LoopAnalysis>();
1047  return PA;
1048 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2607
PASS_NAME
#define PASS_NAME
Definition: TypePromotion.cpp:43
GenerateSignBits
static bool GenerateSignBits(Instruction *I)
Definition: TypePromotion.cpp:200
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
llvm::TargetLoweringBase::getTypeToTransformTo
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
Definition: TargetLowering.h:999
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:249
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2119
llvm::EVT::getFixedSizeInBits
uint64_t getFixedSizeInBits() const
Return the size of the specified fixed width value type in bits.
Definition: ValueTypes.h:348
llvm::Function
Definition: Function.h:59
StringRef.h
Pass.h
llvm::TargetTransformInfo::getRegisterBitWidth
TypeSize getRegisterBitWidth(RegisterKind K) const
Definition: TargetTransformInfo.cpp:650
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:132
llvm::ConstantExpr::getSExt
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2105
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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:172
llvm::IRBuilder<>
llvm::TargetTransformInfo::RGK_Scalar
@ RGK_Scalar
Definition: TargetTransformInfo.h:969
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:138
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::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:119
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:401
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::EVT::isSimple
bool isSimple() const
Test if the given EVT is simple (as opposed to being extended).
Definition: ValueTypes.h:129
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:187
llvm::BitmaskEnumDetail::Mask
constexpr 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
Instruction.h
CommandLine.h
TargetLowering.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
TargetMachine.h
Constants.h
llvm::User
Definition: User.h:44
llvm::EVT
Extended Value Type.
Definition: ValueTypes.h:34
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:3510
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:376
false
Definition: StackSlotColoring.cpp:141
llvm::MCID::Return
@ Return
Definition: MCInstrDesc.h:154
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:41
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:188
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:887
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:156
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::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
LoopInfo.h
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:2663
llvm::TargetLoweringBase::isTypeLegal
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
Definition: TargetLowering.h:936
llvm::TargetLoweringBase::TypePromoteInteger
@ TypePromoteInteger
Definition: TargetLowering.h:208
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:31
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
TargetPassConfig.h
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::details::FixedOrScalableQuantity::getFixedValue
constexpr ScalarTy getFixedValue() const
Definition: TypeSize.h:182
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::TargetMachine
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:78
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:140
Cleanup
static const HTTPClientCleanup Cleanup
Definition: HTTPClient.cpp:42
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
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:280
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::SetVector::pop_back_val
T pop_back_val()
Definition: SetVector.h:225
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:806
uint32_t
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:62
llvm::TypePromotionPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: TypePromotion.cpp:1034
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:165
Attributes.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:354
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::TypeSize
Definition: TypeSize.h:314
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:208
llvm::APInt::isNonPositive
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
Definition: APInt.h:344
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:186
TypePromotion.h
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:439
llvm::codeview::ModifierOptions::Const
@ Const
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
llvm::TargetSubtargetInfo::getTargetLowering
virtual const TargetLowering * getTargetLowering() const
Definition: TargetSubtargetInfo.h:99
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
TargetTransformInfo.h
isSupportedType
static bool isSupportedType(const DataLayout &DL, const ARMTargetLowering &TLI, Type *T)
Definition: ARMCallLowering.cpp:56
llvm::APInt::sgt
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1179
llvm::SmallPtrSetImpl< Instruction * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:308
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:411
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:1494
llvm::createTypePromotionLegacyPass
FunctionPass * createTypePromotionLegacyPass()
Create IR Type Promotion pass.
Definition: TypePromotion.cpp:1030
llvm::SetVector< Value * >
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
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:986
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Type::getPrimitiveSizeInBits
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:163
llvm::EVT::getSimpleVT
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
Definition: ValueTypes.h:288
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:365