1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===-- AArch64AddressTypePromotion.cpp --- Promote type for addr accesses -==// 236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The LLVM Compiler Infrastructure 436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file is distributed under the University of Illinois Open Source 636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// License. See LICENSE.TXT for details. 736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This pass tries to promote the computations use to obtained a sign extended 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// value used into memory accesses. 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// E.g. 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// a = add nsw i32 b, 3 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// d = sext i32 a to i64 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// e = getelementptr ..., i64 d 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// => 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// f = sext i32 b to i64 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// a = add nsw i64 f, 3 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// e = getelementptr ..., i64 a 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 2237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// This is legal to do if the computations are marked with either nsw or nuw 23de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// markers. Moreover, the current heuristic is simple: it does not create new 24de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// sext operations, i.e., it gives up when a sext would have forked (e.g., if a 25de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// = add i32 b, c, two sexts are required to promote the computation). 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// FIXME: This pass may be useful for other targets too. 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// ===---------------------------------------------------------------------===// 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "AArch64.h" 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/DenseMap.h" 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallPtrSet.h" 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallVector.h" 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Constants.h" 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Function.h" 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Instructions.h" 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Module.h" 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Operator.h" 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Pass.h" 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/CommandLine.h" 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/Debug.h" 434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Support/raw_ostream.h" 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesusing namespace llvm; 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "aarch64-type-promotion" 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic cl::opt<bool> 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesEnableAddressTypePromotion("aarch64-type-promotion", cl::Hidden, 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Enable the type promotion pass"), 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::init(true)); 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic cl::opt<bool> 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesEnableMerge("aarch64-type-promotion-merge", cl::Hidden, 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Enable merging of redundant sexts when one is dominating" 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines " the other."), 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::init(true)); 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 59f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#define AARCH64_TYPE_PROMO_NAME "AArch64 Address Type Promotion" 60f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// AArch64AddressTypePromotion 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace llvm { 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid initializeAArch64AddressTypePromotionPass(PassRegistry &); 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace { 70dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesclass AArch64AddressTypePromotion : public FunctionPass { 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static char ID; 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AArch64AddressTypePromotion() 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : FunctionPass(ID), Func(nullptr), ConsideredSExtType(nullptr) { 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines initializeAArch64AddressTypePromotionPass(*PassRegistry::getPassRegistry()); 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *getPassName() const override { 80f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AARCH64_TYPE_PROMO_NAME; 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Iterate over the functions and promote the computation of interesting 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // sext instructions. 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runOnFunction(Function &F) override; 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprivate: 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The current function. 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Function *Func; 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Filter out all sexts that does not have this type. 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Currently initialized with Int64Ty. 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *ConsideredSExtType; 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // This transformation requires dominator info. 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.setPreservesCFG(); 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<DominatorTreeWrapperPass>(); 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionPass::getAnalysisUsage(AU); 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef SmallPtrSet<Instruction *, 32> SetOfInstructions; 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef SmallVector<Instruction *, 16> Instructions; 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef DenseMap<Value *, Instructions> ValueToInsts; 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Check if it is profitable to move a sext through this instruction. 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Currently, we consider it is profitable if: 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// - Inst is used only once (no need to insert truncate). 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// - Inst has only one operand that will require a sext operation (we do 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// do not create new sext operation). 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool shouldGetThrough(const Instruction *Inst); 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Check if it is possible and legal to move a sext through this 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// instruction. 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Current heuristic considers that we can get through: 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// - Arithmetic operation marked with the nsw or nuw flag. 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// - Other sext operation. 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// - Truncate operation if it was just dropping sign extended bits. 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool canGetThrough(const Instruction *Inst); 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Move sext operations through safe to sext instructions. 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool propagateSignExtension(Instructions &SExtInsts); 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Is this sext should be considered for code motion. 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// We look for sext with ConsideredSExtType and uses in at least one 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // GetElementPtrInst. 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool shouldConsiderSExt(const Instruction *SExt) const; 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Collect all interesting sext operations, i.e., the ones with the right 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// type and used in memory accesses. 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// More precisely, a sext instruction is considered as interesting if it 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// is used in a "complex" getelementptr or it exits at least another 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// sext instruction that sign extended the same initial value. 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// A getelementptr is considered as "complex" if it has more than 2 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // operands. 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void analyzeSExtension(Instructions &SExtInsts); 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Merge redundant sign extension operations in common dominator. 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void mergeSExts(ValueToInsts &ValToSExtendedUses, 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SetOfInstructions &ToRemove); 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} // end anonymous namespace. 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar AArch64AddressTypePromotion::ID = 0; 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesINITIALIZE_PASS_BEGIN(AArch64AddressTypePromotion, "aarch64-type-promotion", 147f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AARCH64_TYPE_PROMO_NAME, false, false) 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesINITIALIZE_PASS_END(AArch64AddressTypePromotion, "aarch64-type-promotion", 150f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AARCH64_TYPE_PROMO_NAME, false, false) 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 152dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesFunctionPass *llvm::createAArch64AddressTypePromotionPass() { 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return new AArch64AddressTypePromotion(); 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AArch64AddressTypePromotion::canGetThrough(const Instruction *Inst) { 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<SExtInst>(Inst)) 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst); 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BinOp && isa<OverflowingBinaryOperator>(BinOp) && 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap())) 16336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // sext(trunc(sext)) --> sext 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<TruncInst>(Inst) && isa<SExtInst>(Inst->getOperand(0))) { 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Instruction *Opnd = cast<Instruction>(Inst->getOperand(0)); 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Check that the truncate just drop sign extended bits. 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Inst->getType()->getIntegerBitWidth() >= 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Opnd->getOperand(0)->getType()->getIntegerBitWidth() && 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst->getOperand(0)->getType()->getIntegerBitWidth() <= 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConsideredSExtType->getIntegerBitWidth()) 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 179dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AArch64AddressTypePromotion::shouldGetThrough(const Instruction *Inst) { 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If the type of the sext is the same as the considered one, this sext 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // will become useless. 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Otherwise, we will have to do something to preserve the original value, 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // unless it is used once. 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<SExtInst>(Inst) && 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (Inst->getType() == ConsideredSExtType || Inst->hasOneUse())) 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If the Inst is used more that once, we may need to insert truncate 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // operations and we don't do that at the moment. 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!Inst->hasOneUse()) 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // This truncate is used only once, thus if we can get thourgh, it will become 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // useless. 19536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<TruncInst>(Inst)) 19636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 19736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If both operands are not constant, a new sext will be created here. 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Current heuristic is: each step should be profitable. 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Therefore we don't allow to increase the number of sext even if it may 20136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // be profitable later on. 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<BinaryOperator>(Inst) && isa<ConstantInt>(Inst->getOperand(1))) 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 20736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool shouldSExtOperand(const Instruction *Inst, int OpIdx) { 209de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return !(isa<SelectInst>(Inst) && OpIdx == 0); 21036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 21136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesAArch64AddressTypePromotion::shouldConsiderSExt(const Instruction *SExt) const { 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SExt->getType() != ConsideredSExtType) 21536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 217c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines for (const User *U : SExt->users()) { 218c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (isa<GetElementPtrInst>(U)) 21936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 22436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Input: 22637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// - SExtInsts contains all the sext instructions that are used directly in 22736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// GetElementPtrInst, i.e., access to memory. 22836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Algorithm: 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// - For each sext operation in SExtInsts: 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Let var be the operand of sext. 23136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// while it is profitable (see shouldGetThrough), legal, and safe 23236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// (see canGetThrough) to move sext through var's definition: 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// * promote the type of var's definition. 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// * fold var into sext uses. 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// * move sext above var's definition. 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// * update sext operand to use the operand of var that should be sign 23736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// extended (by construction there is only one). 23836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// E.g., 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// a = ... i32 c, 3 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// b = sext i32 a to i64 <- is it legal/safe/profitable to get through 'a' 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// ... 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// = b 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// => Yes, update the code 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// b = sext i32 c to i64 24636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// a = ... i64 b, 3 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// ... 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// = a 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Iterate on 'c'. 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool 251dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesAArch64AddressTypePromotion::propagateSignExtension(Instructions &SExtInsts) { 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "*** Propagate Sign Extension ***\n"); 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool LocalChange = false; 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SetOfInstructions ToRemove; 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ValueToInsts ValToSExtendedUses; 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (!SExtInsts.empty()) { 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Get through simple chain. 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *SExt = SExtInsts.pop_back_val(); 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Consider:\n" << *SExt << '\n'); 26236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If this SExt has already been merged continue. 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SExt->use_empty() && ToRemove.count(SExt)) { 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "No uses => marked as delete\n"); 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 26836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Now try to get through the chain of definitions. 270c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines while (auto *Inst = dyn_cast<Instruction>(SExt->getOperand(0))) { 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Try to get through:\n" << *Inst << '\n'); 27236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!canGetThrough(Inst) || !shouldGetThrough(Inst)) { 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We cannot get through something that is not an Instruction 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // or not safe to SExt. 27536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Cannot get through\n"); 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LocalChange = true; 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If this is a sign extend, it becomes useless. 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<SExtInst>(Inst) || isa<TruncInst>(Inst)) { 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "SExt or trunc, mark it as to remove\n"); 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We cannot use replaceAllUsesWith here because we may trigger some 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // assertion on the type as all involved sext operation may have not 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // been moved yet. 28636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (!Inst->use_empty()) { 287c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Use &U = *Inst->use_begin(); 288c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Instruction *User = dyn_cast<Instruction>(U.getUser()); 289c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines assert(User && "User of sext is not an Instruction!"); 290c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines User->setOperand(U.getOperandNo(), SExt); 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ToRemove.insert(Inst); 29336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExt->setOperand(0, Inst->getOperand(0)); 29436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExt->moveBefore(Inst); 29536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 29736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Get through the Instruction: 29936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 1. Update its type. 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 2. Replace the uses of SExt by Inst. 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 3. Sign extend each operand that needs to be sign extended. 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Step #1. 30436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst->mutateType(SExt->getType()); 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Step #2. 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExt->replaceAllUsesWith(Inst); 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Step #3. 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *SExtForOpnd = SExt; 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 31036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Propagate SExt to operands\n"); 31136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (int OpIdx = 0, EndOpIdx = Inst->getNumOperands(); OpIdx != EndOpIdx; 31236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++OpIdx) { 31336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Operand:\n" << *(Inst->getOperand(OpIdx)) << '\n'); 31436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Inst->getOperand(OpIdx)->getType() == SExt->getType() || 31536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines !shouldSExtOperand(Inst, OpIdx)) { 31636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "No need to propagate\n"); 31736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 31836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 31936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Check if we can statically sign extend the operand. 32036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Opnd = Inst->getOperand(OpIdx); 32136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) { 32236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Statically sign extend\n"); 32336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst->setOperand(OpIdx, ConstantInt::getSigned(SExt->getType(), 32436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Cst->getSExtValue())); 32536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 32636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 32736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // UndefValue are typed, so we have to statically sign extend them. 32836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<UndefValue>(Opnd)) { 32936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Statically sign extend\n"); 33036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst->setOperand(OpIdx, UndefValue::get(SExt->getType())); 33136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 33236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 33336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Otherwise we have to explicity sign extend it. 33536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(SExtForOpnd && 33636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Only one operand should have been sign extended"); 33736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExtForOpnd->setOperand(0, Opnd); 33936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 34036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Move before:\n" << *Inst << "\nSign extend\n"); 34136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Move the sign extension before the insertion point. 34236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExtForOpnd->moveBefore(Inst); 34336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst->setOperand(OpIdx, SExtForOpnd); 34436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If more sext are required, new instructions will have to be created. 345dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SExtForOpnd = nullptr; 34636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 34736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SExtForOpnd == SExt) { 34836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Sign extension is useless now\n"); 34936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ToRemove.insert(SExt); 35036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 35136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 35236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 35336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 35436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If the use is already of the right type, connect its uses to its argument 35536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // and delete it. 35637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // This can happen for an Instruction all uses of which are sign extended. 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!ToRemove.count(SExt) && 35836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExt->getType() == SExt->getOperand(0)->getType()) { 35936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Sign extension is useless, attach its use to " 36036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "its argument\n"); 36136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExt->replaceAllUsesWith(SExt->getOperand(0)); 36236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ToRemove.insert(SExt); 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else 36436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ValToSExtendedUses[SExt->getOperand(0)].push_back(SExt); 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 36636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (EnableMerge) 36836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines mergeSExts(ValToSExtendedUses, ToRemove); 36936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 37036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Remove all instructions marked as ToRemove. 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Instruction *I: ToRemove) 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I->eraseFromParent(); 37336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return LocalChange; 37436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 37536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 376dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid AArch64AddressTypePromotion::mergeSExts(ValueToInsts &ValToSExtendedUses, 377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SetOfInstructions &ToRemove) { 37836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 37936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &Entry : ValToSExtendedUses) { 38136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instructions &Insts = Entry.second; 38236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instructions CurPts; 38336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Instruction *Inst : Insts) { 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ToRemove.count(Inst)) 38536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 38636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool inserted = false; 387c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines for (auto &Pt : CurPts) { 38836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DT.dominates(Inst, Pt)) { 38936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Replace all uses of:\n" << *Pt << "\nwith:\n" 39036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << *Inst << '\n'); 391c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Pt->replaceAllUsesWith(Inst); 39236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ToRemove.insert(Pt); 39336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Pt = Inst; 39436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines inserted = true; 39536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 39636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 39736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!DT.dominates(Pt, Inst)) 39836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Give up if we need to merge in a common dominator as the 39936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // expermients show it is not profitable. 40036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 40136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 40236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Replace all uses of:\n" << *Inst << "\nwith:\n" 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << *Pt << '\n'); 40436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst->replaceAllUsesWith(Pt); 40536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ToRemove.insert(Inst); 40636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines inserted = true; 40736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 40836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 40936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!inserted) 41036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CurPts.push_back(Inst); 41136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 41236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 41336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 41436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 415dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid AArch64AddressTypePromotion::analyzeSExtension(Instructions &SExtInsts) { 41636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "*** Analyze Sign Extensions ***\n"); 41736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 41836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DenseMap<Value *, Instruction *> SeenChains; 41936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 42036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (auto &BB : *Func) { 421dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &II : BB) { 42236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *SExt = &II; 42336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 42436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Collect all sext operation per type. 42536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!isa<SExtInst>(SExt) || !shouldConsiderSExt(SExt)) 42636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 42736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 42836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Found:\n" << (*SExt) << '\n'); 42936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 43036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Cases where we actually perform the optimization: 43136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 1. SExt is used in a getelementptr with more than 2 operand => 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // likely we can merge some computation if they are done on 64 bits. 43336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 2. The beginning of the SExt chain is SExt several time. => 43436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // code sharing is possible. 43536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool insert = false; 43736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // #1. 438c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines for (const User *U : SExt->users()) { 439dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const Instruction *Inst = dyn_cast<GetElementPtrInst>(U); 44036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Inst && Inst->getNumOperands() > 2) { 44136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Interesting use in GetElementPtrInst\n" << *Inst 44236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << '\n'); 44336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines insert = true; 44436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 44536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 44636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 44736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 44836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // #2. 44936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Check the head of the chain. 45036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *Inst = SExt; 45136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Last; 45236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines do { 45336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines int OpdIdx = 0; 45436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst); 45536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BinOp && isa<ConstantInt>(BinOp->getOperand(0))) 45636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OpdIdx = 1; 45736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Last = Inst->getOperand(OpdIdx); 45836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst = dyn_cast<Instruction>(Last); 45936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } while (Inst && canGetThrough(Inst) && shouldGetThrough(Inst)); 46036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 46136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Head of the chain:\n" << *Last << '\n'); 46236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DenseMap<Value *, Instruction *>::iterator AlreadySeen = 46336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SeenChains.find(Last); 46436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (insert || AlreadySeen != SeenChains.end()) { 46536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Insert\n"); 46636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExtInsts.push_back(SExt); 467dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (AlreadySeen != SeenChains.end() && AlreadySeen->second != nullptr) { 46836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Insert chain member\n"); 46936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SExtInsts.push_back(AlreadySeen->second); 470dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SeenChains[Last] = nullptr; 47136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 47236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 47336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Record its chain membership\n"); 47436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SeenChains[Last] = SExt; 47536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 47636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 47736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 47836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 47936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 480dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AArch64AddressTypePromotion::runOnFunction(Function &F) { 481de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (skipFunction(F)) 482de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 483de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 48436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!EnableAddressTypePromotion || F.isDeclaration()) 48536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 48636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Func = &F; 48736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConsideredSExtType = Type::getInt64Ty(Func->getContext()); 48836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 48936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "*** " << getPassName() << ": " << Func->getName() << '\n'); 49036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instructions SExtInsts; 49236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines analyzeSExtension(SExtInsts); 49336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return propagateSignExtension(SExtInsts); 49436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 495