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 "TestRunner.h"
11#include "llvm/Analysis/ModuleSummaryAnalysis.h"
12#include "llvm/Analysis/ProfileSummaryInfo.h"
13#include "llvm/Bitcode/BitcodeReader.h"
14#include "llvm/Bitcode/BitcodeWriter.h"
15#include "llvm/CodeGen/CommandFlags.h"
16#include "llvm/CodeGen/MIRParser/MIRParser.h"
17#include "llvm/CodeGen/MIRPrinter.h"
18#include "llvm/CodeGen/MachineDominators.h"
19#include "llvm/CodeGen/MachineFrameInfo.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineJumpTableInfo.h"
22#include "llvm/CodeGen/MachineModuleInfo.h"
23#include "llvm/CodeGen/MachineModuleSlotTracker.h"
24#include "llvm/CodeGen/MachineRegisterInfo.h"
25#include "llvm/CodeGen/PseudoSourceValueManager.h"
26#include "llvm/CodeGen/TargetInstrInfo.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/IR/Instructions.h"
29#include "llvm/IR/ModuleSummaryIndex.h"
30#include "llvm/IR/Operator.h"
31#include "llvm/IR/Verifier.h"
32#include "llvm/IRReader/IRReader.h"
33#include "llvm/MC/TargetRegistry.h"
34#include "llvm/Passes/PassBuilder.h"
35#include "llvm/Support/MemoryBufferRef.h"
36#include "llvm/Support/SourceMgr.h"
37#include "llvm/Support/ToolOutputFile.h"
38#include "llvm/Support/WithColor.h"
39#include "llvm/Target/TargetMachine.h"
40#include "llvm/TargetParser/Host.h"
41#include "llvm/Transforms/IPO/ThinLTOBitcodeWriter.h"
42#include "llvm/Transforms/IPO/WholeProgramDevirt.h"
43#include "llvm/Transforms/Utils/AssignGUID.h"
44#include "llvm/Transforms/Utils/Cloning.h"
45#include <optional>
46
47using namespace llvm;
48
49ReducerWorkItem::ReducerWorkItem() = default;
50ReducerWorkItem::~ReducerWorkItem() = default;
51
52extern cl::OptionCategory LLVMReduceOptions;
53static cl::opt<std::string> TargetTriple("mtriple",
54 cl::desc("Set the target triple"),
55 cl::cat(LLVMReduceOptions));
56static cl::opt<bool> PrintInvalidMachineReductions(
57 "print-invalid-reduction-machine-verifier-errors",
58 cl::desc(
59 "Print machine verifier errors on invalid reduction attempts triple"),
60 cl::cat(LLVMReduceOptions));
61
62static cl::opt<bool> TmpFilesAsBitcode(
63 "write-tmp-files-as-bitcode",
64 cl::desc("Always write temporary files as bitcode instead of textual IR"),
65 cl::init(Val: false), cl::cat(LLVMReduceOptions));
66
67static SaveRestorePoints constructSaveRestorePoints(
68 const SaveRestorePoints &SRPoints,
69 const DenseMap<MachineBasicBlock *, MachineBasicBlock *> &BBMap) {
70 SaveRestorePoints Pts{};
71 for (auto &Src : SRPoints)
72 Pts.insert(KV: {BBMap.find(Val: Src.first)->second, Src.second});
73 return Pts;
74}
75
76static void cloneFrameInfo(
77 MachineFrameInfo &DstMFI, const MachineFrameInfo &SrcMFI,
78 const DenseMap<MachineBasicBlock *, MachineBasicBlock *> &Src2DstMBB) {
79 DstMFI.setFrameAddressIsTaken(SrcMFI.isFrameAddressTaken());
80 DstMFI.setReturnAddressIsTaken(SrcMFI.isReturnAddressTaken());
81 DstMFI.setHasStackMap(SrcMFI.hasStackMap());
82 DstMFI.setHasPatchPoint(SrcMFI.hasPatchPoint());
83 DstMFI.setUseLocalStackAllocationBlock(
84 SrcMFI.getUseLocalStackAllocationBlock());
85 DstMFI.setOffsetAdjustment(SrcMFI.getOffsetAdjustment());
86
87 DstMFI.ensureMaxAlignment(Alignment: SrcMFI.getMaxAlign());
88 assert(DstMFI.getMaxAlign() == SrcMFI.getMaxAlign() &&
89 "we need to set exact alignment");
90
91 DstMFI.setAdjustsStack(SrcMFI.adjustsStack());
92 DstMFI.setHasCalls(SrcMFI.hasCalls());
93 DstMFI.setHasOpaqueSPAdjustment(SrcMFI.hasOpaqueSPAdjustment());
94 DstMFI.setHasCopyImplyingStackAdjustment(
95 SrcMFI.hasCopyImplyingStackAdjustment());
96 DstMFI.setHasVAStart(SrcMFI.hasVAStart());
97 DstMFI.setHasMustTailInVarArgFunc(SrcMFI.hasMustTailInVarArgFunc());
98 DstMFI.setHasTailCall(SrcMFI.hasTailCall());
99
100 if (SrcMFI.isMaxCallFrameSizeComputed())
101 DstMFI.setMaxCallFrameSize(SrcMFI.getMaxCallFrameSize());
102
103 DstMFI.setCVBytesOfCalleeSavedRegisters(
104 SrcMFI.getCVBytesOfCalleeSavedRegisters());
105
106 assert(SrcMFI.getSavePoints().size() < 2 &&
107 "Multiple restore points not yet supported!");
108
109 DstMFI.setSavePoints(
110 constructSaveRestorePoints(SRPoints: SrcMFI.getSavePoints(), BBMap: Src2DstMBB));
111
112 assert(SrcMFI.getRestorePoints().size() < 2 &&
113 "Multiple restore points not yet supported!");
114
115 DstMFI.setRestorePoints(
116 constructSaveRestorePoints(SRPoints: SrcMFI.getRestorePoints(), BBMap: Src2DstMBB));
117
118 auto CopyObjectProperties = [](MachineFrameInfo &DstMFI,
119 const MachineFrameInfo &SrcMFI, int FI) {
120 if (SrcMFI.isStatepointSpillSlotObjectIndex(ObjectIdx: FI))
121 DstMFI.markAsStatepointSpillSlotObjectIndex(ObjectIdx: FI);
122 DstMFI.setObjectSSPLayout(ObjectIdx: FI, Kind: SrcMFI.getObjectSSPLayout(ObjectIdx: FI));
123 DstMFI.setObjectZExt(ObjectIdx: FI, IsZExt: SrcMFI.isObjectZExt(ObjectIdx: FI));
124 DstMFI.setObjectSExt(ObjectIdx: FI, IsSExt: SrcMFI.isObjectSExt(ObjectIdx: FI));
125 };
126
127 for (int i = 0, e = SrcMFI.getNumObjects() - SrcMFI.getNumFixedObjects();
128 i != e; ++i) {
129 int NewFI;
130
131 assert(!SrcMFI.isFixedObjectIndex(i));
132 if (SrcMFI.isVariableSizedObjectIndex(ObjectIdx: i)) {
133 NewFI = DstMFI.CreateVariableSizedObject(Alignment: SrcMFI.getObjectAlign(ObjectIdx: i),
134 Alloca: SrcMFI.getObjectAllocation(ObjectIdx: i));
135 } else {
136 NewFI = DstMFI.CreateStackObject(
137 Size: SrcMFI.getObjectSize(ObjectIdx: i), Alignment: SrcMFI.getObjectAlign(ObjectIdx: i),
138 isSpillSlot: SrcMFI.isSpillSlotObjectIndex(ObjectIdx: i), Alloca: SrcMFI.getObjectAllocation(ObjectIdx: i),
139 ID: SrcMFI.getStackID(ObjectIdx: i));
140 DstMFI.setObjectOffset(ObjectIdx: NewFI, SPOffset: SrcMFI.getObjectOffset(ObjectIdx: i));
141 }
142
143 CopyObjectProperties(DstMFI, SrcMFI, i);
144
145 (void)NewFI;
146 assert(i == NewFI && "expected to keep stable frame index numbering");
147 }
148
149 // Copy the fixed frame objects backwards to preserve frame index numbers,
150 // since CreateFixedObject uses front insertion.
151 for (int i = -1; i >= (int)-SrcMFI.getNumFixedObjects(); --i) {
152 assert(SrcMFI.isFixedObjectIndex(i));
153 int NewFI = DstMFI.CreateFixedObject(
154 Size: SrcMFI.getObjectSize(ObjectIdx: i), SPOffset: SrcMFI.getObjectOffset(ObjectIdx: i),
155 IsImmutable: SrcMFI.isImmutableObjectIndex(ObjectIdx: i), isAliased: SrcMFI.isAliasedObjectIndex(ObjectIdx: i));
156 CopyObjectProperties(DstMFI, SrcMFI, i);
157
158 (void)NewFI;
159 assert(i == NewFI && "expected to keep stable frame index numbering");
160 }
161
162 for (unsigned I = 0, E = SrcMFI.getLocalFrameObjectCount(); I < E; ++I) {
163 auto LocalObject = SrcMFI.getLocalFrameObjectMap(i: I);
164 DstMFI.mapLocalFrameObject(ObjectIndex: LocalObject.first, Offset: LocalObject.second);
165 }
166
167 DstMFI.setCalleeSavedInfo(SrcMFI.getCalleeSavedInfo());
168
169 if (SrcMFI.hasStackProtectorIndex()) {
170 DstMFI.setStackProtectorIndex(SrcMFI.getStackProtectorIndex());
171 }
172
173 // FIXME: Needs test, missing MIR serialization.
174 if (SrcMFI.hasFunctionContextIndex()) {
175 DstMFI.setFunctionContextIndex(SrcMFI.getFunctionContextIndex());
176 }
177}
178
179static void cloneJumpTableInfo(
180 MachineFunction &DstMF, const MachineJumpTableInfo &SrcJTI,
181 const DenseMap<MachineBasicBlock *, MachineBasicBlock *> &Src2DstMBB) {
182
183 auto *DstJTI = DstMF.getOrCreateJumpTableInfo(JTEntryKind: SrcJTI.getEntryKind());
184
185 std::vector<MachineBasicBlock *> DstBBs;
186
187 for (const MachineJumpTableEntry &Entry : SrcJTI.getJumpTables()) {
188 for (MachineBasicBlock *X : Entry.MBBs)
189 DstBBs.push_back(x: Src2DstMBB.find(Val: X)->second);
190
191 DstJTI->createJumpTableIndex(DestBBs: DstBBs);
192 DstBBs.clear();
193 }
194}
195
196static void cloneMemOperands(MachineInstr &DstMI, MachineInstr &SrcMI,
197 MachineFunction &SrcMF, MachineFunction &DstMF) {
198 // The new MachineMemOperands should be owned by the new function's
199 // Allocator.
200 PseudoSourceValueManager &PSVMgr = DstMF.getPSVManager();
201
202 // We also need to remap the PseudoSourceValues from the new function's
203 // PseudoSourceValueManager.
204 SmallVector<MachineMemOperand *, 2> NewMMOs;
205 for (MachineMemOperand *OldMMO : SrcMI.memoperands()) {
206 MachinePointerInfo NewPtrInfo(OldMMO->getPointerInfo());
207 if (const PseudoSourceValue *PSV =
208 dyn_cast_if_present<const PseudoSourceValue *>(Val&: NewPtrInfo.V)) {
209 switch (PSV->kind()) {
210 case PseudoSourceValue::Stack:
211 NewPtrInfo.V = PSVMgr.getStack();
212 break;
213 case PseudoSourceValue::GOT:
214 NewPtrInfo.V = PSVMgr.getGOT();
215 break;
216 case PseudoSourceValue::JumpTable:
217 NewPtrInfo.V = PSVMgr.getJumpTable();
218 break;
219 case PseudoSourceValue::ConstantPool:
220 NewPtrInfo.V = PSVMgr.getConstantPool();
221 break;
222 case PseudoSourceValue::FixedStack:
223 NewPtrInfo.V = PSVMgr.getFixedStack(
224 FI: cast<FixedStackPseudoSourceValue>(Val: PSV)->getFrameIndex());
225 break;
226 case PseudoSourceValue::GlobalValueCallEntry:
227 NewPtrInfo.V = PSVMgr.getGlobalValueCallEntry(
228 GV: cast<GlobalValuePseudoSourceValue>(Val: PSV)->getValue());
229 break;
230 case PseudoSourceValue::ExternalSymbolCallEntry:
231 NewPtrInfo.V = PSVMgr.getExternalSymbolCallEntry(
232 ES: cast<ExternalSymbolPseudoSourceValue>(Val: PSV)->getSymbol());
233 break;
234 case PseudoSourceValue::TargetCustom:
235 default:
236 // FIXME: We have no generic interface for allocating custom PSVs.
237 report_fatal_error(reason: "Cloning TargetCustom PSV not handled");
238 }
239 }
240
241 MachineMemOperand *NewMMO = DstMF.getMachineMemOperand(
242 PtrInfo: NewPtrInfo, F: OldMMO->getFlags(), MemTy: OldMMO->getMemoryType(),
243 BaseAlignment: OldMMO->getBaseAlign(),
244 Metadata: MMOMetadata(OldMMO->getAAInfo(), OldMMO->getRanges(),
245 /*MemCacheHint=*/nullptr),
246 SSID: OldMMO->getSyncScopeID(), Ordering: OldMMO->getSuccessOrdering(),
247 FailureOrdering: OldMMO->getFailureOrdering());
248 NewMMOs.push_back(Elt: NewMMO);
249 }
250
251 DstMI.setMemRefs(MF&: DstMF, MemRefs: NewMMOs);
252}
253
254static std::unique_ptr<MachineFunction> cloneMF(MachineFunction *SrcMF,
255 MachineModuleInfo &DestMMI) {
256 auto DstMF = std::make_unique<MachineFunction>(
257 args&: SrcMF->getFunction(), args: SrcMF->getTarget(), args: SrcMF->getSubtarget(),
258 args&: SrcMF->getContext(), args: SrcMF->getFunctionNumber());
259 DenseMap<MachineBasicBlock *, MachineBasicBlock *> Src2DstMBB;
260
261 auto *SrcMRI = &SrcMF->getRegInfo();
262 auto *DstMRI = &DstMF->getRegInfo();
263
264 // Clone blocks.
265 for (MachineBasicBlock &SrcMBB : *SrcMF) {
266 MachineBasicBlock *DstMBB =
267 DstMF->CreateMachineBasicBlock(BB: SrcMBB.getBasicBlock());
268 Src2DstMBB[&SrcMBB] = DstMBB;
269
270 DstMBB->setCallFrameSize(SrcMBB.getCallFrameSize());
271
272 if (SrcMBB.isIRBlockAddressTaken())
273 DstMBB->setAddressTakenIRBlock(SrcMBB.getAddressTakenIRBlock());
274 if (SrcMBB.isMachineBlockAddressTaken())
275 DstMBB->setMachineBlockAddressTaken();
276
277 // FIXME: This is not serialized
278 if (SrcMBB.hasLabelMustBeEmitted())
279 DstMBB->setLabelMustBeEmitted();
280
281 DstMBB->setAlignment(SrcMBB.getAlignment());
282
283 // FIXME: This is not serialized
284 DstMBB->setMaxBytesForAlignment(SrcMBB.getMaxBytesForAlignment());
285
286 DstMBB->setIsEHPad(SrcMBB.isEHPad());
287 DstMBB->setIsEHScopeEntry(SrcMBB.isEHScopeEntry());
288 DstMBB->setIsEHContTarget(SrcMBB.isEHContTarget());
289 DstMBB->setIsEHFuncletEntry(SrcMBB.isEHFuncletEntry());
290
291 // FIXME: These are not serialized
292 DstMBB->setIsCleanupFuncletEntry(SrcMBB.isCleanupFuncletEntry());
293 DstMBB->setIsBeginSection(SrcMBB.isBeginSection());
294 DstMBB->setIsEndSection(SrcMBB.isEndSection());
295
296 DstMBB->setSectionID(SrcMBB.getSectionID());
297 DstMBB->setIsInlineAsmBrIndirectTarget(
298 SrcMBB.isInlineAsmBrIndirectTarget());
299
300 // FIXME: This is not serialized
301 if (std::optional<uint64_t> Weight = SrcMBB.getIrrLoopHeaderWeight())
302 DstMBB->setIrrLoopHeaderWeight(*Weight);
303 }
304
305 const MachineFrameInfo &SrcMFI = SrcMF->getFrameInfo();
306 MachineFrameInfo &DstMFI = DstMF->getFrameInfo();
307
308 // Copy stack objects and other info
309 cloneFrameInfo(DstMFI, SrcMFI, Src2DstMBB);
310
311 if (MachineJumpTableInfo *SrcJTI = SrcMF->getJumpTableInfo()) {
312 cloneJumpTableInfo(DstMF&: *DstMF, SrcJTI: *SrcJTI, Src2DstMBB);
313 }
314
315 // Remap the debug info frame index references.
316 DstMF->VariableDbgInfos = SrcMF->VariableDbgInfos;
317
318 // Clone virtual registers
319 for (unsigned I = 0, E = SrcMRI->getNumVirtRegs(); I != E; ++I) {
320 Register Reg = Register::index2VirtReg(Index: I);
321 Register NewReg = DstMRI->createIncompleteVirtualRegister(
322 Name: SrcMRI->getVRegName(Reg));
323 assert(NewReg == Reg && "expected to preserve virtreg number");
324
325 DstMRI->setRegClassOrRegBank(Reg: NewReg, RCOrRB: SrcMRI->getRegClassOrRegBank(Reg));
326
327 LLT RegTy = SrcMRI->getType(Reg);
328 if (RegTy.isValid())
329 DstMRI->setType(VReg: NewReg, Ty: RegTy);
330
331 // Copy register allocation hints.
332 const auto *Hints = SrcMRI->getRegAllocationHints(VReg: Reg);
333 if (Hints)
334 for (Register PrefReg : Hints->second)
335 DstMRI->addRegAllocationHint(VReg: NewReg, PrefReg);
336 }
337
338 const TargetSubtargetInfo &STI = DstMF->getSubtarget();
339 const TargetInstrInfo *TII = STI.getInstrInfo();
340 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
341
342 // Link blocks.
343 for (auto &SrcMBB : *SrcMF) {
344 auto *DstMBB = Src2DstMBB[&SrcMBB];
345 DstMF->push_back(MBB: DstMBB);
346
347 for (auto It = SrcMBB.succ_begin(), IterEnd = SrcMBB.succ_end();
348 It != IterEnd; ++It) {
349 auto *SrcSuccMBB = *It;
350 auto *DstSuccMBB = Src2DstMBB[SrcSuccMBB];
351 DstMBB->addSuccessor(Succ: DstSuccMBB, Prob: SrcMBB.getSuccProbability(Succ: It));
352 }
353
354 for (auto &LI : SrcMBB.liveins_dbg())
355 DstMBB->addLiveIn(RegMaskPair: LI);
356
357 // Make sure MRI knows about registers clobbered by unwinder.
358 if (DstMBB->isEHPad()) {
359 if (auto *RegMask = TRI->getCustomEHPadPreservedMask(MF: *DstMF))
360 DstMRI->addPhysRegsUsedFromRegMask(RegMask);
361 }
362 }
363
364 // Track predefined/named regmasks which we ignore.
365 DenseSet<const uint32_t *> ConstRegisterMasks(llvm::from_range,
366 TRI->getRegMasks());
367
368 // Clone instructions.
369 for (auto &SrcMBB : *SrcMF) {
370 auto *DstMBB = Src2DstMBB[&SrcMBB];
371 for (auto &SrcMI : SrcMBB) {
372 const auto &MCID = TII->get(Opcode: SrcMI.getOpcode());
373 auto *DstMI = DstMF->CreateMachineInstr(MCID, DL: SrcMI.getDebugLoc(),
374 /*NoImplicit=*/true);
375 DstMI->setFlags(SrcMI.getFlags());
376 DstMI->setAsmPrinterFlag(SrcMI.getAsmPrinterFlags());
377
378 DstMBB->push_back(MI: DstMI);
379 for (auto &SrcMO : SrcMI.operands()) {
380 MachineOperand DstMO(SrcMO);
381 DstMO.clearParent();
382
383 // Update MBB.
384 if (DstMO.isMBB())
385 DstMO.setMBB(Src2DstMBB[DstMO.getMBB()]);
386 else if (DstMO.isRegMask()) {
387 DstMRI->addPhysRegsUsedFromRegMask(RegMask: DstMO.getRegMask());
388
389 if (!ConstRegisterMasks.count(V: DstMO.getRegMask())) {
390 uint32_t *DstMask = DstMF->allocateRegMask();
391 std::memcpy(dest: DstMask, src: SrcMO.getRegMask(),
392 n: sizeof(*DstMask) *
393 MachineOperand::getRegMaskSize(NumRegs: TRI->getNumRegs()));
394 DstMO.setRegMask(DstMask);
395 }
396 }
397
398 DstMI->addOperand(Op: DstMO);
399 }
400
401 cloneMemOperands(DstMI&: *DstMI, SrcMI, SrcMF&: *SrcMF, DstMF&: *DstMF);
402 }
403 }
404
405 DstMF->setAlignment(SrcMF->getAlignment());
406 DstMF->setExposesReturnsTwice(SrcMF->exposesReturnsTwice());
407 DstMF->setHasInlineAsm(SrcMF->hasInlineAsm());
408 DstMF->setHasWinCFI(SrcMF->hasWinCFI());
409
410 DstMF->getProperties().reset().set(SrcMF->getProperties());
411
412 if (!SrcMF->getFrameInstructions().empty() ||
413 !SrcMF->getLongjmpTargets().empty() || !SrcMF->getEHContTargets().empty())
414 report_fatal_error(reason: "cloning not implemented for machine function property");
415
416 DstMF->setCallsEHReturn(SrcMF->callsEHReturn());
417 DstMF->setCallsUnwindInit(SrcMF->callsUnwindInit());
418 DstMF->setHasEHContTarget(SrcMF->hasEHContTarget());
419 DstMF->setHasEHScopes(SrcMF->hasEHScopes());
420 DstMF->setHasEHFunclets(SrcMF->hasEHFunclets());
421 DstMF->setHasFakeUses(SrcMF->hasFakeUses());
422 DstMF->setIsOutlined(SrcMF->isOutlined());
423
424 if (!SrcMF->getLandingPads().empty() ||
425 !SrcMF->getCodeViewAnnotations().empty() ||
426 !SrcMF->getTypeInfos().empty() ||
427 !SrcMF->getFilterIds().empty() ||
428 SrcMF->hasAnyWasmLandingPadIndex() ||
429 SrcMF->hasAnyCallSiteLandingPad() ||
430 SrcMF->hasAnyCallSiteLabel() ||
431 !SrcMF->getCallSitesInfo().empty())
432 report_fatal_error(reason: "cloning not implemented for machine function property");
433
434 DstMF->setDebugInstrNumberingCount(SrcMF->DebugInstrNumberingCount);
435
436 if (!DstMF->cloneInfoFrom(OrigMF: *SrcMF, Src2DstMBB))
437 report_fatal_error(reason: "target does not implement MachineFunctionInfo cloning");
438
439 DstMRI->freezeReservedRegs();
440
441 DstMF->verify(p: nullptr, Banner: "", OS: &errs(), /*AbortOnError=*/true);
442 return DstMF;
443}
444
445void ReducerWorkItem::print(raw_ostream &ROS, void *p) const {
446 if (MMI) {
447 M->renumberMetadataForAssembly();
448 printMIR(OS&: ROS, M: *M);
449 for (Function &F : *M) {
450 if (auto *MF = MMI->getMachineFunction(F)) {
451 MachineModuleSlotTracker MST(
452 [&](const Function &F) { return MMI->getMachineFunction(F); }, MF);
453 MST.renumberMetadataForAssembly();
454 printMIR(OS&: ROS, MMI: *MMI, MF: *MF);
455 }
456 }
457 } else {
458 M->renumberMetadataForAssembly();
459 M->print(OS&: ROS, /*AssemblyAnnotationWriter=*/AAW: nullptr,
460 /*ShouldPreserveUseListOrder=*/true);
461 }
462}
463
464bool ReducerWorkItem::verify(raw_fd_ostream *OS) const {
465 if (verifyModule(M: *M, OS))
466 return true;
467
468 if (!MMI)
469 return false;
470
471 for (const Function &F : getModule()) {
472 if (const MachineFunction *MF = MMI->getMachineFunction(F)) {
473 // With the current state of quality, most reduction attempts fail the
474 // machine verifier. Avoid spamming large function dumps on nearly every
475 // attempt until the situation is better.
476 if (!MF->verify(p: nullptr, Banner: "",
477 /*OS=*/PrintInvalidMachineReductions ? &errs() : nullptr,
478 /*AbortOnError=*/false)) {
479
480 if (!PrintInvalidMachineReductions) {
481 WithColor::warning(OS&: errs())
482 << "reduction attempt on function '" << MF->getName()
483 << "' failed machine verifier (debug with "
484 "-print-invalid-reduction-machine-verifier-errors)\n";
485 }
486 return true;
487 }
488 }
489 }
490
491 return false;
492}
493
494bool ReducerWorkItem::isReduced(const TestRunner &Test) const {
495 const bool UseBitcode = Test.inputIsBitcode() || TmpFilesAsBitcode;
496
497 SmallString<128> CurrentFilepath;
498
499 // Write ReducerWorkItem to tmp file
500 int FD;
501 std::error_code EC = sys::fs::createTemporaryFile(
502 Prefix: "llvm-reduce", Suffix: isMIR() ? "mir" : (UseBitcode ? "bc" : "ll"), ResultFD&: FD,
503 ResultPath&: CurrentFilepath,
504 Flags: UseBitcode && !isMIR() ? sys::fs::OF_None : sys::fs::OF_Text);
505 if (EC) {
506 WithColor::error(OS&: errs(), Prefix: Test.getToolName())
507 << "error making unique filename: " << EC.message() << '\n';
508 exit(status: 1);
509 }
510
511 ToolOutputFile Out(CurrentFilepath, FD);
512
513 writeOutput(OS&: Out.os(), EmitBitcode: UseBitcode);
514
515 Out.os().close();
516 if (Out.os().has_error()) {
517 WithColor::error(OS&: errs(), Prefix: Test.getToolName())
518 << "error emitting bitcode to file '" << CurrentFilepath
519 << "': " << Out.os().error().message() << '\n';
520 exit(status: 1);
521 }
522
523 // Current Chunks aren't interesting
524 return Test.run(Filename: CurrentFilepath);
525}
526
527std::unique_ptr<ReducerWorkItem>
528ReducerWorkItem::clone(const TargetMachine *TM) const {
529 auto CloneMMM = std::make_unique<ReducerWorkItem>();
530 if (TM) {
531 // We're assuming the Module IR contents are always unchanged by MIR
532 // reductions, and can share it as a constant.
533 CloneMMM->M = M;
534
535 // MachineModuleInfo contains a lot of other state used during codegen which
536 // we won't be using here, but we should be able to ignore it (although this
537 // is pretty ugly).
538 CloneMMM->MMI = std::make_unique<MachineModuleInfo>(args&: TM);
539
540 for (const Function &F : getModule()) {
541 if (auto *MF = MMI->getMachineFunction(F))
542 CloneMMM->MMI->insertFunction(F, MF: cloneMF(SrcMF: MF, DestMMI&: *CloneMMM->MMI));
543 }
544 } else {
545 CloneMMM->M = CloneModule(M: *M);
546 }
547 return CloneMMM;
548}
549
550/// Try to produce some number that indicates a function is getting smaller /
551/// simpler.
552static uint64_t computeMIRComplexityScoreImpl(const MachineFunction &MF) {
553 uint64_t Score = 0;
554 const MachineFrameInfo &MFI = MF.getFrameInfo();
555
556 // Add for stack objects
557 Score += MFI.getNumObjects();
558
559 // Add in the block count.
560 Score += 2 * MF.size();
561
562 const MachineRegisterInfo &MRI = MF.getRegInfo();
563 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
564 Register Reg = Register::index2VirtReg(Index: I);
565 if (const auto *Hints = MRI.getRegAllocationHints(VReg: Reg))
566 Score += Hints->second.size();
567 }
568
569 for (const MachineBasicBlock &MBB : MF) {
570 for (const MachineInstr &MI : MBB) {
571 const unsigned Opc = MI.getOpcode();
572
573 // Reductions may want or need to introduce implicit_defs, so don't count
574 // them.
575 // TODO: These probably should count in some way.
576 if (Opc == TargetOpcode::IMPLICIT_DEF ||
577 Opc == TargetOpcode::G_IMPLICIT_DEF)
578 continue;
579
580 // Each instruction adds to the score
581 Score += 4;
582
583 if (Opc == TargetOpcode::PHI || Opc == TargetOpcode::G_PHI ||
584 Opc == TargetOpcode::INLINEASM || Opc == TargetOpcode::INLINEASM_BR)
585 ++Score;
586
587 if (MI.getFlags() != 0)
588 ++Score;
589
590 // Increase weight for more operands.
591 for (const MachineOperand &MO : MI.operands()) {
592 ++Score;
593
594 // Treat registers as more complex.
595 if (MO.isReg()) {
596 ++Score;
597
598 // And subregisters as even more complex.
599 if (MO.getSubReg()) {
600 ++Score;
601 if (MO.isDef())
602 ++Score;
603 }
604 } else if (MO.isRegMask())
605 ++Score;
606 }
607 }
608 }
609
610 return Score;
611}
612
613uint64_t ReducerWorkItem::computeMIRComplexityScore() const {
614 uint64_t Score = 0;
615
616 for (const Function &F : getModule()) {
617 if (auto *MF = MMI->getMachineFunction(F))
618 Score += computeMIRComplexityScoreImpl(MF: *MF);
619 }
620
621 return Score;
622}
623
624// FIXME: ReduceOperandsSkip has similar function, except it uses larger numbers
625// for more reduced.
626static unsigned classifyReductivePower(const Value *V) {
627 if (auto *C = dyn_cast<ConstantData>(Val: V)) {
628 if (C->isNullValue())
629 return 0;
630 if (C->isOneValue())
631 return 1;
632 if (isa<UndefValue>(Val: V))
633 return 2;
634 return 3;
635 }
636
637 if (isa<GlobalValue>(Val: V))
638 return 4;
639
640 // TODO: Account for expression size
641 if (isa<ConstantExpr>(Val: V))
642 return 5;
643
644 if (isa<Constant>(Val: V))
645 return 1;
646
647 if (isa<Argument>(Val: V))
648 return 6;
649
650 if (isa<Instruction>(Val: V))
651 return 7;
652
653 return 0;
654}
655
656// TODO: Additional flags and attributes may be complexity reducing. If we start
657// adding flags and attributes, they could have negative cost.
658static uint64_t computeIRComplexityScoreImpl(const Function &F) {
659 uint64_t Score = 1; // Count the function itself
660 SmallVector<std::pair<unsigned, MDNode *>> MDs;
661
662 AttributeList Attrs = F.getAttributes();
663 for (AttributeSet AttrSet : Attrs)
664 Score += AttrSet.getNumAttributes();
665
666 for (const BasicBlock &BB : F) {
667 ++Score;
668
669 for (const Instruction &I : BB) {
670 ++Score;
671
672 if (const auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(Val: &I)) {
673 if (OverflowOp->hasNoUnsignedWrap())
674 ++Score;
675 if (OverflowOp->hasNoSignedWrap())
676 ++Score;
677 } else if (const auto *Trunc = dyn_cast<TruncInst>(Val: &I)) {
678 if (Trunc->hasNoSignedWrap())
679 ++Score;
680 if (Trunc->hasNoUnsignedWrap())
681 ++Score;
682 } else if (const auto *ExactOp = dyn_cast<PossiblyExactOperator>(Val: &I)) {
683 if (ExactOp->isExact())
684 ++Score;
685 } else if (const auto *NNI = dyn_cast<PossiblyNonNegInst>(Val: &I)) {
686 if (NNI->hasNonNeg())
687 ++Score;
688 } else if (const auto *PDI = dyn_cast<PossiblyDisjointInst>(Val: &I)) {
689 if (PDI->isDisjoint())
690 ++Score;
691 } else if (const auto *ASC = dyn_cast<AddrSpaceCastInst>(Val: &I)) {
692 if (ASC->hasNonNull())
693 ++Score;
694 } else if (const auto *GEP = dyn_cast<GEPOperator>(Val: &I)) {
695 if (GEP->isInBounds())
696 ++Score;
697 if (GEP->hasNoUnsignedSignedWrap())
698 ++Score;
699 if (GEP->hasNoUnsignedWrap())
700 ++Score;
701 } else if (const auto *FPOp = dyn_cast<FPMathOperator>(Val: &I)) {
702 FastMathFlags FMF = FPOp->getFastMathFlags();
703 if (FMF.allowReassoc())
704 ++Score;
705 if (FMF.noNaNs())
706 ++Score;
707 if (FMF.noInfs())
708 ++Score;
709 if (FMF.noSignedZeros())
710 ++Score;
711 if (FMF.allowReciprocal())
712 ++Score;
713 if (FMF.allowContract())
714 ++Score;
715 if (FMF.approxFunc())
716 ++Score;
717 }
718
719 for (const Value *Operand : I.operands()) {
720 ++Score;
721 Score += classifyReductivePower(V: Operand);
722 }
723
724 I.getAllMetadata(MDs);
725 Score += MDs.size();
726 MDs.clear();
727 }
728 }
729
730 return Score;
731}
732
733uint64_t ReducerWorkItem::computeIRComplexityScore() const {
734 uint64_t Score = 0;
735
736 const Module &M = getModule();
737 Score += M.named_metadata_size();
738
739 SmallVector<std::pair<unsigned, MDNode *>, 32> GlobalMetadata;
740 for (const GlobalVariable &GV : M.globals()) {
741 ++Score;
742
743 if (GV.hasInitializer())
744 Score += classifyReductivePower(V: GV.getInitializer());
745
746 // TODO: Account for linkage?
747
748 GV.getAllMetadata(MDs&: GlobalMetadata);
749 Score += GlobalMetadata.size();
750 GlobalMetadata.clear();
751 }
752
753 for (const GlobalAlias &GA : M.aliases())
754 Score += classifyReductivePower(V: GA.getAliasee());
755
756 for (const GlobalIFunc &GI : M.ifuncs())
757 Score += classifyReductivePower(V: GI.getResolver());
758
759 for (const Function &F : M)
760 Score += computeIRComplexityScoreImpl(F);
761
762 return Score;
763}
764
765void ReducerWorkItem::writeOutput(raw_ostream &OS, bool EmitBitcode) const {
766 // Requesting bitcode emission with mir is nonsense, so just ignore it.
767 if (EmitBitcode && !isMIR())
768 writeBitcode(OutStream&: OS);
769 else
770 print(ROS&: OS, /*AnnotationWriter=*/p: nullptr);
771}
772
773void ReducerWorkItem::readBitcode(MemoryBufferRef Data, LLVMContext &Ctx,
774 StringRef ToolName) {
775 Expected<BitcodeFileContents> IF = llvm::getBitcodeFileContents(Buffer: Data);
776 if (!IF) {
777 WithColor::error(OS&: errs(), Prefix: ToolName) << IF.takeError();
778 exit(status: 1);
779 }
780
781 BitcodeModule BM = IF->Mods[0];
782 Expected<BitcodeLTOInfo> LI = BM.getLTOInfo();
783 if (!LI) {
784 WithColor::error(OS&: errs(), Prefix: ToolName) << LI.takeError();
785 exit(status: 1);
786 }
787
788 Expected<std::unique_ptr<Module>> MOrErr = BM.parseModule(Context&: Ctx);
789 if (!MOrErr) {
790 WithColor::error(OS&: errs(), Prefix: ToolName) << MOrErr.takeError();
791 exit(status: 1);
792 }
793
794 LTOInfo = std::make_unique<BitcodeLTOInfo>(args&: *LI);
795 M = std::move(MOrErr.get());
796}
797
798void ReducerWorkItem::writeBitcode(raw_ostream &OutStream) const {
799 const bool ShouldPreserveUseListOrder = true;
800
801 if (LTOInfo && LTOInfo->IsThinLTO && LTOInfo->EnableSplitLTOUnit) {
802 PassBuilder PB;
803 LoopAnalysisManager LAM;
804 FunctionAnalysisManager FAM;
805 CGSCCAnalysisManager CGAM;
806 ModuleAnalysisManager MAM;
807 PB.registerModuleAnalyses(MAM);
808 PB.registerCGSCCAnalyses(CGAM);
809 PB.registerFunctionAnalyses(FAM);
810 PB.registerLoopAnalyses(LAM);
811 PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
812 ModulePassManager MPM;
813 MPM.addPass(Pass: ThinLTOBitcodeWriterPass(OutStream, nullptr,
814 ShouldPreserveUseListOrder));
815 MPM.run(IR&: *M, AM&: MAM);
816 } else {
817 std::unique_ptr<ModuleSummaryIndex> Index;
818 if (LTOInfo && LTOInfo->HasSummary) {
819 ProfileSummaryInfo PSI(*M);
820 Index = std::make_unique<ModuleSummaryIndex>(
821 args: buildModuleSummaryIndex(M: *M, GetBFICallback: nullptr, PSI: &PSI));
822 }
823 WriteBitcodeToFile(M: getModule(), Out&: OutStream, ShouldPreserveUseListOrder,
824 Index: Index.get());
825 }
826}
827
828std::pair<std::unique_ptr<ReducerWorkItem>, bool>
829llvm::parseReducerWorkItem(StringRef ToolName, StringRef Filename,
830 LLVMContext &Ctxt,
831 std::unique_ptr<TargetMachine> &TM, bool IsMIR) {
832 bool IsBitcode = false;
833 Triple TheTriple;
834
835 auto MMM = std::make_unique<ReducerWorkItem>();
836
837 if (IsMIR) {
838 auto FileOrErr = MemoryBuffer::getFileOrSTDIN(Filename, /*IsText=*/true);
839 if (std::error_code EC = FileOrErr.getError()) {
840 WithColor::error(OS&: errs(), Prefix: ToolName) << EC.message() << '\n';
841 return {nullptr, false};
842 }
843
844 std::unique_ptr<MIRParser> MParser =
845 createMIRParser(Contents: std::move(FileOrErr.get()), Context&: Ctxt);
846
847 auto SetDataLayout = [&](StringRef DataLayoutTargetTriple,
848 StringRef OldDLStr) -> std::optional<std::string> {
849 // NB: We always call createTargetMachineForTriple() even if an explicit
850 // DataLayout is already set in the module since we want to use this
851 // callback to setup the TargetMachine rather than doing it later.
852 std::string IRTargetTriple = DataLayoutTargetTriple.str();
853 if (!TargetTriple.empty())
854 IRTargetTriple = Triple::normalize(Str: TargetTriple);
855 TheTriple = Triple(IRTargetTriple);
856 if (TheTriple.getTriple().empty())
857 TheTriple.setTriple(sys::getDefaultTargetTriple());
858 ExitOnError ExitOnErr(std::string(ToolName) + ": error: ");
859 TM = ExitOnErr(codegen::createTargetMachineForTriple(TargetTriple: TheTriple));
860
861 return TheTriple.computeDataLayout();
862 };
863
864 std::unique_ptr<Module> M = MParser->parseIRModule(DataLayoutCallback: SetDataLayout);
865
866 if (!TheTriple.empty())
867 M->setTargetTriple(TheTriple);
868
869 MMM->MMI = std::make_unique<MachineModuleInfo>(args: TM.get());
870 MParser->parseMachineFunctions(M&: *M, MMI&: *MMM->MMI);
871 MMM->M = std::move(M);
872 } else {
873 SMDiagnostic Err;
874 ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
875 MemoryBuffer::getFileOrSTDIN(Filename);
876 if (std::error_code EC = MB.getError()) {
877 WithColor::error(OS&: errs(), Prefix: ToolName)
878 << Filename << ": " << EC.message() << "\n";
879 return {nullptr, false};
880 }
881
882 if (!isBitcode(BufPtr: (const unsigned char *)(*MB)->getBufferStart(),
883 BufEnd: (const unsigned char *)(*MB)->getBufferEnd())) {
884 std::unique_ptr<Module> Result = parseIR(Buffer: **MB, Err, Context&: Ctxt);
885 if (!Result) {
886 Err.print(ProgName: ToolName.data(), S&: errs());
887 return {nullptr, false};
888 }
889 MMM->M = std::move(Result);
890 } else {
891 IsBitcode = true;
892 MMM->readBitcode(Data: MemoryBufferRef(**MB), Ctx&: Ctxt, ToolName);
893 }
894
895 if (MMM->LTOInfo)
896 AssignGUIDPass::runOnModule(M&: MMM->getModule());
897 }
898 if (MMM->verify(OS: &errs())) {
899 WithColor::error(OS&: errs(), Prefix: ToolName)
900 << Filename << " - input module is broken!\n";
901 return {nullptr, false};
902 }
903 return {std::move(MMM), IsBitcode};
904}
905