Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 1 | //===----- 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 | |
| 42 | using namespace llvm; |
| 43 | |
| 44 | static cl::opt<bool> |
Reid Kleckner | b32ff46 | 2018-07-31 23:09:42 +0000 | [diff] [blame] | 45 | DisableCGP("arm-disable-cgp", cl::Hidden, cl::init(true), |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 46 | cl::desc("Disable ARM specific CodeGenPrepare pass")); |
| 47 | |
| 48 | static cl::opt<bool> |
| 49 | EnableDSP("arm-enable-scalar-dsp", cl::Hidden, cl::init(false), |
| 50 | cl::desc("Use DSP instructions for scalar operations")); |
| 51 | |
| 52 | static cl::opt<bool> |
| 53 | EnableDSPWithImms("arm-enable-scalar-dsp-imms", cl::Hidden, cl::init(false), |
| 54 | cl::desc("Use DSP instructions for scalar operations\ |
| 55 | with immediate operands")); |
| 56 | |
| 57 | namespace { |
| 58 | |
| 59 | class IRPromoter { |
| 60 | SmallPtrSet<Value*, 8> NewInsts; |
| 61 | SmallVector<Instruction*, 4> InstsToRemove; |
| 62 | Module *M = nullptr; |
| 63 | LLVMContext &Ctx; |
| 64 | |
| 65 | public: |
| 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 | |
| 84 | class ARMCodeGenPrepare : public FunctionPass { |
| 85 | const ARMSubtarget *ST = nullptr; |
| 86 | IRPromoter *Promoter = nullptr; |
| 87 | std::set<Value*> AllVisited; |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 88 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 89 | bool isSupportedValue(Value *V); |
| 90 | bool isLegalToPromote(Value *V); |
| 91 | bool TryToPromote(Value *V); |
| 92 | |
| 93 | public: |
| 94 | static char ID; |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 95 | static unsigned TypeSize; |
| 96 | Type *OrigTy = nullptr; |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 97 | |
| 98 | ARMCodeGenPrepare() : FunctionPass(ID) {} |
| 99 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 100 | 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 Morehouse | a70685f | 2018-07-23 17:00:45 +0000 | [diff] [blame] | 108 | bool doFinalization(Module &M) override; |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 109 | }; |
| 110 | |
| 111 | } |
| 112 | |
| 113 | /// Can the given value generate sign bits. |
| 114 | static 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. |
| 127 | static bool isSupportedType(Value *V) { |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 128 | LLVM_DEBUG(dbgs() << "ARM CGP: isSupportedType: " << *V << "\n"); |
| 129 | Type *Ty = V->getType(); |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 130 | |
| 131 | // Allow voids and pointers, these won't be promoted. |
| 132 | if (Ty->isVoidTy() || Ty->isPointerTy()) |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 133 | return true; |
| 134 | |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 135 | 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 141 | return false; |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 142 | } |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 143 | |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 144 | return IntTy->getBitWidth() == ARMCodeGenPrepare::TypeSize; |
| 145 | } |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 146 | |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 147 | /// 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. |
| 154 | static bool isSource(Value *V) { |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 155 | if (!isa<IntegerType>(V->getType())) |
| 156 | return false; |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 157 | // 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 165 | } |
| 166 | |
| 167 | /// Return true if V will require any promoted values to be truncated for the |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 168 | /// the IR to remain valid. We can't mutate the value type of these |
| 169 | /// instructions. |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 170 | static bool isSink(Value *V) { |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 171 | // 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 174 | auto UsesNarrowValue = [](Value *V) { |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 175 | return V->getType()->getScalarSizeInBits() == ARMCodeGenPrepare::TypeSize; |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 176 | }; |
| 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 182 | if (auto *Trunc = dyn_cast<TruncInst>(V)) |
| 183 | return UsesNarrowValue(Trunc->getOperand(0)); |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 184 | |
| 185 | return isa<CallInst>(V); |
| 186 | } |
| 187 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 188 | /// Return whether the instruction can be promoted within any modifications to |
| 189 | /// it's operands or result. |
| 190 | static bool isSafeOverflow(Instruction *I) { |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 191 | // FIXME Do we need NSW too? |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 192 | 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 | |
| 228 | static bool shouldPromote(Value *V) { |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 229 | if (!isa<IntegerType>(V->getType()) || isSink(V)) { |
| 230 | LLVM_DEBUG(dbgs() << "ARM CGP: Don't need to promote: " << *V << "\n"); |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 231 | return false; |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 232 | } |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 233 | |
| 234 | if (isSource(V)) |
| 235 | return true; |
| 236 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 237 | auto *I = dyn_cast<Instruction>(V); |
| 238 | if (!I) |
| 239 | return false; |
| 240 | |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 241 | if (isa<ICmpInst>(I)) |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 242 | return false; |
| 243 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 244 | 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. |
| 249 | static 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 270 | static Intrinsic::ID getNarrowIntrinsic(Instruction *I) { |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 271 | // 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 278 | return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_uadd16 : |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 279 | Intrinsic::arm_uadd8; |
| 280 | case Instruction::Sub: |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 281 | return ARMCodeGenPrepare::TypeSize == 16 ? Intrinsic::arm_usub16 : |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 282 | Intrinsic::arm_usub8; |
| 283 | } |
| 284 | llvm_unreachable("unhandled opcode for narrow intrinsic"); |
| 285 | } |
| 286 | |
| 287 | void 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 293 | SmallPtrSet<Value*, 8> Promoted; |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 294 | LLVM_DEBUG(dbgs() << "ARM CGP: Promoting use-def chains to from " |
| 295 | << ARMCodeGenPrepare::TypeSize << " to 32-bits\n"); |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 296 | |
| 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 332 | Intrinsic::getDeclaration(M, getNarrowIntrinsic(I)); |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 333 | 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 360 | if (auto *I = dyn_cast<Instruction>(V)) |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 361 | 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 378 | auto *I = cast<Instruction>(V); |
| 379 | if (Roots.count(I)) |
| 380 | continue; |
| 381 | |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 382 | 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 385 | continue; |
| 386 | |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 387 | if (auto *Const = dyn_cast<ConstantInt>(Op)) |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 388 | FixConst(Const, I); |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 389 | else if (isa<UndefValue>(Op)) |
| 390 | I->setOperand(i, UndefValue::get(ExtTy)); |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 391 | } |
| 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 404 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 405 | 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 Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 428 | if (!isa<IntegerType>(V->getType())) |
| 429 | continue; |
| 430 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 431 | 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 454 | /// 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. |
| 458 | bool 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 Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 473 | if ((isa<Constant>(V) && !isa<ConstantExpr>(V)) || isa<Argument>(V)) |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 474 | 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. |
| 507 | bool 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 517 | 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 540 | bool ARMCodeGenPrepare::TryToPromote(Value *V) { |
| 541 | OrigTy = V->getType(); |
| 542 | TypeSize = OrigTy->getPrimitiveSizeInBits(); |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 543 | if (TypeSize > 16) |
| 544 | return false; |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 545 | |
| 546 | if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V)) |
| 547 | return false; |
| 548 | |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 549 | LLVM_DEBUG(dbgs() << "ARM CGP: TryToPromote: " << *V << ", TypeSize = " |
| 550 | << TypeSize << "\n"); |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 551 | |
| 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 Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 581 | // Ignore non-instructions, other than arguments. |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 582 | 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 620 | LLVM_DEBUG(dbgs() << "ARM CGP: Visited nodes:\n"; |
| 621 | for (auto *I : CurrentVisited) |
| 622 | I->dump(); |
| 623 | ); |
Sam Parker | 7def86b | 2018-08-15 07:52:35 +0000 | [diff] [blame^] | 624 | 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 Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 635 | |
| 636 | Promoter->Mutate(OrigTy, CurrentVisited, Leaves, Roots); |
| 637 | return true; |
| 638 | } |
| 639 | |
| 640 | bool ARMCodeGenPrepare::doInitialization(Module &M) { |
| 641 | Promoter = new IRPromoter(&M); |
| 642 | return false; |
| 643 | } |
| 644 | |
| 645 | bool 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 Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 674 | if (auto *I = dyn_cast<Instruction>(Op)) |
| 675 | MadeChange |= TryToPromote(I); |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 676 | } |
| 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 Morehouse | a70685f | 2018-07-23 17:00:45 +0000 | [diff] [blame] | 691 | bool ARMCodeGenPrepare::doFinalization(Module &M) { |
| 692 | delete Promoter; |
| 693 | return false; |
| 694 | } |
| 695 | |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 696 | INITIALIZE_PASS_BEGIN(ARMCodeGenPrepare, DEBUG_TYPE, |
| 697 | "ARM IR optimizations", false, false) |
| 698 | INITIALIZE_PASS_END(ARMCodeGenPrepare, DEBUG_TYPE, "ARM IR optimizations", |
| 699 | false, false) |
| 700 | |
| 701 | char ARMCodeGenPrepare::ID = 0; |
Sam Parker | 8c4b964 | 2018-08-10 13:57:13 +0000 | [diff] [blame] | 702 | unsigned ARMCodeGenPrepare::TypeSize = 0; |
Sam Parker | 3828c6f | 2018-07-23 12:27:47 +0000 | [diff] [blame] | 703 | |
| 704 | FunctionPass *llvm::createARMCodeGenPreparePass() { |
| 705 | return new ARMCodeGenPrepare(); |
| 706 | } |