Bug Summary

File:lib/Target/Hexagon/HexagonConstPropagation.cpp
Warning:line 2722, column 24
3rd function call argument is an uninitialized value

Annotated Source Code

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