lib/Target/ARM64/ARM64AddressTypePromotion.cpp

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