Index: llvm/include/llvm/Transforms/Scalar/GVN.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/GVN.h +++ llvm/include/llvm/Transforms/Scalar/GVN.h @@ -171,6 +171,10 @@ // Value number to PHINode mapping. Used for phi-translate in scalarpre. DenseMap NumberingPhi; + // Value number to BasicBlock mapping. Used for phi-translate across + // MemoryPhis. + DenseMap NumberingBB; + // Cache for phi-translate in scalarpre. using PhiTranslateMap = DenseMap, uint32_t>; @@ -178,6 +182,7 @@ AAResults *AA = nullptr; MemoryDependenceResults *MD = nullptr; + MemorySSA *MSSA = nullptr; DominatorTree *DT = nullptr; uint32_t nextValueNumber = 1; @@ -187,7 +192,10 @@ Value *LHS, Value *RHS); Expression createExtractvalueExpr(ExtractValueInst *EI); Expression createGEPExpr(GetElementPtrInst *GEP); + Expression createCallExpr(CallInst *C); + void addMemoryStateArg(Instruction *I, Expression &E); uint32_t lookupOrAddCall(CallInst *C); + uint32_t lookupOrAddLoadStore(Instruction *I); uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn); bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred, @@ -216,6 +224,7 @@ void setAliasAnalysis(AAResults *A) { AA = A; } AAResults *getAliasAnalysis() const { return AA; } void setMemDep(MemoryDependenceResults *M) { MD = M; } + void setMemorySSA(MemorySSA *M) { MSSA = M; } void setDomTree(DominatorTree *D) { DT = D; } uint32_t getNextUnusedValueNumber() { return nextValueNumber; } void verifyRemoved(const Value *) const; Index: llvm/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/lib/Transforms/Scalar/GVN.cpp +++ llvm/lib/Transforms/Scalar/GVN.cpp @@ -310,17 +310,9 @@ Expression e; e.type = I->getType(); e.opcode = I->getOpcode(); - if (const GCRelocateInst *GCR = dyn_cast(I)) { - // gc.relocate is 'special' call: its second and third operands are - // not real values, but indices into statepoint's argument list. - // Use the refered to values for purposes of identity. - e.varargs.push_back(lookupOrAdd(GCR->getOperand(0))); - e.varargs.push_back(lookupOrAdd(GCR->getBasePtr())); - e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr())); - } else { - for (Use &Op : I->operands()) - e.varargs.push_back(lookupOrAdd(Op)); - } + for (Use &Op : I->operands()) + e.varargs.push_back(lookupOrAdd(Op)); + if (I->isCommutative()) { // Ensure that commutative instructions that only differ by a permutation // of their operands get the same value number by sorting the operand value @@ -351,6 +343,34 @@ return e; } +GVNPass::Expression GVNPass::ValueTable::createCallExpr(CallInst *C) { + Expression E; + E.type = C->getType(); + E.opcode = C->getOpcode(); + if (const GCRelocateInst *GCR = dyn_cast(C)) { + // gc.relocate is 'special' call: its second and third operands are + // not real values, but indices into statepoint's argument list. + // Use the refered to values for purposes of identity. + E.varargs.push_back(lookupOrAdd(GCR->getOperand(0))); + E.varargs.push_back(lookupOrAdd(GCR->getBasePtr())); + E.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr())); + return E; + } + + for (Use &Op : C->operands()) + E.varargs.push_back(lookupOrAdd(Op)); + + if (C->isCommutative()) { + // There are commutative instrinsic calls. + assert(C->getNumOperands() >= 2 && "Unsupported commutative instruction!"); + if (E.varargs[0] > E.varargs[1]) + std::swap(E.varargs[0], E.varargs[1]); + E.commutative = true; + } + + return E; +} + GVNPass::Expression GVNPass::ValueTable::createCmpExpr( unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && @@ -450,14 +470,50 @@ NumberingPhi[num] = PN; } +// Include the incoming memory state into the hash for the instruction. If the +// incoming memory state is: +// * LiveOnEntry, add the value number of the entry block +// * a MemoryPhi, add the value number of the basic block, +// corresponding to that MemoryPhi +// * a MemoryDef, add the value number of the memory setting +// instruction. +void GVNPass::ValueTable::addMemoryStateArg(Instruction *I, Expression &E) { + assert(MSSA && "Function should not be called without MemorySSA"); + assert(MSSA->getMemoryAccess(I) && "Instruction does not access memory"); + MemoryAccess *MA = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(I); + + uint32_t N = 0; + if (isa(MA)) + N = lookupOrAdd(MA->getBlock()); + else if (MSSA->isLiveOnEntryDef(MA)) + N = lookupOrAdd(&I->getFunction()->getEntryBlock()); + else + N = lookupOrAdd(cast(MA)->getMemoryInst()); + E.varargs.push_back(N); +} + uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) { if (AA->doesNotAccessMemory(C)) { - Expression exp = createExpr(C); + Expression exp = createCallExpr(C); uint32_t e = assignExpNewValueNum(exp).first; valueNumbering[C] = e; return e; - } else if (MD && AA->onlyReadsMemory(C)) { - Expression exp = createExpr(C); + } + + if (MSSA) { + if (AA->onlyReadsMemory(C)) { + Expression E = createCallExpr(C); + addMemoryStateArg(C, E); + uint32_t VN = assignExpNewValueNum(E).first; + valueNumbering[C] = VN; + return VN; + } + valueNumbering[C] = nextValueNumber; + return nextValueNumber++; + } + + if (MD && AA->onlyReadsMemory(C)) { + Expression exp = createCallExpr(C); auto ValNum = assignExpNewValueNum(exp); if (ValNum.second) { valueNumbering[C] = ValNum.first; @@ -553,6 +609,24 @@ } } +uint32_t GVNPass::ValueTable::lookupOrAddLoadStore(Instruction *I) { + if (MSSA == nullptr) { + valueNumbering[I] = nextValueNumber; + return nextValueNumber++; + } + + Expression E; + E.type = I->getType(); + E.opcode = I->getOpcode(); + for (Use &Op : I->operands()) + E.varargs.push_back(lookupOrAdd(Op)); + addMemoryStateArg(I, E); + + uint32_t N = assignExpNewValueNum(E).first; + valueNumbering[I] = N; + return N; +} + /// Returns true if a value number exists for the specified value. bool GVNPass::ValueTable::exists(Value *V) const { return valueNumbering.count(V) != 0; @@ -567,6 +641,10 @@ if (!isa(V)) { valueNumbering[V] = nextValueNumber; + if (MSSA) { + if (auto *BB = dyn_cast(V)) + NumberingBB[nextValueNumber] = BB; + } return nextValueNumber++; } @@ -627,6 +705,9 @@ valueNumbering[V] = nextValueNumber; NumberingPhi[nextValueNumber] = cast(V); return nextValueNumber++; + case Instruction::Load: + case Instruction::Store: + return lookupOrAddLoadStore(I); default: valueNumbering[V] = nextValueNumber; return nextValueNumber++; @@ -664,6 +745,7 @@ valueNumbering.clear(); expressionNumbering.clear(); NumberingPhi.clear(); + NumberingBB.clear(); PhiTranslateTable.clear(); nextValueNumber = 1; Expressions.clear(); @@ -678,6 +760,8 @@ // If V is PHINode, V <--> value number is an one-to-one mapping. if (isa(V)) NumberingPhi.erase(Num); + else if (isa(V)) + NumberingBB.erase(Num); } /// verifyRemoved - Verify that the value is removed from all internal data @@ -2170,14 +2254,38 @@ const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn) { if (PHINode *PN = NumberingPhi[Num]) { + if (PN->getParent() != PhiBlock) + return Num; for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { - if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred) + if (PN->getIncomingBlock(i) == Pred) if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false)) return TransVal; } return Num; } + if (BasicBlock *BB = NumberingBB[Num]) { + assert(MSSA && "NumberingBB is non-empty only when using MemorySSA"); + // Value numbers of basic blocks are used to represent memory state in + // load/store instructions and read-only function calls when said state is + // set by a MemoryPhi. + if (BB != PhiBlock) + return Num; + MemoryPhi *MPhi = MSSA->getMemoryAccess(BB); + for (unsigned I = 0, N = MPhi->getNumIncomingValues(); I != N; ++I) { + if (MPhi->getIncomingBlock(I) != Pred) + continue; + MemoryAccess *MA = MPhi->getIncomingValue(I); + if (auto *PredPhi = dyn_cast(MA)) + return lookupOrAdd(PredPhi->getBlock()); + if (MSSA->isLiveOnEntryDef(MA)) + return lookupOrAdd(&BB->getParent()->getEntryBlock()); + return lookupOrAdd(cast(MA)->getMemoryInst()); + } + llvm_unreachable( + "CFG/MemorySSA mismatch: predecessor not found among incoming blocks"); + } + // If there is any value related with Num is defined in a BB other than // PhiBlock, it cannot depend on a phi in PhiBlock without going through // a backedge. We can do an early exit in that case to save compile time. @@ -2212,7 +2320,7 @@ } if (uint32_t NewNum = expressionNumbering[Exp]) { - if (Exp.opcode == Instruction::Call && NewNum != Num) + if (MSSA == nullptr && Exp.opcode == Instruction::Call && NewNum != Num) return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num; return NewNum; } @@ -2605,6 +2713,7 @@ ICF = &ImplicitCFT; this->LI = LI; VN.setMemDep(MD); + VN.setMemorySSA(MSSA); ORE = RunORE; InvalidBlockRPONumbers = true; MemorySSAUpdater Updater(MSSA); Index: llvm/test/Analysis/ValueTracking/gep-negative-issue.ll =================================================================== --- llvm/test/Analysis/ValueTracking/gep-negative-issue.ll +++ llvm/test/Analysis/ValueTracking/gep-negative-issue.ll @@ -5,16 +5,16 @@ %ArrayImpl = type { i64, i64 addrspace(100)*, [1 x i64], [1 x i64], [1 x i64], i64, i64, double addrspace(100)*, double addrspace(100)*, i8, i64 } %_array = type { i64, %ArrayImpl addrspace(100)*, i8 } -define void @test(i64 %n_chpl) { +define void @test(%_array* %p) { entry: ; First section is some code - %0 = getelementptr inbounds %_array, %_array* null, i32 0, i32 1 + %0 = getelementptr inbounds %_array, %_array* %p, i32 0, i32 1 %1 = load %ArrayImpl addrspace(100)*, %ArrayImpl addrspace(100)** %0 %2 = getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)* %1, i32 0, i32 8 %3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %2 %4 = getelementptr inbounds double, double addrspace(100)* %3, i64 -1 ; Second section is that code repeated - %x0 = getelementptr inbounds %_array, %_array* null, i32 0, i32 1 + %x0 = getelementptr inbounds %_array, %_array* %p, i32 0, i32 1 %x1 = load %ArrayImpl addrspace(100)*, %ArrayImpl addrspace(100)** %x0 %x2 = getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)* %x1, i32 0, i32 8 %x3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %x2