15 #include "llvm/Config/llvm-config.h"
53 unsigned LastGlobalConstantID = 0;
54 unsigned LastGlobalValueID = 0;
58 bool isGlobalConstant(
unsigned ID)
const {
59 return ID <= LastGlobalConstantID;
62 bool isGlobalValue(
unsigned ID)
const {
63 return ID <= LastGlobalValueID && !isGlobalConstant(
ID);
66 unsigned size()
const {
return IDs.
size(); }
67 std::pair<unsigned, bool> &operator[](
const Value *V) {
return IDs[V]; }
69 std::pair<unsigned, bool>
lookup(
const Value *V)
const {
75 unsigned ID = IDs.
size() + 1;
83 if (OM.lookup(V).first)
86 if (
const Constant *
C = dyn_cast<Constant>(V)) {
87 if (
C->getNumOperands() && !isa<GlobalValue>(
C)) {
88 for (
const Value *
Op :
C->operands())
89 if (!isa<BasicBlock>(
Op) && !isa<GlobalValue>(
Op))
91 if (
auto *CE = dyn_cast<ConstantExpr>(
C))
92 if (CE->getOpcode() == Instruction::ShuffleVector)
93 orderValue(CE->getShuffleMaskForBitcode(), OM);
113 if (
G.hasInitializer())
114 if (!isa<GlobalValue>(
G.getInitializer()))
117 if (!isa<GlobalValue>(A.getAliasee()))
120 if (!isa<GlobalValue>(
I.getResolver()))
123 for (
const Use &U :
F.operands())
124 if (!isa<GlobalValue>(U.get()))
133 auto orderConstantValue = [&OM](
const Value *V) {
134 if ((isa<Constant>(V) && !isa<GlobalValue>(V)) || isa<InlineAsm>(V))
138 if (
F.isDeclaration())
142 for (
const Value *V :
I.operands()) {
143 if (
const auto *MAV = dyn_cast<MetadataAsValue>(V)) {
144 if (
const auto *VAM =
145 dyn_cast<ValueAsMetadata>(MAV->getMetadata())) {
146 orderConstantValue(VAM->getValue());
147 }
else if (
const auto *
AL =
148 dyn_cast<DIArgList>(MAV->getMetadata())) {
149 for (
const auto *VAM :
AL->getArgs())
150 orderConstantValue(VAM->getValue());
155 OM.LastGlobalConstantID = OM.size();
173 OM.LastGlobalValueID = OM.size();
176 if (
F.isDeclaration())
187 for (
const Value *
Op :
I.operands())
188 if ((isa<Constant>(*
Op) && !isa<GlobalValue>(*
Op)) ||
191 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
192 orderValue(SVI->getShuffleMaskForBitcode(), OM);
205 using Entry = std::pair<const Use *, unsigned>;
209 if (OM.lookup(U.getUser()).first)
210 List.push_back(std::make_pair(&U,
List.size()));
216 bool IsGlobalValue = OM.isGlobalValue(
ID);
218 const Use *LU = L.first;
219 const Use *RU = R.first;
223 auto LID = OM.lookup(LU->getUser()).first;
224 auto RID = OM.lookup(RU->getUser()).first;
232 if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) {
234 return LU->getOperandNo() > RU->getOperandNo();
256 return LU->getOperandNo() < RU->getOperandNo();
257 return LU->getOperandNo() > RU->getOperandNo();
261 return L.second < R.second;
267 Stack.emplace_back(V,
F,
List.size());
268 assert(
List.size() == Stack.back().Shuffle.size() &&
"Wrong size");
269 for (
size_t I = 0,
E =
List.size();
I !=
E; ++
I)
270 Stack.back().Shuffle[
I] =
List[
I].second;
275 auto &IDPair = OM[V];
276 assert(IDPair.first &&
"Unmapped value");
282 IDPair.second =
true;
287 if (
const Constant *
C = dyn_cast<Constant>(V)) {
288 if (
C->getNumOperands()) {
289 for (
const Value *
Op :
C->operands())
290 if (isa<Constant>(
Op))
292 if (
auto *CE = dyn_cast<ConstantExpr>(
C))
293 if (CE->getOpcode() == Instruction::ShuffleVector)
314 if (
F.isDeclaration())
322 for (
const Value *
Op :
I.operands())
323 if (isa<Constant>(*
Op) || isa<InlineAsm>(*
Op))
325 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
345 if (
G.hasInitializer())
352 for (
const Use &U :
F.operands())
360 return V.first->getType()->isIntOrIntVectorTy();
364 bool ShouldPreserveUseListOrder)
365 : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
366 if (ShouldPreserveUseListOrder)
372 EnumerateType(GV.getValueType());
378 EnumerateType(
F.getValueType());
379 EnumerateAttributes(
F.getAttributes());
385 EnumerateType(GA.getValueType());
390 EnumerateValue(&GIF);
391 EnumerateType(GIF.getValueType());
395 unsigned FirstConstant = Values.size();
399 if (GV.hasInitializer())
400 EnumerateValue(GV.getInitializer());
401 if (GV.hasAttributes())
407 EnumerateValue(GA.getAliasee());
411 EnumerateValue(GIF.getResolver());
415 for (
const Use &U :
F.operands())
416 EnumerateValue(U.get());
426 EnumerateValueSymbolTable(
M.getValueSymbolTable());
427 EnumerateNamedMetadata(
M);
432 GV.getAllMetadata(MDs);
433 for (
const auto &
I : MDs)
437 EnumerateMetadata(
nullptr,
I.second);
443 EnumerateType(A.getType());
447 F.getAllMetadata(MDs);
448 for (
const auto &
I : MDs)
449 EnumerateMetadata(
F.isDeclaration() ?
nullptr : &
F,
I.second);
453 for (
const Use &
Op :
I.operands()) {
454 auto *MD = dyn_cast<MetadataAsValue>(&
Op);
456 EnumerateOperandType(
Op);
463 if (isa<LocalAsMetadata>(MD->getMetadata()))
465 if (
auto *
AL = dyn_cast<DIArgList>(MD->getMetadata())) {
466 for (
auto *VAM :
AL->getArgs())
467 if (isa<ConstantAsMetadata>(VAM))
468 EnumerateMetadata(&
F, VAM);
472 EnumerateMetadata(&
F, MD->getMetadata());
474 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
475 EnumerateType(SVI->getShuffleMaskForBitcode()->getType());
476 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I))
477 EnumerateType(
GEP->getSourceElementType());
478 if (
auto *AI = dyn_cast<AllocaInst>(&
I))
479 EnumerateType(AI->getAllocatedType());
480 EnumerateType(
I.getType());
481 if (
const auto *Call = dyn_cast<CallBase>(&
I)) {
482 EnumerateAttributes(Call->getAttributes());
483 EnumerateType(Call->getFunctionType());
488 I.getAllMetadataOtherThanDebugLoc(MDs);
489 for (
unsigned i = 0,
e = MDs.size();
i !=
e; ++
i)
490 EnumerateMetadata(&
F, MDs[
i].second);
496 EnumerateMetadata(&
F,
Op);
501 OptimizeConstants(FirstConstant, Values.size());
509 assert(
I != InstructionMap.
end() &&
"Instruction is not mapped!");
514 unsigned ComdatID = Comdats.
idFor(
C);
515 assert(ComdatID &&
"Comdat not found!");
520 InstructionMap[
I] = InstructionCount++;
524 if (
auto *MD = dyn_cast<MetadataAsValue>(V))
532 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
542 const char *
Name)
const {
543 OS <<
"Map Name: " <<
Name <<
"\n";
544 OS <<
"Size: " << Map.size() <<
"\n";
545 for (
const auto &
I : Map) {
548 OS <<
"Value: " << V->
getName();
550 OS <<
"Value: [null]\n";
555 for (
const Use &U : V->
uses()) {
559 OS <<
" " << U->getName();
569 const char *
Name)
const {
570 OS <<
"Map Name: " <<
Name <<
"\n";
571 OS <<
"Size: " << Map.size() <<
"\n";
572 for (
const auto &
I : Map) {
574 OS <<
"Metadata: slot = " <<
I.second.ID <<
"\n";
575 OS <<
"Metadata: function = " <<
I.second.F <<
"\n";
582 void ValueEnumerator::OptimizeConstants(
unsigned CstStart,
unsigned CstEnd) {
583 if (CstStart == CstEnd || CstStart+1 == CstEnd)
return;
585 if (ShouldPreserveUseListOrder)
591 [
this](
const std::pair<const Value *, unsigned> &
LHS,
592 const std::pair<const Value *, unsigned> &
RHS) {
594 if (LHS.first->getType() != RHS.first->getType())
595 return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
597 return LHS.second > RHS.second;
603 std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd,
607 for (; CstStart != CstEnd; ++CstStart)
608 ValueMap[Values[CstStart].first] = CstStart+1;
613 void ValueEnumerator::EnumerateValueSymbolTable(
const ValueSymbolTable &VST) {
616 EnumerateValue(
VI->getValue());
621 void ValueEnumerator::EnumerateNamedMetadata(
const Module &M) {
622 for (
const auto &
I :
M.named_metadata())
623 EnumerateNamedMDNode(&
I);
626 void ValueEnumerator::EnumerateNamedMDNode(
const NamedMDNode *MD) {
631 unsigned ValueEnumerator::getMetadataFunctionID(
const Function *
F)
const {
636 EnumerateMetadata(getMetadataFunctionID(
F), MD);
639 void ValueEnumerator::EnumerateFunctionLocalMetadata(
641 EnumerateFunctionLocalMetadata(getMetadataFunctionID(&
F), Local);
644 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
646 EnumerateFunctionLocalListMetadata(getMetadataFunctionID(&
F), ArgList);
649 void ValueEnumerator::dropFunctionFromMetadata(
650 MetadataMapType::value_type &FirstMD) {
653 auto &Entry = MD.second;
665 if (
auto *
N = dyn_cast<MDNode>(MD.first))
666 Worklist.push_back(
N);
669 while (!Worklist.empty())
673 auto MD = MetadataMap.
find(
Op);
674 if (MD != MetadataMap.
end())
679 void ValueEnumerator::EnumerateMetadata(
unsigned F,
const Metadata *MD) {
689 if (
const MDNode *
N = enumerateMetadataImpl(
F, MD))
690 Worklist.push_back(std::make_pair(
N,
N->op_begin()));
692 while (!Worklist.empty()) {
693 const MDNode *
N = Worklist.back().first;
698 Worklist.back().second,
N->op_end(),
699 [&](
const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
700 if (
I !=
N->op_end()) {
701 auto *
Op = cast<MDNode>(*
I);
702 Worklist.back().second = ++
I;
705 if (
Op->isDistinct() && !
N->isDistinct())
706 DelayedDistinctNodes.push_back(
Op);
708 Worklist.push_back(std::make_pair(
Op,
Op->op_begin()));
715 MetadataMap[
N].ID = MDs.size();
719 if (Worklist.empty() || Worklist.back().first->isDistinct()) {
720 for (
const MDNode *
N : DelayedDistinctNodes)
721 Worklist.push_back(std::make_pair(
N,
N->op_begin()));
722 DelayedDistinctNodes.
clear();
727 const MDNode *ValueEnumerator::enumerateMetadataImpl(
unsigned F,
const Metadata *MD) {
732 (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
733 "Invalid metadata kind");
735 auto Insertion = MetadataMap.
insert(std::make_pair(MD, MDIndex(
F)));
736 MDIndex &Entry = Insertion.first->second;
737 if (!Insertion.second) {
739 if (Entry.hasDifferentFunction(
F))
740 dropFunctionFromMetadata(*Insertion.first);
745 if (
auto *
N = dyn_cast<MDNode>(MD))
750 Entry.ID = MDs.size();
753 if (
auto *
C = dyn_cast<ConstantAsMetadata>(MD))
754 EnumerateValue(
C->getValue());
761 void ValueEnumerator::EnumerateFunctionLocalMetadata(
763 assert(
F &&
"Expected a function");
772 MDs.push_back(Local);
774 Index.ID = MDs.size();
776 EnumerateValue(
Local->getValue());
781 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
783 assert(
F &&
"Expected a function");
786 MDIndex &
Index = MetadataMap[ArgList];
793 if (isa<LocalAsMetadata>(VAM)) {
795 "LocalAsMetadata should be enumerated before DIArgList");
797 "Expected LocalAsMetadata in the same function");
799 assert(isa<ConstantAsMetadata>(VAM) &&
800 "Expected LocalAsMetadata or ConstantAsMetadata");
802 "Constant should be enumerated beforeDIArgList");
803 EnumerateMetadata(
F, VAM);
807 MDs.push_back(ArgList);
809 Index.ID = MDs.size();
814 if (isa<MDString>(MD))
819 auto *
N = dyn_cast<MDNode>(MD);
825 return N->isDistinct() ? 2 : 3;
828 void ValueEnumerator::organizeMetadata() {
830 "Metadata map and vector out of sync");
840 Order.push_back(MetadataMap.
lookup(MD));
855 std::vector<const Metadata *> OldMDs;
857 MDs.reserve(OldMDs.size());
858 for (
unsigned I = 0,
E = Order.size();
I !=
E && !Order[
I].F; ++
I) {
859 auto *MD = Order[
I].get(OldMDs);
861 MetadataMap[MD].ID =
I + 1;
862 if (isa<MDString>(MD))
867 if (MDs.size() == Order.size())
872 FunctionMDs.reserve(OldMDs.size());
874 for (
unsigned I = MDs.size(),
E = Order.size(),
ID = MDs.size();
I !=
E;
876 unsigned F = Order[
I].F;
879 }
else if (PrevF !=
F) {
880 R.Last = FunctionMDs.size();
882 R.First = FunctionMDs.size();
888 auto *MD = Order[
I].get(OldMDs);
889 FunctionMDs.push_back(MD);
890 MetadataMap[MD].ID = ++
ID;
891 if (isa<MDString>(MD))
894 R.Last = FunctionMDs.size();
895 FunctionMDInfo[PrevF] =
R;
898 void ValueEnumerator::incorporateFunctionMetadata(
const Function &
F) {
899 NumModuleMDs = MDs.size();
902 NumMDStrings =
R.NumStrings;
903 MDs.insert(MDs.end(), FunctionMDs.begin() +
R.First,
904 FunctionMDs.begin() +
R.Last);
907 void ValueEnumerator::EnumerateValue(
const Value *V) {
909 assert(!isa<MetadataAsValue>(V) &&
"EnumerateValue doesn't handle Metadata!");
915 Values[ValueID-1].second++;
919 if (
auto *GO = dyn_cast<GlobalObject>(V))
920 if (
const Comdat *
C = GO->getComdat())
926 if (
const Constant *
C = dyn_cast<Constant>(V)) {
927 if (isa<GlobalValue>(
C)) {
929 }
else if (
C->getNumOperands()) {
940 if (!isa<BasicBlock>(*
I))
942 if (
auto *CE = dyn_cast<ConstantExpr>(
C)) {
943 if (
CE->getOpcode() == Instruction::ShuffleVector)
944 EnumerateValue(
CE->getShuffleMaskForBitcode());
945 if (
auto *
GEP = dyn_cast<GEPOperator>(CE))
946 EnumerateType(
GEP->getSourceElementType());
951 Values.push_back(std::make_pair(V, 1U));
958 Values.push_back(std::make_pair(V, 1U));
959 ValueID = Values.size();
963 void ValueEnumerator::EnumerateType(
Type *Ty) {
964 unsigned *
TypeID = &TypeMap[Ty];
973 if (
StructType *STy = dyn_cast<StructType>(Ty))
974 if (!STy->isLiteral())
980 EnumerateType(SubTy);
1001 void ValueEnumerator::EnumerateOperandType(
const Value *V) {
1004 assert(!isa<MetadataAsValue>(V) &&
"Unexpected metadata operand");
1006 const Constant *
C = dyn_cast<Constant>(V);
1017 for (
const Value *
Op :
C->operands()) {
1020 if (isa<BasicBlock>(
Op))
1023 EnumerateOperandType(
Op);
1025 if (
auto *CE = dyn_cast<ConstantExpr>(
C)) {
1026 if (
CE->getOpcode() == Instruction::ShuffleVector)
1027 EnumerateOperandType(
CE->getShuffleMaskForBitcode());
1028 if (
CE->getOpcode() == Instruction::GetElementPtr)
1029 EnumerateType(cast<GEPOperator>(CE)->getSourceElementType());
1033 void ValueEnumerator::EnumerateAttributes(
AttributeList PAL) {
1037 unsigned &Entry = AttributeListMap[PAL];
1040 AttributeLists.push_back(PAL);
1041 Entry = AttributeLists.size();
1050 unsigned &Entry = AttributeGroupMap[Pair];
1052 AttributeGroups.push_back(Pair);
1053 Entry = AttributeGroups.size();
1056 if (Attr.isTypeAttribute())
1057 EnumerateType(Attr.getValueAsType());
1064 InstructionCount = 0;
1065 NumModuleValues = Values.size();
1069 incorporateFunctionMetadata(
F);
1072 for (
const auto &
I :
F.args()) {
1074 if (
I.hasAttribute(Attribute::ByVal))
1075 EnumerateType(
I.getParamByValType());
1076 else if (
I.hasAttribute(Attribute::StructRet))
1077 EnumerateType(
I.getParamStructRetType());
1078 else if (
I.hasAttribute(Attribute::ByRef))
1079 EnumerateType(
I.getParamByRefType());
1081 FirstFuncConstantID = Values.size();
1086 for (
const Use &OI :
I.operands()) {
1087 if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
1090 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
1091 EnumerateValue(SVI->getShuffleMaskForBitcode());
1093 BasicBlocks.push_back(&
BB);
1098 OptimizeConstants(FirstFuncConstantID, Values.size());
1102 EnumerateAttributes(
F.getAttributes());
1104 FirstInstID = Values.size();
1111 for (
const Use &OI :
I.operands()) {
1112 if (
auto *MD = dyn_cast<MetadataAsValue>(&OI)) {
1113 if (
auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) {
1115 FnLocalMDVector.push_back(Local);
1116 }
else if (
auto *ArgList = dyn_cast<DIArgList>(MD->getMetadata())) {
1117 ArgListMDVector.push_back(ArgList);
1119 if (
auto *Local = dyn_cast<LocalAsMetadata>(VMD)) {
1122 FnLocalMDVector.push_back(Local);
1129 if (!
I.getType()->isVoidTy())
1135 for (
unsigned i = 0,
e = FnLocalMDVector.size();
i !=
e; ++
i) {
1139 "Missing value for metadata operand");
1140 EnumerateFunctionLocalMetadata(
F, FnLocalMDVector[
i]);
1144 for (
const DIArgList *ArgList : ArgListMDVector)
1145 EnumerateFunctionLocalListMetadata(
F, ArgList);
1150 for (
unsigned i = NumModuleValues,
e = Values.size();
i !=
e; ++
i)
1152 for (
unsigned i = NumModuleMDs,
e = MDs.size();
i !=
e; ++
i)
1153 MetadataMap.
erase(MDs[
i]);
1157 Values.resize(NumModuleValues);
1158 MDs.resize(NumModuleMDs);
1159 BasicBlocks.clear();
1165 unsigned Counter = 0;
1167 IDMap[&
BB] = ++Counter;
1174 unsigned &Idx = GlobalBasicBlockIDs[
BB];