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