xref: /llvm-project/llvm/tools/llvm-reduce/ReducerWorkItem.cpp (revision 333ffafb4500cad19aec81e841686ade1f31f67f) 
1 //===- ReducerWorkItem.cpp - Wrapper for Module and MachineFunction -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "ReducerWorkItem.h"
10 #include "llvm/Bitcode/BitcodeReader.h"
11 #include "llvm/CodeGen/CommandFlags.h"
12 #include "llvm/CodeGen/MIRParser/MIRParser.h"
13 #include "llvm/CodeGen/MIRPrinter.h"
14 #include "llvm/CodeGen/MachineDominators.h"
15 #include "llvm/CodeGen/MachineFrameInfo.h"
16 #include "llvm/CodeGen/MachineFunction.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineModuleInfo.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetInstrInfo.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/ModuleSummaryIndex.h"
24 #include "llvm/IR/Operator.h"
25 #include "llvm/IR/Verifier.h"
26 #include "llvm/IRReader/IRReader.h"
27 #include "llvm/MC/TargetRegistry.h"
28 #include "llvm/Support/Host.h"
29 #include "llvm/Support/MemoryBufferRef.h"
30 #include "llvm/Support/SourceMgr.h"
31 #include "llvm/Support/TargetSelect.h"
32 #include "llvm/Support/WithColor.h"
33 #include "llvm/Target/TargetMachine.h"
34 #include "llvm/Transforms/Utils/Cloning.h"
35 #include <optional>
36 
37 using namespace llvm;
38 
39 ReducerWorkItem::ReducerWorkItem() = default;
40 ReducerWorkItem::~ReducerWorkItem() = default;
41 
42 extern cl::OptionCategory LLVMReduceOptions;
43 static cl::opt<std::string> TargetTriple("mtriple",
44                                          cl::desc("Set the target triple"),
45                                          cl::cat(LLVMReduceOptions));
46 
47 void readBitcode(ReducerWorkItem &M, MemoryBufferRef Data, LLVMContext &Ctx,
48                  StringRef ToolName);
49 
50 static void cloneFrameInfo(
51     MachineFrameInfo &DstMFI, const MachineFrameInfo &SrcMFI,
52     const DenseMap<MachineBasicBlock *, MachineBasicBlock *> &Src2DstMBB) {
53   DstMFI.setFrameAddressIsTaken(SrcMFI.isFrameAddressTaken());
54   DstMFI.setReturnAddressIsTaken(SrcMFI.isReturnAddressTaken());
55   DstMFI.setHasStackMap(SrcMFI.hasStackMap());
56   DstMFI.setHasPatchPoint(SrcMFI.hasPatchPoint());
57   DstMFI.setUseLocalStackAllocationBlock(
58       SrcMFI.getUseLocalStackAllocationBlock());
59   DstMFI.setOffsetAdjustment(SrcMFI.getOffsetAdjustment());
60 
61   DstMFI.ensureMaxAlignment(SrcMFI.getMaxAlign());
62   assert(DstMFI.getMaxAlign() == SrcMFI.getMaxAlign() &&
63          "we need to set exact alignment");
64 
65   DstMFI.setAdjustsStack(SrcMFI.adjustsStack());
66   DstMFI.setHasCalls(SrcMFI.hasCalls());
67   DstMFI.setHasOpaqueSPAdjustment(SrcMFI.hasOpaqueSPAdjustment());
68   DstMFI.setHasCopyImplyingStackAdjustment(
69       SrcMFI.hasCopyImplyingStackAdjustment());
70   DstMFI.setHasVAStart(SrcMFI.hasVAStart());
71   DstMFI.setHasMustTailInVarArgFunc(SrcMFI.hasMustTailInVarArgFunc());
72   DstMFI.setHasTailCall(SrcMFI.hasTailCall());
73 
74   if (SrcMFI.isMaxCallFrameSizeComputed())
75     DstMFI.setMaxCallFrameSize(SrcMFI.getMaxCallFrameSize());
76 
77   DstMFI.setCVBytesOfCalleeSavedRegisters(
78       SrcMFI.getCVBytesOfCalleeSavedRegisters());
79 
80   if (MachineBasicBlock *SavePt = SrcMFI.getSavePoint())
81     DstMFI.setSavePoint(Src2DstMBB.find(SavePt)->second);
82   if (MachineBasicBlock *RestorePt = SrcMFI.getRestorePoint())
83     DstMFI.setRestorePoint(Src2DstMBB.find(RestorePt)->second);
84 
85 
86   auto CopyObjectProperties = [](MachineFrameInfo &DstMFI,
87                                  const MachineFrameInfo &SrcMFI, int FI) {
88     if (SrcMFI.isStatepointSpillSlotObjectIndex(FI))
89       DstMFI.markAsStatepointSpillSlotObjectIndex(FI);
90     DstMFI.setObjectSSPLayout(FI, SrcMFI.getObjectSSPLayout(FI));
91     DstMFI.setObjectZExt(FI, SrcMFI.isObjectZExt(FI));
92     DstMFI.setObjectSExt(FI, SrcMFI.isObjectSExt(FI));
93   };
94 
95   for (int i = 0, e = SrcMFI.getNumObjects() - SrcMFI.getNumFixedObjects();
96        i != e; ++i) {
97     int NewFI;
98 
99     assert(!SrcMFI.isFixedObjectIndex(i));
100     if (SrcMFI.isVariableSizedObjectIndex(i)) {
101       NewFI = DstMFI.CreateVariableSizedObject(SrcMFI.getObjectAlign(i),
102                                                SrcMFI.getObjectAllocation(i));
103     } else {
104       NewFI = DstMFI.CreateStackObject(
105           SrcMFI.getObjectSize(i), SrcMFI.getObjectAlign(i),
106           SrcMFI.isSpillSlotObjectIndex(i), SrcMFI.getObjectAllocation(i),
107           SrcMFI.getStackID(i));
108       DstMFI.setObjectOffset(NewFI, SrcMFI.getObjectOffset(i));
109     }
110 
111     CopyObjectProperties(DstMFI, SrcMFI, i);
112 
113     (void)NewFI;
114     assert(i == NewFI && "expected to keep stable frame index numbering");
115   }
116 
117   // Copy the fixed frame objects backwards to preserve frame index numbers,
118   // since CreateFixedObject uses front insertion.
119   for (int i = -1; i >= (int)-SrcMFI.getNumFixedObjects(); --i) {
120     assert(SrcMFI.isFixedObjectIndex(i));
121     int NewFI = DstMFI.CreateFixedObject(
122       SrcMFI.getObjectSize(i), SrcMFI.getObjectOffset(i),
123       SrcMFI.isImmutableObjectIndex(i), SrcMFI.isAliasedObjectIndex(i));
124     CopyObjectProperties(DstMFI, SrcMFI, i);
125 
126     (void)NewFI;
127     assert(i == NewFI && "expected to keep stable frame index numbering");
128   }
129 
130   for (unsigned I = 0, E = SrcMFI.getLocalFrameObjectCount(); I < E; ++I) {
131     auto LocalObject = SrcMFI.getLocalFrameObjectMap(I);
132     DstMFI.mapLocalFrameObject(LocalObject.first, LocalObject.second);
133   }
134 
135   DstMFI.setCalleeSavedInfo(SrcMFI.getCalleeSavedInfo());
136 
137   if (SrcMFI.hasStackProtectorIndex()) {
138     DstMFI.setStackProtectorIndex(SrcMFI.getStackProtectorIndex());
139   }
140 
141   // FIXME: Needs test, missing MIR serialization.
142   if (SrcMFI.hasFunctionContextIndex()) {
143     DstMFI.setFunctionContextIndex(SrcMFI.getFunctionContextIndex());
144   }
145 }
146 
147 static void cloneMemOperands(MachineInstr &DstMI, MachineInstr &SrcMI,
148                              MachineFunction &SrcMF, MachineFunction &DstMF) {
149   // The new MachineMemOperands should be owned by the new function's
150   // Allocator.
151   PseudoSourceValueManager &PSVMgr = DstMF.getPSVManager();
152 
153   // We also need to remap the PseudoSourceValues from the new function's
154   // PseudoSourceValueManager.
155   SmallVector<MachineMemOperand *, 2> NewMMOs;
156   for (MachineMemOperand *OldMMO : SrcMI.memoperands()) {
157     MachinePointerInfo NewPtrInfo(OldMMO->getPointerInfo());
158     if (const PseudoSourceValue *PSV =
159             NewPtrInfo.V.dyn_cast<const PseudoSourceValue *>()) {
160       switch (PSV->kind()) {
161       case PseudoSourceValue::Stack:
162         NewPtrInfo.V = PSVMgr.getStack();
163         break;
164       case PseudoSourceValue::GOT:
165         NewPtrInfo.V = PSVMgr.getGOT();
166         break;
167       case PseudoSourceValue::JumpTable:
168         NewPtrInfo.V = PSVMgr.getJumpTable();
169         break;
170       case PseudoSourceValue::ConstantPool:
171         NewPtrInfo.V = PSVMgr.getConstantPool();
172         break;
173       case PseudoSourceValue::FixedStack:
174         NewPtrInfo.V = PSVMgr.getFixedStack(
175             cast<FixedStackPseudoSourceValue>(PSV)->getFrameIndex());
176         break;
177       case PseudoSourceValue::GlobalValueCallEntry:
178         NewPtrInfo.V = PSVMgr.getGlobalValueCallEntry(
179             cast<GlobalValuePseudoSourceValue>(PSV)->getValue());
180         break;
181       case PseudoSourceValue::ExternalSymbolCallEntry:
182         NewPtrInfo.V = PSVMgr.getExternalSymbolCallEntry(
183             cast<ExternalSymbolPseudoSourceValue>(PSV)->getSymbol());
184         break;
185       case PseudoSourceValue::TargetCustom:
186       default:
187         // FIXME: We have no generic interface for allocating custom PSVs.
188         report_fatal_error("Cloning TargetCustom PSV not handled");
189       }
190     }
191 
192     MachineMemOperand *NewMMO = DstMF.getMachineMemOperand(
193         NewPtrInfo, OldMMO->getFlags(), OldMMO->getMemoryType(),
194         OldMMO->getBaseAlign(), OldMMO->getAAInfo(), OldMMO->getRanges(),
195         OldMMO->getSyncScopeID(), OldMMO->getSuccessOrdering(),
196         OldMMO->getFailureOrdering());
197     NewMMOs.push_back(NewMMO);
198   }
199 
200   DstMI.setMemRefs(DstMF, NewMMOs);
201 }
202 
203 static std::unique_ptr<MachineFunction> cloneMF(MachineFunction *SrcMF,
204                                                 MachineModuleInfo &DestMMI) {
205   auto DstMF = std::make_unique<MachineFunction>(
206       SrcMF->getFunction(), SrcMF->getTarget(), SrcMF->getSubtarget(),
207       SrcMF->getFunctionNumber(), DestMMI);
208   DenseMap<MachineBasicBlock *, MachineBasicBlock *> Src2DstMBB;
209 
210   auto *SrcMRI = &SrcMF->getRegInfo();
211   auto *DstMRI = &DstMF->getRegInfo();
212 
213   // Clone blocks.
214   for (MachineBasicBlock &SrcMBB : *SrcMF) {
215     MachineBasicBlock *DstMBB =
216         DstMF->CreateMachineBasicBlock(SrcMBB.getBasicBlock());
217     Src2DstMBB[&SrcMBB] = DstMBB;
218 
219     if (SrcMBB.isIRBlockAddressTaken())
220       DstMBB->setAddressTakenIRBlock(SrcMBB.getAddressTakenIRBlock());
221     if (SrcMBB.isMachineBlockAddressTaken())
222       DstMBB->setMachineBlockAddressTaken();
223 
224     // FIXME: This is not serialized
225     if (SrcMBB.hasLabelMustBeEmitted())
226       DstMBB->setLabelMustBeEmitted();
227 
228     DstMBB->setAlignment(SrcMBB.getAlignment());
229 
230     // FIXME: This is not serialized
231     DstMBB->setMaxBytesForAlignment(SrcMBB.getMaxBytesForAlignment());
232 
233     DstMBB->setIsEHPad(SrcMBB.isEHPad());
234     DstMBB->setIsEHScopeEntry(SrcMBB.isEHScopeEntry());
235     DstMBB->setIsEHCatchretTarget(SrcMBB.isEHCatchretTarget());
236     DstMBB->setIsEHFuncletEntry(SrcMBB.isEHFuncletEntry());
237 
238     // FIXME: These are not serialized
239     DstMBB->setIsCleanupFuncletEntry(SrcMBB.isCleanupFuncletEntry());
240     DstMBB->setIsBeginSection(SrcMBB.isBeginSection());
241     DstMBB->setIsEndSection(SrcMBB.isEndSection());
242 
243     DstMBB->setSectionID(SrcMBB.getSectionID());
244     DstMBB->setIsInlineAsmBrIndirectTarget(
245         SrcMBB.isInlineAsmBrIndirectTarget());
246 
247     // FIXME: This is not serialized
248     if (std::optional<uint64_t> Weight = SrcMBB.getIrrLoopHeaderWeight())
249       DstMBB->setIrrLoopHeaderWeight(*Weight);
250   }
251 
252   const MachineFrameInfo &SrcMFI = SrcMF->getFrameInfo();
253   MachineFrameInfo &DstMFI = DstMF->getFrameInfo();
254 
255   // Copy stack objects and other info
256   cloneFrameInfo(DstMFI, SrcMFI, Src2DstMBB);
257 
258   // Remap the debug info frame index references.
259   DstMF->VariableDbgInfos = SrcMF->VariableDbgInfos;
260 
261   // Clone virtual registers
262   for (unsigned I = 0, E = SrcMRI->getNumVirtRegs(); I != E; ++I) {
263     Register Reg = Register::index2VirtReg(I);
264     Register NewReg = DstMRI->createIncompleteVirtualRegister(
265       SrcMRI->getVRegName(Reg));
266     assert(NewReg == Reg && "expected to preserve virtreg number");
267 
268     DstMRI->setRegClassOrRegBank(NewReg, SrcMRI->getRegClassOrRegBank(Reg));
269 
270     LLT RegTy = SrcMRI->getType(Reg);
271     if (RegTy.isValid())
272       DstMRI->setType(NewReg, RegTy);
273 
274     // Copy register allocation hints.
275     const auto &Hints = SrcMRI->getRegAllocationHints(Reg);
276     for (Register PrefReg : Hints.second)
277       DstMRI->addRegAllocationHint(NewReg, PrefReg);
278   }
279 
280   const TargetSubtargetInfo &STI = DstMF->getSubtarget();
281   const TargetInstrInfo *TII = STI.getInstrInfo();
282   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
283 
284   // Link blocks.
285   for (auto &SrcMBB : *SrcMF) {
286     auto *DstMBB = Src2DstMBB[&SrcMBB];
287     DstMF->push_back(DstMBB);
288 
289     for (auto It = SrcMBB.succ_begin(), IterEnd = SrcMBB.succ_end();
290          It != IterEnd; ++It) {
291       auto *SrcSuccMBB = *It;
292       auto *DstSuccMBB = Src2DstMBB[SrcSuccMBB];
293       DstMBB->addSuccessor(DstSuccMBB, SrcMBB.getSuccProbability(It));
294     }
295 
296     for (auto &LI : SrcMBB.liveins_dbg())
297       DstMBB->addLiveIn(LI);
298 
299     // Make sure MRI knows about registers clobbered by unwinder.
300     if (DstMBB->isEHPad()) {
301       if (auto *RegMask = TRI->getCustomEHPadPreservedMask(*DstMF))
302         DstMRI->addPhysRegsUsedFromRegMask(RegMask);
303     }
304   }
305 
306   DenseSet<const uint32_t *> ConstRegisterMasks;
307 
308   // Track predefined/named regmasks which we ignore.
309   for (const uint32_t *Mask : TRI->getRegMasks())
310     ConstRegisterMasks.insert(Mask);
311 
312   // Clone instructions.
313   for (auto &SrcMBB : *SrcMF) {
314     auto *DstMBB = Src2DstMBB[&SrcMBB];
315     for (auto &SrcMI : SrcMBB) {
316       const auto &MCID = TII->get(SrcMI.getOpcode());
317       auto *DstMI = DstMF->CreateMachineInstr(MCID, SrcMI.getDebugLoc(),
318                                               /*NoImplicit=*/true);
319       DstMI->setFlags(SrcMI.getFlags());
320       DstMI->setAsmPrinterFlag(SrcMI.getAsmPrinterFlags());
321 
322       DstMBB->push_back(DstMI);
323       for (auto &SrcMO : SrcMI.operands()) {
324         MachineOperand DstMO(SrcMO);
325         DstMO.clearParent();
326 
327         // Update MBB.
328         if (DstMO.isMBB())
329           DstMO.setMBB(Src2DstMBB[DstMO.getMBB()]);
330         else if (DstMO.isRegMask()) {
331           DstMRI->addPhysRegsUsedFromRegMask(DstMO.getRegMask());
332 
333           if (!ConstRegisterMasks.count(DstMO.getRegMask())) {
334             uint32_t *DstMask = DstMF->allocateRegMask();
335             std::memcpy(DstMask, SrcMO.getRegMask(),
336                         sizeof(*DstMask) *
337                             MachineOperand::getRegMaskSize(TRI->getNumRegs()));
338             DstMO.setRegMask(DstMask);
339           }
340         }
341 
342         DstMI->addOperand(DstMO);
343       }
344 
345       cloneMemOperands(*DstMI, SrcMI, *SrcMF, *DstMF);
346     }
347   }
348 
349   DstMF->setAlignment(SrcMF->getAlignment());
350   DstMF->setExposesReturnsTwice(SrcMF->exposesReturnsTwice());
351   DstMF->setHasInlineAsm(SrcMF->hasInlineAsm());
352   DstMF->setHasWinCFI(SrcMF->hasWinCFI());
353 
354   DstMF->getProperties().reset().set(SrcMF->getProperties());
355 
356   if (!SrcMF->getFrameInstructions().empty() ||
357       !SrcMF->getLongjmpTargets().empty() ||
358       !SrcMF->getCatchretTargets().empty())
359     report_fatal_error("cloning not implemented for machine function property");
360 
361   DstMF->setCallsEHReturn(SrcMF->callsEHReturn());
362   DstMF->setCallsUnwindInit(SrcMF->callsUnwindInit());
363   DstMF->setHasEHCatchret(SrcMF->hasEHCatchret());
364   DstMF->setHasEHScopes(SrcMF->hasEHScopes());
365   DstMF->setHasEHFunclets(SrcMF->hasEHFunclets());
366 
367   if (!SrcMF->getLandingPads().empty() ||
368       !SrcMF->getCodeViewAnnotations().empty() ||
369       !SrcMF->getTypeInfos().empty() ||
370       !SrcMF->getFilterIds().empty() ||
371       SrcMF->hasAnyWasmLandingPadIndex() ||
372       SrcMF->hasAnyCallSiteLandingPad() ||
373       SrcMF->hasAnyCallSiteLabel() ||
374       !SrcMF->getCallSitesInfo().empty())
375     report_fatal_error("cloning not implemented for machine function property");
376 
377   DstMF->setDebugInstrNumberingCount(SrcMF->DebugInstrNumberingCount);
378 
379   if (!DstMF->cloneInfoFrom(*SrcMF, Src2DstMBB))
380     report_fatal_error("target does not implement MachineFunctionInfo cloning");
381 
382   DstMRI->freezeReservedRegs(*DstMF);
383 
384   DstMF->verify(nullptr, "", /*AbortOnError=*/true);
385   return DstMF;
386 }
387 
388 static void initializeTargetInfo() {
389   InitializeAllTargets();
390   InitializeAllTargetMCs();
391   InitializeAllAsmPrinters();
392   InitializeAllAsmParsers();
393 }
394 
395 std::pair<std::unique_ptr<ReducerWorkItem>, bool>
396 parseReducerWorkItem(StringRef ToolName, StringRef Filename, LLVMContext &Ctxt,
397                      std::unique_ptr<TargetMachine> &TM, bool IsMIR) {
398   bool IsBitcode = false;
399   Triple TheTriple;
400 
401   auto MMM = std::make_unique<ReducerWorkItem>();
402 
403   if (IsMIR) {
404     initializeTargetInfo();
405 
406     auto FileOrErr = MemoryBuffer::getFileOrSTDIN(Filename, /*IsText=*/true);
407     if (std::error_code EC = FileOrErr.getError()) {
408       WithColor::error(errs(), ToolName) << EC.message() << '\n';
409       return {nullptr, false};
410     }
411 
412     std::unique_ptr<MIRParser> MParser =
413         createMIRParser(std::move(FileOrErr.get()), Ctxt);
414 
415     auto SetDataLayout = [&](StringRef DataLayoutTargetTriple,
416                              StringRef OldDLStr) -> std::optional<std::string> {
417       // If we are supposed to override the target triple, do so now.
418       std::string IRTargetTriple = DataLayoutTargetTriple.str();
419       if (!TargetTriple.empty())
420         IRTargetTriple = Triple::normalize(TargetTriple);
421       TheTriple = Triple(IRTargetTriple);
422       if (TheTriple.getTriple().empty())
423         TheTriple.setTriple(sys::getDefaultTargetTriple());
424 
425       std::string Error;
426       const Target *TheTarget =
427           TargetRegistry::lookupTarget(codegen::getMArch(), TheTriple, Error);
428       if (!TheTarget) {
429         WithColor::error(errs(), ToolName) << Error;
430         exit(1);
431       }
432 
433       // Hopefully the MIR parsing doesn't depend on any options.
434       TargetOptions Options;
435       std::optional<Reloc::Model> RM = codegen::getExplicitRelocModel();
436       std::string CPUStr = codegen::getCPUStr();
437       std::string FeaturesStr = codegen::getFeaturesStr();
438       TM = std::unique_ptr<TargetMachine>(TheTarget->createTargetMachine(
439           TheTriple.getTriple(), CPUStr, FeaturesStr, Options, RM,
440           codegen::getExplicitCodeModel(), CodeGenOpt::Default));
441       assert(TM && "Could not allocate target machine!");
442 
443       return TM->createDataLayout().getStringRepresentation();
444     };
445 
446     std::unique_ptr<Module> M = MParser->parseIRModule(SetDataLayout);
447     LLVMTargetMachine *LLVMTM = static_cast<LLVMTargetMachine *>(TM.get());
448 
449     MMM->MMI = std::make_unique<MachineModuleInfo>(LLVMTM);
450     MParser->parseMachineFunctions(*M, *MMM->MMI);
451     MMM->M = std::move(M);
452   } else {
453     SMDiagnostic Err;
454     ErrorOr<std::unique_ptr<MemoryBuffer>> MB = MemoryBuffer::getFileOrSTDIN(Filename);
455     if (std::error_code EC = MB.getError()) {
456       WithColor::error(errs(), ToolName) << Filename << ": " << EC.message() << "\n";
457       return {nullptr, false};
458     }
459 
460     if (!isBitcode((const unsigned char *)(*MB)->getBufferStart(),
461                   (const unsigned char *)(*MB)->getBufferEnd())) {
462       std::unique_ptr<Module> Result = parseIRFile(Filename, Err, Ctxt);
463       if (!Result) {
464         Err.print(ToolName.data(), errs());
465         return {nullptr, false};
466       }
467       MMM->M = std::move(Result);
468     } else {
469       IsBitcode = true;
470       readBitcode(*MMM, MemoryBufferRef(**MB), Ctxt, ToolName);
471 
472       if (MMM->LTOInfo->IsThinLTO && MMM->LTOInfo->EnableSplitLTOUnit)
473        initializeTargetInfo();
474     }
475   }
476   if (verifyReducerWorkItem(*MMM, &errs())) {
477     WithColor::error(errs(), ToolName)
478         << Filename << " - input module is broken!\n";
479     return {nullptr, false};
480   }
481   return {std::move(MMM), IsBitcode};
482 }
483 
484 std::unique_ptr<ReducerWorkItem>
485 cloneReducerWorkItem(const ReducerWorkItem &MMM, const TargetMachine *TM) {
486   auto CloneMMM = std::make_unique<ReducerWorkItem>();
487   if (TM) {
488     // We're assuming the Module IR contents are always unchanged by MIR
489     // reductions, and can share it as a constant.
490     CloneMMM->M = MMM.M;
491 
492     // MachineModuleInfo contains a lot of other state used during codegen which
493     // we won't be using here, but we should be able to ignore it (although this
494     // is pretty ugly).
495     const LLVMTargetMachine *LLVMTM =
496         static_cast<const LLVMTargetMachine *>(TM);
497     CloneMMM->MMI = std::make_unique<MachineModuleInfo>(LLVMTM);
498 
499     for (const Function &F : MMM.getModule()) {
500       if (auto *MF = MMM.MMI->getMachineFunction(F))
501         CloneMMM->MMI->insertFunction(F, cloneMF(MF, *CloneMMM->MMI));
502     }
503   } else {
504     CloneMMM->M = CloneModule(*MMM.M);
505   }
506   return CloneMMM;
507 }
508 
509 bool verifyReducerWorkItem(const ReducerWorkItem &MMM, raw_fd_ostream *OS) {
510   if (verifyModule(*MMM.M, OS))
511     return true;
512 
513   if (!MMM.MMI)
514     return false;
515 
516   for (const Function &F : MMM.getModule()) {
517     if (const MachineFunction *MF = MMM.MMI->getMachineFunction(F)) {
518       if (!MF->verify(nullptr, "", /*AbortOnError=*/false))
519         return true;
520     }
521   }
522 
523   return false;
524 }
525 
526 void ReducerWorkItem::print(raw_ostream &ROS, void *p) const {
527   if (MMI) {
528     printMIR(ROS, *M);
529     for (Function &F : *M) {
530       if (auto *MF = MMI->getMachineFunction(F))
531         printMIR(ROS, *MF);
532     }
533   } else {
534     M->print(ROS, /*AssemblyAnnotationWriter=*/nullptr,
535              /*ShouldPreserveUseListOrder=*/true);
536   }
537 }
538 
539 /// Try to produce some number that indicates a function is getting smaller /
540 /// simpler.
541 static uint64_t computeMIRComplexityScoreImpl(const MachineFunction &MF) {
542   uint64_t Score = 0;
543   const MachineFrameInfo &MFI = MF.getFrameInfo();
544 
545   // Add for stack objects
546   Score += MFI.getNumObjects();
547 
548   // Add in the block count.
549   Score += 2 * MF.size();
550 
551   const MachineRegisterInfo &MRI = MF.getRegInfo();
552   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
553     Register Reg = Register::index2VirtReg(I);
554     Score += MRI.getRegAllocationHints(Reg).second.size();
555   }
556 
557   for (const MachineBasicBlock &MBB : MF) {
558     for (const MachineInstr &MI : MBB) {
559       const unsigned Opc = MI.getOpcode();
560 
561       // Reductions may want or need to introduce implicit_defs, so don't count
562       // them.
563       // TODO: These probably should count in some way.
564       if (Opc == TargetOpcode::IMPLICIT_DEF ||
565           Opc == TargetOpcode::G_IMPLICIT_DEF)
566         continue;
567 
568       // Each instruction adds to the score
569       Score += 4;
570 
571       if (Opc == TargetOpcode::PHI || Opc == TargetOpcode::G_PHI ||
572           Opc == TargetOpcode::INLINEASM || Opc == TargetOpcode::INLINEASM_BR)
573         ++Score;
574 
575       if (MI.getFlags() != 0)
576         ++Score;
577 
578       // Increase weight for more operands.
579       for (const MachineOperand &MO : MI.operands()) {
580         ++Score;
581 
582         // Treat registers as more complex.
583         if (MO.isReg()) {
584           ++Score;
585 
586           // And subregisters as even more complex.
587           if (MO.getSubReg()) {
588             ++Score;
589             if (MO.isDef())
590               ++Score;
591           }
592         } else if (MO.isRegMask())
593           ++Score;
594       }
595     }
596   }
597 
598   return Score;
599 }
600 
601 uint64_t ReducerWorkItem::computeMIRComplexityScore() const {
602   uint64_t Score = 0;
603 
604   for (const Function &F : getModule()) {
605     if (auto *MF = MMI->getMachineFunction(F))
606       Score += computeMIRComplexityScoreImpl(*MF);
607   }
608 
609   return Score;
610 }
611 
612 // FIXME: ReduceOperandsSkip has similar function, except it uses larger numbers
613 // for more reduced.
614 static unsigned classifyReductivePower(const Value *V) {
615   if (auto *C = dyn_cast<ConstantData>(V)) {
616     if (C->isNullValue())
617       return 0;
618     if (C->isOneValue())
619       return 1;
620     if (isa<UndefValue>(V))
621       return 2;
622     return 3;
623   }
624 
625   if (isa<GlobalValue>(V))
626     return 4;
627 
628   // TODO: Account for expression size
629   if (isa<ConstantExpr>(V))
630     return 5;
631 
632   if (isa<Constant>(V))
633     return 1;
634 
635   if (isa<Argument>(V))
636     return 6;
637 
638   if (isa<Instruction>(V))
639     return 7;
640 
641   return 0;
642 }
643 
644 // TODO: Additional flags and attributes may be complexity reducing. If we start
645 // adding flags and attributes, they could have negative cost.
646 static uint64_t computeIRComplexityScoreImpl(const Function &F) {
647   uint64_t Score = 1; // Count the function itself
648   SmallVector<std::pair<unsigned, MDNode *>> MDs;
649 
650   AttributeList Attrs = F.getAttributes();
651   for (AttributeSet AttrSet : Attrs)
652     Score += AttrSet.getNumAttributes();
653 
654   for (const BasicBlock &BB : F) {
655     ++Score;
656 
657     for (const Instruction &I : BB) {
658       ++Score;
659 
660       if (const auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(&I)) {
661         if (OverflowOp->hasNoUnsignedWrap())
662           ++Score;
663         if (OverflowOp->hasNoSignedWrap())
664           ++Score;
665       } else if (const auto *GEP = dyn_cast<GEPOperator>(&I)) {
666         if (GEP->isInBounds())
667           ++Score;
668       } else if (const auto *ExactOp = dyn_cast<PossiblyExactOperator>(&I)) {
669         if (ExactOp->isExact())
670           ++Score;
671       } else if (const auto *FPOp = dyn_cast<FPMathOperator>(&I)) {
672         FastMathFlags FMF = FPOp->getFastMathFlags();
673         if (FMF.allowReassoc())
674           ++Score;
675         if (FMF.noNaNs())
676           ++Score;
677         if (FMF.noInfs())
678           ++Score;
679         if (FMF.noSignedZeros())
680           ++Score;
681         if (FMF.allowReciprocal())
682           ++Score;
683         if (FMF.allowContract())
684           ++Score;
685         if (FMF.approxFunc())
686           ++Score;
687       }
688 
689       for (const Value *Operand : I.operands()) {
690         ++Score;
691         Score += classifyReductivePower(Operand);
692       }
693 
694       I.getAllMetadata(MDs);
695       Score += MDs.size();
696       MDs.clear();
697     }
698   }
699 
700   return Score;
701 }
702 
703 uint64_t ReducerWorkItem::computeIRComplexityScore() const {
704   uint64_t Score = 0;
705 
706   const Module &M = getModule();
707   Score += M.named_metadata_size();
708 
709   SmallVector<std::pair<unsigned, MDNode *>, 32> GlobalMetadata;
710   for (const GlobalVariable &GV : M.globals()) {
711     ++Score;
712 
713     if (GV.hasInitializer())
714       Score += classifyReductivePower(GV.getInitializer());
715 
716     // TODO: Account for linkage?
717 
718     GV.getAllMetadata(GlobalMetadata);
719     Score += GlobalMetadata.size();
720     GlobalMetadata.clear();
721   }
722 
723   for (const GlobalAlias &GA : M.aliases())
724     Score += classifyReductivePower(GA.getAliasee());
725 
726   for (const GlobalIFunc &GI : M.ifuncs())
727     Score += classifyReductivePower(GI.getResolver());
728 
729   for (const Function &F : M)
730     Score += computeIRComplexityScoreImpl(F);
731 
732   return Score;
733 }
734