/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

Bug Summary

File:	build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
Warning:	line 401, column 60 Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name Legalizer.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/CodeGen/GlobalISel -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/GlobalISel -I include -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-15/lib/clang/15.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-04-20-140412-16051-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

→

1//===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
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/// \file This file implements the LegalizerHelper class to legalize individual
10/// instructions and the LegalizePass wrapper pass for the primary
11/// legalization.
12//
13//===----------------------------------------------------------------------===//
14 
15#include "llvm/CodeGen/GlobalISel/Legalizer.h"
16#include "llvm/ADT/PostOrderIterator.h"
17#include "llvm/Analysis/OptimizationRemarkEmitter.h"
18#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
19#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
20#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
21#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
22#include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
23#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
24#include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
25#include "llvm/CodeGen/GlobalISel/Utils.h"
26#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
27#include "llvm/CodeGen/TargetPassConfig.h"
28#include "llvm/CodeGen/TargetSubtargetInfo.h"
29#include "llvm/InitializePasses.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Support/Error.h"
32 
33#define DEBUG_TYPE"legalizer" "legalizer"
34 
35using namespace llvm;
36 
37static cl::opt<bool>
38    EnableCSEInLegalizer("enable-cse-in-legalizer",
39                         cl::desc("Should enable CSE in Legalizer"),
40                         cl::Optional, cl::init(false));
41 
42// This is a temporary hack, should be removed soon.
43static cl::opt<bool> AllowGInsertAsArtifact(
44    "allow-ginsert-as-artifact",
45    cl::desc("Allow G_INSERT to be considered an artifact. Hack around AMDGPU "
46             "test infinite loops."),
47    cl::Optional, cl::init(true));
48 
49enum class DebugLocVerifyLevel {
50  None,
51  Legalizations,
52  LegalizationsAndArtifactCombiners,
53};
54#ifndef NDEBUG
55static cl::opt<DebugLocVerifyLevel> VerifyDebugLocs(
56    "verify-legalizer-debug-locs",
57    cl::desc("Verify that debug locations are handled"),
58    cl::values(
59        clEnumValN(DebugLocVerifyLevel::None, "none", "No verification")llvm::cl::OptionEnumValue { "none", int(DebugLocVerifyLevel::
None), "No verification" },
60        clEnumValN(DebugLocVerifyLevel::Legalizations, "legalizations",llvm::cl::OptionEnumValue { "legalizations", int(DebugLocVerifyLevel
::Legalizations), "Verify legalizations" }
61                   "Verify legalizations")llvm::cl::OptionEnumValue { "legalizations", int(DebugLocVerifyLevel
::Legalizations), "Verify legalizations" },
62        clEnumValN(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners,llvm::cl::OptionEnumValue { "legalizations+artifactcombiners"
, int(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners)
, "Verify legalizations and artifact combines" }
63                   "legalizations+artifactcombiners",llvm::cl::OptionEnumValue { "legalizations+artifactcombiners"
, int(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners)
, "Verify legalizations and artifact combines" }
64                   "Verify legalizations and artifact combines")llvm::cl::OptionEnumValue { "legalizations+artifactcombiners"
, int(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners)
, "Verify legalizations and artifact combines" }),
65    cl::init(DebugLocVerifyLevel::Legalizations));
66#else
67// Always disable it for release builds by preventing the observer from being
68// installed.
69static const DebugLocVerifyLevel VerifyDebugLocs = DebugLocVerifyLevel::None;
70#endif
71 
72char Legalizer::ID = 0;
73INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,static void *initializeLegalizerPassOnce(PassRegistry &Registry
) {
74                      "Legalize the Machine IR a function's Machine IR", false,static void *initializeLegalizerPassOnce(PassRegistry &Registry
) {
75                      false)static void *initializeLegalizerPassOnce(PassRegistry &Registry
) {
76INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)initializeTargetPassConfigPass(Registry);
77INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)initializeGISelCSEAnalysisWrapperPassPass(Registry);
78INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Legalize the Machine IR a function's Machine IR"
, "legalizer", &Legalizer::ID, PassInfo::NormalCtor_t(callDefaultCtor
<Legalizer>), false, false); Registry.registerPass(*PI,
 true); return PI; } static llvm::once_flag InitializeLegalizerPassFlag
; void llvm::initializeLegalizerPass(PassRegistry &Registry
) { llvm::call_once(InitializeLegalizerPassFlag, initializeLegalizerPassOnce
, std::ref(Registry)); }
79                    "Legalize the Machine IR a function's Machine IR", false,PassInfo *PI = new PassInfo( "Legalize the Machine IR a function's Machine IR"
, "legalizer", &Legalizer::ID, PassInfo::NormalCtor_t(callDefaultCtor
<Legalizer>), false, false); Registry.registerPass(*PI,
 true); return PI; } static llvm::once_flag InitializeLegalizerPassFlag
; void llvm::initializeLegalizerPass(PassRegistry &Registry
) { llvm::call_once(InitializeLegalizerPassFlag, initializeLegalizerPassOnce
, std::ref(Registry)); }
80                    false)PassInfo *PI = new PassInfo( "Legalize the Machine IR a function's Machine IR"
, "legalizer", &Legalizer::ID, PassInfo::NormalCtor_t(callDefaultCtor
<Legalizer>), false, false); Registry.registerPass(*PI,
 true); return PI; } static llvm::once_flag InitializeLegalizerPassFlag
; void llvm::initializeLegalizerPass(PassRegistry &Registry
) { llvm::call_once(InitializeLegalizerPassFlag, initializeLegalizerPassOnce
, std::ref(Registry)); }
81 
82Legalizer::Legalizer() : MachineFunctionPass(ID) { }
83 
84void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
85  AU.addRequired<TargetPassConfig>();
86  AU.addRequired<GISelCSEAnalysisWrapperPass>();
87  AU.addPreserved<GISelCSEAnalysisWrapperPass>();
88  getSelectionDAGFallbackAnalysisUsage(AU);
89  MachineFunctionPass::getAnalysisUsage(AU);
90}
91 
92void Legalizer::init(MachineFunction &MF) {
93}
94 
95static bool isArtifact(const MachineInstr &MI) {
96  switch (MI.getOpcode()) {
97  default:
98    return false;
99  case TargetOpcode::G_TRUNC:
100  case TargetOpcode::G_ZEXT:
101  case TargetOpcode::G_ANYEXT:
102  case TargetOpcode::G_SEXT:
103  case TargetOpcode::G_MERGE_VALUES:
104  case TargetOpcode::G_UNMERGE_VALUES:
105  case TargetOpcode::G_CONCAT_VECTORS:
106  case TargetOpcode::G_BUILD_VECTOR:
107  case TargetOpcode::G_EXTRACT:
108    return true;
109  case TargetOpcode::G_INSERT:
110    return AllowGInsertAsArtifact;
111  }
112}
113using InstListTy = GISelWorkList<256>;
114using ArtifactListTy = GISelWorkList<128>;
115 
116namespace {
117class LegalizerWorkListManager : public GISelChangeObserver {
118  InstListTy &InstList;
119  ArtifactListTy &ArtifactList;
120#ifndef NDEBUG
121  SmallVector<MachineInstr *, 4> NewMIs;
122#endif
123 
124public:
125  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
126      : InstList(Insts), ArtifactList(Arts) {}
127 
128  void createdOrChangedInstr(MachineInstr &MI) {
129    // Only legalize pre-isel generic instructions.
130    // Legalization process could generate Target specific pseudo
131    // instructions with generic types. Don't record them
132    if (isPreISelGenericOpcode(MI.getOpcode())) {
133      if (isArtifact(MI))
134        ArtifactList.insert(&MI);
135      else
136        InstList.insert(&MI);
137    }
138  }
139 
140  void createdInstr(MachineInstr &MI) override {
141    LLVM_DEBUG(NewMIs.push_back(&MI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { NewMIs.push_back(&MI); } } while (false);
142    createdOrChangedInstr(MI);
143  }
144 
145  void printNewInstrs() {
146    LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { { for (const auto *MI : NewMIs) dbgs() <<
 ".. .. New MI: " << *MI; NewMIs.clear(); }; } } while (
false)
147      for (const auto *MI : NewMIs)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { { for (const auto *MI : NewMIs) dbgs() <<
 ".. .. New MI: " << *MI; NewMIs.clear(); }; } } while (
false)
148        dbgs() << ".. .. New MI: " << *MI;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { { for (const auto *MI : NewMIs) dbgs() <<
 ".. .. New MI: " << *MI; NewMIs.clear(); }; } } while (
false)
149      NewMIs.clear();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { { for (const auto *MI : NewMIs) dbgs() <<
 ".. .. New MI: " << *MI; NewMIs.clear(); }; } } while (
false)
150    })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { { for (const auto *MI : NewMIs) dbgs() <<
 ".. .. New MI: " << *MI; NewMIs.clear(); }; } } while (
false);
151  }
152 
153  void erasingInstr(MachineInstr &MI) override {
154    LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. .. Erasing: " << MI
; } } while (false);
155    InstList.remove(&MI);
156    ArtifactList.remove(&MI);
157  }
158 
159  void changingInstr(MachineInstr &MI) override {
160    LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. .. Changing MI: " <<
 MI; } } while (false);
161  }
162 
163  void changedInstr(MachineInstr &MI) override {
164    // When insts change, we want to revisit them to legalize them again.
165    // We'll consider them the same as created.
166    LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. .. Changed MI: " <<
 MI; } } while (false);
