llvm/lib/Analysis/PHITransAddr.cpp

   1 //===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the PHITransAddr class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Analysis/PHITransAddr.h"
  14 #include "llvm/Analysis/InstructionSimplify.h"
  15 #include "llvm/Analysis/ValueTracking.h"
  16 #include "llvm/Config/llvm-config.h"
  17 #include "llvm/IR/Constants.h"
  18 #include "llvm/IR/Dominators.h"
  19 #include "llvm/IR/Instructions.h"
  20 #include "llvm/Support/CommandLine.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 using namespace llvm;
  24
  25 static cl::opt<bool> EnableAddPhiTranslation(
  26     "gvn-add-phi-translation", cl::init(false), cl::Hidden,
  27     cl::desc("Enable phi-translation of add instructions"));
  28
  29 static bool canPHITrans(Instruction *Inst) {
  30   if (isa<PHINode>(Inst) || isa<GetElementPtrInst>(Inst) || isa<CastInst>(Inst))
  31     return true;
  32
  33   if (Inst->getOpcode() == Instruction::Add &&
  34       isa<ConstantInt>(Inst->getOperand(1)))
  35     return true;
  36
  37   return false;
  38 }
  39
  40 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  41 LLVM_DUMP_METHOD void PHITransAddr::dump() const {
  42   if (!Addr) {
  43     dbgs() << "PHITransAddr: null\n";
  44     return;
  45   }
  46   dbgs() << "PHITransAddr: " << *Addr << "\n";
  47   for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
  48     dbgs() << "  Input #" << i << " is " << *InstInputs[i] << "\n";
  49 }
  50 #endif
  51
  52 static bool verifySubExpr(Value *Expr,
  53                           SmallVectorImpl<Instruction *> &InstInputs) {
  54   // If this is a non-instruction value, there is nothing to do.
  55   Instruction *I = dyn_cast<Instruction>(Expr);
  56   if (!I) return true;
  57
  58   // If it's an instruction, it is either in Tmp or its operands recursively
  59   // are.
  60   if (auto Entry = find(InstInputs, I); Entry != InstInputs.end()) {
  61     InstInputs.erase(Entry);
  62     return true;
  63   }
  64
  65   // If it isn't in the InstInputs list it is a subexpr incorporated into the
  66   // address.  Validate that it is phi translatable.
  67   if (!canPHITrans(I)) {
  68     errs() << "Instruction in PHITransAddr is not phi-translatable:\n";
  69     errs() << *I << '\n';
  70     llvm_unreachable("Either something is missing from InstInputs or "
  71                      "canPHITrans is wrong.");
  72   }
  73
  74   // Validate the operands of the instruction.
  75   return all_of(I->operands(),
  76                 [&](Value *Op) { return verifySubExpr(Op, InstInputs); });
  77 }
  78
  79 /// verify - Check internal consistency of this data structure.  If the
  80 /// structure is valid, it returns true.  If invalid, it prints errors and
  81 /// returns false.
  82 bool PHITransAddr::verify() const {
  83   if (!Addr) return true;
  84
  85   SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end());
  86
  87   if (!verifySubExpr(Addr, Tmp))
  88     return false;
  89
  90   if (!Tmp.empty()) {
  91     errs() << "PHITransAddr contains extra instructions:\n";
  92     for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
  93       errs() << "  InstInput #" << i << " is " << *InstInputs[i] << "\n";
  94     llvm_unreachable("This is unexpected.");
  95   }
  96
  97   // a-ok.
  98   return true;
  99 }
 100
 101 /// isPotentiallyPHITranslatable - If this needs PHI translation, return true
 102 /// if we have some hope of doing it.  This should be used as a filter to
 103 /// avoid calling PHITranslateValue in hopeless situations.
 104 bool PHITransAddr::isPotentiallyPHITranslatable() const {
 105   // If the input value is not an instruction, or if it is not defined in CurBB,
 106   // then we don't need to phi translate it.
 107   Instruction *Inst = dyn_cast<Instruction>(Addr);
 108   return !Inst || canPHITrans(Inst);
 109 }
 110
 111 static void RemoveInstInputs(Value *V,
 112                              SmallVectorImpl<Instruction*> &InstInputs) {
 113   Instruction *I = dyn_cast<Instruction>(V);
 114   if (!I) return;
 115
 116   // If the instruction is in the InstInputs list, remove it.
 117   if (auto Entry = find(InstInputs, I); Entry != InstInputs.end()) {
 118     InstInputs.erase(Entry);
 119     return;
 120   }
 121
 122   assert(!isa<PHINode>(I) && "Error, removing something that isn't an input");
 123
 124   // Otherwise, it must have instruction inputs itself.  Zap them recursively.
 125   for (Value *Op : I->operands())
 126     if (Instruction *OpInst = dyn_cast<Instruction>(Op))
 127       RemoveInstInputs(OpInst, InstInputs);
 128 }
 129
 130 Value *PHITransAddr::translateSubExpr(Value *V, BasicBlock *CurBB,
 131                                       BasicBlock *PredBB,
 132                                       const DominatorTree *DT) {
 133   // If this is a non-instruction value, it can't require PHI translation.
 134   Instruction *Inst = dyn_cast<Instruction>(V);
 135   if (!Inst) return V;
 136
 137   // Determine whether 'Inst' is an input to our PHI translatable expression.
 138   bool isInput = is_contained(InstInputs, Inst);
 139
 140   // Handle inputs instructions if needed.
 141   if (isInput) {
 142     if (Inst->getParent() != CurBB) {
 143       // If it is an input defined in a different block, then it remains an
 144       // input.
 145       return Inst;
 146     }
 147
 148     // If 'Inst' is defined in this block and is an input that needs to be phi
 149     // translated, we need to incorporate the value into the expression or fail.
 150
 151     // In either case, the instruction itself isn't an input any longer.
 152     InstInputs.erase(find(InstInputs, Inst));
 153
 154     // If this is a PHI, go ahead and translate it.
 155     if (PHINode *PN = dyn_cast<PHINode>(Inst))
 156       return addAsInput(PN->getIncomingValueForBlock(PredBB));
 157
 158     // If this is a non-phi value, and it is analyzable, we can incorporate it
 159     // into the expression by making all instruction operands be inputs.
 160     if (!canPHITrans(Inst))
 161       return nullptr;
 162
 163     // All instruction operands are now inputs (and of course, they may also be
 164     // defined in this block, so they may need to be phi translated themselves.
 165     for (Value *Op : Inst->operands())
 166       addAsInput(Op);
 167   }
 168
 169   // Ok, it must be an intermediate result (either because it started that way
 170   // or because we just incorporated it into the expression).  See if its
 171   // operands need to be phi translated, and if so, reconstruct it.
 172
 173   if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
 174     Value *PHIIn = translateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT);
 175     if (!PHIIn) return nullptr;
 176     if (PHIIn == Cast->getOperand(0))
 177       return Cast;
 178
 179     // Find an available version of this cast.
 180
 181     // Try to simplify cast first.
 182     if (Value *V = simplifyCastInst(Cast->getOpcode(), PHIIn, Cast->getType(),
 183                                     {DL, TLI, DT, AC})) {
 184       RemoveInstInputs(PHIIn, InstInputs);
 185       return addAsInput(V);
 186     }
 187
 188     // Otherwise we have to see if a casted version of the incoming pointer
 189     // is available.  If so, we can use it, otherwise we have to fail.
 190     for (User *U : PHIIn->users()) {
 191       if (CastInst *CastI = dyn_cast<CastInst>(U))
 192         if (CastI->getOpcode() == Cast->getOpcode() &&
 193             CastI->getType() == Cast->getType() &&
 194             (!DT || DT->dominates(CastI->getParent(), PredBB)))
 195           return CastI;
 196     }
 197     return nullptr;
 198   }
 199
 200   // Handle getelementptr with at least one PHI translatable operand.
 201   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
 202     SmallVector<Value*, 8> GEPOps;
 203     bool AnyChanged = false;
 204     for (Value *Op : GEP->operands()) {
 205       Value *GEPOp = translateSubExpr(Op, CurBB, PredBB, DT);
 206       if (!GEPOp) return nullptr;
 207
 208       AnyChanged |= GEPOp != Op;
 209       GEPOps.push_back(GEPOp);
 210     }
 211
 212     if (!AnyChanged)
 213       return GEP;
 214
 215     // Simplify the GEP to handle 'gep x, 0' -> x etc.
 216     if (Value *V = simplifyGEPInst(GEP->getSourceElementType(), GEPOps[0],
 217                                    ArrayRef<Value *>(GEPOps).slice(1),
 218                                    GEP->getNoWrapFlags(), {DL, TLI, DT, AC})) {
 219       for (Value *Op : GEPOps)
 220         RemoveInstInputs(Op, InstInputs);
 221
 222       return addAsInput(V);
 223     }
 224
 225     // Scan to see if we have this GEP available.
 226     Value *APHIOp = GEPOps[0];
 227     for (User *U : APHIOp->users()) {
 228       if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U))
 229         if (GEPI->getType() == GEP->getType() &&
 230             GEPI->getSourceElementType() == GEP->getSourceElementType() &&
 231             GEPI->getNumOperands() == GEPOps.size() &&
 232             GEPI->getParent()->getParent() == CurBB->getParent() &&
 233             (!DT || DT->dominates(GEPI->getParent(), PredBB))) {
 234           if (std::equal(GEPOps.begin(), GEPOps.end(), GEPI->op_begin()))
 235             return GEPI;
 236         }
 237     }
 238     return nullptr;
 239   }
 240
 241   // Handle add with a constant RHS.
 242   if (Inst->getOpcode() == Instruction::Add &&
 243       isa<ConstantInt>(Inst->getOperand(1))) {
 244     // PHI translate the LHS.
 245     Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
 246     bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
 247     bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
 248
 249     Value *LHS = translateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT);
 250     if (!LHS) return nullptr;
 251
 252     // If the PHI translated LHS is an add of a constant, fold the immediates.
 253     if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
 254       if (BOp->getOpcode() == Instruction::Add)
 255         if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
 256           LHS = BOp->getOperand(0);
 257           RHS = ConstantExpr::getAdd(RHS, CI);
 258           isNSW = isNUW = false;
 259
 260           // If the old 'LHS' was an input, add the new 'LHS' as an input.
 261           if (is_contained(InstInputs, BOp)) {
 262             RemoveInstInputs(BOp, InstInputs);
 263             addAsInput(LHS);
 264           }
 265         }
 266
 267     // See if the add simplifies away.
 268     if (Value *Res = simplifyAddInst(LHS, RHS, isNSW, isNUW, {DL, TLI, DT, AC})) {
 269       // If we simplified the operands, the LHS is no longer an input, but Res
 270       // is.
 271       RemoveInstInputs(LHS, InstInputs);
 272       return addAsInput(Res);
 273     }
 274
 275     // If we didn't modify the add, just return it.
 276     if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1))
 277       return Inst;
 278
 279     // Otherwise, see if we have this add available somewhere.
 280     for (User *U : LHS->users()) {
 281       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U))
 282         if (BO->getOpcode() == Instruction::Add &&
 283             BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
 284             BO->getParent()->getParent() == CurBB->getParent() &&
 285             (!DT || DT->dominates(BO->getParent(), PredBB)))
 286           return BO;
 287     }
 288
 289     return nullptr;
 290   }
 291
 292   // Otherwise, we failed.
 293   return nullptr;
 294 }
 295
 296 /// PHITranslateValue - PHI translate the current address up the CFG from
 297 /// CurBB to Pred, updating our state to reflect any needed changes.  If
 298 /// 'MustDominate' is true, the translated value must dominate PredBB.
 299 Value *PHITransAddr::translateValue(BasicBlock *CurBB, BasicBlock *PredBB,
 300                                     const DominatorTree *DT,
 301                                     bool MustDominate) {
 302   assert(DT || !MustDominate);
 303   assert(verify() && "Invalid PHITransAddr!");
 304   if (DT && DT->isReachableFromEntry(PredBB))
 305     Addr = translateSubExpr(Addr, CurBB, PredBB, DT);
 306   else
 307     Addr = nullptr;
 308   assert(verify() && "Invalid PHITransAddr!");
 309
 310   if (MustDominate)
 311     // Make sure the value is live in the predecessor.
 312     if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))
 313       if (!DT->dominates(Inst->getParent(), PredBB))
 314         Addr = nullptr;
 315
 316   return Addr;
 317 }
 318
 319 /// PHITranslateWithInsertion - PHI translate this value into the specified
 320 /// predecessor block, inserting a computation of the value if it is
 321 /// unavailable.
 322 ///
 323 /// All newly created instructions are added to the NewInsts list.  This
 324 /// returns null on failure.
 325 ///
 326 Value *
 327 PHITransAddr::translateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,
 328                                      const DominatorTree &DT,
 329                                      SmallVectorImpl<Instruction *> &NewInsts) {
 330   unsigned NISize = NewInsts.size();
 331
 332   // Attempt to PHI translate with insertion.
 333   Addr = insertTranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);
 334
 335   // If successful, return the new value.
 336   if (Addr) return Addr;
 337
 338   // If not, destroy any intermediate instructions inserted.
 339   while (NewInsts.size() != NISize)
 340     NewInsts.pop_back_val()->eraseFromParent();
 341   return nullptr;
 342 }
 343
 344 /// insertTranslatedSubExpr - Insert a computation of the PHI translated
 345 /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
 346 /// block.  All newly created instructions are added to the NewInsts list.
 347 /// This returns null on failure.
 348 ///
 349 Value *PHITransAddr::insertTranslatedSubExpr(
 350     Value *InVal, BasicBlock *CurBB, BasicBlock *PredBB,
 351     const DominatorTree &DT, SmallVectorImpl<Instruction *> &NewInsts) {
 352   // See if we have a version of this value already available and dominating
 353   // PredBB.  If so, there is no need to insert a new instance of it.
 354   PHITransAddr Tmp(InVal, DL, AC);
 355   if (Value *Addr =
 356           Tmp.translateValue(CurBB, PredBB, &DT, /*MustDominate=*/true))
 357     return Addr;
 358
 359   // We don't need to PHI translate values which aren't instructions.
 360   auto *Inst = dyn_cast<Instruction>(InVal);
 361   if (!Inst)
 362     return nullptr;
 363
 364   // Handle cast of PHI translatable value.
 365   if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
 366     Value *OpVal = insertTranslatedSubExpr(Cast->getOperand(0), CurBB, PredBB,
 367                                            DT, NewInsts);
 368     if (!OpVal) return nullptr;
 369
 370     // Otherwise insert a cast at the end of PredBB.
 371     CastInst *New = CastInst::Create(Cast->getOpcode(), OpVal, InVal->getType(),
 372                                      InVal->getName() + ".phi.trans.insert",
 373                                      PredBB->getTerminator()->getIterator());
 374     New->setDebugLoc(Inst->getDebugLoc());
 375     NewInsts.push_back(New);
 376     return New;
 377   }
 378
 379   // Handle getelementptr with at least one PHI operand.
 380   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
 381     SmallVector<Value*, 8> GEPOps;
 382     BasicBlock *CurBB = GEP->getParent();
 383     for (Value *Op : GEP->operands()) {
 384       Value *OpVal = insertTranslatedSubExpr(Op, CurBB, PredBB, DT, NewInsts);
 385       if (!OpVal) return nullptr;
 386       GEPOps.push_back(OpVal);
 387     }
 388
 389     GetElementPtrInst *Result = GetElementPtrInst::Create(
 390         GEP->getSourceElementType(), GEPOps[0], ArrayRef(GEPOps).slice(1),
 391         InVal->getName() + ".phi.trans.insert",
 392         PredBB->getTerminator()->getIterator());
 393     Result->setDebugLoc(Inst->getDebugLoc());
 394     Result->setNoWrapFlags(GEP->getNoWrapFlags());
 395     NewInsts.push_back(Result);
 396     return Result;
 397   }
 398
 399   // Handle add with a constant RHS.
 400   if (EnableAddPhiTranslation && Inst->getOpcode() == Instruction::Add &&
 401       isa<ConstantInt>(Inst->getOperand(1))) {
 402
 403     // FIXME: This code works, but it is unclear that we actually want to insert
 404     // a big chain of computation in order to make a value available in a block.
 405     // This needs to be evaluated carefully to consider its cost trade offs.
 406
 407     // PHI translate the LHS.
 408     Value *OpVal = insertTranslatedSubExpr(Inst->getOperand(0), CurBB, PredBB,
 409                                            DT, NewInsts);
 410     if (OpVal == nullptr)
 411       return nullptr;
 412
 413     BinaryOperator *Res = BinaryOperator::CreateAdd(
 414         OpVal, Inst->getOperand(1), InVal->getName() + ".phi.trans.insert",
 415         PredBB->getTerminator()->getIterator());
 416     Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());
 417     Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());
 418     NewInsts.push_back(Res);
 419     return Res;
 420   }
 421
 422   return nullptr;
 423 }