[IRSim] Adding ilist for IRInstructionData

[AndrewLitteken]

Summary

The IRInstructionData structs are a different representation of the program. This list treats the program as if it was "flattened" and the only parent is this list. This lets us easily create ranges of instructions.

[AndrewLitteken]

Updating for clang-format.

[jroelofs]

LGTM

[AndrewLitteken]

Updating to add the SpecificBumpAllocator for the IRInstructionDataList.

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Allocator.h"
 
 namespace llvm {
 namespace IRSimilarity {
 
+struct IRInstructionDataList;
+
 /// This represents what is and is not supported when finding similarity in
 /// Instructions.
 ///
 /// Legal Instructions are considered when looking at similarity between
 /// Instructions.
 ///
 /// Illegal Instructions cannot be considered when looking for similarity
 /// between Instructions. They act as boundaries between similarity regions.
struct IRInstructionData : ilist_node<IRInstructionData> {
   /// considered similar.
   bool Legal;
 
   /// Gather the information that is difficult to gather for an Instruction, or
   /// is changed. i.e. the operands of an Instruction and the Types of those
   /// operands. This extra information allows for similarity matching to make
   /// assertions that allow for more flexibility when checking for whether an
   /// Instruction performs the same operation.
-  IRInstructionData(Instruction &I, bool Legality);
+  IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL);
 
   /// Hashes \p Value based on its opcode, types, and operand types.
   /// Two IRInstructionData instances produce the same hash when they perform
   /// the same operation.
   ///
   /// As a simple example, consider the following instructions.
   ///
   /// \code
friend hash_code hash_value(const IRInstructionData &ID) {
     for (Value *V : ID.OperVals)
       OperTypes.push_back(V->getType());
 
     return llvm::hash_combine(
         llvm::hash_value(ID.Inst->getOpcode()),
         llvm::hash_value(ID.Inst->getType()),
         llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
   }
+
+  IRInstructionDataList *IDL = nullptr;
 };
 
+struct IRInstructionDataList : simple_ilist<IRInstructionData> {};
+
 /// Compare one IRInstructionData class to another IRInstructionData class for
 /// whether they are performing a the same operation, and can mapped to the
 /// same value. For regular instructions if the hash value is the same, then
 /// they will also be close.
 ///
 /// \param A - The first IRInstructionData class to compare
 /// \param B - The second IRInstructionData class to compare
 /// \returns true if \p A and \p B are similar enough to be mapped to the same
struct IRInstructionMapper {
   /// to be considered for similarity.
   bool HaveLegalRange = false;
 
   /// This allocator pointer is in charge of holding on to the IRInstructionData
   /// so it is not deallocated until whatever external tool is using it is done
   /// with the information.
   SpecificBumpPtrAllocator<IRInstructionData> *InstDataAllocator = nullptr;
 
+  /// This allocator pointer is in charge of creating the IRInstructionDataList
+  /// so it is not deallocated until whatever external tool is using it is done
+  /// with the information.
+  SpecificBumpPtrAllocator<IRInstructionDataList> *IDLAllocator = nullptr;
+
   /// Get an allocated IRInstructionData struct using the InstDataAllocator.
   ///
   /// \param I - The Instruction to wrap with IRInstructionData.
   /// \param Legality - A boolean value that is true if the instruction is to
   /// be considered for similarity, and false if not.
+  /// \param IDL - The InstructionDataList that the IRInstructionData is
+  /// inserted into.
   /// \returns An allocated IRInstructionData struct.
-  IRInstructionData *allocateIRInstructionData(Instruction &I, bool Legality);
+  IRInstructionData *allocateIRInstructionData(Instruction &I, bool Legality,
+                                               IRInstructionDataList &IDL);
+
+  /// Get an allocated IRInstructionDataList object using the IDLAllocator.
+  ///
+  /// \returns An allocated IRInstructionDataList object.
+  IRInstructionDataList *allocateIRInstructionDataList();
+
+  IRInstructionDataList *IDL = nullptr;
 
   /// Maps the Instructions in a BasicBlock \p BB to legal or illegal integers
   /// determined by \p InstrType. Two Instructions are mapped to the same value
   /// if they are close as defined by the InstructionData class above.
   ///
   /// \param [in] BB - The BasicBlock to be mapped to integers.
   /// \param [in,out] InstrList - Vector of IRInstructionData to append to.
   /// \param [in,out] IntegerMapping - Vector of unsigned integers to append to.
struct IRInstructionMapper {
   /// \param [in,out] InstrList - Vector of IRInstructionData to append to.
   /// \param End - true if creating a dummy IRInstructionData at the end of a
   /// basic block.
   /// \returns The integer \p It was mapped to.
   unsigned mapToIllegalUnsigned(
       BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
       std::vector<IRInstructionData *> &InstrListForBB, bool End = false);
 
-  IRInstructionMapper(SpecificBumpPtrAllocator<IRInstructionData> *IDA)
-      : InstDataAllocator(IDA) {
+  IRInstructionMapper(SpecificBumpPtrAllocator<IRInstructionData> *IDA,
+                      SpecificBumpPtrAllocator<IRInstructionDataList> *IDLA)
+      : InstDataAllocator(IDA), IDLAllocator(IDLA) {
     // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
     // changed.
     assert(DenseMapInfo<unsigned>::getEmptyKey() == static_cast<unsigned>(-1) &&
            "DenseMapInfo<unsigned>'s empty key isn't -1!");
     assert(DenseMapInfo<unsigned>::getTombstoneKey() ==
                static_cast<unsigned>(-2) &&
            "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
+
+    IDL = new (IDLAllocator->Allocate())
+        IRInstructionDataList();
   }
 
   /// Custom InstVisitor to classify different instructions for whether it can
   /// be analyzed for similarity.
   struct InstructionClassification
       : public InstVisitor<InstructionClassification, InstrType> {
     InstructionClassification() {}
 

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

 #include "llvm/Analysis/IRSimilarityIdentifier.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/User.h"
 
 using namespace llvm;
 using namespace IRSimilarity;
 
-IRInstructionData::IRInstructionData(Instruction &I, bool Legality)
-    : Inst(&I), Legal(Legality) {
+IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
+                                     IRInstructionDataList &IDList)
+    : Inst(&I), Legal(Legality), IDL(&IDList) {
   // Here we collect the operands to be used to determine whether two
   // instructions are similar to one another.
   for (Use &OI : I.operands())
     OperVals.push_back(OI.get());
 }
 
 bool IRSimilarity::isClose(const IRInstructionData &A,
                            const IRInstructionData &B) {
for (BasicBlock::iterator Et = BB.end(); It != Et; ++It) {
     case InstrType::Invisible:
       AddedIllegalLastTime = false;
       break;
     }
   }
 
   if (HaveLegalRange) {
     mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
+    for_each(InstrListForBB,
+             [this](IRInstructionData *ID) { this->IDL->push_back(*ID); });
     InstrList.insert(InstrList.end(), InstrListForBB.begin(),
                      InstrListForBB.end());
     IntegerMapping.insert(IntegerMapping.end(), IntegerMappingForBB.begin(),
                           IntegerMappingForBB.end());
   }
 }
 
 // TODO: This is the same as the MachineOutliner, and should be consolidated
 // into the same interface.
 unsigned IRInstructionMapper::mapToLegalUnsigned(
     BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
     std::vector<IRInstructionData *> &InstrListForBB) {
   // We added something legal, so we should unset the AddedLegalLastTime
   // flag.
   AddedIllegalLastTime = false;
 
   // If we have at least two adjacent legal instructions (which may have
   // invisible instructions in between), remember that.
   if (CanCombineWithPrevInstr)
     HaveLegalRange = true;
   CanCombineWithPrevInstr = true;
 
   // Get the integer for this instruction or give it the current
   // LegalInstrNumber.
-  IRInstructionData *ID = allocateIRInstructionData(*It, true);
+  IRInstructionData *ID = allocateIRInstructionData(*It, true, *IDL);
   InstrListForBB.push_back(ID);
 
   // Add to the instruction list
   bool WasInserted;
   DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits>::iterator
       ResultIt;
   std::tie(ResultIt, WasInserted) =
       InstructionIntegerMap.insert(std::make_pair(ID, LegalInstrNumber));
assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
          "Tried to assign DenseMap tombstone or empty key to instruction.");
   assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
          "Tried to assign DenseMap tombstone or empty key to instruction.");
 
   return INumber;
 }
 
 IRInstructionData *
-IRInstructionMapper::allocateIRInstructionData(Instruction &I, bool Legality) {
-  return new (InstDataAllocator->Allocate()) IRInstructionData(I, Legality);
+IRInstructionMapper::allocateIRInstructionData(Instruction &I, bool Legality,
+                                               IRInstructionDataList &IDL) {
+  return new (InstDataAllocator->Allocate()) IRInstructionData(I, Legality, IDL);
+}
+
+IRInstructionDataList *
+IRInstructionMapper::allocateIRInstructionDataList() {
+  return new (IDLAllocator->Allocate()) IRInstructionDataList();
 }
 
 // TODO: This is the same as the MachineOutliner, and should be consolidated
 // into the same interface.
 unsigned IRInstructionMapper::mapToIllegalUnsigned(
     BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
     std::vector<IRInstructionData *> &InstrListForBB, bool End) {
   // Can't combine an illegal instruction. Set the flag.
   CanCombineWithPrevInstr = false;
 
   // Only add one illegal number per range of legal numbers.
   if (AddedIllegalLastTime)
     return IllegalInstrNumber;
 
   IRInstructionData *ID = nullptr;
   if (!End)
-    ID = allocateIRInstructionData(*It, false);
+    ID = allocateIRInstructionData(*It, false, *IDL);
   InstrListForBB.push_back(ID);
 
   // Remember that we added an illegal number last time.
   AddedIllegalLastTime = true;
   unsigned INumber = IllegalInstrNumber;
   IntegerMappingForBB.push_back(IllegalInstrNumber--);
 
   assert(LegalInstrNumber < IllegalInstrNumber &&

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
   std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
   assert(M && "Bad LLVM IR?");
   return M;
 }
 
 void getVectors(Module &M, std::vector<IRInstructionData *> &InstrList,
                 std::vector<unsigned> &UnsignedVec) {
   SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
-  IRInstructionMapper Mapper(&InstDataAllocator);
+  SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
+  IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
 
   for (Function &F : M)
     for (BasicBlock &BB : F)
       Mapper.convertToUnsignedVec(BB, InstrList, UnsignedVec);
 }
 
 // Checks that different opcodes are mapped to different values.
 TEST(IRInstructionMapper, OpcodeDifferentiation) {
TEST(IRInstructionMapper, ZextTypeDifference) {
 
   getVectors(*M, InstrList, UnsignedVec);
 
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
   ASSERT_TRUE(UnsignedVec.size() == 3);
   ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
 }
 
-
 // Checks that the sexts that have the different type parameters map to the
 // different unsigned integers.
 TEST(IRInstructionMapper, SextTypeDifference) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i8 %b) {
                           bb0:
                              %0 = sext i32 %a to i64
                              %1 = sext i8 %b to i32