167    createdOrChangedInstr(MI);
168  }
169};
170} // namespace
171 
172Legalizer::MFResult
173Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
174                                   ArrayRef<GISelChangeObserver *> AuxObservers,
175                                   LostDebugLocObserver &LocObserver,
176                                   MachineIRBuilder &MIRBuilder) {
177  MIRBuilder.setMF(MF);
178  MachineRegisterInfo &MRI = MF.getRegInfo();
179 
180  // Populate worklists.
181  InstListTy InstList;
182  ArtifactListTy ArtifactList;
183  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
184  // Perform legalization bottom up so we can DCE as we legalize.
185  // Traverse BB in RPOT and within each basic block, add insts top down,
186  // so when we pop_back_val in the legalization process, we traverse bottom-up.
187  for (auto *MBB : RPOT) {
188    if (MBB->empty())
189      continue;
190    for (MachineInstr &MI : *MBB) {
191      // Only legalize pre-isel generic instructions: others don't have types
192      // and are assumed to be legal.
193      if (!isPreISelGenericOpcode(MI.getOpcode()))
194        continue;
195      if (isArtifact(MI))
196        ArtifactList.deferred_insert(&MI);
197      else
198        InstList.deferred_insert(&MI);
199    }
200  }
201  ArtifactList.finalize();
202  InstList.finalize();
203 
204  // This observer keeps the worklists updated.
205  LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
206  // We want both WorkListObserver as well as all the auxiliary observers (e.g.
207  // CSEInfo) to observe all changes. Use the wrapper observer.
208  GISelObserverWrapper WrapperObserver(&WorkListObserver);
209  for (GISelChangeObserver *Observer : AuxObservers)
12
←
Assuming '__begin1' is equal to '__end1'→
210    WrapperObserver.addObserver(Observer);
211 
212  // Now install the observer as the delegate to MF.
213  // This will keep all the observers notified about new insertions/deletions.
214  RAIIMFObsDelInstaller Installer(MF, WrapperObserver);
215  LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder);
216  LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI);
217  bool Changed = false;
218  SmallVector<MachineInstr *, 128> RetryList;
219  do {
220    LLVM_DEBUG(dbgs() << "=== New Iteration ===\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "=== New Iteration ===\n"; }
 } while (false);
13
←
Assuming 'DebugFlag' is false→
221    assert(RetryList.empty() && "Expected no instructions in RetryList")(static_cast <bool> (RetryList.empty() && "Expected no instructions in RetryList"
) ? void (0) : __assert_fail ("RetryList.empty() && \"Expected no instructions in RetryList\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 221, __extension__
 __PRETTY_FUNCTION__));
14
←
Loop condition is false.  Exiting loop→
15
←
'?' condition is true→
222    unsigned NumArtifacts = ArtifactList.size();
223    while (!InstList.empty()) {
16
←
Assuming the condition is false→
17
←
Loop condition is false. Execution continues on line 259→
224      MachineInstr &MI = *InstList.pop_back_val();
225      assert(isPreISelGenericOpcode(MI.getOpcode()) &&(static_cast <bool> (isPreISelGenericOpcode(MI.getOpcode
()) && "Expecting generic opcode") ? void (0) : __assert_fail
 ("isPreISelGenericOpcode(MI.getOpcode()) && \"Expecting generic opcode\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 226, __extension__
 __PRETTY_FUNCTION__))
226             "Expecting generic opcode")(static_cast <bool> (isPreISelGenericOpcode(MI.getOpcode
()) && "Expecting generic opcode") ? void (0) : __assert_fail
 ("isPreISelGenericOpcode(MI.getOpcode()) && \"Expecting generic opcode\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 226, __extension__
 __PRETTY_FUNCTION__));
227      if (isTriviallyDead(MI, MRI)) {
228        eraseInstr(MI, MRI, &LocObserver);
229        continue;
230      }
231 
232      // Do the legalization for this instruction.
233      auto Res = Helper.legalizeInstrStep(MI, LocObserver);
234      // Error out if we couldn't legalize this instruction. We may want to
235      // fall back to DAG ISel instead in the future.
236      if (Res == LegalizerHelper::UnableToLegalize) {
237        // Move illegal artifacts to RetryList instead of aborting because
238        // legalizing InstList may generate artifacts that allow
239        // ArtifactCombiner to combine away them.
240        if (isArtifact(MI)) {
241          LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Not legalized, moving to artifacts retry\n"
; } } while (false);
242          assert(NumArtifacts == 0 &&(static_cast <bool> (NumArtifacts == 0 && "Artifacts are only expected in instruction list starting the "
 "second iteration, but each iteration starting second must "
 "start with an empty artifacts list") ? void (0) : __assert_fail
 ("NumArtifacts == 0 && \"Artifacts are only expected in instruction list starting the \" \"second iteration, but each iteration starting second must \" \"start with an empty artifacts list\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 245, __extension__
 __PRETTY_FUNCTION__))
243                 "Artifacts are only expected in instruction list starting the "(static_cast <bool> (NumArtifacts == 0 && "Artifacts are only expected in instruction list starting the "
 "second iteration, but each iteration starting second must "
 "start with an empty artifacts list") ? void (0) : __assert_fail
 ("NumArtifacts == 0 && \"Artifacts are only expected in instruction list starting the \" \"second iteration, but each iteration starting second must \" \"start with an empty artifacts list\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 245, __extension__
 __PRETTY_FUNCTION__))
244                 "second iteration, but each iteration starting second must "(static_cast <bool> (NumArtifacts == 0 && "Artifacts are only expected in instruction list starting the "
 "second iteration, but each iteration starting second must "
 "start with an empty artifacts list") ? void (0) : __assert_fail
 ("NumArtifacts == 0 && \"Artifacts are only expected in instruction list starting the \" \"second iteration, but each iteration starting second must \" \"start with an empty artifacts list\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 245, __extension__
 __PRETTY_FUNCTION__))
245                 "start with an empty artifacts list")(static_cast <bool> (NumArtifacts == 0 && "Artifacts are only expected in instruction list starting the "
 "second iteration, but each iteration starting second must "
 "start with an empty artifacts list") ? void (0) : __assert_fail
 ("NumArtifacts == 0 && \"Artifacts are only expected in instruction list starting the \" \"second iteration, but each iteration starting second must \" \"start with an empty artifacts list\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 245, __extension__
 __PRETTY_FUNCTION__));
246          (void)NumArtifacts;
247          RetryList.push_back(&MI);
248          continue;
249        }
250        Helper.MIRBuilder.stopObservingChanges();
251        return {Changed, &MI};
252      }
253      WorkListObserver.printNewInstrs();
254      LocObserver.checkpoint();
255      Changed |= Res == LegalizerHelper::Legalized;
256    }
257    // Try to combine the instructions in RetryList again if there
258    // are new artifacts. If not, stop legalizing.
259    if (!RetryList.empty()) {
18
←
Taking false branch→
260      if (!ArtifactList.empty()) {
261        while (!RetryList.empty())
262          ArtifactList.insert(RetryList.pop_back_val());
263      } else {
264        LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "No new artifacts created, not retrying!\n"
; } } while (false);
265        Helper.MIRBuilder.stopObservingChanges();
266        return {Changed, RetryList.front()};
267      }
268    }
269    LocObserver.checkpoint();
270    while (!ArtifactList.empty()) {
19
←
Assuming the condition is true→
20
←
Loop condition is true.  Entering loop body→
271      MachineInstr &MI = *ArtifactList.pop_back_val();
272      assert(isPreISelGenericOpcode(MI.getOpcode()) &&(static_cast <bool> (isPreISelGenericOpcode(MI.getOpcode
()) && "Expecting generic opcode") ? void (0) : __assert_fail
 ("isPreISelGenericOpcode(MI.getOpcode()) && \"Expecting generic opcode\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 273, __extension__
 __PRETTY_FUNCTION__))
21
←
'?' condition is true→
273             "Expecting generic opcode")(static_cast <bool> (isPreISelGenericOpcode(MI.getOpcode
()) && "Expecting generic opcode") ? void (0) : __assert_fail
 ("isPreISelGenericOpcode(MI.getOpcode()) && \"Expecting generic opcode\""
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 273, __extension__
 __PRETTY_FUNCTION__));
274      if (isTriviallyDead(MI, MRI)) {
22
←
Assuming the condition is false→
23
←
Taking false branch→
275        eraseInstr(MI, MRI, &LocObserver);
276        continue;
277      }
278      SmallVector<MachineInstr *, 4> DeadInstructions;
279      LLVM_DEBUG(dbgs() << "Trying to combine: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Trying to combine: " <<
 MI; } } while (false);
24
←
Assuming 'DebugFlag' is false→
25
←
Loop condition is false.  Exiting loop→
280      if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
26
←
Calling 'LegalizationArtifactCombiner::tryCombineInstruction'→
281                                            WrapperObserver)) {
282        WorkListObserver.printNewInstrs();
283        eraseInstrs(DeadInstructions, MRI, &LocObserver);
284        LocObserver.checkpoint(
285            VerifyDebugLocs ==
286            DebugLocVerifyLevel::LegalizationsAndArtifactCombiners);
287        Changed = true;
288        continue;
289      }
290      // If this was not an artifact (that could be combined away), this might
291      // need special handling. Add it to InstList, so when it's processed
292      // there, it has to be legal or specially handled.
293      else {
294        LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Not combined, moving to instructions list\n"
; } } while (false);
295        InstList.insert(&MI);
296      }
297    }
298  } while (!InstList.empty());
299 
300  return {Changed, /*FailedOn*/ nullptr};
301}
302 
303bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
304  // If the ISel pipeline failed, do not bother running that pass.
305  if (MF.getProperties().hasProperty(
306          MachineFunctionProperties::Property::FailedISel))
307    return false;
308  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Legalize Machine IR for: " <<
 MF.getName() << '\n'; } } while (false);
1
Taking false branch→
2
←
Assuming 'DebugFlag' is false→
3
←
Loop condition is false.  Exiting loop→
309  init(MF);
310  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
311  GISelCSEAnalysisWrapper &Wrapper =
312      getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
313  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
314 
315  const size_t NumBlocks = MF.size();
316 
317  std::unique_ptr<MachineIRBuilder> MIRBuilder;
318  GISelCSEInfo *CSEInfo = nullptr;
319  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
4
←
Assuming the condition is false→
5
←
'?' condition is false→
320                       ? EnableCSEInLegalizer
321                       : TPC.isGISelCSEEnabled();
322  if (EnableCSE) {
6
←
Assuming 'EnableCSE' is false→
7
←
Taking false branch→
323    MIRBuilder = std::make_unique<CSEMIRBuilder>();
324    CSEInfo = &Wrapper.get(TPC.getCSEConfig());
325    MIRBuilder->setCSEInfo(CSEInfo);
326  } else
327    MIRBuilder = std::make_unique<MachineIRBuilder>();
328 
329  SmallVector<GISelChangeObserver *, 1> AuxObservers;
330  if (EnableCSE7.1
'EnableCSE' is false
7.1
'EnableCSE' is false
 && CSEInfo) {
331    // We want CSEInfo in addition to WorkListObserver to observe all changes.
332    AuxObservers.push_back(CSEInfo);
333  }
334  assert(!CSEInfo || !errorToBool(CSEInfo->verify()))(static_cast <bool> (!CSEInfo || !errorToBool(CSEInfo->
verify())) ? void (0) : __assert_fail ("!CSEInfo || !errorToBool(CSEInfo->verify())"
, "llvm/lib/CodeGen/GlobalISel/Legalizer.cpp", 334, __extension__
 __PRETTY_FUNCTION__));
