47 #define DEBUG_TYPE "value-mapper"
50 void ValueMapTypeRemapper::anchor() {}
51 void ValueMaterializer::anchor() {}
57 struct DelayedBasicBlock {
59 std::unique_ptr<BasicBlock> TempBB;
62 : OldBB(Old.getBasicBlock()),
63 TempBB(
BasicBlock::Create(Old.getContext())) {}
66 struct WorklistEntry {
77 struct AppendingGVTy {
81 struct AliasOrIFuncTy {
88 unsigned AppendingGVIsOldCtorDtor : 1;
89 unsigned AppendingGVNumNewMembers;
92 AppendingGVTy AppendingGV;
93 AliasOrIFuncTy AliasOrIFunc;
98 struct MappingContext {
105 : VM(&VM), Materializer(Materializer) {}
109 friend class MDNodeMapper;
117 unsigned CurrentMCID = 0;
127 MCs(1, MappingContext(VM, Materializer)) {}
130 ~Mapper() {
assert(!hasWorkToDo() &&
"Expected to be flushed"); }
132 bool hasWorkToDo()
const {
return !Worklist.empty(); }
137 MCs.push_back(MappingContext(VM, Materializer));
138 return MCs.size() - 1;
150 return cast_or_null<Constant>(mapValue(
C));
167 void scheduleRemapFunction(
Function &
F,
unsigned MCID);
182 std::optional<Metadata *> mapSimpleMetadata(
const Metadata *MD);
193 bool HasChanged =
false;
195 TempMDNode Placeholder;
199 struct UniquedGraph {
207 void propagateChanges();
221 MDNodeMapper(Mapper &M) :
M(
M) {}
274 std::optional<Metadata *> tryToMapOperand(
const Metadata *
Op);
302 bool createPOT(UniquedGraph &
G,
const MDNode &FirstN);
323 void mapNodesInPOT(UniquedGraph &
G);
331 template <
class OperandMapper>
332 void remapOperands(
MDNode &
N, OperandMapper mapOperand);
341 if (
I != getVM().
end()) {
342 assert(
I->second &&
"Unexpected null mapping");
347 if (
auto *Materializer = getMaterializer()) {
348 if (
Value *NewV = Materializer->materialize(
const_cast<Value *
>(V))) {
356 if (isa<GlobalValue>(V)) {
359 return getVM()[V] =
const_cast<Value *
>(V);
362 if (
const InlineAsm *
IA = dyn_cast<InlineAsm>(V)) {
366 NewTy = cast<FunctionType>(TypeMapper->
remapType(NewTy));
368 if (NewTy !=
IA->getFunctionType())
370 IA->hasSideEffects(),
IA->isAlignStack(),
371 IA->getDialect(),
IA->canThrow());
374 return getVM()[V] =
const_cast<Value *
>(V);
377 if (
const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
378 const Metadata *MD = MDV->getMetadata();
380 if (
auto *
LAM = dyn_cast<LocalAsMetadata>(MD)) {
382 if (
Value *LV = mapValue(
LAM->getValue())) {
383 if (V ==
LAM->getValue())
384 return const_cast<Value *
>(V);
396 if (
auto *
AL = dyn_cast<DIArgList>(MD)) {
398 for (
auto *VAM :
AL->getArgs()) {
405 MappedArgs.push_back(VAM);
406 }
else if (
Value *LV = mapValue(VAM->getValue())) {
407 MappedArgs.push_back(
410 MappedArgs.push_back(VAM);
424 return getVM()[V] =
const_cast<Value *
>(V);
427 auto *MappedMD = mapMetadata(MD);
429 return getVM()[V] =
const_cast<Value *
>(V);
440 return mapBlockAddress(*BA);
442 if (
const auto *
E = dyn_cast<DSOLocalEquivalent>(
C)) {
443 auto *Val = mapValue(
E->getGlobalValue());
448 auto *
Func = cast<Function>(Val->stripPointerCastsAndAliases());
449 Type *NewTy =
E->getType();
456 if (
const auto *
NC = dyn_cast<NoCFIValue>(
C)) {
457 auto *Val = mapValue(
NC->getGlobalValue());
462 auto mapValueOrNull = [
this](
Value *V) {
463 auto Mapped = mapValue(V);
465 "Unexpected null mapping for constant operand without "
466 "NullMapMissingGlobalValues flag");
472 unsigned OpNo = 0, NumOperands =
C->getNumOperands();
473 Value *Mapped =
nullptr;
474 for (; OpNo != NumOperands; ++OpNo) {
476 Mapped = mapValueOrNull(
Op);
484 Type *NewTy =
C->getType();
490 if (OpNo == NumOperands && NewTy ==
C->getType())
491 return getVM()[V] =
C;
497 for (
unsigned j = 0;
j != OpNo; ++
j)
498 Ops.push_back(cast<Constant>(
C->getOperand(
j)));
501 if (OpNo != NumOperands) {
502 Ops.push_back(cast<Constant>(Mapped));
505 for (++OpNo; OpNo != NumOperands; ++OpNo) {
506 Mapped = mapValueOrNull(
C->getOperand(OpNo));
509 Ops.push_back(cast<Constant>(Mapped));
512 Type *NewSrcTy =
nullptr;
514 if (
auto *GEPO = dyn_cast<GEPOperator>(
C))
515 NewSrcTy = TypeMapper->
remapType(GEPO->getSourceElementType());
518 return getVM()[V] =
CE->getWithOperands(Ops, NewTy,
false, NewSrcTy);
519 if (isa<ConstantArray>(
C))
521 if (isa<ConstantStruct>(
C))
523 if (isa<ConstantVector>(
C))
526 if (isa<UndefValue>(
C))
528 if (isa<ConstantAggregateZero>(
C))
530 assert(isa<ConstantPointerNull>(
C));
542 DelayedBBs.push_back(DelayedBasicBlock(BA));
543 BB = DelayedBBs.back().TempBB.get();
552 getVM().MD()[
Key].reset(Val);
557 return mapToMetadata(MD,
const_cast<Metadata *
>(MD));
560 std::optional<Metadata *> MDNodeMapper::tryToMapOperand(
const Metadata *
Op) {
564 if (std::optional<Metadata *> MappedOp =
M.mapSimpleMetadata(
Op)) {
566 if (
auto *CMD = dyn_cast<ConstantAsMetadata>(
Op))
567 assert((!*MappedOp ||
M.getVM().count(CMD->getValue()) ||
568 M.getVM().getMappedMD(
Op)) &&
569 "Expected Value to be memoized");
571 assert((isa<MDString>(
Op) ||
M.getVM().getMappedMD(
Op)) &&
572 "Expected result to be memoized");
579 return mapDistinctNode(
N);
584 assert(
N.isDistinct() &&
"Expected a distinct node");
585 assert(!
M.getVM().getMappedMD(&
N) &&
"Expected an unmapped node");
589 NewM =
M.mapToSelf(&
N);
593 <<
"To " << *NewM <<
"\n\n");
594 M.mapToMetadata(&
N, NewM);
596 DistinctWorklist.push_back(cast<MDNode>(NewM));
598 return DistinctWorklist.back();
612 if (std::optional<Metadata *> MappedOp =
M.getVM().getMappedMD(
Op))
615 if (isa<MDString>(
Op))
618 if (
auto *CMD = dyn_cast<ConstantAsMetadata>(
Op))
625 auto Where =
Info.find(&
Op);
626 assert(Where !=
Info.end() &&
"Expected a valid reference");
628 auto &OpD = Where->second;
633 if (!OpD.Placeholder)
634 OpD.Placeholder =
Op.clone();
636 return *OpD.Placeholder;
639 template <
class OperandMapper>
640 void MDNodeMapper::remapOperands(
MDNode &
N, OperandMapper mapOperand) {
641 assert(!
N.isUniqued() &&
"Expected distinct or temporary nodes");
642 for (
unsigned I = 0,
E =
N.getNumOperands();
I !=
E; ++
I) {
646 LLVM_DEBUG(
dbgs() <<
"Replacing Op " << Old <<
" with " << New <<
" in "
650 N.replaceOperandWith(
I, New);
657 struct POTWorklistEntry {
663 bool HasChanged =
false;
665 POTWorklistEntry(
MDNode &
N) :
N(&
N),
Op(
N.op_begin()) {}
670 bool MDNodeMapper::createPOT(UniquedGraph &
G,
const MDNode &FirstN) {
671 assert(
G.Info.empty() &&
"Expected a fresh traversal");
675 bool AnyChanges =
false;
677 Worklist.push_back(POTWorklistEntry(
const_cast<MDNode &
>(FirstN)));
678 (void)
G.Info[&FirstN];
679 while (!Worklist.empty()) {
681 auto &WE = Worklist.back();
682 if (
MDNode *
N = visitOperands(
G, WE.Op, WE.N->op_end(), WE.HasChanged)) {
684 Worklist.push_back(POTWorklistEntry(*
N));
689 assert(WE.N->isUniqued() &&
"Expected only uniqued nodes");
690 assert(WE.Op == WE.N->op_end() &&
"Expected to visit all operands");
691 auto &
D =
G.Info[WE.N];
692 AnyChanges |=
D.HasChanged = WE.HasChanged;
694 G.POT.push_back(WE.N);
706 if (std::optional<Metadata *> MappedOp = tryToMapOperand(
Op)) {
708 HasChanged |=
Op != *MappedOp;
715 "Only uniqued operands cannot be mapped immediately");
716 if (
G.Info.insert(std::make_pair(&OpN,
Data())).second)
722 void MDNodeMapper::UniquedGraph::propagateChanges() {
732 auto Where = Info.find(Op);
733 return Where != Info.end() && Where->second.HasChanged;
737 AnyChanges =
D.HasChanged =
true;
739 }
while (AnyChanges);
742 void MDNodeMapper::mapNodesInPOT(UniquedGraph &
G) {
745 for (
auto *
N :
G.POT) {
754 bool HadPlaceholder(
D.Placeholder);
757 TempMDNode ClonedN =
D.Placeholder ?
std::move(
D.Placeholder) :
N->clone();
758 remapOperands(*ClonedN, [
this, &
D, &
G](
Metadata *Old) {
759 if (std::optional<Metadata *> MappedOp =
getMappedOp(Old))
762 assert(
G.Info[Old].ID >
D.ID &&
"Expected a forward reference");
763 return &
G.getFwdReference(*cast<MDNode>(Old));
767 if (
N && NewN &&
N != NewN) {
769 <<
"To " << *NewN <<
"\n\n");
772 M.mapToMetadata(
N, NewN);
777 CyclicNodes.push_back(NewN);
781 for (
auto *
N : CyclicNodes)
782 if (!
N->isResolved())
787 assert(DistinctWorklist.empty() &&
"MDNodeMapper::map is not recursive");
789 "MDNodeMapper::map assumes module-level changes");
792 assert(
N.isResolved() &&
"Unexpected unresolved node");
795 N.isUniqued() ? mapTopLevelUniquedNode(
N) : mapDistinctNode(
N);
796 while (!DistinctWorklist.empty())
797 remapOperands(*DistinctWorklist.pop_back_val(), [
this](
Metadata *Old) {
798 if (std::optional<Metadata *> MappedOp = tryToMapOperand(Old))
800 return mapTopLevelUniquedNode(*cast<MDNode>(Old));
805 Metadata *MDNodeMapper::mapTopLevelUniquedNode(
const MDNode &FirstN) {
810 if (!createPOT(
G, FirstN)) {
814 return &
const_cast<MDNode &
>(FirstN);
818 G.propagateChanges();
827 std::optional<Metadata *> Mapper::mapSimpleMetadata(
const Metadata *MD) {
829 if (std::optional<Metadata *> NewMD = getVM().getMappedMD(MD))
832 if (isa<MDString>(MD))
840 if (
auto *CMD = dyn_cast<ConstantAsMetadata>(MD)) {
848 assert(isa<MDNode>(MD) &&
"Expected a metadata node");
854 assert(MD &&
"Expected valid metadata");
855 assert(!isa<LocalAsMetadata>(MD) &&
"Unexpected local metadata");
857 if (std::optional<Metadata *> NewMD = mapSimpleMetadata(MD))
860 return MDNodeMapper(*this).map(*cast<MDNode>(MD));
863 void Mapper::flush() {
865 while (!Worklist.empty()) {
867 CurrentMCID =
E.MCID;
869 case WorklistEntry::MapGlobalInit:
870 E.Data.GVInit.GV->setInitializer(mapConstant(
E.Data.GVInit.Init));
871 remapGlobalObjectMetadata(*
E.Data.GVInit.GV);
873 case WorklistEntry::MapAppendingVar: {
874 unsigned PrefixSize = AppendingInits.size() -
E.AppendingGVNumNewMembers;
880 AppendingInits.
resize(PrefixSize);
881 mapAppendingVariable(*
E.Data.AppendingGV.GV,
882 E.Data.AppendingGV.InitPrefix,
883 E.AppendingGVIsOldCtorDtor,
ArrayRef(NewInits));
886 case WorklistEntry::MapAliasOrIFunc: {
889 if (
auto *GA = dyn_cast<GlobalAlias>(GV))
891 else if (
auto *GI = dyn_cast<GlobalIFunc>(GV))
898 remapFunction(*
E.Data.RemapF);
906 while (!DelayedBBs.empty()) {
908 BasicBlock *
BB = cast_or_null<BasicBlock>(mapValue(DBB.OldBB));
909 DBB.TempBB->replaceAllUsesWith(
BB ?
BB : DBB.OldBB);
915 for (
Use &
Op :
I->operands()) {
922 "Referenced value not in value map!");
926 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
927 for (
unsigned i = 0,
e = PN->getNumIncomingValues();
i !=
e; ++
i) {
928 Value *V = mapValue(PN->getIncomingBlock(
i));
931 PN->setIncomingBlock(
i, cast<BasicBlock>(V));
934 "Referenced block not in value map!");
940 I->getAllMetadata(MDs);
941 for (
const auto &
MI : MDs) {
943 MDNode *
New = cast_or_null<MDNode>(mapMetadata(Old));
945 I->setMetadata(
MI.first, New);
952 if (
auto *CB = dyn_cast<CallBase>(
I)) {
957 Tys.push_back(TypeMapper->
remapType(Ty));
963 for (
unsigned i = 0;
i <
Attrs.getNumAttrSets(); ++
i) {
964 for (
int AttrIdx = Attribute::FirstTypeAttr;
965 AttrIdx <= Attribute::LastTypeAttr; AttrIdx++) {
969 Attrs =
Attrs.replaceAttributeTypeAtIndex(
C,
i, TypedAttr,
978 if (
auto *AI = dyn_cast<AllocaInst>(
I))
979 AI->setAllocatedType(TypeMapper->
remapType(AI->getAllocatedType()));
980 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I)) {
981 GEP->setSourceElementType(
983 GEP->setResultElementType(
986 I->mutateType(TypeMapper->
remapType(
I->getType()));
989 void Mapper::remapGlobalObjectMetadata(
GlobalObject &GO) {
993 for (
const auto &
I : MDs)
994 GO.
addMetadata(
I.first, *cast<MDNode>(mapMetadata(
I.second)));
997 void Mapper::remapFunction(
Function &
F) {
999 for (
Use &
Op :
F.operands())
1004 remapGlobalObjectMetadata(
F);
1014 remapInstruction(&
I);
1022 unsigned NumElements =
1023 cast<ArrayType>(InitPrefix->
getType())->getNumElements();
1024 for (
unsigned I = 0;
I != NumElements; ++
I)
1030 if (IsOldCtorDtor) {
1035 Type *Tys[3] = {
ST.getElementType(0),
ST.getElementType(1), VoidPtrTy};
1039 for (
auto *V : NewMembers) {
1041 if (IsOldCtorDtor) {
1042 auto *
S = cast<ConstantStruct>(V);
1043 auto *E1 = cast<Constant>(mapValue(
S->getOperand(0)));
1044 auto *E2 = cast<Constant>(mapValue(
S->getOperand(1)));
1048 NewV = cast_or_null<Constant>(mapValue(V));
1059 assert(AlreadyScheduled.
insert(&GV).second &&
"Should not reschedule");
1060 assert(MCID < MCs.size() &&
"Invalid mapping context");
1063 WE.Kind = WorklistEntry::MapGlobalInit;
1065 WE.Data.GVInit.GV = &GV;
1066 WE.Data.GVInit.Init = &
Init;
1067 Worklist.push_back(WE);
1075 assert(AlreadyScheduled.
insert(&GV).second &&
"Should not reschedule");
1076 assert(MCID < MCs.size() &&
"Invalid mapping context");
1079 WE.Kind = WorklistEntry::MapAppendingVar;
1081 WE.Data.AppendingGV.GV = &GV;
1082 WE.Data.AppendingGV.InitPrefix = InitPrefix;
1083 WE.AppendingGVIsOldCtorDtor = IsOldCtorDtor;
1084 WE.AppendingGVNumNewMembers = NewMembers.
size();
1085 Worklist.push_back(WE);
1091 assert(AlreadyScheduled.
insert(&GV).second &&
"Should not reschedule");
1092 assert((isa<GlobalAlias>(GV) || isa<GlobalIFunc>(GV)) &&
1093 "Should be alias or ifunc");
1094 assert(MCID < MCs.size() &&
"Invalid mapping context");
1097 WE.Kind = WorklistEntry::MapAliasOrIFunc;
1099 WE.Data.AliasOrIFunc.GV = &GV;
1100 WE.Data.AliasOrIFunc.Target = &
Target;
1101 Worklist.push_back(WE);
1104 void Mapper::scheduleRemapFunction(
Function &
F,
unsigned MCID) {
1105 assert(AlreadyScheduled.
insert(&
F).second &&
"Should not reschedule");
1106 assert(MCID < MCs.size() &&
"Invalid mapping context");
1111 WE.Data.RemapF = &
F;
1112 Worklist.push_back(WE);
1116 assert(!hasWorkToDo() &&
"Expected to have flushed the worklist");
1117 this->Flags = this->Flags |
Flags;
1121 return reinterpret_cast<Mapper *
>(pImpl);
1126 class FlushingMapper {
1130 explicit FlushingMapper(
void *pImpl) :
M(*
getAsMapper(pImpl)) {
1131 assert(!
M.hasWorkToDo() &&
"Expected to be flushed");
1134 ~FlushingMapper() {
M.flush(); }
1136 Mapper *operator->()
const {
return &
M; }
1144 : pImpl(
new Mapper(VM, Flags, TypeMapper, Materializer)) {}
1151 return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
1155 FlushingMapper(pImpl)->addFlags(Flags);
1159 return FlushingMapper(pImpl)->mapValue(&V);
1163 return cast_or_null<Constant>(
mapValue(
C));
1167 return FlushingMapper(pImpl)->mapMetadata(&MD);
1175 FlushingMapper(pImpl)->remapInstruction(&
I);
1179 FlushingMapper(pImpl)->remapFunction(
F);
1194 GV, InitPrefix, IsOldCtorDtor, NewMembers, MCID);
1199 getAsMapper(pImpl)->scheduleMapAliasOrIFunc(GA, Aliasee, MCID);