427 lines · 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-exception6//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"23using namespace llvm;24 25static cl::opt<bool> EnableAddPhiTranslation(26 "gvn-add-phi-translation", cl::init(false), cl::Hidden,27 cl::desc("Enable phi-translation of add instructions"));28 29static 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)41LLVM_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#endif51 52static 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 recursively59 // 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 the66 // 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 the80/// structure is valid, it returns true. If invalid, it prints errors and81/// returns false.82bool 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 true102/// if we have some hope of doing it. This should be used as a filter to103/// avoid calling PHITranslateValue in hopeless situations.104bool 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 111static 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 130Value *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 an144 // input.145 return Inst;146 }147 148 // If 'Inst' is defined in this block and is an input that needs to be phi149 // 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 it159 // 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 be164 // 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 way170 // or because we just incorporated it into the expression). See if its171 // 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 pointer189 // 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 if (isa<ConstantData>(APHIOp))228 return nullptr;229 230 for (User *U : APHIOp->users()) {231 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U))232 if (GEPI->getType() == GEP->getType() &&233 GEPI->getSourceElementType() == GEP->getSourceElementType() &&234 GEPI->getNumOperands() == GEPOps.size() &&235 GEPI->getParent()->getParent() == CurBB->getParent() &&236 (!DT || DT->dominates(GEPI->getParent(), PredBB))) {237 if (std::equal(GEPOps.begin(), GEPOps.end(), GEPI->op_begin()))238 return GEPI;239 }240 }241 return nullptr;242 }243 244 // Handle add with a constant RHS.245 if (Inst->getOpcode() == Instruction::Add &&246 isa<ConstantInt>(Inst->getOperand(1))) {247 // PHI translate the LHS.248 Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));249 bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();250 bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();251 252 Value *LHS = translateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT);253 if (!LHS) return nullptr;254 255 // If the PHI translated LHS is an add of a constant, fold the immediates.256 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))257 if (BOp->getOpcode() == Instruction::Add)258 if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {259 LHS = BOp->getOperand(0);260 RHS = ConstantExpr::getAdd(RHS, CI);261 isNSW = isNUW = false;262 263 // If the old 'LHS' was an input, add the new 'LHS' as an input.264 if (is_contained(InstInputs, BOp)) {265 RemoveInstInputs(BOp, InstInputs);266 addAsInput(LHS);267 }268 }269 270 // See if the add simplifies away.271 if (Value *Res = simplifyAddInst(LHS, RHS, isNSW, isNUW, {DL, TLI, DT, AC})) {272 // If we simplified the operands, the LHS is no longer an input, but Res273 // is.274 RemoveInstInputs(LHS, InstInputs);275 return addAsInput(Res);276 }277 278 // If we didn't modify the add, just return it.279 if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1))280 return Inst;281 282 // Otherwise, see if we have this add available somewhere.283 for (User *U : LHS->users()) {284 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U))285 if (BO->getOpcode() == Instruction::Add &&286 BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&287 BO->getParent()->getParent() == CurBB->getParent() &&288 (!DT || DT->dominates(BO->getParent(), PredBB)))289 return BO;290 }291 292 return nullptr;293 }294 295 // Otherwise, we failed.296 return nullptr;297}298 299/// PHITranslateValue - PHI translate the current address up the CFG from300/// CurBB to Pred, updating our state to reflect any needed changes. If301/// 'MustDominate' is true, the translated value must dominate PredBB.302Value *PHITransAddr::translateValue(BasicBlock *CurBB, BasicBlock *PredBB,303 const DominatorTree *DT,304 bool MustDominate) {305 assert(DT || !MustDominate);306 assert(verify() && "Invalid PHITransAddr!");307 if (DT && DT->isReachableFromEntry(PredBB))308 Addr = translateSubExpr(Addr, CurBB, PredBB, DT);309 else310 Addr = nullptr;311 assert(verify() && "Invalid PHITransAddr!");312 313 if (MustDominate)314 // Make sure the value is live in the predecessor.315 if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))316 if (!DT->dominates(Inst->getParent(), PredBB))317 Addr = nullptr;318 319 return Addr;320}321 322/// PHITranslateWithInsertion - PHI translate this value into the specified323/// predecessor block, inserting a computation of the value if it is324/// unavailable.325///326/// All newly created instructions are added to the NewInsts list. This327/// returns null on failure.328///329Value *330PHITransAddr::translateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,331 const DominatorTree &DT,332 SmallVectorImpl<Instruction *> &NewInsts) {333 unsigned NISize = NewInsts.size();334 335 // Attempt to PHI translate with insertion.336 Addr = insertTranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);337 338 // If successful, return the new value.339 if (Addr) return Addr;340 341 // If not, destroy any intermediate instructions inserted.342 while (NewInsts.size() != NISize)343 NewInsts.pop_back_val()->eraseFromParent();344 return nullptr;345}346 347/// insertTranslatedSubExpr - Insert a computation of the PHI translated348/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB349/// block. All newly created instructions are added to the NewInsts list.350/// This returns null on failure.351///352Value *PHITransAddr::insertTranslatedSubExpr(353 Value *InVal, BasicBlock *CurBB, BasicBlock *PredBB,354 const DominatorTree &DT, SmallVectorImpl<Instruction *> &NewInsts) {355 // See if we have a version of this value already available and dominating356 // PredBB. If so, there is no need to insert a new instance of it.357 PHITransAddr Tmp(InVal, DL, AC);358 if (Value *Addr =359 Tmp.translateValue(CurBB, PredBB, &DT, /*MustDominate=*/true))360 return Addr;361 362 // We don't need to PHI translate values which aren't instructions.363 auto *Inst = dyn_cast<Instruction>(InVal);364 if (!Inst)365 return nullptr;366 367 // Handle cast of PHI translatable value.368 if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {369 Value *OpVal = insertTranslatedSubExpr(Cast->getOperand(0), CurBB, PredBB,370 DT, NewInsts);371 if (!OpVal) return nullptr;372 373 // Otherwise insert a cast at the end of PredBB.374 CastInst *New = CastInst::Create(Cast->getOpcode(), OpVal, InVal->getType(),375 InVal->getName() + ".phi.trans.insert",376 PredBB->getTerminator()->getIterator());377 New->setDebugLoc(Inst->getDebugLoc());378 NewInsts.push_back(New);379 return New;380 }381 382 // Handle getelementptr with at least one PHI operand.383 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {384 SmallVector<Value*, 8> GEPOps;385 BasicBlock *CurBB = GEP->getParent();386 for (Value *Op : GEP->operands()) {387 Value *OpVal = insertTranslatedSubExpr(Op, CurBB, PredBB, DT, NewInsts);388 if (!OpVal) return nullptr;389 GEPOps.push_back(OpVal);390 }391 392 GetElementPtrInst *Result = GetElementPtrInst::Create(393 GEP->getSourceElementType(), GEPOps[0], ArrayRef(GEPOps).slice(1),394 InVal->getName() + ".phi.trans.insert",395 PredBB->getTerminator()->getIterator());396 Result->setDebugLoc(Inst->getDebugLoc());397 Result->setNoWrapFlags(GEP->getNoWrapFlags());398 NewInsts.push_back(Result);399 return Result;400 }401 402 // Handle add with a constant RHS.403 if (EnableAddPhiTranslation && Inst->getOpcode() == Instruction::Add &&404 isa<ConstantInt>(Inst->getOperand(1))) {405 406 // FIXME: This code works, but it is unclear that we actually want to insert407 // a big chain of computation in order to make a value available in a block.408 // This needs to be evaluated carefully to consider its cost trade offs.409 410 // PHI translate the LHS.411 Value *OpVal = insertTranslatedSubExpr(Inst->getOperand(0), CurBB, PredBB,412 DT, NewInsts);413 if (OpVal == nullptr)414 return nullptr;415 416 BinaryOperator *Res = BinaryOperator::CreateAdd(417 OpVal, Inst->getOperand(1), InVal->getName() + ".phi.trans.insert",418 PredBB->getTerminator()->getIterator());419 Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());420 Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());421 NewInsts.push_back(Res);422 return Res;423 }424 425 return nullptr;426}427