blob: 768fe554e3d3a9b1b0ea369259aabcbfb8689352 [file] [log] [blame]
Aart Bik281c6812016-08-26 11:31:48 -07001/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_
18#define ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_
19
Vladimir Markoca6fff82017-10-03 14:49:14 +010020#include "base/scoped_arena_allocator.h"
21#include "base/scoped_arena_containers.h"
Aart Bik281c6812016-08-26 11:31:48 -070022#include "induction_var_range.h"
23#include "nodes.h"
24#include "optimization.h"
25
26namespace art {
27
Aart Bik92685a82017-03-06 11:13:43 -080028class CompilerDriver;
29
Aart Bik281c6812016-08-26 11:31:48 -070030/**
31 * Loop optimizations. Builds a loop hierarchy and applies optimizations to
Aart Bikf8f5a162017-02-06 15:35:29 -080032 * the detected nested loops, such as removal of dead induction and empty loops
33 * and inner loop vectorization.
Aart Bik281c6812016-08-26 11:31:48 -070034 */
35class HLoopOptimization : public HOptimization {
36 public:
Aart Bik92685a82017-03-06 11:13:43 -080037 HLoopOptimization(HGraph* graph,
38 CompilerDriver* compiler_driver,
Aart Bikb92cc332017-09-06 15:53:17 -070039 HInductionVarAnalysis* induction_analysis,
40 OptimizingCompilerStats* stats);
Aart Bik281c6812016-08-26 11:31:48 -070041
42 void Run() OVERRIDE;
43
44 static constexpr const char* kLoopOptimizationPassName = "loop_optimization";
45
46 private:
47 /**
48 * A single loop inside the loop hierarchy representation.
49 */
Aart Bik96202302016-10-04 17:33:56 -070050 struct LoopNode : public ArenaObject<kArenaAllocLoopOptimization> {
Aart Bik281c6812016-08-26 11:31:48 -070051 explicit LoopNode(HLoopInformation* lp_info)
52 : loop_info(lp_info),
53 outer(nullptr),
54 inner(nullptr),
55 previous(nullptr),
56 next(nullptr) {}
Aart Bikf8f5a162017-02-06 15:35:29 -080057 HLoopInformation* loop_info;
Aart Bik281c6812016-08-26 11:31:48 -070058 LoopNode* outer;
59 LoopNode* inner;
60 LoopNode* previous;
61 LoopNode* next;
62 };
63
Aart Bikf8f5a162017-02-06 15:35:29 -080064 /*
65 * Vectorization restrictions (bit mask).
66 */
67 enum VectorRestrictions {
Aart Bik0148de42017-09-05 09:25:01 -070068 kNone = 0, // no restrictions
69 kNoMul = 1 << 0, // no multiplication
70 kNoDiv = 1 << 1, // no division
71 kNoShift = 1 << 2, // no shift
72 kNoShr = 1 << 3, // no arithmetic shift right
73 kNoHiBits = 1 << 4, // "wider" operations cannot bring in higher order bits
74 kNoSignedHAdd = 1 << 5, // no signed halving add
75 kNoUnroundedHAdd = 1 << 6, // no unrounded halving add
76 kNoAbs = 1 << 7, // no absolute value
77 kNoMinMax = 1 << 8, // no min/max
78 kNoStringCharAt = 1 << 9, // no StringCharAt
79 kNoReduction = 1 << 10, // no reduction
Aart Bikdbbac8f2017-09-01 13:06:08 -070080 kNoSAD = 1 << 11, // no sum of absolute differences (SAD)
Artem Serov6e9b1372017-10-05 16:48:30 +010081 kNoWideSAD = 1 << 12, // no sum of absolute differences (SAD) with operand widening
Aart Bikf8f5a162017-02-06 15:35:29 -080082 };
Aart Bik96202302016-10-04 17:33:56 -070083
Aart Bikf8f5a162017-02-06 15:35:29 -080084 /*
85 * Vectorization mode during synthesis
86 * (sequential peeling/cleanup loop or vector loop).
87 */
88 enum VectorMode {
89 kSequential,
90 kVector
91 };
92
93 /*
94 * Representation of a unit-stride array reference.
95 */
96 struct ArrayReference {
Vladimir Marko0ebe0d82017-09-21 22:50:39 +010097 ArrayReference(HInstruction* b, HInstruction* o, DataType::Type t, bool l)
Aart Bikf8f5a162017-02-06 15:35:29 -080098 : base(b), offset(o), type(t), lhs(l) { }
99 bool operator<(const ArrayReference& other) const {
100 return
101 (base < other.base) ||
102 (base == other.base &&
103 (offset < other.offset || (offset == other.offset &&
104 (type < other.type ||
105 (type == other.type && lhs < other.lhs)))));
106 }
107 HInstruction* base; // base address
108 HInstruction* offset; // offset + i
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100109 DataType::Type type; // component type
Aart Bikf8f5a162017-02-06 15:35:29 -0800110 bool lhs; // def/use
111 };
112
Aart Bikb29f6842017-07-28 15:58:41 -0700113 //
Aart Bikf8f5a162017-02-06 15:35:29 -0800114 // Loop setup and traversal.
Aart Bikb29f6842017-07-28 15:58:41 -0700115 //
116
Aart Bikf8f5a162017-02-06 15:35:29 -0800117 void LocalRun();
Aart Bik281c6812016-08-26 11:31:48 -0700118 void AddLoop(HLoopInformation* loop_info);
119 void RemoveLoop(LoopNode* node);
Aart Bik281c6812016-08-26 11:31:48 -0700120
Aart Bikb29f6842017-07-28 15:58:41 -0700121 // Traverses all loops inner to outer to perform simplifications and optimizations.
122 // Returns true if loops nested inside current loop (node) have changed.
123 bool TraverseLoopsInnerToOuter(LoopNode* node);
124
125 //
Aart Bikf8f5a162017-02-06 15:35:29 -0800126 // Optimization.
Aart Bikb29f6842017-07-28 15:58:41 -0700127 //
128
Aart Bik281c6812016-08-26 11:31:48 -0700129 void SimplifyInduction(LoopNode* node);
Aart Bik482095d2016-10-10 15:39:10 -0700130 void SimplifyBlocks(LoopNode* node);
Aart Bikf8f5a162017-02-06 15:35:29 -0800131
Aart Bikb29f6842017-07-28 15:58:41 -0700132 // Performs optimizations specific to inner loop (empty loop removal,
133 // unrolling, vectorization). Returns true if anything changed.
134 bool OptimizeInnerLoop(LoopNode* node);
135
136 //
Aart Bikf8f5a162017-02-06 15:35:29 -0800137 // Vectorization analysis and synthesis.
Aart Bikb29f6842017-07-28 15:58:41 -0700138 //
139
Aart Bik14a68b42017-06-08 14:06:58 -0700140 bool ShouldVectorize(LoopNode* node, HBasicBlock* block, int64_t trip_count);
Aart Bikf8f5a162017-02-06 15:35:29 -0800141 void Vectorize(LoopNode* node, HBasicBlock* block, HBasicBlock* exit, int64_t trip_count);
142 void GenerateNewLoop(LoopNode* node,
143 HBasicBlock* block,
144 HBasicBlock* new_preheader,
145 HInstruction* lo,
146 HInstruction* hi,
Aart Bik14a68b42017-06-08 14:06:58 -0700147 HInstruction* step,
148 uint32_t unroll);
Aart Bikf8f5a162017-02-06 15:35:29 -0800149 bool VectorizeDef(LoopNode* node, HInstruction* instruction, bool generate_code);
150 bool VectorizeUse(LoopNode* node,
151 HInstruction* instruction,
152 bool generate_code,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100153 DataType::Type type,
Aart Bikf8f5a162017-02-06 15:35:29 -0800154 uint64_t restrictions);
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100155 bool TrySetVectorType(DataType::Type type, /*out*/ uint64_t* restrictions);
Aart Bikf8f5a162017-02-06 15:35:29 -0800156 bool TrySetVectorLength(uint32_t length);
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100157 void GenerateVecInv(HInstruction* org, DataType::Type type);
Aart Bik14a68b42017-06-08 14:06:58 -0700158 void GenerateVecSub(HInstruction* org, HInstruction* offset);
Aart Bikf8f5a162017-02-06 15:35:29 -0800159 void GenerateVecMem(HInstruction* org,
160 HInstruction* opa,
161 HInstruction* opb,
Aart Bik14a68b42017-06-08 14:06:58 -0700162 HInstruction* offset,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100163 DataType::Type type);
Aart Bik0148de42017-09-05 09:25:01 -0700164 void GenerateVecReductionPhi(HPhi* phi);
165 void GenerateVecReductionPhiInputs(HPhi* phi, HInstruction* reduction);
166 HInstruction* ReduceAndExtractIfNeeded(HInstruction* instruction);
Aart Bik304c8a52017-05-23 11:01:13 -0700167 void GenerateVecOp(HInstruction* org,
168 HInstruction* opa,
169 HInstruction* opb,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100170 DataType::Type type,
Aart Bik304c8a52017-05-23 11:01:13 -0700171 bool is_unsigned = false);
Aart Bik281c6812016-08-26 11:31:48 -0700172
Aart Bikf3e61ee2017-04-12 17:09:20 -0700173 // Vectorization idioms.
174 bool VectorizeHalvingAddIdiom(LoopNode* node,
175 HInstruction* instruction,
176 bool generate_code,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100177 DataType::Type type,
Aart Bikf3e61ee2017-04-12 17:09:20 -0700178 uint64_t restrictions);
Aart Bikdbbac8f2017-09-01 13:06:08 -0700179 bool VectorizeSADIdiom(LoopNode* node,
180 HInstruction* instruction,
181 bool generate_code,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100182 DataType::Type type,
Aart Bikdbbac8f2017-09-01 13:06:08 -0700183 uint64_t restrictions);
Aart Bikf3e61ee2017-04-12 17:09:20 -0700184
Aart Bik14a68b42017-06-08 14:06:58 -0700185 // Vectorization heuristics.
186 bool IsVectorizationProfitable(int64_t trip_count);
Aart Bikb29f6842017-07-28 15:58:41 -0700187 void SetPeelingCandidate(const ArrayReference* candidate, int64_t trip_count);
Aart Bik14a68b42017-06-08 14:06:58 -0700188 uint32_t GetUnrollingFactor(HBasicBlock* block, int64_t trip_count);
189
Aart Bikb29f6842017-07-28 15:58:41 -0700190 //
Aart Bik6b69e0a2017-01-11 10:20:43 -0800191 // Helpers.
Aart Bikb29f6842017-07-28 15:58:41 -0700192 //
193
Aart Bikf8f5a162017-02-06 15:35:29 -0800194 bool TrySetPhiInduction(HPhi* phi, bool restrict_uses);
Aart Bikb29f6842017-07-28 15:58:41 -0700195 bool TrySetPhiReduction(HPhi* phi);
196
197 // Detects loop header with a single induction (returned in main_phi), possibly
198 // other phis for reductions, but no other side effects. Returns true on success.
199 bool TrySetSimpleLoopHeader(HBasicBlock* block, /*out*/ HPhi** main_phi);
200
Aart Bikcc42be02016-10-20 16:14:16 -0700201 bool IsEmptyBody(HBasicBlock* block);
Aart Bik482095d2016-10-10 15:39:10 -0700202 bool IsOnlyUsedAfterLoop(HLoopInformation* loop_info,
Aart Bik8c4a8542016-10-06 11:36:57 -0700203 HInstruction* instruction,
Aart Bik6b69e0a2017-01-11 10:20:43 -0800204 bool collect_loop_uses,
Aart Bik8c4a8542016-10-06 11:36:57 -0700205 /*out*/ int32_t* use_count);
Aart Bikf8f5a162017-02-06 15:35:29 -0800206 bool IsUsedOutsideLoop(HLoopInformation* loop_info,
207 HInstruction* instruction);
Nicolas Geoffray1a0a5192017-06-22 11:56:01 +0100208 bool TryReplaceWithLastValue(HLoopInformation* loop_info,
209 HInstruction* instruction,
210 HBasicBlock* block);
Aart Bikf8f5a162017-02-06 15:35:29 -0800211 bool TryAssignLastValue(HLoopInformation* loop_info,
212 HInstruction* instruction,
213 HBasicBlock* block,
214 bool collect_loop_uses);
Aart Bik6b69e0a2017-01-11 10:20:43 -0800215 void RemoveDeadInstructions(const HInstructionList& list);
Nicolas Geoffray1a0a5192017-06-22 11:56:01 +0100216 bool CanRemoveCycle(); // Whether the current 'iset_' is removable.
Aart Bik281c6812016-08-26 11:31:48 -0700217
Aart Bik92685a82017-03-06 11:13:43 -0800218 // Compiler driver (to query ISA features).
219 const CompilerDriver* compiler_driver_;
220
Aart Bik96202302016-10-04 17:33:56 -0700221 // Range information based on prior induction variable analysis.
Aart Bik281c6812016-08-26 11:31:48 -0700222 InductionVarRange induction_range_;
223
224 // Phase-local heap memory allocator for the loop optimizer. Storage obtained
Aart Bik96202302016-10-04 17:33:56 -0700225 // through this allocator is immediately released when the loop optimizer is done.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100226 ScopedArenaAllocator* loop_allocator_;
Aart Bik281c6812016-08-26 11:31:48 -0700227
Aart Bikf8f5a162017-02-06 15:35:29 -0800228 // Global heap memory allocator. Used to build HIR.
229 ArenaAllocator* global_allocator_;
230
Aart Bik96202302016-10-04 17:33:56 -0700231 // Entries into the loop hierarchy representation. The hierarchy resides
232 // in phase-local heap memory.
Aart Bik281c6812016-08-26 11:31:48 -0700233 LoopNode* top_loop_;
234 LoopNode* last_loop_;
235
Aart Bik8c4a8542016-10-06 11:36:57 -0700236 // Temporary bookkeeping of a set of instructions.
237 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100238 ScopedArenaSet<HInstruction*>* iset_;
Aart Bik8c4a8542016-10-06 11:36:57 -0700239
Aart Bikb29f6842017-07-28 15:58:41 -0700240 // Temporary bookkeeping of reduction instructions. Mapping is two-fold:
241 // (1) reductions in the loop-body are mapped back to their phi definition,
242 // (2) phi definitions are mapped to their initial value (updated during
243 // code generation to feed the proper values into the new chain).
244 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100245 ScopedArenaSafeMap<HInstruction*, HInstruction*>* reductions_;
Aart Bik482095d2016-10-10 15:39:10 -0700246
Aart Bikdf7822e2016-12-06 10:05:30 -0800247 // Flag that tracks if any simplifications have occurred.
248 bool simplified_;
249
Aart Bikf8f5a162017-02-06 15:35:29 -0800250 // Number of "lanes" for selected packed type.
251 uint32_t vector_length_;
252
253 // Set of array references in the vector loop.
254 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100255 ScopedArenaSet<ArrayReference>* vector_refs_;
Aart Bikf8f5a162017-02-06 15:35:29 -0800256
Aart Bik14a68b42017-06-08 14:06:58 -0700257 // Dynamic loop peeling candidate for alignment.
258 const ArrayReference* vector_peeling_candidate_;
259
260 // Dynamic data dependence test of the form a != b.
261 HInstruction* vector_runtime_test_a_;
262 HInstruction* vector_runtime_test_b_;
263
Aart Bikf8f5a162017-02-06 15:35:29 -0800264 // Mapping used during vectorization synthesis for both the scalar peeling/cleanup
Aart Bik14a68b42017-06-08 14:06:58 -0700265 // loop (mode is kSequential) and the actual vector loop (mode is kVector). The data
Aart Bikf8f5a162017-02-06 15:35:29 -0800266 // structure maps original instructions into the new instructions.
267 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100268 ScopedArenaSafeMap<HInstruction*, HInstruction*>* vector_map_;
Aart Bikf8f5a162017-02-06 15:35:29 -0800269
Aart Bik0148de42017-09-05 09:25:01 -0700270 // Permanent mapping used during vectorization synthesis.
271 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100272 ScopedArenaSafeMap<HInstruction*, HInstruction*>* vector_permanent_map_;
Aart Bik0148de42017-09-05 09:25:01 -0700273
Aart Bikf8f5a162017-02-06 15:35:29 -0800274 // Temporary vectorization bookkeeping.
Aart Bik14a68b42017-06-08 14:06:58 -0700275 VectorMode vector_mode_; // synthesis mode
Aart Bikf8f5a162017-02-06 15:35:29 -0800276 HBasicBlock* vector_preheader_; // preheader of the new loop
277 HBasicBlock* vector_header_; // header of the new loop
278 HBasicBlock* vector_body_; // body of the new loop
Aart Bik14a68b42017-06-08 14:06:58 -0700279 HInstruction* vector_index_; // normalized index of the new loop
Aart Bikf8f5a162017-02-06 15:35:29 -0800280
Aart Bik281c6812016-08-26 11:31:48 -0700281 friend class LoopOptimizationTest;
282
283 DISALLOW_COPY_AND_ASSIGN(HLoopOptimization);
284};
285
286} // namespace art
287
288#endif // ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_