[llvm][IROutliner] Account for return void in sort comparator

[DavidSpickett]

Summary

This fixes 69 llvm tests that failed when EXPENSIVE_CHECKS was enabled.
llvm/test/Transforms/IROutliner/outlining-commutative-operands-opposite-order.ll
is one example.

When we have EXPENSIVE_CHECKS, _GLIBCXX_DEBUG is defined. This means
that libstdc++ will call the compare function to check if it is
implemented correctly (that !(a < a) is true).

This happens even if there is only one item and here, we expect
to see one return void or multiple return constant integer.

Don't sort if we have 1 item, but do assert that it is the 1
ret void we expect. In the comparator, assert that neither
Value is a nullptr in case one ended up in a the list somehow.

[DavidSpickett]

The thing I'm not sure of here is if we should ever expect to have >1 item in the map if there is a "ret void". Or if it is one of two states:

• one ret void
• multiple return constant integer

I'm not familiar enough with this area to know that. If it's like that then it's probably better to say if EXPENSIVE_CHECKS defined and size is 1, skip the sort entirely.

[AndrewLitteken]

There shouldn't be a case where there is a ret void and a ret <Constant Int> in a function. I am pretty sure that there will only more than one return value when the function has more than one exit block. In that case, there are multiple return values have an integer value. So the cases you laid out should be correct.

So it may be better to use your suggestion to only sort when there is more than one value, and add two assertions. One to check that the only value is a nullptr when the map is size 1, and then another in the sort itself that checks that neither the LHS or the RHS is a nullptr.

[DavidSpickett]

Thanks for explaining, I'll update this shortly.

[DavidSpickett]

Implement suggested changes.

[AndrewLitteken]

LGTM with small nit.

llvm/lib/Transforms/IPO/IROutliner.cpp

191

small nit, you could add an early return here, and then remove the else statement.

[DavidSpickett]

Use early return.

llvm/lib/Transforms/IPO/IROutliner.cpp

 //===- IROutliner.cpp -- Outline Similar Regions ----------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///

 /// \param SortedKeys - The vector the keys will be return in and sorted.
 /// \param Map - The DenseMap containing keys to sort.
 static void getSortedConstantKeys(std::vector<Value *> &SortedKeys,
                                   DenseMap<Value *, BasicBlock *> &Map) {
   for (auto &VtoBB : Map)
     SortedKeys.push_back(VtoBB.first);
 
   stable_sort(SortedKeys, [](const Value *LHS, const Value *RHS) {
+    // We may be dealing with a return void here in which case Value* will be
+    // nullptr. Assume that void is < any ConstantInt.
+    if ((LHS == nullptr) && (RHS == nullptr))
+      return false;
+    if (LHS == nullptr)
+      return true;
+    if (RHS == nullptr)
+      return false;
+
     const ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS);
     const ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS);
     assert(RHSC && "Not a constant integer in return value?");
     assert(LHSC && "Not a constant integer in return value?");
 
     return LHSC->getLimitedValue() < RHSC->getLimitedValue();
   });
 }
 
 Value *OutlinableRegion::findCorrespondingValueIn(const OutlinableRegion &Other,
                                                   Value *V) {
   Optional<unsigned> GVN = Candidate->getGVN(V);
   assert(GVN && "No GVN for incoming value");
   Optional<unsigned> CanonNum = Candidate->getCanonicalNum(*GVN);
   Optional<unsigned> FirstGVN = Other.Candidate->fromCanonicalNum(*CanonNum);
   Optional<Value *> FoundValueOpt = Other.Candidate->fromGVN(*FirstGVN);
   return FoundValueOpt.value_or(nullptr);
 }