Coverage Report

Created: 2017-10-03 07:32

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