contrib/llvm/lib/Target/AArch64/AArch64AddressTypePromotion.cpp

   1 //===-- AArch64AddressTypePromotion.cpp --- Promote type for addr accesses -==//
   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 // This pass tries to promote the computations use to obtained a sign extended
  11 // value used into memory accesses.
  12 // E.g.
  13 // a = add nsw i32 b, 3
  14 // d = sext i32 a to i64
  15 // e = getelementptr ..., i64 d
  16 //
  17 // =>
  18 // f = sext i32 b to i64
  19 // a = add nsw i64 f, 3
  20 // e = getelementptr ..., i64 a
  21 //
  22 // This is legal to do if the computations are marked with either nsw or nuw
  23 // markers. Moreover, the current heuristic is simple: it does not create new
  24 // sext operations, i.e., it gives up when a sext would have forked (e.g., if a
  25 // = add i32 b, c, two sexts are required to promote the computation).
  26 //
  27 // FIXME: This pass may be useful for other targets too.
  28 // ===---------------------------------------------------------------------===//
  29
  30 #include "AArch64.h"
  31 #include "llvm/ADT/DenseMap.h"
  32 #include "llvm/ADT/SmallPtrSet.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/IR/Constants.h"
  35 #include "llvm/IR/Dominators.h"
  36 #include "llvm/IR/Function.h"
  37 #include "llvm/IR/Instructions.h"
  38 #include "llvm/IR/Module.h"
  39 #include "llvm/IR/Operator.h"
  40 #include "llvm/Pass.h"
  41 #include "llvm/Support/CommandLine.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/Support/raw_ostream.h"
  44
  45 using namespace llvm;
  46
  47 #define DEBUG_TYPE "aarch64-type-promotion"
  48
  49 static cl::opt<bool>
  50 EnableMerge("aarch64-type-promotion-merge", cl::Hidden,
  51             cl::desc("Enable merging of redundant sexts when one is dominating"
  52                      " the other."),
  53             cl::init(true));
  54
  55 #define AARCH64_TYPE_PROMO_NAME "AArch64 Address Type Promotion"
  56
  57 //===----------------------------------------------------------------------===//
  58 //                       AArch64AddressTypePromotion
  59 //===----------------------------------------------------------------------===//
  60
  61 namespace {
  62 class AArch64AddressTypePromotion : public FunctionPass {
  63
  64 public:
  65   static char ID;
  66   AArch64AddressTypePromotion()
  67       : FunctionPass(ID), Func(nullptr), ConsideredSExtType(nullptr) {
  68     initializeAArch64AddressTypePromotionPass(*PassRegistry::getPassRegistry());
  69   }
  70
  71   StringRef getPassName() const override { return AARCH64_TYPE_PROMO_NAME; }
  72
  73   /// Iterate over the functions and promote the computation of interesting
  74   // sext instructions.
  75   bool runOnFunction(Function &F) override;
  76
  77 private:
  78   /// The current function.
  79   Function *Func;
  80   /// Filter out all sexts that does not have this type.
  81   /// Currently initialized with Int64Ty.
  82   Type *ConsideredSExtType;
  83
  84   // This transformation requires dominator info.
  85   void getAnalysisUsage(AnalysisUsage &AU) const override {
  86     AU.setPreservesCFG();
  87     AU.addRequired<DominatorTreeWrapperPass>();
  88     AU.addPreserved<DominatorTreeWrapperPass>();
  89     FunctionPass::getAnalysisUsage(AU);
  90   }
  91
  92   typedef SmallPtrSet<Instruction *, 32> SetOfInstructions;
  93   typedef SmallVector<Instruction *, 16> Instructions;
  94   typedef DenseMap<Value *, Instructions> ValueToInsts;
  95
  96   /// Check if it is profitable to move a sext through this instruction.
  97   /// Currently, we consider it is profitable if:
  98   /// - Inst is used only once (no need to insert truncate).
  99   /// - Inst has only one operand that will require a sext operation (we do
 100   ///   do not create new sext operation).
 101   bool shouldGetThrough(const Instruction *Inst);
 102
 103   /// Check if it is possible and legal to move a sext through this
 104   /// instruction.
 105   /// Current heuristic considers that we can get through:
 106   /// - Arithmetic operation marked with the nsw or nuw flag.
 107   /// - Other sext operation.
 108   /// - Truncate operation if it was just dropping sign extended bits.
 109   bool canGetThrough(const Instruction *Inst);
 110
 111   /// Move sext operations through safe to sext instructions.
 112   bool propagateSignExtension(Instructions &SExtInsts);
 113
 114   /// Is this sext should be considered for code motion.
 115   /// We look for sext with ConsideredSExtType and uses in at least one
 116   // GetElementPtrInst.
 117   bool shouldConsiderSExt(const Instruction *SExt) const;
 118
 119   /// Collect all interesting sext operations, i.e., the ones with the right
 120   /// type and used in memory accesses.
 121   /// More precisely, a sext instruction is considered as interesting if it
 122   /// is used in a "complex" getelementptr or it exits at least another
 123   /// sext instruction that sign extended the same initial value.
 124   /// A getelementptr is considered as "complex" if it has more than 2
 125   // operands.
 126   void analyzeSExtension(Instructions &SExtInsts);
 127
 128   /// Merge redundant sign extension operations in common dominator.
 129   void mergeSExts(ValueToInsts &ValToSExtendedUses,
 130                   SetOfInstructions &ToRemove);
 131 };
 132 } // end anonymous namespace.
 133
 134 char AArch64AddressTypePromotion::ID = 0;
 135
 136 INITIALIZE_PASS_BEGIN(AArch64AddressTypePromotion, "aarch64-type-promotion",
 137                       AARCH64_TYPE_PROMO_NAME, false, false)
 138 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 139 INITIALIZE_PASS_END(AArch64AddressTypePromotion, "aarch64-type-promotion",
 140                     AARCH64_TYPE_PROMO_NAME, false, false)
 141
 142 FunctionPass *llvm::createAArch64AddressTypePromotionPass() {
 143   return new AArch64AddressTypePromotion();
 144 }
 145
 146 bool AArch64AddressTypePromotion::canGetThrough(const Instruction *Inst) {
 147   if (isa<SExtInst>(Inst))
 148     return true;
 149
 150   const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
 151   if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
 152       (BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap()))
 153     return true;
 154
 155   // sext(trunc(sext)) --> sext
 156   if (isa<TruncInst>(Inst) && isa<SExtInst>(Inst->getOperand(0))) {
 157     const Instruction *Opnd = cast<Instruction>(Inst->getOperand(0));
 158     // Check that the truncate just drop sign extended bits.
 159     if (Inst->getType()->getIntegerBitWidth() >=
 160             Opnd->getOperand(0)->getType()->getIntegerBitWidth() &&
 161         Inst->getOperand(0)->getType()->getIntegerBitWidth() <=
 162             ConsideredSExtType->getIntegerBitWidth())
 163       return true;
 164   }
 165
 166   return false;
 167 }
 168
 169 bool AArch64AddressTypePromotion::shouldGetThrough(const Instruction *Inst) {
 170   // If the type of the sext is the same as the considered one, this sext
 171   // will become useless.
 172   // Otherwise, we will have to do something to preserve the original value,
 173   // unless it is used once.
 174   if (isa<SExtInst>(Inst) &&
 175       (Inst->getType() == ConsideredSExtType || Inst->hasOneUse()))
 176     return true;
 177
 178   // If the Inst is used more that once, we may need to insert truncate
 179   // operations and we don't do that at the moment.
 180   if (!Inst->hasOneUse())
 181     return false;
 182
 183   // This truncate is used only once, thus if we can get thourgh, it will become
 184   // useless.
 185   if (isa<TruncInst>(Inst))
 186     return true;
 187
 188   // If both operands are not constant, a new sext will be created here.
 189   // Current heuristic is: each step should be profitable.
 190   // Therefore we don't allow to increase the number of sext even if it may
 191   // be profitable later on.
 192   if (isa<BinaryOperator>(Inst) && isa<ConstantInt>(Inst->getOperand(1)))
 193     return true;
 194
 195   return false;
 196 }
 197
 198 static bool shouldSExtOperand(const Instruction *Inst, int OpIdx) {
 199   return !(isa<SelectInst>(Inst) && OpIdx == 0);
 200 }
 201
 202 bool
 203 AArch64AddressTypePromotion::shouldConsiderSExt(const Instruction *SExt) const {
 204   if (SExt->getType() != ConsideredSExtType)
 205     return false;
 206
 207   for (const User *U : SExt->users()) {
 208     if (isa<GetElementPtrInst>(U))
 209       return true;
 210   }
 211
 212   return false;
 213 }
 214
 215 // Input:
 216 // - SExtInsts contains all the sext instructions that are used directly in
 217 //   GetElementPtrInst, i.e., access to memory.
 218 // Algorithm:
 219 // - For each sext operation in SExtInsts:
 220 //   Let var be the operand of sext.
 221 //   while it is profitable (see shouldGetThrough), legal, and safe
 222 //   (see canGetThrough) to move sext through var's definition:
 223 //   * promote the type of var's definition.
 224 //   * fold var into sext uses.
 225 //   * move sext above var's definition.
 226 //   * update sext operand to use the operand of var that should be sign
 227 //     extended (by construction there is only one).
 228 //
 229 //   E.g.,
 230 //   a = ... i32 c, 3
 231 //   b = sext i32 a to i64 <- is it legal/safe/profitable to get through 'a'
 232 //   ...
 233 //   = b
 234 // => Yes, update the code
 235 //   b = sext i32 c to i64
 236 //   a = ... i64 b, 3
 237 //   ...
 238 //   = a
 239 // Iterate on 'c'.
 240 bool
 241 AArch64AddressTypePromotion::propagateSignExtension(Instructions &SExtInsts) {
 242   DEBUG(dbgs() << "*** Propagate Sign Extension ***\n");
 243
 244   bool LocalChange = false;
 245   SetOfInstructions ToRemove;
 246   ValueToInsts ValToSExtendedUses;
 247   while (!SExtInsts.empty()) {
 248     // Get through simple chain.
 249     Instruction *SExt = SExtInsts.pop_back_val();
 250
 251     DEBUG(dbgs() << "Consider:\n" << *SExt << '\n');
 252
 253     // If this SExt has already been merged continue.
 254     if (SExt->use_empty() && ToRemove.count(SExt)) {
 255       DEBUG(dbgs() << "No uses => marked as delete\n");
 256       continue;
 257     }
 258
 259     // Now try to get through the chain of definitions.
 260     while (auto *Inst = dyn_cast<Instruction>(SExt->getOperand(0))) {
 261       DEBUG(dbgs() << "Try to get through:\n" << *Inst << '\n');
 262       if (!canGetThrough(Inst) || !shouldGetThrough(Inst)) {
 263         // We cannot get through something that is not an Instruction
 264         // or not safe to SExt.
 265         DEBUG(dbgs() << "Cannot get through\n");
 266         break;
 267       }
 268
 269       LocalChange = true;
 270       // If this is a sign extend, it becomes useless.
 271       if (isa<SExtInst>(Inst) || isa<TruncInst>(Inst)) {
 272         DEBUG(dbgs() << "SExt or trunc, mark it as to remove\n");
 273         // We cannot use replaceAllUsesWith here because we may trigger some
 274         // assertion on the type as all involved sext operation may have not
 275         // been moved yet.
 276         while (!Inst->use_empty()) {
 277           Use &U = *Inst->use_begin();
 278           Instruction *User = dyn_cast<Instruction>(U.getUser());
 279           assert(User && "User of sext is not an Instruction!");
 280           User->setOperand(U.getOperandNo(), SExt);
 281         }
 282         ToRemove.insert(Inst);
 283         SExt->setOperand(0, Inst->getOperand(0));
 284         SExt->moveBefore(Inst);
 285         continue;
 286       }
 287
 288       // Get through the Instruction:
 289       // 1. Update its type.
 290       // 2. Replace the uses of SExt by Inst.
 291       // 3. Sign extend each operand that needs to be sign extended.
 292
 293       // Step #1.
 294       Inst->mutateType(SExt->getType());
 295       // Step #2.
 296       SExt->replaceAllUsesWith(Inst);
 297       // Step #3.
 298       Instruction *SExtForOpnd = SExt;
 299
 300       DEBUG(dbgs() << "Propagate SExt to operands\n");
 301       for (int OpIdx = 0, EndOpIdx = Inst->getNumOperands(); OpIdx != EndOpIdx;
 302            ++OpIdx) {
 303         DEBUG(dbgs() << "Operand:\n" << *(Inst->getOperand(OpIdx)) << '\n');
 304         if (Inst->getOperand(OpIdx)->getType() == SExt->getType() ||
 305             !shouldSExtOperand(Inst, OpIdx)) {
 306           DEBUG(dbgs() << "No need to propagate\n");
 307           continue;
 308         }
 309         // Check if we can statically sign extend the operand.
 310         Value *Opnd = Inst->getOperand(OpIdx);
 311         if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
 312           DEBUG(dbgs() << "Statically sign extend\n");
 313           Inst->setOperand(OpIdx, ConstantInt::getSigned(SExt->getType(),
 314                                                          Cst->getSExtValue()));
 315           continue;
 316         }
 317         // UndefValue are typed, so we have to statically sign extend them.
 318         if (isa<UndefValue>(Opnd)) {
 319           DEBUG(dbgs() << "Statically sign extend\n");
 320           Inst->setOperand(OpIdx, UndefValue::get(SExt->getType()));
 321           continue;
 322         }
 323
 324         // Otherwise we have to explicity sign extend it.
 325         assert(SExtForOpnd &&
 326                "Only one operand should have been sign extended");
 327
 328         SExtForOpnd->setOperand(0, Opnd);
 329
 330         DEBUG(dbgs() << "Move before:\n" << *Inst << "\nSign extend\n");
 331         // Move the sign extension before the insertion point.
 332         SExtForOpnd->moveBefore(Inst);
 333         Inst->setOperand(OpIdx, SExtForOpnd);
 334         // If more sext are required, new instructions will have to be created.
 335         SExtForOpnd = nullptr;
 336       }
 337       if (SExtForOpnd == SExt) {
 338         DEBUG(dbgs() << "Sign extension is useless now\n");
 339         ToRemove.insert(SExt);
 340         break;
 341       }
 342     }
 343
 344     // If the use is already of the right type, connect its uses to its argument
 345     // and delete it.
 346     // This can happen for an Instruction all uses of which are sign extended.
 347     if (!ToRemove.count(SExt) &&
 348         SExt->getType() == SExt->getOperand(0)->getType()) {
 349       DEBUG(dbgs() << "Sign extension is useless, attach its use to "
 350                       "its argument\n");
 351       SExt->replaceAllUsesWith(SExt->getOperand(0));
 352       ToRemove.insert(SExt);
 353     } else
 354       ValToSExtendedUses[SExt->getOperand(0)].push_back(SExt);
 355   }
 356
 357   if (EnableMerge)
 358     mergeSExts(ValToSExtendedUses, ToRemove);
 359
 360   // Remove all instructions marked as ToRemove.
 361   for (Instruction *I: ToRemove)
 362     I->eraseFromParent();
 363   return LocalChange;
 364 }
 365
 366 void AArch64AddressTypePromotion::mergeSExts(ValueToInsts &ValToSExtendedUses,
 367                                              SetOfInstructions &ToRemove) {
 368   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 369
 370   for (auto &Entry : ValToSExtendedUses) {
 371     Instructions &Insts = Entry.second;
 372     Instructions CurPts;
 373     for (Instruction *Inst : Insts) {
 374       if (ToRemove.count(Inst))
 375         continue;
 376       bool inserted = false;
 377       for (auto &Pt : CurPts) {
 378         if (DT.dominates(Inst, Pt)) {
 379           DEBUG(dbgs() << "Replace all uses of:\n" << *Pt << "\nwith:\n"
 380                        << *Inst << '\n');
 381           Pt->replaceAllUsesWith(Inst);
 382           ToRemove.insert(Pt);
 383           Pt = Inst;
 384           inserted = true;
 385           break;
 386         }
 387         if (!DT.dominates(Pt, Inst))
 388           // Give up if we need to merge in a common dominator as the
 389           // expermients show it is not profitable.
 390           continue;
 391
 392         DEBUG(dbgs() << "Replace all uses of:\n" << *Inst << "\nwith:\n"
 393                      << *Pt << '\n');
 394         Inst->replaceAllUsesWith(Pt);
 395         ToRemove.insert(Inst);
 396         inserted = true;
 397         break;
 398       }
 399       if (!inserted)
 400         CurPts.push_back(Inst);
 401     }
 402   }
 403 }
 404
 405 void AArch64AddressTypePromotion::analyzeSExtension(Instructions &SExtInsts) {
 406   DEBUG(dbgs() << "*** Analyze Sign Extensions ***\n");
 407
 408   DenseMap<Value *, Instruction *> SeenChains;
 409
 410   for (auto &BB : *Func) {
 411     for (auto &II : BB) {
 412       Instruction *SExt = &II;
 413
 414       // Collect all sext operation per type.
 415       if (!isa<SExtInst>(SExt) || !shouldConsiderSExt(SExt))
 416         continue;
 417
 418       DEBUG(dbgs() << "Found:\n" << (*SExt) << '\n');
 419
 420       // Cases where we actually perform the optimization:
 421       // 1. SExt is used in a getelementptr with more than 2 operand =>
 422       //    likely we can merge some computation if they are done on 64 bits.
 423       // 2. The beginning of the SExt chain is SExt several time. =>
 424       //    code sharing is possible.
 425
 426       bool insert = false;
 427       // #1.
 428       for (const User *U : SExt->users()) {
 429         const Instruction *Inst = dyn_cast<GetElementPtrInst>(U);
 430         if (Inst && Inst->getNumOperands() > 2) {
 431           DEBUG(dbgs() << "Interesting use in GetElementPtrInst\n" << *Inst
 432                        << '\n');
 433           insert = true;
 434           break;
 435         }
 436       }
 437
 438       // #2.
 439       // Check the head of the chain.
 440       Instruction *Inst = SExt;
 441       Value *Last;
 442       do {
 443         int OpdIdx = 0;
 444         const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
 445         if (BinOp && isa<ConstantInt>(BinOp->getOperand(0)))
 446           OpdIdx = 1;
 447         Last = Inst->getOperand(OpdIdx);
 448         Inst = dyn_cast<Instruction>(Last);
 449       } while (Inst && canGetThrough(Inst) && shouldGetThrough(Inst));
 450
 451       DEBUG(dbgs() << "Head of the chain:\n" << *Last << '\n');
 452       DenseMap<Value *, Instruction *>::iterator AlreadySeen =
 453           SeenChains.find(Last);
 454       if (insert || AlreadySeen != SeenChains.end()) {
 455         DEBUG(dbgs() << "Insert\n");
 456         SExtInsts.push_back(SExt);
 457         if (AlreadySeen != SeenChains.end() && AlreadySeen->second != nullptr) {
 458           DEBUG(dbgs() << "Insert chain member\n");
 459           SExtInsts.push_back(AlreadySeen->second);
 460           SeenChains[Last] = nullptr;
 461         }
 462       } else {
 463         DEBUG(dbgs() << "Record its chain membership\n");
 464         SeenChains[Last] = SExt;
 465       }
 466     }
 467   }
 468 }
 469
 470 bool AArch64AddressTypePromotion::runOnFunction(Function &F) {
 471   if (skipFunction(F))
 472     return false;
 473
 474   if (F.isDeclaration())
 475     return false;
 476   Func = &F;
 477   ConsideredSExtType = Type::getInt64Ty(Func->getContext());
 478
 479   DEBUG(dbgs() << "*** " << getPassName() << ": " << Func->getName() << '\n');
 480
 481   Instructions SExtInsts;
 482   analyzeSExtension(SExtInsts);
 483   return propagateSignExtension(SExtInsts);
 484 }