LLVM 19.0.0git
HexagonConstPropagation.cpp
Go to the documentation of this file.
1//===- HexagonConstPropagation.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#include "HexagonInstrInfo.h"
10#include "HexagonRegisterInfo.h"
11#include "HexagonSubtarget.h"
12#include "llvm/ADT/APFloat.h"
13#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/SetVector.h"
17#include "llvm/ADT/StringRef.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/IR/Type.h"
29#include "llvm/Pass.h"
32#include "llvm/Support/Debug.h"
36#include <cassert>
37#include <cstdint>
38#include <cstring>
39#include <iterator>
40#include <map>
41#include <queue>
42#include <set>
43#include <utility>
44#include <vector>
45
46#define DEBUG_TYPE "hcp"
47
48using namespace llvm;
49
50namespace {
51
52 // Properties of a value that are tracked by the propagation.
53 // A property that is marked as present (i.e. bit is set) dentes that the
54 // value is known (proven) to have this property. Not all combinations
55 // of bits make sense, for example Zero and NonZero are mutually exclusive,
56 // but on the other hand, Zero implies Finite. In this case, whenever
57 // the Zero property is present, Finite should also be present.
58 class ConstantProperties {
59 public:
60 enum {
61 Unknown = 0x0000,
62 Zero = 0x0001,
63 NonZero = 0x0002,
64 Finite = 0x0004,
65 Infinity = 0x0008,
66 NaN = 0x0010,
67 SignedZero = 0x0020,
68 NumericProperties = (Zero|NonZero|Finite|Infinity|NaN|SignedZero),
69 PosOrZero = 0x0100,
70 NegOrZero = 0x0200,
71 SignProperties = (PosOrZero|NegOrZero),
72 Everything = (NumericProperties|SignProperties)
73 };
74
75 // For a given constant, deduce the set of trackable properties that this
76 // constant has.
77 static uint32_t deduce(const Constant *C);
78 };
79
80 // A representation of a register as it can appear in a MachineOperand,
81 // i.e. a pair register:subregister.
82
83 // FIXME: Use TargetInstrInfo::RegSubRegPair. Also duplicated in
84 // HexagonGenPredicate
85 struct RegisterSubReg {
86 Register Reg;
87 unsigned SubReg;
88
89 explicit RegisterSubReg(unsigned R, unsigned SR = 0) : Reg(R), SubReg(SR) {}
90 explicit RegisterSubReg(const MachineOperand &MO)
91 : Reg(MO.getReg()), SubReg(MO.getSubReg()) {}
92
93 void print(const TargetRegisterInfo *TRI = nullptr) const {
94 dbgs() << printReg(Reg, TRI, SubReg);
95 }
96
97 bool operator== (const RegisterSubReg &R) const {
98 return (Reg == R.Reg) && (SubReg == R.SubReg);
99 }
100 };
101
102 // Lattice cell, based on that was described in the W-Z paper on constant
103 // propagation.
104 // Latice cell will be allowed to hold multiple constant values. While
105 // multiple values would normally indicate "bottom", we can still derive
106 // some useful information from them. For example, comparison X > 0
107 // could be folded if all the values in the cell associated with X are
108 // positive.
109 class LatticeCell {
110 private:
111 enum { Normal, Top, Bottom };
112
113 static const unsigned MaxCellSize = 4;
114
115 unsigned Kind:2;
116 unsigned Size:3;
117 unsigned IsSpecial:1;
118 unsigned :0;
119
120 public:
121 union {
122 uint32_t Properties;
123 const Constant *Value;
124 const Constant *Values[MaxCellSize];
125 };
126
127 LatticeCell() : Kind(Top), Size(0), IsSpecial(false) {
128 for (const Constant *&Value : Values)
129 Value = nullptr;
130 }
131
132 bool meet(const LatticeCell &L);
133 bool add(const Constant *C);
134 bool add(uint32_t Property);
135 uint32_t properties() const;
136 unsigned size() const { return Size; }
137
138 LatticeCell(const LatticeCell &L) {
139 // This memcpy also copies Properties (when L.Size == 0).
140 uint32_t N =
141 L.IsSpecial ? sizeof L.Properties : L.Size * sizeof(const Constant *);
142 memcpy(Values, L.Values, N);
143 Kind = L.Kind;
144 Size = L.Size;
145 IsSpecial = L.IsSpecial;
146 }
147
148 LatticeCell &operator=(const LatticeCell &L) {
149 if (this != &L) {
150 // This memcpy also copies Properties (when L.Size == 0).
151 uint32_t N = L.IsSpecial ? sizeof L.Properties
152 : L.Size * sizeof(const Constant *);
153 memcpy(Values, L.Values, N);
154 Kind = L.Kind;
155 Size = L.Size;
156 IsSpecial = L.IsSpecial;
157 }
158 return *this;
159 }
160
161 bool isSingle() const { return size() == 1; }
162 bool isProperty() const { return IsSpecial; }
163 bool isTop() const { return Kind == Top; }
164 bool isBottom() const { return Kind == Bottom; }
165
166 bool setBottom() {
167 bool Changed = (Kind != Bottom);
168 Kind = Bottom;
169 Size = 0;
170 IsSpecial = false;
171 return Changed;
172 }
173
174 void print(raw_ostream &os) const;
175
176 private:
177 void setProperty() {
178 IsSpecial = true;
179 Size = 0;
180 Kind = Normal;
181 }
182
183 bool convertToProperty();
184 };
185
186#ifndef NDEBUG
187 raw_ostream &operator<< (raw_ostream &os, const LatticeCell &L) {
188 L.print(os);
189 return os;
190 }
191#endif
192
193 class MachineConstEvaluator;
194
195 class MachineConstPropagator {
196 public:
197 MachineConstPropagator(MachineConstEvaluator &E) : MCE(E) {
198 Bottom.setBottom();
199 }
200
201 // Mapping: vreg -> cell
202 // The keys are registers _without_ subregisters. This won't allow
203 // definitions in the form of "vreg:subreg = ...". Such definitions
204 // would be questionable from the point of view of SSA, since the "vreg"
205 // could not be initialized in its entirety (specifically, an instruction
206 // defining the "other part" of "vreg" would also count as a definition
207 // of "vreg", which would violate the SSA).
208 // If a value of a pair vreg:subreg needs to be obtained, the cell for
209 // "vreg" needs to be looked up, and then the value of subregister "subreg"
210 // needs to be evaluated.
211 class CellMap {
212 public:
213 CellMap() {
214 assert(Top.isTop());
215 Bottom.setBottom();
216 }
217
218 void clear() { Map.clear(); }
219
220 bool has(Register R) const {
221 // All non-virtual registers are considered "bottom".
222 if (!R.isVirtual())
223 return true;
224 MapType::const_iterator F = Map.find(R);
225 return F != Map.end();
226 }
227
228 const LatticeCell &get(Register R) const {
229 if (!R.isVirtual())
230 return Bottom;
231 MapType::const_iterator F = Map.find(R);
232 if (F != Map.end())
233 return F->second;
234 return Top;
235 }
236
237 // Invalidates any const references.
238 void update(Register R, const LatticeCell &L) { Map[R] = L; }
239
240 void print(raw_ostream &os, const TargetRegisterInfo &TRI) const;
241
242 private:
243 using MapType = std::map<Register, LatticeCell>;
244
245 MapType Map;
246 // To avoid creating "top" entries, return a const reference to
247 // this cell in "get". Also, have a "Bottom" cell to return from
248 // get when a value of a physical register is requested.
249 LatticeCell Top, Bottom;
250
251 public:
252 using const_iterator = MapType::const_iterator;
253
254 const_iterator begin() const { return Map.begin(); }
255 const_iterator end() const { return Map.end(); }
256 };
257
258 bool run(MachineFunction &MF);
259
260 private:
261 void visitPHI(const MachineInstr &PN);
262 void visitNonBranch(const MachineInstr &MI);
263 void visitBranchesFrom(const MachineInstr &BrI);
264 void visitUsesOf(unsigned R);
265 bool computeBlockSuccessors(const MachineBasicBlock *MB,
267 void removeCFGEdge(MachineBasicBlock *From, MachineBasicBlock *To);
268
269 void propagate(MachineFunction &MF);
270 bool rewrite(MachineFunction &MF);
271
272 MachineRegisterInfo *MRI = nullptr;
273 MachineConstEvaluator &MCE;
274
275 using CFGEdge = std::pair<unsigned, unsigned>;
276 using SetOfCFGEdge = std::set<CFGEdge>;
277 using SetOfInstr = std::set<const MachineInstr *>;
278 using QueueOfCFGEdge = std::queue<CFGEdge>;
279
280 LatticeCell Bottom;
281 CellMap Cells;
282 SetOfCFGEdge EdgeExec;
283 SetOfInstr InstrExec;
284 QueueOfCFGEdge FlowQ;
285 };
286
287 // The "evaluator/rewriter" of machine instructions. This is an abstract
288 // base class that provides the interface that the propagator will use,
289 // as well as some helper functions that are target-independent.
290 class MachineConstEvaluator {
291 public:
292 MachineConstEvaluator(MachineFunction &Fn)
294 MF(Fn), CX(Fn.getFunction().getContext()) {}
295 virtual ~MachineConstEvaluator() = default;
296
297 // The required interface:
298 // - A set of three "evaluate" functions. Each returns "true" if the
299 // computation succeeded, "false" otherwise.
300 // (1) Given an instruction MI, and the map with input values "Inputs",
301 // compute the set of output values "Outputs". An example of when
302 // the computation can "fail" is if MI is not an instruction that
303 // is recognized by the evaluator.
304 // (2) Given a register R (as reg:subreg), compute the cell that
305 // corresponds to the "subreg" part of the given register.
306 // (3) Given a branch instruction BrI, compute the set of target blocks.
307 // If the branch can fall-through, add null (0) to the list of
308 // possible targets.
309 // - A function "rewrite", that given the cell map after propagation,
310 // could rewrite instruction MI in a more beneficial form. Return
311 // "true" if a change has been made, "false" otherwise.
312 using CellMap = MachineConstPropagator::CellMap;
313 virtual bool evaluate(const MachineInstr &MI, const CellMap &Inputs,
314 CellMap &Outputs) = 0;
315 virtual bool evaluate(const RegisterSubReg &R, const LatticeCell &SrcC,
316 LatticeCell &Result) = 0;
317 virtual bool evaluate(const MachineInstr &BrI, const CellMap &Inputs,
319 bool &CanFallThru) = 0;
320 virtual bool rewrite(MachineInstr &MI, const CellMap &Inputs) = 0;
321
322 const TargetRegisterInfo &TRI;
323
324 protected:
325 MachineFunction &MF;
326 LLVMContext &CX;
327
328 struct Comparison {
329 enum {
330 Unk = 0x00,
331 EQ = 0x01,
332 NE = 0x02,
333 L = 0x04, // Less-than property.
334 G = 0x08, // Greater-than property.
335 U = 0x40, // Unsigned property.
336 LTs = L,
337 LEs = L | EQ,
338 GTs = G,
339 GEs = G | EQ,
340 LTu = L | U,
341 LEu = L | EQ | U,
342 GTu = G | U,
343 GEu = G | EQ | U
344 };
345
346 static uint32_t negate(uint32_t Cmp) {
347 if (Cmp == EQ)
348 return NE;
349 if (Cmp == NE)
350 return EQ;
351 assert((Cmp & (L|G)) != (L|G));
352 return Cmp ^ (L|G);
353 }
354 };
355
356 // Helper functions.
357
358 bool getCell(const RegisterSubReg &R, const CellMap &Inputs, LatticeCell &RC);
359 bool constToInt(const Constant *C, APInt &Val) const;
360 const ConstantInt *intToConst(const APInt &Val) const;
361
362 // Compares.
363 bool evaluateCMPrr(uint32_t Cmp, const RegisterSubReg &R1, const RegisterSubReg &R2,
364 const CellMap &Inputs, bool &Result);
365 bool evaluateCMPri(uint32_t Cmp, const RegisterSubReg &R1, const APInt &A2,
366 const CellMap &Inputs, bool &Result);
367 bool evaluateCMPrp(uint32_t Cmp, const RegisterSubReg &R1, uint64_t Props2,
368 const CellMap &Inputs, bool &Result);
369 bool evaluateCMPii(uint32_t Cmp, const APInt &A1, const APInt &A2,
370 bool &Result);
371 bool evaluateCMPpi(uint32_t Cmp, uint32_t Props, const APInt &A2,
372 bool &Result);
373 bool evaluateCMPpp(uint32_t Cmp, uint32_t Props1, uint32_t Props2,
374 bool &Result);
375
376 bool evaluateCOPY(const RegisterSubReg &R1, const CellMap &Inputs,
377 LatticeCell &Result);
378
379 // Logical operations.
380 bool evaluateANDrr(const RegisterSubReg &R1, const RegisterSubReg &R2,
381 const CellMap &Inputs, LatticeCell &Result);
382 bool evaluateANDri(const RegisterSubReg &R1, const APInt &A2,
383 const CellMap &Inputs, LatticeCell &Result);
384 bool evaluateANDii(const APInt &A1, const APInt &A2, APInt &Result);
385 bool evaluateORrr(const RegisterSubReg &R1, const RegisterSubReg &R2,
386 const CellMap &Inputs, LatticeCell &Result);
387 bool evaluateORri(const RegisterSubReg &R1, const APInt &A2,
388 const CellMap &Inputs, LatticeCell &Result);
389 bool evaluateORii(const APInt &A1, const APInt &A2, APInt &Result);
390 bool evaluateXORrr(const RegisterSubReg &R1, const RegisterSubReg &R2,
391 const CellMap &Inputs, LatticeCell &Result);
392 bool evaluateXORri(const RegisterSubReg &R1, const APInt &A2,
393 const CellMap &Inputs, LatticeCell &Result);
394 bool evaluateXORii(const APInt &A1, const APInt &A2, APInt &Result);
395
396 // Extensions.
397 bool evaluateZEXTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,
398 const CellMap &Inputs, LatticeCell &Result);
399 bool evaluateZEXTi(const APInt &A1, unsigned Width, unsigned Bits,
400 APInt &Result);
401 bool evaluateSEXTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,
402 const CellMap &Inputs, LatticeCell &Result);
403 bool evaluateSEXTi(const APInt &A1, unsigned Width, unsigned Bits,
404 APInt &Result);
405
406 // Leading/trailing bits.
407 bool evaluateCLBr(const RegisterSubReg &R1, bool Zeros, bool Ones,
408 const CellMap &Inputs, LatticeCell &Result);
409 bool evaluateCLBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result);
410 bool evaluateCTBr(const RegisterSubReg &R1, bool Zeros, bool Ones,
411 const CellMap &Inputs, LatticeCell &Result);
412 bool evaluateCTBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result);
413
414 // Bitfield extract.
415 bool evaluateEXTRACTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,
416 unsigned Offset, bool Signed, const CellMap &Inputs,
417 LatticeCell &Result);
418 bool evaluateEXTRACTi(const APInt &A1, unsigned Bits, unsigned Offset,
419 bool Signed, APInt &Result);
420 // Vector operations.
421 bool evaluateSplatr(const RegisterSubReg &R1, unsigned Bits, unsigned Count,
422 const CellMap &Inputs, LatticeCell &Result);
423 bool evaluateSplati(const APInt &A1, unsigned Bits, unsigned Count,
424 APInt &Result);
425 };
426
427} // end anonymous namespace
428
429uint32_t ConstantProperties::deduce(const Constant *C) {
430 if (isa<ConstantInt>(C)) {
431 const ConstantInt *CI = cast<ConstantInt>(C);
432 if (CI->isZero())
433 return Zero | PosOrZero | NegOrZero | Finite;
434 uint32_t Props = (NonZero | Finite);
435 if (CI->isNegative())
436 return Props | NegOrZero;
437 return Props | PosOrZero;
438 }
439
440 if (isa<ConstantFP>(C)) {
441 const ConstantFP *CF = cast<ConstantFP>(C);
442 uint32_t Props = CF->isNegative() ? (NegOrZero|NonZero)
443 : PosOrZero;
444 if (CF->isZero())
445 return (Props & ~NumericProperties) | (Zero|Finite);
446 Props = (Props & ~NumericProperties) | NonZero;
447 if (CF->isNaN())
448 return (Props & ~NumericProperties) | NaN;
449 const APFloat &Val = CF->getValueAPF();
450 if (Val.isInfinity())
451 return (Props & ~NumericProperties) | Infinity;
452 Props |= Finite;
453 return Props;
454 }
455
456 return Unknown;
457}
458
459// Convert a cell from a set of specific values to a cell that tracks
460// properties.
461bool LatticeCell::convertToProperty() {
462 if (isProperty())
463 return false;
464 // Corner case: converting a fresh (top) cell to "special".
465 // This can happen, when adding a property to a top cell.
466 uint32_t Everything = ConstantProperties::Everything;
467 uint32_t Ps = !isTop() ? properties()
468 : Everything;
469 if (Ps != ConstantProperties::Unknown) {
470 Properties = Ps;
471 setProperty();
472 } else {
473 setBottom();
474 }
475 return true;
476}
477
478#ifndef NDEBUG
479void LatticeCell::print(raw_ostream &os) const {
480 if (isProperty()) {
481 os << "{ ";
482 uint32_t Ps = properties();
483 if (Ps & ConstantProperties::Zero)
484 os << "zero ";
485 if (Ps & ConstantProperties::NonZero)
486 os << "nonzero ";
487 if (Ps & ConstantProperties::Finite)
488 os << "finite ";
489 if (Ps & ConstantProperties::Infinity)
490 os << "infinity ";
491 if (Ps & ConstantProperties::NaN)
492 os << "nan ";
493 if (Ps & ConstantProperties::PosOrZero)
494 os << "poz ";
495 if (Ps & ConstantProperties::NegOrZero)
496 os << "nez ";
497 os << '}';
498 return;
499 }
500
501 os << "{ ";
502 if (isBottom()) {
503 os << "bottom";
504 } else if (isTop()) {
505 os << "top";
506 } else {
507 for (unsigned i = 0; i < size(); ++i) {
508 const Constant *C = Values[i];
509 if (i != 0)
510 os << ", ";
511 C->print(os);
512 }
513 }
514 os << " }";
515}
516#endif
517
518// "Meet" operation on two cells. This is the key of the propagation
519// algorithm.
520bool LatticeCell::meet(const LatticeCell &L) {
521 bool Changed = false;
522 if (L.isBottom())
523 Changed = setBottom();
524 if (isBottom() || L.isTop())
525 return Changed;
526 if (isTop()) {
527 *this = L;
528 // L can be neither Top nor Bottom, so *this must have changed.
529 return true;
530 }
531
532 // Top/bottom cases covered. Need to integrate L's set into ours.
533 if (L.isProperty())
534 return add(L.properties());
535 for (unsigned i = 0; i < L.size(); ++i) {
536 const Constant *LC = L.Values[i];
537 Changed |= add(LC);
538 }
539 return Changed;
540}
541
542// Add a new constant to the cell. This is actually where the cell update
543// happens. If a cell has room for more constants, the new constant is added.
544// Otherwise, the cell is converted to a "property" cell (i.e. a cell that
545// will track properties of the associated values, and not the values
546// themselves. Care is taken to handle special cases, like "bottom", etc.
547bool LatticeCell::add(const Constant *LC) {
548 assert(LC);
549 if (isBottom())
550 return false;
551
552 if (!isProperty()) {
553 // Cell is not special. Try to add the constant here first,
554 // if there is room.
555 unsigned Index = 0;
556 while (Index < Size) {
557 const Constant *C = Values[Index];
558 // If the constant is already here, no change is needed.
559 if (C == LC)
560 return false;
561 Index++;
562 }
563 if (Index < MaxCellSize) {
564 Values[Index] = LC;
565 Kind = Normal;
566 Size++;
567 return true;
568 }
569 }
570
571 bool Changed = false;
572
573 // This cell is special, or is not special, but is full. After this
574 // it will be special.
575 Changed = convertToProperty();
576 uint32_t Ps = properties();
577 uint32_t NewPs = Ps & ConstantProperties::deduce(LC);
578 if (NewPs == ConstantProperties::Unknown) {
579 setBottom();
580 return true;
581 }
582 if (Ps != NewPs) {
583 Properties = NewPs;
584 Changed = true;
585 }
586 return Changed;
587}
588
589// Add a property to the cell. This will force the cell to become a property-
590// tracking cell.
591bool LatticeCell::add(uint32_t Property) {
592 bool Changed = convertToProperty();
593 uint32_t Ps = properties();
594 if (Ps == (Ps & Property))
595 return Changed;
596 Properties = Property & Ps;
597 return true;
598}
599
600// Return the properties of the values in the cell. This is valid for any
601// cell, and does not alter the cell itself.
602uint32_t LatticeCell::properties() const {
603 if (isProperty())
604 return Properties;
605 assert(!isTop() && "Should not call this for a top cell");
606 if (isBottom())
607 return ConstantProperties::Unknown;
608
609 assert(size() > 0 && "Empty cell");
610 uint32_t Ps = ConstantProperties::deduce(Values[0]);
611 for (unsigned i = 1; i < size(); ++i) {
612 if (Ps == ConstantProperties::Unknown)
613 break;
614 Ps &= ConstantProperties::deduce(Values[i]);
615 }
616 return Ps;
617}
618
619#ifndef NDEBUG
620void MachineConstPropagator::CellMap::print(raw_ostream &os,
621 const TargetRegisterInfo &TRI) const {
622 for (auto &I : Map)
623 dbgs() << " " << printReg(I.first, &TRI) << " -> " << I.second << '\n';
624}
625#endif
626
627void MachineConstPropagator::visitPHI(const MachineInstr &PN) {
628 const MachineBasicBlock *MB = PN.getParent();
629 unsigned MBN = MB->getNumber();
630 LLVM_DEBUG(dbgs() << "Visiting FI(" << printMBBReference(*MB) << "): " << PN);
631
632 const MachineOperand &MD = PN.getOperand(0);
633 RegisterSubReg DefR(MD);
634 assert(DefR.Reg.isVirtual());
635
636 bool Changed = false;
637
638 // If the def has a sub-register, set the corresponding cell to "bottom".
639 if (DefR.SubReg) {
640Bottomize:
641 const LatticeCell &T = Cells.get(DefR.Reg);
642 Changed = !T.isBottom();
643 Cells.update(DefR.Reg, Bottom);
644 if (Changed)
645 visitUsesOf(DefR.Reg);
646 return;
647 }
648
649 LatticeCell DefC = Cells.get(DefR.Reg);
650
651 for (unsigned i = 1, n = PN.getNumOperands(); i < n; i += 2) {
652 const MachineBasicBlock *PB = PN.getOperand(i+1).getMBB();
653 unsigned PBN = PB->getNumber();
654 if (!EdgeExec.count(CFGEdge(PBN, MBN))) {
655 LLVM_DEBUG(dbgs() << " edge " << printMBBReference(*PB) << "->"
656 << printMBBReference(*MB) << " not executable\n");
657 continue;
658 }
659 const MachineOperand &SO = PN.getOperand(i);
660 RegisterSubReg UseR(SO);
661 // If the input is not a virtual register, we don't really know what
662 // value it holds.
663 if (!UseR.Reg.isVirtual())
664 goto Bottomize;
665 // If there is no cell for an input register, it means top.
666 if (!Cells.has(UseR.Reg))
667 continue;
668
669 LatticeCell SrcC;
670 bool Eval = MCE.evaluate(UseR, Cells.get(UseR.Reg), SrcC);
671 LLVM_DEBUG(dbgs() << " edge from " << printMBBReference(*PB) << ": "
672 << printReg(UseR.Reg, &MCE.TRI, UseR.SubReg) << SrcC
673 << '\n');
674 Changed |= Eval ? DefC.meet(SrcC)
675 : DefC.setBottom();
676 Cells.update(DefR.Reg, DefC);
677 if (DefC.isBottom())
678 break;
679 }
680 if (Changed)
681 visitUsesOf(DefR.Reg);
682}
683
684void MachineConstPropagator::visitNonBranch(const MachineInstr &MI) {
685 LLVM_DEBUG(dbgs() << "Visiting MI(" << printMBBReference(*MI.getParent())
686 << "): " << MI);
687 CellMap Outputs;
688 bool Eval = MCE.evaluate(MI, Cells, Outputs);
689 LLVM_DEBUG({
690 if (Eval) {
691 dbgs() << " outputs:";
692 for (auto &I : Outputs)
693 dbgs() << ' ' << I.second;
694 dbgs() << '\n';
695 }
696 });
697
698 // Update outputs. If the value was not computed, set all the
699 // def cells to bottom.
700 for (const MachineOperand &MO : MI.operands()) {
701 if (!MO.isReg() || !MO.isDef())
702 continue;
703 RegisterSubReg DefR(MO);
704 // Only track virtual registers.
705 if (!DefR.Reg.isVirtual())
706 continue;
707 bool Changed = false;
708 // If the evaluation failed, set cells for all output registers to bottom.
709 if (!Eval) {
710 const LatticeCell &T = Cells.get(DefR.Reg);
711 Changed = !T.isBottom();
712 Cells.update(DefR.Reg, Bottom);
713 } else {
714 // Find the corresponding cell in the computed outputs.
715 // If it's not there, go on to the next def.
716 if (!Outputs.has(DefR.Reg))
717 continue;
718 LatticeCell RC = Cells.get(DefR.Reg);
719 Changed = RC.meet(Outputs.get(DefR.Reg));
720 Cells.update(DefR.Reg, RC);
721 }
722 if (Changed)
723 visitUsesOf(DefR.Reg);
724 }
725}
726
727// Starting at a given branch, visit remaining branches in the block.
728// Traverse over the subsequent branches for as long as the preceding one
729// can fall through. Add all the possible targets to the flow work queue,
730// including the potential fall-through to the layout-successor block.
731void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) {
732 const MachineBasicBlock &B = *BrI.getParent();
733 unsigned MBN = B.getNumber();
736
738 bool EvalOk = true, FallsThru = true;
739 while (It != End) {
740 const MachineInstr &MI = *It;
741 InstrExec.insert(&MI);
742 LLVM_DEBUG(dbgs() << "Visiting " << (EvalOk ? "BR" : "br") << "("
743 << printMBBReference(B) << "): " << MI);
744 // Do not evaluate subsequent branches if the evaluation of any of the
745 // previous branches failed. Keep iterating over the branches only
746 // to mark them as executable.
747 EvalOk = EvalOk && MCE.evaluate(MI, Cells, Targets, FallsThru);
748 if (!EvalOk)
749 FallsThru = true;
750 if (!FallsThru)
751 break;
752 ++It;
753 }
754
755 if (B.mayHaveInlineAsmBr())
756 EvalOk = false;
757
758 if (EvalOk) {
759 // Need to add all CFG successors that lead to EH landing pads.
760 // There won't be explicit branches to these blocks, but they must
761 // be processed.
762 for (const MachineBasicBlock *SB : B.successors()) {
763 if (SB->isEHPad())
764 Targets.insert(SB);
765 }
766 if (FallsThru) {
767 const MachineFunction &MF = *B.getParent();
768 MachineFunction::const_iterator BI = B.getIterator();
769 MachineFunction::const_iterator Next = std::next(BI);
770 if (Next != MF.end())
771 Targets.insert(&*Next);
772 }
773 } else {
774 // If the evaluation of the branches failed, make "Targets" to be the
775 // set of all successors of the block from the CFG.
776 // If the evaluation succeeded for all visited branches, then if the
777 // last one set "FallsThru", then add an edge to the layout successor
778 // to the targets.
779 Targets.clear();
780 LLVM_DEBUG(dbgs() << " failed to evaluate a branch...adding all CFG "
781 "successors\n");
782 for (const MachineBasicBlock *SB : B.successors())
783 Targets.insert(SB);
784 }
785
786 for (const MachineBasicBlock *TB : Targets) {
787 unsigned TBN = TB->getNumber();
788 LLVM_DEBUG(dbgs() << " pushing edge " << printMBBReference(B) << " -> "
789 << printMBBReference(*TB) << "\n");
790 FlowQ.push(CFGEdge(MBN, TBN));
791 }
792}
793
794void MachineConstPropagator::visitUsesOf(unsigned Reg) {
795 LLVM_DEBUG(dbgs() << "Visiting uses of " << printReg(Reg, &MCE.TRI)
796 << Cells.get(Reg) << '\n');
797 for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
798 // Do not process non-executable instructions. They can become exceutable
799 // later (via a flow-edge in the work queue). In such case, the instruc-
800 // tion will be visited at that time.
801 if (!InstrExec.count(&MI))
802 continue;
803 if (MI.isPHI())
804 visitPHI(MI);
805 else if (!MI.isBranch())
806 visitNonBranch(MI);
807 else
808 visitBranchesFrom(MI);
809 }
810}
811
812bool MachineConstPropagator::computeBlockSuccessors(const MachineBasicBlock *MB,
814 Targets.clear();
815
817 for (const MachineInstr &MI : *MB) {
818 if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)
819 return false;
820 if (MI.isDebugInstr())
821 continue;
822 if (MI.isBranch()) {
823 FirstBr = MI.getIterator();
824 break;
825 }
826 }
827
829
830 bool DoNext = true;
831 for (MachineBasicBlock::const_iterator I = FirstBr; I != End; ++I) {
832 const MachineInstr &MI = *I;
833 // Can there be debug instructions between branches?
834 if (MI.isDebugInstr())
835 continue;
836 if (!InstrExec.count(&MI))
837 continue;
838 bool Eval = MCE.evaluate(MI, Cells, Targets, DoNext);
839 if (!Eval)
840 return false;
841 if (!DoNext)
842 break;
843 }
844 // If the last branch could fall-through, add block's layout successor.
845 if (DoNext) {
846 MachineFunction::const_iterator BI = MB->getIterator();
847 MachineFunction::const_iterator NextI = std::next(BI);
848 if (NextI != MB->getParent()->end())
849 Targets.insert(&*NextI);
850 }
851
852 // Add all the EH landing pads.
853 for (const MachineBasicBlock *SB : MB->successors())
854 if (SB->isEHPad())
855 Targets.insert(SB);
856
857 return true;
858}
859
860void MachineConstPropagator::removeCFGEdge(MachineBasicBlock *From,
861 MachineBasicBlock *To) {
862 // First, remove the CFG successor/predecessor information.
863 From->removeSuccessor(To);
864 // Remove all corresponding PHI operands in the To block.
865 for (MachineInstr &PN : To->phis()) {
866 // reg0 = PHI reg1, bb2, reg3, bb4, ...
867 int N = PN.getNumOperands() - 2;
868 while (N > 0) {
869 if (PN.getOperand(N + 1).getMBB() == From) {
870 PN.removeOperand(N + 1);
871 PN.removeOperand(N);
872 }
873 N -= 2;
874 }
875 }
876}
877
878void MachineConstPropagator::propagate(MachineFunction &MF) {
880 unsigned EntryNum = Entry->getNumber();
881
882 // Start with a fake edge, just to process the entry node.
883 FlowQ.push(CFGEdge(EntryNum, EntryNum));
884
885 while (!FlowQ.empty()) {
886 CFGEdge Edge = FlowQ.front();
887 FlowQ.pop();
888
890 dbgs() << "Picked edge "
891 << printMBBReference(*MF.getBlockNumbered(Edge.first)) << "->"
892 << printMBBReference(*MF.getBlockNumbered(Edge.second)) << '\n');
893 if (Edge.first != EntryNum)
894 if (EdgeExec.count(Edge))
895 continue;
896 EdgeExec.insert(Edge);
897 MachineBasicBlock *SB = MF.getBlockNumbered(Edge.second);
898
899 // Process the block in three stages:
900 // - visit all PHI nodes,
901 // - visit all non-branch instructions,
902 // - visit block branches.
904
905 // Visit PHI nodes in the successor block.
906 while (It != End && It->isPHI()) {
907 InstrExec.insert(&*It);
908 visitPHI(*It);
909 ++It;
910 }
911
912 // If the successor block just became executable, visit all instructions.
913 // To see if this is the first time we're visiting it, check the first
914 // non-debug instruction to see if it is executable.
915 while (It != End && It->isDebugInstr())
916 ++It;
917 assert(It == End || !It->isPHI());
918 // If this block has been visited, go on to the next one.
919 if (It != End && InstrExec.count(&*It))
920 continue;
921 // For now, scan all non-branch instructions. Branches require different
922 // processing.
923 while (It != End && !It->isBranch()) {
924 if (!It->isDebugInstr()) {
925 InstrExec.insert(&*It);
926 visitNonBranch(*It);
927 }
928 ++It;
929 }
930
931 // Time to process the end of the block. This is different from
932 // processing regular (non-branch) instructions, because there can
933 // be multiple branches in a block, and they can cause the block to
934 // terminate early.
935 if (It != End) {
936 visitBranchesFrom(*It);
937 } else {
938 // If the block didn't have a branch, add all successor edges to the
939 // work queue. (There should really be only one successor in such case.)
940 unsigned SBN = SB->getNumber();
941 for (const MachineBasicBlock *SSB : SB->successors())
942 FlowQ.push(CFGEdge(SBN, SSB->getNumber()));
943 }
944 } // while (FlowQ)
945
946 LLVM_DEBUG({
947 dbgs() << "Cells after propagation:\n";
948 Cells.print(dbgs(), MCE.TRI);
949 dbgs() << "Dead CFG edges:\n";
950 for (const MachineBasicBlock &B : MF) {
951 unsigned BN = B.getNumber();
952 for (const MachineBasicBlock *SB : B.successors()) {
953 unsigned SN = SB->getNumber();
954 if (!EdgeExec.count(CFGEdge(BN, SN)))
955 dbgs() << " " << printMBBReference(B) << " -> "
956 << printMBBReference(*SB) << '\n';
957 }
958 }
959 });
960}
961
962bool MachineConstPropagator::rewrite(MachineFunction &MF) {
963 bool Changed = false;
964 // Rewrite all instructions based on the collected cell information.
965 //
966 // Traverse the instructions in a post-order, so that rewriting an
967 // instruction can make changes "downstream" in terms of control-flow
968 // without affecting the rewriting process. (We should not change
969 // instructions that have not yet been visited by the rewriter.)
970 // The reason for this is that the rewriter can introduce new vregs,
971 // and replace uses of old vregs (which had corresponding cells
972 // computed during propagation) with these new vregs (which at this
973 // point would not have any cells, and would appear to be "top").
974 // If an attempt was made to evaluate an instruction with a fresh
975 // "top" vreg, it would cause an error (abend) in the evaluator.
976
977 // Collect the post-order-traversal block ordering. The subsequent
978 // traversal/rewrite will update block successors, so it's safer
979 // if the visiting order it computed ahead of time.
980 std::vector<MachineBasicBlock*> POT;
981 for (MachineBasicBlock *B : post_order(&MF))
982 if (!B->empty())
983 POT.push_back(B);
984
985 for (MachineBasicBlock *B : POT) {
986 // Walk the block backwards (which usually begin with the branches).
987 // If any branch is rewritten, we may need to update the successor
988 // information for this block. Unless the block's successors can be
989 // precisely determined (which may not be the case for indirect
990 // branches), we cannot modify any branch.
991
992 // Compute the successor information.
994 bool HaveTargets = computeBlockSuccessors(B, Targets);
995 // Rewrite the executable instructions. Skip branches if we don't
996 // have block successor information.
997 for (MachineInstr &MI : llvm::reverse(*B)) {
998 if (InstrExec.count(&MI)) {
999 if (MI.isBranch() && !HaveTargets)
1000 continue;
1001 Changed |= MCE.rewrite(MI, Cells);
1002 }
1003 }
1004 // The rewriting could rewrite PHI nodes to non-PHI nodes, causing
1005 // regular instructions to appear in between PHI nodes. Bring all
1006 // the PHI nodes to the beginning of the block.
1007 for (auto I = B->begin(), E = B->end(); I != E; ++I) {
1008 if (I->isPHI())
1009 continue;
1010 // I is not PHI. Find the next PHI node P.
1011 auto P = I;
1012 while (++P != E)
1013 if (P->isPHI())
1014 break;
1015 // Not found.
1016 if (P == E)
1017 break;
1018 // Splice P right before I.
1019 B->splice(I, B, P);
1020 // Reset I to point at the just spliced PHI node.
1021 --I;
1022 }
1023 // Update the block successor information: remove unnecessary successors.
1024 if (HaveTargets) {
1026 for (MachineBasicBlock *SB : B->successors()) {
1027 if (!Targets.count(SB))
1028 ToRemove.push_back(const_cast<MachineBasicBlock*>(SB));
1029 Targets.remove(SB);
1030 }
1032 removeCFGEdge(B, MBB);
1033 // If there are any blocks left in the computed targets, it means that
1034 // we think that the block could go somewhere, but the CFG does not.
1035 // This could legitimately happen in blocks that have non-returning
1036 // calls---we would think that the execution can continue, but the
1037 // CFG will not have a successor edge.
1038 }
1039 }
1040 // Need to do some final post-processing.
1041 // If a branch was not executable, it will not get rewritten, but should
1042 // be removed (or replaced with something equivalent to a A2_nop). We can't
1043 // erase instructions during rewriting, so this needs to be delayed until
1044 // now.
1045 for (MachineBasicBlock &B : MF) {
1047 if (MI.isBranch() && !InstrExec.count(&MI))
1048 B.erase(&MI);
1049 }
1050 return Changed;
1051}
1052
1053// This is the constant propagation algorithm as described by Wegman-Zadeck.
1054// Most of the terminology comes from there.
1055bool MachineConstPropagator::run(MachineFunction &MF) {
1056 LLVM_DEBUG(MF.print(dbgs() << "Starting MachineConstPropagator\n", nullptr));
1057
1058 MRI = &MF.getRegInfo();
1059
1060 Cells.clear();
1061 EdgeExec.clear();
1062 InstrExec.clear();
1063 assert(FlowQ.empty());
1064
1065 propagate(MF);
1066 bool Changed = rewrite(MF);
1067
1068 LLVM_DEBUG({
1069 dbgs() << "End of MachineConstPropagator (Changed=" << Changed << ")\n";
1070 if (Changed)
1071 MF.print(dbgs(), nullptr);
1072 });
1073 return Changed;
1074}
1075
1076// --------------------------------------------------------------------
1077// Machine const evaluator.
1078
1079bool MachineConstEvaluator::getCell(const RegisterSubReg &R, const CellMap &Inputs,
1080 LatticeCell &RC) {
1081 if (!R.Reg.isVirtual())
1082 return false;
1083 const LatticeCell &L = Inputs.get(R.Reg);
1084 if (!R.SubReg) {
1085 RC = L;
1086 return !RC.isBottom();
1087 }
1088 bool Eval = evaluate(R, L, RC);
1089 return Eval && !RC.isBottom();
1090}
1091
1092bool MachineConstEvaluator::constToInt(const Constant *C,
1093 APInt &Val) const {
1094 const ConstantInt *CI = dyn_cast<ConstantInt>(C);
1095 if (!CI)
1096 return false;
1097 Val = CI->getValue();
1098 return true;
1099}
1100
1101const ConstantInt *MachineConstEvaluator::intToConst(const APInt &Val) const {
1102 return ConstantInt::get(CX, Val);
1103}
1104
1105bool MachineConstEvaluator::evaluateCMPrr(uint32_t Cmp, const RegisterSubReg &R1,
1106 const RegisterSubReg &R2, const CellMap &Inputs, bool &Result) {
1107 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1108 LatticeCell LS1, LS2;
1109 if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1110 return false;
1111
1112 bool IsProp1 = LS1.isProperty();
1113 bool IsProp2 = LS2.isProperty();
1114 if (IsProp1) {
1115 uint32_t Prop1 = LS1.properties();
1116 if (IsProp2)
1117 return evaluateCMPpp(Cmp, Prop1, LS2.properties(), Result);
1118 uint32_t NegCmp = Comparison::negate(Cmp);
1119 return evaluateCMPrp(NegCmp, R2, Prop1, Inputs, Result);
1120 }
1121 if (IsProp2) {
1122 uint32_t Prop2 = LS2.properties();
1123 return evaluateCMPrp(Cmp, R1, Prop2, Inputs, Result);
1124 }
1125
1126 APInt A;
1127 bool IsTrue = true, IsFalse = true;
1128 for (unsigned i = 0; i < LS2.size(); ++i) {
1129 bool Res;
1130 bool Computed = constToInt(LS2.Values[i], A) &&
1131 evaluateCMPri(Cmp, R1, A, Inputs, Res);
1132 if (!Computed)
1133 return false;
1134 IsTrue &= Res;
1135 IsFalse &= !Res;
1136 }
1137 assert(!IsTrue || !IsFalse);
1138 // The actual logical value of the comparison is same as IsTrue.
1139 Result = IsTrue;
1140 // Return true if the result was proven to be true or proven to be false.
1141 return IsTrue || IsFalse;
1142}
1143
1144bool MachineConstEvaluator::evaluateCMPri(uint32_t Cmp, const RegisterSubReg &R1,
1145 const APInt &A2, const CellMap &Inputs, bool &Result) {
1146 assert(Inputs.has(R1.Reg));
1147 LatticeCell LS;
1148 if (!getCell(R1, Inputs, LS))
1149 return false;
1150 if (LS.isProperty())
1151 return evaluateCMPpi(Cmp, LS.properties(), A2, Result);
1152
1153 APInt A;
1154 bool IsTrue = true, IsFalse = true;
1155 for (unsigned i = 0; i < LS.size(); ++i) {
1156 bool Res;
1157 bool Computed = constToInt(LS.Values[i], A) &&
1158 evaluateCMPii(Cmp, A, A2, Res);
1159 if (!Computed)
1160 return false;
1161 IsTrue &= Res;
1162 IsFalse &= !Res;
1163 }
1164 assert(!IsTrue || !IsFalse);
1165 // The actual logical value of the comparison is same as IsTrue.
1166 Result = IsTrue;
1167 // Return true if the result was proven to be true or proven to be false.
1168 return IsTrue || IsFalse;
1169}
1170
1171bool MachineConstEvaluator::evaluateCMPrp(uint32_t Cmp, const RegisterSubReg &R1,
1172 uint64_t Props2, const CellMap &Inputs, bool &Result) {
1173 assert(Inputs.has(R1.Reg));
1174 LatticeCell LS;
1175 if (!getCell(R1, Inputs, LS))
1176 return false;
1177 if (LS.isProperty())
1178 return evaluateCMPpp(Cmp, LS.properties(), Props2, Result);
1179
1180 APInt A;
1181 uint32_t NegCmp = Comparison::negate(Cmp);
1182 bool IsTrue = true, IsFalse = true;
1183 for (unsigned i = 0; i < LS.size(); ++i) {
1184 bool Res;
1185 bool Computed = constToInt(LS.Values[i], A) &&
1186 evaluateCMPpi(NegCmp, Props2, A, Res);
1187 if (!Computed)
1188 return false;
1189 IsTrue &= Res;
1190 IsFalse &= !Res;
1191 }
1192 assert(!IsTrue || !IsFalse);
1193 Result = IsTrue;
1194 return IsTrue || IsFalse;
1195}
1196
1197bool MachineConstEvaluator::evaluateCMPii(uint32_t Cmp, const APInt &A1,
1198 const APInt &A2, bool &Result) {
1199 // NE is a special kind of comparison (not composed of smaller properties).
1200 if (Cmp == Comparison::NE) {
1201 Result = !APInt::isSameValue(A1, A2);
1202 return true;
1203 }
1204 if (Cmp == Comparison::EQ) {
1205 Result = APInt::isSameValue(A1, A2);
1206 return true;
1207 }
1208 if (Cmp & Comparison::EQ) {
1209 if (APInt::isSameValue(A1, A2))
1210 return (Result = true);
1211 }
1212 assert((Cmp & (Comparison::L | Comparison::G)) && "Malformed comparison");
1213 Result = false;
1214
1215 unsigned W1 = A1.getBitWidth();
1216 unsigned W2 = A2.getBitWidth();
1217 unsigned MaxW = (W1 >= W2) ? W1 : W2;
1218 if (Cmp & Comparison::U) {
1219 APInt Zx1 = A1.zext(MaxW);
1220 APInt Zx2 = A2.zext(MaxW);
1221 if (Cmp & Comparison::L)
1222 Result = Zx1.ult(Zx2);
1223 else if (Cmp & Comparison::G)
1224 Result = Zx2.ult(Zx1);
1225 return true;
1226 }
1227
1228 // Signed comparison.
1229 APInt Sx1 = A1.sext(MaxW);
1230 APInt Sx2 = A2.sext(MaxW);
1231 if (Cmp & Comparison::L)
1232 Result = Sx1.slt(Sx2);
1233 else if (Cmp & Comparison::G)
1234 Result = Sx2.slt(Sx1);
1235 return true;
1236}
1237
1238bool MachineConstEvaluator::evaluateCMPpi(uint32_t Cmp, uint32_t Props,
1239 const APInt &A2, bool &Result) {
1240 if (Props == ConstantProperties::Unknown)
1241 return false;
1242
1243 // Should never see NaN here, but check for it for completeness.
1244 if (Props & ConstantProperties::NaN)
1245 return false;
1246 // Infinity could theoretically be compared to a number, but the
1247 // presence of infinity here would be very suspicious. If we don't
1248 // know for sure that the number is finite, bail out.
1249 if (!(Props & ConstantProperties::Finite))
1250 return false;
1251
1252 // Let X be a number that has properties Props.
1253
1254 if (Cmp & Comparison::U) {
1255 // In case of unsigned comparisons, we can only compare against 0.
1256 if (A2 == 0) {
1257 // Any x!=0 will be considered >0 in an unsigned comparison.
1258 if (Props & ConstantProperties::Zero)
1259 Result = (Cmp & Comparison::EQ);
1260 else if (Props & ConstantProperties::NonZero)
1261 Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1262 else
1263 return false;
1264 return true;
1265 }
1266 // A2 is not zero. The only handled case is if X = 0.
1267 if (Props & ConstantProperties::Zero) {
1268 Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1269 return true;
1270 }
1271 return false;
1272 }
1273
1274 // Signed comparisons are different.
1275 if (Props & ConstantProperties::Zero) {
1276 if (A2 == 0)
1277 Result = (Cmp & Comparison::EQ);
1278 else
1279 Result = (Cmp == Comparison::NE) ||
1280 ((Cmp & Comparison::L) && !A2.isNegative()) ||
1281 ((Cmp & Comparison::G) && A2.isNegative());
1282 return true;
1283 }
1284 if (Props & ConstantProperties::PosOrZero) {
1285 // X >= 0 and !(A2 < 0) => cannot compare
1286 if (!A2.isNegative())
1287 return false;
1288 // X >= 0 and A2 < 0
1289 Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1290 return true;
1291 }
1292 if (Props & ConstantProperties::NegOrZero) {
1293 // X <= 0 and Src1 < 0 => cannot compare
1294 if (A2 == 0 || A2.isNegative())
1295 return false;
1296 // X <= 0 and A2 > 0
1297 Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1298 return true;
1299 }
1300
1301 return false;
1302}
1303
1304bool MachineConstEvaluator::evaluateCMPpp(uint32_t Cmp, uint32_t Props1,
1305 uint32_t Props2, bool &Result) {
1306 using P = ConstantProperties;
1307
1308 if ((Props1 & P::NaN) && (Props2 & P::NaN))
1309 return false;
1310 if (!(Props1 & P::Finite) || !(Props2 & P::Finite))
1311 return false;
1312
1313 bool Zero1 = (Props1 & P::Zero), Zero2 = (Props2 & P::Zero);
1314 bool NonZero1 = (Props1 & P::NonZero), NonZero2 = (Props2 & P::NonZero);
1315 if (Zero1 && Zero2) {
1316 Result = (Cmp & Comparison::EQ);
1317 return true;
1318 }
1319 if (Cmp == Comparison::NE) {
1320 if ((Zero1 && NonZero2) || (NonZero1 && Zero2))
1321 return (Result = true);
1322 return false;
1323 }
1324
1325 if (Cmp & Comparison::U) {
1326 // In unsigned comparisons, we can only compare against a known zero,
1327 // or a known non-zero.
1328 if (Zero1 && NonZero2) {
1329 Result = (Cmp & Comparison::L);
1330 return true;
1331 }
1332 if (NonZero1 && Zero2) {
1333 Result = (Cmp & Comparison::G);
1334 return true;
1335 }
1336 return false;
1337 }
1338
1339 // Signed comparison. The comparison is not NE.
1340 bool Poz1 = (Props1 & P::PosOrZero), Poz2 = (Props2 & P::PosOrZero);
1341 bool Nez1 = (Props1 & P::NegOrZero), Nez2 = (Props2 & P::NegOrZero);
1342 if (Nez1 && Poz2) {
1343 if (NonZero1 || NonZero2) {
1344 Result = (Cmp & Comparison::L);
1345 return true;
1346 }
1347 // Either (or both) could be zero. Can only say that X <= Y.
1348 if ((Cmp & Comparison::EQ) && (Cmp & Comparison::L))
1349 return (Result = true);
1350 }
1351 if (Poz1 && Nez2) {
1352 if (NonZero1 || NonZero2) {
1353 Result = (Cmp & Comparison::G);
1354 return true;
1355 }
1356 // Either (or both) could be zero. Can only say that X >= Y.
1357 if ((Cmp & Comparison::EQ) && (Cmp & Comparison::G))
1358 return (Result = true);
1359 }
1360
1361 return false;
1362}
1363
1364bool MachineConstEvaluator::evaluateCOPY(const RegisterSubReg &R1,
1365 const CellMap &Inputs, LatticeCell &Result) {
1366 return getCell(R1, Inputs, Result);
1367}
1368
1369bool MachineConstEvaluator::evaluateANDrr(const RegisterSubReg &R1,
1370 const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) {
1371 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1372 const LatticeCell &L1 = Inputs.get(R2.Reg);
1373 const LatticeCell &L2 = Inputs.get(R2.Reg);
1374 // If both sources are bottom, exit. Otherwise try to evaluate ANDri
1375 // with the non-bottom argument passed as the immediate. This is to
1376 // catch cases of ANDing with 0.
1377 if (L2.isBottom()) {
1378 if (L1.isBottom())
1379 return false;
1380 return evaluateANDrr(R2, R1, Inputs, Result);
1381 }
1382 LatticeCell LS2;
1383 if (!evaluate(R2, L2, LS2))
1384 return false;
1385 if (LS2.isBottom() || LS2.isProperty())
1386 return false;
1387
1388 APInt A;
1389 for (unsigned i = 0; i < LS2.size(); ++i) {
1390 LatticeCell RC;
1391 bool Eval = constToInt(LS2.Values[i], A) &&
1392 evaluateANDri(R1, A, Inputs, RC);
1393 if (!Eval)
1394 return false;
1395 Result.meet(RC);
1396 }
1397 return !Result.isBottom();
1398}
1399
1400bool MachineConstEvaluator::evaluateANDri(const RegisterSubReg &R1,
1401 const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1402 assert(Inputs.has(R1.Reg));
1403 if (A2 == -1)
1404 return getCell(R1, Inputs, Result);
1405 if (A2 == 0) {
1406 LatticeCell RC;
1407 RC.add(intToConst(A2));
1408 // Overwrite Result.
1409 Result = RC;
1410 return true;
1411 }
1412 LatticeCell LS1;
1413 if (!getCell(R1, Inputs, LS1))
1414 return false;
1415 if (LS1.isBottom() || LS1.isProperty())
1416 return false;
1417
1418 APInt A, ResA;
1419 for (unsigned i = 0; i < LS1.size(); ++i) {
1420 bool Eval = constToInt(LS1.Values[i], A) &&
1421 evaluateANDii(A, A2, ResA);
1422 if (!Eval)
1423 return false;
1424 const Constant *C = intToConst(ResA);
1425 Result.add(C);
1426 }
1427 return !Result.isBottom();
1428}
1429
1430bool MachineConstEvaluator::evaluateANDii(const APInt &A1,
1431 const APInt &A2, APInt &Result) {
1432 Result = A1 & A2;
1433 return true;
1434}
1435
1436bool MachineConstEvaluator::evaluateORrr(const RegisterSubReg &R1,
1437 const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) {
1438 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1439 const LatticeCell &L1 = Inputs.get(R2.Reg);
1440 const LatticeCell &L2 = Inputs.get(R2.Reg);
1441 // If both sources are bottom, exit. Otherwise try to evaluate ORri
1442 // with the non-bottom argument passed as the immediate. This is to
1443 // catch cases of ORing with -1.
1444 if (L2.isBottom()) {
1445 if (L1.isBottom())
1446 return false;
1447 return evaluateORrr(R2, R1, Inputs, Result);
1448 }
1449 LatticeCell LS2;
1450 if (!evaluate(R2, L2, LS2))
1451 return false;
1452 if (LS2.isBottom() || LS2.isProperty())
1453 return false;
1454
1455 APInt A;
1456 for (unsigned i = 0; i < LS2.size(); ++i) {
1457 LatticeCell RC;
1458 bool Eval = constToInt(LS2.Values[i], A) &&
1459 evaluateORri(R1, A, Inputs, RC);
1460 if (!Eval)
1461 return false;
1462 Result.meet(RC);
1463 }
1464 return !Result.isBottom();
1465}
1466
1467bool MachineConstEvaluator::evaluateORri(const RegisterSubReg &R1,
1468 const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1469 assert(Inputs.has(R1.Reg));
1470 if (A2 == 0)
1471 return getCell(R1, Inputs, Result);
1472 if (A2 == -1) {
1473 LatticeCell RC;
1474 RC.add(intToConst(A2));
1475 // Overwrite Result.
1476 Result = RC;
1477 return true;
1478 }
1479 LatticeCell LS1;
1480 if (!getCell(R1, Inputs, LS1))
1481 return false;
1482 if (LS1.isBottom() || LS1.isProperty())
1483 return false;
1484
1485 APInt A, ResA;
1486 for (unsigned i = 0; i < LS1.size(); ++i) {
1487 bool Eval = constToInt(LS1.Values[i], A) &&
1488 evaluateORii(A, A2, ResA);
1489 if (!Eval)
1490 return false;
1491 const Constant *C = intToConst(ResA);
1492 Result.add(C);
1493 }
1494 return !Result.isBottom();
1495}
1496
1497bool MachineConstEvaluator::evaluateORii(const APInt &A1,
1498 const APInt &A2, APInt &Result) {
1499 Result = A1 | A2;
1500 return true;
1501}
1502
1503bool MachineConstEvaluator::evaluateXORrr(const RegisterSubReg &R1,
1504 const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) {
1505 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1506 LatticeCell LS1, LS2;
1507 if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1508 return false;
1509 if (LS1.isProperty()) {
1510 if (LS1.properties() & ConstantProperties::Zero)
1511 return !(Result = LS2).isBottom();
1512 return false;
1513 }
1514 if (LS2.isProperty()) {
1515 if (LS2.properties() & ConstantProperties::Zero)
1516 return !(Result = LS1).isBottom();
1517 return false;
1518 }
1519
1520 APInt A;
1521 for (unsigned i = 0; i < LS2.size(); ++i) {
1522 LatticeCell RC;
1523 bool Eval = constToInt(LS2.Values[i], A) &&
1524 evaluateXORri(R1, A, Inputs, RC);
1525 if (!Eval)
1526 return false;
1527 Result.meet(RC);
1528 }
1529 return !Result.isBottom();
1530}
1531
1532bool MachineConstEvaluator::evaluateXORri(const RegisterSubReg &R1,
1533 const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1534 assert(Inputs.has(R1.Reg));
1535 LatticeCell LS1;
1536 if (!getCell(R1, Inputs, LS1))
1537 return false;
1538 if (LS1.isProperty()) {
1539 if (LS1.properties() & ConstantProperties::Zero) {
1540 const Constant *C = intToConst(A2);
1541 Result.add(C);
1542 return !Result.isBottom();
1543 }
1544 return false;
1545 }
1546
1547 APInt A, XA;
1548 for (unsigned i = 0; i < LS1.size(); ++i) {
1549 bool Eval = constToInt(LS1.Values[i], A) &&
1550 evaluateXORii(A, A2, XA);
1551 if (!Eval)
1552 return false;
1553 const Constant *C = intToConst(XA);
1554 Result.add(C);
1555 }
1556 return !Result.isBottom();
1557}
1558
1559bool MachineConstEvaluator::evaluateXORii(const APInt &A1,
1560 const APInt &A2, APInt &Result) {
1561 Result = A1 ^ A2;
1562 return true;
1563}
1564
1565bool MachineConstEvaluator::evaluateZEXTr(const RegisterSubReg &R1, unsigned Width,
1566 unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1567 assert(Inputs.has(R1.Reg));
1568 LatticeCell LS1;
1569 if (!getCell(R1, Inputs, LS1))
1570 return false;
1571 if (LS1.isProperty())
1572 return false;
1573
1574 APInt A, XA;
1575 for (unsigned i = 0; i < LS1.size(); ++i) {
1576 bool Eval = constToInt(LS1.Values[i], A) &&
1577 evaluateZEXTi(A, Width, Bits, XA);
1578 if (!Eval)
1579 return false;
1580 const Constant *C = intToConst(XA);
1581 Result.add(C);
1582 }
1583 return true;
1584}
1585
1586bool MachineConstEvaluator::evaluateZEXTi(const APInt &A1, unsigned Width,
1587 unsigned Bits, APInt &Result) {
1588 unsigned BW = A1.getBitWidth();
1589 (void)BW;
1590 assert(Width >= Bits && BW >= Bits);
1591 APInt Mask = APInt::getLowBitsSet(Width, Bits);
1592 Result = A1.zextOrTrunc(Width) & Mask;
1593 return true;
1594}
1595
1596bool MachineConstEvaluator::evaluateSEXTr(const RegisterSubReg &R1, unsigned Width,
1597 unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1598 assert(Inputs.has(R1.Reg));
1599 LatticeCell LS1;
1600 if (!getCell(R1, Inputs, LS1))
1601 return false;
1602 if (LS1.isBottom() || LS1.isProperty())
1603 return false;
1604
1605 APInt A, XA;
1606 for (unsigned i = 0; i < LS1.size(); ++i) {
1607 bool Eval = constToInt(LS1.Values[i], A) &&
1608 evaluateSEXTi(A, Width, Bits, XA);
1609 if (!Eval)
1610 return false;
1611 const Constant *C = intToConst(XA);
1612 Result.add(C);
1613 }
1614 return true;
1615}
1616
1617bool MachineConstEvaluator::evaluateSEXTi(const APInt &A1, unsigned Width,
1618 unsigned Bits, APInt &Result) {
1619 unsigned BW = A1.getBitWidth();
1620 assert(Width >= Bits && BW >= Bits);
1621 // Special case to make things faster for smaller source widths.
1622 // Sign extension of 0 bits generates 0 as a result. This is consistent
1623 // with what the HW does.
1624 if (Bits == 0) {
1625 Result = APInt(Width, 0);
1626 return true;
1627 }
1628 // In C, shifts by 64 invoke undefined behavior: handle that case in APInt.
1629 if (BW <= 64 && Bits != 0) {
1630 int64_t V = A1.getSExtValue();
1631 switch (Bits) {
1632 case 8:
1633 V = static_cast<int8_t>(V);
1634 break;
1635 case 16:
1636 V = static_cast<int16_t>(V);
1637 break;
1638 case 32:
1639 V = static_cast<int32_t>(V);
1640 break;
1641 default:
1642 // Shift left to lose all bits except lower "Bits" bits, then shift
1643 // the value back, replicating what was a sign bit after the first
1644 // shift.
1645 V = (V << (64-Bits)) >> (64-Bits);
1646 break;
1647 }
1648 // V is a 64-bit sign-extended value. Convert it to APInt of desired
1649 // width.
1650 Result = APInt(Width, V, true);
1651 return true;
1652 }
1653 // Slow case: the value doesn't fit in int64_t.
1654 if (Bits < BW)
1655 Result = A1.trunc(Bits).sext(Width);
1656 else // Bits == BW
1657 Result = A1.sext(Width);
1658 return true;
1659}
1660
1661bool MachineConstEvaluator::evaluateCLBr(const RegisterSubReg &R1, bool Zeros,
1662 bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1663 assert(Inputs.has(R1.Reg));
1664 LatticeCell LS1;
1665 if (!getCell(R1, Inputs, LS1))
1666 return false;
1667 if (LS1.isBottom() || LS1.isProperty())
1668 return false;
1669
1670 APInt A, CA;
1671 for (unsigned i = 0; i < LS1.size(); ++i) {
1672 bool Eval = constToInt(LS1.Values[i], A) &&
1673 evaluateCLBi(A, Zeros, Ones, CA);
1674 if (!Eval)
1675 return false;
1676 const Constant *C = intToConst(CA);
1677 Result.add(C);
1678 }
1679 return true;
1680}
1681
1682bool MachineConstEvaluator::evaluateCLBi(const APInt &A1, bool Zeros,
1683 bool Ones, APInt &Result) {
1684 unsigned BW = A1.getBitWidth();
1685 if (!Zeros && !Ones)
1686 return false;
1687 unsigned Count = 0;
1688 if (Zeros && (Count == 0))
1689 Count = A1.countl_zero();
1690 if (Ones && (Count == 0))
1691 Count = A1.countl_one();
1692 Result = APInt(BW, static_cast<uint64_t>(Count), false);
1693 return true;
1694}
1695
1696bool MachineConstEvaluator::evaluateCTBr(const RegisterSubReg &R1, bool Zeros,
1697 bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1698 assert(Inputs.has(R1.Reg));
1699 LatticeCell LS1;
1700 if (!getCell(R1, Inputs, LS1))
1701 return false;
1702 if (LS1.isBottom() || LS1.isProperty())
1703 return false;
1704
1705 APInt A, CA;
1706 for (unsigned i = 0; i < LS1.size(); ++i) {
1707 bool Eval = constToInt(LS1.Values[i], A) &&
1708 evaluateCTBi(A, Zeros, Ones, CA);
1709 if (!Eval)
1710 return false;
1711 const Constant *C = intToConst(CA);
1712 Result.add(C);
1713 }
1714 return true;
1715}
1716
1717bool MachineConstEvaluator::evaluateCTBi(const APInt &A1, bool Zeros,
1718 bool Ones, APInt &Result) {
1719 unsigned BW = A1.getBitWidth();
1720 if (!Zeros && !Ones)
1721 return false;
1722 unsigned Count = 0;
1723 if (Zeros && (Count == 0))
1724 Count = A1.countr_zero();
1725 if (Ones && (Count == 0))
1726 Count = A1.countr_one();
1727 Result = APInt(BW, static_cast<uint64_t>(Count), false);
1728 return true;
1729}
1730
1731bool MachineConstEvaluator::evaluateEXTRACTr(const RegisterSubReg &R1,
1732 unsigned Width, unsigned Bits, unsigned Offset, bool Signed,
1733 const CellMap &Inputs, LatticeCell &Result) {
1734 assert(Inputs.has(R1.Reg));
1735 assert(Bits+Offset <= Width);
1736 LatticeCell LS1;
1737 if (!getCell(R1, Inputs, LS1))
1738 return false;
1739 if (LS1.isBottom())
1740 return false;
1741 if (LS1.isProperty()) {
1742 uint32_t Ps = LS1.properties();
1743 if (Ps & ConstantProperties::Zero) {
1744 const Constant *C = intToConst(APInt(Width, 0, false));
1745 Result.add(C);
1746 return true;
1747 }
1748 return false;
1749 }
1750
1751 APInt A, CA;
1752 for (unsigned i = 0; i < LS1.size(); ++i) {
1753 bool Eval = constToInt(LS1.Values[i], A) &&
1754 evaluateEXTRACTi(A, Bits, Offset, Signed, CA);
1755 if (!Eval)
1756 return false;
1757 const Constant *C = intToConst(CA);
1758 Result.add(C);
1759 }
1760 return true;
1761}
1762
1763bool MachineConstEvaluator::evaluateEXTRACTi(const APInt &A1, unsigned Bits,
1764 unsigned Offset, bool Signed, APInt &Result) {
1765 unsigned BW = A1.getBitWidth();
1766 assert(Bits+Offset <= BW);
1767 // Extracting 0 bits generates 0 as a result (as indicated by the HW people).
1768 if (Bits == 0) {
1769 Result = APInt(BW, 0);
1770 return true;
1771 }
1772 if (BW <= 64) {
1773 int64_t V = A1.getZExtValue();
1774 V <<= (64-Bits-Offset);
1775 if (Signed)
1776 V >>= (64-Bits);
1777 else
1778 V = static_cast<uint64_t>(V) >> (64-Bits);
1779 Result = APInt(BW, V, Signed);
1780 return true;
1781 }
1782 if (Signed)
1783 Result = A1.shl(BW-Bits-Offset).ashr(BW-Bits);
1784 else
1785 Result = A1.shl(BW-Bits-Offset).lshr(BW-Bits);
1786 return true;
1787}
1788
1789bool MachineConstEvaluator::evaluateSplatr(const RegisterSubReg &R1,
1790 unsigned Bits, unsigned Count, const CellMap &Inputs,
1791 LatticeCell &Result) {
1792 assert(Inputs.has(R1.Reg));
1793 LatticeCell LS1;
1794 if (!getCell(R1, Inputs, LS1))
1795 return false;
1796 if (LS1.isBottom() || LS1.isProperty())
1797 return false;
1798
1799 APInt A, SA;
1800 for (unsigned i = 0; i < LS1.size(); ++i) {
1801 bool Eval = constToInt(LS1.Values[i], A) &&
1802 evaluateSplati(A, Bits, Count, SA);
1803 if (!Eval)
1804 return false;
1805 const Constant *C = intToConst(SA);
1806 Result.add(C);
1807 }
1808 return true;
1809}
1810
1811bool MachineConstEvaluator::evaluateSplati(const APInt &A1, unsigned Bits,
1812 unsigned Count, APInt &Result) {
1813 assert(Count > 0);
1814 unsigned BW = A1.getBitWidth(), SW = Count*Bits;
1815 APInt LoBits = (Bits < BW) ? A1.trunc(Bits) : A1.zext(Bits);
1816 if (Count > 1)
1817 LoBits = LoBits.zext(SW);
1818
1819 APInt Res(SW, 0, false);
1820 for (unsigned i = 0; i < Count; ++i) {
1821 Res <<= Bits;
1822 Res |= LoBits;
1823 }
1824 Result = Res;
1825 return true;
1826}
1827
1828// ----------------------------------------------------------------------
1829// Hexagon-specific code.
1830
1831namespace llvm {
1832
1835
1836} // end namespace llvm
1837
1838namespace {
1839
1840 class HexagonConstEvaluator : public MachineConstEvaluator {
1841 public:
1842 HexagonConstEvaluator(MachineFunction &Fn);
1843
1844 bool evaluate(const MachineInstr &MI, const CellMap &Inputs,
1845 CellMap &Outputs) override;
1846 bool evaluate(const RegisterSubReg &R, const LatticeCell &SrcC,
1847 LatticeCell &Result) override;
1848 bool evaluate(const MachineInstr &BrI, const CellMap &Inputs,
1849 SetVector<const MachineBasicBlock*> &Targets, bool &FallsThru)
1850 override;
1851 bool rewrite(MachineInstr &MI, const CellMap &Inputs) override;
1852
1853 private:
1854 unsigned getRegBitWidth(unsigned Reg) const;
1855
1856 static uint32_t getCmp(unsigned Opc);
1857 static APInt getCmpImm(unsigned Opc, unsigned OpX,
1858 const MachineOperand &MO);
1859 void replaceWithNop(MachineInstr &MI);
1860
1861 bool evaluateHexRSEQ32(RegisterSubReg RL, RegisterSubReg RH, const CellMap &Inputs,
1862 LatticeCell &Result);
1863 bool evaluateHexCompare(const MachineInstr &MI, const CellMap &Inputs,
1864 CellMap &Outputs);
1865 // This is suitable to be called for compare-and-jump instructions.
1866 bool evaluateHexCompare2(uint32_t Cmp, const MachineOperand &Src1,
1867 const MachineOperand &Src2, const CellMap &Inputs, bool &Result);
1868 bool evaluateHexLogical(const MachineInstr &MI, const CellMap &Inputs,
1869 CellMap &Outputs);
1870 bool evaluateHexCondMove(const MachineInstr &MI, const CellMap &Inputs,
1871 CellMap &Outputs);
1872 bool evaluateHexExt(const MachineInstr &MI, const CellMap &Inputs,
1873 CellMap &Outputs);
1874 bool evaluateHexVector1(const MachineInstr &MI, const CellMap &Inputs,
1875 CellMap &Outputs);
1876 bool evaluateHexVector2(const MachineInstr &MI, const CellMap &Inputs,
1877 CellMap &Outputs);
1878
1879 void replaceAllRegUsesWith(Register FromReg, Register ToReg);
1880 bool rewriteHexBranch(MachineInstr &BrI, const CellMap &Inputs);
1881 bool rewriteHexConstDefs(MachineInstr &MI, const CellMap &Inputs,
1882 bool &AllDefs);
1883 bool rewriteHexConstUses(MachineInstr &MI, const CellMap &Inputs);
1884
1886 const HexagonInstrInfo &HII;
1887 const HexagonRegisterInfo &HRI;
1888 };
1889
1890 class HexagonConstPropagation : public MachineFunctionPass {
1891 public:
1892 static char ID;
1893
1894 HexagonConstPropagation() : MachineFunctionPass(ID) {}
1895
1896 StringRef getPassName() const override {
1897 return "Hexagon Constant Propagation";
1898 }
1899
1900 bool runOnMachineFunction(MachineFunction &MF) override {
1901 const Function &F = MF.getFunction();
1902 if (skipFunction(F))
1903 return false;
1904
1905 HexagonConstEvaluator HCE(MF);
1906 return MachineConstPropagator(HCE).run(MF);
1907 }
1908 };
1909
1910} // end anonymous namespace
1911
1912char HexagonConstPropagation::ID = 0;
1913
1914INITIALIZE_PASS(HexagonConstPropagation, "hexagon-constp",
1915 "Hexagon Constant Propagation", false, false)
1916
1917HexagonConstEvaluator::HexagonConstEvaluator(MachineFunction &Fn)
1918 : MachineConstEvaluator(Fn),
1919 HII(*Fn.getSubtarget<HexagonSubtarget>().getInstrInfo()),
1920 HRI(*Fn.getSubtarget<HexagonSubtarget>().getRegisterInfo()) {
1921 MRI = &Fn.getRegInfo();
1922}
1923
1924bool HexagonConstEvaluator::evaluate(const MachineInstr &MI,
1925 const CellMap &Inputs, CellMap &Outputs) {
1926 if (MI.isCall())
1927 return false;
1928 if (MI.getNumOperands() == 0 || !MI.getOperand(0).isReg())
1929 return false;
1930 const MachineOperand &MD = MI.getOperand(0);
1931 if (!MD.isDef())
1932 return false;
1933
1934 unsigned Opc = MI.getOpcode();
1935 RegisterSubReg DefR(MD);
1936 assert(!DefR.SubReg);
1937 if (!DefR.Reg.isVirtual())
1938 return false;
1939
1940 if (MI.isCopy()) {
1941 LatticeCell RC;
1942 RegisterSubReg SrcR(MI.getOperand(1));
1943 bool Eval = evaluateCOPY(SrcR, Inputs, RC);
1944 if (!Eval)
1945 return false;
1946 Outputs.update(DefR.Reg, RC);
1947 return true;
1948 }
1949 if (MI.isRegSequence()) {
1950 unsigned Sub1 = MI.getOperand(2).getImm();
1951 unsigned Sub2 = MI.getOperand(4).getImm();
1952 const TargetRegisterClass &DefRC = *MRI->getRegClass(DefR.Reg);
1953 unsigned SubLo = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_lo);
1954 unsigned SubHi = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_hi);
1955 if (Sub1 != SubLo && Sub1 != SubHi)
1956 return false;
1957 if (Sub2 != SubLo && Sub2 != SubHi)
1958 return false;
1959 assert(Sub1 != Sub2);
1960 bool LoIs1 = (Sub1 == SubLo);
1961 const MachineOperand &OpLo = LoIs1 ? MI.getOperand(1) : MI.getOperand(3);
1962 const MachineOperand &OpHi = LoIs1 ? MI.getOperand(3) : MI.getOperand(1);
1963 LatticeCell RC;
1964 RegisterSubReg SrcRL(OpLo), SrcRH(OpHi);
1965 bool Eval = evaluateHexRSEQ32(SrcRL, SrcRH, Inputs, RC);
1966 if (!Eval)
1967 return false;
1968 Outputs.update(DefR.Reg, RC);
1969 return true;
1970 }
1971 if (MI.isCompare()) {
1972 bool Eval = evaluateHexCompare(MI, Inputs, Outputs);
1973 return Eval;
1974 }
1975
1976 switch (Opc) {
1977 default:
1978 return false;
1979 case Hexagon::A2_tfrsi:
1980 case Hexagon::A2_tfrpi:
1981 case Hexagon::CONST32:
1982 case Hexagon::CONST64:
1983 {
1984 const MachineOperand &VO = MI.getOperand(1);
1985 // The operand of CONST32 can be a blockaddress, e.g.
1986 // %0 = CONST32 <blockaddress(@eat, %l)>
1987 // Do this check for all instructions for safety.
1988 if (!VO.isImm())
1989 return false;
1990 int64_t V = MI.getOperand(1).getImm();
1991 unsigned W = getRegBitWidth(DefR.Reg);
1992 if (W != 32 && W != 64)
1993 return false;
1994 IntegerType *Ty = (W == 32) ? Type::getInt32Ty(CX)
1995 : Type::getInt64Ty(CX);
1996 const ConstantInt *CI = ConstantInt::get(Ty, V, true);
1997 LatticeCell RC = Outputs.get(DefR.Reg);
1998 RC.add(CI);
1999 Outputs.update(DefR.Reg, RC);
2000 break;
2001 }
2002
2003 case Hexagon::PS_true:
2004 case Hexagon::PS_false:
2005 {
2006 LatticeCell RC = Outputs.get(DefR.Reg);
2007 bool NonZero = (Opc == Hexagon::PS_true);
2008 uint32_t P = NonZero ? ConstantProperties::NonZero
2009 : ConstantProperties::Zero;
2010 RC.add(P);
2011 Outputs.update(DefR.Reg, RC);
2012 break;
2013 }
2014
2015 case Hexagon::A2_and:
2016 case Hexagon::A2_andir:
2017 case Hexagon::A2_andp:
2018 case Hexagon::A2_or:
2019 case Hexagon::A2_orir:
2020 case Hexagon::A2_orp:
2021 case Hexagon::A2_xor:
2022 case Hexagon::A2_xorp:
2023 {
2024 bool Eval = evaluateHexLogical(MI, Inputs, Outputs);
2025 if (!Eval)
2026 return false;
2027 break;
2028 }
2029
2030 case Hexagon::A2_combineii: // combine(#s8Ext, #s8)
2031 case Hexagon::A4_combineii: // combine(#s8, #u6Ext)
2032 {
2033 if (!MI.getOperand(1).isImm() || !MI.getOperand(2).isImm())
2034 return false;
2035 uint64_t Hi = MI.getOperand(1).getImm();
2036 uint64_t Lo = MI.getOperand(2).getImm();
2037 uint64_t Res = (Hi << 32) | (Lo & 0xFFFFFFFF);
2038 IntegerType *Ty = Type::getInt64Ty(CX);
2039 const ConstantInt *CI = ConstantInt::get(Ty, Res, false);
2040 LatticeCell RC = Outputs.get(DefR.Reg);
2041 RC.add(CI);
2042 Outputs.update(DefR.Reg, RC);
2043 break;
2044 }
2045
2046 case Hexagon::S2_setbit_i:
2047 {
2048 int64_t B = MI.getOperand(2).getImm();
2049 assert(B >=0 && B < 32);
2050 APInt A(32, (1ull << B), false);
2051 RegisterSubReg R(MI.getOperand(1));
2052 LatticeCell RC = Outputs.get(DefR.Reg);
2053 bool Eval = evaluateORri(R, A, Inputs, RC);
2054 if (!Eval)
2055 return false;
2056 Outputs.update(DefR.Reg, RC);
2057 break;
2058 }
2059
2060 case Hexagon::C2_mux:
2061 case Hexagon::C2_muxir:
2062 case Hexagon::C2_muxri:
2063 case Hexagon::C2_muxii:
2064 {
2065 bool Eval = evaluateHexCondMove(MI, Inputs, Outputs);
2066 if (!Eval)
2067 return false;
2068 break;
2069 }
2070
2071 case Hexagon::A2_sxtb:
2072 case Hexagon::A2_sxth:
2073 case Hexagon::A2_sxtw:
2074 case Hexagon::A2_zxtb:
2075 case Hexagon::A2_zxth:
2076 {
2077 bool Eval = evaluateHexExt(MI, Inputs, Outputs);
2078 if (!Eval)
2079 return false;
2080 break;
2081 }
2082
2083 case Hexagon::S2_ct0:
2084 case Hexagon::S2_ct0p:
2085 case Hexagon::S2_ct1:
2086 case Hexagon::S2_ct1p:
2087 {
2088 using namespace Hexagon;
2089
2090 bool Ones = (Opc == S2_ct1) || (Opc == S2_ct1p);
2091 RegisterSubReg R1(MI.getOperand(1));
2092 assert(Inputs.has(R1.Reg));
2093 LatticeCell T;
2094 bool Eval = evaluateCTBr(R1, !Ones, Ones, Inputs, T);
2095 if (!Eval)
2096 return false;
2097 // All of these instructions return a 32-bit value. The evaluate
2098 // will generate the same type as the operand, so truncate the
2099 // result if necessary.
2100 APInt C;
2101 LatticeCell RC = Outputs.get(DefR.Reg);
2102 for (unsigned i = 0; i < T.size(); ++i) {
2103 const Constant *CI = T.Values[i];
2104 if (constToInt(CI, C) && C.getBitWidth() > 32)
2105 CI = intToConst(C.trunc(32));
2106 RC.add(CI);
2107 }
2108 Outputs.update(DefR.Reg, RC);
2109 break;
2110 }
2111
2112 case Hexagon::S2_cl0:
2113 case Hexagon::S2_cl0p:
2114 case Hexagon::S2_cl1:
2115 case Hexagon::S2_cl1p:
2116 case Hexagon::S2_clb:
2117 case Hexagon::S2_clbp:
2118 {
2119 using namespace Hexagon;
2120
2121 bool OnlyZeros = (Opc == S2_cl0) || (Opc == S2_cl0p);
2122 bool OnlyOnes = (Opc == S2_cl1) || (Opc == S2_cl1p);
2123 RegisterSubReg R1(MI.getOperand(1));
2124 assert(Inputs.has(R1.Reg));
2125 LatticeCell T;
2126 bool Eval = evaluateCLBr(R1, !OnlyOnes, !OnlyZeros, Inputs, T);
2127 if (!Eval)
2128 return false;
2129 // All of these instructions return a 32-bit value. The evaluate
2130 // will generate the same type as the operand, so truncate the
2131 // result if necessary.
2132 APInt C;
2133 LatticeCell RC = Outputs.get(DefR.Reg);
2134 for (unsigned i = 0; i < T.size(); ++i) {
2135 const Constant *CI = T.Values[i];
2136 if (constToInt(CI, C) && C.getBitWidth() > 32)
2137 CI = intToConst(C.trunc(32));
2138 RC.add(CI);
2139 }
2140 Outputs.update(DefR.Reg, RC);
2141 break;
2142 }
2143
2144 case Hexagon::S4_extract:
2145 case Hexagon::S4_extractp:
2146 case Hexagon::S2_extractu:
2147 case Hexagon::S2_extractup:
2148 {
2149 bool Signed = (Opc == Hexagon::S4_extract) ||
2150 (Opc == Hexagon::S4_extractp);
2151 RegisterSubReg R1(MI.getOperand(1));
2152 unsigned BW = getRegBitWidth(R1.Reg);
2153 unsigned Bits = MI.getOperand(2).getImm();
2154 unsigned Offset = MI.getOperand(3).getImm();
2155 LatticeCell RC = Outputs.get(DefR.Reg);
2156 if (Offset >= BW) {
2157 APInt Zero(BW, 0, false);
2158 RC.add(intToConst(Zero));
2159 break;
2160 }
2161 if (Offset+Bits > BW) {
2162 // If the requested bitfield extends beyond the most significant bit,
2163 // the extra bits are treated as 0s. To emulate this behavior, reduce
2164 // the number of requested bits, and make the extract unsigned.
2165 Bits = BW-Offset;
2166 Signed = false;
2167 }
2168 bool Eval = evaluateEXTRACTr(R1, BW, Bits, Offset, Signed, Inputs, RC);
2169 if (!Eval)
2170 return false;
2171 Outputs.update(DefR.Reg, RC);
2172 break;
2173 }
2174
2175 case Hexagon::S2_vsplatrb:
2176 case Hexagon::S2_vsplatrh:
2177 // vabsh, vabsh:sat
2178 // vabsw, vabsw:sat
2179 // vconj:sat
2180 // vrndwh, vrndwh:sat
2181 // vsathb, vsathub, vsatwuh
2182 // vsxtbh, vsxthw
2183 // vtrunehb, vtrunohb
2184 // vzxtbh, vzxthw
2185 {
2186 bool Eval = evaluateHexVector1(MI, Inputs, Outputs);
2187 if (!Eval)
2188 return false;
2189 break;
2190 }
2191
2192 // TODO:
2193 // A2_vaddh
2194 // A2_vaddhs
2195 // A2_vaddw
2196 // A2_vaddws
2197 }
2198
2199 return true;
2200}
2201
2202bool HexagonConstEvaluator::evaluate(const RegisterSubReg &R,
2203 const LatticeCell &Input, LatticeCell &Result) {
2204 if (!R.SubReg) {
2205 Result = Input;
2206 return true;
2207 }
2208 const TargetRegisterClass *RC = MRI->getRegClass(R.Reg);
2209 if (RC != &Hexagon::DoubleRegsRegClass)
2210 return false;
2211 if (R.SubReg != Hexagon::isub_lo && R.SubReg != Hexagon::isub_hi)
2212 return false;
2213
2214 assert(!Input.isTop());
2215 if (Input.isBottom())
2216 return false;
2217
2218 using P = ConstantProperties;
2219
2220 if (Input.isProperty()) {
2221 uint32_t Ps = Input.properties();
2222 if (Ps & (P::Zero|P::NaN)) {
2223 uint32_t Ns = (Ps & (P::Zero|P::NaN|P::SignProperties));
2224 Result.add(Ns);
2225 return true;
2226 }
2227 if (R.SubReg == Hexagon::isub_hi) {
2228 uint32_t Ns = (Ps & P::SignProperties);
2229 Result.add(Ns);
2230 return true;
2231 }
2232 return false;
2233 }
2234
2235 // The Input cell contains some known values. Pick the word corresponding
2236 // to the subregister.
2237 APInt A;
2238 for (unsigned i = 0; i < Input.size(); ++i) {
2239 const Constant *C = Input.Values[i];
2240 if (!constToInt(C, A))
2241 return false;
2242 if (!A.isIntN(64))
2243 return false;
2244 uint64_t U = A.getZExtValue();
2245 if (R.SubReg == Hexagon::isub_hi)
2246 U >>= 32;
2247 U &= 0xFFFFFFFFULL;
2248 uint32_t U32 = Lo_32(U);
2249 int32_t V32;
2250 memcpy(&V32, &U32, sizeof V32);
2251 IntegerType *Ty = Type::getInt32Ty(CX);
2252 const ConstantInt *C32 = ConstantInt::get(Ty, static_cast<int64_t>(V32));
2253 Result.add(C32);
2254 }
2255 return true;
2256}
2257
2258bool HexagonConstEvaluator::evaluate(const MachineInstr &BrI,
2259 const CellMap &Inputs, SetVector<const MachineBasicBlock*> &Targets,
2260 bool &FallsThru) {
2261 // We need to evaluate one branch at a time. TII::analyzeBranch checks
2262 // all the branches in a basic block at once, so we cannot use it.
2263 unsigned Opc = BrI.getOpcode();
2264 bool SimpleBranch = false;
2265 bool Negated = false;
2266 switch (Opc) {
2267 case Hexagon::J2_jumpf:
2268 case Hexagon::J2_jumpfnew:
2269 case Hexagon::J2_jumpfnewpt:
2270 Negated = true;
2271 [[fallthrough]];
2272 case Hexagon::J2_jumpt:
2273 case Hexagon::J2_jumptnew:
2274 case Hexagon::J2_jumptnewpt:
2275 // Simple branch: if([!]Pn) jump ...
2276 // i.e. Op0 = predicate, Op1 = branch target.
2277 SimpleBranch = true;
2278 break;
2279 case Hexagon::J2_jump:
2280 Targets.insert(BrI.getOperand(0).getMBB());
2281 FallsThru = false;
2282 return true;
2283 default:
2284Undetermined:
2285 // If the branch is of unknown type, assume that all successors are
2286 // executable.
2287 FallsThru = !BrI.isUnconditionalBranch();
2288 return false;
2289 }
2290
2291 if (SimpleBranch) {
2292 const MachineOperand &MD = BrI.getOperand(0);
2293 RegisterSubReg PR(MD);
2294 // If the condition operand has a subregister, this is not something
2295 // we currently recognize.
2296 if (PR.SubReg)
2297 goto Undetermined;
2298 assert(Inputs.has(PR.Reg));
2299 const LatticeCell &PredC = Inputs.get(PR.Reg);
2300 if (PredC.isBottom())
2301 goto Undetermined;
2302
2303 uint32_t Props = PredC.properties();
2304 bool CTrue = false, CFalse = false;
2305 if (Props & ConstantProperties::Zero)
2306 CFalse = true;
2307 else if (Props & ConstantProperties::NonZero)
2308 CTrue = true;
2309 // If the condition is not known to be either, bail out.
2310 if (!CTrue && !CFalse)
2311 goto Undetermined;
2312
2314
2315 FallsThru = false;
2316 if ((!Negated && CTrue) || (Negated && CFalse))
2317 Targets.insert(BranchTarget);
2318 else if ((!Negated && CFalse) || (Negated && CTrue))
2319 FallsThru = true;
2320 else
2321 goto Undetermined;
2322 }
2323
2324 return true;
2325}
2326
2327bool HexagonConstEvaluator::rewrite(MachineInstr &MI, const CellMap &Inputs) {
2328 if (MI.isBranch())
2329 return rewriteHexBranch(MI, Inputs);
2330
2331 unsigned Opc = MI.getOpcode();
2332 switch (Opc) {
2333 default:
2334 break;
2335 case Hexagon::A2_tfrsi:
2336 case Hexagon::A2_tfrpi:
2337 case Hexagon::CONST32:
2338 case Hexagon::CONST64:
2339 case Hexagon::PS_true:
2340 case Hexagon::PS_false:
2341 return false;
2342 }
2343
2344 unsigned NumOp = MI.getNumOperands();
2345 if (NumOp == 0)
2346 return false;
2347
2348 bool AllDefs, Changed;
2349 Changed = rewriteHexConstDefs(MI, Inputs, AllDefs);
2350 // If not all defs have been rewritten (i.e. the instruction defines
2351 // a register that is not compile-time constant), then try to rewrite
2352 // register operands that are known to be constant with immediates.
2353 if (!AllDefs)
2354 Changed |= rewriteHexConstUses(MI, Inputs);
2355
2356 return Changed;
2357}
2358
2359unsigned HexagonConstEvaluator::getRegBitWidth(unsigned Reg) const {
2360 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
2361 if (Hexagon::IntRegsRegClass.hasSubClassEq(RC))
2362 return 32;
2363 if (Hexagon::DoubleRegsRegClass.hasSubClassEq(RC))
2364 return 64;
2365 if (Hexagon::PredRegsRegClass.hasSubClassEq(RC))
2366 return 8;
2367 llvm_unreachable("Invalid register");
2368 return 0;
2369}
2370
2371uint32_t HexagonConstEvaluator::getCmp(unsigned Opc) {
2372 switch (Opc) {
2373 case Hexagon::C2_cmpeq:
2374 case Hexagon::C2_cmpeqp:
2375 case Hexagon::A4_cmpbeq:
2376 case Hexagon::A4_cmpheq:
2377 case Hexagon::A4_cmpbeqi:
2378 case Hexagon::A4_cmpheqi:
2379 case Hexagon::C2_cmpeqi:
2380 case Hexagon::J4_cmpeqn1_t_jumpnv_nt:
2381 case Hexagon::J4_cmpeqn1_t_jumpnv_t:
2382 case Hexagon::J4_cmpeqi_t_jumpnv_nt:
2383 case Hexagon::J4_cmpeqi_t_jumpnv_t:
2384 case Hexagon::J4_cmpeq_t_jumpnv_nt:
2385 case Hexagon::J4_cmpeq_t_jumpnv_t:
2386 return Comparison::EQ;
2387
2388 case Hexagon::C4_cmpneq:
2389 case Hexagon::C4_cmpneqi:
2390 case Hexagon::J4_cmpeqn1_f_jumpnv_nt:
2391 case Hexagon::J4_cmpeqn1_f_jumpnv_t:
2392 case Hexagon::J4_cmpeqi_f_jumpnv_nt:
2393 case Hexagon::J4_cmpeqi_f_jumpnv_t:
2394 case Hexagon::J4_cmpeq_f_jumpnv_nt:
2395 case Hexagon::J4_cmpeq_f_jumpnv_t:
2396 return Comparison::NE;
2397
2398 case Hexagon::C2_cmpgt:
2399 case Hexagon::C2_cmpgtp:
2400 case Hexagon::A4_cmpbgt:
2401 case Hexagon::A4_cmphgt:
2402 case Hexagon::A4_cmpbgti:
2403 case Hexagon::A4_cmphgti:
2404 case Hexagon::C2_cmpgti:
2405 case Hexagon::J4_cmpgtn1_t_jumpnv_nt:
2406 case Hexagon::J4_cmpgtn1_t_jumpnv_t:
2407 case Hexagon::J4_cmpgti_t_jumpnv_nt:
2408 case Hexagon::J4_cmpgti_t_jumpnv_t:
2409 case Hexagon::J4_cmpgt_t_jumpnv_nt:
2410 case Hexagon::J4_cmpgt_t_jumpnv_t:
2411 return Comparison::GTs;
2412
2413 case Hexagon::C4_cmplte:
2414 case Hexagon::C4_cmpltei:
2415 case Hexagon::J4_cmpgtn1_f_jumpnv_nt:
2416 case Hexagon::J4_cmpgtn1_f_jumpnv_t:
2417 case Hexagon::J4_cmpgti_f_jumpnv_nt:
2418 case Hexagon::J4_cmpgti_f_jumpnv_t:
2419 case Hexagon::J4_cmpgt_f_jumpnv_nt:
2420 case Hexagon::J4_cmpgt_f_jumpnv_t:
2421 return Comparison::LEs;
2422
2423 case Hexagon::C2_cmpgtu:
2424 case Hexagon::C2_cmpgtup:
2425 case Hexagon::A4_cmpbgtu:
2426 case Hexagon::A4_cmpbgtui:
2427 case Hexagon::A4_cmphgtu:
2428 case Hexagon::A4_cmphgtui:
2429 case Hexagon::C2_cmpgtui:
2430 case Hexagon::J4_cmpgtui_t_jumpnv_nt:
2431 case Hexagon::J4_cmpgtui_t_jumpnv_t:
2432 case Hexagon::J4_cmpgtu_t_jumpnv_nt:
2433 case Hexagon::J4_cmpgtu_t_jumpnv_t:
2434 return Comparison::GTu;
2435
2436 case Hexagon::J4_cmpltu_f_jumpnv_nt:
2437 case Hexagon::J4_cmpltu_f_jumpnv_t:
2438 return Comparison::GEu;
2439
2440 case Hexagon::J4_cmpltu_t_jumpnv_nt:
2441 case Hexagon::J4_cmpltu_t_jumpnv_t:
2442 return Comparison::LTu;
2443
2444 case Hexagon::J4_cmplt_f_jumpnv_nt:
2445 case Hexagon::J4_cmplt_f_jumpnv_t:
2446 return Comparison::GEs;
2447
2448 case Hexagon::C4_cmplteu:
2449 case Hexagon::C4_cmplteui:
2450 case Hexagon::J4_cmpgtui_f_jumpnv_nt:
2451 case Hexagon::J4_cmpgtui_f_jumpnv_t:
2452 case Hexagon::J4_cmpgtu_f_jumpnv_nt:
2453 case Hexagon::J4_cmpgtu_f_jumpnv_t:
2454 return Comparison::LEu;
2455
2456 case Hexagon::J4_cmplt_t_jumpnv_nt:
2457 case Hexagon::J4_cmplt_t_jumpnv_t:
2458 return Comparison::LTs;
2459
2460 default:
2461 break;
2462 }
2463 return Comparison::Unk;
2464}
2465
2466APInt HexagonConstEvaluator::getCmpImm(unsigned Opc, unsigned OpX,
2467 const MachineOperand &MO) {
2468 bool Signed = false;
2469 switch (Opc) {
2470 case Hexagon::A4_cmpbgtui: // u7
2471 case Hexagon::A4_cmphgtui: // u7
2472 break;
2473 case Hexagon::A4_cmpheqi: // s8
2474 case Hexagon::C4_cmpneqi: // s8
2475 Signed = true;
2476 break;
2477 case Hexagon::A4_cmpbeqi: // u8
2478 break;
2479 case Hexagon::C2_cmpgtui: // u9
2480 case Hexagon::C4_cmplteui: // u9
2481 break;
2482 case Hexagon::C2_cmpeqi: // s10
2483 case Hexagon::C2_cmpgti: // s10
2484 case Hexagon::C4_cmpltei: // s10
2485 Signed = true;
2486 break;
2487 case Hexagon::J4_cmpeqi_f_jumpnv_nt: // u5
2488 case Hexagon::J4_cmpeqi_f_jumpnv_t: // u5
2489 case Hexagon::J4_cmpeqi_t_jumpnv_nt: // u5
2490 case Hexagon::J4_cmpeqi_t_jumpnv_t: // u5
2491 case Hexagon::J4_cmpgti_f_jumpnv_nt: // u5
2492 case Hexagon::J4_cmpgti_f_jumpnv_t: // u5
2493 case Hexagon::J4_cmpgti_t_jumpnv_nt: // u5
2494 case Hexagon::J4_cmpgti_t_jumpnv_t: // u5
2495 case Hexagon::J4_cmpgtui_f_jumpnv_nt: // u5
2496 case Hexagon::J4_cmpgtui_f_jumpnv_t: // u5
2497 case Hexagon::J4_cmpgtui_t_jumpnv_nt: // u5
2498 case Hexagon::J4_cmpgtui_t_jumpnv_t: // u5
2499 break;
2500 default:
2501 llvm_unreachable("Unhandled instruction");
2502 break;
2503 }
2504
2505 uint64_t Val = MO.getImm();
2506 return APInt(32, Val, Signed);
2507}
2508
2509void HexagonConstEvaluator::replaceWithNop(MachineInstr &MI) {
2510 MI.setDesc(HII.get(Hexagon::A2_nop));
2511 while (MI.getNumOperands() > 0)
2512 MI.removeOperand(0);
2513}
2514
2515bool HexagonConstEvaluator::evaluateHexRSEQ32(RegisterSubReg RL, RegisterSubReg RH,
2516 const CellMap &Inputs, LatticeCell &Result) {
2517 assert(Inputs.has(RL.Reg) && Inputs.has(RH.Reg));
2518 LatticeCell LSL, LSH;
2519 if (!getCell(RL, Inputs, LSL) || !getCell(RH, Inputs, LSH))
2520 return false;
2521 if (LSL.isProperty() || LSH.isProperty())
2522 return false;
2523
2524 unsigned LN = LSL.size(), HN = LSH.size();
2525 SmallVector<APInt,4> LoVs(LN), HiVs(HN);
2526 for (unsigned i = 0; i < LN; ++i) {
2527 bool Eval = constToInt(LSL.Values[i], LoVs[i]);
2528 if (!Eval)
2529 return false;
2530 assert(LoVs[i].getBitWidth() == 32);
2531 }
2532 for (unsigned i = 0; i < HN; ++i) {
2533 bool Eval = constToInt(LSH.Values[i], HiVs[i]);
2534 if (!Eval)
2535 return false;
2536 assert(HiVs[i].getBitWidth() == 32);
2537 }
2538
2539 for (unsigned i = 0; i < HiVs.size(); ++i) {
2540 APInt HV = HiVs[i].zext(64) << 32;
2541 for (unsigned j = 0; j < LoVs.size(); ++j) {
2542 APInt LV = LoVs[j].zext(64);
2543 const Constant *C = intToConst(HV | LV);
2544 Result.add(C);
2545 if (Result.isBottom())
2546 return false;
2547 }
2548 }
2549 return !Result.isBottom();
2550}
2551
2552bool HexagonConstEvaluator::evaluateHexCompare(const MachineInstr &MI,
2553 const CellMap &Inputs, CellMap &Outputs) {
2554 unsigned Opc = MI.getOpcode();
2555 bool Classic = false;
2556 switch (Opc) {
2557 case Hexagon::C2_cmpeq:
2558 case Hexagon::C2_cmpeqp:
2559 case Hexagon::C2_cmpgt:
2560 case Hexagon::C2_cmpgtp:
2561 case Hexagon::C2_cmpgtu:
2562 case Hexagon::C2_cmpgtup:
2563 case Hexagon::C2_cmpeqi:
2564 case Hexagon::C2_cmpgti:
2565 case Hexagon::C2_cmpgtui:
2566 // Classic compare: Dst0 = CMP Src1, Src2
2567 Classic = true;
2568 break;
2569 default:
2570 // Not handling other compare instructions now.
2571 return false;
2572 }
2573
2574 if (Classic) {
2575 const MachineOperand &Src1 = MI.getOperand(1);
2576 const MachineOperand &Src2 = MI.getOperand(2);
2577
2578 bool Result;
2579 unsigned Opc = MI.getOpcode();
2580 bool Computed = evaluateHexCompare2(Opc, Src1, Src2, Inputs, Result);
2581 if (Computed) {
2582 // Only create a zero/non-zero cell. At this time there isn't really
2583 // much need for specific values.
2584 RegisterSubReg DefR(MI.getOperand(0));
2585 LatticeCell L = Outputs.get(DefR.Reg);
2586 uint32_t P = Result ? ConstantProperties::NonZero
2587 : ConstantProperties::Zero;
2588 L.add(P);
2589 Outputs.update(DefR.Reg, L);
2590 return true;
2591 }
2592 }
2593
2594 return false;
2595}
2596
2597bool HexagonConstEvaluator::evaluateHexCompare2(unsigned Opc,
2598 const MachineOperand &Src1, const MachineOperand &Src2,
2599 const CellMap &Inputs, bool &Result) {
2600 uint32_t Cmp = getCmp(Opc);
2601 bool Reg1 = Src1.isReg(), Reg2 = Src2.isReg();
2602 bool Imm1 = Src1.isImm(), Imm2 = Src2.isImm();
2603 if (Reg1) {
2604 RegisterSubReg R1(Src1);
2605 if (Reg2) {
2606 RegisterSubReg R2(Src2);
2607 return evaluateCMPrr(Cmp, R1, R2, Inputs, Result);
2608 } else if (Imm2) {
2609 APInt A2 = getCmpImm(Opc, 2, Src2);
2610 return evaluateCMPri(Cmp, R1, A2, Inputs, Result);
2611 }
2612 } else if (Imm1) {
2613 APInt A1 = getCmpImm(Opc, 1, Src1);
2614 if (Reg2) {
2615 RegisterSubReg R2(Src2);
2616 uint32_t NegCmp = Comparison::negate(Cmp);
2617 return evaluateCMPri(NegCmp, R2, A1, Inputs, Result);
2618 } else if (Imm2) {
2619 APInt A2 = getCmpImm(Opc, 2, Src2);
2620 return evaluateCMPii(Cmp, A1, A2, Result);
2621 }
2622 }
2623 // Unknown kind of comparison.
2624 return false;
2625}
2626
2627bool HexagonConstEvaluator::evaluateHexLogical(const MachineInstr &MI,
2628 const CellMap &Inputs, CellMap &Outputs) {
2629 unsigned Opc = MI.getOpcode();
2630 if (MI.getNumOperands() != 3)
2631 return false;
2632 const MachineOperand &Src1 = MI.getOperand(1);
2633 const MachineOperand &Src2 = MI.getOperand(2);
2634 RegisterSubReg R1(Src1);
2635 bool Eval = false;
2636 LatticeCell RC;
2637 switch (Opc) {
2638 default:
2639 return false;
2640 case Hexagon::A2_and:
2641 case Hexagon::A2_andp:
2642 Eval = evaluateANDrr(R1, RegisterSubReg(Src2), Inputs, RC);
2643 break;
2644 case Hexagon::A2_andir: {
2645 if (!Src2.isImm())
2646 return false;
2647 APInt A(32, Src2.getImm(), true);
2648 Eval = evaluateANDri(R1, A, Inputs, RC);
2649 break;
2650 }
2651 case Hexagon::A2_or:
2652 case Hexagon::A2_orp:
2653 Eval = evaluateORrr(R1, RegisterSubReg(Src2), Inputs, RC);
2654 break;
2655 case Hexagon::A2_orir: {
2656 if (!Src2.isImm())
2657 return false;
2658 APInt A(32, Src2.getImm(), true);
2659 Eval = evaluateORri(R1, A, Inputs, RC);
2660 break;
2661 }
2662 case Hexagon::A2_xor:
2663 case Hexagon::A2_xorp:
2664 Eval = evaluateXORrr(R1, RegisterSubReg(Src2), Inputs, RC);
2665 break;
2666 }
2667 if (Eval) {
2668 RegisterSubReg DefR(MI.getOperand(0));
2669 Outputs.update(DefR.Reg, RC);
2670 }
2671 return Eval;
2672}
2673
2674bool HexagonConstEvaluator::evaluateHexCondMove(const MachineInstr &MI,
2675 const CellMap &Inputs, CellMap &Outputs) {
2676 // Dst0 = Cond1 ? Src2 : Src3
2677 RegisterSubReg CR(MI.getOperand(1));
2678 assert(Inputs.has(CR.Reg));
2679 LatticeCell LS;
2680 if (!getCell(CR, Inputs, LS))
2681 return false;
2682 uint32_t Ps = LS.properties();
2683 unsigned TakeOp;
2684 if (Ps & ConstantProperties::Zero)
2685 TakeOp = 3;
2686 else if (Ps & ConstantProperties::NonZero)
2687 TakeOp = 2;
2688 else
2689 return false;
2690
2691 const MachineOperand &ValOp = MI.getOperand(TakeOp);
2692 RegisterSubReg DefR(MI.getOperand(0));
2693 LatticeCell RC = Outputs.get(DefR.Reg);
2694
2695 if (ValOp.isImm()) {
2696 int64_t V = ValOp.getImm();
2697 unsigned W = getRegBitWidth(DefR.Reg);
2698 APInt A(W, V, true);
2699 const Constant *C = intToConst(A);
2700 RC.add(C);
2701 Outputs.update(DefR.Reg, RC);
2702 return true;
2703 }
2704 if (ValOp.isReg()) {
2705 RegisterSubReg R(ValOp);
2706 const LatticeCell &LR = Inputs.get(R.Reg);
2707 LatticeCell LSR;
2708 if (!evaluate(R, LR, LSR))
2709 return false;
2710 RC.meet(LSR);
2711 Outputs.update(DefR.Reg, RC);
2712 return true;
2713 }
2714 return false;
2715}
2716
2717bool HexagonConstEvaluator::evaluateHexExt(const MachineInstr &MI,
2718 const CellMap &Inputs, CellMap &Outputs) {
2719 // Dst0 = ext R1
2720 RegisterSubReg R1(MI.getOperand(1));
2721 assert(Inputs.has(R1.Reg));
2722
2723 unsigned Opc = MI.getOpcode();
2724 unsigned Bits;
2725 switch (Opc) {
2726 case Hexagon::A2_sxtb:
2727 case Hexagon::A2_zxtb:
2728 Bits = 8;
2729 break;
2730 case Hexagon::A2_sxth:
2731 case Hexagon::A2_zxth:
2732 Bits = 16;
2733 break;
2734 case Hexagon::A2_sxtw:
2735 Bits = 32;
2736 break;
2737 default:
2738 llvm_unreachable("Unhandled extension opcode");
2739 }
2740
2741 bool Signed = false;
2742 switch (Opc) {
2743 case Hexagon::A2_sxtb:
2744 case Hexagon::A2_sxth:
2745 case Hexagon::A2_sxtw:
2746 Signed = true;
2747 break;
2748 }
2749
2750 RegisterSubReg DefR(MI.getOperand(0));
2751 unsigned BW = getRegBitWidth(DefR.Reg);
2752 LatticeCell RC = Outputs.get(DefR.Reg);
2753 bool Eval = Signed ? evaluateSEXTr(R1, BW, Bits, Inputs, RC)
2754 : evaluateZEXTr(R1, BW, Bits, Inputs, RC);
2755 if (!Eval)
2756 return false;
2757 Outputs.update(DefR.Reg, RC);
2758 return true;
2759}
2760
2761bool HexagonConstEvaluator::evaluateHexVector1(const MachineInstr &MI,
2762 const CellMap &Inputs, CellMap &Outputs) {
2763 // DefR = op R1
2764 RegisterSubReg DefR(MI.getOperand(0));
2765 RegisterSubReg R1(MI.getOperand(1));
2766 assert(Inputs.has(R1.Reg));
2767 LatticeCell RC = Outputs.get(DefR.Reg);
2768 bool Eval;
2769
2770 unsigned Opc = MI.getOpcode();
2771 switch (Opc) {
2772 case Hexagon::S2_vsplatrb:
2773 // Rd = 4 times Rs:0..7
2774 Eval = evaluateSplatr(R1, 8, 4, Inputs, RC);
2775 break;
2776 case Hexagon::S2_vsplatrh:
2777 // Rdd = 4 times Rs:0..15
2778 Eval = evaluateSplatr(R1, 16, 4, Inputs, RC);
2779 break;
2780 default:
2781 return false;
2782 }
2783
2784 if (!Eval)
2785 return false;
2786 Outputs.update(DefR.Reg, RC);
2787 return true;
2788}
2789
2790bool HexagonConstEvaluator::rewriteHexConstDefs(MachineInstr &MI,
2791 const CellMap &Inputs, bool &AllDefs) {
2792 AllDefs = false;
2793
2794 // Some diagnostics.
2795 // LLVM_DEBUG({...}) gets confused with all this code as an argument.
2796#ifndef NDEBUG
2797 bool Debugging = DebugFlag && isCurrentDebugType(DEBUG_TYPE);
2798 if (Debugging) {
2799 bool Const = true, HasUse = false;
2800 for (const MachineOperand &MO : MI.operands()) {
2801 if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2802 continue;
2803 RegisterSubReg R(MO);
2804 if (!R.Reg.isVirtual())
2805 continue;
2806 HasUse = true;
2807 // PHIs can legitimately have "top" cells after propagation.
2808 if (!MI.isPHI() && !Inputs.has(R.Reg)) {
2809 dbgs() << "Top " << printReg(R.Reg, &HRI, R.SubReg)
2810 << " in MI: " << MI;
2811 continue;
2812 }
2813 const LatticeCell &L = Inputs.get(R.Reg);
2814 Const &= L.isSingle();
2815 if (!Const)
2816 break;
2817 }
2818 if (HasUse && Const) {
2819 if (!MI.isCopy()) {
2820 dbgs() << "CONST: " << MI;
2821 for (const MachineOperand &MO : MI.operands()) {
2822 if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2823 continue;
2824 Register R = MO.getReg();
2825 dbgs() << printReg(R, &TRI) << ": " << Inputs.get(R) << "\n";
2826 }
2827 }
2828 }
2829 }
2830#endif
2831
2832 // Avoid generating TFRIs for register transfers---this will keep the
2833 // coalescing opportunities.
2834 if (MI.isCopy())
2835 return false;
2836
2837 MachineFunction *MF = MI.getParent()->getParent();
2838 auto &HST = MF->getSubtarget<HexagonSubtarget>();
2839
2840 // Collect all virtual register-def operands.
2842 for (const MachineOperand &MO : MI.operands()) {
2843 if (!MO.isReg() || !MO.isDef())
2844 continue;
2845 Register R = MO.getReg();
2846 if (!R.isVirtual())
2847 continue;
2848 assert(!MO.getSubReg());
2849 assert(Inputs.has(R));
2850 DefRegs.push_back(R);
2851 }
2852
2853 MachineBasicBlock &B = *MI.getParent();
2854 const DebugLoc &DL = MI.getDebugLoc();
2855 unsigned ChangedNum = 0;
2856#ifndef NDEBUG
2858#endif
2859
2860 // For each defined register, if it is a constant, create an instruction
2861 // NewR = const
2862 // and replace all uses of the defined register with NewR.
2863 for (unsigned R : DefRegs) {
2864 const LatticeCell &L = Inputs.get(R);
2865 if (L.isBottom())
2866 continue;
2867 const TargetRegisterClass *RC = MRI->getRegClass(R);
2868 MachineBasicBlock::iterator At = MI.getIterator();
2869
2870 if (!L.isSingle()) {
2871 // If this a zero/non-zero cell, we can fold a definition
2872 // of a predicate register.
2873 using P = ConstantProperties;
2874
2875 uint64_t Ps = L.properties();
2876 if (!(Ps & (P::Zero|P::NonZero)))
2877 continue;
2878 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
2879 if (RC != PredRC)
2880 continue;
2881 const MCInstrDesc *NewD = (Ps & P::Zero) ?
2882 &HII.get(Hexagon::PS_false) :
2883 &HII.get(Hexagon::PS_true);
2884 Register NewR = MRI->createVirtualRegister(PredRC);
2885 const MachineInstrBuilder &MIB = BuildMI(B, At, DL, *NewD, NewR);
2886 (void)MIB;
2887#ifndef NDEBUG
2888 NewInstrs.push_back(&*MIB);
2889#endif
2890 replaceAllRegUsesWith(R, NewR);
2891 } else {
2892 // This cell has a single value.
2893 APInt A;
2894 if (!constToInt(L.Value, A) || !A.isSignedIntN(64))
2895 continue;
2896 const TargetRegisterClass *NewRC;
2897 const MCInstrDesc *NewD;
2898
2899 unsigned W = getRegBitWidth(R);
2900 int64_t V = A.getSExtValue();
2901 assert(W == 32 || W == 64);
2902 if (W == 32)
2903 NewRC = &Hexagon::IntRegsRegClass;
2904 else
2905 NewRC = &Hexagon::DoubleRegsRegClass;
2906 Register NewR = MRI->createVirtualRegister(NewRC);
2907 const MachineInstr *NewMI;
2908
2909 if (W == 32) {
2910 NewD = &HII.get(Hexagon::A2_tfrsi);
2911 NewMI = BuildMI(B, At, DL, *NewD, NewR)
2912 .addImm(V);
2913 } else {
2914 if (A.isSignedIntN(8)) {
2915 NewD = &HII.get(Hexagon::A2_tfrpi);
2916 NewMI = BuildMI(B, At, DL, *NewD, NewR)
2917 .addImm(V);
2918 } else {
2919 int32_t Hi = V >> 32;
2920 int32_t Lo = V & 0xFFFFFFFFLL;
2921 if (isInt<8>(Hi) && isInt<8>(Lo)) {
2922 NewD = &HII.get(Hexagon::A2_combineii);
2923 NewMI = BuildMI(B, At, DL, *NewD, NewR)
2924 .addImm(Hi)
2925 .addImm(Lo);
2926 } else if (MF->getFunction().hasOptSize() || !HST.isTinyCore()) {
2927 // Disable CONST64 for tiny core since it takes a LD resource.
2928 NewD = &HII.get(Hexagon::CONST64);
2929 NewMI = BuildMI(B, At, DL, *NewD, NewR)
2930 .addImm(V);
2931 } else
2932 return false;
2933 }
2934 }
2935 (void)NewMI;
2936#ifndef NDEBUG
2937 NewInstrs.push_back(NewMI);
2938#endif
2939 replaceAllRegUsesWith(R, NewR);
2940 }
2941 ChangedNum++;
2942 }
2943
2944 LLVM_DEBUG({
2945 if (!NewInstrs.empty()) {
2946 MachineFunction &MF = *MI.getParent()->getParent();
2947 dbgs() << "In function: " << MF.getName() << "\n";
2948 dbgs() << "Rewrite: for " << MI << " created " << *NewInstrs[0];
2949 for (unsigned i = 1; i < NewInstrs.size(); ++i)
2950 dbgs() << " " << *NewInstrs[i];
2951 }
2952 });
2953
2954 AllDefs = (ChangedNum == DefRegs.size());
2955 return ChangedNum > 0;
2956}
2957
2958bool HexagonConstEvaluator::rewriteHexConstUses(MachineInstr &MI,
2959 const CellMap &Inputs) {
2960 bool Changed = false;
2961 unsigned Opc = MI.getOpcode();
2962 MachineBasicBlock &B = *MI.getParent();
2963 const DebugLoc &DL = MI.getDebugLoc();
2964 MachineBasicBlock::iterator At = MI.getIterator();
2965 MachineInstr *NewMI = nullptr;
2966
2967 switch (Opc) {
2968 case Hexagon::M2_maci:
2969 // Convert DefR += mpyi(R2, R3)
2970 // to DefR += mpyi(R, #imm),
2971 // or DefR -= mpyi(R, #imm).
2972 {
2973 RegisterSubReg DefR(MI.getOperand(0));
2974 assert(!DefR.SubReg);
2975 RegisterSubReg R2(MI.getOperand(2));
2976 RegisterSubReg R3(MI.getOperand(3));
2977 assert(Inputs.has(R2.Reg) && Inputs.has(R3.Reg));
2978 LatticeCell LS2, LS3;
2979 // It is enough to get one of the input cells, since we will only try
2980 // to replace one argument---whichever happens to be a single constant.
2981 bool HasC2 = getCell(R2, Inputs, LS2), HasC3 = getCell(R3, Inputs, LS3);
2982 if (!HasC2 && !HasC3)
2983 return false;
2984 bool Zero = ((HasC2 && (LS2.properties() & ConstantProperties::Zero)) ||
2985 (HasC3 && (LS3.properties() & ConstantProperties::Zero)));
2986 // If one of the operands is zero, eliminate the multiplication.
2987 if (Zero) {
2988 // DefR == R1 (tied operands).
2989 MachineOperand &Acc = MI.getOperand(1);
2990 RegisterSubReg R1(Acc);
2991 unsigned NewR = R1.Reg;
2992 if (R1.SubReg) {
2993 // Generate COPY. FIXME: Replace with the register:subregister.
2994 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
2995 NewR = MRI->createVirtualRegister(RC);
2996 NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
2997 .addReg(R1.Reg, getRegState(Acc), R1.SubReg);
2998 }
2999 replaceAllRegUsesWith(DefR.Reg, NewR);
3000 MRI->clearKillFlags(NewR);
3001 Changed = true;
3002 break;
3003 }
3004
3005 bool Swap = false;
3006 if (!LS3.isSingle()) {
3007 if (!LS2.isSingle())
3008 return false;
3009 Swap = true;
3010 }
3011 const LatticeCell &LI = Swap ? LS2 : LS3;
3012 const MachineOperand &OpR2 = Swap ? MI.getOperand(3)
3013 : MI.getOperand(2);
3014 // LI is single here.
3015 APInt A;
3016 if (!constToInt(LI.Value, A) || !A.isSignedIntN(8))
3017 return false;
3018 int64_t V = A.getSExtValue();
3019 const MCInstrDesc &D = (V >= 0) ? HII.get(Hexagon::M2_macsip)
3020 : HII.get(Hexagon::M2_macsin);
3021 if (V < 0)
3022 V = -V;
3023 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3024 Register NewR = MRI->createVirtualRegister(RC);
3025 const MachineOperand &Src1 = MI.getOperand(1);
3026 NewMI = BuildMI(B, At, DL, D, NewR)
3027 .addReg(Src1.getReg(), getRegState(Src1), Src1.getSubReg())
3028 .addReg(OpR2.getReg(), getRegState(OpR2), OpR2.getSubReg())
3029 .addImm(V);
3030 replaceAllRegUsesWith(DefR.Reg, NewR);
3031 Changed = true;
3032 break;
3033 }
3034
3035 case Hexagon::A2_and:
3036 {
3037 RegisterSubReg R1(MI.getOperand(1));
3038 RegisterSubReg R2(MI.getOperand(2));
3039 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3040 LatticeCell LS1, LS2;
3041 unsigned CopyOf = 0;
3042 // Check if any of the operands is -1 (i.e. all bits set).
3043 if (getCell(R1, Inputs, LS1) && LS1.isSingle()) {
3044 APInt M1;
3045 if (constToInt(LS1.Value, M1) && !~M1)
3046 CopyOf = 2;
3047 }
3048 else if (getCell(R2, Inputs, LS2) && LS2.isSingle()) {
3049 APInt M1;
3050 if (constToInt(LS2.Value, M1) && !~M1)
3051 CopyOf = 1;
3052 }
3053 if (!CopyOf)
3054 return false;
3055 MachineOperand &SO = MI.getOperand(CopyOf);
3056 RegisterSubReg SR(SO);
3057 RegisterSubReg DefR(MI.getOperand(0));
3058 unsigned NewR = SR.Reg;
3059 if (SR.SubReg) {
3060 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3061 NewR = MRI->createVirtualRegister(RC);
3062 NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3063 .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3064 }
3065 replaceAllRegUsesWith(DefR.Reg, NewR);
3066 MRI->clearKillFlags(NewR);
3067 Changed = true;
3068 }
3069 break;
3070
3071 case Hexagon::A2_or:
3072 {
3073 RegisterSubReg R1(MI.getOperand(1));
3074 RegisterSubReg R2(MI.getOperand(2));
3075 assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3076 LatticeCell LS1, LS2;
3077 unsigned CopyOf = 0;
3078
3079 using P = ConstantProperties;
3080
3081 if (getCell(R1, Inputs, LS1) && (LS1.properties() & P::Zero))
3082 CopyOf = 2;
3083 else if (getCell(R2, Inputs, LS2) && (LS2.properties() & P::Zero))
3084 CopyOf = 1;
3085 if (!CopyOf)
3086 return false;
3087 MachineOperand &SO = MI.getOperand(CopyOf);
3088 RegisterSubReg SR(SO);
3089 RegisterSubReg DefR(MI.getOperand(0));
3090 unsigned NewR = SR.Reg;
3091 if (SR.SubReg) {
3092 const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3093 NewR = MRI->createVirtualRegister(RC);
3094 NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3095 .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3096 }
3097 replaceAllRegUsesWith(DefR.Reg, NewR);
3098 MRI->clearKillFlags(NewR);
3099 Changed = true;
3100 }
3101 break;
3102 }
3103
3104 if (NewMI) {
3105 // clear all the kill flags of this new instruction.
3106 for (MachineOperand &MO : NewMI->operands())
3107 if (MO.isReg() && MO.isUse())
3108 MO.setIsKill(false);
3109 }
3110
3111 LLVM_DEBUG({
3112 if (NewMI) {
3113 dbgs() << "Rewrite: for " << MI;
3114 if (NewMI != &MI)
3115 dbgs() << " created " << *NewMI;
3116 else
3117 dbgs() << " modified the instruction itself and created:" << *NewMI;
3118 }
3119 });
3120
3121 return Changed;
3122}
3123
3124void HexagonConstEvaluator::replaceAllRegUsesWith(Register FromReg,
3125 Register ToReg) {
3126 assert(FromReg.isVirtual());
3127 assert(ToReg.isVirtual());
3128 for (MachineOperand &O :
3129 llvm::make_early_inc_range(MRI->use_operands(FromReg)))
3130 O.setReg(ToReg);
3131}
3132
3133bool HexagonConstEvaluator::rewriteHexBranch(MachineInstr &BrI,
3134 const CellMap &Inputs) {
3135 MachineBasicBlock &B = *BrI.getParent();
3136 unsigned NumOp = BrI.getNumOperands();
3137 if (!NumOp)
3138 return false;
3139
3140 bool FallsThru;
3142 bool Eval = evaluate(BrI, Inputs, Targets, FallsThru);
3143 unsigned NumTargets = Targets.size();
3144 if (!Eval || NumTargets > 1 || (NumTargets == 1 && FallsThru))
3145 return false;
3146 if (BrI.getOpcode() == Hexagon::J2_jump)
3147 return false;
3148
3149 LLVM_DEBUG(dbgs() << "Rewrite(" << printMBBReference(B) << "):" << BrI);
3150 bool Rewritten = false;
3151 if (NumTargets > 0) {
3152 assert(!FallsThru && "This should have been checked before");
3153 // MIB.addMBB needs non-const pointer.
3154 MachineBasicBlock *TargetB = const_cast<MachineBasicBlock*>(Targets[0]);
3155 bool Moot = B.isLayoutSuccessor(TargetB);
3156 if (!Moot) {
3157 // If we build a branch here, we must make sure that it won't be
3158 // erased as "non-executable". We can't mark any new instructions
3159 // as executable here, so we need to overwrite the BrI, which we
3160 // know is executable.
3161 const MCInstrDesc &JD = HII.get(Hexagon::J2_jump);
3162 auto NI = BuildMI(B, BrI.getIterator(), BrI.getDebugLoc(), JD)
3163 .addMBB(TargetB);
3164 BrI.setDesc(JD);
3165 while (BrI.getNumOperands() > 0)
3166 BrI.removeOperand(0);
3167 // This ensures that all implicit operands (e.g. implicit-def %r31, etc)
3168 // are present in the rewritten branch.
3169 for (auto &Op : NI->operands())
3170 BrI.addOperand(Op);
3171 NI->eraseFromParent();
3172 Rewritten = true;
3173 }
3174 }
3175
3176 // Do not erase instructions. A newly created instruction could get
3177 // the same address as an instruction marked as executable during the
3178 // propagation.
3179 if (!Rewritten)
3180 replaceWithNop(BrI);
3181 return true;
3182}
3183
3185 return new HexagonConstPropagation();
3186}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file declares a class to represent arbitrary precision floating point values and provide a varie...
This file implements a class to represent arbitrary precision integral constant values and operations...
ReachingDefAnalysis InstSet & ToRemove
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:148
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Size
bool End
Definition: ELF_riscv.cpp:480
#define DEBUG_TYPE
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
unsigned const TargetRegisterInfo * TRI
#define R2(n)
#define P(N)
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static bool rewrite(Function &F)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
static Comparison getCmp(SelectionDAG &DAG, SDValue CmpOp0, SDValue CmpOp1, ISD::CondCode Cond, const SDLoc &DL, SDValue Chain=SDValue(), bool IsSignaling=false)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
support::ulittle16_t & Lo
Definition: aarch32.cpp:206
support::ulittle16_t & Hi
Definition: aarch32.cpp:205
bool isInfinity() const
Definition: APFloat.h:1292
Class for arbitrary precision integers.
Definition: APInt.h:76
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:981
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1491
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:1002
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:906
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1439
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1089
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:307
unsigned countr_zero() const
Count the number of trailing zero bits.
Definition: APInt.h:1589
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition: APInt.h:1548
unsigned countl_one() const
Count the number of leading one bits.
Definition: APInt.h:1565
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:805
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:954
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:851
static bool isSameValue(const APInt &I1, const APInt &I2)
Determine if two APInts have the same value, after zero-extending one of them (if needed!...
Definition: APInt.h:531
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:284
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1108
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1513
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:829
unsigned countr_one() const
Count the number of trailing one bits.
Definition: APInt.h:1606
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:267
const APFloat & getValueAPF() const
Definition: Constants.h:310
bool isNegative() const
Return true if the sign bit is set.
Definition: Constants.h:317
bool isNaN() const
Return true if the value is a NaN.
Definition: Constants.h:323
bool isZero() const
Return true if the value is positive or negative zero.
Definition: Constants.h:314
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
bool isNegative() const
Definition: Constants.h:199
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:204
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:144
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an Operation in the Expression.
A debug info location.
Definition: DebugLoc.h:33
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:178
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:680
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:342
Class to represent integer types.
Definition: DerivedTypes.h:40
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator_range< succ_iterator > successors()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Function & getFunction()
Return the LLVM function that this machine code represents.
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
BasicBlockListType::const_iterator const_iterator
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Representation of each machine instruction.
Definition: MachineInstr.h:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:544
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:327
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:547
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
void setDesc(const MCInstrDesc &TID)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
bool isUnconditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which always transfers control flow to some other block.
Definition: MachineInstr.h:970
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:660
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:473
void removeOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:554
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
int64_t getImm() const
bool isImplicit() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
void setIsKill(bool Val=true)
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:37
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
A vector that has set insertion semantics.
Definition: SetVector.h:57
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:188
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
void clear()
Completely clear the SetVector.
Definition: SetVector.h:273
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:264
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
static IntegerType * getInt32Ty(LLVMContext &C)
static IntegerType * getInt64Ty(LLVMContext &C)
LLVM Value Representation.
Definition: Value.h:74
self_iterator getIterator()
Definition: ilist_node.h:109
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned getRegBitWidth(const TargetRegisterClass &RC)
Get the size in bits of a register from the register class RC.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:121
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
@ TB
TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...
Definition: X86BaseInfo.h:749
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1689
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
iterator_range< po_iterator< T > > post_order(const T &G)
FunctionPass * createHexagonConstPropagationPass()
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
unsigned M1(unsigned Val)
Definition: VE.h:376
bool DebugFlag
This boolean is set to true if the '-debug' command line option is specified.
Definition: Debug.cpp:45
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
Definition: MathExtras.h:141
bool isCurrentDebugType(const char *Type)
isCurrentDebugType - Return true if the specified string is the debug type specified on the command l...
Definition: Debug.cpp:52
unsigned getRegState(const MachineOperand &RegOp)
Get all register state flags from machine operand RegOp.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
void initializeHexagonConstPropagationPass(PassRegistry &Registry)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
#define N
#define EQ(a, b)
Definition: regexec.c:112