8
←
'?' condition is true→
335  LostDebugLocObserver LocObserver(DEBUG_TYPE"legalizer");
336  if (VerifyDebugLocs > DebugLocVerifyLevel::None)
9
←
Assuming the condition is false→
10
←
Taking false branch→
337    AuxObservers.push_back(&LocObserver);
338 
339  const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
340  MFResult Result =
341      legalizeMachineFunction(MF, LI, AuxObservers, LocObserver, *MIRBuilder);
11
←
Calling 'Legalizer::legalizeMachineFunction'→
342 
343  if (Result.FailedOn) {
344    reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
345                       "unable to legalize instruction", *Result.FailedOn);
346    return false;
347  }
348  // For now don't support if new blocks are inserted - we would need to fix the
349  // outer loop for that.
350  if (MF.size() != NumBlocks) {
351    MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
352                                      MF.getFunction().getSubprogram(),
353                                      /*MBB=*/nullptr);
354    R << "inserting blocks is not supported yet";
355    reportGISelFailure(MF, TPC, MORE, R);
356    return false;
357  }
358 
359  if (LocObserver.getNumLostDebugLocs()) {
360    MachineOptimizationRemarkMissed R("gisel-legalize", "LostDebugLoc",
361                                      MF.getFunction().getSubprogram(),
362                                      /*MBB=*/&*MF.begin());
363    R << "lost "
364      << ore::NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs())
365      << " debug locations during pass";
366    reportGISelWarning(MF, TPC, MORE, R);
367    // Example remark:
368    // --- !Missed
369    // Pass:            gisel-legalize
370    // Name:            GISelFailure
371    // DebugLoc:        { File: '.../legalize-urem.mir', Line: 1, Column: 0 }
372    // Function:        test_urem_s32
373    // Args:
374    //   - String:          'lost '
375    //   - NumLostDebugLocs: '1'
376    //   - String:          ' debug locations during pass'
377    // ...
378  }
379 
380  // If for some reason CSE was not enabled, make sure that we invalidate the
381  // CSEInfo object (as we currently declare that the analysis is preserved).
382  // The next time get on the wrapper is called, it will force it to recompute
383  // the analysis.
384  if (!EnableCSE)
385    Wrapper.setComputed(false);
386  return Result.Changed;
387}

←

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

1//===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- C++ -*-//
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// This file contains some helper functions which try to cleanup artifacts
9// such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
10// the types match. This file also contains some combines of merges that happens
11// at the end of the legalization.
12//===----------------------------------------------------------------------===//

14#ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H
15#define LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H

17#include "llvm/ADT/SmallBitVector.h"
18#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
19#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
20#include "llvm/CodeGen/GlobalISel/Legalizer.h"
21#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
22#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
23#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
24#include "llvm/CodeGen/GlobalISel/Utils.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/CodeGen/Register.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/Support/Debug.h"

30#define DEBUG_TYPE"legalizer" "legalizer"

32namespace llvm {
33class LegalizationArtifactCombiner {
MachineIRBuilder &Builder;
MachineRegisterInfo &MRI;
const LegalizerInfo &LI;

static bool isArtifactCast(unsigned Opc) {
  switch (Opc) {
  case TargetOpcode::G_TRUNC:
  case TargetOpcode::G_SEXT:
  case TargetOpcode::G_ZEXT:
  case TargetOpcode::G_ANYEXT:
    return true;
  default:
    return false;
  }
}

50public:
LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
                  const LegalizerInfo &LI)
    : Builder(B), MRI(MRI), LI(LI) {}

bool tryCombineAnyExt(MachineInstr &MI,
                      SmallVectorImpl<MachineInstr *> &DeadInsts,
                      SmallVectorImpl<Register> &UpdatedDefs,
                      GISelObserverWrapper &Observer) {
  using namespace llvm::MIPatternMatch;
  assert(MI.getOpcode() == TargetOpcode::G_ANYEXT)(static_cast <bool> (MI.getOpcode() == TargetOpcode::G_ANYEXT
) ? void (0) : __assert_fail ("MI.getOpcode() == TargetOpcode::G_ANYEXT"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 60, __extension__ __PRETTY_FUNCTION__));

  Builder.setInstrAndDebugLoc(MI);
  Register DstReg = MI.getOperand(0).getReg();
  Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());

  // aext(trunc x) - > aext/copy/trunc x
  Register TruncSrc;
  if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
    LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine MI: " << MI
;; } } while (false);
    if (MRI.getType(DstReg) == MRI.getType(TruncSrc))
      replaceRegOrBuildCopy(DstReg, TruncSrc, MRI, Builder, UpdatedDefs,
                            Observer);
    else
      Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
    UpdatedDefs.push_back(DstReg);
    markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
    return true;
  }

  // aext([asz]ext x) -> [asz]ext x
  Register ExtSrc;
  MachineInstr *ExtMI;
  if (mi_match(SrcReg, MRI,
               m_all_of(m_MInstr(ExtMI), m_any_of(m_GAnyExt(m_Reg(ExtSrc)),
                                                  m_GSExt(m_Reg(ExtSrc)),
                                                  m_GZExt(m_Reg(ExtSrc)))))) {
    Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
    UpdatedDefs.push_back(DstReg);
    markInstAndDefDead(MI, *ExtMI, DeadInsts);
    return true;
  }

  // Try to fold aext(g_constant) when the larger constant type is legal.
  auto *SrcMI = MRI.getVRegDef(SrcReg);
  if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
    const LLT DstTy = MRI.getType(DstReg);
    if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
      auto &CstVal = SrcMI->getOperand(1);
      Builder.buildConstant(
          DstReg, CstVal.getCImm()->getValue().sext(DstTy.getSizeInBits()));
      UpdatedDefs.push_back(DstReg);
      markInstAndDefDead(MI, *SrcMI, DeadInsts);
      return true;
    }
  }
  return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
}

bool tryCombineZExt(MachineInstr &MI,
                    SmallVectorImpl<MachineInstr *> &DeadInsts,
                    SmallVectorImpl<Register> &UpdatedDefs,
                    GISelObserverWrapper &Observer) {
  using namespace llvm::MIPatternMatch;
  assert(MI.getOpcode() == TargetOpcode::G_ZEXT)(static_cast <bool> (MI.getOpcode() == TargetOpcode::G_ZEXT
) ? void (0) : __assert_fail ("MI.getOpcode() == TargetOpcode::G_ZEXT"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 114, __extension__ __PRETTY_FUNCTION__));

  Builder.setInstrAndDebugLoc(MI);
  Register DstReg = MI.getOperand(0).getReg();
  Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());

  // zext(trunc x) - > and (aext/copy/trunc x), mask
  // zext(sext x) -> and (sext x), mask
  Register TruncSrc;
  Register SextSrc;
  if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc))) ||
      mi_match(SrcReg, MRI, m_GSExt(m_Reg(SextSrc)))) {
    LLT DstTy = MRI.getType(DstReg);
    if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
        isConstantUnsupported(DstTy))
      return false;
    LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine MI: " << MI
;; } } while (false);
    LLT SrcTy = MRI.getType(SrcReg);
    APInt MaskVal = APInt::getAllOnes(SrcTy.getScalarSizeInBits());
    auto Mask = Builder.buildConstant(
      DstTy, MaskVal.zext(DstTy.getScalarSizeInBits()));
    if (SextSrc && (DstTy != MRI.getType(SextSrc)))
      SextSrc = Builder.buildSExtOrTrunc(DstTy, SextSrc).getReg(0);
    if (TruncSrc && (DstTy != MRI.getType(TruncSrc)))
      TruncSrc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc).getReg(0);
    Builder.buildAnd(DstReg, SextSrc ? SextSrc : TruncSrc, Mask);
    markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
    return true;
  }

  // zext(zext x) -> (zext x)
  Register ZextSrc;
  if (mi_match(SrcReg, MRI, m_GZExt(m_Reg(ZextSrc)))) {
    LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine MI: " << MI
; } } while (false);
    Observer.changingInstr(MI);
    MI.getOperand(1).setReg(ZextSrc);
    Observer.changedInstr(MI);
    UpdatedDefs.push_back(DstReg);
    markDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
    return true;
  }

  // Try to fold zext(g_constant) when the larger constant type is legal.
  auto *SrcMI = MRI.getVRegDef(SrcReg);
  if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
    const LLT DstTy = MRI.getType(DstReg);
    if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
      auto &CstVal = SrcMI->getOperand(1);
      Builder.buildConstant(
          DstReg, CstVal.getCImm()->getValue().zext(DstTy.getSizeInBits()));
      UpdatedDefs.push_back(DstReg);
      markInstAndDefDead(MI, *SrcMI, DeadInsts);
      return true;
    }
  }
  return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
}

bool tryCombineSExt(MachineInstr &MI,
                    SmallVectorImpl<MachineInstr *> &DeadInsts,
                    SmallVectorImpl<Register> &UpdatedDefs) {
  using namespace llvm::MIPatternMatch;
  assert(MI.getOpcode() == TargetOpcode::G_SEXT)(static_cast <bool> (MI.getOpcode() == TargetOpcode::G_SEXT
) ? void (0) : __assert_fail ("MI.getOpcode() == TargetOpcode::G_SEXT"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 176, __extension__ __PRETTY_FUNCTION__));

  Builder.setInstrAndDebugLoc(MI);
  Register DstReg = MI.getOperand(0).getReg();
  Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());

  // sext(trunc x) - > (sext_inreg (aext/copy/trunc x), c)
  Register TruncSrc;
  if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
    LLT DstTy = MRI.getType(DstReg);
    if (isInstUnsupported({TargetOpcode::G_SEXT_INREG, {DstTy}}))
      return false;
    LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine MI: " << MI
