15 #include "llvm/Config/llvm-config.h"
53 unsigned LastGlobalValueID = 0;
57 bool isGlobalValue(
unsigned ID)
const {
58 return ID <= LastGlobalValueID;
61 unsigned size()
const {
return IDs.
size(); }
62 std::pair<unsigned, bool> &operator[](
const Value *V) {
return IDs[V]; }
64 std::pair<unsigned, bool>
lookup(
const Value *V)
const {
70 unsigned ID = IDs.
size() + 1;
78 if (OM.lookup(V).first)
81 if (
const Constant *
C = dyn_cast<Constant>(V)) {
82 if (
C->getNumOperands()) {
83 for (
const Value *
Op :
C->operands())
84 if (!isa<BasicBlock>(
Op) && !isa<GlobalValue>(
Op))
86 if (
auto *CE = dyn_cast<ConstantExpr>(
C))
87 if (CE->getOpcode() == Instruction::ShuffleVector)
88 orderValue(CE->getShuffleMaskForBitcode(), OM);
118 OM.LastGlobalValueID = OM.size();
120 auto orderConstantValue = [&OM](
const Value *V) {
121 if (isa<Constant>(V) || isa<InlineAsm>(V))
126 if (
F.isDeclaration())
138 for (
const Value *V :
I.operands()) {
139 if (
const auto *MAV = dyn_cast<MetadataAsValue>(V)) {
140 if (
const auto *VAM =
141 dyn_cast<ValueAsMetadata>(MAV->getMetadata())) {
142 orderConstantValue(VAM->getValue());
143 }
else if (
const auto *
AL =
144 dyn_cast<DIArgList>(MAV->getMetadata())) {
145 for (
const auto *VAM :
AL->getArgs())
146 orderConstantValue(VAM->getValue());
155 for (
const Value *
Op :
I.operands())
156 orderConstantValue(
Op);
157 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
158 orderValue(SVI->getShuffleMaskForBitcode(), OM);
169 using Entry = std::pair<const Use *, unsigned>;
173 if (OM.lookup(U.getUser()).first)
174 List.push_back(std::make_pair(&U,
List.size()));
180 bool IsGlobalValue = OM.isGlobalValue(
ID);
182 const Use *LU = L.first;
183 const Use *RU = R.first;
187 auto LID = OM.lookup(LU->getUser()).first;
188 auto RID = OM.lookup(RU->getUser()).first;
208 return LU->getOperandNo() < RU->getOperandNo();
209 return LU->getOperandNo() > RU->getOperandNo();
217 Stack.emplace_back(V,
F,
List.size());
218 assert(
List.size() == Stack.back().Shuffle.size() &&
"Wrong size");
219 for (
size_t I = 0,
E =
List.size();
I !=
E; ++
I)
220 Stack.back().Shuffle[
I] =
List[
I].second;
225 auto &IDPair = OM[V];
226 assert(IDPair.first &&
"Unmapped value");
232 IDPair.second =
true;
237 if (
const Constant *
C = dyn_cast<Constant>(V)) {
238 if (
C->getNumOperands()) {
239 for (
const Value *
Op :
C->operands())
240 if (isa<Constant>(
Op))
242 if (
auto *CE = dyn_cast<ConstantExpr>(
C))
243 if (CE->getOpcode() == Instruction::ShuffleVector)
264 if (
F.isDeclaration())
272 for (
const Value *
Op :
I.operands()) {
273 if (isa<Constant>(*
Op) || isa<InlineAsm>(*
Op))
275 if (
const auto *MAV = dyn_cast<MetadataAsValue>(
Op)) {
276 if (
const auto *VAM =
277 dyn_cast<ValueAsMetadata>(MAV->getMetadata())) {
279 }
else if (
const auto *
AL =
280 dyn_cast<DIArgList>(MAV->getMetadata())) {
281 for (
const auto *VAM :
AL->getArgs())
286 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
304 if (
G.hasInitializer())
311 for (
const Use &U :
F.operands())
319 return V.first->getType()->isIntOrIntVectorTy();
323 bool ShouldPreserveUseListOrder)
324 : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
325 if (ShouldPreserveUseListOrder)
331 EnumerateType(GV.getValueType());
337 EnumerateType(
F.getValueType());
338 EnumerateAttributes(
F.getAttributes());
344 EnumerateType(GA.getValueType());
349 EnumerateValue(&GIF);
350 EnumerateType(GIF.getValueType());
354 unsigned FirstConstant = Values.size();
358 if (GV.hasInitializer())
359 EnumerateValue(GV.getInitializer());
360 if (GV.hasAttributes())
366 EnumerateValue(GA.getAliasee());
370 EnumerateValue(GIF.getResolver());
374 for (
const Use &U :
F.operands())
375 EnumerateValue(U.get());
385 EnumerateValueSymbolTable(
M.getValueSymbolTable());
386 EnumerateNamedMetadata(
M);
391 GV.getAllMetadata(MDs);
392 for (
const auto &
I : MDs)
396 EnumerateMetadata(
nullptr,
I.second);
402 EnumerateType(A.getType());
406 F.getAllMetadata(MDs);
407 for (
const auto &
I : MDs)
408 EnumerateMetadata(
F.isDeclaration() ?
nullptr : &
F,
I.second);
412 for (
const Use &
Op :
I.operands()) {
413 auto *MD = dyn_cast<MetadataAsValue>(&
Op);
415 EnumerateOperandType(
Op);
422 if (isa<LocalAsMetadata>(MD->getMetadata()))
424 if (
auto *
AL = dyn_cast<DIArgList>(MD->getMetadata())) {
425 for (
auto *VAM :
AL->getArgs())
426 if (isa<ConstantAsMetadata>(VAM))
427 EnumerateMetadata(&
F, VAM);
431 EnumerateMetadata(&
F, MD->getMetadata());
433 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
434 EnumerateType(SVI->getShuffleMaskForBitcode()->getType());
435 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I))
436 EnumerateType(
GEP->getSourceElementType());
437 if (
auto *AI = dyn_cast<AllocaInst>(&
I))
438 EnumerateType(AI->getAllocatedType());
439 EnumerateType(
I.getType());
440 if (
const auto *Call = dyn_cast<CallBase>(&
I)) {
441 EnumerateAttributes(Call->getAttributes());
442 EnumerateType(Call->getFunctionType());
447 I.getAllMetadataOtherThanDebugLoc(MDs);
448 for (
unsigned i = 0,
e = MDs.size();
i !=
e; ++
i)
449 EnumerateMetadata(&
F, MDs[
i].second);
455 EnumerateMetadata(&
F,
Op);
460 OptimizeConstants(FirstConstant, Values.size());
468 assert(
I != InstructionMap.
end() &&
"Instruction is not mapped!");
473 unsigned ComdatID = Comdats.
idFor(
C);
474 assert(ComdatID &&
"Comdat not found!");
479 InstructionMap[
I] = InstructionCount++;
483 if (
auto *MD = dyn_cast<MetadataAsValue>(V))
491 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
501 const char *
Name)
const {
502 OS <<
"Map Name: " <<
Name <<
"\n";
503 OS <<
"Size: " << Map.size() <<
"\n";
504 for (
const auto &
I : Map) {
507 OS <<
"Value: " << V->
getName();
509 OS <<
"Value: [null]\n";
514 for (
const Use &U : V->
uses()) {
518 OS <<
" " << U->getName();
528 const char *
Name)
const {
529 OS <<
"Map Name: " <<
Name <<
"\n";
530 OS <<
"Size: " << Map.size() <<
"\n";
531 for (
const auto &
I : Map) {
533 OS <<
"Metadata: slot = " <<
I.second.ID <<
"\n";
534 OS <<
"Metadata: function = " <<
I.second.F <<
"\n";
541 void ValueEnumerator::OptimizeConstants(
unsigned CstStart,
unsigned CstEnd) {
542 if (CstStart == CstEnd || CstStart+1 == CstEnd)
return;
544 if (ShouldPreserveUseListOrder)
550 [
this](
const std::pair<const Value *, unsigned> &
LHS,
551 const std::pair<const Value *, unsigned> &
RHS) {
553 if (LHS.first->getType() != RHS.first->getType())
554 return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
556 return LHS.second > RHS.second;
562 std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd,
566 for (; CstStart != CstEnd; ++CstStart)
567 ValueMap[Values[CstStart].first] = CstStart+1;
572 void ValueEnumerator::EnumerateValueSymbolTable(
const ValueSymbolTable &VST) {
575 EnumerateValue(
VI->getValue());
580 void ValueEnumerator::EnumerateNamedMetadata(
const Module &M) {
581 for (
const auto &
I :
M.named_metadata())
582 EnumerateNamedMDNode(&
I);
585 void ValueEnumerator::EnumerateNamedMDNode(
const NamedMDNode *MD) {
590 unsigned ValueEnumerator::getMetadataFunctionID(
const Function *
F)
const {
595 EnumerateMetadata(getMetadataFunctionID(
F), MD);
598 void ValueEnumerator::EnumerateFunctionLocalMetadata(
600 EnumerateFunctionLocalMetadata(getMetadataFunctionID(&
F), Local);
603 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
605 EnumerateFunctionLocalListMetadata(getMetadataFunctionID(&
F), ArgList);
608 void ValueEnumerator::dropFunctionFromMetadata(
609 MetadataMapType::value_type &FirstMD) {
612 auto &Entry = MD.second;
624 if (
auto *
N = dyn_cast<MDNode>(MD.first))
625 Worklist.push_back(
N);
628 while (!Worklist.empty())
632 auto MD = MetadataMap.
find(
Op);
633 if (MD != MetadataMap.
end())
638 void ValueEnumerator::EnumerateMetadata(
unsigned F,
const Metadata *MD) {
648 if (
const MDNode *
N = enumerateMetadataImpl(
F, MD))
649 Worklist.push_back(std::make_pair(
N,
N->op_begin()));
651 while (!Worklist.empty()) {
652 const MDNode *
N = Worklist.back().first;
657 Worklist.back().second,
N->op_end(),
658 [&](
const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
659 if (
I !=
N->op_end()) {
660 auto *
Op = cast<MDNode>(*
I);
661 Worklist.back().second = ++
I;
664 if (
Op->isDistinct() && !
N->isDistinct())
665 DelayedDistinctNodes.push_back(
Op);
667 Worklist.push_back(std::make_pair(
Op,
Op->op_begin()));
674 MetadataMap[
N].ID = MDs.size();
678 if (Worklist.empty() || Worklist.back().first->isDistinct()) {
679 for (
const MDNode *
N : DelayedDistinctNodes)
680 Worklist.push_back(std::make_pair(
N,
N->op_begin()));
681 DelayedDistinctNodes.
clear();
686 const MDNode *ValueEnumerator::enumerateMetadataImpl(
unsigned F,
const Metadata *MD) {
691 (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
692 "Invalid metadata kind");
694 auto Insertion = MetadataMap.
insert(std::make_pair(MD, MDIndex(
F)));
695 MDIndex &Entry = Insertion.first->second;
696 if (!Insertion.second) {
698 if (Entry.hasDifferentFunction(
F))
699 dropFunctionFromMetadata(*Insertion.first);
704 if (
auto *
N = dyn_cast<MDNode>(MD))
709 Entry.ID = MDs.size();
712 if (
auto *
C = dyn_cast<ConstantAsMetadata>(MD))
713 EnumerateValue(
C->getValue());
720 void ValueEnumerator::EnumerateFunctionLocalMetadata(
722 assert(
F &&
"Expected a function");
731 MDs.push_back(Local);
733 Index.ID = MDs.size();
735 EnumerateValue(
Local->getValue());
740 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
742 assert(
F &&
"Expected a function");
745 MDIndex &
Index = MetadataMap[ArgList];
752 if (isa<LocalAsMetadata>(VAM)) {
754 "LocalAsMetadata should be enumerated before DIArgList");
756 "Expected LocalAsMetadata in the same function");
758 assert(isa<ConstantAsMetadata>(VAM) &&
759 "Expected LocalAsMetadata or ConstantAsMetadata");
761 "Constant should be enumerated beforeDIArgList");
762 EnumerateMetadata(
F, VAM);
766 MDs.push_back(ArgList);
768 Index.ID = MDs.size();
773 if (isa<MDString>(MD))
778 auto *
N = dyn_cast<MDNode>(MD);
784 return N->isDistinct() ? 2 : 3;
787 void ValueEnumerator::organizeMetadata() {
789 "Metadata map and vector out of sync");
799 Order.push_back(MetadataMap.
lookup(MD));
814 std::vector<const Metadata *> OldMDs;
816 MDs.reserve(OldMDs.size());
817 for (
unsigned I = 0,
E = Order.size();
I !=
E && !Order[
I].F; ++
I) {
818 auto *MD = Order[
I].get(OldMDs);
820 MetadataMap[MD].ID =
I + 1;
821 if (isa<MDString>(MD))
826 if (MDs.size() == Order.size())
831 FunctionMDs.reserve(OldMDs.size());
833 for (
unsigned I = MDs.size(),
E = Order.size(),
ID = MDs.size();
I !=
E;
835 unsigned F = Order[
I].F;
838 }
else if (PrevF !=
F) {
839 R.Last = FunctionMDs.size();
841 R.First = FunctionMDs.size();
847 auto *MD = Order[
I].get(OldMDs);
848 FunctionMDs.push_back(MD);
849 MetadataMap[MD].ID = ++
ID;
850 if (isa<MDString>(MD))
853 R.Last = FunctionMDs.size();
854 FunctionMDInfo[PrevF] =
R;
857 void ValueEnumerator::incorporateFunctionMetadata(
const Function &
F) {
858 NumModuleMDs = MDs.size();
861 NumMDStrings =
R.NumStrings;
862 MDs.insert(MDs.end(), FunctionMDs.begin() +
R.First,
863 FunctionMDs.begin() +
R.Last);
866 void ValueEnumerator::EnumerateValue(
const Value *V) {
868 assert(!isa<MetadataAsValue>(V) &&
"EnumerateValue doesn't handle Metadata!");
874 Values[ValueID-1].second++;
878 if (
auto *GO = dyn_cast<GlobalObject>(V))
879 if (
const Comdat *
C = GO->getComdat())
885 if (
const Constant *
C = dyn_cast<Constant>(V)) {
886 if (isa<GlobalValue>(
C)) {
888 }
else if (
C->getNumOperands()) {
899 if (!isa<BasicBlock>(*
I))
901 if (
auto *CE = dyn_cast<ConstantExpr>(
C)) {
902 if (
CE->getOpcode() == Instruction::ShuffleVector)
903 EnumerateValue(
CE->getShuffleMaskForBitcode());
904 if (
auto *
GEP = dyn_cast<GEPOperator>(CE))
905 EnumerateType(
GEP->getSourceElementType());
910 Values.push_back(std::make_pair(V, 1U));
917 Values.push_back(std::make_pair(V, 1U));
918 ValueID = Values.size();
922 void ValueEnumerator::EnumerateType(
Type *Ty) {
923 unsigned *
TypeID = &TypeMap[Ty];
932 if (
StructType *STy = dyn_cast<StructType>(Ty))
933 if (!STy->isLiteral())
939 EnumerateType(SubTy);
960 void ValueEnumerator::EnumerateOperandType(
const Value *V) {
963 assert(!isa<MetadataAsValue>(V) &&
"Unexpected metadata operand");
965 const Constant *
C = dyn_cast<Constant>(V);
976 for (
const Value *
Op :
C->operands()) {
979 if (isa<BasicBlock>(
Op))
982 EnumerateOperandType(
Op);
984 if (
auto *CE = dyn_cast<ConstantExpr>(
C)) {
985 if (
CE->getOpcode() == Instruction::ShuffleVector)
986 EnumerateOperandType(
CE->getShuffleMaskForBitcode());
987 if (
CE->getOpcode() == Instruction::GetElementPtr)
988 EnumerateType(cast<GEPOperator>(CE)->getSourceElementType());
992 void ValueEnumerator::EnumerateAttributes(
AttributeList PAL) {
996 unsigned &Entry = AttributeListMap[PAL];
999 AttributeLists.push_back(PAL);
1000 Entry = AttributeLists.size();
1009 unsigned &Entry = AttributeGroupMap[Pair];
1011 AttributeGroups.push_back(Pair);
1012 Entry = AttributeGroups.size();
1015 if (Attr.isTypeAttribute())
1016 EnumerateType(Attr.getValueAsType());
1023 InstructionCount = 0;
1024 NumModuleValues = Values.size();
1028 incorporateFunctionMetadata(
F);
1031 for (
const auto &
I :
F.args()) {
1033 if (
I.hasAttribute(Attribute::ByVal))
1034 EnumerateType(
I.getParamByValType());
1035 else if (
I.hasAttribute(Attribute::StructRet))
1036 EnumerateType(
I.getParamStructRetType());
1037 else if (
I.hasAttribute(Attribute::ByRef))
1038 EnumerateType(
I.getParamByRefType());
1040 FirstFuncConstantID = Values.size();
1045 for (
const Use &OI :
I.operands()) {
1046 if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
1049 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
1050 EnumerateValue(SVI->getShuffleMaskForBitcode());
1052 BasicBlocks.push_back(&
BB);
1057 OptimizeConstants(FirstFuncConstantID, Values.size());
1061 EnumerateAttributes(
F.getAttributes());
1063 FirstInstID = Values.size();
1070 for (
const Use &OI :
I.operands()) {
1071 if (
auto *MD = dyn_cast<MetadataAsValue>(&OI)) {
1072 if (
auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) {
1074 FnLocalMDVector.push_back(Local);
1075 }
else if (
auto *ArgList = dyn_cast<DIArgList>(MD->getMetadata())) {
1076 ArgListMDVector.push_back(ArgList);
1078 if (
auto *Local = dyn_cast<LocalAsMetadata>(VMD)) {
1081 FnLocalMDVector.push_back(Local);
1088 if (!
I.getType()->isVoidTy())
1094 for (
unsigned i = 0,
e = FnLocalMDVector.size();
i !=
e; ++
i) {
1098 "Missing value for metadata operand");
1099 EnumerateFunctionLocalMetadata(
F, FnLocalMDVector[
i]);
1103 for (
const DIArgList *ArgList : ArgListMDVector)
1104 EnumerateFunctionLocalListMetadata(
F, ArgList);
1109 for (
unsigned i = NumModuleValues,
e = Values.size();
i !=
e; ++
i)
1111 for (
unsigned i = NumModuleMDs,
e = MDs.size();
i !=
e; ++
i)
1112 MetadataMap.
erase(MDs[
i]);
1116 Values.resize(NumModuleValues);
1117 MDs.resize(NumModuleMDs);
1118 BasicBlocks.clear();
1124 unsigned Counter = 0;
1126 IDMap[&
BB] = ++Counter;
1133 unsigned &Idx = GlobalBasicBlockIDs[
BB];