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