1 //===- IRSimilarityIdentifier.cpp - Find similarity in a module -----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // \file
10 // Implementation file for the IRSimilarityIdentifier for identifying
11 // similarities in IR including the IRInstructionMapper.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/Analysis/IRSimilarityIdentifier.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/IR/Intrinsics.h"
18 #include "llvm/IR/User.h"
19 
20 using namespace llvm;
21 using namespace IRSimilarity;
22 
23 IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
24                                      IRInstructionDataList &IDList)
25     : Inst(&I), Legal(Legality), IDL(&IDList) {
26   // Here we collect the operands to be used to determine whether two
27   // instructions are similar to one another.
28   for (Use &OI : I.operands())
29     OperVals.push_back(OI.get());
30 }
31 
32 bool IRSimilarity::isClose(const IRInstructionData &A,
33                            const IRInstructionData &B) {
34   return A.Legal && A.Inst->isSameOperationAs(B.Inst);
35 }
36 
37 // TODO: This is the same as the MachineOutliner, and should be consolidated
38 // into the same interface.
39 void IRInstructionMapper::convertToUnsignedVec(
40     BasicBlock &BB, std::vector<IRInstructionData *> &InstrList,
41     std::vector<unsigned> &IntegerMapping) {
42   BasicBlock::iterator It = BB.begin();
43 
44   std::vector<unsigned> IntegerMappingForBB;
45   std::vector<IRInstructionData *> InstrListForBB;
46 
47   HaveLegalRange = false;
48   CanCombineWithPrevInstr = false;
49   AddedIllegalLastTime = true;
50 
51   for (BasicBlock::iterator Et = BB.end(); It != Et; ++It) {
52     switch (InstClassifier.visit(*It)) {
53     case InstrType::Legal:
54       mapToLegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
55       break;
56     case InstrType::Illegal:
57       mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
58       break;
59     case InstrType::Invisible:
60       AddedIllegalLastTime = false;
61       break;
62     }
63   }
64 
65   if (HaveLegalRange) {
66     mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
67     for_each(InstrListForBB,
68              [this](IRInstructionData *ID) { this->IDL->push_back(*ID); });
69     InstrList.insert(InstrList.end(), InstrListForBB.begin(),
70                      InstrListForBB.end());
71     IntegerMapping.insert(IntegerMapping.end(), IntegerMappingForBB.begin(),
72                           IntegerMappingForBB.end());
73   }
74 }
75 
76 // TODO: This is the same as the MachineOutliner, and should be consolidated
77 // into the same interface.
78 unsigned IRInstructionMapper::mapToLegalUnsigned(
79     BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
80     std::vector<IRInstructionData *> &InstrListForBB) {
81   // We added something legal, so we should unset the AddedLegalLastTime
82   // flag.
83   AddedIllegalLastTime = false;
84 
85   // If we have at least two adjacent legal instructions (which may have
86   // invisible instructions in between), remember that.
87   if (CanCombineWithPrevInstr)
88     HaveLegalRange = true;
89   CanCombineWithPrevInstr = true;
90 
91   // Get the integer for this instruction or give it the current
92   // LegalInstrNumber.
93   IRInstructionData *ID = allocateIRInstructionData(*It, true, *IDL);
94   InstrListForBB.push_back(ID);
95 
96   // Add to the instruction list
97   bool WasInserted;
98   DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits>::iterator
99       ResultIt;
100   std::tie(ResultIt, WasInserted) =
101       InstructionIntegerMap.insert(std::make_pair(ID, LegalInstrNumber));
102   unsigned INumber = ResultIt->second;
103 
104   // There was an insertion.
105   if (WasInserted)
106     LegalInstrNumber++;
107 
108   IntegerMappingForBB.push_back(INumber);
109 
110   // Make sure we don't overflow or use any integers reserved by the DenseMap.
111   assert(LegalInstrNumber < IllegalInstrNumber &&
112          "Instruction mapping overflow!");
113 
114   assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
115          "Tried to assign DenseMap tombstone or empty key to instruction.");
116   assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
117          "Tried to assign DenseMap tombstone or empty key to instruction.");
118 
119   return INumber;
120 }
121 
122 IRInstructionData *
123 IRInstructionMapper::allocateIRInstructionData(Instruction &I, bool Legality,
124                                                IRInstructionDataList &IDL) {
125   return new (InstDataAllocator->Allocate()) IRInstructionData(I, Legality, IDL);
126 }
127 
128 IRInstructionDataList *
129 IRInstructionMapper::allocateIRInstructionDataList() {
130   return new (IDLAllocator->Allocate()) IRInstructionDataList();
131 }
132 
133 // TODO: This is the same as the MachineOutliner, and should be consolidated
134 // into the same interface.
135 unsigned IRInstructionMapper::mapToIllegalUnsigned(
136     BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
137     std::vector<IRInstructionData *> &InstrListForBB, bool End) {
138   // Can't combine an illegal instruction. Set the flag.
139   CanCombineWithPrevInstr = false;
140 
141   // Only add one illegal number per range of legal numbers.
142   if (AddedIllegalLastTime)
143     return IllegalInstrNumber;
144 
145   IRInstructionData *ID = nullptr;
146   if (!End)
147     ID = allocateIRInstructionData(*It, false, *IDL);
148   InstrListForBB.push_back(ID);
149 
150   // Remember that we added an illegal number last time.
151   AddedIllegalLastTime = true;
152   unsigned INumber = IllegalInstrNumber;
153   IntegerMappingForBB.push_back(IllegalInstrNumber--);
154 
155   assert(LegalInstrNumber < IllegalInstrNumber &&
156          "Instruction mapping overflow!");
157 
158   assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
159          "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
160 
161   assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
162          "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
163 
164   return INumber;
165 }
166