NewGVN: Add UnknownExpression and create them for things we can't symbolize. Kill fragile machinery for handling null expressions.

[• dberlin]

Summary

This avoids the very fragile code for null expressions. We could also use a denseset that tracks which things have null expressions instead, but that seems pretty fragile and premature optimization.

This resolves a number of infinite loop cases, test reductions coming.

[davide]

This generally feels like an improvement, but I have a question (inline) about handling of terminators.
I can help reducing the testcase if you provide the original one (not sure which PR this is associated with, if any).

include/llvm/Transforms/Scalar/GVNExpression.h

586 ↗

(On Diff #82758)

auto & probably as cast<> makes the type obvious.

lib/Transforms/Scalar/NewGVN.cpp

644–648 ↗

(On Diff #82758)

I think we may want to add doxygen documentation to every create* function, but probably that can be done separately in a single pass (if you agree, of course).

1015–1032 ↗

(On Diff #82758)

Glad to see this going away =)

1392–1397 ↗

(On Diff #82758)

There's another terminator which can return values, i.e. catchswitch. Maybe we should handle it specially here as well? http://llvm.org/docs/LangRef.html#catchswitch-instruction

[• dberlin]

So, note that i'm wrong about a testcase. This is already test by pr31491.ll.

It's just fixing it in a less fragile way.

lib/Transforms/Scalar/NewGVN.cpp

644–648 ↗

(On Diff #82758)

Sure.
What do you want it to say?

There are only a few that have any special behavior. :)

1392–1397 ↗

(On Diff #82758)

I think i can just change the test to be about whether the terminator is a void type.
I'll check.

[davide]

This looks good with the comment on terminators inline addressed. I wouldn't worry too much about adding a test for catchswitch, but up to you.

lib/Transforms/Scalar/NewGVN.cpp

644–648 ↗

(On Diff #82758)

My bad, I was thinking about the perform* class of function. Some of them are commented (sometimes the comment is trivial) and some of them are not. I'd rather have some uniformity there. This one is good, of course, as it doesn't have any specific behaviour.

1392–1397 ↗

(On Diff #82758)

Yes, I think that's a more robust way of handling (in case somebody introduces a new terminator etc..)

[davide]

Also, after starring at the code for a bit, I think the the idea of introducing an explicit UnknownExpression class instead of having specialized code logic for handling it is very nice. I think it also makes the code easier to read/understand. I did some profiling (on llvm itself, and on some internal benchmarks) and I haven't noticed this handling popping up so I think not using a DenseSet for now is the right thing)

[• dberlin]

The testcase we'd want, i think, is to have an invoke and a catchswitch that both return values.
Previously, it should have considered them the same value, i think.

I actually discovered that part while looking at this comment:

// FIXME: We should eventually be able to replace everything still
// in the initial class with undef, as they should be unreachable.
// Right now, initial still contains some things we skip value
// numbering of (UNREACHABLE's, for example)."

it contained a few invoke's, so i went hunting why.

llvm/trunk/include/llvm/Transforms/Scalar/GVNExpression.h

 class MemoryAccess;
 
 namespace GVNExpression {
 
 enum ExpressionType {
   ET_Base,
   ET_Constant,
   ET_Variable,
+  ET_Unknown,
   ET_BasicStart,
   ET_Basic,
   ET_Call,
   ET_AggregateValue,
   ET_Phi,
   ET_Load,
   ET_Store,
   ET_BasicEnd
public:
   //
   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeConstant, ";
     this->Expression::printInternal(OS, false);
     OS << " constant = " << *ConstantValue;
   }
 };
+
+class UnknownExpression final : public Expression {
+private:
+  Instruction *Inst;
+
+public:
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ET_Unknown;
+  }
+
+  UnknownExpression(Instruction *I) : Expression(ET_Unknown), Inst(I) {}
+  void operator=(const UnknownExpression &) = delete;
+  UnknownExpression(const UnknownExpression &) = delete;
+  UnknownExpression() = delete;
+
+  Instruction *getInstruction() const { return Inst; }
+  void setInstruction(Instruction *I) { Inst = I; }
+  virtual bool equals(const Expression &Other) const override {
+    const auto &OU = cast<UnknownExpression>(Other);
+    return Inst == OU.Inst;
+  }
+  virtual hash_code getHashValue() const override {
+    return hash_combine(getExpressionType(), Inst);
+  }
+  //
+  // Debugging support
+  //
+  virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
+    if (PrintEType)
+      OS << "ExpressionTypeUnknown, ";
+    this->Expression::printInternal(OS, false);
+    OS << " inst = " << *Inst;
+  }
+};
 }
 }
 
 #endif

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

private:
   // Expression handling.
   const Expression *createExpression(Instruction *, const BasicBlock *);
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
                                            const BasicBlock *);
   PHIExpression *createPHIExpression(Instruction *);
   const VariableExpression *createVariableExpression(Value *);
   const ConstantExpression *createConstantExpression(Constant *);
   const Expression *createVariableOrConstant(Value *V, const BasicBlock *B);
+  const UnknownExpression *createUnknownExpression(Instruction *);
   const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *,
                                                const BasicBlock *);
   LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
                                        MemoryAccess *, const BasicBlock *);
 
   const CallExpression *createCallExpression(CallInst *, MemoryAccess *,
                                              const BasicBlock *);
   const AggregateValueExpression *

 }
 
 const ConstantExpression *NewGVN::createConstantExpression(Constant *C) {
   auto *E = new (ExpressionAllocator) ConstantExpression(C);
   E->setOpcode(C->getValueID());
   return E;
 }
 
