16 #include "llvm/Config/llvm-config.h"
56 unsigned LastGlobalConstantID = 0;
57 unsigned LastGlobalValueID = 0;
61 bool isGlobalConstant(
unsigned ID)
const {
62 return ID <= LastGlobalConstantID;
65 bool isGlobalValue(
unsigned ID)
const {
66 return ID <= LastGlobalValueID && !isGlobalConstant(
ID);
69 unsigned size()
const {
return IDs.
size(); }
70 std::pair<unsigned, bool> &operator[](
const Value *V) {
return IDs[V]; }
72 std::pair<unsigned, bool>
lookup(
const Value *V)
const {
78 unsigned ID = IDs.
size() + 1;
86 if (OM.lookup(V).first)
89 if (
const Constant *
C = dyn_cast<Constant>(V)) {
90 if (
C->getNumOperands() && !isa<GlobalValue>(
C)) {
91 for (
const Value *
Op :
C->operands())
92 if (!isa<BasicBlock>(
Op) && !isa<GlobalValue>(
Op))
94 if (
auto *CE = dyn_cast<ConstantExpr>(
C))
95 if (CE->getOpcode() == Instruction::ShuffleVector)
96 orderValue(CE->getShuffleMaskForBitcode(), OM);
116 if (
G.hasInitializer())
117 if (!isa<GlobalValue>(
G.getInitializer()))
120 if (!isa<GlobalValue>(A.getAliasee()))
123 if (!isa<GlobalValue>(
I.getResolver()))
126 for (
const Use &U :
F.operands())
127 if (!isa<GlobalValue>(U.get()))
136 auto orderConstantValue = [&OM](
const Value *V) {
137 if ((isa<Constant>(V) && !isa<GlobalValue>(V)) || isa<InlineAsm>(V))
141 if (
F.isDeclaration())
145 for (
const Value *V :
I.operands()) {
146 if (
const auto *MAV = dyn_cast<MetadataAsValue>(V)) {
147 if (
const auto *VAM =
148 dyn_cast<ValueAsMetadata>(MAV->getMetadata())) {
149 orderConstantValue(VAM->getValue());
150 }
else if (
const auto *
AL =
151 dyn_cast<DIArgList>(MAV->getMetadata())) {
152 for (
const auto *VAM :
AL->getArgs())
153 orderConstantValue(VAM->getValue());
158 OM.LastGlobalConstantID = OM.size();
176 OM.LastGlobalValueID = OM.size();
179 if (
F.isDeclaration())
190 for (
const Value *
Op :
I.operands())
191 if ((isa<Constant>(*
Op) && !isa<GlobalValue>(*
Op)) ||
194 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
195 orderValue(SVI->getShuffleMaskForBitcode(), OM);
208 using Entry = std::pair<const Use *, unsigned>;
212 if (OM.lookup(U.getUser()).first)
213 List.push_back(std::make_pair(&U,
List.size()));
219 bool IsGlobalValue = OM.isGlobalValue(
ID);
221 const Use *LU = L.first;
222 const Use *RU = R.first;
226 auto LID = OM.lookup(LU->getUser()).first;
227 auto RID = OM.lookup(RU->getUser()).first;
235 if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) {
237 return LU->getOperandNo() > RU->getOperandNo();
259 return LU->getOperandNo() < RU->getOperandNo();
260 return LU->getOperandNo() > RU->getOperandNo();
268 Stack.emplace_back(V,
F,
List.size());
269 assert(
List.size() == Stack.back().Shuffle.size() &&
"Wrong size");
270 for (
size_t I = 0,
E =
List.size();
I !=
E; ++
I)
271 Stack.back().Shuffle[
I] =
List[
I].second;
276 auto &IDPair = OM[V];
277 assert(IDPair.first &&
"Unmapped value");
283 IDPair.second =
true;
288 if (
const Constant *
C = dyn_cast<Constant>(V)) {
289 if (
C->getNumOperands()) {
290 for (
const Value *
Op :
C->operands())
291 if (isa<Constant>(
Op))
293 if (
auto *CE = dyn_cast<ConstantExpr>(
C))
294 if (CE->getOpcode() == Instruction::ShuffleVector)
315 if (
F.isDeclaration())
323 for (
const Value *
Op :
I.operands())
324 if (isa<Constant>(*
Op) || isa<InlineAsm>(*
Op))
326 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
346 if (
G.hasInitializer())
353 for (
const Use &U :
F.operands())
377 EnumerateAttributes(
F.getAttributes());
388 EnumerateValue(&GIF);
394 if (GV.hasInitializer())
395 EnumerateValue(GV.getInitializer());
398 if (GV.hasAttributes())
404 EnumerateValue(GA.getAliasee());
408 EnumerateValue(GIF.getResolver());
412 for (
const Use &U :
F.operands())
413 EnumerateValue(U.get());
423 EnumerateValueSymbolTable(
M.getValueSymbolTable());
424 EnumerateNamedMetadata(
M);
429 GV.getAllMetadata(MDs);
430 for (
const auto &
I : MDs)
434 EnumerateMetadata(
nullptr,
I.second);
444 F.getAllMetadata(MDs);
445 for (
const auto &
I : MDs)
446 EnumerateMetadata(
F.isDeclaration() ?
nullptr : &
F,
I.second);
450 for (
const Use &
Op :
I.operands()) {
451 auto *MD = dyn_cast<MetadataAsValue>(&
Op);
453 EnumerateOperandType(
Op);
460 if (isa<LocalAsMetadata>(MD->getMetadata()))
462 if (
auto *
AL = dyn_cast<DIArgList>(MD->getMetadata())) {
463 for (
auto *VAM :
AL->getArgs())
464 if (isa<ConstantAsMetadata>(VAM))
465 EnumerateMetadata(&
F, VAM);
469 EnumerateMetadata(&
F, MD->getMetadata());
471 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
473 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I))
475 if (
auto *AI = dyn_cast<AllocaInst>(&
I))
478 if (
const auto *Call = dyn_cast<CallBase>(&
I)) {
479 EnumerateAttributes(Call->getAttributes());
485 I.getAllMetadataOtherThanDebugLoc(MDs);
486 for (
unsigned i = 0,
e = MDs.size();
i !=
e; ++
i)
487 EnumerateMetadata(&
F, MDs[
i].second);
493 EnumerateMetadata(&
F,
Op);
503 assert(
I != InstructionMap.
end() &&
"Instruction is not mapped!");
508 unsigned ComdatID = Comdats.
idFor(
C);
509 assert(ComdatID &&
"Comdat not found!");
514 InstructionMap[
I] = InstructionCount++;
518 if (
auto *MD = dyn_cast<MetadataAsValue>(V))
523 return I->second - 1;
526 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
536 const char *Name)
const {
537 OS <<
"Map Name: " <<
Name <<
"\n";
538 OS <<
"Size: " <<
Map.size() <<
"\n";
539 for (
const auto &
I : Map) {
542 OS <<
"Value: " << V->
getName();
544 OS <<
"Value: [null]\n";
549 for (
const Use &U : V->
uses()) {
553 OS <<
" " << U->getName();
562 const char *Name)
const {
563 OS <<
"Map Name: " <<
Name <<
"\n";
564 OS <<
"Size: " <<
Map.size() <<
"\n";
565 for (
const auto &
I : Map) {
567 OS <<
"Metadata: slot = " <<
I.second.ID <<
"\n";
568 OS <<
"Metadata: function = " <<
I.second.F <<
"\n";
576 void ValueEnumerator::EnumerateValueSymbolTable(
const ValueSymbolTable &VST) {
579 EnumerateValue(
VI->getValue());
584 void ValueEnumerator::EnumerateNamedMetadata(
const Module &M) {
585 for (
const auto &
I :
M.named_metadata())
586 EnumerateNamedMDNode(&
I);
589 void ValueEnumerator::EnumerateNamedMDNode(
const NamedMDNode *MD) {
594 unsigned ValueEnumerator::getMetadataFunctionID(
const Function *
F)
const {
599 EnumerateMetadata(getMetadataFunctionID(
F), MD);
602 void ValueEnumerator::EnumerateFunctionLocalMetadata(
604 EnumerateFunctionLocalMetadata(getMetadataFunctionID(&
F), Local);
607 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
609 EnumerateFunctionLocalListMetadata(getMetadataFunctionID(&
F), ArgList);
612 void ValueEnumerator::dropFunctionFromMetadata(
613 MetadataMapType::value_type &FirstMD) {
616 auto &Entry = MD.second;
628 if (
auto *
N = dyn_cast<MDNode>(MD.first))
629 Worklist.push_back(
N);
632 while (!Worklist.empty())
636 auto MD = MetadataMap.
find(
Op);
637 if (MD != MetadataMap.
end())
642 void ValueEnumerator::EnumerateMetadata(
unsigned F,
const Metadata *MD) {
652 if (
const MDNode *
N = enumerateMetadataImpl(
F, MD))
653 Worklist.push_back(std::make_pair(
N,
N->op_begin()));
655 while (!Worklist.empty()) {
656 const MDNode *
N = Worklist.back().first;
661 Worklist.back().second,
N->op_end(),
662 [&](
const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
663 if (
I !=
N->op_end()) {
664 auto *
Op = cast<MDNode>(*
I);
665 Worklist.back().second = ++
I;
668 if (
Op->isDistinct() && !
N->isDistinct())
669 DelayedDistinctNodes.push_back(
Op);
671 Worklist.push_back(std::make_pair(
Op,
Op->op_begin()));
678 MetadataMap[
N].ID = MDs.size();
682 if (Worklist.empty() || Worklist.back().first->isDistinct()) {
683 for (
const MDNode *
N : DelayedDistinctNodes)
684 Worklist.push_back(std::make_pair(
N,
N->op_begin()));
685 DelayedDistinctNodes.
clear();
690 const MDNode *ValueEnumerator::enumerateMetadataImpl(
unsigned F,
696 (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
697 "Invalid metadata kind");
699 auto Insertion = MetadataMap.
insert(std::make_pair(MD, MDIndex(
F)));
700 MDIndex &Entry = Insertion.first->second;
701 if (!Insertion.second) {
703 if (Entry.hasDifferentFunction(
F))
704 dropFunctionFromMetadata(*Insertion.first);
709 if (
auto *
N = dyn_cast<MDNode>(MD))
714 Entry.ID = MDs.size();
717 if (
auto *
C = dyn_cast<ConstantAsMetadata>(MD))
718 EnumerateValue(
C->getValue());
725 void ValueEnumerator::EnumerateFunctionLocalMetadata(
727 assert(
F &&
"Expected a function");
736 MDs.push_back(Local);
738 Index.ID = MDs.size();
740 EnumerateValue(
Local->getValue());
745 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
747 assert(
F &&
"Expected a function");
750 MDIndex &
Index = MetadataMap[ArgList];
757 if (isa<LocalAsMetadata>(VAM)) {
759 "LocalAsMetadata should be enumerated before DIArgList");
761 "Expected LocalAsMetadata in the same function");
763 assert(isa<ConstantAsMetadata>(VAM) &&
764 "Expected LocalAsMetadata or ConstantAsMetadata");
766 "Constant should be enumerated beforeDIArgList");
767 EnumerateMetadata(
F, VAM);
771 MDs.push_back(ArgList);
773 Index.ID = MDs.size();
778 if (isa<MDString>(MD))
783 auto *
N = dyn_cast<MDNode>(MD);
789 return N->isDistinct() ? 2 : 3;
792 void ValueEnumerator::organizeMetadata() {
794 "Metadata map and vector out of sync");
804 Order.push_back(MetadataMap.
lookup(MD));
819 std::vector<const Metadata *> OldMDs;
821 MDs.reserve(OldMDs.size());
822 for (
unsigned I = 0,
E = Order.size();
I !=
E && !Order[
I].F; ++
I) {
823 auto *MD = Order[
I].get(OldMDs);
825 MetadataMap[MD].ID =
I + 1;
826 if (isa<MDString>(MD))
831 if (MDs.size() == Order.size())
836 FunctionMDs.reserve(OldMDs.size());
838 for (
unsigned I = MDs.size(),
E = Order.size(),
ID = MDs.size();
I !=
E;
840 unsigned F = Order[
I].F;
843 }
else if (PrevF !=
F) {
844 R.Last = FunctionMDs.size();
846 R.First = FunctionMDs.size();
852 auto *MD = Order[
I].get(OldMDs);
853 FunctionMDs.push_back(MD);
854 MetadataMap[MD].ID = ++
ID;
855 if (isa<MDString>(MD))
858 R.Last = FunctionMDs.size();
859 FunctionMDInfo[PrevF] =
R;
862 void ValueEnumerator::incorporateFunctionMetadata(
const Function &
F) {
863 NumModuleMDs = MDs.size();
866 NumMDStrings =
R.NumStrings;
867 MDs.insert(MDs.end(), FunctionMDs.begin() +
R.First,
868 FunctionMDs.begin() +
R.Last);
871 void ValueEnumerator::EnumerateValue(
const Value *V) {
873 assert(!isa<MetadataAsValue>(V) &&
"EnumerateValue doesn't handle Metadata!");
879 Values[ValueID - 1].second++;
883 if (
auto *GO = dyn_cast<GlobalObject>(V))
884 if (
const Comdat *
C = GO->getComdat())
890 if (
const Constant *
C = dyn_cast<Constant>(V)) {
891 if (isa<GlobalValue>(
C)) {
893 }
else if (
C->getNumOperands()) {
904 if (!isa<BasicBlock>(*
I))
906 if (
auto *CE = dyn_cast<ConstantExpr>(
C)) {
907 if (
CE->getOpcode() == Instruction::ShuffleVector)
908 EnumerateValue(
CE->getShuffleMaskForBitcode());
909 if (
auto *
GEP = dyn_cast<GEPOperator>(CE))
915 Values.push_back(std::make_pair(V, 1U));
922 Values.push_back(std::make_pair(V, 1U));
923 ValueID = Values.size();
927 unsigned *
TypeID = &TypeMap[Ty];
936 if (
StructType *STy = dyn_cast<StructType>(Ty))
937 if (!STy->isLiteral())
964 void ValueEnumerator::EnumerateOperandType(
const Value *V) {
967 assert(!isa<MetadataAsValue>(V) &&
"Unexpected metadata operand");
969 const Constant *
C = dyn_cast<Constant>(V);
980 for (
const Value *
Op :
C->operands()) {
983 if (isa<BasicBlock>(
Op))
986 EnumerateOperandType(
Op);
988 if (
auto *CE = dyn_cast<ConstantExpr>(
C)) {
989 if (
CE->getOpcode() == Instruction::ShuffleVector)
990 EnumerateOperandType(
CE->getShuffleMaskForBitcode());
991 if (
CE->getOpcode() == Instruction::GetElementPtr)
992 EnumerateType(cast<GEPOperator>(CE)->getSourceElementType());
996 void ValueEnumerator::EnumerateAttributes(
AttributeList PAL) {
1001 unsigned &Entry = AttributeListMap[PAL];
1004 AttributeLists.push_back(PAL);
1005 Entry = AttributeLists.size();
1014 unsigned &Entry = AttributeGroupMap[Pair];
1016 AttributeGroups.push_back(Pair);
1017 Entry = AttributeGroups.size();
1020 if (Attr.isTypeAttribute())
1028 InstructionCount = 0;
1029 NumModuleValues = Values.size();
1033 incorporateFunctionMetadata(
F);
1036 for (
const auto &
I :
F.args()) {
1038 if (
I.hasAttribute(Attribute::ByVal))
1040 else if (
I.hasAttribute(Attribute::StructRet))
1042 else if (
I.hasAttribute(Attribute::ByRef))
1045 FirstFuncConstantID = Values.size();
1050 for (
const Use &OI :
I.operands()) {
1051 if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
1054 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
1055 EnumerateValue(SVI->getShuffleMaskForBitcode());
1057 BasicBlocks.push_back(&
BB);
1063 EnumerateAttributes(
F.getAttributes());
1065 FirstInstID = Values.size();
1072 for (
const Use &OI :
I.operands()) {
1073 if (
auto *MD = dyn_cast<MetadataAsValue>(&OI)) {
1074 if (
auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) {
1076 FnLocalMDVector.push_back(Local);
1077 }
else if (
auto *ArgList = dyn_cast<DIArgList>(MD->getMetadata())) {
1078 ArgListMDVector.push_back(ArgList);
1080 if (
auto *Local = dyn_cast<LocalAsMetadata>(VMD)) {
1083 FnLocalMDVector.push_back(Local);
1090 if (!
I.getType()->isVoidTy())
1096 for (
unsigned i = 0,
e = FnLocalMDVector.size();
i !=
e; ++
i) {
1100 "Missing value for metadata operand");
1101 EnumerateFunctionLocalMetadata(
F, FnLocalMDVector[
i]);
1105 for (
const DIArgList *ArgList : ArgListMDVector)
1106 EnumerateFunctionLocalListMetadata(
F, ArgList);
1111 for (
unsigned i = NumModuleValues,
e = Values.size();
i !=
e; ++
i)
1113 for (
unsigned i = NumModuleMDs,
e = MDs.size();
i !=
e; ++
i)
1114 MetadataMap.
erase(MDs[
i]);
1118 Values.resize(NumModuleValues);
1119 MDs.resize(NumModuleMDs);
1120 BasicBlocks.clear();
1126 unsigned Counter = 0;
1128 IDMap[&
BB] = ++Counter;
1135 unsigned &Idx = GlobalBasicBlockIDs[
BB];