1274955Ssvnmir//===-- AArch64AddressTypePromotion.cpp --- Promote type for addr accesses -==// 2274955Ssvnmir// 3274955Ssvnmir// The LLVM Compiler Infrastructure 4274955Ssvnmir// 5274955Ssvnmir// This file is distributed under the University of Illinois Open Source 6274955Ssvnmir// License. See LICENSE.TXT for details. 7274955Ssvnmir// 8274955Ssvnmir//===----------------------------------------------------------------------===// 9274955Ssvnmir// 10274955Ssvnmir// This pass tries to promote the computations use to obtained a sign extended 11274955Ssvnmir// value used into memory accesses. 12274955Ssvnmir// E.g. 13274955Ssvnmir// a = add nsw i32 b, 3 14274955Ssvnmir// d = sext i32 a to i64 15274955Ssvnmir// e = getelementptr ..., i64 d 16274955Ssvnmir// 17274955Ssvnmir// => 18274955Ssvnmir// f = sext i32 b to i64 19274955Ssvnmir// a = add nsw i64 f, 3 20274955Ssvnmir// e = getelementptr ..., i64 a 21274955Ssvnmir// 22280031Sdim// This is legal to do if the computations are marked with either nsw or nuw 23274955Ssvnmir// markers. 24274955Ssvnmir// Moreover, the current heuristic is simple: it does not create new sext 25274955Ssvnmir// operations, i.e., it gives up when a sext would have forked (e.g., if 26274955Ssvnmir// a = add i32 b, c, two sexts are required to promote the computation). 27274955Ssvnmir// 28274955Ssvnmir// FIXME: This pass may be useful for other targets too. 29274955Ssvnmir// ===---------------------------------------------------------------------===// 30274955Ssvnmir 31274955Ssvnmir#include "AArch64.h" 32274955Ssvnmir#include "llvm/ADT/DenseMap.h" 33274955Ssvnmir#include "llvm/ADT/SmallPtrSet.h" 34274955Ssvnmir#include "llvm/ADT/SmallVector.h" 35274955Ssvnmir#include "llvm/IR/Constants.h" 36274955Ssvnmir#include "llvm/IR/Dominators.h" 37274955Ssvnmir#include "llvm/IR/Function.h" 38274955Ssvnmir#include "llvm/IR/Instructions.h" 39274955Ssvnmir#include "llvm/IR/Module.h" 40274955Ssvnmir#include "llvm/IR/Operator.h" 41274955Ssvnmir#include "llvm/Pass.h" 42274955Ssvnmir#include "llvm/Support/CommandLine.h" 43274955Ssvnmir#include "llvm/Support/Debug.h" 44288943Sdim#include "llvm/Support/raw_ostream.h" 45274955Ssvnmir 46274955Ssvnmirusing namespace llvm; 47274955Ssvnmir 48274955Ssvnmir#define DEBUG_TYPE "aarch64-type-promotion" 49274955Ssvnmir 50274955Ssvnmirstatic cl::opt<bool> 51274955SsvnmirEnableAddressTypePromotion("aarch64-type-promotion", cl::Hidden, 52274955Ssvnmir cl::desc("Enable the type promotion pass"), 53274955Ssvnmir cl::init(true)); 54274955Ssvnmirstatic cl::opt<bool> 55274955SsvnmirEnableMerge("aarch64-type-promotion-merge", cl::Hidden, 56274955Ssvnmir cl::desc("Enable merging of redundant sexts when one is dominating" 57274955Ssvnmir " the other."), 58274955Ssvnmir cl::init(true)); 59274955Ssvnmir 60296417Sdim#define AARCH64_TYPE_PROMO_NAME "AArch64 Address Type Promotion" 61296417Sdim 62274955Ssvnmir//===----------------------------------------------------------------------===// 63274955Ssvnmir// AArch64AddressTypePromotion 64274955Ssvnmir//===----------------------------------------------------------------------===// 65274955Ssvnmir 66274955Ssvnmirnamespace llvm { 67274955Ssvnmirvoid initializeAArch64AddressTypePromotionPass(PassRegistry &); 68274955Ssvnmir} 69274955Ssvnmir 70274955Ssvnmirnamespace { 71274955Ssvnmirclass AArch64AddressTypePromotion : public FunctionPass { 72274955Ssvnmir 73274955Ssvnmirpublic: 74274955Ssvnmir static char ID; 75274955Ssvnmir AArch64AddressTypePromotion() 76274955Ssvnmir : FunctionPass(ID), Func(nullptr), ConsideredSExtType(nullptr) { 77274955Ssvnmir initializeAArch64AddressTypePromotionPass(*PassRegistry::getPassRegistry()); 78274955Ssvnmir } 79274955Ssvnmir 80274955Ssvnmir const char *getPassName() const override { 81296417Sdim return AARCH64_TYPE_PROMO_NAME; 82274955Ssvnmir } 83274955Ssvnmir 84274955Ssvnmir /// Iterate over the functions and promote the computation of interesting 85274955Ssvnmir // sext instructions. 86274955Ssvnmir bool runOnFunction(Function &F) override; 87274955Ssvnmir 88274955Ssvnmirprivate: 89274955Ssvnmir /// The current function. 90274955Ssvnmir Function *Func; 91274955Ssvnmir /// Filter out all sexts that does not have this type. 92274955Ssvnmir /// Currently initialized with Int64Ty. 93274955Ssvnmir Type *ConsideredSExtType; 94274955Ssvnmir 95274955Ssvnmir // This transformation requires dominator info. 96274955Ssvnmir void getAnalysisUsage(AnalysisUsage &AU) const override { 97274955Ssvnmir AU.setPreservesCFG(); 98274955Ssvnmir AU.addRequired<DominatorTreeWrapperPass>(); 99274955Ssvnmir AU.addPreserved<DominatorTreeWrapperPass>(); 100274955Ssvnmir FunctionPass::getAnalysisUsage(AU); 101274955Ssvnmir } 102274955Ssvnmir 103274955Ssvnmir typedef SmallPtrSet<Instruction *, 32> SetOfInstructions; 104274955Ssvnmir typedef SmallVector<Instruction *, 16> Instructions; 105274955Ssvnmir typedef DenseMap<Value *, Instructions> ValueToInsts; 106274955Ssvnmir 107274955Ssvnmir /// Check if it is profitable to move a sext through this instruction. 108274955Ssvnmir /// Currently, we consider it is profitable if: 109274955Ssvnmir /// - Inst is used only once (no need to insert truncate). 110274955Ssvnmir /// - Inst has only one operand that will require a sext operation (we do 111274955Ssvnmir /// do not create new sext operation). 112274955Ssvnmir bool shouldGetThrough(const Instruction *Inst); 113274955Ssvnmir 114274955Ssvnmir /// Check if it is possible and legal to move a sext through this 115274955Ssvnmir /// instruction. 116274955Ssvnmir /// Current heuristic considers that we can get through: 117274955Ssvnmir /// - Arithmetic operation marked with the nsw or nuw flag. 118274955Ssvnmir /// - Other sext operation. 119274955Ssvnmir /// - Truncate operation if it was just dropping sign extended bits. 120274955Ssvnmir bool canGetThrough(const Instruction *Inst); 121274955Ssvnmir 122274955Ssvnmir /// Move sext operations through safe to sext instructions. 123274955Ssvnmir bool propagateSignExtension(Instructions &SExtInsts); 124274955Ssvnmir 125274955Ssvnmir /// Is this sext should be considered for code motion. 126274955Ssvnmir /// We look for sext with ConsideredSExtType and uses in at least one 127274955Ssvnmir // GetElementPtrInst. 128274955Ssvnmir bool shouldConsiderSExt(const Instruction *SExt) const; 129274955Ssvnmir 130274955Ssvnmir /// Collect all interesting sext operations, i.e., the ones with the right 131274955Ssvnmir /// type and used in memory accesses. 132274955Ssvnmir /// More precisely, a sext instruction is considered as interesting if it 133274955Ssvnmir /// is used in a "complex" getelementptr or it exits at least another 134274955Ssvnmir /// sext instruction that sign extended the same initial value. 135274955Ssvnmir /// A getelementptr is considered as "complex" if it has more than 2 136274955Ssvnmir // operands. 137274955Ssvnmir void analyzeSExtension(Instructions &SExtInsts); 138274955Ssvnmir 139274955Ssvnmir /// Merge redundant sign extension operations in common dominator. 140274955Ssvnmir void mergeSExts(ValueToInsts &ValToSExtendedUses, 141274955Ssvnmir SetOfInstructions &ToRemove); 142274955Ssvnmir}; 143274955Ssvnmir} // end anonymous namespace. 144274955Ssvnmir 145274955Ssvnmirchar AArch64AddressTypePromotion::ID = 0; 146274955Ssvnmir 147274955SsvnmirINITIALIZE_PASS_BEGIN(AArch64AddressTypePromotion, "aarch64-type-promotion", 148296417Sdim AARCH64_TYPE_PROMO_NAME, false, false) 149274955SsvnmirINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 150274955SsvnmirINITIALIZE_PASS_END(AArch64AddressTypePromotion, "aarch64-type-promotion", 151296417Sdim AARCH64_TYPE_PROMO_NAME, false, false) 152274955Ssvnmir 153274955SsvnmirFunctionPass *llvm::createAArch64AddressTypePromotionPass() { 154274955Ssvnmir return new AArch64AddressTypePromotion(); 155274955Ssvnmir} 156274955Ssvnmir 157274955Ssvnmirbool AArch64AddressTypePromotion::canGetThrough(const Instruction *Inst) { 158274955Ssvnmir if (isa<SExtInst>(Inst)) 159274955Ssvnmir return true; 160274955Ssvnmir 161274955Ssvnmir const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst); 162274955Ssvnmir if (BinOp && isa<OverflowingBinaryOperator>(BinOp) && 163274955Ssvnmir (BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap())) 164274955Ssvnmir return true; 165274955Ssvnmir 166274955Ssvnmir // sext(trunc(sext)) --> sext 167274955Ssvnmir if (isa<TruncInst>(Inst) && isa<SExtInst>(Inst->getOperand(0))) { 168274955Ssvnmir const Instruction *Opnd = cast<Instruction>(Inst->getOperand(0)); 169274955Ssvnmir // Check that the truncate just drop sign extended bits. 170274955Ssvnmir if (Inst->getType()->getIntegerBitWidth() >= 171274955Ssvnmir Opnd->getOperand(0)->getType()->getIntegerBitWidth() && 172274955Ssvnmir Inst->getOperand(0)->getType()->getIntegerBitWidth() <= 173274955Ssvnmir ConsideredSExtType->getIntegerBitWidth()) 174274955Ssvnmir return true; 175274955Ssvnmir } 176274955Ssvnmir 177274955Ssvnmir return false; 178274955Ssvnmir} 179274955Ssvnmir 180274955Ssvnmirbool AArch64AddressTypePromotion::shouldGetThrough(const Instruction *Inst) { 181274955Ssvnmir // If the type of the sext is the same as the considered one, this sext 182274955Ssvnmir // will become useless. 183274955Ssvnmir // Otherwise, we will have to do something to preserve the original value, 184274955Ssvnmir // unless it is used once. 185274955Ssvnmir if (isa<SExtInst>(Inst) && 186274955Ssvnmir (Inst->getType() == ConsideredSExtType || Inst->hasOneUse())) 187274955Ssvnmir return true; 188274955Ssvnmir 189274955Ssvnmir // If the Inst is used more that once, we may need to insert truncate 190274955Ssvnmir // operations and we don't do that at the moment. 191274955Ssvnmir if (!Inst->hasOneUse()) 192274955Ssvnmir return false; 193274955Ssvnmir 194274955Ssvnmir // This truncate is used only once, thus if we can get thourgh, it will become 195274955Ssvnmir // useless. 196274955Ssvnmir if (isa<TruncInst>(Inst)) 197274955Ssvnmir return true; 198274955Ssvnmir 199274955Ssvnmir // If both operands are not constant, a new sext will be created here. 200274955Ssvnmir // Current heuristic is: each step should be profitable. 201274955Ssvnmir // Therefore we don't allow to increase the number of sext even if it may 202274955Ssvnmir // be profitable later on. 203274955Ssvnmir if (isa<BinaryOperator>(Inst) && isa<ConstantInt>(Inst->getOperand(1))) 204274955Ssvnmir return true; 205274955Ssvnmir 206274955Ssvnmir return false; 207274955Ssvnmir} 208274955Ssvnmir 209274955Ssvnmirstatic bool shouldSExtOperand(const Instruction *Inst, int OpIdx) { 210274955Ssvnmir if (isa<SelectInst>(Inst) && OpIdx == 0) 211274955Ssvnmir return false; 212274955Ssvnmir return true; 213274955Ssvnmir} 214274955Ssvnmir 215274955Ssvnmirbool 216274955SsvnmirAArch64AddressTypePromotion::shouldConsiderSExt(const Instruction *SExt) const { 217274955Ssvnmir if (SExt->getType() != ConsideredSExtType) 218274955Ssvnmir return false; 219274955Ssvnmir 220274955Ssvnmir for (const User *U : SExt->users()) { 221274955Ssvnmir if (isa<GetElementPtrInst>(U)) 222274955Ssvnmir return true; 223274955Ssvnmir } 224274955Ssvnmir 225274955Ssvnmir return false; 226274955Ssvnmir} 227274955Ssvnmir 228274955Ssvnmir// Input: 229280031Sdim// - SExtInsts contains all the sext instructions that are used directly in 230274955Ssvnmir// GetElementPtrInst, i.e., access to memory. 231274955Ssvnmir// Algorithm: 232274955Ssvnmir// - For each sext operation in SExtInsts: 233274955Ssvnmir// Let var be the operand of sext. 234274955Ssvnmir// while it is profitable (see shouldGetThrough), legal, and safe 235274955Ssvnmir// (see canGetThrough) to move sext through var's definition: 236274955Ssvnmir// * promote the type of var's definition. 237274955Ssvnmir// * fold var into sext uses. 238274955Ssvnmir// * move sext above var's definition. 239274955Ssvnmir// * update sext operand to use the operand of var that should be sign 240274955Ssvnmir// extended (by construction there is only one). 241274955Ssvnmir// 242274955Ssvnmir// E.g., 243274955Ssvnmir// a = ... i32 c, 3 244274955Ssvnmir// b = sext i32 a to i64 <- is it legal/safe/profitable to get through 'a' 245274955Ssvnmir// ... 246274955Ssvnmir// = b 247274955Ssvnmir// => Yes, update the code 248274955Ssvnmir// b = sext i32 c to i64 249274955Ssvnmir// a = ... i64 b, 3 250274955Ssvnmir// ... 251274955Ssvnmir// = a 252274955Ssvnmir// Iterate on 'c'. 253274955Ssvnmirbool 254274955SsvnmirAArch64AddressTypePromotion::propagateSignExtension(Instructions &SExtInsts) { 255274955Ssvnmir DEBUG(dbgs() << "*** Propagate Sign Extension ***\n"); 256274955Ssvnmir 257274955Ssvnmir bool LocalChange = false; 258274955Ssvnmir SetOfInstructions ToRemove; 259274955Ssvnmir ValueToInsts ValToSExtendedUses; 260274955Ssvnmir while (!SExtInsts.empty()) { 261274955Ssvnmir // Get through simple chain. 262274955Ssvnmir Instruction *SExt = SExtInsts.pop_back_val(); 263274955Ssvnmir 264274955Ssvnmir DEBUG(dbgs() << "Consider:\n" << *SExt << '\n'); 265274955Ssvnmir 266274955Ssvnmir // If this SExt has already been merged continue. 267274955Ssvnmir if (SExt->use_empty() && ToRemove.count(SExt)) { 268274955Ssvnmir DEBUG(dbgs() << "No uses => marked as delete\n"); 269274955Ssvnmir continue; 270274955Ssvnmir } 271274955Ssvnmir 272274955Ssvnmir // Now try to get through the chain of definitions. 273274955Ssvnmir while (auto *Inst = dyn_cast<Instruction>(SExt->getOperand(0))) { 274274955Ssvnmir DEBUG(dbgs() << "Try to get through:\n" << *Inst << '\n'); 275274955Ssvnmir if (!canGetThrough(Inst) || !shouldGetThrough(Inst)) { 276274955Ssvnmir // We cannot get through something that is not an Instruction 277274955Ssvnmir // or not safe to SExt. 278274955Ssvnmir DEBUG(dbgs() << "Cannot get through\n"); 279274955Ssvnmir break; 280274955Ssvnmir } 281274955Ssvnmir 282274955Ssvnmir LocalChange = true; 283274955Ssvnmir // If this is a sign extend, it becomes useless. 284274955Ssvnmir if (isa<SExtInst>(Inst) || isa<TruncInst>(Inst)) { 285274955Ssvnmir DEBUG(dbgs() << "SExt or trunc, mark it as to remove\n"); 286274955Ssvnmir // We cannot use replaceAllUsesWith here because we may trigger some 287274955Ssvnmir // assertion on the type as all involved sext operation may have not 288274955Ssvnmir // been moved yet. 289274955Ssvnmir while (!Inst->use_empty()) { 290274955Ssvnmir Use &U = *Inst->use_begin(); 291274955Ssvnmir Instruction *User = dyn_cast<Instruction>(U.getUser()); 292274955Ssvnmir assert(User && "User of sext is not an Instruction!"); 293274955Ssvnmir User->setOperand(U.getOperandNo(), SExt); 294274955Ssvnmir } 295274955Ssvnmir ToRemove.insert(Inst); 296274955Ssvnmir SExt->setOperand(0, Inst->getOperand(0)); 297274955Ssvnmir SExt->moveBefore(Inst); 298274955Ssvnmir continue; 299274955Ssvnmir } 300274955Ssvnmir 301274955Ssvnmir // Get through the Instruction: 302274955Ssvnmir // 1. Update its type. 303274955Ssvnmir // 2. Replace the uses of SExt by Inst. 304274955Ssvnmir // 3. Sign extend each operand that needs to be sign extended. 305274955Ssvnmir 306274955Ssvnmir // Step #1. 307274955Ssvnmir Inst->mutateType(SExt->getType()); 308274955Ssvnmir // Step #2. 309274955Ssvnmir SExt->replaceAllUsesWith(Inst); 310274955Ssvnmir // Step #3. 311274955Ssvnmir Instruction *SExtForOpnd = SExt; 312274955Ssvnmir 313274955Ssvnmir DEBUG(dbgs() << "Propagate SExt to operands\n"); 314274955Ssvnmir for (int OpIdx = 0, EndOpIdx = Inst->getNumOperands(); OpIdx != EndOpIdx; 315274955Ssvnmir ++OpIdx) { 316274955Ssvnmir DEBUG(dbgs() << "Operand:\n" << *(Inst->getOperand(OpIdx)) << '\n'); 317274955Ssvnmir if (Inst->getOperand(OpIdx)->getType() == SExt->getType() || 318274955Ssvnmir !shouldSExtOperand(Inst, OpIdx)) { 319274955Ssvnmir DEBUG(dbgs() << "No need to propagate\n"); 320274955Ssvnmir continue; 321274955Ssvnmir } 322274955Ssvnmir // Check if we can statically sign extend the operand. 323274955Ssvnmir Value *Opnd = Inst->getOperand(OpIdx); 324274955Ssvnmir if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) { 325274955Ssvnmir DEBUG(dbgs() << "Statically sign extend\n"); 326274955Ssvnmir Inst->setOperand(OpIdx, ConstantInt::getSigned(SExt->getType(), 327274955Ssvnmir Cst->getSExtValue())); 328274955Ssvnmir continue; 329274955Ssvnmir } 330274955Ssvnmir // UndefValue are typed, so we have to statically sign extend them. 331274955Ssvnmir if (isa<UndefValue>(Opnd)) { 332274955Ssvnmir DEBUG(dbgs() << "Statically sign extend\n"); 333274955Ssvnmir Inst->setOperand(OpIdx, UndefValue::get(SExt->getType())); 334274955Ssvnmir continue; 335274955Ssvnmir } 336274955Ssvnmir 337274955Ssvnmir // Otherwise we have to explicity sign extend it. 338274955Ssvnmir assert(SExtForOpnd && 339274955Ssvnmir "Only one operand should have been sign extended"); 340274955Ssvnmir 341274955Ssvnmir SExtForOpnd->setOperand(0, Opnd); 342274955Ssvnmir 343274955Ssvnmir DEBUG(dbgs() << "Move before:\n" << *Inst << "\nSign extend\n"); 344274955Ssvnmir // Move the sign extension before the insertion point. 345274955Ssvnmir SExtForOpnd->moveBefore(Inst); 346274955Ssvnmir Inst->setOperand(OpIdx, SExtForOpnd); 347274955Ssvnmir // If more sext are required, new instructions will have to be created. 348274955Ssvnmir SExtForOpnd = nullptr; 349274955Ssvnmir } 350274955Ssvnmir if (SExtForOpnd == SExt) { 351274955Ssvnmir DEBUG(dbgs() << "Sign extension is useless now\n"); 352274955Ssvnmir ToRemove.insert(SExt); 353274955Ssvnmir break; 354274955Ssvnmir } 355274955Ssvnmir } 356274955Ssvnmir 357274955Ssvnmir // If the use is already of the right type, connect its uses to its argument 358274955Ssvnmir // and delete it. 359280031Sdim // This can happen for an Instruction all uses of which are sign extended. 360274955Ssvnmir if (!ToRemove.count(SExt) && 361274955Ssvnmir SExt->getType() == SExt->getOperand(0)->getType()) { 362274955Ssvnmir DEBUG(dbgs() << "Sign extension is useless, attach its use to " 363274955Ssvnmir "its argument\n"); 364274955Ssvnmir SExt->replaceAllUsesWith(SExt->getOperand(0)); 365274955Ssvnmir ToRemove.insert(SExt); 366274955Ssvnmir } else 367274955Ssvnmir ValToSExtendedUses[SExt->getOperand(0)].push_back(SExt); 368274955Ssvnmir } 369274955Ssvnmir 370274955Ssvnmir if (EnableMerge) 371274955Ssvnmir mergeSExts(ValToSExtendedUses, ToRemove); 372274955Ssvnmir 373274955Ssvnmir // Remove all instructions marked as ToRemove. 374274955Ssvnmir for (Instruction *I: ToRemove) 375274955Ssvnmir I->eraseFromParent(); 376274955Ssvnmir return LocalChange; 377274955Ssvnmir} 378274955Ssvnmir 379274955Ssvnmirvoid AArch64AddressTypePromotion::mergeSExts(ValueToInsts &ValToSExtendedUses, 380274955Ssvnmir SetOfInstructions &ToRemove) { 381274955Ssvnmir DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 382274955Ssvnmir 383274955Ssvnmir for (auto &Entry : ValToSExtendedUses) { 384274955Ssvnmir Instructions &Insts = Entry.second; 385274955Ssvnmir Instructions CurPts; 386274955Ssvnmir for (Instruction *Inst : Insts) { 387274955Ssvnmir if (ToRemove.count(Inst)) 388274955Ssvnmir continue; 389274955Ssvnmir bool inserted = false; 390274955Ssvnmir for (auto &Pt : CurPts) { 391274955Ssvnmir if (DT.dominates(Inst, Pt)) { 392274955Ssvnmir DEBUG(dbgs() << "Replace all uses of:\n" << *Pt << "\nwith:\n" 393274955Ssvnmir << *Inst << '\n'); 394274955Ssvnmir Pt->replaceAllUsesWith(Inst); 395274955Ssvnmir ToRemove.insert(Pt); 396274955Ssvnmir Pt = Inst; 397274955Ssvnmir inserted = true; 398274955Ssvnmir break; 399274955Ssvnmir } 400274955Ssvnmir if (!DT.dominates(Pt, Inst)) 401274955Ssvnmir // Give up if we need to merge in a common dominator as the 402274955Ssvnmir // expermients show it is not profitable. 403274955Ssvnmir continue; 404274955Ssvnmir 405274955Ssvnmir DEBUG(dbgs() << "Replace all uses of:\n" << *Inst << "\nwith:\n" 406274955Ssvnmir << *Pt << '\n'); 407274955Ssvnmir Inst->replaceAllUsesWith(Pt); 408274955Ssvnmir ToRemove.insert(Inst); 409274955Ssvnmir inserted = true; 410274955Ssvnmir break; 411274955Ssvnmir } 412274955Ssvnmir if (!inserted) 413274955Ssvnmir CurPts.push_back(Inst); 414274955Ssvnmir } 415274955Ssvnmir } 416274955Ssvnmir} 417274955Ssvnmir 418274955Ssvnmirvoid AArch64AddressTypePromotion::analyzeSExtension(Instructions &SExtInsts) { 419274955Ssvnmir DEBUG(dbgs() << "*** Analyze Sign Extensions ***\n"); 420274955Ssvnmir 421274955Ssvnmir DenseMap<Value *, Instruction *> SeenChains; 422274955Ssvnmir 423274955Ssvnmir for (auto &BB : *Func) { 424274955Ssvnmir for (auto &II : BB) { 425274955Ssvnmir Instruction *SExt = &II; 426274955Ssvnmir 427274955Ssvnmir // Collect all sext operation per type. 428274955Ssvnmir if (!isa<SExtInst>(SExt) || !shouldConsiderSExt(SExt)) 429274955Ssvnmir continue; 430274955Ssvnmir 431274955Ssvnmir DEBUG(dbgs() << "Found:\n" << (*SExt) << '\n'); 432274955Ssvnmir 433274955Ssvnmir // Cases where we actually perform the optimization: 434274955Ssvnmir // 1. SExt is used in a getelementptr with more than 2 operand => 435274955Ssvnmir // likely we can merge some computation if they are done on 64 bits. 436274955Ssvnmir // 2. The beginning of the SExt chain is SExt several time. => 437274955Ssvnmir // code sharing is possible. 438274955Ssvnmir 439274955Ssvnmir bool insert = false; 440274955Ssvnmir // #1. 441274955Ssvnmir for (const User *U : SExt->users()) { 442274955Ssvnmir const Instruction *Inst = dyn_cast<GetElementPtrInst>(U); 443274955Ssvnmir if (Inst && Inst->getNumOperands() > 2) { 444274955Ssvnmir DEBUG(dbgs() << "Interesting use in GetElementPtrInst\n" << *Inst 445274955Ssvnmir << '\n'); 446274955Ssvnmir insert = true; 447274955Ssvnmir break; 448274955Ssvnmir } 449274955Ssvnmir } 450274955Ssvnmir 451274955Ssvnmir // #2. 452274955Ssvnmir // Check the head of the chain. 453274955Ssvnmir Instruction *Inst = SExt; 454274955Ssvnmir Value *Last; 455274955Ssvnmir do { 456274955Ssvnmir int OpdIdx = 0; 457274955Ssvnmir const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst); 458274955Ssvnmir if (BinOp && isa<ConstantInt>(BinOp->getOperand(0))) 459274955Ssvnmir OpdIdx = 1; 460274955Ssvnmir Last = Inst->getOperand(OpdIdx); 461274955Ssvnmir Inst = dyn_cast<Instruction>(Last); 462274955Ssvnmir } while (Inst && canGetThrough(Inst) && shouldGetThrough(Inst)); 463274955Ssvnmir 464274955Ssvnmir DEBUG(dbgs() << "Head of the chain:\n" << *Last << '\n'); 465274955Ssvnmir DenseMap<Value *, Instruction *>::iterator AlreadySeen = 466274955Ssvnmir SeenChains.find(Last); 467274955Ssvnmir if (insert || AlreadySeen != SeenChains.end()) { 468274955Ssvnmir DEBUG(dbgs() << "Insert\n"); 469274955Ssvnmir SExtInsts.push_back(SExt); 470274955Ssvnmir if (AlreadySeen != SeenChains.end() && AlreadySeen->second != nullptr) { 471274955Ssvnmir DEBUG(dbgs() << "Insert chain member\n"); 472274955Ssvnmir SExtInsts.push_back(AlreadySeen->second); 473274955Ssvnmir SeenChains[Last] = nullptr; 474274955Ssvnmir } 475274955Ssvnmir } else { 476274955Ssvnmir DEBUG(dbgs() << "Record its chain membership\n"); 477274955Ssvnmir SeenChains[Last] = SExt; 478274955Ssvnmir } 479274955Ssvnmir } 480274955Ssvnmir } 481274955Ssvnmir} 482274955Ssvnmir 483274955Ssvnmirbool AArch64AddressTypePromotion::runOnFunction(Function &F) { 484274955Ssvnmir if (!EnableAddressTypePromotion || F.isDeclaration()) 485274955Ssvnmir return false; 486274955Ssvnmir Func = &F; 487274955Ssvnmir ConsideredSExtType = Type::getInt64Ty(Func->getContext()); 488274955Ssvnmir 489274955Ssvnmir DEBUG(dbgs() << "*** " << getPassName() << ": " << Func->getName() << '\n'); 490274955Ssvnmir 491274955Ssvnmir Instructions SExtInsts; 492274955Ssvnmir analyzeSExtension(SExtInsts); 493274955Ssvnmir return propagateSignExtension(SExtInsts); 494274955Ssvnmir} 495