;; } } while (false);
    LLT SrcTy = MRI.getType(SrcReg);
    uint64_t SizeInBits = SrcTy.getScalarSizeInBits();
    if (DstTy != MRI.getType(TruncSrc))
      TruncSrc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc).getReg(0);
    Builder.buildSExtInReg(DstReg, TruncSrc, SizeInBits);
    markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
    return true;
  }

  // sext(zext x) -> (zext x)
  // sext(sext x) -> (sext x)
  Register ExtSrc;
  MachineInstr *ExtMI;
  if (mi_match(SrcReg, MRI,
               m_all_of(m_MInstr(ExtMI), m_any_of(m_GZExt(m_Reg(ExtSrc)),
                                                  m_GSExt(m_Reg(ExtSrc)))))) {
    LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine MI: " << MI
; } } while (false);
    Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
    UpdatedDefs.push_back(DstReg);
    markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
    return true;
  }

  // Try to fold sext(g_constant) when the larger constant type is legal.
  auto *SrcMI = MRI.getVRegDef(SrcReg);
  if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
    const LLT DstTy = MRI.getType(DstReg);
    if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
      auto &CstVal = SrcMI->getOperand(1);
      Builder.buildConstant(
          DstReg, CstVal.getCImm()->getValue().sext(DstTy.getSizeInBits()));
      UpdatedDefs.push_back(DstReg);
      markInstAndDefDead(MI, *SrcMI, DeadInsts);
      return true;
    }
  }

  return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs);
}

bool tryCombineTrunc(MachineInstr &MI,
                     SmallVectorImpl<MachineInstr *> &DeadInsts,
                     SmallVectorImpl<Register> &UpdatedDefs,
                     GISelObserverWrapper &Observer) {
  using namespace llvm::MIPatternMatch;
  assert(MI.getOpcode() == TargetOpcode::G_TRUNC)(static_cast <bool> (MI.getOpcode() == TargetOpcode::G_TRUNC
) ? void (0) : __assert_fail ("MI.getOpcode() == TargetOpcode::G_TRUNC"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 234, __extension__ __PRETTY_FUNCTION__));

  Builder.setInstr(MI);
  Register DstReg = MI.getOperand(0).getReg();
  Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());

  // Try to fold trunc(g_constant) when the smaller constant type is legal.
  auto *SrcMI = MRI.getVRegDef(SrcReg);
  if (SrcMI->getOpcode() == TargetOpcode::G_CONSTANT) {
    const LLT DstTy = MRI.getType(DstReg);
    if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
      auto &CstVal = SrcMI->getOperand(1);
      Builder.buildConstant(
          DstReg, CstVal.getCImm()->getValue().trunc(DstTy.getSizeInBits()));
      UpdatedDefs.push_back(DstReg);
      markInstAndDefDead(MI, *SrcMI, DeadInsts);
      return true;
    }
  }

  // Try to fold trunc(merge) to directly use the source of the merge.
  // This gets rid of large, difficult to legalize, merges
  if (auto *SrcMerge = dyn_cast<GMerge>(SrcMI)) {
    const Register MergeSrcReg = SrcMerge->getSourceReg(0);
    const LLT MergeSrcTy = MRI.getType(MergeSrcReg);
    const LLT DstTy = MRI.getType(DstReg);

    // We can only fold if the types are scalar
    const unsigned DstSize = DstTy.getSizeInBits();
    const unsigned MergeSrcSize = MergeSrcTy.getSizeInBits();
    if (!DstTy.isScalar() || !MergeSrcTy.isScalar())
      return false;

    if (DstSize < MergeSrcSize) {
      // When the merge source is larger than the destination, we can just
      // truncate the merge source directly
      if (isInstUnsupported({TargetOpcode::G_TRUNC, {DstTy, MergeSrcTy}}))
        return false;

      LLVM_DEBUG(dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_TRUNC: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_TRUNC: "
 << MI; } } while (false)
                        << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_TRUNC: "
 << MI; } } while (false);

      Builder.buildTrunc(DstReg, MergeSrcReg);
      UpdatedDefs.push_back(DstReg);
    } else if (DstSize == MergeSrcSize) {
      // If the sizes match we can simply try to replace the register
      LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Replacing G_TRUNC(G_MERGE_VALUES) with merge input: "
 << MI; } } while (false)
          dbgs() << "Replacing G_TRUNC(G_MERGE_VALUES) with merge input: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Replacing G_TRUNC(G_MERGE_VALUES) with merge input: "
 << MI; } } while (false)
                 << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Replacing G_TRUNC(G_MERGE_VALUES) with merge input: "
 << MI; } } while (false);
      replaceRegOrBuildCopy(DstReg, MergeSrcReg, MRI, Builder, UpdatedDefs,
                            Observer);
    } else if (DstSize % MergeSrcSize == 0) {
      // If the trunc size is a multiple of the merge source size we can use
      // a smaller merge instead
      if (isInstUnsupported(
              {TargetOpcode::G_MERGE_VALUES, {DstTy, MergeSrcTy}}))
        return false;

      LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_MERGE_VALUES: "
 << MI; } } while (false)
          dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_MERGE_VALUES: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_MERGE_VALUES: "
 << MI; } } while (false)
                 << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_MERGE_VALUES: "
 << MI; } } while (false);

      const unsigned NumSrcs = DstSize / MergeSrcSize;
      assert(NumSrcs < SrcMI->getNumOperands() - 1 &&(static_cast <bool> (NumSrcs < SrcMI->getNumOperands
() - 1 && "trunc(merge) should require less inputs than merge"
) ? void (0) : __assert_fail ("NumSrcs < SrcMI->getNumOperands() - 1 && \"trunc(merge) should require less inputs than merge\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 298, __extension__ __PRETTY_FUNCTION__))
             "trunc(merge) should require less inputs than merge")(static_cast <bool> (NumSrcs < SrcMI->getNumOperands
() - 1 && "trunc(merge) should require less inputs than merge"
) ? void (0) : __assert_fail ("NumSrcs < SrcMI->getNumOperands() - 1 && \"trunc(merge) should require less inputs than merge\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 298, __extension__ __PRETTY_FUNCTION__));
      SmallVector<Register, 8> SrcRegs(NumSrcs);
      for (unsigned i = 0; i < NumSrcs; ++i)
        SrcRegs[i] = SrcMerge->getSourceReg(i);

      Builder.buildMerge(DstReg, SrcRegs);
      UpdatedDefs.push_back(DstReg);
    } else {
      // Unable to combine
      return false;
    }

    markInstAndDefDead(MI, *SrcMerge, DeadInsts);
    return true;
  }

  // trunc(trunc) -> trunc
  Register TruncSrc;
  if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
    // Always combine trunc(trunc) since the eventual resulting trunc must be
    // legal anyway as it must be legal for all outputs of the consumer type
    // set.
    LLVM_DEBUG(dbgs() << ".. Combine G_TRUNC(G_TRUNC): " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine G_TRUNC(G_TRUNC): "
 << MI; } } while (false);

    Builder.buildTrunc(DstReg, TruncSrc);
    UpdatedDefs.push_back(DstReg);
    markInstAndDefDead(MI, *MRI.getVRegDef(TruncSrc), DeadInsts);
    return true;
  }

  return false;
}

/// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
bool tryFoldImplicitDef(MachineInstr &MI,
                        SmallVectorImpl<MachineInstr *> &DeadInsts,
                        SmallVectorImpl<Register> &UpdatedDefs) {
  unsigned Opcode = MI.getOpcode();
  assert(Opcode == TargetOpcode::G_ANYEXT || Opcode == TargetOpcode::G_ZEXT ||(static_cast <bool> (Opcode == TargetOpcode::G_ANYEXT ||
 Opcode == TargetOpcode::G_ZEXT || Opcode == TargetOpcode::G_SEXT
) ? void (0) : __assert_fail ("Opcode == TargetOpcode::G_ANYEXT || Opcode == TargetOpcode::G_ZEXT || Opcode == TargetOpcode::G_SEXT"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 337, __extension__ __PRETTY_FUNCTION__))
         Opcode == TargetOpcode::G_SEXT)(static_cast <bool> (Opcode == TargetOpcode::G_ANYEXT ||
 Opcode == TargetOpcode::G_ZEXT || Opcode == TargetOpcode::G_SEXT
) ? void (0) : __assert_fail ("Opcode == TargetOpcode::G_ANYEXT || Opcode == TargetOpcode::G_ZEXT || Opcode == TargetOpcode::G_SEXT"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 337, __extension__ __PRETTY_FUNCTION__));

  if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
                                         MI.getOperand(1).getReg(), MRI)) {
    Builder.setInstr(MI);
    Register DstReg = MI.getOperand(0).getReg();
    LLT DstTy = MRI.getType(DstReg);

    if (Opcode == TargetOpcode::G_ANYEXT) {
      // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
      if (!isInstLegal({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
        return false;
      LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): "
 << MI;; } } while (false);
      Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, {DstReg}, {});
      UpdatedDefs.push_back(DstReg);
    } else {
      // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
      // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
      if (isConstantUnsupported(DstTy))
        return false;
      LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI;)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): "
 << MI;; } } while (false);
      Builder.buildConstant(DstReg, 0);
      UpdatedDefs.push_back(DstReg);
    }

    markInstAndDefDead(MI, *DefMI, DeadInsts);
    return true;
  }
  return false;
}

