blob: a707ad13580fc341de6ed5d1eb4327822189b146 [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,
Aart Bik2ca10eb2017-11-15 15:17:53 -080040 OptimizingCompilerStats* stats,
41 const char* name = kLoopOptimizationPassName);
Aart Bik281c6812016-08-26 11:31:48 -070042
43 void Run() OVERRIDE;
44
45 static constexpr const char* kLoopOptimizationPassName = "loop_optimization";
46
47 private:
48 /**
49 * A single loop inside the loop hierarchy representation.
50 */
Aart Bik96202302016-10-04 17:33:56 -070051 struct LoopNode : public ArenaObject<kArenaAllocLoopOptimization> {
Aart Bik281c6812016-08-26 11:31:48 -070052 explicit LoopNode(HLoopInformation* lp_info)
53 : loop_info(lp_info),
54 outer(nullptr),
55 inner(nullptr),
56 previous(nullptr),
57 next(nullptr) {}
Aart Bikf8f5a162017-02-06 15:35:29 -080058 HLoopInformation* loop_info;
Aart Bik281c6812016-08-26 11:31:48 -070059 LoopNode* outer;
60 LoopNode* inner;
61 LoopNode* previous;
62 LoopNode* next;
63 };
64
Aart Bikf8f5a162017-02-06 15:35:29 -080065 /*
66 * Vectorization restrictions (bit mask).
67 */
68 enum VectorRestrictions {
Aart Bik0148de42017-09-05 09:25:01 -070069 kNone = 0, // no restrictions
70 kNoMul = 1 << 0, // no multiplication
71 kNoDiv = 1 << 1, // no division
72 kNoShift = 1 << 2, // no shift
73 kNoShr = 1 << 3, // no arithmetic shift right
74 kNoHiBits = 1 << 4, // "wider" operations cannot bring in higher order bits
75 kNoSignedHAdd = 1 << 5, // no signed halving add
76 kNoUnroundedHAdd = 1 << 6, // no unrounded halving add
77 kNoAbs = 1 << 7, // no absolute value
78 kNoMinMax = 1 << 8, // no min/max
79 kNoStringCharAt = 1 << 9, // no StringCharAt
80 kNoReduction = 1 << 10, // no reduction
Aart Bikdbbac8f2017-09-01 13:06:08 -070081 kNoSAD = 1 << 11, // no sum of absolute differences (SAD)
Artem Serov6e9b1372017-10-05 16:48:30 +010082 kNoWideSAD = 1 << 12, // no sum of absolute differences (SAD) with operand widening
Aart Bikf8f5a162017-02-06 15:35:29 -080083 };
Aart Bik96202302016-10-04 17:33:56 -070084
Aart Bikf8f5a162017-02-06 15:35:29 -080085 /*
86 * Vectorization mode during synthesis
87 * (sequential peeling/cleanup loop or vector loop).
88 */
89 enum VectorMode {
90 kSequential,
91 kVector
92 };
93
94 /*
95 * Representation of a unit-stride array reference.
96 */
97 struct ArrayReference {
Aart Bik38a3f212017-10-20 17:02:21 -070098 ArrayReference(HInstruction* b, HInstruction* o, DataType::Type t, bool l, bool c = false)
99 : base(b), offset(o), type(t), lhs(l), is_string_char_at(c) { }
Aart Bikf8f5a162017-02-06 15:35:29 -0800100 bool operator<(const ArrayReference& other) const {
101 return
102 (base < other.base) ||
103 (base == other.base &&
104 (offset < other.offset || (offset == other.offset &&
105 (type < other.type ||
Aart Bik38a3f212017-10-20 17:02:21 -0700106 (type == other.type &&
107 (lhs < other.lhs ||
108 (lhs == other.lhs &&
109 is_string_char_at < other.is_string_char_at)))))));
Aart Bikf8f5a162017-02-06 15:35:29 -0800110 }
Aart Bik38a3f212017-10-20 17:02:21 -0700111 HInstruction* base; // base address
112 HInstruction* offset; // offset + i
113 DataType::Type type; // component type
114 bool lhs; // def/use
115 bool is_string_char_at; // compressed string read
Aart Bikf8f5a162017-02-06 15:35:29 -0800116 };
117
Aart Bikb29f6842017-07-28 15:58:41 -0700118 //
Aart Bikf8f5a162017-02-06 15:35:29 -0800119 // Loop setup and traversal.
Aart Bikb29f6842017-07-28 15:58:41 -0700120 //
121
Aart Bikf8f5a162017-02-06 15:35:29 -0800122 void LocalRun();
Aart Bik281c6812016-08-26 11:31:48 -0700123 void AddLoop(HLoopInformation* loop_info);
124 void RemoveLoop(LoopNode* node);
Aart Bik281c6812016-08-26 11:31:48 -0700125
Aart Bikb29f6842017-07-28 15:58:41 -0700126 // Traverses all loops inner to outer to perform simplifications and optimizations.
127 // Returns true if loops nested inside current loop (node) have changed.
128 bool TraverseLoopsInnerToOuter(LoopNode* node);
129
130 //
Aart Bikf8f5a162017-02-06 15:35:29 -0800131 // Optimization.
Aart Bikb29f6842017-07-28 15:58:41 -0700132 //
133
Aart Bik281c6812016-08-26 11:31:48 -0700134 void SimplifyInduction(LoopNode* node);
Aart Bik482095d2016-10-10 15:39:10 -0700135 void SimplifyBlocks(LoopNode* node);
Aart Bikf8f5a162017-02-06 15:35:29 -0800136
Aart Bikb29f6842017-07-28 15:58:41 -0700137 // Performs optimizations specific to inner loop (empty loop removal,
138 // unrolling, vectorization). Returns true if anything changed.
139 bool OptimizeInnerLoop(LoopNode* node);
140
141 //
Aart Bikf8f5a162017-02-06 15:35:29 -0800142 // Vectorization analysis and synthesis.
Aart Bikb29f6842017-07-28 15:58:41 -0700143 //
144
Aart Bik14a68b42017-06-08 14:06:58 -0700145 bool ShouldVectorize(LoopNode* node, HBasicBlock* block, int64_t trip_count);
Aart Bikf8f5a162017-02-06 15:35:29 -0800146 void Vectorize(LoopNode* node, HBasicBlock* block, HBasicBlock* exit, int64_t trip_count);
147 void GenerateNewLoop(LoopNode* node,
148 HBasicBlock* block,
149 HBasicBlock* new_preheader,
150 HInstruction* lo,
151 HInstruction* hi,
Aart Bik14a68b42017-06-08 14:06:58 -0700152 HInstruction* step,
153 uint32_t unroll);
Aart Bikf8f5a162017-02-06 15:35:29 -0800154 bool VectorizeDef(LoopNode* node, HInstruction* instruction, bool generate_code);
155 bool VectorizeUse(LoopNode* node,
156 HInstruction* instruction,
157 bool generate_code,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100158 DataType::Type type,
Aart Bikf8f5a162017-02-06 15:35:29 -0800159 uint64_t restrictions);
Aart Bik38a3f212017-10-20 17:02:21 -0700160 uint32_t GetVectorSizeInBytes();
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100161 bool TrySetVectorType(DataType::Type type, /*out*/ uint64_t* restrictions);
Aart Bikf8f5a162017-02-06 15:35:29 -0800162 bool TrySetVectorLength(uint32_t length);
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100163 void GenerateVecInv(HInstruction* org, DataType::Type type);
Aart Bik14a68b42017-06-08 14:06:58 -0700164 void GenerateVecSub(HInstruction* org, HInstruction* offset);
Aart Bikf8f5a162017-02-06 15:35:29 -0800165 void GenerateVecMem(HInstruction* org,
166 HInstruction* opa,
167 HInstruction* opb,
Aart Bik14a68b42017-06-08 14:06:58 -0700168 HInstruction* offset,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100169 DataType::Type type);
Aart Bik0148de42017-09-05 09:25:01 -0700170 void GenerateVecReductionPhi(HPhi* phi);
171 void GenerateVecReductionPhiInputs(HPhi* phi, HInstruction* reduction);
172 HInstruction* ReduceAndExtractIfNeeded(HInstruction* instruction);
Aart Bik304c8a52017-05-23 11:01:13 -0700173 void GenerateVecOp(HInstruction* org,
174 HInstruction* opa,
175 HInstruction* opb,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100176 DataType::Type type,
Aart Bik304c8a52017-05-23 11:01:13 -0700177 bool is_unsigned = false);
Aart Bik281c6812016-08-26 11:31:48 -0700178
Aart Bikf3e61ee2017-04-12 17:09:20 -0700179 // Vectorization idioms.
180 bool VectorizeHalvingAddIdiom(LoopNode* node,
181 HInstruction* instruction,
182 bool generate_code,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100183 DataType::Type type,
Aart Bikf3e61ee2017-04-12 17:09:20 -0700184 uint64_t restrictions);
Aart Bikdbbac8f2017-09-01 13:06:08 -0700185 bool VectorizeSADIdiom(LoopNode* node,
186 HInstruction* instruction,
187 bool generate_code,
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100188 DataType::Type type,
Aart Bikdbbac8f2017-09-01 13:06:08 -0700189 uint64_t restrictions);
Aart Bikf3e61ee2017-04-12 17:09:20 -0700190
Aart Bik14a68b42017-06-08 14:06:58 -0700191 // Vectorization heuristics.
Aart Bik38a3f212017-10-20 17:02:21 -0700192 Alignment ComputeAlignment(HInstruction* offset,
193 DataType::Type type,
194 bool is_string_char_at,
195 uint32_t peeling = 0);
196 void SetAlignmentStrategy(uint32_t peeling_votes[],
197 const ArrayReference* peeling_candidate);
198 uint32_t MaxNumberPeeled();
Aart Bik14a68b42017-06-08 14:06:58 -0700199 bool IsVectorizationProfitable(int64_t trip_count);
Aart Bik14a68b42017-06-08 14:06:58 -0700200 uint32_t GetUnrollingFactor(HBasicBlock* block, int64_t trip_count);
201
Aart Bikb29f6842017-07-28 15:58:41 -0700202 //
Aart Bik6b69e0a2017-01-11 10:20:43 -0800203 // Helpers.
Aart Bikb29f6842017-07-28 15:58:41 -0700204 //
205
Aart Bikf8f5a162017-02-06 15:35:29 -0800206 bool TrySetPhiInduction(HPhi* phi, bool restrict_uses);
Aart Bikb29f6842017-07-28 15:58:41 -0700207 bool TrySetPhiReduction(HPhi* phi);
208
209 // Detects loop header with a single induction (returned in main_phi), possibly
210 // other phis for reductions, but no other side effects. Returns true on success.
211 bool TrySetSimpleLoopHeader(HBasicBlock* block, /*out*/ HPhi** main_phi);
212
Aart Bikcc42be02016-10-20 16:14:16 -0700213 bool IsEmptyBody(HBasicBlock* block);
Aart Bik482095d2016-10-10 15:39:10 -0700214 bool IsOnlyUsedAfterLoop(HLoopInformation* loop_info,
Aart Bik8c4a8542016-10-06 11:36:57 -0700215 HInstruction* instruction,
Aart Bik6b69e0a2017-01-11 10:20:43 -0800216 bool collect_loop_uses,
Aart Bik38a3f212017-10-20 17:02:21 -0700217 /*out*/ uint32_t* use_count);
Aart Bikf8f5a162017-02-06 15:35:29 -0800218 bool IsUsedOutsideLoop(HLoopInformation* loop_info,
219 HInstruction* instruction);
Nicolas Geoffray1a0a5192017-06-22 11:56:01 +0100220 bool TryReplaceWithLastValue(HLoopInformation* loop_info,
221 HInstruction* instruction,
222 HBasicBlock* block);
Aart Bikf8f5a162017-02-06 15:35:29 -0800223 bool TryAssignLastValue(HLoopInformation* loop_info,
224 HInstruction* instruction,
225 HBasicBlock* block,
226 bool collect_loop_uses);
Aart Bik6b69e0a2017-01-11 10:20:43 -0800227 void RemoveDeadInstructions(const HInstructionList& list);
Nicolas Geoffray1a0a5192017-06-22 11:56:01 +0100228 bool CanRemoveCycle(); // Whether the current 'iset_' is removable.
Aart Bik281c6812016-08-26 11:31:48 -0700229
Aart Bik92685a82017-03-06 11:13:43 -0800230 // Compiler driver (to query ISA features).
231 const CompilerDriver* compiler_driver_;
232
Aart Bik96202302016-10-04 17:33:56 -0700233 // Range information based on prior induction variable analysis.
Aart Bik281c6812016-08-26 11:31:48 -0700234 InductionVarRange induction_range_;
235
236 // Phase-local heap memory allocator for the loop optimizer. Storage obtained
Aart Bik96202302016-10-04 17:33:56 -0700237 // through this allocator is immediately released when the loop optimizer is done.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100238 ScopedArenaAllocator* loop_allocator_;
Aart Bik281c6812016-08-26 11:31:48 -0700239
Aart Bikf8f5a162017-02-06 15:35:29 -0800240 // Global heap memory allocator. Used to build HIR.
241 ArenaAllocator* global_allocator_;
242
Aart Bik96202302016-10-04 17:33:56 -0700243 // Entries into the loop hierarchy representation. The hierarchy resides
244 // in phase-local heap memory.
Aart Bik281c6812016-08-26 11:31:48 -0700245 LoopNode* top_loop_;
246 LoopNode* last_loop_;
247
Aart Bik8c4a8542016-10-06 11:36:57 -0700248 // Temporary bookkeeping of a set of instructions.
249 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100250 ScopedArenaSet<HInstruction*>* iset_;
Aart Bik8c4a8542016-10-06 11:36:57 -0700251
Aart Bikb29f6842017-07-28 15:58:41 -0700252 // Temporary bookkeeping of reduction instructions. Mapping is two-fold:
253 // (1) reductions in the loop-body are mapped back to their phi definition,
254 // (2) phi definitions are mapped to their initial value (updated during
255 // code generation to feed the proper values into the new chain).
256 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100257 ScopedArenaSafeMap<HInstruction*, HInstruction*>* reductions_;
Aart Bik482095d2016-10-10 15:39:10 -0700258
Aart Bikdf7822e2016-12-06 10:05:30 -0800259 // Flag that tracks if any simplifications have occurred.
260 bool simplified_;
261
Aart Bikf8f5a162017-02-06 15:35:29 -0800262 // Number of "lanes" for selected packed type.
263 uint32_t vector_length_;
264
265 // Set of array references in the vector loop.
266 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100267 ScopedArenaSet<ArrayReference>* vector_refs_;
Aart Bikf8f5a162017-02-06 15:35:29 -0800268
Aart Bik38a3f212017-10-20 17:02:21 -0700269 // Static or dynamic loop peeling for alignment.
270 uint32_t vector_static_peeling_factor_;
271 const ArrayReference* vector_dynamic_peeling_candidate_;
Aart Bik14a68b42017-06-08 14:06:58 -0700272
273 // Dynamic data dependence test of the form a != b.
274 HInstruction* vector_runtime_test_a_;
275 HInstruction* vector_runtime_test_b_;
276
Aart Bikf8f5a162017-02-06 15:35:29 -0800277 // Mapping used during vectorization synthesis for both the scalar peeling/cleanup
Aart Bik14a68b42017-06-08 14:06:58 -0700278 // loop (mode is kSequential) and the actual vector loop (mode is kVector). The data
Aart Bikf8f5a162017-02-06 15:35:29 -0800279 // structure maps original instructions into the new instructions.
280 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100281 ScopedArenaSafeMap<HInstruction*, HInstruction*>* vector_map_;
Aart Bikf8f5a162017-02-06 15:35:29 -0800282
Aart Bik0148de42017-09-05 09:25:01 -0700283 // Permanent mapping used during vectorization synthesis.
284 // Contents reside in phase-local heap memory.
Vladimir Markoca6fff82017-10-03 14:49:14 +0100285 ScopedArenaSafeMap<HInstruction*, HInstruction*>* vector_permanent_map_;
Aart Bik0148de42017-09-05 09:25:01 -0700286
Aart Bikf8f5a162017-02-06 15:35:29 -0800287 // Temporary vectorization bookkeeping.
Aart Bik14a68b42017-06-08 14:06:58 -0700288 VectorMode vector_mode_; // synthesis mode
Aart Bikf8f5a162017-02-06 15:35:29 -0800289 HBasicBlock* vector_preheader_; // preheader of the new loop
290 HBasicBlock* vector_header_; // header of the new loop
291 HBasicBlock* vector_body_; // body of the new loop
Aart Bik14a68b42017-06-08 14:06:58 -0700292 HInstruction* vector_index_; // normalized index of the new loop
Aart Bikf8f5a162017-02-06 15:35:29 -0800293
Aart Bik281c6812016-08-26 11:31:48 -0700294 friend class LoopOptimizationTest;
295
296 DISALLOW_COPY_AND_ASSIGN(HLoopOptimization);
297};
298
299} // namespace art
300
301#endif // ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_