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