OpenASIP  2.0
OffsetAliasAnalyzer.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2009 Tampere University.
3 
4  This file is part of TTA-Based Codesign Environment (TCE).
5 
6  Permission is hereby granted, free of charge, to any person obtaining a
7  copy of this software and associated documentation files (the "Software"),
8  to deal in the Software without restriction, including without limitation
9  the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  and/or sell copies of the Software, and to permit persons to whom the
11  Software is furnished to do so, subject to the following conditions:
12 
13  The above copyright notice and this permission notice shall be included in
14  all copies or substantial portions of the Software.
15 
16  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  DEALINGS IN THE SOFTWARE.
23  */
24 /**
25  * @file OffsetAliasAnalyzer.cc
26  *
27  * Implementation of OffsetAliasAnalyzer class.
28  *
29  * This class does simple alias analysis between memory addresses
30  * which are offsets of same register (register + index)
31  * Usually this are fields of same struct.
32  *
33  * @author Heikki Kultala 2009 (heikki.kultala-no.spam-tut.fi)
34  * @note rating: red
35  */
36 
37 #include "OffsetAliasAnalyzer.hh"
38 
39 #include "MoveNode.hh"
40 #include "Move.hh"
41 #include "ProgramOperation.hh"
42 #include "DataDependenceGraph.hh"
43 #include "RegisterFile.hh"
44 #include "Terminal.hh"
45 #include "MoveNodeSet.hh"
46 #include "Operation.hh"
47 
48 using namespace TTAProgram;
49 using namespace TTAMachine;
50 
51 /**
52  * Checks if the node contains an adress that is an offset.
53  *
54  * @param ddg DDG where to analyze from
55  * @param mn the node being checked
56  * @return true if is a traceable stack offset, false if not.
57  */
58 bool
59 OffsetAliasAnalyzer::isAddressTraceable(
60  DataDependenceGraph& ddg, const ProgramOperation& pop) {
61 
62  std::map<int,OffsetData>::iterator i = offsetData_.find(pop.poId());
63  if (i != offsetData_.end()) {
64  if (i->second.baseNode == NULL) {
65  return false;
66  } else {
67  return true;
68  }
69  }
70 
71  const MoveNode* addrMove = addressOperandMove(pop);
72  if (addrMove == NULL) {
73 
74  TwoPartAddressOperandDetection addressParts =
75  findTwoPartAddressOperands(pop);
76  if (addressParts.offsetOperation ==
77  TwoPartAddressOperandDetection::NOT_FOUND) {
78  return false;
79  }
80 
81  MoveNodeSet& addr1Set = pop.inputNode(addressParts.operand1);
82  MoveNodeSet& addr2Set = pop.inputNode(addressParts.operand2);
83  if (addr1Set.count() != 1) {
84  return false;
85  }
86  if (addr2Set.count() != 1) {
87  return false;
88  }
89  MoveNode& addr1 = addr1Set.at(0);
90  MoveNode& addr2 = addr2Set.at(0);
91 
92  if ((addr1.move().source().isImmediate() &&
93  addr2.move().source().isGPR()) ||
94  (addr2.move().source().isImmediate() &&
95  addr1.move().source().isGPR())) {
96  return true;
97  } else {
98  return false;
99  }
100  }
101 
102  // first find base and index of the first node.
103  const MoveNode* rawSrc = ddg.onlyRegisterRawAncestor(*addrMove, sp_);
104 
105  if (!rawSrc->isSourceOperation()) {
106  offsetData_.insert(
107  std::pair<int,OffsetData>(
108  pop.poId(),OffsetData(rawSrc, 0)));
109  return true;
110  }
111 
112  ProgramOperation& po = rawSrc->sourceOperation();
113 
114  if (po.operation().name() != "ADD" &&
115  po.operation().name() != "SUB") {
116  if (ddg.regRawSuccessorCount(*rawSrc, false) > 1) {
117  offsetData_.insert(
118  std::pair<int,OffsetData>(
119  pop.poId(),OffsetData(rawSrc, 0)));
120  return true;
121  } else {
122  offsetData_.insert(
123  std::pair<int,OffsetData>(
124  pop.poId(),OffsetData(NULL, INT_MAX)));
125  return false;
126  }
127  }
128 
129  // offset calc, add or sub. check for node2
130  MoveNodeSet& baseSet = po.inputNode(1);
131  MoveNodeSet& offsetSet = po.inputNode(2);
132 
133  if (baseSet.count() != 1 || offsetSet.count() != 1) {
134  offsetData_.insert(
135  std::pair<int,OffsetData>(
136  pop.poId(),OffsetData(NULL, INT_MAX)));
137  return false;
138  }
139 
140  MoveNode& offsetNode = offsetSet.at(0);
141  MoveNode& base = baseSet.at(0);
142 
143  if (!base.move().source().isGPR() ||
144  !offsetNode.move().source().isImmediate()) {
145  offsetData_.insert(
146  std::pair<int,OffsetData>(
147  pop.poId(), OffsetData(NULL, INT_MAX)));
148  return false;
149  }
150 
151  return true;
152 }
153 
154 /**
155  * Analyzes aliasing of two memory adderesses.
156  *
157  * Checks if they are stack offsets and compares the offsets.
158  *
159  * @param ddg ddg where they belong.
160  * @param node1 first node to compare
161  * @param another anpther node to compare
162  * @return ALIAS_TRUE if they alias, ALIAS_FALSE if they don't or
163  * ALIAS_UNKNOWN if cannot analyze.
164  */
165 MemoryAliasAnalyzer::AliasingResult
166 OffsetAliasAnalyzer::analyze(
167  DataDependenceGraph& ddg, const ProgramOperation& pop1,
168  const ProgramOperation& pop2, MoveNodeUse::BBRelation bbRel) {
169  const MoveNode* anc1 = NULL;
170  const MoveNode* anc2 = NULL;
171  long offsetVal1 = 0;
172  long offsetVal2 = 0;
173 
174  std::map<int,OffsetData>::const_iterator i =
175  offsetData_.find(pop1.poId());
176  if (i != offsetData_.end()) {
177  if (i->second.baseNode == NULL) {
178  return ALIAS_UNKNOWN;
179  } else {
180  anc1 = i->second.baseNode;
181  offsetVal1 = i->second.offset;
182  }
183  } else {
184 
185  const MoveNode* addrMove1 = addressOperandMove(pop1);
186  if (addrMove1 == NULL) {
187 
188  int offsetMul = 0;
189  TwoPartAddressOperandDetection addressParts =
190  findTwoPartAddressOperands(pop1);
191  switch(addressParts.offsetOperation) {
192  case TwoPartAddressOperandDetection::ADD:
193  offsetMul = 1;
194  break;
195  case TwoPartAddressOperandDetection::SUB:
196  offsetMul = -1;
197  break;
198  case TwoPartAddressOperandDetection::NOT_FOUND:
199  offsetData_.insert(
200  std::pair<int,OffsetData>(
201  pop1.poId(),OffsetData(NULL, INT_MAX)));
202  return ALIAS_UNKNOWN;
203  }
204 
205  MoveNodeSet& addr1Set = pop1.inputNode(addressParts.operand1);
206  MoveNodeSet& addr2Set = pop1.inputNode(addressParts.operand2);
207  if (addr1Set.count() != 1) {
208  offsetData_.insert(
209  std::pair<int,OffsetData>(
210  pop1.poId(),OffsetData(NULL, INT_MAX)));
211  return ALIAS_UNKNOWN;
212  }
213  if (addr2Set.count() != 1) {
214  offsetData_.insert(
215  std::pair<int,OffsetData>(
216  pop1.poId(),OffsetData(NULL, INT_MAX)));
217  return ALIAS_UNKNOWN;
218  }
219  MoveNode& addr1 = addr1Set.at(0);
220  MoveNode& addr2 = addr2Set.at(0);
221 
222  if (addr1.isSourceConstant() &&
223  addr2.move().source().isGPR()) {
224  anc1 = ddg.onlyRegisterRawAncestor(addr2, sp_);
225  offsetVal1 = addr1.move().source().value().intValue() *
226  offsetMul;
227  } else {
228  if (addr2.isSourceConstant() &&
229  addr1.move().source().isGPR()) {
230  anc1 = ddg.onlyRegisterRawAncestor(addr1, sp_);
231  offsetVal1 = addr2.move().source().value().intValue() *
232  offsetMul;
233  } else {
234  offsetData_.insert(
235  std::pair<int,OffsetData>(
236  pop1.poId(),OffsetData(NULL, INT_MAX)));
237  return ALIAS_UNKNOWN;
238  }
239  }
240 
241  offsetData_.insert(
242  std::pair<int,OffsetData>(
243  pop1.poId(),OffsetData(anc1, offsetVal1)));
244 
245  } else {
246  // direct memory op. have to search for the add.
247 
248  // first find base and index of the first node.
249  const MoveNode* rawSrc1 =
250  ddg.onlyRegisterRawAncestor(*addrMove1, sp_);
251 
252  if (!rawSrc1->isSourceOperation()) {
253  offsetData_.insert(
254  std::pair<int,OffsetData>(
255  pop1.poId(),OffsetData(rawSrc1, 0)));
256  } else {
257 
258  ProgramOperation& po1 = rawSrc1->sourceOperation();
259 
260  if (po1.operation().name() == "ADD" ||
261  po1.operation().name() == "SUB") {
262 
263 
264  // offset calc, add or sub. check for node2
265  MoveNodeSet& baseSet1 = po1.inputNode(1);
266  MoveNodeSet& offsetSet1 = po1.inputNode(2);
267 
268  if (baseSet1.count() != 1 || offsetSet1.count() != 1) {
269  offsetData_.insert(
270  std::pair<int,OffsetData>(
271  pop1.poId(),OffsetData(NULL, INT_MAX)));
272  return ALIAS_UNKNOWN;
273  }
274 
275  MoveNode& offsetNode1 = offsetSet1.at(0);
276  MoveNode& base1 = baseSet1.at(0);
277 
278  if (!base1.move().source().isGPR() ||
279  !offsetNode1.move().source().isImmediate()) {
280  offsetData_.insert(
281  std::pair<int,OffsetData>(
282  pop1.poId(),OffsetData(NULL, INT_MAX)));
283  return ALIAS_UNKNOWN;
284  }
285 
286  offsetVal1 = offsetNode1.move().source().value().intValue();
287  if (po1.operation().name() == "SUB") {
288  offsetVal1 = -offsetVal1;
289  }
290 
291  anc1 = ddg.onlyRegisterRawAncestor(base1, sp_);
292  // update cache.
293  offsetData_.insert(
294  std::pair<int,OffsetData>(
295  pop1.poId(),OffsetData(anc1, offsetVal1)));
296  } else {
297  // comes directly from some untraceable op.
298  if (ddg.regRawSuccessorCount(*rawSrc1, false) > 1) {
299  offsetData_.insert(
300  std::pair<int,OffsetData>(
301  pop1.poId(),OffsetData(rawSrc1, 0)));
302  anc1 = rawSrc1;
303  offsetVal1 = 0;
304  } else {
305  offsetData_.insert(
306  std::pair<int,OffsetData>(
307  pop1.poId(),OffsetData(NULL, INT_MAX)));
308  return ALIAS_UNKNOWN;
309  }
310  }
311  }
312  }
313  }
314  // then find base and index for second node.
315 
316  //first search cache.
317  i = offsetData_.find(pop2.poId());
318  if (i != offsetData_.end()) {
319  if (i->second.baseNode == NULL) {
320  return ALIAS_UNKNOWN;
321  } else {
322  anc2 = i->second.baseNode;
323  offsetVal2 = i->second.offset;
324  }
325  } else {
326  const MoveNode* addrMove2 = addressOperandMove(pop2);
327  if (addrMove2 == NULL) {
328 
329  int offsetMul = 0;
330  TwoPartAddressOperandDetection addressParts =
331  findTwoPartAddressOperands(pop2);
332  switch(addressParts.offsetOperation) {
333  case TwoPartAddressOperandDetection::ADD:
334  offsetMul = 1;
335  break;
336  case TwoPartAddressOperandDetection::SUB:
337  offsetMul = -1;
338  break;
339  case TwoPartAddressOperandDetection::NOT_FOUND:
340  offsetData_.insert(
341  std::pair<int,OffsetData>(
342  pop2.poId(),OffsetData(NULL, INT_MAX)));
343  return ALIAS_UNKNOWN;
344  }
345 
346  MoveNodeSet& addr1Set = pop2.inputNode(addressParts.operand1);
347  MoveNodeSet& addr2Set = pop2.inputNode(addressParts.operand2);
348  if (addr1Set.count() != 1) {
349  offsetData_.insert(
350  std::pair<int,OffsetData>(
351  pop2.poId(),OffsetData(NULL, INT_MAX)));
352  return ALIAS_UNKNOWN;
353  }
354  if (addr2Set.count() != 1) {
355  offsetData_.insert(
356  std::pair<int,OffsetData>(
357  pop2.poId(),OffsetData(NULL, INT_MAX)));
358  return ALIAS_UNKNOWN;
359  }
360  MoveNode& addr1 = addr1Set.at(0);
361  MoveNode& addr2 = addr2Set.at(0);
362 
363  if (addr1.isSourceConstant() &&
364  addr2.move().source().isGPR()) {
365  anc2 = ddg.onlyRegisterRawAncestor(addr2, sp_);
366  offsetVal2 = addr1.move().source().value().intValue() *
367  offsetMul;
368  } else {
369  if (addr2.isSourceConstant() &&
370  addr1.move().source().isGPR()) {
371  anc2 = ddg.onlyRegisterRawAncestor(addr1, sp_);
372  offsetVal2 = addr2.move().source().value().intValue() *
373  offsetMul;
374  } else {
375  offsetData_.insert(
376  std::pair<int,OffsetData>(
377  pop2.poId(),OffsetData(NULL, INT_MAX)));
378  return ALIAS_UNKNOWN;
379  }
380  }
381 
382  offsetData_.insert(
383  std::pair<int,OffsetData>(
384  pop2.poId(),OffsetData(anc2, offsetVal2)));
385  } else {
386  // direct memory op. have to search for the add.
387 
388  // first find base and index of the first node.
389  const MoveNode* rawSrc2 =
390  ddg.onlyRegisterRawAncestor(*addrMove2, sp_);
391 
392  if (!rawSrc2->isSourceOperation()) {
393  offsetData_.insert(
394  std::pair<int,OffsetData>(
395  pop2.poId(),OffsetData(rawSrc2, 0)));
396 
397  } else {
398 
399  ProgramOperation& po2 = rawSrc2->sourceOperation();
400 
401  if (po2.operation().name() == "ADD" ||
402  po2.operation().name() == "SUB") {
403 
404  // offset calc, add or sub. check for node2
405  MoveNodeSet& baseSet2 = po2.inputNode(1);
406  MoveNodeSet& offsetSet2 = po2.inputNode(2);
407 
408  if (baseSet2.count() != 1 || offsetSet2.count() != 1) {
409  offsetData_.insert(
410  std::pair<int,OffsetData>(
411  pop2.poId(),OffsetData(NULL, INT_MAX)));
412  return ALIAS_UNKNOWN;
413  }
414 
415  MoveNode& offsetNode2 = offsetSet2.at(0);
416  MoveNode& base2 = baseSet2.at(0);
417 
418  // check that base is register coming from same place.
419 
420  if (!base2.move().source().isGPR() ||
421  !offsetNode2.move().source().isImmediate()) {
422  offsetData_.insert(
423  std::pair<int,OffsetData>(
424  pop2.poId(),OffsetData(NULL, INT_MAX)));
425  return ALIAS_UNKNOWN;
426  }
427 
428  offsetVal2 = offsetNode2.move().source().value().intValue();
429  if (po2.operation().name() == "SUB") {
430  offsetVal2 = -offsetVal2;
431  }
432 
433  anc2 = ddg.onlyRegisterRawAncestor(base2, sp_);
434  // update cache.
435  offsetData_.insert(
436  std::pair<int,OffsetData>(
437  pop2.poId(),OffsetData(anc2, offsetVal2)));
438  } else {
439  // comes directly from some untraceable op.
440  if (ddg.regRawSuccessorCount(*rawSrc2, false) > 1) {
441  offsetData_.insert(
442  std::pair<int,OffsetData>(
443  pop2.poId(),OffsetData(rawSrc2, 0)));
444  anc2 = rawSrc2;
445  offsetVal2 = 0;
446  } else {
447  offsetData_.insert(
448  std::pair<int,OffsetData>(
449  pop2.poId(),OffsetData(NULL, INT_MAX)));
450  return ALIAS_UNKNOWN;
451  }
452  }
453  }
454  }
455  }
456  // now we have the defining move for base and offset. compare them
457 
458  if (anc1 == NULL || anc2 == NULL) {
459  return ALIAS_UNKNOWN;
460  }
461 
462  if (anc1 == anc2 || sameLoopAndPrevSources(ddg, *anc1, *anc2)) {
463 
464  if (bbRel == MoveNodeUse::LOOP) {
465  if (!analyzeLoopPtrIncrease(ddg, *anc2, offsetVal2)) {
466  return ALIAS_UNKNOWN;
467  }
468  }
469 
470  AliasingResult res = compareIndeces(
471  offsetVal1, offsetVal2, pop1, pop2);
472 
473  return res;
474  }
475  return ALIAS_UNKNOWN;
476 }
477 
478 bool OffsetAliasAnalyzer::sameLoopAndPrevSources(
479  const DataDependenceGraph& ddg, const MoveNode& anc1, const MoveNode& anc2) {
480 
481  MoveNode* prevSrc1 = ddg.onlyRegisterRawSource(anc1,2,2);
482  MoveNode* loopSrc1 = ddg.onlyRegisterRawSource(anc1,2,1);
483  MoveNode* prevSrc2 = ddg.onlyRegisterRawSource(anc2,2,2);
484  MoveNode* loopSrc2 = ddg.onlyRegisterRawSource(anc2,2,1);
485 
486  return (prevSrc1 == prevSrc2 && loopSrc1 == loopSrc2 &&
487  prevSrc1 != NULL);
488 }
489 
490 OffsetAliasAnalyzer::~OffsetAliasAnalyzer() {}
491 
492 OffsetAliasAnalyzer::OffsetAliasAnalyzer(const TCEString& sp) : sp_(sp) {
493 }
494 
495 bool OffsetAliasAnalyzer::analyzeLoopPtrIncrease(
496  const DataDependenceGraph& ddg, const MoveNode& mn, long& offset) {
497 
498  MoveNode* prevSrc = ddg.onlyRegisterRawSource(mn,2,2);
499  MoveNode* loopSrc = ddg.onlyRegisterRawSource(mn,2,1);
500  // does not change in loop?
501  if (loopSrc == NULL) {
502  return true;
503  }
504 
505  if (prevSrc == NULL) {
506  return false;
507  }
508  return findIncrement(*loopSrc, offset);
509 }
ProgramOperation::operation
const Operation & operation() const
Definition: ProgramOperation.cc:590
SimValue::intValue
int intValue() const
Definition: SimValue.cc:895
TTAProgram
Definition: Estimator.hh:65
MoveNodeUse::BBRelation
BBRelation
Definition: MoveNodeUse.hh:23
OffsetAliasAnalyzer::OffsetData
Definition: OffsetAliasAnalyzer.hh:63
DataDependenceGraph::onlyRegisterRawAncestor
const MoveNode * onlyRegisterRawAncestor(const MoveNode &node, const std::string &sp) const
Definition: DataDependenceGraph.cc:4203
OffsetAliasAnalyzer::analyze
virtual AliasingResult analyze(DataDependenceGraph &ddg, const ProgramOperation &pop1, const ProgramOperation &pop2, MoveNodeUse::BBRelation bbRelation)
Definition: OffsetAliasAnalyzer.cc:166
OffsetAliasAnalyzer::analyzeLoopPtrIncrease
bool analyzeLoopPtrIncrease(const DataDependenceGraph &ddg, const MoveNode &mn, long &offset)
Definition: OffsetAliasAnalyzer.cc:495
DataDependenceGraph.hh
ProgramOperation
Definition: ProgramOperation.hh:70
MoveNode
Definition: MoveNode.hh:65
MoveNode::isSourceConstant
bool isSourceConstant() const
Definition: MoveNode.cc:238
Terminal.hh
Operation::name
virtual TCEString name() const
Definition: Operation.cc:93
DataDependenceGraph::onlyRegisterRawSource
MoveNode * onlyRegisterRawSource(const MoveNode &mn, int allowGuardEdges=2, int backEdges=0) const
Definition: DataDependenceGraph.cc:4083
MoveNode::sourceOperation
ProgramOperation & sourceOperation() const
Definition: MoveNode.cc:453
OffsetAliasAnalyzer::sameLoopAndPrevSources
bool sameLoopAndPrevSources(const DataDependenceGraph &ddg, const MoveNode &anc1, const MoveNode &anc2)
Definition: OffsetAliasAnalyzer.cc:478
MemoryAliasAnalyzer::TwoPartAddressOperandDetection::offsetOperation
OffsetOperation offsetOperation
Definition: MemoryAliasAnalyzer.hh:86
MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand2
int operand2
Definition: MemoryAliasAnalyzer.hh:88
OffsetAliasAnalyzer::~OffsetAliasAnalyzer
~OffsetAliasAnalyzer()
Definition: OffsetAliasAnalyzer.cc:490
MemoryAliasAnalyzer::AliasingResult
AliasingResult
Definition: MemoryAliasAnalyzer.hh:50
MoveNodeSet::at
MoveNode & at(int index)
OffsetAliasAnalyzer::isAddressTraceable
virtual bool isAddressTraceable(DataDependenceGraph &ddg, const ProgramOperation &pop)
Definition: OffsetAliasAnalyzer.cc:59
TTAProgram::Terminal::isGPR
virtual bool isGPR() const
Definition: Terminal.cc:107
Operation.hh
MoveNode::isSourceOperation
bool isSourceOperation() const
Definition: MoveNode.cc:168
TTAProgram::Terminal::value
virtual SimValue value() const
Definition: Terminal.cc:178
MoveNodeSet
Definition: MoveNodeSet.hh:41
MoveNodeUse::LOOP
@ LOOP
Definition: MoveNodeUse.hh:26
ProgramOperation.hh
MoveNodeSet::count
int count() const
MoveNode::move
TTAProgram::Move & move()
MemoryAliasAnalyzer::findIncrement
static const MoveNode * findIncrement(const MoveNode &mn, long &increment)
Definition: MemoryAliasAnalyzer.cc:273
RegisterFile.hh
MoveNodeSet.hh
TCEString
Definition: TCEString.hh:53
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
ProgramOperation::inputNode
MoveNodeSet & inputNode(int in) const
Definition: ProgramOperation.cc:513
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
ProgramOperation::poId
unsigned int poId() const
Definition: ProgramOperation.cc:765
OffsetAliasAnalyzer.hh
MemoryAliasAnalyzer::TwoPartAddressOperandDetection
Definition: MemoryAliasAnalyzer.hh:84
Move.hh
TTAMachine
Definition: Assembler.hh:48
TTAProgram::Terminal::isImmediate
virtual bool isImmediate() const
Definition: Terminal.cc:63
MoveNode.hh
DataDependenceGraph::regRawSuccessorCount
int regRawSuccessorCount(const MoveNode &mn, bool onlyScheduled)
Definition: DataDependenceGraph.cc:3952
OffsetAliasAnalyzer::OffsetAliasAnalyzer
OffsetAliasAnalyzer(const TCEString &sp)
Definition: OffsetAliasAnalyzer.cc:492
MemoryAliasAnalyzer::TwoPartAddressOperandDetection::operand1
int operand1
Definition: MemoryAliasAnalyzer.hh:87
Generated by   doxygen 1.8.17