|
121
|
1 //===- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ----------===//
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 // This pass performs loop invariant code motion on machine instructions. We
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 // attempt to remove as much code from the body of a loop as possible.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 // This pass is not intended to be a replacement or a complete alternative
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 // for the LLVM-IR-level LICM pass. It is only designed to hoist simple
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 // constructs that are not exposed before lowering and instruction selection.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18
|
|
121
|
19 #include "llvm/ADT/BitVector.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 #include "llvm/ADT/DenseMap.h"
|
|
121
|
21 #include "llvm/ADT/STLExtras.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 #include "llvm/ADT/SmallSet.h"
|
|
121
|
23 #include "llvm/ADT/SmallVector.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 #include "llvm/ADT/Statistic.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 #include "llvm/Analysis/AliasAnalysis.h"
|
|
121
|
26 #include "llvm/CodeGen/MachineBasicBlock.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 #include "llvm/CodeGen/MachineDominators.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 #include "llvm/CodeGen/MachineFrameInfo.h"
|
|
121
|
29 #include "llvm/CodeGen/MachineFunction.h"
|
|
|
30 #include "llvm/CodeGen/MachineFunctionPass.h"
|
|
|
31 #include "llvm/CodeGen/MachineInstr.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 #include "llvm/CodeGen/MachineLoopInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 #include "llvm/CodeGen/MachineMemOperand.h"
|
|
121
|
34 #include "llvm/CodeGen/MachineOperand.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 #include "llvm/CodeGen/PseudoSourceValue.h"
|
|
134
|
37 #include "llvm/CodeGen/TargetInstrInfo.h"
|
|
|
38 #include "llvm/CodeGen/TargetLowering.h"
|
|
|
39 #include "llvm/CodeGen/TargetRegisterInfo.h"
|
|
95
|
40 #include "llvm/CodeGen/TargetSchedule.h"
|
|
134
|
41 #include "llvm/CodeGen/TargetSubtargetInfo.h"
|
|
121
|
42 #include "llvm/IR/DebugLoc.h"
|
|
|
43 #include "llvm/MC/MCInstrDesc.h"
|
|
|
44 #include "llvm/MC/MCRegisterInfo.h"
|
|
|
45 #include "llvm/Pass.h"
|
|
|
46 #include "llvm/Support/Casting.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 #include "llvm/Support/CommandLine.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 #include "llvm/Support/Debug.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 #include "llvm/Support/raw_ostream.h"
|
|
121
|
50 #include <algorithm>
|
|
|
51 #include <cassert>
|
|
|
52 #include <limits>
|
|
|
53 #include <vector>
|
|
|
54
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56
|
|
121
|
57 #define DEBUG_TYPE "machinelicm"
|
|
77
|
58
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 static cl::opt<bool>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 AvoidSpeculation("avoid-speculation",
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 cl::desc("MachineLICM should avoid speculation"),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 cl::init(true), cl::Hidden);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63
|
|
83
|
64 static cl::opt<bool>
|
|
|
65 HoistCheapInsts("hoist-cheap-insts",
|
|
|
66 cl::desc("MachineLICM should hoist even cheap instructions"),
|
|
|
67 cl::init(false), cl::Hidden);
|
|
|
68
|
|
95
|
69 static cl::opt<bool>
|
|
|
70 SinkInstsToAvoidSpills("sink-insts-to-avoid-spills",
|
|
|
71 cl::desc("MachineLICM should sink instructions into "
|
|
|
72 "loops to avoid register spills"),
|
|
|
73 cl::init(false), cl::Hidden);
|
|
|
74
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 STATISTIC(NumHoisted,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 "Number of machine instructions hoisted out of loops");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 STATISTIC(NumLowRP,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78 "Number of instructions hoisted in low reg pressure situation");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 STATISTIC(NumHighLatency,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 "Number of high latency instructions hoisted");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 STATISTIC(NumCSEed,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 "Number of hoisted machine instructions CSEed");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 STATISTIC(NumPostRAHoisted,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 "Number of machine instructions hoisted out of loops post regalloc");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 namespace {
|
|
121
|
87
|
|
134
|
88 class MachineLICMBase : public MachineFunctionPass {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 const TargetInstrInfo *TII;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 const TargetLoweringBase *TLI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 const TargetRegisterInfo *TRI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 const MachineFrameInfo *MFI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 MachineRegisterInfo *MRI;
|
|
95
|
94 TargetSchedModel SchedModel;
|
|
134
|
95 bool PreRegAlloc;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 // Various analyses that we use...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 AliasAnalysis *AA; // Alias analysis info.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99 MachineLoopInfo *MLI; // Current MachineLoopInfo
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 MachineDominatorTree *DT; // Machine dominator tree for the cur loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 // State that is updated as we process loops
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103 bool Changed; // True if a loop is changed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 bool FirstInLoop; // True if it's the first LICM in the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 MachineLoop *CurLoop; // The current loop we are working on.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 // Exit blocks for CurLoop.
|
|
121
|
109 SmallVector<MachineBasicBlock *, 8> ExitBlocks;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 bool isExitBlock(const MachineBasicBlock *MBB) const {
|
|
120
|
112 return is_contained(ExitBlocks, MBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 // Track 'estimated' register pressure.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 SmallSet<unsigned, 32> RegSeen;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 SmallVector<unsigned, 8> RegPressure;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118
|
|
95
|
119 // Register pressure "limit" per register pressure set. If the pressure
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 // is higher than the limit, then it's considered high.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 SmallVector<unsigned, 8> RegLimit;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 // Register pressure on path leading from loop preheader to current BB.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 SmallVector<SmallVector<unsigned, 8>, 16> BackTrace;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 // For each opcode, keep a list of potential CSE instructions.
|
|
121
|
127 DenseMap<unsigned, std::vector<const MachineInstr *>> CSEMap;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
128
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129 enum {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
130 SpeculateFalse = 0,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
131 SpeculateTrue = 1,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 SpeculateUnknown = 2
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 // If a MBB does not dominate loop exiting blocks then it may not safe
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136 // to hoist loads from this block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 // Tri-state: 0 - false, 1 - true, 2 - unknown
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
138 unsigned SpeculationState;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
140 public:
|
|
134
|
141 MachineLICMBase(char &PassID, bool PreRegAlloc)
|
|
|
142 : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {}
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
143
|
|
77
|
144 bool runOnMachineFunction(MachineFunction &MF) override;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145
|
|
77
|
146 void getAnalysisUsage(AnalysisUsage &AU) const override {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147 AU.addRequired<MachineLoopInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
148 AU.addRequired<MachineDominatorTree>();
|
|
95
|
149 AU.addRequired<AAResultsWrapperPass>();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 AU.addPreserved<MachineLoopInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 AU.addPreserved<MachineDominatorTree>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 MachineFunctionPass::getAnalysisUsage(AU);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154
|
|
77
|
155 void releaseMemory() override {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156 RegSeen.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157 RegPressure.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
158 RegLimit.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
159 BackTrace.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160 CSEMap.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 private:
|
|
100
|
164 /// Keep track of information about hoisting candidates.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 struct CandidateInfo {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 MachineInstr *MI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167 unsigned Def;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168 int FI;
|
|
121
|
169
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 CandidateInfo(MachineInstr *mi, unsigned def, int fi)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 : MI(mi), Def(def), FI(fi) {}
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 void HoistRegionPostRA();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 void HoistPostRA(MachineInstr *MI, unsigned Def);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177
|
|
100
|
178 void ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs,
|
|
|
179 BitVector &PhysRegClobbers, SmallSet<int, 32> &StoredFIs,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 SmallVectorImpl<CandidateInfo> &Candidates);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 void AddToLiveIns(unsigned Reg);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
183
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 bool IsLICMCandidate(MachineInstr &I);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186 bool IsLoopInvariantInst(MachineInstr &I);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
187
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
188 bool HasLoopPHIUse(const MachineInstr *MI) const;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
189
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190 bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
191 unsigned Reg) const;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
192
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
193 bool IsCheapInstruction(MachineInstr &MI) const;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
194
|
|
95
|
195 bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost,
|
|
|
196 bool Cheap);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
197
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198 void UpdateBackTraceRegPressure(const MachineInstr *MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
199
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
200 bool IsProfitableToHoist(MachineInstr &MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
201
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
202 bool IsGuaranteedToExecute(MachineBasicBlock *BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
204 void EnterScope(MachineBasicBlock *MBB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
205
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
206 void ExitScope(MachineBasicBlock *MBB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
207
|
|
100
|
208 void ExitScopeIfDone(
|
|
|
209 MachineDomTreeNode *Node,
|
|
|
210 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
|
|
|
211 DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
212
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
213 void HoistOutOfLoop(MachineDomTreeNode *LoopHeaderNode);
|
|
100
|
214
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
215 void HoistRegion(MachineDomTreeNode *N, bool IsHeader);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
216
|
|
95
|
217 void SinkIntoLoop();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
218
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
219 void InitRegPressure(MachineBasicBlock *BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
220
|
|
95
|
221 DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
|
|
|
222 bool ConsiderSeen,
|
|
|
223 bool ConsiderUnseenAsDef);
|
|
|
224
|
|
|
225 void UpdateRegPressure(const MachineInstr *MI,
|
|
|
226 bool ConsiderUnseenAsDef = false);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
227
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
228 MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
229
|
|
100
|
230 const MachineInstr *
|
|
|
231 LookForDuplicate(const MachineInstr *MI,
|
|
|
232 std::vector<const MachineInstr *> &PrevMIs);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
233
|
|
100
|
234 bool EliminateCSE(
|
|
|
235 MachineInstr *MI,
|
|
|
236 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
237
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
238 bool MayCSE(MachineInstr *MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
239
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
240 bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
241
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
242 void InitCSEMap(MachineBasicBlock *BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
243
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
244 MachineBasicBlock *getCurPreheader();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
245 };
|
|
121
|
246
|
|
134
|
247 class MachineLICM : public MachineLICMBase {
|
|
|
248 public:
|
|
|
249 static char ID;
|
|
|
250 MachineLICM() : MachineLICMBase(ID, false) {
|
|
|
251 initializeMachineLICMPass(*PassRegistry::getPassRegistry());
|
|
|
252 }
|
|
|
253 };
|
|
|
254
|
|
|
255 class EarlyMachineLICM : public MachineLICMBase {
|
|
|
256 public:
|
|
|
257 static char ID;
|
|
|
258 EarlyMachineLICM() : MachineLICMBase(ID, true) {
|
|
|
259 initializeEarlyMachineLICMPass(*PassRegistry::getPassRegistry());
|
|
|
260 }
|
|
|
261 };
|
|
|
262
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
263 } // end anonymous namespace
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
264
|
|
134
|
265 char MachineLICM::ID;
|
|
|
266 char EarlyMachineLICM::ID;
|
|
121
|
267
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
268 char &llvm::MachineLICMID = MachineLICM::ID;
|
|
134
|
269 char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID;
|
|
121
|
270
|
|
|
271 INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
|
|
|
272 "Machine Loop Invariant Code Motion", false, false)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
273 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
274 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
|
|
95
|
275 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
|
|
121
|
276 INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,
|
|
|
277 "Machine Loop Invariant Code Motion", false, false)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
278
|
|
134
|
279 INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
|
|
|
280 "Early Machine Loop Invariant Code Motion", false, false)
|
|
|
281 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
|
|
|
282 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
|
|
|
283 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
|
|
|
284 INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
|
|
|
285 "Early Machine Loop Invariant Code Motion", false, false)
|
|
|
286
|
|
100
|
287 /// Test if the given loop is the outer-most loop that has a unique predecessor.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
288 static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
289 // Check whether this loop even has a unique predecessor.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
290 if (!CurLoop->getLoopPredecessor())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
291 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
292 // Ok, now check to see if any of its outer loops do.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
293 for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
294 if (L->getLoopPredecessor())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
295 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
296 // None of them did, so this is the outermost with a unique predecessor.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
297 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
298 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
299
|
|
134
|
300 bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
|
|
|
301 if (skipFunction(MF.getFunction()))
|
|
77
|
302 return false;
|
|
|
303
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
304 Changed = FirstInLoop = false;
|
|
95
|
305 const TargetSubtargetInfo &ST = MF.getSubtarget();
|
|
|
306 TII = ST.getInstrInfo();
|
|
|
307 TLI = ST.getTargetLowering();
|
|
|
308 TRI = ST.getRegisterInfo();
|
|
120
|
309 MFI = &MF.getFrameInfo();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
310 MRI = &MF.getRegInfo();
|
|
95
|
311 SchedModel.init(ST.getSchedModel(), &ST, TII);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
312
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
313 PreRegAlloc = MRI->isSSA();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
314
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
315 if (PreRegAlloc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
316 DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: ");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
317 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
318 DEBUG(dbgs() << "******** Post-regalloc Machine LICM: ");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
319 DEBUG(dbgs() << MF.getName() << " ********\n");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
320
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
321 if (PreRegAlloc) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
322 // Estimate register pressure during pre-regalloc pass.
|
|
95
|
323 unsigned NumRPS = TRI->getNumRegPressureSets();
|
|
|
324 RegPressure.resize(NumRPS);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
325 std::fill(RegPressure.begin(), RegPressure.end(), 0);
|
|
95
|
326 RegLimit.resize(NumRPS);
|
|
|
327 for (unsigned i = 0, e = NumRPS; i != e; ++i)
|
|
|
328 RegLimit[i] = TRI->getRegPressureSetLimit(MF, i);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
329 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
330
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
331 // Get our Loop information...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
332 MLI = &getAnalysis<MachineLoopInfo>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
333 DT = &getAnalysis<MachineDominatorTree>();
|
|
95
|
334 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
335
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
336 SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
337 while (!Worklist.empty()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
338 CurLoop = Worklist.pop_back_val();
|
|
77
|
339 CurPreheader = nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
340 ExitBlocks.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
341
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
342 // If this is done before regalloc, only visit outer-most preheader-sporting
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
343 // loops.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
344 if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
345 Worklist.append(CurLoop->begin(), CurLoop->end());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
346 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
347 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
348
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
349 CurLoop->getExitBlocks(ExitBlocks);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
350
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
351 if (!PreRegAlloc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
352 HoistRegionPostRA();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
353 else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
354 // CSEMap is initialized for loop header when the first instruction is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
355 // being hoisted.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
356 MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
357 FirstInLoop = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
358 HoistOutOfLoop(N);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
359 CSEMap.clear();
|
|
95
|
360
|
|
|
361 if (SinkInstsToAvoidSpills)
|
|
|
362 SinkIntoLoop();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
363 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
364 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
365
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
366 return Changed;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
367 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
368
|
|
100
|
369 /// Return true if instruction stores to the specified frame.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
370 static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
|
|
100
|
371 // If we lost memory operands, conservatively assume that the instruction
|
|
121
|
372 // writes to all slots.
|
|
100
|
373 if (MI->memoperands_empty())
|
|
|
374 return true;
|
|
|
375 for (const MachineMemOperand *MemOp : MI->memoperands()) {
|
|
|
376 if (!MemOp->isStore() || !MemOp->getPseudoValue())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
377 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
378 if (const FixedStackPseudoSourceValue *Value =
|
|
100
|
379 dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
380 if (Value->getFrameIndex() == FI)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
381 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
382 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
383 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
384 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
385 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
386
|
|
100
|
387 /// Examine the instruction for potentai LICM candidate. Also
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
388 /// gather register def and frame object update information.
|
|
134
|
389 void MachineLICMBase::ProcessMI(MachineInstr *MI,
|
|
|
390 BitVector &PhysRegDefs,
|
|
|
391 BitVector &PhysRegClobbers,
|
|
|
392 SmallSet<int, 32> &StoredFIs,
|
|
|
393 SmallVectorImpl<CandidateInfo> &Candidates) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
394 bool RuledOut = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
395 bool HasNonInvariantUse = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
396 unsigned Def = 0;
|
|
100
|
397 for (const MachineOperand &MO : MI->operands()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
398 if (MO.isFI()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
399 // Remember if the instruction stores to the frame index.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
400 int FI = MO.getIndex();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
401 if (!StoredFIs.count(FI) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
402 MFI->isSpillSlotObjectIndex(FI) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
403 InstructionStoresToFI(MI, FI))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
404 StoredFIs.insert(FI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
405 HasNonInvariantUse = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
406 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
407 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
408
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
409 // We can't hoist an instruction defining a physreg that is clobbered in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
410 // the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
411 if (MO.isRegMask()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
412 PhysRegClobbers.setBitsNotInMask(MO.getRegMask());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
413 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
414 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
415
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
416 if (!MO.isReg())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
417 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
418 unsigned Reg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
419 if (!Reg)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
420 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
421 assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
422 "Not expecting virtual register!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
423
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
424 if (!MO.isDef()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
425 if (Reg && (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg)))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
426 // If it's using a non-loop-invariant register, then it's obviously not
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
427 // safe to hoist.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
428 HasNonInvariantUse = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
429 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
430 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
431
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
432 if (MO.isImplicit()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
433 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
434 PhysRegClobbers.set(*AI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
435 if (!MO.isDead())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
436 // Non-dead implicit def? This cannot be hoisted.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
437 RuledOut = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
438 // No need to check if a dead implicit def is also defined by
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
439 // another instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
440 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
441 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
442
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
443 // FIXME: For now, avoid instructions with multiple defs, unless
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
444 // it's a dead implicit def.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
445 if (Def)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
446 RuledOut = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
447 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
448 Def = Reg;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
449
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
450 // If we have already seen another instruction that defines the same
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
451 // register, then this is not safe. Two defs is indicated by setting a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
452 // PhysRegClobbers bit.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
453 for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
454 if (PhysRegDefs.test(*AS))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
455 PhysRegClobbers.set(*AS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
456 PhysRegDefs.set(*AS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
457 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
458 if (PhysRegClobbers.test(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
459 // MI defined register is seen defined by another instruction in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
460 // the loop, it cannot be a LICM candidate.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
461 RuledOut = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
462 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
463
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
464 // Only consider reloads for now and remats which do not have register
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
465 // operands. FIXME: Consider unfold load folding instructions.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
466 if (Def && !RuledOut) {
|
|
121
|
467 int FI = std::numeric_limits<int>::min();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
468 if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) ||
|
|
120
|
469 (TII->isLoadFromStackSlot(*MI, FI) && MFI->isSpillSlotObjectIndex(FI)))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
470 Candidates.push_back(CandidateInfo(MI, Def, FI));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
471 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
472 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
473
|
|
100
|
474 /// Walk the specified region of the CFG and hoist loop invariants out to the
|
|
|
475 /// preheader.
|
|
134
|
476 void MachineLICMBase::HoistRegionPostRA() {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
477 MachineBasicBlock *Preheader = getCurPreheader();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
478 if (!Preheader)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
479 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
480
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
481 unsigned NumRegs = TRI->getNumRegs();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
482 BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
483 BitVector PhysRegClobbers(NumRegs); // Regs defined more than once.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
484
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
485 SmallVector<CandidateInfo, 32> Candidates;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
486 SmallSet<int, 32> StoredFIs;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
487
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
488 // Walk the entire region, count number of defs for each register, and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
489 // collect potential LICM candidates.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
490 const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks();
|
|
100
|
491 for (MachineBasicBlock *BB : Blocks) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
492 // If the header of the loop containing this basic block is a landing pad,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
493 // then don't try to hoist instructions out of this loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
494 const MachineLoop *ML = MLI->getLoopFor(BB);
|
|
95
|
495 if (ML && ML->getHeader()->isEHPad()) continue;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
496
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
497 // Conservatively treat live-in's as an external def.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
498 // FIXME: That means a reload that're reused in successor block(s) will not
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
499 // be LICM'ed.
|
|
95
|
500 for (const auto &LI : BB->liveins()) {
|
|
|
501 for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
502 PhysRegDefs.set(*AI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
503 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
504
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
505 SpeculationState = SpeculateUnknown;
|
|
100
|
506 for (MachineInstr &MI : *BB)
|
|
|
507 ProcessMI(&MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
508 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
509
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
510 // Gather the registers read / clobbered by the terminator.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
511 BitVector TermRegs(NumRegs);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
512 MachineBasicBlock::iterator TI = Preheader->getFirstTerminator();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
513 if (TI != Preheader->end()) {
|
|
100
|
514 for (const MachineOperand &MO : TI->operands()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
515 if (!MO.isReg())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
516 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
517 unsigned Reg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
518 if (!Reg)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
519 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
520 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
521 TermRegs.set(*AI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
522 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
523 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
524
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
525 // Now evaluate whether the potential candidates qualify.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
526 // 1. Check if the candidate defined register is defined by another
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
527 // instruction in the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
528 // 2. If the candidate is a load from stack slot (always true for now),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
529 // check if the slot is stored anywhere in the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
530 // 3. Make sure candidate def should not clobber
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
531 // registers read by the terminator. Similarly its def should not be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
532 // clobbered by the terminator.
|
|
100
|
533 for (CandidateInfo &Candidate : Candidates) {
|
|
121
|
534 if (Candidate.FI != std::numeric_limits<int>::min() &&
|
|
100
|
535 StoredFIs.count(Candidate.FI))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
536 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
537
|
|
100
|
538 unsigned Def = Candidate.Def;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
539 if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
540 bool Safe = true;
|
|
100
|
541 MachineInstr *MI = Candidate.MI;
|
|
|
542 for (const MachineOperand &MO : MI->operands()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
543 if (!MO.isReg() || MO.isDef() || !MO.getReg())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
544 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
545 unsigned Reg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
546 if (PhysRegDefs.test(Reg) ||
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
547 PhysRegClobbers.test(Reg)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
548 // If it's using a non-loop-invariant register, then it's obviously
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
549 // not safe to hoist.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
550 Safe = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
551 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
552 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
553 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
554 if (Safe)
|
|
100
|
555 HoistPostRA(MI, Candidate.Def);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
556 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
557 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
558 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
559
|
|
100
|
560 /// Add register 'Reg' to the livein sets of BBs in the current loop, and make
|
|
|
561 /// sure it is not killed by any instructions in the loop.
|
|
134
|
562 void MachineLICMBase::AddToLiveIns(unsigned Reg) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
563 const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks();
|
|
100
|
564 for (MachineBasicBlock *BB : Blocks) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
565 if (!BB->isLiveIn(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
566 BB->addLiveIn(Reg);
|
|
100
|
567 for (MachineInstr &MI : *BB) {
|
|
|
568 for (MachineOperand &MO : MI.operands()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
569 if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
570 if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg()))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
571 MO.setIsKill(false);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
572 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
573 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
574 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
575 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
576
|
|
100
|
577 /// When an instruction is found to only use loop invariant operands that is
|
|
|
578 /// safe to hoist, this instruction is called to do the dirty work.
|
|
134
|
579 void MachineLICMBase::HoistPostRA(MachineInstr *MI, unsigned Def) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
580 MachineBasicBlock *Preheader = getCurPreheader();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
581
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
582 // Now move the instructions to the predecessor, inserting it before any
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
583 // terminator instructions.
|
|
134
|
584 DEBUG(dbgs() << "Hoisting to " << printMBBReference(*Preheader) << " from "
|
|
|
585 << printMBBReference(*MI->getParent()) << ": " << *MI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
586
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
587 // Splice the instruction to the preheader.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
588 MachineBasicBlock *MBB = MI->getParent();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
589 Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
590
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
591 // Add register to livein list to all the BBs in the current loop since a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
592 // loop invariant must be kept live throughout the whole loop. This is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593 // important to ensure later passes do not scavenge the def register.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
594 AddToLiveIns(Def);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
595
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
596 ++NumPostRAHoisted;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
597 Changed = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599
|
|
100
|
600 /// Check if this mbb is guaranteed to execute. If not then a load from this mbb
|
|
|
601 /// may not be safe to hoist.
|
|
134
|
602 bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
603 if (SpeculationState != SpeculateUnknown)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
604 return SpeculationState == SpeculateFalse;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
605
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
606 if (BB != CurLoop->getHeader()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
607 // Check loop exiting blocks.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
608 SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
609 CurLoop->getExitingBlocks(CurrentLoopExitingBlocks);
|
|
100
|
610 for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
|
|
|
611 if (!DT->dominates(BB, CurrentLoopExitingBlock)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
612 SpeculationState = SpeculateTrue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
613 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
614 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
615 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
616
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
617 SpeculationState = SpeculateFalse;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
618 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
619 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
620
|
|
134
|
621 void MachineLICMBase::EnterScope(MachineBasicBlock *MBB) {
|
|
|
622 DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n');
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
623
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
624 // Remember livein register pressure.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
625 BackTrace.push_back(RegPressure);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
626 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
627
|
|
134
|
628 void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) {
|
|
|
629 DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
630 BackTrace.pop_back();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
631 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
632
|
|
100
|
633 /// Destroy scope for the MBB that corresponds to the given dominator tree node
|
|
|
634 /// if its a leaf or all of its children are done. Walk up the dominator tree to
|
|
|
635 /// destroy ancestors which are now done.
|
|
134
|
636 void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node,
|
|
|
637 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
|
|
|
638 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
639 if (OpenChildren[Node])
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
640 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
641
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
642 // Pop scope.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
643 ExitScope(Node->getBlock());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
644
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
645 // Now traverse upwards to pop ancestors whose offsprings are all done.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
646 while (MachineDomTreeNode *Parent = ParentMap[Node]) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
647 unsigned Left = --OpenChildren[Parent];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
648 if (Left != 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
649 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
650 ExitScope(Parent->getBlock());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
651 Node = Parent;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
652 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
653 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
654
|
|
100
|
655 /// Walk the specified loop in the CFG (defined by all blocks dominated by the
|
|
|
656 /// specified header block, and that are in the current loop) in depth first
|
|
|
657 /// order w.r.t the DominatorTree. This allows us to visit definitions before
|
|
|
658 /// uses, allowing us to hoist a loop body in one pass without iteration.
|
|
134
|
659 void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
|
|
83
|
660 MachineBasicBlock *Preheader = getCurPreheader();
|
|
|
661 if (!Preheader)
|
|
|
662 return;
|
|
|
663
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
664 SmallVector<MachineDomTreeNode*, 32> Scopes;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
665 SmallVector<MachineDomTreeNode*, 8> WorkList;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
666 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
667 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
668
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
669 // Perform a DFS walk to determine the order of visit.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
670 WorkList.push_back(HeaderN);
|
|
83
|
671 while (!WorkList.empty()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
672 MachineDomTreeNode *Node = WorkList.pop_back_val();
|
|
77
|
673 assert(Node && "Null dominator tree node?");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
674 MachineBasicBlock *BB = Node->getBlock();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
675
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
676 // If the header of the loop containing this basic block is a landing pad,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
677 // then don't try to hoist instructions out of this loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
678 const MachineLoop *ML = MLI->getLoopFor(BB);
|
|
95
|
679 if (ML && ML->getHeader()->isEHPad())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
680 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
681
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
682 // If this subregion is not in the top level loop at all, exit.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
683 if (!CurLoop->contains(BB))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
684 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
685
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
686 Scopes.push_back(Node);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
687 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
688 unsigned NumChildren = Children.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
689
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
690 // Don't hoist things out of a large switch statement. This often causes
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
691 // code to be hoisted that wasn't going to be executed, and increases
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
692 // register pressure in a situation where it's likely to matter.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
693 if (BB->succ_size() >= 25)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
694 NumChildren = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
695
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
696 OpenChildren[Node] = NumChildren;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
697 // Add children in reverse order as then the next popped worklist node is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
698 // the first child of this node. This means we ultimately traverse the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
699 // DOM tree in exactly the same order as if we'd recursed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
700 for (int i = (int)NumChildren-1; i >= 0; --i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
701 MachineDomTreeNode *Child = Children[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
702 ParentMap[Child] = Node;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
703 WorkList.push_back(Child);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
704 }
|
|
83
|
705 }
|
|
|
706
|
|
|
707 if (Scopes.size() == 0)
|
|
|
708 return;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
709
|
|
83
|
710 // Compute registers which are livein into the loop headers.
|
|
|
711 RegSeen.clear();
|
|
|
712 BackTrace.clear();
|
|
|
713 InitRegPressure(Preheader);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
714
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
715 // Now perform LICM.
|
|
100
|
716 for (MachineDomTreeNode *Node : Scopes) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
717 MachineBasicBlock *MBB = Node->getBlock();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
718
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
719 EnterScope(MBB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
720
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
721 // Process the block
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
722 SpeculationState = SpeculateUnknown;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
723 for (MachineBasicBlock::iterator
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
724 MII = MBB->begin(), E = MBB->end(); MII != E; ) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
725 MachineBasicBlock::iterator NextMII = MII; ++NextMII;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
726 MachineInstr *MI = &*MII;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
727 if (!Hoist(MI, Preheader))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
728 UpdateRegPressure(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
729 MII = NextMII;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
730 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
731
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
732 // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
733 ExitScopeIfDone(Node, OpenChildren, ParentMap);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
734 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
735 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
736
|
|
100
|
737 /// Sink instructions into loops if profitable. This especially tries to prevent
|
|
|
738 /// register spills caused by register pressure if there is little to no
|
|
|
739 /// overhead moving instructions into loops.
|
|
134
|
740 void MachineLICMBase::SinkIntoLoop() {
|
|
95
|
741 MachineBasicBlock *Preheader = getCurPreheader();
|
|
|
742 if (!Preheader)
|
|
|
743 return;
|
|
|
744
|
|
|
745 SmallVector<MachineInstr *, 8> Candidates;
|
|
|
746 for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin();
|
|
|
747 I != Preheader->instr_end(); ++I) {
|
|
|
748 // We need to ensure that we can safely move this instruction into the loop.
|
|
121
|
749 // As such, it must not have side-effects, e.g. such as a call has.
|
|
95
|
750 if (IsLoopInvariantInst(*I) && !HasLoopPHIUse(&*I))
|
|
|
751 Candidates.push_back(&*I);
|
|
|
752 }
|
|
|
753
|
|
|
754 for (MachineInstr *I : Candidates) {
|
|
|
755 const MachineOperand &MO = I->getOperand(0);
|
|
|
756 if (!MO.isDef() || !MO.isReg() || !MO.getReg())
|
|
|
757 continue;
|
|
|
758 if (!MRI->hasOneDef(MO.getReg()))
|
|
|
759 continue;
|
|
|
760 bool CanSink = true;
|
|
|
761 MachineBasicBlock *B = nullptr;
|
|
|
762 for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
|
|
|
763 // FIXME: Come up with a proper cost model that estimates whether sinking
|
|
|
764 // the instruction (and thus possibly executing it on every loop
|
|
|
765 // iteration) is more expensive than a register.
|
|
|
766 // For now assumes that copies are cheap and thus almost always worth it.
|
|
|
767 if (!MI.isCopy()) {
|
|
|
768 CanSink = false;
|
|
|
769 break;
|
|
|
770 }
|
|
|
771 if (!B) {
|
|
|
772 B = MI.getParent();
|
|
|
773 continue;
|
|
|
774 }
|
|
|
775 B = DT->findNearestCommonDominator(B, MI.getParent());
|
|
|
776 if (!B) {
|
|
|
777 CanSink = false;
|
|
|
778 break;
|
|
|
779 }
|
|
|
780 }
|
|
|
781 if (!CanSink || !B || B == Preheader)
|
|
|
782 continue;
|
|
|
783 B->splice(B->getFirstNonPHI(), Preheader, I);
|
|
|
784 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
785 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
786
|
|
95
|
787 static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
|
|
|
788 return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
789 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
790
|
|
100
|
791 /// Find all virtual register references that are liveout of the preheader to
|
|
|
792 /// initialize the starting "register pressure". Note this does not count live
|
|
|
793 /// through (livein but not used) registers.
|
|
134
|
794 void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
795 std::fill(RegPressure.begin(), RegPressure.end(), 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
796
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
797 // If the preheader has only a single predecessor and it ends with a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
798 // fallthrough or an unconditional branch, then scan its predecessor for live
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
799 // defs as well. This happens whenever the preheader is created by splitting
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
800 // the critical edge from the loop predecessor to the loop header.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
801 if (BB->pred_size() == 1) {
|
|
77
|
802 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
803 SmallVector<MachineOperand, 4> Cond;
|
|
120
|
804 if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
805 InitRegPressure(*BB->pred_begin());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
806 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
807
|
|
95
|
808 for (const MachineInstr &MI : *BB)
|
|
|
809 UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
810 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
811
|
|
100
|
812 /// Update estimate of register pressure after the specified instruction.
|
|
134
|
813 void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI,
|
|
|
814 bool ConsiderUnseenAsDef) {
|
|
95
|
815 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
|
|
|
816 for (const auto &RPIdAndCost : Cost) {
|
|
|
817 unsigned Class = RPIdAndCost.first;
|
|
|
818 if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second)
|
|
|
819 RegPressure[Class] = 0;
|
|
|
820 else
|
|
|
821 RegPressure[Class] += RPIdAndCost.second;
|
|
|
822 }
|
|
|
823 }
|
|
|
824
|
|
100
|
825 /// Calculate the additional register pressure that the registers used in MI
|
|
|
826 /// cause.
|
|
|
827 ///
|
|
|
828 /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
|
|
|
829 /// figure out which usages are live-ins.
|
|
|
830 /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
|
|
95
|
831 DenseMap<unsigned, int>
|
|
134
|
832 MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
|
|
|
833 bool ConsiderUnseenAsDef) {
|
|
95
|
834 DenseMap<unsigned, int> Cost;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
835 if (MI->isImplicitDef())
|
|
95
|
836 return Cost;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
837 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
838 const MachineOperand &MO = MI->getOperand(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
839 if (!MO.isReg() || MO.isImplicit())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
840 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
841 unsigned Reg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
842 if (!TargetRegisterInfo::isVirtualRegister(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
843 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
844
|
|
95
|
845 // FIXME: It seems bad to use RegSeen only for some of these calculations.
|
|
|
846 bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false;
|
|
|
847 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
|
|
|
848
|
|
|
849 RegClassWeight W = TRI->getRegClassWeight(RC);
|
|
|
850 int RCCost = 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
851 if (MO.isDef())
|
|
95
|
852 RCCost = W.RegWeight;
|
|
|
853 else {
|
|
|
854 bool isKill = isOperandKill(MO, MRI);
|
|
|
855 if (isNew && !isKill && ConsiderUnseenAsDef)
|
|
|
856 // Haven't seen this, it must be a livein.
|
|
|
857 RCCost = W.RegWeight;
|
|
|
858 else if (!isNew && isKill)
|
|
|
859 RCCost = -W.RegWeight;
|
|
|
860 }
|
|
|
861 if (RCCost == 0)
|
|
|
862 continue;
|
|
|
863 const int *PS = TRI->getRegClassPressureSets(RC);
|
|
|
864 for (; *PS != -1; ++PS) {
|
|
|
865 if (Cost.find(*PS) == Cost.end())
|
|
|
866 Cost[*PS] = RCCost;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
867 else
|
|
95
|
868 Cost[*PS] += RCCost;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
869 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
870 }
|
|
95
|
871 return Cost;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
872 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
873
|
|
100
|
874 /// Return true if this machine instruction loads from global offset table or
|
|
|
875 /// constant pool.
|
|
|
876 static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
|
|
121
|
877 assert(MI.mayLoad() && "Expected MI that loads!");
|
|
|
878
|
|
100
|
879 // If we lost memory operands, conservatively assume that the instruction
|
|
121
|
880 // reads from everything..
|
|
100
|
881 if (MI.memoperands_empty())
|
|
|
882 return true;
|
|
|
883
|
|
|
884 for (MachineMemOperand *MemOp : MI.memoperands())
|
|
|
885 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
|
|
95
|
886 if (PSV->isGOT() || PSV->isConstantPool())
|
|
77
|
887 return true;
|
|
100
|
888
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
889 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
890 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
891
|
|
100
|
892 /// Returns true if the instruction may be a suitable candidate for LICM.
|
|
|
893 /// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
|
|
134
|
894 bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
895 // Check if it's safe to move the instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
896 bool DontMoveAcrossStore = true;
|
|
95
|
897 if (!I.isSafeToMove(AA, DontMoveAcrossStore))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
898 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
899
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
900 // If it is load then check if it is guaranteed to execute by making sure that
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
901 // it dominates all exiting blocks. If it doesn't, then there is a path out of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
902 // the loop which does not execute this load, so we can't hoist it. Loads
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
903 // from constant memory are not safe to speculate all the time, for example
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
904 // indexed load from a jump table.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
905 // Stores and side effects are already checked by isSafeToMove.
|
|
100
|
906 if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) &&
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
907 !IsGuaranteedToExecute(I.getParent()))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
908 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
909
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
910 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
911 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
912
|
|
100
|
913 /// Returns true if the instruction is loop invariant.
|
|
|
914 /// I.e., all virtual register operands are defined outside of the loop,
|
|
|
915 /// physical registers aren't accessed explicitly, and there are no side
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
916 /// effects that aren't captured by the operands or other flags.
|
|
134
|
917 bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
918 if (!IsLICMCandidate(I))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
919 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
920
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
921 // The instruction is loop invariant if all of its operands are.
|
|
100
|
922 for (const MachineOperand &MO : I.operands()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
923 if (!MO.isReg())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
924 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
925
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
926 unsigned Reg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
927 if (Reg == 0) continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
928
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
929 // Don't hoist an instruction that uses or defines a physical register.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
930 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
931 if (MO.isUse()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
932 // If the physreg has no defs anywhere, it's just an ambient register
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
933 // and we can freely move its uses. Alternatively, if it's allocatable,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
934 // it could get allocated to something with a def during allocation.
|
|
121
|
935 // However, if the physreg is known to always be caller saved/restored
|
|
|
936 // then this use is safe to hoist.
|
|
|
937 if (!MRI->isConstantPhysReg(Reg) &&
|
|
|
938 !(TRI->isCallerPreservedPhysReg(Reg, *I.getMF())))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
939 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
940 // Otherwise it's safe to move.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
941 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
942 } else if (!MO.isDead()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
943 // A def that isn't dead. We can't move it.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
944 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
945 } else if (CurLoop->getHeader()->isLiveIn(Reg)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
946 // If the reg is live into the loop, we can't hoist an instruction
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
947 // which would clobber it.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
948 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
949 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
950 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
951
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
952 if (!MO.isUse())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
953 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
954
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
955 assert(MRI->getVRegDef(Reg) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
956 "Machine instr not mapped for this vreg?!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
957
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
958 // If the loop contains the definition of an operand, then the instruction
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
959 // isn't loop invariant.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
960 if (CurLoop->contains(MRI->getVRegDef(Reg)))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
961 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
962 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
963
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
964 // If we got this far, the instruction is loop invariant!
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
965 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
966 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
967
|
|
100
|
968 /// Return true if the specified instruction is used by a phi node and hoisting
|
|
|
969 /// it could cause a copy to be inserted.
|
|
134
|
970 bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
971 SmallVector<const MachineInstr*, 8> Work(1, MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
972 do {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
973 MI = Work.pop_back_val();
|
|
95
|
974 for (const MachineOperand &MO : MI->operands()) {
|
|
|
975 if (!MO.isReg() || !MO.isDef())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
976 continue;
|
|
95
|
977 unsigned Reg = MO.getReg();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
978 if (!TargetRegisterInfo::isVirtualRegister(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
979 continue;
|
|
77
|
980 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
981 // A PHI may cause a copy to be inserted.
|
|
77
|
982 if (UseMI.isPHI()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
983 // A PHI inside the loop causes a copy because the live range of Reg is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
984 // extended across the PHI.
|
|
77
|
985 if (CurLoop->contains(&UseMI))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
986 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
987 // A PHI in an exit block can cause a copy to be inserted if the PHI
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
988 // has multiple predecessors in the loop with different values.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
989 // For now, approximate by rejecting all exit blocks.
|
|
77
|
990 if (isExitBlock(UseMI.getParent()))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
991 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
992 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
993 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
994 // Look past copies as well.
|
|
77
|
995 if (UseMI.isCopy() && CurLoop->contains(&UseMI))
|
|
|
996 Work.push_back(&UseMI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
997 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
998 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
999 } while (!Work.empty());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1000 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1001 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1002
|
|
100
|
1003 /// Compute operand latency between a def of 'Reg' and an use in the current
|
|
|
1004 /// loop, return true if the target considered it high.
|
|
134
|
1005 bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI,
|
|
|
1006 unsigned DefIdx,
|
|
|
1007 unsigned Reg) const {
|
|
95
|
1008 if (MRI->use_nodbg_empty(Reg))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1009 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1010
|
|
77
|
1011 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
|
|
|
1012 if (UseMI.isCopyLike())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1013 continue;
|
|
77
|
1014 if (!CurLoop->contains(UseMI.getParent()))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1015 continue;
|
|
77
|
1016 for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) {
|
|
|
1017 const MachineOperand &MO = UseMI.getOperand(i);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1018 if (!MO.isReg() || !MO.isUse())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1019 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1020 unsigned MOReg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1021 if (MOReg != Reg)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1022 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1023
|
|
120
|
1024 if (TII->hasHighOperandLatency(SchedModel, MRI, MI, DefIdx, UseMI, i))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1025 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1026 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1027
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1028 // Only look at the first in loop use.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1029 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1030 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1031
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1032 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1033 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1034
|
|
100
|
1035 /// Return true if the instruction is marked "cheap" or the operand latency
|
|
|
1036 /// between its def and a use is one or less.
|
|
134
|
1037 bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const {
|
|
120
|
1038 if (TII->isAsCheapAsAMove(MI) || MI.isCopyLike())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1039 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1040
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1041 bool isCheap = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1042 unsigned NumDefs = MI.getDesc().getNumDefs();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1043 for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1044 MachineOperand &DefMO = MI.getOperand(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1045 if (!DefMO.isReg() || !DefMO.isDef())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1046 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1047 --NumDefs;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1048 unsigned Reg = DefMO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1049 if (TargetRegisterInfo::isPhysicalRegister(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1050 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1051
|
|
120
|
1052 if (!TII->hasLowDefLatency(SchedModel, MI, i))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1053 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1054 isCheap = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1055 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1056
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1057 return isCheap;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1058 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1059
|
|
100
|
1060 /// Visit BBs from header to current BB, check if hoisting an instruction of the
|
|
|
1061 /// given cost matrix can cause high register pressure.
|
|
134
|
1062 bool
|
|
|
1063 MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
|
|
|
1064 bool CheapInstr) {
|
|
95
|
1065 for (const auto &RPIdAndCost : Cost) {
|
|
|
1066 if (RPIdAndCost.second <= 0)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1067 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1068
|
|
95
|
1069 unsigned Class = RPIdAndCost.first;
|
|
|
1070 int Limit = RegLimit[Class];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1071
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1072 // Don't hoist cheap instructions if they would increase register pressure,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1073 // even if we're under the limit.
|
|
83
|
1074 if (CheapInstr && !HoistCheapInsts)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1075 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1076
|
|
95
|
1077 for (const auto &RP : BackTrace)
|
|
|
1078 if (static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1079 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1080 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1081
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1082 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1083 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1084
|
|
100
|
1085 /// Traverse the back trace from header to the current block and update their
|
|
|
1086 /// register pressures to reflect the effect of hoisting MI from the current
|
|
|
1087 /// block to the preheader.
|
|
134
|
1088 void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1089 // First compute the 'cost' of the instruction, i.e. its contribution
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1090 // to register pressure.
|
|
95
|
1091 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
|
|
|
1092 /*ConsiderUnseenAsDef=*/false);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1093
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1094 // Update register pressure of blocks from loop header to current block.
|
|
95
|
1095 for (auto &RP : BackTrace)
|
|
|
1096 for (const auto &RPIdAndCost : Cost)
|
|
|
1097 RP[RPIdAndCost.first] += RPIdAndCost.second;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1098 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1099
|
|
100
|
1100 /// Return true if it is potentially profitable to hoist the given loop
|
|
|
1101 /// invariant.
|
|
134
|
1102 bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1103 if (MI.isImplicitDef())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1104 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1105
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1106 // Besides removing computation from the loop, hoisting an instruction has
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1107 // these effects:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1108 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1109 // - The value defined by the instruction becomes live across the entire
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1110 // loop. This increases register pressure in the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1111 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1112 // - If the value is used by a PHI in the loop, a copy will be required for
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1113 // lowering the PHI after extending the live range.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1114 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1115 // - When hoisting the last use of a value in the loop, that value no longer
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1116 // needs to be live in the loop. This lowers register pressure in the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1117
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1118 bool CheapInstr = IsCheapInstruction(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1119 bool CreatesCopy = HasLoopPHIUse(&MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1120
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1121 // Don't hoist a cheap instruction if it would create a copy in the loop.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1122 if (CheapInstr && CreatesCopy) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1123 DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1124 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1125 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1126
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1127 // Rematerializable instructions should always be hoisted since the register
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1128 // allocator can just pull them down again when needed.
|
|
120
|
1129 if (TII->isTriviallyReMaterializable(MI, AA))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1130 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1131
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1132 // FIXME: If there are long latency loop-invariant instructions inside the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1133 // loop at this point, why didn't the optimizer's LICM hoist them?
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1134 for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1135 const MachineOperand &MO = MI.getOperand(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1136 if (!MO.isReg() || MO.isImplicit())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1137 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1138 unsigned Reg = MO.getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1139 if (!TargetRegisterInfo::isVirtualRegister(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1140 continue;
|
|
95
|
1141 if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) {
|
|
|
1142 DEBUG(dbgs() << "Hoist High Latency: " << MI);
|
|
|
1143 ++NumHighLatency;
|
|
|
1144 return true;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1145 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1146 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1147
|
|
95
|
1148 // Estimate register pressure to determine whether to LICM the instruction.
|
|
|
1149 // In low register pressure situation, we can be more aggressive about
|
|
|
1150 // hoisting. Also, favors hoisting long latency instructions even in
|
|
|
1151 // moderately high pressure situation.
|
|
|
1152 // Cheap instructions will only be hoisted if they don't increase register
|
|
|
1153 // pressure at all.
|
|
|
1154 auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false,
|
|
|
1155 /*ConsiderUnseenAsDef=*/false);
|
|
|
1156
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1157 // Visit BBs from header to current BB, if hoisting this doesn't cause
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1158 // high register pressure, then it's safe to proceed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1159 if (!CanCauseHighRegPressure(Cost, CheapInstr)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1160 DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1161 ++NumLowRP;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1162 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1163 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1164
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1165 // Don't risk increasing register pressure if it would create copies.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1166 if (CreatesCopy) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1167 DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1168 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1169 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1170
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1171 // Do not "speculate" in high register pressure situation. If an
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1172 // instruction is not guaranteed to be executed in the loop, it's best to be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1173 // conservative.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1174 if (AvoidSpeculation &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1175 (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1176 DEBUG(dbgs() << "Won't speculate: " << MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1177 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1178 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1179
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1180 // High register pressure situation, only hoist if the instruction is going
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1181 // to be remat'ed.
|
|
120
|
1182 if (!TII->isTriviallyReMaterializable(MI, AA) &&
|
|
|
1183 !MI.isDereferenceableInvariantLoad(AA)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1184 DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1185 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1186 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1187
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1188 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1189 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1190
|
|
100
|
1191 /// Unfold a load from the given machineinstr if the load itself could be
|
|
|
1192 /// hoisted. Return the unfolded and hoistable load, or null if the load
|
|
|
1193 /// couldn't be unfolded or if it wouldn't be hoistable.
|
|
134
|
1194 MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1195 // Don't unfold simple loads.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1196 if (MI->canFoldAsLoad())
|
|
77
|
1197 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1198
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1199 // If not, we may be able to unfold a load and hoist that.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1200 // First test whether the instruction is loading from an amenable
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1201 // memory location.
|
|
120
|
1202 if (!MI->isDereferenceableInvariantLoad(AA))
|
|
77
|
1203 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1204
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1205 // Next determine the register class for a temporary register.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1206 unsigned LoadRegIndex;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1207 unsigned NewOpc =
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1208 TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1209 /*UnfoldLoad=*/true,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1210 /*UnfoldStore=*/false,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1211 &LoadRegIndex);
|
|
77
|
1212 if (NewOpc == 0) return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1213 const MCInstrDesc &MID = TII->get(NewOpc);
|
|
121
|
1214 MachineFunction &MF = *MI->getMF();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1215 const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1216 // Ok, we're unfolding. Create a temporary register and do the unfold.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1217 unsigned Reg = MRI->createVirtualRegister(RC);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1218
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1219 SmallVector<MachineInstr *, 2> NewMIs;
|
|
120
|
1220 bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg,
|
|
|
1221 /*UnfoldLoad=*/true,
|
|
|
1222 /*UnfoldStore=*/false, NewMIs);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1223 (void)Success;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1224 assert(Success &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1225 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1226 "succeeded!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1227 assert(NewMIs.size() == 2 &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1228 "Unfolded a load into multiple instructions!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1229 MachineBasicBlock *MBB = MI->getParent();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1230 MachineBasicBlock::iterator Pos = MI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1231 MBB->insert(Pos, NewMIs[0]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1232 MBB->insert(Pos, NewMIs[1]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1233 // If unfolding produced a load that wasn't loop-invariant or profitable to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1234 // hoist, discard the new instructions and bail.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1235 if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1236 NewMIs[0]->eraseFromParent();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1237 NewMIs[1]->eraseFromParent();
|
|
77
|
1238 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1239 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1240
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1241 // Update register pressure for the unfolded instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1242 UpdateRegPressure(NewMIs[1]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1243
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1244 // Otherwise we successfully unfolded a load that we can hoist.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1245 MI->eraseFromParent();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1246 return NewMIs[0];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1247 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1248
|
|
100
|
1249 /// Initialize the CSE map with instructions that are in the current loop
|
|
|
1250 /// preheader that may become duplicates of instructions that are hoisted
|
|
|
1251 /// out of the loop.
|
|
134
|
1252 void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) {
|
|
100
|
1253 for (MachineInstr &MI : *BB)
|
|
|
1254 CSEMap[MI.getOpcode()].push_back(&MI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1255 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1256
|
|
100
|
1257 /// Find an instruction amount PrevMIs that is a duplicate of MI.
|
|
|
1258 /// Return this instruction if it's found.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1259 const MachineInstr*
|
|
134
|
1260 MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
|
|
|
1261 std::vector<const MachineInstr*> &PrevMIs) {
|
|
100
|
1262 for (const MachineInstr *PrevMI : PrevMIs)
|
|
120
|
1263 if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1264 return PrevMI;
|
|
100
|
1265
|
|
77
|
1266 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1267 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1268
|
|
100
|
1269 /// Given a LICM'ed instruction, look for an instruction on the preheader that
|
|
|
1270 /// computes the same value. If it's found, do a RAU on with the definition of
|
|
|
1271 /// the existing instruction rather than hoisting the instruction to the
|
|
|
1272 /// preheader.
|
|
134
|
1273 bool MachineLICMBase::EliminateCSE(MachineInstr *MI,
|
|
|
1274 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1275 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1276 // the undef property onto uses.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1277 if (CI == CSEMap.end() || MI->isImplicitDef())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1278 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1279
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1280 if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1281 DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1282
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1283 // Replace virtual registers defined by MI by their counterparts defined
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1284 // by Dup.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1285 SmallVector<unsigned, 2> Defs;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1286 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1287 const MachineOperand &MO = MI->getOperand(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1288
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1289 // Physical registers may not differ here.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1290 assert((!MO.isReg() || MO.getReg() == 0 ||
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1291 !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) ||
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1292 MO.getReg() == Dup->getOperand(i).getReg()) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1293 "Instructions with different phys regs are not identical!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1294
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1295 if (MO.isReg() && MO.isDef() &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1296 !TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1297 Defs.push_back(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1298 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1299
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1300 SmallVector<const TargetRegisterClass*, 2> OrigRCs;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1301 for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1302 unsigned Idx = Defs[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1303 unsigned Reg = MI->getOperand(Idx).getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1304 unsigned DupReg = Dup->getOperand(Idx).getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1305 OrigRCs.push_back(MRI->getRegClass(DupReg));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1306
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1307 if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1308 // Restore old RCs if more than one defs.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1309 for (unsigned j = 0; j != i; ++j)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1310 MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1311 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1312 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1313 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1314
|
|
100
|
1315 for (unsigned Idx : Defs) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1316 unsigned Reg = MI->getOperand(Idx).getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1317 unsigned DupReg = Dup->getOperand(Idx).getReg();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1318 MRI->replaceRegWith(Reg, DupReg);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1319 MRI->clearKillFlags(DupReg);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1320 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1321
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1322 MI->eraseFromParent();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1323 ++NumCSEed;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1324 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1325 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1326 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1327 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1328
|
|
100
|
1329 /// Return true if the given instruction will be CSE'd if it's hoisted out of
|
|
|
1330 /// the loop.
|
|
134
|
1331 bool MachineLICMBase::MayCSE(MachineInstr *MI) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1332 unsigned Opcode = MI->getOpcode();
|
|
121
|
1333 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1334 CI = CSEMap.find(Opcode);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1335 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1336 // the undef property onto uses.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1337 if (CI == CSEMap.end() || MI->isImplicitDef())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1338 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1339
|
|
77
|
1340 return LookForDuplicate(MI, CI->second) != nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1341 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1342
|
|
100
|
1343 /// When an instruction is found to use only loop invariant operands
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1344 /// that are safe to hoist, this instruction is called to do the dirty work.
|
|
100
|
1345 /// It returns true if the instruction is hoisted.
|
|
134
|
1346 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1347 // First check whether we should hoist this instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1348 if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1349 // If not, try unfolding a hoistable load.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1350 MI = ExtractHoistableLoad(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1351 if (!MI) return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1352 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1353
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1354 // Now move the instructions to the predecessor, inserting it before any
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1355 // terminator instructions.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1356 DEBUG({
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1357 dbgs() << "Hoisting " << *MI;
|
|
120
|
1358 if (MI->getParent()->getBasicBlock())
|
|
134
|
1359 dbgs() << " from " << printMBBReference(*MI->getParent());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1360 if (Preheader->getBasicBlock())
|
|
134
|
1361 dbgs() << " to " << printMBBReference(*Preheader);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1362 dbgs() << "\n";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1363 });
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1364
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1365 // If this is the first instruction being hoisted to the preheader,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1366 // initialize the CSE map with potential common expressions.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1367 if (FirstInLoop) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1368 InitCSEMap(Preheader);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1369 FirstInLoop = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1370 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1371
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1372 // Look for opportunity to CSE the hoisted instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1373 unsigned Opcode = MI->getOpcode();
|
|
121
|
1374 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1375 CI = CSEMap.find(Opcode);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1376 if (!EliminateCSE(MI, CI)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1377 // Otherwise, splice the instruction to the preheader.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1378 Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1379
|
|
121
|
1380 // Since we are moving the instruction out of its basic block, we do not
|
|
|
1381 // retain its debug location. Doing so would degrade the debugging
|
|
|
1382 // experience and adversely affect the accuracy of profiling information.
|
|
|
1383 MI->setDebugLoc(DebugLoc());
|
|
|
1384
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1385 // Update register pressure for BBs from header to this block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1386 UpdateBackTraceRegPressure(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1387
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1388 // Clear the kill flags of any register this instruction defines,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1389 // since they may need to be live throughout the entire loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1390 // rather than just live for part of it.
|
|
100
|
1391 for (MachineOperand &MO : MI->operands())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1392 if (MO.isReg() && MO.isDef() && !MO.isDead())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1393 MRI->clearKillFlags(MO.getReg());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1394
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1395 // Add to the CSE map.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1396 if (CI != CSEMap.end())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1397 CI->second.push_back(MI);
|
|
83
|
1398 else
|
|
|
1399 CSEMap[Opcode].push_back(MI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1400 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1401
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1402 ++NumHoisted;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1403 Changed = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1404
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1405 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1406 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1407
|
|
100
|
1408 /// Get the preheader for the current loop, splitting a critical edge if needed.
|
|
134
|
1409 MachineBasicBlock *MachineLICMBase::getCurPreheader() {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1410 // Determine the block to which to hoist instructions. If we can't find a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1411 // suitable loop predecessor, we can't do any hoisting.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1412
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1413 // If we've tried to get a preheader and failed, don't try again.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1414 if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
|
|
77
|
1415 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1416
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1417 if (!CurPreheader) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1418 CurPreheader = CurLoop->getLoopPreheader();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1419 if (!CurPreheader) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1420 MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1421 if (!Pred) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1422 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
|
|
77
|
1423 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1424 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1425
|
|
120
|
1426 CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), *this);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1427 if (!CurPreheader) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1428 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
|
|
77
|
1429 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1430 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1431 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1432 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1433 return CurPreheader;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1434 }
|
