Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -2724,9 +2724,14 @@ MemAccess->getDefiningAccess()->getBlock() == I->getParent()) return nullptr; - SmallPtrSet VisitedOps; // Convert op of phis to phi of ops - for (auto *Op : I->operand_values()) { + SmallPtrSet VisitedOps; + SmallVector Ops(I->operand_values()); + BasicBlock *SamePHIBlock = nullptr; + PHINode *OpPHI = nullptr; + if (!DebugCounter::shouldExecute(PHIOfOpsCounter)) + return nullptr; + for (auto *Op : Ops) { if (!isa(Op)) { auto *ValuePHI = RealToTemp.lookup(Op); if (!ValuePHI) @@ -2734,116 +2739,125 @@ DEBUG(dbgs() << "Found possible dependent phi of ops\n"); Op = ValuePHI; } - auto *OpPHI = cast(Op); + OpPHI = cast(Op); + if (!SamePHIBlock) { + SamePHIBlock = getBlockForValue(OpPHI); + } else if (SamePHIBlock != getBlockForValue(OpPHI)) { + DEBUG(dbgs() + << "PHIs for operands are not all in the same block, aborting\n"); + return nullptr; + } // No point in doing this for one-operand phis. - if (OpPHI->getNumOperands() == 1) + if (OpPHI->getNumOperands() == 1) { + OpPHI = nullptr; continue; - if (!DebugCounter::shouldExecute(PHIOfOpsCounter)) - return nullptr; - SmallVector Ops; - SmallPtrSet Deps; - auto *PHIBlock = getBlockForValue(OpPHI); - RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I)); - for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) { - auto *PredBB = OpPHI->getIncomingBlock(PredNum); - Value *FoundVal = nullptr; - // We could just skip unreachable edges entirely but it's tricky to do - // with rewriting existing phi nodes. - if (ReachableEdges.count({PredBB, PHIBlock})) { - // Clone the instruction, create an expression from it that is - // translated back into the predecessor, and see if we have a leader. - Instruction *ValueOp = I->clone(); - SmallPtrSet CurrentDeps; - if (MemAccess) - TempToMemory.insert({ValueOp, MemAccess}); - bool SafeForPHIOfOps = true; - VisitedOps.clear(); - for (auto &Op : ValueOp->operands()) { - auto *OrigOp = &*Op; - // When these operand changes, it could change whether there is a - // leader for us or not, so we have to add additional users. - if (isa(Op)) { - Op = Op->DoPHITranslation(PHIBlock, PredBB); - if (Op != OrigOp && Op != I) - CurrentDeps.insert(Op); - } else if (auto *ValuePHI = RealToTemp.lookup(Op)) { - if (getBlockForValue(ValuePHI) == PHIBlock) - Op = ValuePHI->getIncomingValueForBlock(PredBB); - } - // If we phi-translated the op, it must be safe. - SafeForPHIOfOps = - SafeForPHIOfOps && - (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps)); - } - // FIXME: For those things that are not safe we could generate - // expressions all the way down, and see if this comes out to a - // constant. For anything where that is true, and unsafe, we should - // have made a phi-of-ops (or value numbered it equivalent to something) - // for the pieces already. - FoundVal = !SafeForPHIOfOps ? nullptr - : findLeaderForInst(ValueOp, Visited, - MemAccess, I, PredBB); - ValueOp->deleteValue(); - if (!FoundVal) { - // We failed to find a leader for the current ValueOp, but this might - // change in case of the translated operands change. - if (SafeForPHIOfOps) - for (auto Dep : CurrentDeps) - addAdditionalUsers(Dep, I); - - return nullptr; + } + } + + if (!OpPHI) + return nullptr; + + SmallVector PHIOps; + SmallPtrSet Deps; + auto *PHIBlock = getBlockForValue(OpPHI); + RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I)); + for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) { + auto *PredBB = OpPHI->getIncomingBlock(PredNum); + Value *FoundVal = nullptr; + SmallPtrSet CurrentDeps; + // We could just skip unreachable edges entirely but it's tricky to do + // with rewriting existing phi nodes. + if (ReachableEdges.count({PredBB, PHIBlock})) { + // Clone the instruction, create an expression from it that is + // translated back into the predecessor, and see if we have a leader. + Instruction *ValueOp = I->clone(); + if (MemAccess) + TempToMemory.insert({ValueOp, MemAccess}); + bool SafeForPHIOfOps = true; + VisitedOps.clear(); + for (auto &Op : ValueOp->operands()) { + auto *OrigOp = &*Op; + // When these operand changes, it could change whether there is a + // leader for us or not, so we have to add additional users. + if (isa(Op)) { + Op = Op->DoPHITranslation(PHIBlock, PredBB); + if (Op != OrigOp && Op != I) + CurrentDeps.insert(Op); + } else if (auto *ValuePHI = RealToTemp.lookup(Op)) { + if (getBlockForValue(ValuePHI) == PHIBlock) + Op = ValuePHI->getIncomingValueForBlock(PredBB); } - Deps.insert(CurrentDeps.begin(), CurrentDeps.end()); - } else { - DEBUG(dbgs() << "Skipping phi of ops operand for incoming block " - << getBlockName(PredBB) - << " because the block is unreachable\n"); - FoundVal = UndefValue::get(I->getType()); - RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); + // If we phi-translated the op, it must be safe. + SafeForPHIOfOps = + SafeForPHIOfOps && + (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps)); } - - Ops.push_back({FoundVal, PredBB}); - DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in " - << getBlockName(PredBB) << "\n"); - } - for (auto Dep : Deps) - addAdditionalUsers(Dep, I); - sortPHIOps(Ops); - auto *E = performSymbolicPHIEvaluation(Ops, I, PHIBlock); - if (isa(E) || isa(E)) { - DEBUG(dbgs() - << "Not creating real PHI of ops because it simplified to existing " - "value or constant\n"); - return E; - } - auto *ValuePHI = RealToTemp.lookup(I); - bool NewPHI = false; - if (!ValuePHI) { - ValuePHI = - PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops"); - addPhiOfOps(ValuePHI, PHIBlock, I); - NewPHI = true; - NumGVNPHIOfOpsCreated++; - } - if (NewPHI) { - for (auto PHIOp : Ops) - ValuePHI->addIncoming(PHIOp.first, PHIOp.second); - } else { - TempToBlock[ValuePHI] = PHIBlock; - unsigned int i = 0; - for (auto PHIOp : Ops) { - ValuePHI->setIncomingValue(i, PHIOp.first); - ValuePHI->setIncomingBlock(i, PHIOp.second); - ++i; + // FIXME: For those things that are not safe we could generate + // expressions all the way down, and see if this comes out to a + // constant. For anything where that is true, and unsafe, we should + // have made a phi-of-ops (or value numbered it equivalent to something) + // for the pieces already. + FoundVal = !SafeForPHIOfOps ? nullptr + : findLeaderForInst(ValueOp, Visited, + MemAccess, I, PredBB); + ValueOp->deleteValue(); + if (!FoundVal) { + // We failed to find a leader for the current ValueOp, but this might + // change in case of the translated operands change. + if (SafeForPHIOfOps) + for (auto Dep : CurrentDeps) + addAdditionalUsers(Dep, I); + + return nullptr; } + Deps.insert(CurrentDeps.begin(), CurrentDeps.end()); + } else { + DEBUG(dbgs() << "Skipping phi of ops operand for incoming block " + << getBlockName(PredBB) + << " because the block is unreachable\n"); + FoundVal = UndefValue::get(I->getType()); + RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); } - RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); - DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I - << "\n"); + PHIOps.push_back({FoundVal, PredBB}); + DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in " + << getBlockName(PredBB) << "\n"); + } + for (auto Dep : Deps) + addAdditionalUsers(Dep, I); + sortPHIOps(PHIOps); + auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock); + if (isa(E) || isa(E)) { + DEBUG(dbgs() + << "Not creating real PHI of ops because it simplified to existing " + "value or constant\n"); return E; } - return nullptr; + auto *ValuePHI = RealToTemp.lookup(I); + bool NewPHI = false; + if (!ValuePHI) { + ValuePHI = + PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops"); + addPhiOfOps(ValuePHI, PHIBlock, I); + NewPHI = true; + NumGVNPHIOfOpsCreated++; + } + if (NewPHI) { + for (auto PHIOp : PHIOps) + ValuePHI->addIncoming(PHIOp.first, PHIOp.second); + } else { + TempToBlock[ValuePHI] = PHIBlock; + unsigned int i = 0; + for (auto PHIOp : PHIOps) { + ValuePHI->setIncomingValue(i, PHIOp.first); + ValuePHI->setIncomingBlock(i, PHIOp.second); + ++i; + } + } + RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); + DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I << "\n"); + + return E; } // The algorithm initially places the values of the routine in the TOP Index: test/Transforms/NewGVN/phi-of-ops-move-block.ll =================================================================== --- test/Transforms/NewGVN/phi-of-ops-move-block.ll +++ test/Transforms/NewGVN/phi-of-ops-move-block.ll @@ -54,3 +54,54 @@ end: ret void } + +; In this test case a temporary PhiOfOps node gets moved to BB with more +; predecessors, so a new one needs to be created. +define void @test2() { +; CHECK-LABEL: @test2( +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[STOREMERGE:%.*]] = phi i32 [ 0, [[TMP0:%.*]] ], [ [[ADD:%.*]], [[CRITEDGE:%.*]] ] +; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[STOREMERGE]], 0 +; CHECK-NEXT: br i1 [[CMP1]], label [[LR_PH:%.*]], label [[CRITEDGE]] +; CHECK: lr.ph: +; CHECK-NEXT: br i1 undef, label [[SPLIT1:%.*]], label [[SPLIT2:%.*]] +; CHECK: split1: +; CHECK-NEXT: br label [[CRITEDGE]] +; CHECK: split2: +; CHECK-NEXT: br label [[CRITEDGE]] +; CHECK: critedge: +; CHECK-NEXT: [[PHIOFOPS1:%.*]] = phi i1 [ false, [[BB1]] ], [ true, [[SPLIT2]] ], [ true, [[SPLIT1]] ] +; CHECK-NEXT: [[PHIOFOPS:%.*]] = phi i1 [ undef, [[BB1]] ], [ undef, [[SPLIT2]] ], [ undef, [[SPLIT1]] ] +; CHECK-NEXT: [[LCSSA:%.*]] = phi i32 [ 0, [[BB1]] ], [ -1, [[SPLIT1]] ], [ -1, [[SPLIT2]] ] +; CHECK-NEXT: [[ADD]] = add nsw i32 [[STOREMERGE]], -1 +; CHECK-NEXT: br i1 [[PHIOFOPS]], label [[BB1]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; + br label %bb1 + +bb1: ; preds = %critedge, %0 + %storemerge = phi i32 [ 0, %0 ], [ %add, %critedge ] + %cmp1 = icmp eq i32 %storemerge, 0 + br i1 %cmp1, label %lr.ph, label %critedge + +lr.ph: ; preds = %bb1 + br i1 undef, label %split1, label %split2 + +split1: ; preds = %lr.ph + br label %critedge + +split2: ; preds = %lr.ph + br label %critedge + +critedge: ; preds = %split1, %split2, %bb1 + %lcssa = phi i32 [ 0, %bb1 ], [ -1, %split1 ], [ -1, %split2 ] + %cmp2 = icmp ne i32 %lcssa, 0 + %brmerge = or i1 %cmp1, %cmp2 + %add = add nsw i32 %storemerge, -1 + br i1 %brmerge, label %bb1, label %exit + +exit: ; preds = %critedge + ret void +}