bool tryFoldUnmergeCast(MachineInstr &MI, MachineInstr &CastMI,
                        SmallVectorImpl<MachineInstr *> &DeadInsts,
                        SmallVectorImpl<Register> &UpdatedDefs) {

  assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES)(static_cast <bool> (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES
) ? void (0) : __assert_fail ("MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 372, __extension__ __PRETTY_FUNCTION__));
40
←
Assuming the condition is true→
41
←
'?' condition is true→

  const unsigned CastOpc = CastMI.getOpcode();

  if (!isArtifactCast(CastOpc))
42
←
Assuming the condition is false→
43
←
Taking false branch→
    return false;

  const unsigned NumDefs = MI.getNumOperands() - 1;
44
←
'NumDefs' initialized to 0→

  const Register CastSrcReg = CastMI.getOperand(1).getReg();
  const LLT CastSrcTy = MRI.getType(CastSrcReg);
  const LLT DestTy = MRI.getType(MI.getOperand(0).getReg());
  const LLT SrcTy = MRI.getType(MI.getOperand(NumDefs).getReg());

  const unsigned CastSrcSize = CastSrcTy.getSizeInBits();
  const unsigned DestSize = DestTy.getSizeInBits();

  if (CastOpc44.1
'CastOpc' is equal to G_TRUNC
1
'CastOpc' is equal to G_TRUNC
 == TargetOpcode::G_TRUNC) {
    if (SrcTy.isVector() && SrcTy.getScalarType() == DestTy.getScalarType()) {
45
←
Assuming the condition is true→
46
←
Assuming the condition is true→
      //  %1:_(<4 x s8>) = G_TRUNC %0(<4 x s32>)
      //  %2:_(s8), %3:_(s8), %4:_(s8), %5:_(s8) = G_UNMERGE_VALUES %1
      // =>
      //  %6:_(s32), %7:_(s32), %8:_(s32), %9:_(s32) = G_UNMERGE_VALUES %0
      //  %2:_(s8) = G_TRUNC %6
      //  %3:_(s8) = G_TRUNC %7
      //  %4:_(s8) = G_TRUNC %8
      //  %5:_(s8) = G_TRUNC %9

      unsigned UnmergeNumElts =
47
←
Taking true branch→
          DestTy.isVector() ? CastSrcTy.getNumElements() / NumDefs : 1;
48
←
Assuming the condition is true→
49
←
'?' condition is true→
50
←
Division by zero
      LLT UnmergeTy = CastSrcTy.changeElementCount(
          ElementCount::getFixed(UnmergeNumElts));

      if (isInstUnsupported(
              {TargetOpcode::G_UNMERGE_VALUES, {UnmergeTy, CastSrcTy}}))
        return false;

      Builder.setInstr(MI);
      auto NewUnmerge = Builder.buildUnmerge(UnmergeTy, CastSrcReg);

      for (unsigned I = 0; I != NumDefs; ++I) {
        Register DefReg = MI.getOperand(I).getReg();
        UpdatedDefs.push_back(DefReg);
        Builder.buildTrunc(DefReg, NewUnmerge.getReg(I));
      }

      markInstAndDefDead(MI, CastMI, DeadInsts);
      return true;
    }

    if (CastSrcTy.isScalar() && SrcTy.isScalar() && !DestTy.isVector()) {
      //  %1:_(s16) = G_TRUNC %0(s32)
      //  %2:_(s8), %3:_(s8) = G_UNMERGE_VALUES %1
      // =>
      //  %2:_(s8), %3:_(s8), %4:_(s8), %5:_(s8) = G_UNMERGE_VALUES %0

      // Unmerge(trunc) can be combined if the trunc source size is a multiple
      // of the unmerge destination size
      if (CastSrcSize % DestSize != 0)
        return false;

      // Check if the new unmerge is supported
      if (isInstUnsupported(
              {TargetOpcode::G_UNMERGE_VALUES, {DestTy, CastSrcTy}}))
        return false;

      // Gather the original destination registers and create new ones for the
      // unused bits
      const unsigned NewNumDefs = CastSrcSize / DestSize;
      SmallVector<Register, 8> DstRegs(NewNumDefs);
      for (unsigned Idx = 0; Idx < NewNumDefs; ++Idx) {
        if (Idx < NumDefs)
          DstRegs[Idx] = MI.getOperand(Idx).getReg();
        else
          DstRegs[Idx] = MRI.createGenericVirtualRegister(DestTy);
      }

      // Build new unmerge
      Builder.setInstr(MI);
      Builder.buildUnmerge(DstRegs, CastSrcReg);
      UpdatedDefs.append(DstRegs.begin(), DstRegs.begin() + NewNumDefs);
      markInstAndDefDead(MI, CastMI, DeadInsts);
      return true;
    }
  }

  // TODO: support combines with other casts as well
  return false;
}

static bool canFoldMergeOpcode(unsigned MergeOp, unsigned ConvertOp,
                               LLT OpTy, LLT DestTy) {
  // Check if we found a definition that is like G_MERGE_VALUES.
  switch (MergeOp) {
  default:
    return false;
  case TargetOpcode::G_BUILD_VECTOR:
  case TargetOpcode::G_MERGE_VALUES:
    // The convert operation that we will need to insert is
    // going to convert the input of that type of instruction (scalar)
    // to the destination type (DestTy).
    // The conversion needs to stay in the same domain (scalar to scalar
    // and vector to vector), so if we were to allow to fold the merge
    // we would need to insert some bitcasts.
    // E.g.,
    // <2 x s16> = build_vector s16, s16
    // <2 x s32> = zext <2 x s16>
    // <2 x s16>, <2 x s16> = unmerge <2 x s32>
    //
    // As is the folding would produce:
    // <2 x s16> = zext s16  <-- scalar to vector
    // <2 x s16> = zext s16  <-- scalar to vector
    // Which is invalid.
    // Instead we would want to generate:
    // s32 = zext s16
    // <2 x s16> = bitcast s32
    // s32 = zext s16
    // <2 x s16> = bitcast s32
    //
    // That is not done yet.
    if (ConvertOp == 0)
      return true;
    return !DestTy.isVector() && OpTy.isVector() &&
           DestTy == OpTy.getElementType();
  case TargetOpcode::G_CONCAT_VECTORS: {
    if (ConvertOp == 0)
      return true;
    if (!DestTy.isVector())
      return false;

    const unsigned OpEltSize = OpTy.getElementType().getSizeInBits();

    // Don't handle scalarization with a cast that isn't in the same
    // direction as the vector cast. This could be handled, but it would
    // require more intermediate unmerges.
    if (ConvertOp == TargetOpcode::G_TRUNC)
      return DestTy.getSizeInBits() <= OpEltSize;
    return DestTy.getSizeInBits() >= OpEltSize;
  }
  }
}

/// Try to replace DstReg with SrcReg or build a COPY instruction
/// depending on the register constraints.
static void replaceRegOrBuildCopy(Register DstReg, Register SrcReg,
                                  MachineRegisterInfo &MRI,
                                  MachineIRBuilder &Builder,
                                  SmallVectorImpl<Register> &UpdatedDefs,
                                  GISelChangeObserver &Observer) {
  if (!llvm::canReplaceReg(DstReg, SrcReg, MRI)) {
    Builder.buildCopy(DstReg, SrcReg);
    UpdatedDefs.push_back(DstReg);
    return;
  }
  SmallVector<MachineInstr *, 4> UseMIs;
  // Get the users and notify the observer before replacing.
  for (auto &UseMI : MRI.use_instructions(DstReg)) {
    UseMIs.push_back(&UseMI);
    Observer.changingInstr(UseMI);
  }
  // Replace the registers.
  MRI.replaceRegWith(DstReg, SrcReg);
  UpdatedDefs.push_back(SrcReg);
  // Notify the observer that we changed the instructions.
  for (auto *UseMI : UseMIs)
    Observer.changedInstr(*UseMI);
}

/// Return the operand index in \p MI that defines \p Def
static unsigned getDefIndex(const MachineInstr &MI, Register SearchDef) {
  unsigned DefIdx = 0;
  for (const MachineOperand &Def : MI.defs()) {
    if (Def.getReg() == SearchDef)
      break;
    ++DefIdx;
  }

  return DefIdx;
}

/// This class provides utilities for finding source registers of specific
/// bit ranges in an artifact. The routines can look through the source
/// registers if they're other artifacts to try to find a non-artifact source
/// of a value.
class ArtifactValueFinder {
  MachineRegisterInfo &MRI;
  MachineIRBuilder &MIB;
  const LegalizerInfo &LI;

  // Stores the best register found in the current query so far.
  Register CurrentBest = Register();

  /// Given an concat_vector op \p Concat and a start bit and size, try to
  /// find the origin of the value defined by that start position and size.
  ///
  /// \returns a register with the requested size, or the current best
  /// register found during the current query.
  Register findValueFromConcat(GConcatVectors &Concat, unsigned StartBit,
                               unsigned Size) {
    assert(Size > 0)(static_cast <bool> (Size > 0) ? void (0) : __assert_fail
 ("Size > 0", "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 571, __extension__ __PRETTY_FUNCTION__));

    // Find the source operand that provides the bits requested.
    Register Src1Reg = Concat.getSourceReg(0);
    unsigned SrcSize = MRI.getType(Src1Reg).getSizeInBits();

    // Operand index of the source that provides the start of the bit range.
    unsigned StartSrcIdx = (StartBit / SrcSize) + 1;
    // Offset into the source at which the bit range starts.
    unsigned InRegOffset = StartBit % SrcSize;
    // Check that the bits don't span multiple sources.
    // FIXME: we might be able return multiple sources? Or create an
    // appropriate concat to make it fit.
    if (InRegOffset + Size > SrcSize)
      return CurrentBest;

    Register SrcReg = Concat.getReg(StartSrcIdx);
    if (InRegOffset == 0 && Size == SrcSize) {
      CurrentBest = SrcReg;
      return findValueFromDefImpl(SrcReg, 0, Size);
    }

    return findValueFromDefImpl(SrcReg, InRegOffset, Size);
  }

  /// Given an build_vector op \p BV and a start bit and size, try to find
  /// the origin of the value defined by that start position and size.
  ///
  /// \returns a register with the requested size, or the current best
  /// register found during the current query.
  Register findValueFromBuildVector(GBuildVector &BV, unsigned StartBit,
                                    unsigned Size) {
    assert(Size > 0)(static_cast <bool> (Size > 0) ? void (0) : __assert_fail
 ("Size > 0", "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 603, __extension__ __PRETTY_FUNCTION__));

    // Find the source operand that provides the bits requested.
    Register Src1Reg = BV.getSourceReg(0);
    unsigned SrcSize = MRI.getType(Src1Reg).getSizeInBits();

    // Operand index of the source that provides the start of the bit range.
    unsigned StartSrcIdx = (StartBit / SrcSize) + 1;
    // Offset into the source at which the bit range starts.
    unsigned InRegOffset = StartBit % SrcSize;

    if (InRegOffset != 0)
      return CurrentBest; // Give up, bits don't start at a scalar source.
    if (Size < SrcSize)
      return CurrentBest; // Scalar source is too large for requested bits.

    // If the bits cover multiple sources evenly, then create a new
    // build_vector to synthesize the required size, if that's been requested.
    if (Size > SrcSize) {
      if (Size % SrcSize > 0)
        return CurrentBest; // Isn't covered exactly by sources.

      unsigned NumSrcsUsed = Size / SrcSize;
      // If we're requesting all of the sources, just return this def.
      if (NumSrcsUsed == BV.getNumSources())
        return BV.getReg(0);

      LLT SrcTy = MRI.getType(Src1Reg);
      LLT NewBVTy = LLT::fixed_vector(NumSrcsUsed, SrcTy);

      // Check if the resulting build vector would be legal.
      LegalizeActionStep ActionStep =
          LI.getAction({TargetOpcode::G_BUILD_VECTOR, {NewBVTy, SrcTy}});
      if (ActionStep.Action != LegalizeActions::Legal)
        return CurrentBest;

      SmallVector<Register> NewSrcs;
      for (unsigned SrcIdx = StartSrcIdx; SrcIdx < StartSrcIdx + NumSrcsUsed;
           ++SrcIdx)
        NewSrcs.push_back(BV.getReg(SrcIdx));
      MIB.setInstrAndDebugLoc(BV);
      return MIB.buildBuildVector(NewBVTy, NewSrcs).getReg(0);
    }
    // A single source is requested, just return it.
    return BV.getReg(StartSrcIdx);
  }

  /// Given an G_INSERT op \p MI and a start bit and size, try to find
  /// the origin of the value defined by that start position and size.
  ///
  /// \returns a register with the requested size, or the current best
  /// register found during the current query.
  Register findValueFromInsert(MachineInstr &MI, unsigned StartBit,
                               unsigned Size) {
    assert(MI.getOpcode() == TargetOpcode::G_INSERT)(static_cast <bool> (MI.getOpcode() == TargetOpcode::G_INSERT
) ? void (0) : __assert_fail ("MI.getOpcode() == TargetOpcode::G_INSERT"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 657, __extension__ __PRETTY_FUNCTION__));
    assert(Size > 0)(static_cast <bool> (Size > 0) ? void (0) : __assert_fail
 ("Size > 0", "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 658, __extension__ __PRETTY_FUNCTION__));

    Register ContainerSrcReg = MI.getOperand(1).getReg();
    Register InsertedReg = MI.getOperand(2).getReg();
    LLT InsertedRegTy = MRI.getType(InsertedReg);
    unsigned InsertOffset = MI.getOperand(3).getImm();

    // There are 4 possible container/insertreg + requested bit-range layouts
    // that the instruction and query could be representing.
    // For: %_ = G_INSERT %CONTAINER, %INS, InsOff (abbrev. to 'IO')
    // and a start bit 'SB', with size S, giving an end bit 'EB', we could
    // have...
    // Scenario A:
    //   --------------------------
    //  |  INS    |  CONTAINER     |
    //   --------------------------
    //       |   |
    //       SB  EB
    //
    // Scenario B:
    //   --------------------------
    //  |  INS    |  CONTAINER     |
    //   --------------------------
    //                |    |
    //                SB   EB
    //
    // Scenario C:
    //   --------------------------
    //  |  CONTAINER    |  INS     |
    //   --------------------------
    //       |    |
    //       SB   EB
    //
    // Scenario D:
    //   --------------------------
    //  |  CONTAINER    |  INS     |
    //   --------------------------
    //                     |   |
    //                     SB  EB
    //
    // So therefore, A and D are requesting data from the INS operand, while
    // B and C are requesting from the container operand.

    unsigned InsertedEndBit = InsertOffset + InsertedRegTy.getSizeInBits();
    unsigned EndBit = StartBit + Size;
    unsigned NewStartBit;
    Register SrcRegToUse;
    if (EndBit <= InsertOffset || InsertedEndBit <= StartBit) {
      SrcRegToUse = ContainerSrcReg;
      NewStartBit = StartBit;
      return findValueFromDefImpl(SrcRegToUse, NewStartBit, Size);
    }
    if (InsertOffset <= StartBit && EndBit <= InsertedEndBit) {
      SrcRegToUse = InsertedReg;
      NewStartBit = StartBit - InsertOffset;
      if (NewStartBit == 0 &&
          Size == MRI.getType(SrcRegToUse).getSizeInBits())
        CurrentBest = SrcRegToUse;
      return findValueFromDefImpl(SrcRegToUse, NewStartBit, Size);
    }
    // The bit range spans both the inserted and container regions.
    return Register();
  }

  /// Internal implementation for findValueFromDef(). findValueFromDef()
  /// initializes some data like the CurrentBest register, which this method
  /// and its callees rely upon.
  Register findValueFromDefImpl(Register DefReg, unsigned StartBit,
                                unsigned Size) {
    MachineInstr *Def = getDefIgnoringCopies(DefReg, MRI);
    // If the instruction has a single def, then simply delegate the search.
    // For unmerge however with multiple defs, we need to compute the offset
    // into the source of the unmerge.
    switch (Def->getOpcode()) {
    case TargetOpcode::G_CONCAT_VECTORS:
      return findValueFromConcat(cast<GConcatVectors>(*Def), StartBit, Size);
    case TargetOpcode::G_UNMERGE_VALUES: {
      unsigned DefStartBit = 0;
      unsigned DefSize = MRI.getType(DefReg).getSizeInBits();
      for (const auto &MO : Def->defs()) {
        if (MO.getReg() == DefReg)
          break;
        DefStartBit += DefSize;
      }
      Register SrcReg = Def->getOperand(Def->getNumOperands() - 1).getReg();
      Register SrcOriginReg =
          findValueFromDefImpl(SrcReg, StartBit + DefStartBit, Size);
      if (SrcOriginReg)
        return SrcOriginReg;
      // Failed to find a further value. If the StartBit and Size perfectly
      // covered the requested DefReg, return that since it's better than
      // nothing.
      if (StartBit == 0 && Size == DefSize)
        return DefReg;
      return CurrentBest;
    }
    case TargetOpcode::G_BUILD_VECTOR:
      return findValueFromBuildVector(cast<GBuildVector>(*Def), StartBit,
                                      Size);
    case TargetOpcode::G_INSERT:
      return findValueFromInsert(*Def, StartBit, Size);
    default:
      return CurrentBest;
    }
  }

public:
  ArtifactValueFinder(MachineRegisterInfo &Mri, MachineIRBuilder &Builder,
                      const LegalizerInfo &Info)
      : MRI(Mri), MIB(Builder), LI(Info) {}

  /// Try to find a source of the value defined in the def \p DefReg, starting
  /// at position \p StartBit with size \p Size.
  /// \returns a register with the requested size, or an empty Register if no
  /// better value could be found.
  Register findValueFromDef(Register DefReg, unsigned StartBit,
                            unsigned Size) {
    CurrentBest = Register();
    Register FoundReg = findValueFromDefImpl(DefReg, StartBit, Size);
    return FoundReg != DefReg ? FoundReg : Register();
  }

  /// Try to combine the defs of an unmerge \p MI by attempting to find
  /// values that provides the bits for each def reg.
  /// \returns true if all the defs of the unmerge have been made dead.
  bool tryCombineUnmergeDefs(GUnmerge &MI, GISelChangeObserver &Observer,
                             SmallVectorImpl<Register> &UpdatedDefs) {
    unsigned NumDefs = MI.getNumDefs();
    LLT DestTy = MRI.getType(MI.getReg(0));

    SmallBitVector DeadDefs(NumDefs);
    for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
      Register DefReg = MI.getReg(DefIdx);
      if (MRI.use_nodbg_empty(DefReg)) {
        DeadDefs[DefIdx] = true;
        continue;
      }
      Register FoundVal = findValueFromDef(DefReg, 0, DestTy.getSizeInBits());
      if (!FoundVal)
        continue;
      if (MRI.getType(FoundVal) != DestTy)
        continue;

      replaceRegOrBuildCopy(DefReg, FoundVal, MRI, MIB, UpdatedDefs,
                            Observer);
      // We only want to replace the uses, not the def of the old reg.
      Observer.changingInstr(MI);
      MI.getOperand(DefIdx).setReg(DefReg);
      Observer.changedInstr(MI);
      DeadDefs[DefIdx] = true;
    }
    return DeadDefs.all();
  }
};

bool tryCombineUnmergeValues(GUnmerge &MI,
                             SmallVectorImpl<MachineInstr *> &DeadInsts,
                             SmallVectorImpl<Register> &UpdatedDefs,
                             GISelChangeObserver &Observer) {
  unsigned NumDefs = MI.getNumDefs();
  Register SrcReg = MI.getSourceReg();
  MachineInstr *SrcDef = getDefIgnoringCopies(SrcReg, MRI);
  if (!SrcDef)
31
←
Assuming 'SrcDef' is non-null→
32
←
Taking false branch→
    return false;

  LLT OpTy = MRI.getType(SrcReg);
  LLT DestTy = MRI.getType(MI.getReg(0));
  unsigned SrcDefIdx = getDefIndex(*SrcDef, SrcReg);

  Builder.setInstrAndDebugLoc(MI);

  ArtifactValueFinder Finder(MRI, Builder, LI);
  if (Finder.tryCombineUnmergeDefs(MI, Observer, UpdatedDefs)) {
33
←
Assuming the condition is false→
34
←
Taking false branch→
    markInstAndDefDead(MI, *SrcDef, DeadInsts, SrcDefIdx);
    return true;
  }

  if (auto *SrcUnmerge35.1
'SrcUnmerge' is null
1
'SrcUnmerge' is null
 = dyn_cast<GUnmerge>(SrcDef)) {
35
←
Assuming 'SrcDef' is not a 'GUnmerge'→
36
←
Taking false branch→
    // %0:_(<4 x s16>) = G_FOO
    // %1:_(<2 x s16>), %2:_(<2 x s16>) = G_UNMERGE_VALUES %0
    // %3:_(s16), %4:_(s16) = G_UNMERGE_VALUES %1
    //
    // %3:_(s16), %4:_(s16), %5:_(s16), %6:_(s16) = G_UNMERGE_VALUES %0
    Register SrcUnmergeSrc = SrcUnmerge->getSourceReg();
    LLT SrcUnmergeSrcTy = MRI.getType(SrcUnmergeSrc);

    // If we need to decrease the number of vector elements in the result type
    // of an unmerge, this would involve the creation of an equivalent unmerge
    // to copy back to the original result registers.
    LegalizeActionStep ActionStep = LI.getAction(
        {TargetOpcode::G_UNMERGE_VALUES, {OpTy, SrcUnmergeSrcTy}});
    switch (ActionStep.Action) {
    case LegalizeActions::Lower:
    case LegalizeActions::Unsupported:
      break;
    case LegalizeActions::FewerElements:
    case LegalizeActions::NarrowScalar:
      if (ActionStep.TypeIdx == 1)
        return false;
      break;
    default:
      return false;
    }

    auto NewUnmerge = Builder.buildUnmerge(DestTy, SrcUnmergeSrc);

    // TODO: Should we try to process out the other defs now? If the other
    // defs of the source unmerge are also unmerged, we end up with a separate
    // unmerge for each one.
    for (unsigned I = 0; I != NumDefs; ++I) {
      Register Def = MI.getReg(I);
      replaceRegOrBuildCopy(Def, NewUnmerge.getReg(SrcDefIdx * NumDefs + I),
                            MRI, Builder, UpdatedDefs, Observer);
    }

    markInstAndDefDead(MI, *SrcUnmerge, DeadInsts, SrcDefIdx);
    return true;
  }

  MachineInstr *MergeI = SrcDef;
  unsigned ConvertOp = 0;

  // Handle intermediate conversions
  unsigned SrcOp = SrcDef->getOpcode();
  if (isArtifactCast(SrcOp)) {
37
←
Taking true branch→
    ConvertOp = SrcOp;
    MergeI = getDefIgnoringCopies(SrcDef->getOperand(1).getReg(), MRI);
  }

  if (!MergeI || !canFoldMergeOpcode(MergeI->getOpcode(),
38
←
Assuming 'MergeI' is null→
                                     ConvertOp, OpTy, DestTy)) {
    // We might have a chance to combine later by trying to combine
    // unmerge(cast) first
    return tryFoldUnmergeCast(MI, *SrcDef, DeadInsts, UpdatedDefs);
39
←
Calling 'LegalizationArtifactCombiner::tryFoldUnmergeCast'→
  }

  const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;

  if (NumMergeRegs < NumDefs) {
    if (NumDefs % NumMergeRegs != 0)
      return false;

    Builder.setInstr(MI);
    // Transform to UNMERGEs, for example
    //   %1 = G_MERGE_VALUES %4, %5
    //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
    // to
    //   %9, %10 = G_UNMERGE_VALUES %4
    //   %11, %12 = G_UNMERGE_VALUES %5

    const unsigned NewNumDefs = NumDefs / NumMergeRegs;
    for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
      SmallVector<Register, 8> DstRegs;
      for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
           ++j, ++DefIdx)
        DstRegs.push_back(MI.getReg(DefIdx));

      if (ConvertOp) {
        LLT MergeSrcTy = MRI.getType(MergeI->getOperand(1).getReg());

        // This is a vector that is being split and casted. Extract to the
        // element type, and do the conversion on the scalars (or smaller
        // vectors).
        LLT MergeEltTy = MergeSrcTy.divide(NewNumDefs);

        // Handle split to smaller vectors, with conversions.
        // %2(<8 x s8>) = G_CONCAT_VECTORS %0(<4 x s8>), %1(<4 x s8>)
        // %3(<8 x s16>) = G_SEXT %2
        // %4(<2 x s16>), %5(<2 x s16>), %6(<2 x s16>), %7(<2 x s16>) = G_UNMERGE_VALUES %3
        //
        // =>
        //
        // %8(<2 x s8>), %9(<2 x s8>) = G_UNMERGE_VALUES %0
        // %10(<2 x s8>), %11(<2 x s8>) = G_UNMERGE_VALUES %1
        // %4(<2 x s16>) = G_SEXT %8
        // %5(<2 x s16>) = G_SEXT %9
        // %6(<2 x s16>) = G_SEXT %10
        // %7(<2 x s16>)= G_SEXT %11

        SmallVector<Register, 4> TmpRegs(NewNumDefs);
        for (unsigned k = 0; k < NewNumDefs; ++k)
          TmpRegs[k] = MRI.createGenericVirtualRegister(MergeEltTy);

        Builder.buildUnmerge(TmpRegs, MergeI->getOperand(Idx + 1).getReg());

        for (unsigned k = 0; k < NewNumDefs; ++k)
          Builder.buildInstr(ConvertOp, {DstRegs[k]}, {TmpRegs[k]});
      } else {
        Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
      }
      UpdatedDefs.append(DstRegs.begin(), DstRegs.end());
    }

  } else if (NumMergeRegs > NumDefs) {
    if (ConvertOp != 0 || NumMergeRegs % NumDefs != 0)
      return false;

    Builder.setInstr(MI);
    // Transform to MERGEs
    //   %6 = G_MERGE_VALUES %17, %18, %19, %20
    //   %7, %8 = G_UNMERGE_VALUES %6
    // to
    //   %7 = G_MERGE_VALUES %17, %18
    //   %8 = G_MERGE_VALUES %19, %20

    const unsigned NumRegs = NumMergeRegs / NumDefs;
    for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
      SmallVector<Register, 8> Regs;
      for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
           ++j, ++Idx)
        Regs.push_back(MergeI->getOperand(Idx).getReg());

      Register DefReg = MI.getReg(DefIdx);
      Builder.buildMerge(DefReg, Regs);
      UpdatedDefs.push_back(DefReg);
    }

  } else {
    LLT MergeSrcTy = MRI.getType(MergeI->getOperand(1).getReg());

    if (!ConvertOp && DestTy != MergeSrcTy)
      ConvertOp = TargetOpcode::G_BITCAST;

    if (ConvertOp) {
      Builder.setInstr(MI);

      for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
        Register DefReg = MI.getOperand(Idx).getReg();
        Register MergeSrc = MergeI->getOperand(Idx + 1).getReg();

        if (!MRI.use_empty(DefReg)) {
          Builder.buildInstr(ConvertOp, {DefReg}, {MergeSrc});
          UpdatedDefs.push_back(DefReg);
        }
      }

      markInstAndDefDead(MI, *MergeI, DeadInsts);
      return true;
    }

    assert(DestTy == MergeSrcTy &&(static_cast <bool> (DestTy == MergeSrcTy && "Bitcast and the other kinds of conversions should "
 "have happened earlier") ? void (0) : __assert_fail ("DestTy == MergeSrcTy && \"Bitcast and the other kinds of conversions should \" \"have happened earlier\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1000, __extension__ __PRETTY_FUNCTION__))
           "Bitcast and the other kinds of conversions should "(static_cast <bool> (DestTy == MergeSrcTy && "Bitcast and the other kinds of conversions should "
 "have happened earlier") ? void (0) : __assert_fail ("DestTy == MergeSrcTy && \"Bitcast and the other kinds of conversions should \" \"have happened earlier\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1000, __extension__ __PRETTY_FUNCTION__))
           "have happened earlier")(static_cast <bool> (DestTy == MergeSrcTy && "Bitcast and the other kinds of conversions should "
 "have happened earlier") ? void (0) : __assert_fail ("DestTy == MergeSrcTy && \"Bitcast and the other kinds of conversions should \" \"have happened earlier\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1000, __extension__ __PRETTY_FUNCTION__));

    Builder.setInstr(MI);
    for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
      Register DstReg = MI.getOperand(Idx).getReg();
      Register SrcReg = MergeI->getOperand(Idx + 1).getReg();
      replaceRegOrBuildCopy(DstReg, SrcReg, MRI, Builder, UpdatedDefs,
                            Observer);
    }
  }

  markInstAndDefDead(MI, *MergeI, DeadInsts);
  return true;
}

bool tryCombineExtract(MachineInstr &MI,
                       SmallVectorImpl<MachineInstr *> &DeadInsts,
                       SmallVectorImpl<Register> &UpdatedDefs) {
  assert(MI.getOpcode() == TargetOpcode::G_EXTRACT)(static_cast <bool> (MI.getOpcode() == TargetOpcode::G_EXTRACT
) ? void (0) : __assert_fail ("MI.getOpcode() == TargetOpcode::G_EXTRACT"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1018, __extension__ __PRETTY_FUNCTION__));

  // Try to use the source registers from a G_MERGE_VALUES
  //
  // %2 = G_MERGE_VALUES %0, %1
  // %3 = G_EXTRACT %2, N
  // =>
  //
  // for N < %2.getSizeInBits() / 2
  //     %3 = G_EXTRACT %0, N
  //
  // for N >= %2.getSizeInBits() / 2
  //    %3 = G_EXTRACT %1, (N - %0.getSizeInBits()

  Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
  MachineInstr *MergeI = MRI.getVRegDef(SrcReg);
  if (!MergeI || !isa<GMergeLikeOp>(MergeI))
    return false;

  Register DstReg = MI.getOperand(0).getReg();
  LLT DstTy = MRI.getType(DstReg);
  LLT SrcTy = MRI.getType(SrcReg);

  // TODO: Do we need to check if the resulting extract is supported?
  unsigned ExtractDstSize = DstTy.getSizeInBits();
  unsigned Offset = MI.getOperand(2).getImm();
  unsigned NumMergeSrcs = MergeI->getNumOperands() - 1;
  unsigned MergeSrcSize = SrcTy.getSizeInBits() / NumMergeSrcs;
  unsigned MergeSrcIdx = Offset / MergeSrcSize;

  // Compute the offset of the last bit the extract needs.
  unsigned EndMergeSrcIdx = (Offset + ExtractDstSize - 1) / MergeSrcSize;

  // Can't handle the case where the extract spans multiple inputs.
  if (MergeSrcIdx != EndMergeSrcIdx)
    return false;

  // TODO: We could modify MI in place in most cases.
  Builder.setInstr(MI);
  Builder.buildExtract(DstReg, MergeI->getOperand(MergeSrcIdx + 1).getReg(),
                       Offset - MergeSrcIdx * MergeSrcSize);
  UpdatedDefs.push_back(DstReg);
  markInstAndDefDead(MI, *MergeI, DeadInsts);
  return true;
}

/// Try to combine away MI.
/// Returns true if it combined away the MI.
/// Adds instructions that are dead as a result of the combine
/// into DeadInsts, which can include MI.
bool tryCombineInstruction(MachineInstr &MI,
                           SmallVectorImpl<MachineInstr *> &DeadInsts,
                           GISelObserverWrapper &WrapperObserver) {
  // This might be a recursive call, and we might have DeadInsts already
  // populated. To avoid bad things happening later with multiple vreg defs
  // etc, process the dead instructions now if any.
  if (!DeadInsts.empty())
27
←
Taking true branch→
    deleteMarkedDeadInsts(DeadInsts, WrapperObserver);

  // Put here every vreg that was redefined in such a way that it's at least
  // possible that one (or more) of its users (immediate or COPY-separated)
  // could become artifact combinable with the new definition (or the
  // instruction reachable from it through a chain of copies if any).
  SmallVector<Register, 4> UpdatedDefs;
  bool Changed = false;
  switch (MI.getOpcode()) {
28
←
Control jumps to 'case G_UNMERGE_VALUES:'  at line 1095→
  default:
    return false;
  case TargetOpcode::G_ANYEXT:
    Changed = tryCombineAnyExt(MI, DeadInsts, UpdatedDefs, WrapperObserver);
    break;
  case TargetOpcode::G_ZEXT:
    Changed = tryCombineZExt(MI, DeadInsts, UpdatedDefs, WrapperObserver);
    break;
  case TargetOpcode::G_SEXT:
    Changed = tryCombineSExt(MI, DeadInsts, UpdatedDefs);
    break;
  case TargetOpcode::G_UNMERGE_VALUES:
    Changed = tryCombineUnmergeValues(cast<GUnmerge>(MI), DeadInsts,
29
←
'MI' is a 'GUnmerge'→
30
←
Calling 'LegalizationArtifactCombiner::tryCombineUnmergeValues'→
                                      UpdatedDefs, WrapperObserver);
    break;
  case TargetOpcode::G_MERGE_VALUES:
  case TargetOpcode::G_BUILD_VECTOR:
  case TargetOpcode::G_CONCAT_VECTORS:
    // If any of the users of this merge are an unmerge, then add them to the
    // artifact worklist in case there's folding that can be done looking up.
    for (MachineInstr &U : MRI.use_instructions(MI.getOperand(0).getReg())) {
      if (U.getOpcode() == TargetOpcode::G_UNMERGE_VALUES ||
          U.getOpcode() == TargetOpcode::G_TRUNC) {
        UpdatedDefs.push_back(MI.getOperand(0).getReg());
        break;
      }
    }
    break;
  case TargetOpcode::G_EXTRACT:
    Changed = tryCombineExtract(MI, DeadInsts, UpdatedDefs);
    break;
  case TargetOpcode::G_TRUNC:
    Changed = tryCombineTrunc(MI, DeadInsts, UpdatedDefs, WrapperObserver);
    if (!Changed) {
      // Try to combine truncates away even if they are legal. As all artifact
      // combines at the moment look only "up" the def-use chains, we achieve
      // that by throwing truncates' users (with look through copies) into the
      // ArtifactList again.
      UpdatedDefs.push_back(MI.getOperand(0).getReg());
    }
    break;
  }
  // If the main loop through the ArtifactList found at least one combinable
  // pair of artifacts, not only combine it away (as done above), but also
  // follow the def-use chain from there to combine everything that can be
  // combined within this def-use chain of artifacts.
  while (!UpdatedDefs.empty()) {
    Register NewDef = UpdatedDefs.pop_back_val();
    assert(NewDef.isVirtual() && "Unexpected redefinition of a physreg")(static_cast <bool> (NewDef.isVirtual() && "Unexpected redefinition of a physreg"
) ? void (0) : __assert_fail ("NewDef.isVirtual() && \"Unexpected redefinition of a physreg\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1132, __extension__ __PRETTY_FUNCTION__));
    for (MachineInstr &Use : MRI.use_instructions(NewDef)) {
      switch (Use.getOpcode()) {
      // Keep this list in sync with the list of all artifact combines.
      case TargetOpcode::G_ANYEXT:
      case TargetOpcode::G_ZEXT:
      case TargetOpcode::G_SEXT:
      case TargetOpcode::G_UNMERGE_VALUES:
      case TargetOpcode::G_EXTRACT:
      case TargetOpcode::G_TRUNC:
        // Adding Use to ArtifactList.
        WrapperObserver.changedInstr(Use);
        break;
      case TargetOpcode::COPY: {
        Register Copy = Use.getOperand(0).getReg();
        if (Copy.isVirtual())
          UpdatedDefs.push_back(Copy);
        break;
      }
      default:
        // If we do not have an artifact combine for the opcode, there is no
        // point in adding it to the ArtifactList as nothing interesting will
        // be done to it anyway.
        break;
      }
    }
  }
  return Changed;
}

1162private:
static Register getArtifactSrcReg(const MachineInstr &MI) {
  switch (MI.getOpcode()) {
  case TargetOpcode::COPY:
  case TargetOpcode::G_TRUNC:
  case TargetOpcode::G_ZEXT:
  case TargetOpcode::G_ANYEXT:
  case TargetOpcode::G_SEXT:
  case TargetOpcode::G_EXTRACT:
    return MI.getOperand(1).getReg();
  case TargetOpcode::G_UNMERGE_VALUES:
    return MI.getOperand(MI.getNumOperands() - 1).getReg();
  default:
    llvm_unreachable("Not a legalization artifact happen")::llvm::llvm_unreachable_internal("Not a legalization artifact happen"
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1175);
  }
}

/// Mark a def of one of MI's original operands, DefMI, as dead if changing MI
/// (either by killing it or changing operands) results in DefMI being dead
/// too. In-between COPYs or artifact-casts are also collected if they are
/// dead.
/// MI is not marked dead.
void markDefDead(MachineInstr &MI, MachineInstr &DefMI,
                 SmallVectorImpl<MachineInstr *> &DeadInsts,
                 unsigned DefIdx = 0) {
  // Collect all the copy instructions that are made dead, due to deleting
  // this instruction. Collect all of them until the Trunc(DefMI).
  // Eg,
  // %1(s1) = G_TRUNC %0(s32)
  // %2(s1) = COPY %1(s1)
  // %3(s1) = COPY %2(s1)
  // %4(s32) = G_ANYEXT %3(s1)
  // In this case, we would have replaced %4 with a copy of %0,
  // and as a result, %3, %2, %1 are dead.
  MachineInstr *PrevMI = &MI;
  while (PrevMI != &DefMI) {
    Register PrevRegSrc = getArtifactSrcReg(*PrevMI);

    MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
    if (MRI.hasOneUse(PrevRegSrc)) {
      if (TmpDef != &DefMI) {
        assert((TmpDef->getOpcode() == TargetOpcode::COPY ||(static_cast <bool> ((TmpDef->getOpcode() == TargetOpcode
::COPY || isArtifactCast(TmpDef->getOpcode())) && "Expecting copy or artifact cast here"
) ? void (0) : __assert_fail ("(TmpDef->getOpcode() == TargetOpcode::COPY || isArtifactCast(TmpDef->getOpcode())) && \"Expecting copy or artifact cast here\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1205, __extension__ __PRETTY_FUNCTION__))
                isArtifactCast(TmpDef->getOpcode())) &&(static_cast <bool> ((TmpDef->getOpcode() == TargetOpcode
::COPY || isArtifactCast(TmpDef->getOpcode())) && "Expecting copy or artifact cast here"
) ? void (0) : __assert_fail ("(TmpDef->getOpcode() == TargetOpcode::COPY || isArtifactCast(TmpDef->getOpcode())) && \"Expecting copy or artifact cast here\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1205, __extension__ __PRETTY_FUNCTION__))
               "Expecting copy or artifact cast here")(static_cast <bool> ((TmpDef->getOpcode() == TargetOpcode
::COPY || isArtifactCast(TmpDef->getOpcode())) && "Expecting copy or artifact cast here"
) ? void (0) : __assert_fail ("(TmpDef->getOpcode() == TargetOpcode::COPY || isArtifactCast(TmpDef->getOpcode())) && \"Expecting copy or artifact cast here\""
, "llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
, 1205, __extension__ __PRETTY_FUNCTION__));

        DeadInsts.push_back(TmpDef);
      }
    } else
      break;
    PrevMI = TmpDef;
  }

  if (PrevMI == &DefMI) {
    unsigned I = 0;
    bool IsDead = true;
    for (MachineOperand &Def : DefMI.defs()) {
      if (I != DefIdx) {
        if (!MRI.use_empty(Def.getReg())) {
          IsDead = false;
          break;
        }
      } else {
        if (!MRI.hasOneUse(DefMI.getOperand(DefIdx).getReg()))
          break;
      }

      ++I;
    }

    if (IsDead)
      DeadInsts.push_back(&DefMI);
  }
}

/// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
/// dead due to MI being killed, then mark DefMI as dead too.
/// Some of the combines (extends(trunc)), try to walk through redundant
/// copies in between the extends and the truncs, and this attempts to collect
/// the in between copies if they're dead.
void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
                        SmallVectorImpl<MachineInstr *> &DeadInsts,
                        unsigned DefIdx = 0) {
  DeadInsts.push_back(&MI);
  markDefDead(MI, DefMI, DeadInsts, DefIdx);
}

/// Erase the dead instructions in the list and call the observer hooks.
/// Normally the Legalizer will deal with erasing instructions that have been
/// marked dead. However, for the trunc(ext(x)) cases we can end up trying to
/// process instructions which have been marked dead, but otherwise break the
/// MIR by introducing multiple vreg defs. For those cases, allow the combines
/// to explicitly delete the instructions before we run into trouble.
void deleteMarkedDeadInsts(SmallVectorImpl<MachineInstr *> &DeadInsts,
                           GISelObserverWrapper &WrapperObserver) {
  for (auto *DeadMI : DeadInsts) {
    LLVM_DEBUG(dbgs() << *DeadMI << "Is dead, eagerly deleting\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("legalizer")) { dbgs() << *DeadMI << "Is dead, eagerly deleting\n"
; } } while (false);
    WrapperObserver.erasingInstr(*DeadMI);
    DeadMI->eraseFromParent();
  }
  DeadInsts.clear();
}

/// Checks if the target legalizer info has specified anything about the
/// instruction, or if unsupported.
bool isInstUnsupported(const LegalityQuery &Query) const {
  using namespace LegalizeActions;
  auto Step = LI.getAction(Query);
  return Step.Action == Unsupported || Step.Action == NotFound;
}

bool isInstLegal(const LegalityQuery &Query) const {
  return LI.getAction(Query).Action == LegalizeActions::Legal;
}

bool isConstantUnsupported(LLT Ty) const {
  if (!Ty.isVector())
    return isInstUnsupported({TargetOpcode::G_CONSTANT, {Ty}});

  LLT EltTy = Ty.getElementType();
  return isInstUnsupported({TargetOpcode::G_CONSTANT, {EltTy}}) ||
         isInstUnsupported({TargetOpcode::G_BUILD_VECTOR, {Ty, EltTy}});
}

/// Looks through copy instructions and returns the actual
/// source register.
Register lookThroughCopyInstrs(Register Reg) {
  using namespace llvm::MIPatternMatch;

  Register TmpReg;
  while (mi_match(Reg, MRI, m_Copy(m_Reg(TmpReg)))) {
    if (MRI.getType(TmpReg).isValid())
      Reg = TmpReg;
    else
      break;
  }
  return Reg;
}
1299};

1301} // namespace llvm

1303#endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H