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