Coverage Report

Created: 2019-07-24 05:18

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