diff options
| -rw-r--r-- | llvm/include/llvm/Transforms/Scalar/GVNExpression.h | 13 | ||||
| -rw-r--r-- | llvm/lib/Transforms/Scalar/NewGVN.cpp | 80 | ||||
| -rw-r--r-- | llvm/test/Transforms/NewGVN/completeness.ll | 2 | ||||
| -rw-r--r-- | llvm/test/Transforms/NewGVN/pr32403.ll | 3 | ||||
| -rw-r--r-- | llvm/test/Transforms/NewGVN/pr32897.ll | 1 | ||||
| -rw-r--r-- | llvm/test/Transforms/NewGVN/pr33187.ll | 148 |
6 files changed, 211 insertions, 36 deletions
diff --git a/llvm/include/llvm/Transforms/Scalar/GVNExpression.h b/llvm/include/llvm/Transforms/Scalar/GVNExpression.h index 324ebca46de..00834130499 100644 --- a/llvm/include/llvm/Transforms/Scalar/GVNExpression.h +++ b/llvm/include/llvm/Transforms/Scalar/GVNExpression.h @@ -93,6 +93,11 @@ public: } virtual bool equals(const Expression &Other) const { return true; } + // Return true if the two expressions are exactly the same, including the + // normally ignored fields. + virtual bool exactlyEquals(const Expression &Other) const { + return getExpressionType() == Other.getExpressionType() && equals(Other); + } unsigned getOpcode() const { return Opcode; } void setOpcode(unsigned opcode) { Opcode = opcode; } @@ -345,6 +350,10 @@ public: void setAlignment(unsigned Align) { Alignment = Align; } bool equals(const Expression &Other) const override; + bool exactlyEquals(const Expression &Other) const override { + return Expression::exactlyEquals(Other) && + cast<LoadExpression>(Other).getLoadInst() == getLoadInst(); + } // // Debugging support @@ -382,6 +391,10 @@ public: Value *getStoredValue() const { return StoredValue; } bool equals(const Expression &Other) const override; + bool exactlyEquals(const Expression &Other) const override { + return Expression::exactlyEquals(Other) && + cast<StoreExpression>(Other).getStoreInst() == getStoreInst(); + } // Debugging support // diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp index 27809f5b6f6..6926aae3796 100644 --- a/llvm/lib/Transforms/Scalar/NewGVN.cpp +++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp @@ -378,6 +378,15 @@ private: }; namespace llvm { +struct ExactEqualsExpression { + const Expression &E; + explicit ExactEqualsExpression(const Expression &E) : E(E) {} + hash_code getComputedHash() const { return E.getComputedHash(); } + bool operator==(const Expression &Other) const { + return E.exactlyEquals(Other); + } +}; + template <> struct DenseMapInfo<const Expression *> { static const Expression *getEmptyKey() { auto Val = static_cast<uintptr_t>(-1); @@ -390,8 +399,17 @@ template <> struct DenseMapInfo<const Expression *> { return reinterpret_cast<const Expression *>(Val); } static unsigned getHashValue(const Expression *E) { - return static_cast<unsigned>(E->getComputedHash()); + return E->getComputedHash(); + } + static unsigned getHashValue(const ExactEqualsExpression &E) { + return E.getComputedHash(); + } + static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS) { + if (RHS == getTombstoneKey() || RHS == getEmptyKey()) + return false; + return LHS == *RHS; } + static bool isEqual(const Expression *LHS, const Expression *RHS) { if (LHS == RHS) return true; @@ -848,6 +866,8 @@ PHIExpression *NewGVN::createPHIExpression(Instruction *I, bool &HasBackedge, // Things in TOPClass are equivalent to everything. if (ValueToClass.lookup(*U) == TOPClass) return false; + if (lookupOperandLeader(*U) == PN) + return false; return true; }); std::transform(Filtered.begin(), Filtered.end(), op_inserter(E), @@ -1571,30 +1591,6 @@ bool NewGVN::isCycleFree(const Instruction *I) const { // Evaluate PHI nodes symbolically, and create an expression result. const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) const { - // Resolve irreducible and reducible phi cycles. - // FIXME: This is hopefully a temporary solution while we resolve the issues - // with fixpointing self-cycles. It currently should be "guaranteed" to be - // correct, but non-optimal. The SCCFinder does not, for example, take - // reachability of arguments into account, etc. - SCCFinder.Start(I); - bool CanOptimize = true; - SmallPtrSet<Value *, 8> OuterOps; - - auto &Component = SCCFinder.getComponentFor(I); - for (auto *Member : Component) { - if (!isa<PHINode>(Member)) { - CanOptimize = false; - break; - } - for (auto &PHIOp : cast<PHINode>(Member)->operands()) - if (!isa<PHINode>(PHIOp) || !Component.count(cast<PHINode>(PHIOp))) - OuterOps.insert(PHIOp); - } - if (CanOptimize && OuterOps.size() == 1) { - DEBUG(dbgs() << "Resolving cyclic phi to value " << *(*OuterOps.begin()) - << "\n"); - return createVariableOrConstant(*OuterOps.begin()); - } // True if one of the incoming phi edges is a backedge. bool HasBackedge = false; // All constant tracks the state of whether all the *original* phi operands @@ -1662,7 +1658,12 @@ const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) const { if (!someEquivalentDominates(AllSameInst, I)) return E; } - + // Can't simplify to something that comes later in the iteration. + // Otherwise, when and if it changes congruence class, we will never catch + // up. We will always be a class behind it. + if (isa<Instruction>(AllSameValue) && + InstrToDFSNum(AllSameValue) > InstrToDFSNum(I)) + return E; NumGVNPhisAllSame++; DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue << "\n"); @@ -2158,7 +2159,17 @@ void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E, if (OldClass->getDefiningExpr()) { DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr() << " from table\n"); - ExpressionToClass.erase(OldClass->getDefiningExpr()); + // We erase it as an exact expression to make sure we don't just erase an + // equivalent one. + auto Iter = ExpressionToClass.find_as( + ExactEqualsExpression(*OldClass->getDefiningExpr())); + if (Iter != ExpressionToClass.end()) + ExpressionToClass.erase(Iter); +#ifdef EXPENSIVE_CHECKS + assert( + (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) && + "We erased the expression we just inserted, which should not happen"); +#endif } } else if (OldClass->getLeader() == I) { // When the leader changes, the value numbering of @@ -2272,8 +2283,13 @@ void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) { auto *OldE = ValueToExpression.lookup(I); // It could just be that the old class died. We don't want to erase it if we // just moved classes. - if (OldE && isa<StoreExpression>(OldE) && *E != *OldE) - ExpressionToClass.erase(OldE); + if (OldE && isa<StoreExpression>(OldE) && *E != *OldE) { + // Erase this as an exact expression to ensure we don't erase expressions + // equivalent to it. + auto Iter = ExpressionToClass.find_as(ExactEqualsExpression(*OldE)); + if (Iter != ExpressionToClass.end()) + ExpressionToClass.erase(Iter); + } } ValueToExpression[I] = E; } @@ -3060,6 +3076,9 @@ void NewGVN::iterateTouchedInstructions() { } updateProcessedCount(CurrBlock); } + // Reset after processing (because we may mark ourselves as touched when + // we propagate equalities). + TouchedInstructions.reset(InstrNum); if (auto *MP = dyn_cast<MemoryPhi>(V)) { DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n"); @@ -3070,9 +3089,6 @@ void NewGVN::iterateTouchedInstructions() { llvm_unreachable("Should have been a MemoryPhi or Instruction"); } updateProcessedCount(V); - // Reset after processing (because we may mark ourselves as touched when - // we propagate equalities). - TouchedInstructions.reset(InstrNum); } } NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations); diff --git a/llvm/test/Transforms/NewGVN/completeness.ll b/llvm/test/Transforms/NewGVN/completeness.ll index 2c35871e9ae..1798bfea5fe 100644 --- a/llvm/test/Transforms/NewGVN/completeness.ll +++ b/llvm/test/Transforms/NewGVN/completeness.ll @@ -395,7 +395,7 @@ define void @test10() { ; CHECK: g: ; CHECK-NEXT: [[N:%.*]] = phi i32* [ [[H:%.*]], [[I:%.*]] ], [ null, [[B:%.*]] ] ; CHECK-NEXT: [[H]] = getelementptr i32, i32* [[N]], i64 1 -; CHECK-NEXT: [[J:%.*]] = icmp eq i32* %h, inttoptr (i64 32 to i32*) +; CHECK-NEXT: [[J:%.*]] = icmp eq i32* [[H]], inttoptr (i64 32 to i32*) ; CHECK-NEXT: br i1 [[J]], label [[C:%.*]], label [[I]] ; CHECK: i: ; CHECK-NEXT: br i1 undef, label [[K:%.*]], label [[G]] diff --git a/llvm/test/Transforms/NewGVN/pr32403.ll b/llvm/test/Transforms/NewGVN/pr32403.ll index 505d31a9463..2552e0e66ab 100644 --- a/llvm/test/Transforms/NewGVN/pr32403.ll +++ b/llvm/test/Transforms/NewGVN/pr32403.ll @@ -17,8 +17,7 @@ define void @reorder_ref_pic_list() local_unnamed_addr { ; CHECK-NEXT: [[INC_I:%.*]] = add nsw i32 [[REFIDXLX_0]], 1 ; CHECK-NEXT: br label [[FOR_BODY8_I:%.*]] ; CHECK: for.body8.i: -; CHECK-NEXT: [[NIDX_052_I:%.*]] = phi i32 [ [[INC_I]], [[IF_THEN13]] ], [ [[NIDX_052_I]], [[FOR_INC24_I:%.*]] ] -; CHECK-NEXT: br i1 undef, label [[FOR_INC24_I]], label [[IF_THEN17_I:%.*]] +; CHECK-NEXT: br i1 undef, label [[FOR_INC24_I:%.*]], label [[IF_THEN17_I:%.*]] ; CHECK: if.then17.i: ; CHECK-NEXT: br label [[FOR_INC24_I]] ; CHECK: for.inc24.i: diff --git a/llvm/test/Transforms/NewGVN/pr32897.ll b/llvm/test/Transforms/NewGVN/pr32897.ll index eb19aa367b7..dcf2af30b23 100644 --- a/llvm/test/Transforms/NewGVN/pr32897.ll +++ b/llvm/test/Transforms/NewGVN/pr32897.ll @@ -7,7 +7,6 @@ define void @tinkywinky(i64* %b) { ; CHECK-NEXT: br label [[BODY:%.*]] ; CHECK: body: ; CHECK-NEXT: store i64 undef, i64* [[B:%.*]] -; CHECK-NEXT: [[B2:%.*]] = load i64, i64* [[B]] ; CHECK-NEXT: br i1 undef, label [[BODY]], label [[END:%.*]] ; CHECK: end: ; CHECK-NEXT: br label [[BODY]] diff --git a/llvm/test/Transforms/NewGVN/pr33187.ll b/llvm/test/Transforms/NewGVN/pr33187.ll new file mode 100644 index 00000000000..61e767d3656 --- /dev/null +++ b/llvm/test/Transforms/NewGVN/pr33187.ll @@ -0,0 +1,148 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +;; Ensure we don't change after value numbering by accidentally deleting the wrong expression. +; RUN: opt -newgvn -S %s | FileCheck %s +define void @fn1() local_unnamed_addr #0 { +; CHECK-LABEL: @fn1( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND_PREHEADER:%.*]] +; CHECK: while.cond: +; CHECK-NEXT: br label [[FOR_COND_PREHEADER]] +; CHECK: for.cond.preheader: +; CHECK-NEXT: [[H_031:%.*]] = phi i32 [ 5, [[ENTRY:%.*]] ], [ [[H_127:%.*]], [[WHILE_COND:%.*]] ] +; CHECK-NEXT: br label [[FOR_BODY:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[H_128:%.*]] = phi i32 [ [[H_031]], [[FOR_COND_PREHEADER]] ], [ [[H_2:%.*]], [[FOR_INC:%.*]] ] +; CHECK-NEXT: br label [[IF_THEN:%.*]] +; CHECK: if.then: +; CHECK-NEXT: br i1 false, label [[L_LOOPEXIT:%.*]], label [[IF_END:%.*]] +; CHECK: if.end: +; CHECK-NEXT: br i1 undef, label [[FOR_INC]], label [[IF_END9:%.*]] +; CHECK: if.end9: +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[H_2]] = phi i32 [ [[H_128]], [[IF_END]] ], [ 0, [[IF_END9]] ] +; CHECK-NEXT: br i1 undef, label [[WHILE_COND10_LOOPEXIT:%.*]], label [[FOR_BODY]] +; CHECK: while.cond10.loopexit: +; CHECK-NEXT: br label [[WHILE_COND10:%.*]] +; CHECK: while.cond10: +; CHECK-NEXT: [[H_127]] = phi i32 [ [[H_126:%.*]], [[IF_END18:%.*]] ], [ [[H_125:%.*]], [[L:%.*]] ], [ [[H_2]], [[WHILE_COND10_LOOPEXIT]] ] +; CHECK-NEXT: br i1 undef, label [[WHILE_COND]], label [[WHILE_BODY12:%.*]] +; CHECK: while.body12: +; CHECK-NEXT: br i1 undef, label [[IF_END18]], label [[L]] +; CHECK: L.loopexit: +; CHECK-NEXT: store i8 undef, i8* null +; CHECK-NEXT: br label [[L]] +; CHECK: L: +; CHECK-NEXT: [[H_125]] = phi i32 [ [[H_127]], [[WHILE_BODY12]] ], [ undef, [[L_LOOPEXIT]] ] +; CHECK-NEXT: br i1 undef, label [[WHILE_COND10]], label [[IF_END18]] +; CHECK: if.end18: +; CHECK-NEXT: [[H_126]] = phi i32 [ [[H_125]], [[L]] ], [ [[H_127]], [[WHILE_BODY12]] ] +; CHECK-NEXT: br label [[WHILE_COND10]] +; +entry: + br label %for.cond.preheader + +while.cond: ; preds = %while.cond10 + br label %for.cond.preheader + +for.cond.preheader: ; preds = %while.cond, %entry + %h.031 = phi i32 [ 5, %entry ], [ %h.127, %while.cond ] + br label %for.body + +for.body: ; preds = %for.inc, %for.cond.preheader + %h.128 = phi i32 [ %h.031, %for.cond.preheader ], [ %h.2, %for.inc ] + br label %if.then + +if.then: ; preds = %for.body + br i1 false, label %L.loopexit, label %if.end + +if.end: ; preds = %if.then + br i1 undef, label %for.inc, label %if.end9 + +if.end9: ; preds = %if.end + br label %for.inc + +for.inc: ; preds = %if.end9, %if.end + %h.2 = phi i32 [ %h.128, %if.end ], [ 0, %if.end9 ] + br i1 undef, label %while.cond10.loopexit, label %for.body + +while.cond10.loopexit: ; preds = %for.inc + %h.2.lcssa = phi i32 [ %h.2, %for.inc ] + br label %while.cond10 + +while.cond10: ; preds = %if.end18, %L, %while.cond10.loopexit + %h.127 = phi i32 [ %h.126, %if.end18 ], [ %h.125, %L ], [ %h.2.lcssa, %while.cond10.loopexit ] + br i1 undef, label %while.cond, label %while.body12 + +while.body12: ; preds = %while.cond10 + br i1 undef, label %if.end18, label %L + +L.loopexit: ; preds = %if.then + br label %L + +L: ; preds = %L.loopexit, %while.body12 + %h.125 = phi i32 [ %h.127, %while.body12 ], [ undef, %L.loopexit ] + br i1 undef, label %while.cond10, label %if.end18 + +if.end18: ; preds = %L, %while.body12 + %h.126 = phi i32 [ %h.125, %L ], [ %h.127, %while.body12 ] + br label %while.cond10 +} + + +define void @hoge() local_unnamed_addr #0 { +; CHECK-LABEL: @hoge( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[TMP:%.*]] = phi i64 [ 0, [[BB:%.*]] ], [ [[TMP2:%.*]], [[BB1]] ] +; CHECK-NEXT: [[TMP2]] = add nuw nsw i64 [[TMP]], 1 +; CHECK-NEXT: br label [[BB1]] +; +bb: + br label %bb1 + +bb1: ; preds = %bb1, %bb + %tmp = phi i64 [ 0, %bb ], [ %tmp2, %bb1 ] + %tmp2 = add nuw nsw i64 %tmp, 1 + br label %bb1 +} + +attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } + + +source_filename = "pr33187-c.ll" + +define void @a() { +; CHECK-LABEL: @a( +; CHECK-NEXT: b: +; CHECK-NEXT: store i8* null, i8** null +; CHECK-NEXT: br label [[D:%.*]] +; CHECK: d: +; CHECK-NEXT: [[I:%.*]] = phi i8* [ null, [[B:%.*]] ], [ [[E:%.*]], [[F:%.*]] ] +; CHECK-NEXT: br i1 undef, label [[F]], label [[G:%.*]] +; CHECK: g: +; CHECK-NEXT: store i8* [[I]], i8** null +; CHECK-NEXT: unreachable +; CHECK: f: +; CHECK-NEXT: [[E]] = getelementptr i8, i8* [[I]], i64 1 +; CHECK-NEXT: br label [[D]] +; +b: + store i8* null, i8** null + br label %d + +d: ; preds = %f, %b + %i = phi i8* [ null, %b ], [ %e, %f ] + br i1 undef, label %f, label %g + +g: ; preds = %d + %h = phi i8* [ %i, %d ] + store i8* %h, i8** null + unreachable + +f: ; preds = %d + %e = getelementptr i8, i8* %i, i64 1 + br label %d +} + |
