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