blob: 69ecc337820a33c4f4e7034b412a70572e4302f4 [file] [log] [blame]
Sam Parker3828c6f2018-07-23 12:27:47 +00001//===----- ARMCodeGenPrepare.cpp ------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10/// \file
11/// This pass inserts intrinsics to handle small types that would otherwise be
12/// promoted during legalization. Here we can manually promote types or insert
13/// intrinsics which can handle narrow types that aren't supported by the
14/// register classes.
15//
16//===----------------------------------------------------------------------===//
17
18#include "ARM.h"
19#include "ARMSubtarget.h"
20#include "ARMTargetMachine.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/CodeGen/Passes.h"
23#include "llvm/CodeGen/TargetPassConfig.h"
24#include "llvm/IR/Attributes.h"
25#include "llvm/IR/BasicBlock.h"
26#include "llvm/IR/IRBuilder.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/IR/InstrTypes.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/IntrinsicInst.h"
32#include "llvm/IR/Intrinsics.h"
33#include "llvm/IR/Type.h"
34#include "llvm/IR/Value.h"
35#include "llvm/IR/Verifier.h"
36#include "llvm/Pass.h"
37#include "llvm/Support/Casting.h"
38#include "llvm/Support/CommandLine.h"
39
40#define DEBUG_TYPE "arm-codegenprepare"
41
42using namespace llvm;
43
44static cl::opt<bool>
Reid Klecknerb32ff462018-07-31 23:09:42 +000045DisableCGP("arm-disable-cgp", cl::Hidden, cl::init(true),
Sam Parker3828c6f2018-07-23 12:27:47 +000046 cl::desc("Disable ARM specific CodeGenPrepare pass"));
47
48static cl::opt<bool>
49EnableDSP("arm-enable-scalar-dsp", cl::Hidden, cl::init(false),
50 cl::desc("Use DSP instructions for scalar operations"));
51
52static cl::opt<bool>
53EnableDSPWithImms("arm-enable-scalar-dsp-imms", cl::Hidden, cl::init(false),
54 cl::desc("Use DSP instructions for scalar operations\
55 with immediate operands"));
56
57namespace {
58
59class IRPromoter {
60 SmallPtrSet<Value*, 8> NewInsts;
61 SmallVector<Instruction*, 4> InstsToRemove;
62 Module *M = nullptr;
63 LLVMContext &Ctx;
64
65public:
66 IRPromoter(Module *M) : M(M), Ctx(M->getContext()) { }
67
68 void Cleanup() {
69 for (auto *I : InstsToRemove) {
70 LLVM_DEBUG(dbgs() << "ARM CGP: Removing " << *I << "\n");
71 I->dropAllReferences();
72 I->eraseFromParent();
73 }
74 InstsToRemove.clear();
75 NewInsts.clear();
76 }
77
78 void Mutate(Type *OrigTy,
79 SmallPtrSetImpl<Value*> &Visited,
80 SmallPtrSetImpl<Value*> &Leaves,
81 SmallPtrSetImpl<Instruction*> &Roots);
82};
83
84class ARMCodeGenPrepare : public FunctionPass {
85 const ARMSubtarget *ST = nullptr;
86 IRPromoter *Promoter = nullptr;
87 std::set<Value*> AllVisited;
Sam Parker3828c6f2018-07-23 12:27:47 +000088
Sam Parker3828c6f2018-07-23 12:27:47 +000089 bool isSupportedValue(Value *V);
90 bool isLegalToPromote(Value *V);
91 bool TryToPromote(Value *V);
92
93public:
94 static char ID;
Sam Parker8c4b9642018-08-10 13:57:13 +000095 static unsigned TypeSize;
96 Type *OrigTy = nullptr;
Sam Parker3828c6f2018-07-23 12:27:47 +000097
98 ARMCodeGenPrepare() : FunctionPass(ID) {}
99
Sam Parker3828c6f2018-07-23 12:27:47 +0000100 void getAnalysisUsage(AnalysisUsage &AU) const override {
101 AU.addRequired<TargetPassConfig>();
102 }
103
104 StringRef getPassName() const override { return "ARM IR optimizations"; }
105
106 bool doInitialization(Module &M) override;
107 bool runOnFunction(Function &F) override;
Matt Morehousea70685f2018-07-23 17:00:45 +0000108 bool doFinalization(Module &M) override;
Sam Parker3828c6f2018-07-23 12:27:47 +0000109};
110
111}
112
113/// Can the given value generate sign bits.
114static bool isSigned(Value *V) {
115 if (!isa<Instruction>(V))
116 return false;
117
118 unsigned Opc = cast<Instruction>(V)->getOpcode();
119 return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
120 Opc == Instruction::SRem;
121}
122
123/// Some instructions can use 8- and 16-bit operands, and we don't need to
124/// promote anything larger. We disallow booleans to make life easier when
125/// dealing with icmps but allow any other integer that is <= 16 bits. Void
126/// types are accepted so we can handle switches.
127static bool isSupportedType(Value *V) {
Sam Parker8c4b9642018-08-10 13:57:13 +0000128 LLVM_DEBUG(dbgs() << "ARM CGP: isSupportedType: " << *V << "\n");
129 Type *Ty = V->getType();
Sam Parker7def86b2018-08-15 07:52:35 +0000130
131 // Allow voids and pointers, these won't be promoted.
132 if (Ty->isVoidTy() || Ty->isPointerTy())
Sam Parker3828c6f2018-07-23 12:27:47 +0000133 return true;
134
Sam Parker8c4b9642018-08-10 13:57:13 +0000135 if (auto *Ld = dyn_cast<LoadInst>(V))
136 Ty = cast<PointerType>(Ld->getPointerOperandType())->getElementType();
137
138 const IntegerType *IntTy = dyn_cast<IntegerType>(Ty);
139 if (!IntTy) {
140 LLVM_DEBUG(dbgs() << "ARM CGP: No, not an integer.\n");
Sam Parker3828c6f2018-07-23 12:27:47 +0000141 return false;
Sam Parker8c4b9642018-08-10 13:57:13 +0000142 }
Sam Parker3828c6f2018-07-23 12:27:47 +0000143
Sam Parker8c4b9642018-08-10 13:57:13 +0000144 return IntTy->getBitWidth() == ARMCodeGenPrepare::TypeSize;
145}
Sam Parker3828c6f2018-07-23 12:27:47 +0000146
Sam Parker8c4b9642018-08-10 13:57:13 +0000147/// Return true if the given value is a leaf in the use-def chain, producing
148/// a narrow (i8, i16) value. These values will be zext to start the promotion
149/// of the tree to i32. We guarantee that these won't populate the upper bits
150/// of the register. ZExt on the loads will be free, and the same for call
151/// return values because we only accept ones that guarantee a zeroext ret val.
152/// Many arguments will have the zeroext attribute too, so those would be free
153/// too.
154static bool isSource(Value *V) {
Sam Parker7def86b2018-08-15 07:52:35 +0000155 if (!isa<IntegerType>(V->getType()))
156 return false;
Sam Parker8c4b9642018-08-10 13:57:13 +0000157 // TODO Allow truncs and zext to be sources.
158 if (isa<Argument>(V))
159 return true;
160 else if (isa<LoadInst>(V))
161 return true;
162 else if (auto *Call = dyn_cast<CallInst>(V))
163 return Call->hasRetAttr(Attribute::AttrKind::ZExt);
164 return false;
Sam Parker3828c6f2018-07-23 12:27:47 +0000165}
166
167/// Return true if V will require any promoted values to be truncated for the
Sam Parker8c4b9642018-08-10 13:57:13 +0000168/// the IR to remain valid. We can't mutate the value type of these
169/// instructions.
Sam Parker3828c6f2018-07-23 12:27:47 +0000170static bool isSink(Value *V) {
Sam Parker8c4b9642018-08-10 13:57:13 +0000171 // TODO The truncate also isn't actually necessary because we would already
172 // proved that the data value is kept within the range of the original data
173 // type.
Sam Parker3828c6f2018-07-23 12:27:47 +0000174 auto UsesNarrowValue = [](Value *V) {
Sam Parker8c4b9642018-08-10 13:57:13 +0000175 return V->getType()->getScalarSizeInBits() == ARMCodeGenPrepare::TypeSize;
Sam Parker3828c6f2018-07-23 12:27:47 +0000176 };
177
178 if (auto *Store = dyn_cast<StoreInst>(V))
179 return UsesNarrowValue(Store->getValueOperand());
180 if (auto *Return = dyn_cast<ReturnInst>(V))
181 return UsesNarrowValue(Return->getReturnValue());
Sam Parker8c4b9642018-08-10 13:57:13 +0000182 if (auto *Trunc = dyn_cast<TruncInst>(V))
183 return UsesNarrowValue(Trunc->getOperand(0));
Sam Parker3828c6f2018-07-23 12:27:47 +0000184
185 return isa<CallInst>(V);
186}
187
Sam Parker3828c6f2018-07-23 12:27:47 +0000188/// Return whether the instruction can be promoted within any modifications to
189/// it's operands or result.
190static bool isSafeOverflow(Instruction *I) {
Sam Parker8c4b9642018-08-10 13:57:13 +0000191 // FIXME Do we need NSW too?
Sam Parker3828c6f2018-07-23 12:27:47 +0000192 if (isa<OverflowingBinaryOperator>(I) && I->hasNoUnsignedWrap())
193 return true;
194
195 unsigned Opc = I->getOpcode();
196 if (Opc == Instruction::Add || Opc == Instruction::Sub) {
197 // We don't care if the add or sub could wrap if the value is decreasing
198 // and is only being used by an unsigned compare.
199 if (!I->hasOneUse() ||
200 !isa<ICmpInst>(*I->user_begin()) ||
201 !isa<ConstantInt>(I->getOperand(1)))
202 return false;
203
204 auto *CI = cast<ICmpInst>(*I->user_begin());
205 if (CI->isSigned())
206 return false;
207
208 bool NegImm = cast<ConstantInt>(I->getOperand(1))->isNegative();
209 bool IsDecreasing = ((Opc == Instruction::Sub) && !NegImm) ||
210 ((Opc == Instruction::Add) && NegImm);
211 if (!IsDecreasing)
212 return false;
213
214 LLVM_DEBUG(dbgs() << "ARM CGP: Allowing safe overflow for " << *I << "\n");
215 return true;
216 }
217
218 // Otherwise, if an instruction is using a negative immediate we will need
219 // to fix it up during the promotion.
220 for (auto &Op : I->operands()) {
221 if (auto *Const = dyn_cast<ConstantInt>(Op))
222 if (Const->isNegative())
223 return false;
224 }
225 return false;
226}
227
228static bool shouldPromote(Value *V) {
Sam Parker7def86b2018-08-15 07:52:35 +0000229 if (!isa<IntegerType>(V->getType()) || isSink(V)) {
230 LLVM_DEBUG(dbgs() << "ARM CGP: Don't need to promote: " << *V << "\n");
Sam Parker8c4b9642018-08-10 13:57:13 +0000231 return false;
Sam Parker7def86b2018-08-15 07:52:35 +0000232 }
Sam Parker8c4b9642018-08-10 13:57:13 +0000233
234 if (isSource(V))
235 return true;
236
Sam Parker3828c6f2018-07-23 12:27:47 +0000237 auto *I = dyn_cast<Instruction>(V);
238 if (!I)
239 return false;
240
Sam Parker8c4b9642018-08-10 13:57:13 +0000241 if (isa<ICmpInst>(I))
Sam Parker3828c6f2018-07-23 12:27:47 +0000242 return false;
243
Sam Parker3828c6f2018-07-23 12:27:47 +0000244 return true;
245}
246
247/// Return whether we can safely mutate V's type to ExtTy without having to be
248/// concerned with zero extending or truncation.
249static bool isPromotedResultSafe(Value *V) {
250 if (!isa<Instruction>(V))
251 return true;
252
253 if (isSigned(V))
254 return false;
255
256 // If I is only being used by something that will require its value to be
257 // truncated, then we don't care about the promoted result.
258 auto *I = cast<Instruction>(V);
259 if (I->hasOneUse() && isSink(*I->use_begin()))
260 return true;
261
262 if (isa<OverflowingBinaryOperator>(I))
263 return isSafeOverflow(I);
264 return true;
265}
266
267/// Return the intrinsic for the instruction that can perform the same
268/// operation but on a narrow type. This is using the parallel dsp intrinsics
269/// on scalar values.
Sam Parker8c4b9642018-08-10 13:57:13 +0000270static Intrinsic::ID getNarrowIntrinsic(Instruction *I) {
Sam Parker3828c6f2018-07-23 12:27:47 +0000271 // Whether we use the signed or unsigned versions of these intrinsics
272 // doesn't matter because we're not using the GE bits that they set in
273 // the APSR.
274 switch(I->getOpcode()) {
275 default:
276 break;
277 case Instruction::Add:
Sam Parker8c4b9642018-08-10 13:57:13 +0000278 return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_uadd16 :
Sam Parker3828c6f2018-07-23 12:27:47 +0000279 Intrinsic::arm_uadd8;
280 case Instruction::Sub:
Sam Parker8c4b9642018-08-10 13:57:13 +0000281 return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_usub16 :
Sam Parker3828c6f2018-07-23 12:27:47 +0000282 Intrinsic::arm_usub8;
283 }
284 llvm_unreachable("unhandled opcode for narrow intrinsic");
285}
286
287void IRPromoter::Mutate(Type *OrigTy,
288 SmallPtrSetImpl<Value*> &Visited,
289 SmallPtrSetImpl<Value*> &Leaves,
290 SmallPtrSetImpl<Instruction*> &Roots) {
291 IRBuilder<> Builder{Ctx};
292 Type *ExtTy = Type::getInt32Ty(M->getContext());
Sam Parker3828c6f2018-07-23 12:27:47 +0000293 SmallPtrSet<Value*, 8> Promoted;
Sam Parker8c4b9642018-08-10 13:57:13 +0000294 LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from "
295 << ARMCodeGenPrepare::TypeSize << " to 32-bits\n");
Sam Parker3828c6f2018-07-23 12:27:47 +0000296
297 auto ReplaceAllUsersOfWith = [&](Value *From, Value *To) {
298 SmallVector<Instruction*, 4> Users;
299 Instruction *InstTo = dyn_cast<Instruction>(To);
300 for (Use &U : From->uses()) {
301 auto *User = cast<Instruction>(U.getUser());
302 if (InstTo && User->isIdenticalTo(InstTo))
303 continue;
304 Users.push_back(User);
305 }
306
307 for (auto &U : Users)
308 U->replaceUsesOfWith(From, To);
309 };
310
311 auto FixConst = [&](ConstantInt *Const, Instruction *I) {
312 Constant *NewConst = nullptr;
313 if (isSafeOverflow(I)) {
314 NewConst = (Const->isNegative()) ?
315 ConstantExpr::getSExt(Const, ExtTy) :
316 ConstantExpr::getZExt(Const, ExtTy);
317 } else {
318 uint64_t NewVal = *Const->getValue().getRawData();
319 if (Const->getType() == Type::getInt16Ty(Ctx))
320 NewVal &= 0xFFFF;
321 else
322 NewVal &= 0xFF;
323 NewConst = ConstantInt::get(ExtTy, NewVal);
324 }
325 I->replaceUsesOfWith(Const, NewConst);
326 };
327
328 auto InsertDSPIntrinsic = [&](Instruction *I) {
329 LLVM_DEBUG(dbgs() << "ARM CGP: Inserting DSP intrinsic for "
330 << *I << "\n");
331 Function *DSPInst =
Sam Parker8c4b9642018-08-10 13:57:13 +0000332 Intrinsic::getDeclaration(M, getNarrowIntrinsic(I));
Sam Parker3828c6f2018-07-23 12:27:47 +0000333 Builder.SetInsertPoint(I);
334 Builder.SetCurrentDebugLocation(I->getDebugLoc());
335 Value *Args[] = { I->getOperand(0), I->getOperand(1) };
336 CallInst *Call = Builder.CreateCall(DSPInst, Args);
337 ReplaceAllUsersOfWith(I, Call);
338 InstsToRemove.push_back(I);
339 NewInsts.insert(Call);
340 };
341
342 auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
343 LLVM_DEBUG(dbgs() << "ARM CGP: Inserting ZExt for " << *V << "\n");
344 Builder.SetInsertPoint(InsertPt);
345 if (auto *I = dyn_cast<Instruction>(V))
346 Builder.SetCurrentDebugLocation(I->getDebugLoc());
347 auto *ZExt = cast<Instruction>(Builder.CreateZExt(V, ExtTy));
348 if (isa<Argument>(V))
349 ZExt->moveBefore(InsertPt);
350 else
351 ZExt->moveAfter(InsertPt);
352 ReplaceAllUsersOfWith(V, ZExt);
353 NewInsts.insert(ZExt);
354 };
355
356 // First, insert extending instructions between the leaves and their users.
357 LLVM_DEBUG(dbgs() << "ARM CGP: Promoting leaves:\n");
358 for (auto V : Leaves) {
359 LLVM_DEBUG(dbgs() << " - " << *V << "\n");
Sam Parker8c4b9642018-08-10 13:57:13 +0000360 if (auto *I = dyn_cast<Instruction>(V))
Sam Parker3828c6f2018-07-23 12:27:47 +0000361 InsertZExt(I, I);
362 else if (auto *Arg = dyn_cast<Argument>(V)) {
363 BasicBlock &BB = Arg->getParent()->front();
364 InsertZExt(Arg, &*BB.getFirstInsertionPt());
365 } else {
366 llvm_unreachable("unhandled leaf that needs extending");
367 }
368 Promoted.insert(V);
369 }
370
371 LLVM_DEBUG(dbgs() << "ARM CGP: Mutating the tree..\n");
372 // Then mutate the types of the instructions within the tree. Here we handle
373 // constant operands.
374 for (auto *V : Visited) {
375 if (Leaves.count(V))
376 continue;
377
Sam Parker3828c6f2018-07-23 12:27:47 +0000378 auto *I = cast<Instruction>(V);
379 if (Roots.count(I))
380 continue;
381
Sam Parker7def86b2018-08-15 07:52:35 +0000382 for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
383 Value *Op = I->getOperand(i);
384 if ((Op->getType() == ExtTy) || !isa<IntegerType>(Op->getType()))
Sam Parker3828c6f2018-07-23 12:27:47 +0000385 continue;
386
Sam Parker7def86b2018-08-15 07:52:35 +0000387 if (auto *Const = dyn_cast<ConstantInt>(Op))
Sam Parker3828c6f2018-07-23 12:27:47 +0000388 FixConst(Const, I);
Sam Parker7def86b2018-08-15 07:52:35 +0000389 else if (isa<UndefValue>(Op))
390 I->setOperand(i, UndefValue::get(ExtTy));
Sam Parker3828c6f2018-07-23 12:27:47 +0000391 }
392
393 if (shouldPromote(I)) {
394 I->mutateType(ExtTy);
395 Promoted.insert(I);
396 }
397 }
398
399 // Now we need to remove any zexts that have become unnecessary, as well
400 // as insert any intrinsics.
401 for (auto *V : Visited) {
402 if (Leaves.count(V))
403 continue;
Sam Parker8c4b9642018-08-10 13:57:13 +0000404
Sam Parker3828c6f2018-07-23 12:27:47 +0000405 if (!shouldPromote(V) || isPromotedResultSafe(V))
406 continue;
407
408 // Replace unsafe instructions with appropriate intrinsic calls.
409 InsertDSPIntrinsic(cast<Instruction>(V));
410 }
411
412 LLVM_DEBUG(dbgs() << "ARM CGP: Fixing up the roots:\n");
413 // Fix up any stores or returns that use the results of the promoted
414 // chain.
415 for (auto I : Roots) {
416 LLVM_DEBUG(dbgs() << " - " << *I << "\n");
417 Type *TruncTy = OrigTy;
418 if (auto *Store = dyn_cast<StoreInst>(I)) {
419 auto *PtrTy = cast<PointerType>(Store->getPointerOperandType());
420 TruncTy = PtrTy->getElementType();
421 } else if (isa<ReturnInst>(I)) {
422 Function *F = I->getParent()->getParent();
423 TruncTy = F->getFunctionType()->getReturnType();
424 }
425
426 for (unsigned i = 0; i < I->getNumOperands(); ++i) {
427 Value *V = I->getOperand(i);
Sam Parker7def86b2018-08-15 07:52:35 +0000428 if (!isa<IntegerType>(V->getType()))
429 continue;
430
Sam Parker3828c6f2018-07-23 12:27:47 +0000431 if (Promoted.count(V) || NewInsts.count(V)) {
432 if (auto *Op = dyn_cast<Instruction>(V)) {
433
434 if (auto *Call = dyn_cast<CallInst>(I))
435 TruncTy = Call->getFunctionType()->getParamType(i);
436
437 if (TruncTy == ExtTy)
438 continue;
439
440 LLVM_DEBUG(dbgs() << "ARM CGP: Creating " << *TruncTy
441 << " Trunc for " << *Op << "\n");
442 Builder.SetInsertPoint(Op);
443 auto *Trunc = cast<Instruction>(Builder.CreateTrunc(Op, TruncTy));
444 Trunc->moveBefore(I);
445 I->setOperand(i, Trunc);
446 NewInsts.insert(Trunc);
447 }
448 }
449 }
450 }
451 LLVM_DEBUG(dbgs() << "ARM CGP: Mutation complete.\n");
452}
453
Sam Parker8c4b9642018-08-10 13:57:13 +0000454/// We accept most instructions, as well as Arguments and ConstantInsts. We
455/// Disallow casts other than zext and truncs and only allow calls if their
456/// return value is zeroext. We don't allow opcodes that can introduce sign
457/// bits.
458bool ARMCodeGenPrepare::isSupportedValue(Value *V) {
459 LLVM_DEBUG(dbgs() << "ARM CGP: Is " << *V << " supported?\n");
460
461 if (auto *ICmp = dyn_cast<ICmpInst>(V))
462 return ICmp->isEquality() || !ICmp->isSigned();
463
464 // Memory instructions
465 if (isa<StoreInst>(V) || isa<GetElementPtrInst>(V))
466 return true;
467
468 // Branches and targets.
469 if( isa<BranchInst>(V) || isa<SwitchInst>(V) || isa<BasicBlock>(V))
470 return true;
471
472 // Non-instruction values that we can handle.
Sam Parker7def86b2018-08-15 07:52:35 +0000473 if ((isa<Constant>(V) && !isa<ConstantExpr>(V)) || isa<Argument>(V))
Sam Parker8c4b9642018-08-10 13:57:13 +0000474 return isSupportedType(V);
475
476 if (isa<PHINode>(V) || isa<SelectInst>(V) || isa<ReturnInst>(V) ||
477 isa<LoadInst>(V))
478 return isSupportedType(V);
479
480 // Currently, Trunc is the only cast we support.
481 if (auto *Trunc = dyn_cast<TruncInst>(V))
482 return isSupportedType(Trunc->getOperand(0));
483
484 // Special cases for calls as we need to check for zeroext
485 // TODO We should accept calls even if they don't have zeroext, as they can
486 // still be roots.
487 if (auto *Call = dyn_cast<CallInst>(V))
488 return isSupportedType(Call) &&
489 Call->hasRetAttr(Attribute::AttrKind::ZExt);
490
491 if (!isa<BinaryOperator>(V)) {
492 LLVM_DEBUG(dbgs() << "ARM CGP: No, not a binary operator.\n");
493 return false;
494 }
495 if (!isSupportedType(V))
496 return false;
497
498 bool res = !isSigned(V);
499 if (!res)
500 LLVM_DEBUG(dbgs() << "ARM CGP: No, it's a signed instruction.\n");
501 return res;
502}
503
504/// Check that the type of V would be promoted and that the original type is
505/// smaller than the targeted promoted type. Check that we're not trying to
506/// promote something larger than our base 'TypeSize' type.
507bool ARMCodeGenPrepare::isLegalToPromote(Value *V) {
508 if (isPromotedResultSafe(V))
509 return true;
510
511 auto *I = dyn_cast<Instruction>(V);
512 if (!I)
513 return false;
514
515 // If promotion is not safe, can we use a DSP instruction to natively
516 // handle the narrow type?
Sam Parker3828c6f2018-07-23 12:27:47 +0000517 if (!ST->hasDSP() || !EnableDSP || !isSupportedType(I))
518 return false;
519
520 if (ST->isThumb() && !ST->hasThumb2())
521 return false;
522
523 if (I->getOpcode() != Instruction::Add && I->getOpcode() != Instruction::Sub)
524 return false;
525
526 // TODO
527 // Would it be profitable? For Thumb code, these parallel DSP instructions
528 // are only Thumb-2, so we wouldn't be able to dual issue on Cortex-M33. For
529 // Cortex-A, specifically Cortex-A72, the latency is double and throughput is
530 // halved. They also do not take immediates as operands.
531 for (auto &Op : I->operands()) {
532 if (isa<Constant>(Op)) {
533 if (!EnableDSPWithImms)
534 return false;
535 }
536 }
537 return true;
538}
539
Sam Parker3828c6f2018-07-23 12:27:47 +0000540bool ARMCodeGenPrepare::TryToPromote(Value *V) {
541 OrigTy = V->getType();
542 TypeSize = OrigTy->getPrimitiveSizeInBits();
Sam Parker8c4b9642018-08-10 13:57:13 +0000543 if (TypeSize > 16)
544 return false;
Sam Parker3828c6f2018-07-23 12:27:47 +0000545
546 if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
547 return false;
548
Sam Parker8c4b9642018-08-10 13:57:13 +0000549 LLVM_DEBUG(dbgs() << "ARM CGP: TryToPromote: " << *V << ", TypeSize = "
550 << TypeSize << "\n");
Sam Parker3828c6f2018-07-23 12:27:47 +0000551
552 SetVector<Value*> WorkList;
553 SmallPtrSet<Value*, 8> Leaves;
554 SmallPtrSet<Instruction*, 4> Roots;
555 WorkList.insert(V);
556 SmallPtrSet<Value*, 16> CurrentVisited;
557 CurrentVisited.clear();
558
559 // Return true if the given value can, or has been, visited. Add V to the
560 // worklist if needed.
561 auto AddLegalInst = [&](Value *V) {
562 if (CurrentVisited.count(V))
563 return true;
564
565 if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
566 LLVM_DEBUG(dbgs() << "ARM CGP: Can't handle: " << *V << "\n");
567 return false;
568 }
569
570 WorkList.insert(V);
571 return true;
572 };
573
574 // Iterate through, and add to, a tree of operands and users in the use-def.
575 while (!WorkList.empty()) {
576 Value *V = WorkList.back();
577 WorkList.pop_back();
578 if (CurrentVisited.count(V))
579 continue;
580
Sam Parker7def86b2018-08-15 07:52:35 +0000581 // Ignore non-instructions, other than arguments.
Sam Parker3828c6f2018-07-23 12:27:47 +0000582 if (!isa<Instruction>(V) && !isSource(V))
583 continue;
584
585 // If we've already visited this value from somewhere, bail now because
586 // the tree has already been explored.
587 // TODO: This could limit the transform, ie if we try to promote something
588 // from an i8 and fail first, before trying an i16.
589 if (AllVisited.count(V)) {
590 LLVM_DEBUG(dbgs() << "ARM CGP: Already visited this: " << *V << "\n");
591 return false;
592 }
593
594 CurrentVisited.insert(V);
595 AllVisited.insert(V);
596
597 // Calls can be both sources and sinks.
598 if (isSink(V))
599 Roots.insert(cast<Instruction>(V));
600 if (isSource(V))
601 Leaves.insert(V);
602 else if (auto *I = dyn_cast<Instruction>(V)) {
603 // Visit operands of any instruction visited.
604 for (auto &U : I->operands()) {
605 if (!AddLegalInst(U))
606 return false;
607 }
608 }
609
610 // Don't visit users of a node which isn't going to be mutated unless its a
611 // source.
612 if (isSource(V) || shouldPromote(V)) {
613 for (Use &U : V->uses()) {
614 if (!AddLegalInst(U.getUser()))
615 return false;
616 }
617 }
618 }
619
Sam Parker3828c6f2018-07-23 12:27:47 +0000620 LLVM_DEBUG(dbgs() << "ARM CGP: Visited nodes:\n";
621 for (auto *I : CurrentVisited)
622 I->dump();
623 );
Sam Parker7def86b2018-08-15 07:52:35 +0000624 unsigned ToPromote = 0;
625 for (auto *V : CurrentVisited) {
626 if (Leaves.count(V))
627 continue;
628 if (Roots.count(cast<Instruction>(V)))
629 continue;
630 ++ToPromote;
631 }
632
633 if (ToPromote < 2)
634 return false;
Sam Parker3828c6f2018-07-23 12:27:47 +0000635
636 Promoter->Mutate(OrigTy, CurrentVisited, Leaves, Roots);
637 return true;
638}
639
640bool ARMCodeGenPrepare::doInitialization(Module &M) {
641 Promoter = new IRPromoter(&M);
642 return false;
643}
644
645bool ARMCodeGenPrepare::runOnFunction(Function &F) {
646 if (skipFunction(F) || DisableCGP)
647 return false;
648
649 auto *TPC = &getAnalysis<TargetPassConfig>();
650 if (!TPC)
651 return false;
652
653 const TargetMachine &TM = TPC->getTM<TargetMachine>();
654 ST = &TM.getSubtarget<ARMSubtarget>(F);
655 bool MadeChange = false;
656 LLVM_DEBUG(dbgs() << "ARM CGP: Running on " << F.getName() << "\n");
657
658 // Search up from icmps to try to promote their operands.
659 for (BasicBlock &BB : F) {
660 auto &Insts = BB.getInstList();
661 for (auto &I : Insts) {
662 if (AllVisited.count(&I))
663 continue;
664
665 if (isa<ICmpInst>(I)) {
666 auto &CI = cast<ICmpInst>(I);
667
668 // Skip signed or pointer compares
669 if (CI.isSigned() || !isa<IntegerType>(CI.getOperand(0)->getType()))
670 continue;
671
672 LLVM_DEBUG(dbgs() << "ARM CGP: Searching from: " << CI << "\n");
673 for (auto &Op : CI.operands()) {
Sam Parker8c4b9642018-08-10 13:57:13 +0000674 if (auto *I = dyn_cast<Instruction>(Op))
675 MadeChange |= TryToPromote(I);
Sam Parker3828c6f2018-07-23 12:27:47 +0000676 }
677 }
678 }
679 Promoter->Cleanup();
680 LLVM_DEBUG(if (verifyFunction(F, &dbgs())) {
681 dbgs();
682 report_fatal_error("Broken function after type promotion");
683 });
684 }
685 if (MadeChange)
686 LLVM_DEBUG(dbgs() << "After ARMCodeGenPrepare: " << F << "\n");
687
688 return MadeChange;
689}
690
Matt Morehousea70685f2018-07-23 17:00:45 +0000691bool ARMCodeGenPrepare::doFinalization(Module &M) {
692 delete Promoter;
693 return false;
694}
695
Sam Parker3828c6f2018-07-23 12:27:47 +0000696INITIALIZE_PASS_BEGIN(ARMCodeGenPrepare, DEBUG_TYPE,
697 "ARM IR optimizations", false, false)
698INITIALIZE_PASS_END(ARMCodeGenPrepare, DEBUG_TYPE, "ARM IR optimizations",
699 false, false)
700
701char ARMCodeGenPrepare::ID = 0;
Sam Parker8c4b9642018-08-10 13:57:13 +0000702unsigned ARMCodeGenPrepare::TypeSize = 0;
Sam Parker3828c6f2018-07-23 12:27:47 +0000703
704FunctionPass *llvm::createARMCodeGenPreparePass() {
705 return new ARMCodeGenPrepare();
706}