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