blob: 8fc4d955b5a323934ef61723a5127afbe106e498 [file] [log] [blame]
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +00001//===--- HexagonEarlyIfConv.cpp -------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This implements a Hexagon-specific if-conversion pass that runs on the
11// SSA form.
12// In SSA it is not straightforward to represent instructions that condi-
13// tionally define registers, since a conditionally-defined register may
14// only be used under the same condition on which the definition was based.
15// To avoid complications of this nature, this patch will only generate
16// predicated stores, and speculate other instructions from the "if-conver-
17// ted" block.
18// The code will recognize CFG patterns where a block with a conditional
19// branch "splits" into a "true block" and a "false block". Either of these
20// could be omitted (in case of a triangle, for example).
21// If after conversion of the side block(s) the CFG allows it, the resul-
22// ting blocks may be merged. If the "join" block contained PHI nodes, they
23// will be replaced with MUX (or MUX-like) instructions to maintain the
24// semantics of the PHI.
25//
26// Example:
27//
28// %vreg40<def> = L2_loadrub_io %vreg39<kill>, 1
29// %vreg41<def> = S2_tstbit_i %vreg40<kill>, 0
30// J2_jumpt %vreg41<kill>, <BB#5>, %PC<imp-def,dead>
31// J2_jump <BB#4>, %PC<imp-def,dead>
32// Successors according to CFG: BB#4(62) BB#5(62)
33//
34// BB#4: derived from LLVM BB %if.then
35// Predecessors according to CFG: BB#3
36// %vreg11<def> = A2_addp %vreg6, %vreg10
37// S2_storerd_io %vreg32, 16, %vreg11
38// Successors according to CFG: BB#5
39//
40// BB#5: derived from LLVM BB %if.end
41// Predecessors according to CFG: BB#3 BB#4
42// %vreg12<def> = PHI %vreg6, <BB#3>, %vreg11, <BB#4>
43// %vreg13<def> = A2_addp %vreg7, %vreg12
44// %vreg42<def> = C2_cmpeqi %vreg9, 10
45// J2_jumpf %vreg42<kill>, <BB#3>, %PC<imp-def,dead>
46// J2_jump <BB#6>, %PC<imp-def,dead>
47// Successors according to CFG: BB#6(4) BB#3(124)
48//
49// would become:
50//
51// %vreg40<def> = L2_loadrub_io %vreg39<kill>, 1
52// %vreg41<def> = S2_tstbit_i %vreg40<kill>, 0
53// spec-> %vreg11<def> = A2_addp %vreg6, %vreg10
54// pred-> S2_pstorerdf_io %vreg41, %vreg32, 16, %vreg11
55// %vreg46<def> = MUX64_rr %vreg41, %vreg6, %vreg11
56// %vreg13<def> = A2_addp %vreg7, %vreg46
57// %vreg42<def> = C2_cmpeqi %vreg9, 10
58// J2_jumpf %vreg42<kill>, <BB#3>, %PC<imp-def,dead>
59// J2_jump <BB#6>, %PC<imp-def,dead>
60// Successors according to CFG: BB#6 BB#3
61
62#define DEBUG_TYPE "hexagon-eif"
63
64#include "llvm/ADT/DenseSet.h"
65#include "llvm/ADT/SetVector.h"
66#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
67#include "llvm/CodeGen/MachineDominators.h"
68#include "llvm/CodeGen/MachineFunctionPass.h"
69#include "llvm/CodeGen/MachineInstrBuilder.h"
70#include "llvm/CodeGen/MachineLoopInfo.h"
71#include "llvm/CodeGen/MachineRegisterInfo.h"
72#include "llvm/CodeGen/Passes.h"
73#include "llvm/Support/CommandLine.h"
74#include "llvm/Support/Debug.h"
75#include "llvm/Support/raw_ostream.h"
76#include "llvm/Target/TargetInstrInfo.h"
77#include "llvm/Target/TargetMachine.h"
78#include "HexagonTargetMachine.h"
79
80#include <functional>
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +000081
82using namespace llvm;
83
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +000084namespace llvm {
85 FunctionPass *createHexagonEarlyIfConversion();
86 void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry);
87}
88
89namespace {
Krzysztof Parzyszek8d2b2cf2015-10-06 18:29:36 +000090 cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden,
91 cl::init(false), cl::desc("Enable branch probability info"));
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +000092 cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden,
Krzysztof Parzyszek8d2b2cf2015-10-06 18:29:36 +000093 cl::desc("Size limit in Hexagon early if-conversion"));
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +000094
95 struct PrintMB {
96 PrintMB(const MachineBasicBlock *B) : MB(B) {}
97 const MachineBasicBlock *MB;
98 };
99 raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) {
100 if (!P.MB)
101 return OS << "<none>";
102 return OS << '#' << P.MB->getNumber();
103 }
104
105 struct FlowPattern {
106 FlowPattern() : SplitB(0), TrueB(0), FalseB(0), JoinB(0), PredR(0) {}
107 FlowPattern(MachineBasicBlock *B, unsigned PR, MachineBasicBlock *TB,
108 MachineBasicBlock *FB, MachineBasicBlock *JB)
109 : SplitB(B), TrueB(TB), FalseB(FB), JoinB(JB), PredR(PR) {}
110
111 MachineBasicBlock *SplitB;
112 MachineBasicBlock *TrueB, *FalseB, *JoinB;
113 unsigned PredR;
114 };
115 struct PrintFP {
116 PrintFP(const FlowPattern &P, const TargetRegisterInfo &T)
117 : FP(P), TRI(T) {}
118 const FlowPattern &FP;
119 const TargetRegisterInfo &TRI;
120 friend raw_ostream &operator<< (raw_ostream &OS, const PrintFP &P);
121 };
122 raw_ostream &operator<<(raw_ostream &OS,
123 const PrintFP &P) LLVM_ATTRIBUTE_UNUSED;
124 raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) {
125 OS << "{ SplitB:" << PrintMB(P.FP.SplitB)
126 << ", PredR:" << PrintReg(P.FP.PredR, &P.TRI)
127 << ", TrueB:" << PrintMB(P.FP.TrueB) << ", FalseB:"
128 << PrintMB(P.FP.FalseB)
129 << ", JoinB:" << PrintMB(P.FP.JoinB) << " }";
130 return OS;
131 }
132
133 class HexagonEarlyIfConversion : public MachineFunctionPass {
134 public:
135 static char ID;
136 HexagonEarlyIfConversion() : MachineFunctionPass(ID),
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000137 HII(0), TRI(0), MFN(0), MRI(0), MDT(0), MLI(0) {
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000138 initializeHexagonEarlyIfConversionPass(*PassRegistry::getPassRegistry());
139 }
140 const char *getPassName() const override {
141 return "Hexagon early if conversion";
142 }
143 void getAnalysisUsage(AnalysisUsage &AU) const override {
144 AU.addRequired<MachineBranchProbabilityInfo>();
145 AU.addRequired<MachineDominatorTree>();
146 AU.addPreserved<MachineDominatorTree>();
147 AU.addRequired<MachineLoopInfo>();
148 MachineFunctionPass::getAnalysisUsage(AU);
149 }
150 bool runOnMachineFunction(MachineFunction &MF) override;
151
152 private:
153 typedef DenseSet<MachineBasicBlock*> BlockSetType;
154
155 bool isPreheader(const MachineBasicBlock *B) const;
156 bool matchFlowPattern(MachineBasicBlock *B, MachineLoop *L,
157 FlowPattern &FP);
158 bool visitBlock(MachineBasicBlock *B, MachineLoop *L);
159 bool visitLoop(MachineLoop *L);
160
161 bool hasEHLabel(const MachineBasicBlock *B) const;
162 bool hasUncondBranch(const MachineBasicBlock *B) const;
163 bool isValidCandidate(const MachineBasicBlock *B) const;
164 bool usesUndefVReg(const MachineInstr *MI) const;
165 bool isValid(const FlowPattern &FP) const;
166 unsigned countPredicateDefs(const MachineBasicBlock *B) const;
167 unsigned computePhiCost(MachineBasicBlock *B) const;
168 bool isProfitable(const FlowPattern &FP) const;
169 bool isPredicableStore(const MachineInstr *MI) const;
170 bool isSafeToSpeculate(const MachineInstr *MI) const;
171
172 unsigned getCondStoreOpcode(unsigned Opc, bool IfTrue) const;
173 void predicateInstr(MachineBasicBlock *ToB, MachineBasicBlock::iterator At,
174 MachineInstr *MI, unsigned PredR, bool IfTrue);
175 void predicateBlockNB(MachineBasicBlock *ToB,
176 MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
177 unsigned PredR, bool IfTrue);
178
179 void updatePhiNodes(MachineBasicBlock *WhereB, const FlowPattern &FP);
180 void convert(const FlowPattern &FP);
181
182 void removeBlock(MachineBasicBlock *B);
183 void eliminatePhis(MachineBasicBlock *B);
184 void replacePhiEdges(MachineBasicBlock *OldB, MachineBasicBlock *NewB);
185 void mergeBlocks(MachineBasicBlock *PredB, MachineBasicBlock *SuccB);
186 void simplifyFlowGraph(const FlowPattern &FP);
187
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000188 const HexagonInstrInfo *HII;
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000189 const TargetRegisterInfo *TRI;
190 MachineFunction *MFN;
191 MachineRegisterInfo *MRI;
192 MachineDominatorTree *MDT;
193 MachineLoopInfo *MLI;
194 BlockSetType Deleted;
195 const MachineBranchProbabilityInfo *MBPI;
196 };
197
198 char HexagonEarlyIfConversion::ID = 0;
199}
200
201INITIALIZE_PASS(HexagonEarlyIfConversion, "hexagon-eif",
202 "Hexagon early if conversion", false, false)
203
204bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const {
205 if (B->succ_size() != 1)
206 return false;
207 MachineBasicBlock *SB = *B->succ_begin();
208 MachineLoop *L = MLI->getLoopFor(SB);
209 return L && SB == L->getHeader();
210}
211
212
213bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B,
214 MachineLoop *L, FlowPattern &FP) {
215 DEBUG(dbgs() << "Checking flow pattern at BB#" << B->getNumber() << "\n");
216
217 // Interested only in conditional branches, no .new, no new-value, etc.
218 // Check the terminators directly, it's easier than handling all responses
219 // from AnalyzeBranch.
220 MachineBasicBlock *TB = 0, *FB = 0;
221 MachineBasicBlock::const_iterator T1I = B->getFirstTerminator();
222 if (T1I == B->end())
223 return false;
224 unsigned Opc = T1I->getOpcode();
225 if (Opc != Hexagon::J2_jumpt && Opc != Hexagon::J2_jumpf)
226 return false;
227 unsigned PredR = T1I->getOperand(0).getReg();
228
229 // Get the layout successor, or 0 if B does not have one.
230 MachineFunction::iterator NextBI = std::next(MachineFunction::iterator(B));
231 MachineBasicBlock *NextB = (NextBI != MFN->end()) ? &*NextBI : 0;
232
233 MachineBasicBlock *T1B = T1I->getOperand(1).getMBB();
234 MachineBasicBlock::const_iterator T2I = std::next(T1I);
235 // The second terminator should be an unconditional branch.
236 assert(T2I == B->end() || T2I->getOpcode() == Hexagon::J2_jump);
237 MachineBasicBlock *T2B = (T2I == B->end()) ? NextB
238 : T2I->getOperand(0).getMBB();
239 if (T1B == T2B) {
240 // XXX merge if T1B == NextB, or convert branch to unconditional.
241 // mark as diamond with both sides equal?
242 return false;
243 }
244 // Loop could be null for both.
245 if (MLI->getLoopFor(T1B) != L || MLI->getLoopFor(T2B) != L)
246 return false;
247
248 // Record the true/false blocks in such a way that "true" means "if (PredR)",
249 // and "false" means "if (!PredR)".
250 if (Opc == Hexagon::J2_jumpt)
251 TB = T1B, FB = T2B;
252 else
253 TB = T2B, FB = T1B;
254
255 if (!MDT->properlyDominates(B, TB) || !MDT->properlyDominates(B, FB))
256 return false;
257
258 // Detect triangle first. In case of a triangle, one of the blocks TB/FB
259 // can fall through into the other, in other words, it will be executed
260 // in both cases. We only want to predicate the block that is executed
261 // conditionally.
262 unsigned TNP = TB->pred_size(), FNP = FB->pred_size();
263 unsigned TNS = TB->succ_size(), FNS = FB->succ_size();
264
265 // A block is predicable if it has one predecessor (it must be B), and
266 // it has a single successor. In fact, the block has to end either with
267 // an unconditional branch (which can be predicated), or with a fall-
268 // through.
269 bool TOk = (TNP == 1) && (TNS == 1);
270 bool FOk = (FNP == 1) && (FNS == 1);
271
272 // If neither is predicable, there is nothing interesting.
273 if (!TOk && !FOk)
274 return false;
275
276 MachineBasicBlock *TSB = (TNS > 0) ? *TB->succ_begin() : 0;
277 MachineBasicBlock *FSB = (FNS > 0) ? *FB->succ_begin() : 0;
278 MachineBasicBlock *JB = 0;
279
280 if (TOk) {
281 if (FOk) {
282 if (TSB == FSB)
283 JB = TSB;
284 // Diamond: "if (P) then TB; else FB;".
285 } else {
286 // TOk && !FOk
287 if (TSB == FB) {
288 JB = FB;
289 FB = 0;
290 }
291 }
292 } else {
293 // !TOk && FOk (at least one must be true by now).
294 if (FSB == TB) {
295 JB = TB;
296 TB = 0;
297 }
298 }
299 // Don't try to predicate loop preheaders.
300 if ((TB && isPreheader(TB)) || (FB && isPreheader(FB))) {
301 DEBUG(dbgs() << "One of blocks " << PrintMB(TB) << ", " << PrintMB(FB)
302 << " is a loop preheader. Skipping.\n");
303 return false;
304 }
305
306 FP = FlowPattern(B, PredR, TB, FB, JB);
307 DEBUG(dbgs() << "Detected " << PrintFP(FP, *TRI) << "\n");
308 return true;
309}
310
311
312// KLUDGE: HexagonInstrInfo::AnalyzeBranch won't work on a block that
313// contains EH_LABEL.
314bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const {
315 for (auto &I : *B)
316 if (I.isEHLabel())
317 return true;
318 return false;
319}
320
321
322// KLUDGE: HexagonInstrInfo::AnalyzeBranch may be unable to recognize
323// that a block can never fall-through.
324bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B)
325 const {
326 MachineBasicBlock::const_iterator I = B->getFirstTerminator(), E = B->end();
327 while (I != E) {
328 if (I->isBarrier())
329 return true;
330 ++I;
331 }
332 return false;
333}
334
335
336bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B)
337 const {
338 if (!B)
339 return true;
340 if (B->isEHPad() || B->hasAddressTaken())
341 return false;
342 if (B->succ_size() == 0)
343 return false;
344
345 for (auto &MI : *B) {
346 if (MI.isDebugValue())
347 continue;
348 if (MI.isConditionalBranch())
349 return false;
350 unsigned Opc = MI.getOpcode();
351 bool IsJMP = (Opc == Hexagon::J2_jump);
352 if (!isPredicableStore(&MI) && !IsJMP && !isSafeToSpeculate(&MI))
353 return false;
354 // Look for predicate registers defined by this instruction. It's ok
355 // to speculate such an instruction, but the predicate register cannot
356 // be used outside of this block (or else it won't be possible to
357 // update the use of it after predication). PHI uses will be updated
358 // to use a result of a MUX, and a MUX cannot be created for predicate
359 // registers.
Duncan P. N. Exon Smithf9ab4162016-02-27 17:05:33 +0000360 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000361 if (!MO->isReg() || !MO->isDef())
362 continue;
363 unsigned R = MO->getReg();
364 if (!TargetRegisterInfo::isVirtualRegister(R))
365 continue;
366 if (MRI->getRegClass(R) != &Hexagon::PredRegsRegClass)
367 continue;
368 for (auto U = MRI->use_begin(R); U != MRI->use_end(); ++U)
369 if (U->getParent()->isPHI())
370 return false;
371 }
372 }
373 return true;
374}
375
376
377bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const {
Duncan P. N. Exon Smithf9ab4162016-02-27 17:05:33 +0000378 for (ConstMIOperands MO(*MI); MO.isValid(); ++MO) {
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000379 if (!MO->isReg() || !MO->isUse())
380 continue;
381 unsigned R = MO->getReg();
382 if (!TargetRegisterInfo::isVirtualRegister(R))
383 continue;
384 const MachineInstr *DefI = MRI->getVRegDef(R);
385 // "Undefined" virtual registers are actually defined via IMPLICIT_DEF.
386 assert(DefI && "Expecting a reaching def in MRI");
387 if (DefI->isImplicitDef())
388 return true;
389 }
390 return false;
391}
392
393
394bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const {
395 if (hasEHLabel(FP.SplitB)) // KLUDGE: see function definition
396 return false;
397 if (FP.TrueB && !isValidCandidate(FP.TrueB))
398 return false;
399 if (FP.FalseB && !isValidCandidate(FP.FalseB))
400 return false;
401 // Check the PHIs in the join block. If any of them use a register
402 // that is defined as IMPLICIT_DEF, do not convert this. This can
403 // legitimately happen if one side of the split never executes, but
404 // the compiler is unable to prove it. That side may then seem to
405 // provide an "undef" value to the join block, however it will never
406 // execute at run-time. If we convert this case, the "undef" will
407 // be used in a MUX instruction, and that may seem like actually
408 // using an undefined value to other optimizations. This could lead
409 // to trouble further down the optimization stream, cause assertions
410 // to fail, etc.
411 if (FP.JoinB) {
412 const MachineBasicBlock &B = *FP.JoinB;
413 for (auto &MI : B) {
414 if (!MI.isPHI())
415 break;
416 if (usesUndefVReg(&MI))
417 return false;
418 unsigned DefR = MI.getOperand(0).getReg();
419 const TargetRegisterClass *RC = MRI->getRegClass(DefR);
420 if (RC == &Hexagon::PredRegsRegClass)
421 return false;
422 }
423 }
424 return true;
425}
426
427
428unsigned HexagonEarlyIfConversion::computePhiCost(MachineBasicBlock *B) const {
429 assert(B->pred_size() <= 2);
430 if (B->pred_size() < 2)
431 return 0;
432
433 unsigned Cost = 0;
434 MachineBasicBlock::const_iterator I, E = B->getFirstNonPHI();
435 for (I = B->begin(); I != E; ++I) {
436 const MachineOperand &RO1 = I->getOperand(1);
437 const MachineOperand &RO3 = I->getOperand(3);
438 assert(RO1.isReg() && RO3.isReg());
439 // Must have a MUX if the phi uses a subregister.
440 if (RO1.getSubReg() != 0 || RO3.getSubReg() != 0) {
441 Cost++;
442 continue;
443 }
444 MachineInstr *Def1 = MRI->getVRegDef(RO1.getReg());
445 MachineInstr *Def3 = MRI->getVRegDef(RO3.getReg());
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000446 if (!HII->isPredicable(*Def1) || !HII->isPredicable(*Def3))
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000447 Cost++;
448 }
449 return Cost;
450}
451
452
453unsigned HexagonEarlyIfConversion::countPredicateDefs(
454 const MachineBasicBlock *B) const {
455 unsigned PredDefs = 0;
456 for (auto &MI : *B) {
Duncan P. N. Exon Smithf9ab4162016-02-27 17:05:33 +0000457 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000458 if (!MO->isReg() || !MO->isDef())
459 continue;
460 unsigned R = MO->getReg();
461 if (!TargetRegisterInfo::isVirtualRegister(R))
462 continue;
463 if (MRI->getRegClass(R) == &Hexagon::PredRegsRegClass)
464 PredDefs++;
465 }
466 }
467 return PredDefs;
468}
469
470
471bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const {
472 if (FP.TrueB && FP.FalseB) {
473
474 // Do not IfCovert if the branch is one sided.
475 if (MBPI) {
476 BranchProbability Prob(9, 10);
477 if (MBPI->getEdgeProbability(FP.SplitB, FP.TrueB) > Prob)
478 return false;
479 if (MBPI->getEdgeProbability(FP.SplitB, FP.FalseB) > Prob)
480 return false;
481 }
482
483 // If both sides are predicable, convert them if they join, and the
484 // join block has no other predecessors.
485 MachineBasicBlock *TSB = *FP.TrueB->succ_begin();
486 MachineBasicBlock *FSB = *FP.FalseB->succ_begin();
487 if (TSB != FSB)
488 return false;
489 if (TSB->pred_size() != 2)
490 return false;
491 }
492
493 // Calculate the total size of the predicated blocks.
494 // Assume instruction counts without branches to be the approximation of
495 // the code size. If the predicated blocks are smaller than a packet size,
496 // approximate the spare room in the packet that could be filled with the
497 // predicated/speculated instructions.
498 unsigned TS = 0, FS = 0, Spare = 0;
499 if (FP.TrueB) {
500 TS = std::distance(FP.TrueB->begin(), FP.TrueB->getFirstTerminator());
501 if (TS < HEXAGON_PACKET_SIZE)
502 Spare += HEXAGON_PACKET_SIZE-TS;
503 }
504 if (FP.FalseB) {
505 FS = std::distance(FP.FalseB->begin(), FP.FalseB->getFirstTerminator());
506 if (FS < HEXAGON_PACKET_SIZE)
507 Spare += HEXAGON_PACKET_SIZE-TS;
508 }
509 unsigned TotalIn = TS+FS;
510 DEBUG(dbgs() << "Total number of instructions to be predicated/speculated: "
511 << TotalIn << ", spare room: " << Spare << "\n");
512 if (TotalIn >= SizeLimit+Spare)
513 return false;
514
515 // Count the number of PHI nodes that will need to be updated (converted
516 // to MUX). Those can be later converted to predicated instructions, so
517 // they aren't always adding extra cost.
518 // KLUDGE: Also, count the number of predicate register definitions in
519 // each block. The scheduler may increase the pressure of these and cause
520 // expensive spills (e.g. bitmnp01).
521 unsigned TotalPh = 0;
522 unsigned PredDefs = countPredicateDefs(FP.SplitB);
523 if (FP.JoinB) {
524 TotalPh = computePhiCost(FP.JoinB);
525 PredDefs += countPredicateDefs(FP.JoinB);
526 } else {
527 if (FP.TrueB && FP.TrueB->succ_size() > 0) {
528 MachineBasicBlock *SB = *FP.TrueB->succ_begin();
529 TotalPh += computePhiCost(SB);
530 PredDefs += countPredicateDefs(SB);
531 }
532 if (FP.FalseB && FP.FalseB->succ_size() > 0) {
533 MachineBasicBlock *SB = *FP.FalseB->succ_begin();
534 TotalPh += computePhiCost(SB);
535 PredDefs += countPredicateDefs(SB);
536 }
537 }
538 DEBUG(dbgs() << "Total number of extra muxes from converted phis: "
539 << TotalPh << "\n");
540 if (TotalIn+TotalPh >= SizeLimit+Spare)
541 return false;
542
543 DEBUG(dbgs() << "Total number of predicate registers: " << PredDefs << "\n");
544 if (PredDefs > 4)
545 return false;
546
547 return true;
548}
549
550
551bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B,
552 MachineLoop *L) {
553 bool Changed = false;
554
555 // Visit all dominated blocks from the same loop first, then process B.
556 MachineDomTreeNode *N = MDT->getNode(B);
557 typedef GraphTraits<MachineDomTreeNode*> GTN;
558 // We will change CFG/DT during this traversal, so take precautions to
559 // avoid problems related to invalidated iterators. In fact, processing
560 // a child C of B cannot cause another child to be removed, but it can
561 // cause a new child to be added (which was a child of C before C itself
562 // was removed. This new child C, however, would have been processed
563 // prior to processing B, so there is no need to process it again.
564 // Simply keep a list of children of B, and traverse that list.
565 typedef SmallVector<MachineDomTreeNode*,4> DTNodeVectType;
566 DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
567 for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
568 MachineBasicBlock *SB = (*I)->getBlock();
569 if (!Deleted.count(SB))
570 Changed |= visitBlock(SB, L);
571 }
572 // When walking down the dominator tree, we want to traverse through
573 // blocks from nested (other) loops, because they can dominate blocks
574 // that are in L. Skip the non-L blocks only after the tree traversal.
575 if (MLI->getLoopFor(B) != L)
576 return Changed;
577
578 FlowPattern FP;
579 if (!matchFlowPattern(B, L, FP))
580 return Changed;
581
582 if (!isValid(FP)) {
583 DEBUG(dbgs() << "Conversion is not valid\n");
584 return Changed;
585 }
586 if (!isProfitable(FP)) {
587 DEBUG(dbgs() << "Conversion is not profitable\n");
588 return Changed;
589 }
590
591 convert(FP);
592 simplifyFlowGraph(FP);
593 return true;
594}
595
596
597bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) {
598 MachineBasicBlock *HB = L ? L->getHeader() : 0;
599 DEBUG((L ? dbgs() << "Visiting loop H:" << PrintMB(HB)
600 : dbgs() << "Visiting function") << "\n");
601 bool Changed = false;
602 if (L) {
603 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
604 Changed |= visitLoop(*I);
605 }
606
607 MachineBasicBlock *EntryB = GraphTraits<MachineFunction*>::getEntryNode(MFN);
608 Changed |= visitBlock(L ? HB : EntryB, L);
609 return Changed;
610}
611
612
613bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI)
614 const {
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000615 // HexagonInstrInfo::isPredicable will consider these stores are non-
616 // -predicable if the offset would become constant-extended after
617 // predication.
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000618 unsigned Opc = MI->getOpcode();
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000619 switch (Opc) {
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000620 case Hexagon::S2_storerb_io:
621 case Hexagon::S2_storerbnew_io:
622 case Hexagon::S2_storerh_io:
623 case Hexagon::S2_storerhnew_io:
624 case Hexagon::S2_storeri_io:
625 case Hexagon::S2_storerinew_io:
626 case Hexagon::S2_storerd_io:
627 case Hexagon::S4_storeirb_io:
628 case Hexagon::S4_storeirh_io:
629 case Hexagon::S4_storeiri_io:
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000630 return true;
631 }
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000632
633 // TargetInstrInfo::isPredicable takes a non-const pointer.
634 return MI->mayStore() && HII->isPredicable(const_cast<MachineInstr&>(*MI));
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000635}
636
637
638bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI)
639 const {
640 if (MI->mayLoad() || MI->mayStore())
641 return false;
642 if (MI->isCall() || MI->isBarrier() || MI->isBranch())
643 return false;
644 if (MI->hasUnmodeledSideEffects())
645 return false;
646
647 return true;
648}
649
650
651unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc,
652 bool IfTrue) const {
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000653 return HII->getCondOpcode(Opc, !IfTrue);
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000654}
655
656
657void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB,
658 MachineBasicBlock::iterator At, MachineInstr *MI,
659 unsigned PredR, bool IfTrue) {
660 DebugLoc DL;
661 if (At != ToB->end())
662 DL = At->getDebugLoc();
663 else if (!ToB->empty())
664 DL = ToB->back().getDebugLoc();
665
666 unsigned Opc = MI->getOpcode();
667
668 if (isPredicableStore(MI)) {
669 unsigned COpc = getCondStoreOpcode(Opc, IfTrue);
670 assert(COpc);
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000671 MachineInstrBuilder MIB = BuildMI(*ToB, At, DL, HII->get(COpc));
672 MIOperands MO(*MI);
Krzysztof Parzyszek8fb181c2016-08-01 17:55:48 +0000673 if (HII->isPostIncrement(*MI)) {
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000674 MIB.addOperand(*MO);
675 ++MO;
676 }
677 MIB.addReg(PredR);
678 for (; MO.isValid(); ++MO)
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000679 MIB.addOperand(*MO);
680
681 // Set memory references.
682 MachineInstr::mmo_iterator MMOBegin = MI->memoperands_begin();
683 MachineInstr::mmo_iterator MMOEnd = MI->memoperands_end();
684 MIB.setMemRefs(MMOBegin, MMOEnd);
685
686 MI->eraseFromParent();
687 return;
688 }
689
690 if (Opc == Hexagon::J2_jump) {
691 MachineBasicBlock *TB = MI->getOperand(0).getMBB();
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000692 const MCInstrDesc &D = HII->get(IfTrue ? Hexagon::J2_jumpt
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000693 : Hexagon::J2_jumpf);
694 BuildMI(*ToB, At, DL, D)
695 .addReg(PredR)
696 .addMBB(TB);
697 MI->eraseFromParent();
698 return;
699 }
700
701 // Print the offending instruction unconditionally as we are about to
702 // abort.
703 dbgs() << *MI;
704 llvm_unreachable("Unexpected instruction");
705}
706
707
708// Predicate/speculate non-branch instructions from FromB into block ToB.
709// Leave the branches alone, they will be handled later. Btw, at this point
710// FromB should have at most one branch, and it should be unconditional.
711void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB,
712 MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
713 unsigned PredR, bool IfTrue) {
714 DEBUG(dbgs() << "Predicating block " << PrintMB(FromB) << "\n");
715 MachineBasicBlock::iterator End = FromB->getFirstTerminator();
716 MachineBasicBlock::iterator I, NextI;
717
718 for (I = FromB->begin(); I != End; I = NextI) {
719 assert(!I->isPHI());
720 NextI = std::next(I);
721 if (isSafeToSpeculate(&*I))
722 ToB->splice(At, FromB, I);
723 else
724 predicateInstr(ToB, At, &*I, PredR, IfTrue);
725 }
726}
727
728
729void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB,
730 const FlowPattern &FP) {
731 // Visit all PHI nodes in the WhereB block and generate MUX instructions
732 // in the split block. Update the PHI nodes with the values of the MUX.
733 auto NonPHI = WhereB->getFirstNonPHI();
734 for (auto I = WhereB->begin(); I != NonPHI; ++I) {
735 MachineInstr *PN = &*I;
736 // Registers and subregisters corresponding to TrueB, FalseB and SplitB.
737 unsigned TR = 0, TSR = 0, FR = 0, FSR = 0, SR = 0, SSR = 0;
738 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
739 const MachineOperand &RO = PN->getOperand(i), &BO = PN->getOperand(i+1);
740 if (BO.getMBB() == FP.SplitB)
741 SR = RO.getReg(), SSR = RO.getSubReg();
742 else if (BO.getMBB() == FP.TrueB)
743 TR = RO.getReg(), TSR = RO.getSubReg();
744 else if (BO.getMBB() == FP.FalseB)
745 FR = RO.getReg(), FSR = RO.getSubReg();
746 else
747 continue;
748 PN->RemoveOperand(i+1);
749 PN->RemoveOperand(i);
750 }
751 if (TR == 0)
752 TR = SR, TSR = SSR;
753 else if (FR == 0)
754 FR = SR, FSR = SSR;
755 assert(TR && FR);
756
757 using namespace Hexagon;
758 unsigned DR = PN->getOperand(0).getReg();
759 const TargetRegisterClass *RC = MRI->getRegClass(DR);
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000760 unsigned Opc = 0;
761 if (RC == &IntRegsRegClass)
762 Opc = C2_mux;
763 else if (RC == &DoubleRegsRegClass)
764 Opc = MUX64_rr;
765 else if (RC == &VectorRegsRegClass)
766 Opc = VSelectPseudo_V6;
767 else if (RC == &VecDblRegsRegClass)
768 Opc = VSelectDblPseudo_V6;
769 else if (RC == &VectorRegs128BRegClass)
770 Opc = VSelectPseudo_V6_128B;
771 else if (RC == &VecDblRegs128BRegClass)
772 Opc = VSelectDblPseudo_V6_128B;
773 else
774 llvm_unreachable("unexpected register type");
775 const MCInstrDesc &D = HII->get(Opc);
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000776
777 MachineBasicBlock::iterator MuxAt = FP.SplitB->getFirstTerminator();
778 DebugLoc DL;
779 if (MuxAt != FP.SplitB->end())
780 DL = MuxAt->getDebugLoc();
781 unsigned MuxR = MRI->createVirtualRegister(RC);
782 BuildMI(*FP.SplitB, MuxAt, DL, D, MuxR)
783 .addReg(FP.PredR)
784 .addReg(TR, 0, TSR)
785 .addReg(FR, 0, FSR);
786
787 PN->addOperand(MachineOperand::CreateReg(MuxR, false));
788 PN->addOperand(MachineOperand::CreateMBB(FP.SplitB));
789 }
790}
791
792
793void HexagonEarlyIfConversion::convert(const FlowPattern &FP) {
794 MachineBasicBlock *TSB = 0, *FSB = 0;
795 MachineBasicBlock::iterator OldTI = FP.SplitB->getFirstTerminator();
796 assert(OldTI != FP.SplitB->end());
797 DebugLoc DL = OldTI->getDebugLoc();
798
799 if (FP.TrueB) {
800 TSB = *FP.TrueB->succ_begin();
801 predicateBlockNB(FP.SplitB, OldTI, FP.TrueB, FP.PredR, true);
802 }
803 if (FP.FalseB) {
804 FSB = *FP.FalseB->succ_begin();
805 MachineBasicBlock::iterator At = FP.SplitB->getFirstTerminator();
806 predicateBlockNB(FP.SplitB, At, FP.FalseB, FP.PredR, false);
807 }
808
809 // Regenerate new terminators in the split block and update the successors.
810 // First, remember any information that may be needed later and remove the
811 // existing terminators/successors from the split block.
812 MachineBasicBlock *SSB = 0;
813 FP.SplitB->erase(OldTI, FP.SplitB->end());
814 while (FP.SplitB->succ_size() > 0) {
815 MachineBasicBlock *T = *FP.SplitB->succ_begin();
816 // It's possible that the split block had a successor that is not a pre-
817 // dicated block. This could only happen if there was only one block to
818 // be predicated. Example:
819 // split_b:
820 // if (p) jump true_b
821 // jump unrelated2_b
822 // unrelated1_b:
823 // ...
824 // unrelated2_b: ; can have other predecessors, so it's not "false_b"
825 // jump other_b
826 // true_b: ; only reachable from split_b, can be predicated
827 // ...
828 //
829 // Find this successor (SSB) if it exists.
830 if (T != FP.TrueB && T != FP.FalseB) {
831 assert(!SSB);
832 SSB = T;
833 }
834 FP.SplitB->removeSuccessor(FP.SplitB->succ_begin());
835 }
836
837 // Insert new branches and update the successors of the split block. This
838 // may create unconditional branches to the layout successor, etc., but
839 // that will be cleaned up later. For now, make sure that correct code is
840 // generated.
841 if (FP.JoinB) {
842 assert(!SSB || SSB == FP.JoinB);
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000843 BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000844 .addMBB(FP.JoinB);
845 FP.SplitB->addSuccessor(FP.JoinB);
846 } else {
847 bool HasBranch = false;
848 if (TSB) {
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000849 BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jumpt))
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000850 .addReg(FP.PredR)
851 .addMBB(TSB);
852 FP.SplitB->addSuccessor(TSB);
853 HasBranch = true;
854 }
855 if (FSB) {
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000856 const MCInstrDesc &D = HasBranch ? HII->get(Hexagon::J2_jump)
857 : HII->get(Hexagon::J2_jumpf);
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000858 MachineInstrBuilder MIB = BuildMI(*FP.SplitB, FP.SplitB->end(), DL, D);
859 if (!HasBranch)
860 MIB.addReg(FP.PredR);
861 MIB.addMBB(FSB);
862 FP.SplitB->addSuccessor(FSB);
863 }
864 if (SSB) {
865 // This cannot happen if both TSB and FSB are set. [TF]SB are the
866 // successor blocks of the TrueB and FalseB (or null of the TrueB
867 // or FalseB block is null). SSB is the potential successor block
868 // of the SplitB that is neither TrueB nor FalseB.
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000869 BuildMI(*FP.SplitB, FP.SplitB->end(), DL, HII->get(Hexagon::J2_jump))
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000870 .addMBB(SSB);
871 FP.SplitB->addSuccessor(SSB);
872 }
873 }
874
875 // What is left to do is to update the PHI nodes that could have entries
876 // referring to predicated blocks.
877 if (FP.JoinB) {
878 updatePhiNodes(FP.JoinB, FP);
879 } else {
880 if (TSB)
881 updatePhiNodes(TSB, FP);
882 if (FSB)
883 updatePhiNodes(FSB, FP);
884 // Nothing to update in SSB, since SSB's predecessors haven't changed.
885 }
886}
887
888
889void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) {
890 DEBUG(dbgs() << "Removing block " << PrintMB(B) << "\n");
891
892 // Transfer the immediate dominator information from B to its descendants.
893 MachineDomTreeNode *N = MDT->getNode(B);
894 MachineDomTreeNode *IDN = N->getIDom();
895 if (IDN) {
896 MachineBasicBlock *IDB = IDN->getBlock();
897 typedef GraphTraits<MachineDomTreeNode*> GTN;
898 typedef SmallVector<MachineDomTreeNode*,4> DTNodeVectType;
899 DTNodeVectType Cn(GTN::child_begin(N), GTN::child_end(N));
900 for (DTNodeVectType::iterator I = Cn.begin(), E = Cn.end(); I != E; ++I) {
901 MachineBasicBlock *SB = (*I)->getBlock();
902 MDT->changeImmediateDominator(SB, IDB);
903 }
904 }
905
906 while (B->succ_size() > 0)
907 B->removeSuccessor(B->succ_begin());
908
909 for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I)
Cong Houc1069892015-12-13 09:26:17 +0000910 (*I)->removeSuccessor(B, true);
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000911
912 Deleted.insert(B);
913 MDT->eraseNode(B);
Duncan P. N. Exon Smitha72c6e22015-10-20 00:46:39 +0000914 MFN->erase(B->getIterator());
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000915}
916
917
918void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) {
919 DEBUG(dbgs() << "Removing phi nodes from block " << PrintMB(B) << "\n");
920 MachineBasicBlock::iterator I, NextI, NonPHI = B->getFirstNonPHI();
921 for (I = B->begin(); I != NonPHI; I = NextI) {
922 NextI = std::next(I);
923 MachineInstr *PN = &*I;
924 assert(PN->getNumOperands() == 3 && "Invalid phi node");
925 MachineOperand &UO = PN->getOperand(1);
926 unsigned UseR = UO.getReg(), UseSR = UO.getSubReg();
927 unsigned DefR = PN->getOperand(0).getReg();
928 unsigned NewR = UseR;
929 if (UseSR) {
930 // MRI.replaceVregUsesWith does not allow to update the subregister,
931 // so instead of doing the use-iteration here, create a copy into a
932 // "non-subregistered" register.
Benjamin Kramer4ca41fd2016-06-12 17:30:47 +0000933 const DebugLoc &DL = PN->getDebugLoc();
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000934 const TargetRegisterClass *RC = MRI->getRegClass(DefR);
935 NewR = MRI->createVirtualRegister(RC);
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000936 NonPHI = BuildMI(*B, NonPHI, DL, HII->get(TargetOpcode::COPY), NewR)
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000937 .addReg(UseR, 0, UseSR);
938 }
939 MRI->replaceRegWith(DefR, NewR);
940 B->erase(I);
941 }
942}
943
944
945void HexagonEarlyIfConversion::replacePhiEdges(MachineBasicBlock *OldB,
946 MachineBasicBlock *NewB) {
947 for (auto I = OldB->succ_begin(), E = OldB->succ_end(); I != E; ++I) {
948 MachineBasicBlock *SB = *I;
949 MachineBasicBlock::iterator P, N = SB->getFirstNonPHI();
950 for (P = SB->begin(); P != N; ++P) {
Duncan P. N. Exon Smithf9ab4162016-02-27 17:05:33 +0000951 MachineInstr &PN = *P;
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000952 for (MIOperands MO(PN); MO.isValid(); ++MO)
953 if (MO->isMBB() && MO->getMBB() == OldB)
954 MO->setMBB(NewB);
955 }
956 }
957}
958
959
960void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
961 MachineBasicBlock *SuccB) {
962 DEBUG(dbgs() << "Merging blocks " << PrintMB(PredB) << " and "
963 << PrintMB(SuccB) << "\n");
964 bool TermOk = hasUncondBranch(SuccB);
965 eliminatePhis(SuccB);
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +0000966 HII->RemoveBranch(*PredB);
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000967 PredB->removeSuccessor(SuccB);
968 PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end());
969 MachineBasicBlock::succ_iterator I, E = SuccB->succ_end();
970 for (I = SuccB->succ_begin(); I != E; ++I)
971 PredB->addSuccessor(*I);
Cong Houc1069892015-12-13 09:26:17 +0000972 PredB->normalizeSuccProbs();
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +0000973 replacePhiEdges(SuccB, PredB);
974 removeBlock(SuccB);
975 if (!TermOk)
976 PredB->updateTerminator();
977}
978
979
980void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) {
981 if (FP.TrueB)
982 removeBlock(FP.TrueB);
983 if (FP.FalseB)
984 removeBlock(FP.FalseB);
985
986 FP.SplitB->updateTerminator();
987 if (FP.SplitB->succ_size() != 1)
988 return;
989
990 MachineBasicBlock *SB = *FP.SplitB->succ_begin();
991 if (SB->pred_size() != 1)
992 return;
993
994 // By now, the split block has only one successor (SB), and SB has only
995 // one predecessor. We can try to merge them. We will need to update ter-
996 // minators in FP.Split+SB, and that requires working AnalyzeBranch, which
997 // fails on Hexagon for blocks that have EH_LABELs. However, if SB ends
998 // with an unconditional branch, we won't need to touch the terminators.
999 if (!hasEHLabel(SB) || hasUncondBranch(SB))
1000 mergeBlocks(FP.SplitB, SB);
1001}
1002
1003
1004bool HexagonEarlyIfConversion::runOnMachineFunction(MachineFunction &MF) {
Andrew Kaylor5b444a22016-04-26 19:46:28 +00001005 if (skipFunction(*MF.getFunction()))
1006 return false;
1007
Krzysztof Parzyszek2a480592016-07-26 20:30:30 +00001008 auto &ST = MF.getSubtarget<HexagonSubtarget>();
1009 HII = ST.getInstrInfo();
Krzysztof Parzyszekfb338242015-10-06 15:49:14 +00001010 TRI = ST.getRegisterInfo();
1011 MFN = &MF;
1012 MRI = &MF.getRegInfo();
1013 MDT = &getAnalysis<MachineDominatorTree>();
1014 MLI = &getAnalysis<MachineLoopInfo>();
1015 MBPI = EnableHexagonBP ? &getAnalysis<MachineBranchProbabilityInfo>() :
1016 nullptr;
1017
1018 Deleted.clear();
1019 bool Changed = false;
1020
1021 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
1022 Changed |= visitLoop(*I);
1023 Changed |= visitLoop(0);
1024
1025 return Changed;
1026}
1027
1028//===----------------------------------------------------------------------===//
1029// Public Constructor Functions
1030//===----------------------------------------------------------------------===//
1031FunctionPass *llvm::createHexagonEarlyIfConversion() {
1032 return new HexagonEarlyIfConversion();
1033}
1034