+const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) {
+  auto *E = new (ExpressionAllocator) UnknownExpression(I);
+  E->setOpcode(I->getOpcode());
+  return E;
+}
+
 const CallExpression *NewGVN::createCallExpression(CallInst *CI,
                                                    MemoryAccess *HV,
                                                    const BasicBlock *B) {
   // FIXME: Add operand bundles for calls.
   auto *E =
       new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, HV);
   setBasicExpressionInfo(CI, E, B);
   return E;
void NewGVN::performCongruenceFinding(Value *V, const Expression *E) {
   // This is guaranteed to return something, since it will at least find
   // INITIAL.
   CongruenceClass *VClass = ValueToClass[V];
   assert(VClass && "Should have found a vclass");
   // Dead classes should have been eliminated from the mapping.
   assert(!VClass->Dead && "Found a dead class");
 
   CongruenceClass *EClass;
-  // Expressions we can't symbolize are always in their own unique
-  // congruence class.  FIXME: This is hard to perfect. Long term, we should try
-  // to create expressions for everything. We should add UnknownExpression(Inst)
-  // or something to avoid wasting time creating real ones.  Then the existing
-  // logic will just work.
-  if (E == nullptr) {
-    // We may have already made a unique class.
-    // Test whether we are still in the initial class, or we have found a class
-    if (VClass == InitialClass || VClass->RepLeader != V) {
-      CongruenceClass *NewClass = createCongruenceClass(V, nullptr);
-      // We should always be adding the member in the below code.
-      EClass = NewClass;
-      DEBUG(dbgs() << "Created new congruence class for " << *V
-                   << " due to nullptr expression\n");
-    } else {
-      EClass = VClass;
-    }
-  } else if (const auto *VE = dyn_cast<VariableExpression>(E)) {
+  if (const auto *VE = dyn_cast<VariableExpression>(E)) {
     EClass = ValueToClass[VE->getVariableValue()];
   } else {
     auto lookupResult = ExpressionToClass.insert({E, nullptr});
 
     // If it's not in the value table, create a new congruence class.
     if (lookupResult.second) {
       CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
       auto place = lookupResult.first;

 void NewGVN::valueNumberInstruction(Instruction *I) {
   DEBUG(dbgs() << "Processing instruction " << *I << "\n");
   if (isInstructionTriviallyDead(I, TLI)) {
     DEBUG(dbgs() << "Skipping unused instruction\n");
     markInstructionForDeletion(I);
     return;
   }
   if (!I->isTerminator()) {
-    const Expression *Symbolized = performSymbolicEvaluation(I, I->getParent());
+    const auto *Symbolized = performSymbolicEvaluation(I, I->getParent());
+    // If we couldn't come up with a symbolic expression, use the unknown
+    // expression
+    if (Symbolized == nullptr)
+      Symbolized = createUnknownExpression(I);
     performCongruenceFinding(I, Symbolized);
   } else {
+    // Handle terminators that return values. All of them produce values we
+    // don't currently understand.
+    if (!I->getType()->isVoidTy()){
+      auto *Symbolized = createUnknownExpression(I);
+      performCongruenceFinding(I, Symbolized);
+    }
     processOutgoingEdges(dyn_cast<TerminatorInst>(I), I->getParent());
   }
 }
 
 // Verify the that the memory equivalence table makes sense relative to the
 // congruence classes.
 void NewGVN::verifyMemoryCongruency() {
   // Anything equivalent in the memory access table should be in the same