49 #define DEBUG_TYPE "value-mapper"
52 void ValueMapTypeRemapper::anchor() {}
53 void ValueMaterializer::anchor() {}
59 struct DelayedBasicBlock {
61 std::unique_ptr<BasicBlock> TempBB;
64 : OldBB(Old.getBasicBlock()),
65 TempBB(
BasicBlock::Create(Old.getContext())) {}
68 struct WorklistEntry {
79 struct AppendingGVTy {
83 struct AliasOrIFuncTy {
90 unsigned AppendingGVIsOldCtorDtor : 1;
91 unsigned AppendingGVNumNewMembers;
94 AppendingGVTy AppendingGV;
95 AliasOrIFuncTy AliasOrIFunc;
100 struct MappingContext {
107 : VM(&VM), Materializer(Materializer) {}
111 friend class MDNodeMapper;
119 unsigned CurrentMCID = 0;
128 : Flags(Flags), TypeMapper(TypeMapper),
129 MCs(1, MappingContext(VM, Materializer)) {}
132 ~Mapper() {
assert(!hasWorkToDo() &&
"Expected to be flushed"); }
134 bool hasWorkToDo()
const {
return !Worklist.empty(); }
139 MCs.push_back(MappingContext(VM, Materializer));
140 return MCs.size() - 1;
152 return cast_or_null<Constant>(mapValue(
C));
169 void scheduleRemapFunction(
Function &
F,
unsigned MCID);
195 bool HasChanged =
false;
197 TempMDNode Placeholder;
201 struct UniquedGraph {
209 void propagateChanges();
223 MDNodeMapper(Mapper &M) :
M(
M) {}
303 bool createPOT(UniquedGraph &
G,
const MDNode &FirstN);
325 void mapNodesInPOT(UniquedGraph &
G);
333 template <
class OperandMapper>
334 void remapOperands(
MDNode &
N, OperandMapper mapOperand);
343 if (
I != getVM().
end()) {
344 assert(
I->second &&
"Unexpected null mapping");
349 if (
auto *Materializer = getMaterializer()) {
350 if (
Value *NewV = Materializer->materialize(
const_cast<Value *
>(V))) {
358 if (isa<GlobalValue>(V)) {
361 return getVM()[V] =
const_cast<Value *
>(V);
364 if (
const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
368 NewTy = cast<FunctionType>(TypeMapper->
remapType(NewTy));
370 if (NewTy != IA->getFunctionType())
371 V =
InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(),
372 IA->hasSideEffects(), IA->isAlignStack(),
373 IA->getDialect(), IA->canThrow());
376 return getVM()[V] =
const_cast<Value *
>(V);
379 if (
const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
380 const Metadata *MD = MDV->getMetadata();
382 if (
auto *
LAM = dyn_cast<LocalAsMetadata>(MD)) {
384 if (
Value *LV = mapValue(
LAM->getValue())) {
385 if (V ==
LAM->getValue())
386 return const_cast<Value *
>(V);
397 if (
auto *
AL = dyn_cast<DIArgList>(MD)) {
399 for (
auto *VAM :
AL->getArgs()) {
406 MappedArgs.push_back(VAM);
407 }
else if (
Value *LV = mapValue(VAM->getValue())) {
408 MappedArgs.push_back(
411 MappedArgs.push_back(VAM);
425 return getVM()[V] =
const_cast<Value *
>(V);
428 auto *MappedMD = mapMetadata(MD);
430 return getVM()[V] =
const_cast<Value *
>(V);
441 return mapBlockAddress(*BA);
443 if (
const auto *
E = dyn_cast<DSOLocalEquivalent>(
C)) {
444 auto *Val = mapValue(
E->getGlobalValue());
449 auto *
Func = cast<Function>(Val->stripPointerCastsAndAliases());
450 Type *NewTy =
E->getType();
457 if (
const auto *
NC = dyn_cast<NoCFIValue>(
C)) {
458 auto *Val = mapValue(
NC->getGlobalValue());
463 auto mapValueOrNull = [
this](
Value *V) {
464 auto Mapped = mapValue(V);
466 "Unexpected null mapping for constant operand without "
467 "NullMapMissingGlobalValues flag");
473 unsigned OpNo = 0, NumOperands =
C->getNumOperands();
474 Value *Mapped =
nullptr;
475 for (; OpNo != NumOperands; ++OpNo) {
477 Mapped = mapValueOrNull(
Op);
485 Type *NewTy =
C->getType();
491 if (OpNo == NumOperands && NewTy ==
C->getType())
492 return getVM()[V] =
C;
498 for (
unsigned j = 0;
j != OpNo; ++
j)
499 Ops.push_back(cast<Constant>(
C->getOperand(
j)));
502 if (OpNo != NumOperands) {
503 Ops.push_back(cast<Constant>(Mapped));
506 for (++OpNo; OpNo != NumOperands; ++OpNo) {
507 Mapped = mapValueOrNull(
C->getOperand(OpNo));
510 Ops.push_back(cast<Constant>(Mapped));
513 Type *NewSrcTy =
nullptr;
515 if (
auto *GEPO = dyn_cast<GEPOperator>(
C))
516 NewSrcTy = TypeMapper->
remapType(GEPO->getSourceElementType());
519 return getVM()[V] =
CE->getWithOperands(Ops, NewTy,
false, NewSrcTy);
520 if (isa<ConstantArray>(
C))
522 if (isa<ConstantStruct>(
C))
524 if (isa<ConstantVector>(
C))
527 if (isa<UndefValue>(
C))
529 if (isa<ConstantAggregateZero>(
C))
531 assert(isa<ConstantPointerNull>(
C));
543 DelayedBBs.push_back(DelayedBasicBlock(BA));
544 BB = DelayedBBs.back().TempBB.get();
553 getVM().MD()[
Key].reset(Val);
558 return mapToMetadata(MD,
const_cast<Metadata *
>(MD));
567 if (
auto *CMD = dyn_cast<ConstantAsMetadata>(
Op))
568 assert((!*MappedOp ||
M.getVM().count(CMD->getValue()) ||
569 M.getVM().getMappedMD(
Op)) &&
570 "Expected Value to be memoized");
572 assert((isa<MDString>(
Op) ||
M.getVM().getMappedMD(
Op)) &&
573 "Expected result to be memoized");
580 return mapDistinctNode(
N);
585 assert(
N.isDistinct() &&
"Expected a distinct node");
586 assert(!
M.getVM().getMappedMD(&
N) &&
"Expected an unmapped node");
590 NewM =
M.mapToSelf(&
N);
594 <<
"To " << *NewM <<
"\n\n");
595 M.mapToMetadata(&
N, NewM);
597 DistinctWorklist.push_back(cast<MDNode>(NewM));
599 return DistinctWorklist.back();
616 if (isa<MDString>(
Op))
619 if (
auto *CMD = dyn_cast<ConstantAsMetadata>(
Op))
626 auto Where =
Info.find(&
Op);
627 assert(Where !=
Info.end() &&
"Expected a valid reference");
629 auto &OpD = Where->second;
634 if (!OpD.Placeholder)
635 OpD.Placeholder =
Op.clone();
637 return *OpD.Placeholder;
640 template <
class OperandMapper>
641 void MDNodeMapper::remapOperands(
MDNode &
N, OperandMapper mapOperand) {
642 assert(!
N.isUniqued() &&
"Expected distinct or temporary nodes");
643 for (
unsigned I = 0,
E =
N.getNumOperands();
I !=
E; ++
I) {
647 LLVM_DEBUG(
dbgs() <<
"Replacing Op " << Old <<
" with " << New <<
" in "
651 N.replaceOperandWith(
I, New);
658 struct POTWorklistEntry {
664 bool HasChanged =
false;
666 POTWorklistEntry(
MDNode &
N) :
N(&
N),
Op(
N.op_begin()) {}
671 bool MDNodeMapper::createPOT(UniquedGraph &
G,
const MDNode &FirstN) {
672 assert(
G.Info.empty() &&
"Expected a fresh traversal");
676 bool AnyChanges =
false;
678 Worklist.push_back(POTWorklistEntry(
const_cast<MDNode &
>(FirstN)));
679 (void)
G.Info[&FirstN];
680 while (!Worklist.empty()) {
682 auto &WE = Worklist.back();
683 if (
MDNode *
N = visitOperands(
G, WE.Op, WE.N->op_end(), WE.HasChanged)) {
685 Worklist.push_back(POTWorklistEntry(*
N));
690 assert(WE.N->isUniqued() &&
"Expected only uniqued nodes");
691 assert(WE.Op == WE.N->op_end() &&
"Expected to visit all operands");
692 auto &
D =
G.Info[WE.N];
693 AnyChanges |=
D.HasChanged = WE.HasChanged;
695 G.POT.push_back(WE.N);
709 HasChanged |=
Op != *MappedOp;
716 "Only uniqued operands cannot be mapped immediately");
717 if (
G.Info.insert(std::make_pair(&OpN,
Data())).second)
723 void MDNodeMapper::UniquedGraph::propagateChanges() {
733 auto Where = Info.find(Op);
734 return Where != Info.end() && Where->second.HasChanged;
738 AnyChanges =
D.HasChanged =
true;
740 }
while (AnyChanges);
743 void MDNodeMapper::mapNodesInPOT(UniquedGraph &
G) {
746 for (
auto *
N :
G.POT) {
755 bool HadPlaceholder(
D.Placeholder);
758 TempMDNode ClonedN =
D.Placeholder ?
std::move(
D.Placeholder) :
N->clone();
759 remapOperands(*ClonedN, [
this, &
D, &
G](
Metadata *Old) {
763 assert(
G.Info[Old].ID >
D.ID &&
"Expected a forward reference");
764 return &
G.getFwdReference(*cast<MDNode>(Old));
768 if (
N && NewN &&
N != NewN) {
770 <<
"To " << *NewN <<
"\n\n");
773 M.mapToMetadata(
N, NewN);
778 CyclicNodes.push_back(NewN);
782 for (
auto *
N : CyclicNodes)
783 if (!
N->isResolved())
788 assert(DistinctWorklist.empty() &&
"MDNodeMapper::map is not recursive");
790 "MDNodeMapper::map assumes module-level changes");
793 assert(
N.isResolved() &&
"Unexpected unresolved node");
796 N.isUniqued() ? mapTopLevelUniquedNode(
N) : mapDistinctNode(
N);
797 while (!DistinctWorklist.empty())
798 remapOperands(*DistinctWorklist.pop_back_val(), [
this](
Metadata *Old) {
799 if (Optional<Metadata *> MappedOp = tryToMapOperand(Old))
801 return mapTopLevelUniquedNode(*cast<MDNode>(Old));
806 Metadata *MDNodeMapper::mapTopLevelUniquedNode(
const MDNode &FirstN) {
811 if (!createPOT(
G, FirstN)) {
815 return &
const_cast<MDNode &
>(FirstN);
819 G.propagateChanges();
833 if (isa<MDString>(MD))
841 if (
auto *CMD = dyn_cast<ConstantAsMetadata>(MD)) {
849 assert(isa<MDNode>(MD) &&
"Expected a metadata node");
855 assert(MD &&
"Expected valid metadata");
856 assert(!isa<LocalAsMetadata>(MD) &&
"Unexpected local metadata");
861 return MDNodeMapper(*this).map(*cast<MDNode>(MD));
864 void Mapper::flush() {
866 while (!Worklist.empty()) {
868 CurrentMCID =
E.MCID;
870 case WorklistEntry::MapGlobalInit:
871 E.Data.GVInit.GV->setInitializer(mapConstant(
E.Data.GVInit.Init));
872 remapGlobalObjectMetadata(*
E.Data.GVInit.GV);
874 case WorklistEntry::MapAppendingVar: {
875 unsigned PrefixSize = AppendingInits.size() -
E.AppendingGVNumNewMembers;
881 AppendingInits.
resize(PrefixSize);
882 mapAppendingVariable(*
E.Data.AppendingGV.GV,
883 E.Data.AppendingGV.InitPrefix,
887 case WorklistEntry::MapAliasOrIFunc: {
890 if (
auto *GA = dyn_cast<GlobalAlias>(GV))
892 else if (
auto *GI = dyn_cast<GlobalIFunc>(GV))
899 remapFunction(*
E.Data.RemapF);
907 while (!DelayedBBs.empty()) {
909 BasicBlock *
BB = cast_or_null<BasicBlock>(mapValue(DBB.OldBB));
910 DBB.TempBB->replaceAllUsesWith(
BB ?
BB : DBB.OldBB);
916 for (
Use &
Op :
I->operands()) {
923 "Referenced value not in value map!");
927 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
928 for (
unsigned i = 0,
e = PN->getNumIncomingValues();
i !=
e; ++
i) {
929 Value *V = mapValue(PN->getIncomingBlock(
i));
932 PN->setIncomingBlock(
i, cast<BasicBlock>(V));
935 "Referenced block not in value map!");
941 I->getAllMetadata(MDs);
942 for (
const auto &
MI : MDs) {
944 MDNode *
New = cast_or_null<MDNode>(mapMetadata(Old));
946 I->setMetadata(
MI.first, New);
953 if (
auto *CB = dyn_cast<CallBase>(
I)) {
958 Tys.push_back(TypeMapper->
remapType(Ty));
964 for (
unsigned i = 0;
i <
Attrs.getNumAttrSets(); ++
i) {
965 for (
int AttrIdx = Attribute::FirstTypeAttr;
966 AttrIdx <= Attribute::LastTypeAttr; AttrIdx++) {
970 Attrs =
Attrs.replaceAttributeTypeAtIndex(
C,
i, TypedAttr,
979 if (
auto *AI = dyn_cast<AllocaInst>(
I))
980 AI->setAllocatedType(TypeMapper->
remapType(AI->getAllocatedType()));
981 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I)) {
982 GEP->setSourceElementType(
984 GEP->setResultElementType(
987 I->mutateType(TypeMapper->
remapType(
I->getType()));
990 void Mapper::remapGlobalObjectMetadata(
GlobalObject &GO) {
994 for (
const auto &
I : MDs)
995 GO.
addMetadata(
I.first, *cast<MDNode>(mapMetadata(
I.second)));
998 void Mapper::remapFunction(
Function &
F) {
1000 for (
Use &
Op :
F.operands())
1005 remapGlobalObjectMetadata(
F);
1015 remapInstruction(&
I);
1023 unsigned NumElements =
1024 cast<ArrayType>(InitPrefix->
getType())->getNumElements();
1025 for (
unsigned I = 0;
I != NumElements; ++
I)
1031 if (IsOldCtorDtor) {
1036 Type *Tys[3] = {
ST.getElementType(0),
ST.getElementType(1), VoidPtrTy};
1040 for (
auto *V : NewMembers) {
1042 if (IsOldCtorDtor) {
1043 auto *
S = cast<ConstantStruct>(V);
1044 auto *E1 = cast<Constant>(mapValue(
S->getOperand(0)));
1045 auto *E2 = cast<Constant>(mapValue(
S->getOperand(1)));
1049 NewV = cast_or_null<Constant>(mapValue(V));
1051 Elements.push_back(NewV);
1060 assert(AlreadyScheduled.
insert(&GV).second &&
"Should not reschedule");
1061 assert(MCID < MCs.size() &&
"Invalid mapping context");
1064 WE.Kind = WorklistEntry::MapGlobalInit;
1066 WE.Data.GVInit.GV = &GV;
1067 WE.Data.GVInit.Init = &
Init;
1068 Worklist.push_back(WE);
1076 assert(AlreadyScheduled.
insert(&GV).second &&
"Should not reschedule");
1077 assert(MCID < MCs.size() &&
"Invalid mapping context");
1080 WE.Kind = WorklistEntry::MapAppendingVar;
1082 WE.Data.AppendingGV.GV = &GV;
1083 WE.Data.AppendingGV.InitPrefix = InitPrefix;
1084 WE.AppendingGVIsOldCtorDtor = IsOldCtorDtor;
1085 WE.AppendingGVNumNewMembers = NewMembers.
size();
1086 Worklist.push_back(WE);
1092 assert(AlreadyScheduled.
insert(&GV).second &&
"Should not reschedule");
1093 assert((isa<GlobalAlias>(GV) || isa<GlobalIFunc>(GV)) &&
1094 "Should be alias or ifunc");
1095 assert(MCID < MCs.size() &&
"Invalid mapping context");
1098 WE.Kind = WorklistEntry::MapAliasOrIFunc;
1100 WE.Data.AliasOrIFunc.GV = &GV;
1101 WE.Data.AliasOrIFunc.Target = &
Target;
1102 Worklist.push_back(WE);
1105 void Mapper::scheduleRemapFunction(
Function &
F,
unsigned MCID) {
1106 assert(AlreadyScheduled.
insert(&
F).second &&
"Should not reschedule");
1107 assert(MCID < MCs.size() &&
"Invalid mapping context");
1112 WE.Data.RemapF = &
F;
1113 Worklist.push_back(WE);
1117 assert(!hasWorkToDo() &&
"Expected to have flushed the worklist");
1118 this->Flags = this->Flags | Flags;
1122 return reinterpret_cast<Mapper *
>(pImpl);
1127 class FlushingMapper {
1131 explicit FlushingMapper(
void *pImpl) :
M(*
getAsMapper(pImpl)) {
1132 assert(!
M.hasWorkToDo() &&
"Expected to be flushed");
1135 ~FlushingMapper() {
M.flush(); }
1137 Mapper *operator->()
const {
return &
M; }
1145 : pImpl(
new Mapper(VM, Flags, TypeMapper, Materializer)) {}
1152 return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
1156 FlushingMapper(pImpl)->addFlags(Flags);
1160 return FlushingMapper(pImpl)->mapValue(&V);
1164 return cast_or_null<Constant>(
mapValue(
C));
1168 return FlushingMapper(pImpl)->mapMetadata(&MD);
1176 FlushingMapper(pImpl)->remapInstruction(&
I);
1180 FlushingMapper(pImpl)->remapFunction(
F);
1195 GV, InitPrefix, IsOldCtorDtor, NewMembers, MCID);
1200 getAsMapper(pImpl)->scheduleMapAliasOrIFunc(GA, Aliasee, MCID);