OpenASIP  2.0
PreOptimizer.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2020 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 PreOptimizer.cc
26  *
27  * Implementation of GuardInverver class.
28  *
29  * This optimizer does some peephole optimizations before actual scheduling:
30  *
31  * Removes unneeded predicate arithmetic by using
32  * opposite guard instead where the guard is used.
33  *
34  * Changes registers of address calculations to eliminate entideps
35  *
36  * Removes adds of compile-time ocnstants
37  *
38  * @author Heikki Kultala 2009 (hkultala-no.spam-cs.tut.fi)
39  * @note rating: red
40  */
41 
42 #include "PreOptimizer.hh"
43 #include "Procedure.hh"
44 #include "Instruction.hh"
45 #include "Move.hh"
46 #include "ControlFlowGraph.hh"
48 #include "ProgramOperation.hh"
49 #include "Terminal.hh"
50 #include "CodeGenerator.hh"
52 #include "RegisterFile.hh"
53 #include "DisassemblyRegister.hh"
54 #include "Program.hh"
55 #include "Operation.hh"
56 #include "BasicBlock.hh"
58 #include "Operand.hh"
59 #include "TerminalImmediate.hh"
60 #include "Bus.hh"
61 
62 static const int DEFAULT_LOWMEM_MODE_THRESHOLD = 200000;
63 
64 /**
65  * Constructor. Initializes interpassData.
66  *
67  * @param data InterPassData to store.
68  */
70  ProgramPass(data),
71  ControlFlowGraphPass(data) {
72 }
73 
74 /**
75  * Handles a program.
76  *
77  * @param program the program.
78  * @param targetMachine targetmachine. Not used at all.
79  */
80 void
82  TTAProgram::Program& program, const TTAMachine::Machine& targetMachine) {
83  ProgramPass::executeProcedurePass(program, targetMachine, *this);
84 }
85 
86 bool
89 
90  DataDependenceEdge* connectingEdge = NULL;
91 
92  if (po.outputMoveCount() != 1 || po.inputMoveCount() != 1) {
93  return false;
94  }
95  MoveNode& address = po.inputMove(0);
96  MoveNode& result = po.outputMove(0);
97 
98  DataDependenceGraph::EdgeSet iEdges = ddg.inEdges(address);
99 
100  if (!result.move().destination().isGPR()) {
101  return false;
102  }
103 
104  // do not put addresses to lane RF's
105  const TTAMachine::RegisterFile& rf =
106  result.move().destination().registerFile();
107  if (rf.name().find("L_") == 0) {
108  return false;
109  }
110 
111  MoveNode* src = NULL;
112  // loop thru all inedges find who writes the address.
113  for (DataDependenceGraph::EdgeSet::iterator i = iEdges.begin();
114  i != iEdges.end(); i++) {
115  DataDependenceEdge& edge = **i;
117  !edge.guardUse()) {
119  return false;
120  }
121  if (edge.isBackEdge()) {
122  return false;
123  }
124  if (src == NULL) {
125  src = &ddg.tailNode(edge);
126  connectingEdge = &edge;
127  } else {
128  return false;
129  }
130  }
131  }
132  if (src == NULL) {
133  // load address missing
134  return false;
135  }
136 
137  if (&ddg.getBasicBlockNode(address) != &ddg.getBasicBlockNode(*src)) {
138  return false;
139  }
140 
141  // TODO: multi-threading might make this fail too often!
142  if (src->nodeID() != address.nodeID() - 1) {
143  // some other moves between these moves.
144  return false;
145  }
146 
147  DataDependenceGraph::EdgeSet oEdges = ddg.outEdges(*src);
148  // loop thru all outedges.
149  for (DataDependenceGraph::EdgeSet::iterator i = oEdges.begin();
150  i != oEdges.end(); i++) {
151  DataDependenceEdge& edge = **i;
153  if (&ddg.headNode(edge) != &address) {
154  // same address used for some other operation.
155  return false;
156  }
157  }
158  }
159 
160  // cannot use narrower reg for address.
161  if (address.move().source().registerFile().width() !=
162  result.move().destination().registerFile().width()) {
163  return false;
164  }
165 
166  TCEString oldReg =
168  TCEString newReg =
170 
171  address.move().setSource(result.move().destination().copy());
172  src->move().setDestination(result.move().destination().copy());
173 
175  *src, address, result, *connectingEdge, oldReg, newReg);
176  return true;
177 }
178 
179 /**
180  * Tries to remove an unnecessary guard value xor before a conditional jump.
181  *
182  * Tries to remove xor operation which is used for converting false boolean
183  * value into true boolean value which is then used for jump. The xor
184  * operation is removed and the jump predicate reversed.
185  *
186  * @param ddg The datadependence graph of the whole function
187  * @param po ProgramOperation which is a xor operation
188  * @param irm instructionreferencemanager of the program.
189  *
190  * @return Basic block whose output edge predicates need to be
191  * reversed of cfg or NULL if no need to change cfg.
192  */
193 
198  if (po.outputMoveCount() != 1 || po.inputMoveCount() != 2) {
199  return ControlFlowGraph::NodeSet();
200  }
201  // check that it's or by 1.
202  MoveNode& operand2 = po.inputMove(1);
203  TTAProgram::Terminal& src2 = operand2.move().source();
204  if (!src2.isImmediate() || src2.value().intValue() != 1) {
205  return ControlFlowGraph::NodeSet();
206  }
207  // now we have a xor op which is a truth value reversal.
208  // find where the result is used.
209 
210  return tryToRemoveGuardInversingOp(ddg, po, irm, cfg);
211 }
212 
213 
218  if (po.outputMoveCount() != 1 || po.inputMoveCount() != 2) {
219  return ControlFlowGraph::NodeSet();
220  }
221  // check that it's or by 0.
222  MoveNode& operand1 = po.inputMove(0);
223  MoveNode& operand2 = po.inputMove(1);
224  TTAProgram::Terminal& src2 = operand2.move().source();
225  if (!src2.isImmediate() || src2.value().intValue() != 0) {
226  return ControlFlowGraph::NodeSet();
227  }
228  MoveNode* src = ddg.onlyRegisterRawSource(operand1);
229  if (src == NULL || !src->isSourceOperation()) {
230  return ControlFlowGraph::NodeSet();
231  }
232  ProgramOperation& srcOp = src->sourceOperation();
233  if (srcOp.operation().operand(
234  src->move().source().operationIndex()).type() == Operand::BOOL) {
235  // now we have a xor op which is a truth value reversal.
236  // find where the result is used.
237  return tryToRemoveGuardInversingOp(ddg, po, irm, cfg);
238  }
239  return ControlFlowGraph::NodeSet();
240 }
241 
242 
247  ControlFlowGraph& cfg) {
248 
249  MoveNode& operand1 = po.inputMove(0);
250  MoveNode& operand2 = po.inputMove(1);
251  MoveNode& result = po.outputMove(0);
252  TTAProgram::Move& resultMove = result.move();
253  DataDependenceGraph::EdgeSet oEdges = ddg.outEdges(result);
254 
255  // some more complex things done with the guard.
256  // converting those not yet supported.
257  if (!checkGuardReversalAllowed(ddg, oEdges)) {
258  return ControlFlowGraph::NodeSet();
259  }
260 
261  TTAProgram::Instruction& operand1Ins = operand1.move().parent();
262  TTAProgram::Instruction& operand2Ins = operand2.move().parent();
263  TTAProgram::Instruction& resultIns = resultMove.parent();
264 
265  // cannot remove if has refs. TODO: move refs to next ins.
266  // if we don't have irm, assume we don't have irefs.
267  if (irm != NULL &&
268  (irm->hasReference(operand1Ins) || irm->hasReference(operand2Ins) ||
269  irm->hasReference(resultIns))) {
270  return ControlFlowGraph::NodeSet();
271  }
272 
273  auto reverseJumpBBs = inverseGuardsOfHeads(ddg, oEdges);
274 
275  // If cannot reverse jumps, have to undo and abort.
276  for ([[maybe_unused]] auto n: reverseJumpBBs) {
277  if (!cfgAllowsJumpReversal(operand1Ins, cfg)) {
278  inverseGuardsOfHeads(ddg, oEdges);
279  return ControlFlowGraph::NodeSet();
280  }
281  }
282 
283  // need some copy from one predicate to another?
284  TTAProgram::Terminal& src1 = operand1.move().source();
285  TTAProgram::Terminal& dst = resultMove.destination();
286  if (!src1.equals(dst)) {
287  auto newMove = std::make_shared<TTAProgram::Move>(
288  src1.copy(), dst.copy(), operand1.move().bus());
289 
291  newIns->addMove(newMove);
292  resultMove.parent().parent().insertAfter(
293  resultMove.parent(), newIns);
294  MoveNode* newMN = new MoveNode(newMove);
295  ddg.addNode(*newMN, operand1);
296  ddg.combineNodes(operand1, result, *newMN);
297 
298  } else {
299  // the op just gets deleted.
300  ddg.copyDepsOver(operand1, result, true, true);
301  }
302 
303  // delete the xor operation. (the moves and instructions.)
304  TTAProgram::CodeSnippet& parent = operand1Ins.parent();
305 
306  assert(operand1Ins.moveCount() == 1);
307  ddg.deleteNode(operand1);
308  parent.remove(operand1Ins);
309  delete &operand1Ins;
310 
311  assert(operand2Ins.moveCount() == 1);
312  ddg.deleteNode(operand2);
313  parent.remove(operand2Ins);
314  delete &operand2Ins;
315 
316 
317  assert(resultIns.moveCount() == 1);
318  ddg.deleteNode(result);
319  parent.remove(resultIns);
320  delete &resultIns;
321 
322  return reverseJumpBBs;
323 }
324 
325 
327  DataDependenceGraph& ddg,
329 
330  // loop through all outedges.
331  for (DataDependenceGraph::EdgeSet::iterator i = oEdges.begin();
332  i != oEdges.end(); i++) {
333  DataDependenceEdge& edge = **i;
334  bool dstOpIsSelect = false;
336  !edge.guardUse()) {
337  MoveNode& dstMN = ddg.headNode(edge);
338  if (!dstMN.isDestinationOperation()) {
339  return false;
340  }
341  ProgramOperation &dstOp = dstMN.destinationOperation();
342  if (dstOp.operation().name() != "SELECT") {
343  return false;
344  }
345  dstOpIsSelect = true;
346  }
347 
348 
349  // them checks that those guard usages cannot have some other
350  // movenode writing the guard, if some complex guard
351  // calculation where guard write itself is conditional
352  // or multiple guard sources in different BBs.
353  int gRawCount = 0;
354  MoveNode& head = ddg.headNode(edge);
355  DataDependenceGraph::EdgeSet iEdges = ddg.inEdges(head);
356  for (DataDependenceGraph::EdgeSet::iterator j = iEdges.begin();
357  j != iEdges.end(); j++) {
358  if ((**j).guardUse() &&
359  (**j).dependenceType() == DataDependenceEdge::DEP_RAW) {
360  gRawCount++;
361  if (gRawCount > 1) {
362  return false;
363  }
364  }
365 
366  // Prevent select's condition to be reversed multiple times.
367  if ((**j).dependenceType() == DataDependenceEdge::DEP_RAW &&
368  dstOpIsSelect) {
369  gRawCount++;
370  if (gRawCount > 1) {
371  return false;
372  }
373  }
374  }
375  }
376  return true;
377 }
378 
381  DataDependenceGraph& ddg,
383  ControlFlowGraph::NodeSet guardReverseBBs;
384  for (DataDependenceGraph::EdgeSet::iterator i = oEdges.begin();
385  i != oEdges.end(); i++) {
386  DataDependenceEdge& edge = **i;
388  continue;
389  }
390  MoveNode& head = ddg.headNode(edge);
391  if (edge.guardUse()) {
392  TTAProgram::Move& guardUseMove = head.move();
393  assert(!guardUseMove.isUnconditional());
394  guardUseMove.setGuard(
396  guardUseMove.guard()));
397  if (guardUseMove.isJump()) {
398  BasicBlockNode& jumpBBN = ddg.getBasicBlockNode(head);
399  guardReverseBBs.insert(&jumpBBN);
400  }
401  } else {
403  }
404  }
405  return guardReverseBBs;
406 }
407 
408 /**
409  * Remove additions that can be removed staticly. LLVM leaves these when
410  * another ide of the addition is an address of a global variable.
411  */
414 
415  if (po.operation().name() != "ADD" ) return;
416 
417  MoveNode& result = po.outputMove(0);
418  if (po.inputMoveCount() != 2) {
419  return;
420  }
421  MoveNode& operand1 = po.inputMove(0);
422  MoveNode& operand2 = po.inputMove(1);
423  MoveNode* src1 = &operand1;
424  MoveNode* src2 = &operand2;
425 
426  // allow hopping over regs
427  while (src1->isSourceVariable()) {
428  src1 = ddg.onlyRegisterRawSource(*src1,2);
429  if (src1 == nullptr) {
430  return;
431  }
432  }
433 
434  // allow hopping over regs
435  while (src2->isSourceVariable()) {
436  src2 = ddg.onlyRegisterRawSource(*src2,2);
437  if (src2 == nullptr) {
438  return;
439  }
440  }
441  if (!src2->isSourceConstant() || !src1->isSourceConstant()) {
442  return;
443  }
444 
445  auto& s1 = src1->move().source();
446  auto& s2 = src2->move().source();
447 
448  if (s1.value().intValue() == 0 || s2.value().intValue() == 0) {
449  return;
450  }
451 
452  // all tests ok, proceed and remove the add.
453  TTAProgram::Instruction& operand1Ins = operand1.move().parent();
454  TTAProgram::Instruction& operand2Ins = operand2.move().parent();
455  TTAProgram::CodeSnippet& parent = operand1Ins.parent();
456 
457  int val = s1.value().intValue() + s2.value().intValue();
458  auto immTerm =
460 
461  result.unsetSourceOperation();
462  po.removeOutputNode(result);
463 
464  result.move().setSource(immTerm);
465 
466  assert(operand1Ins.moveCount() == 1);
467  ddg.deleteNode(operand1);
468  parent.remove(operand1Ins);
469  delete &operand1Ins;
470 
471  assert(operand2Ins.moveCount() == 1);
472  ddg.deleteNode(operand2);
473  parent.remove(operand2Ins);
474  delete &operand2Ins;
475 }
476 
477 /**
478  * Handles a procedure.
479  *
480  * @param procedure the procedure.
481  * @param targetMachine targetmachine. Not used at all.
482  */
483 void
485  TTAProgram::Procedure& procedure, const TTAMachine::Machine& mach) {
486  // If procedure has too many instructions, may run out of memory.
487  // so check the lowmem mode. in lowmem mode this optimiziation
488  // is disabled, so returns.
489  SchedulerCmdLineOptions* opts =
491  int lowMemThreshold = DEFAULT_LOWMEM_MODE_THRESHOLD;
492 
493  if (opts != NULL && opts->lowMemModeThreshold() > -1) {
494  lowMemThreshold = opts->lowMemModeThreshold();
495  }
496 
497  if (procedure.instructionCount() >=lowMemThreshold) {
498  return;
499  }
500 
501  ControlFlowGraph cfg(procedure /*, ProcedurePass::interPassData()*/);
503 
504  handleControlFlowGraph(cfg, mach);
505 
506  // copy back to the program.
507  cfg.copyToProcedure(procedure);
508 }
509 
510 void
512  ControlFlowGraph& cfg,
513  DataDependenceGraph& ddg) {
514 
517  program == NULL ? NULL :
518  &program->instructionReferenceManager();
519 
520  // Loop over all programoperations. find XOR's by 1.
521  for (int i = ddg.programOperationCount() - 1; i >= 0; i--) {
522  ProgramOperation& po = ddg.programOperation(i);
523  ControlFlowGraph::NodeSet jumpNodes;
524  if (po.operation().name() == "XOR" ||
525  po.operation().name() == "XOR64") {
526  jumpNodes = tryToRemoveXor(ddg, po, irm, cfg);
527  }
528  if (po.operation().name() == "EQ") {
529  jumpNodes = tryToRemoveEq(ddg, po, irm, cfg);
530  }
531  for (auto bbn : jumpNodes) {
532  cfg.reverseGuardOnOutEdges(*bbn);
533  }
534  if (po.operation().readsMemory()) {
535  tryToOptimizeAddressReg(ddg, po);
536  }
537 
538  if (po.operation().name() == "ADD") {
539  tryToPrecalcConstantAdd(ddg, po);
540  }
541  }
542  // todo: remove also programoprations.
543 }
544 
545 void
547  ControlFlowGraph& cfg, const TTAMachine::Machine& mach) {
549  // only RAW register edges and operation edges. no mem edges,
550  // no anti-edges.
551  DataDependenceGraph* ddg = ddgBuilder.build(
552  cfg, DataDependenceGraph::NO_ANTIDEPS, mach, NULL, false);
553 
554  handleCFGDDG(cfg, *ddg);
555 
556  delete ddg;
557 }
558 
559 /** Check that we can revert the out edges of the cfg when reverting
560  * a jump guard */
561 bool
564  TTAProgram::CodeSnippet* parent = &ins.parent();
565  for (int j = 0; j < cfg.nodeCount(); j++) {
566  BasicBlockNode& bbn = cfg.node(j);
567  if (&bbn.basicBlock() == parent) {
568  for (int i = 0; i < cfg.outDegree(bbn); i++) {
569  ControlFlowEdge& e = cfg.outEdge(bbn,i);
570  if (!e.isTrueEdge() && !e.isFalseEdge()) {
571  return false;
572  }
573  }
574  }
575  }
576  return true;
577 }
ProgramOperation::operation
const Operation & operation() const
Definition: ProgramOperation.cc:590
ControlFlowGraph::program
TTAProgram::Program * program() const
Definition: ControlFlowGraph.cc:1171
SimValue::intValue
int intValue() const
Definition: SimValue.cc:895
ProcedurePass
Definition: ProcedurePass.hh:53
ControlFlowGraph::reverseGuardOnOutEdges
void reverseGuardOnOutEdges(const BasicBlockNode &bbn)
Definition: ControlFlowGraph.cc:2486
BoostGraph::outEdge
virtual Edge & outEdge(const Node &node, const int index) const
TTAProgram::Program
Definition: Program.hh:63
TTAProgram::Instruction::addMove
void addMove(std::shared_ptr< Move > move)
Definition: Instruction.cc:147
PreOptimizer::inverseGuardsOfHeads
ControlFlowGraph::NodeSet inverseGuardsOfHeads(DataDependenceGraph &ddg, DataDependenceGraph::EdgeSet &oEdges)
Definition: PreOptimizer.cc:380
Operand::BOOL
@ BOOL
Definition: Operand.hh:64
BoostGraph::tailNode
virtual Node & tailNode(const Edge &edge) const
TTAMachine::Component::name
virtual TCEString name() const
Definition: MachinePart.cc:125
DataDependenceGraph::programOperation
ProgramOperation & programOperation(int index)
Definition: DataDependenceGraph.cc:227
DataDependenceGraph::renamedSimpleLiveRange
void renamedSimpleLiveRange(MoveNode &src, MoveNode &dest, MoveNode &antidepPoint, DataDependenceEdge &lrEdge, const TCEString &oldReg, const TCEString &newReg)
Definition: DataDependenceGraph.cc:5182
BoostGraph::headNode
virtual Node & headNode(const Edge &edge) const
ControlFlowGraph::copyToProcedure
void copyToProcedure(TTAProgram::Procedure &proc, TTAProgram::InstructionReferenceManager *irm=NULL)
Definition: ControlFlowGraph.cc:1448
BoostGraph::node
Node & node(const int index) const
DataDependenceEdge::isBackEdge
bool isBackEdge() const
Definition: DataDependenceEdge.hh:118
TTAProgram::Terminal::registerFile
virtual const TTAMachine::RegisterFile & registerFile() const
Definition: Terminal.cc:225
MoveNode::isDestinationOperation
bool isDestinationOperation() const
BoostGraph< BasicBlockNode, ControlFlowEdge >::NodeSet
std::set< BasicBlockNode *, typename BasicBlockNode ::Comparator > NodeSet
Definition: BoostGraph.hh:86
TTAProgram::Instruction
Definition: Instruction.hh:57
TTAProgram::Move::isUnconditional
bool isUnconditional() const
Definition: Move.cc:154
Procedure.hh
PreOptimizer::handleControlFlowGraph
void handleControlFlowGraph(ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine)
Definition: PreOptimizer.cc:546
ProgramPass
Definition: ProgramPass.hh:52
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
TTAProgram::CodeSnippet::remove
virtual void remove(Instruction &ins)
Definition: CodeSnippet.cc:558
ControlFlowGraph::updateReferencesFromProcToCfg
void updateReferencesFromProcToCfg()
Definition: ControlFlowGraph.cc:2207
GraphNode::nodeID
int nodeID() const
TTAProgram::Move::bus
const TTAMachine::Bus & bus() const
Definition: Move.cc:373
ProgramOperation::switchInputs
void switchInputs(int idx1=1, int idx2=2)
Definition: ProgramOperation.cc:795
ProgramOperation
Definition: ProgramOperation.hh:70
TTAProgram::Move::setGuard
void setGuard(MoveGuard *guard)
Definition: Move.cc:360
MoveNode
Definition: MoveNode.hh:65
MoveNode::isSourceConstant
bool isSourceConstant() const
Definition: MoveNode.cc:238
PreOptimizer::handleCFGDDG
void handleCFGDDG(ControlFlowGraph &cfg, DataDependenceGraph &ddg)
Definition: PreOptimizer.cc:511
PreOptimizer::tryToRemoveXor
ControlFlowGraph::NodeSet tryToRemoveXor(DataDependenceGraph &ddg, ProgramOperation &po, TTAProgram::InstructionReferenceManager *irm, ControlFlowGraph &cfg)
Definition: PreOptimizer.cc:195
Terminal.hh
DataDependenceEdge::EDGE_REGISTER
@ EDGE_REGISTER
Definition: DataDependenceEdge.hh:53
Operation::name
virtual TCEString name() const
Definition: Operation.cc:93
DataDependenceEdge::dependenceType
DependenceType dependenceType() const
Definition: DataDependenceEdge.hh:88
ControlFlowEdge::isTrueEdge
bool isTrueEdge() const
Definition: ControlFlowEdge.cc:119
DataDependenceGraph::onlyRegisterRawSource
MoveNode * onlyRegisterRawSource(const MoveNode &mn, int allowGuardEdges=2, int backEdges=0) const
Definition: DataDependenceGraph.cc:4083
SchedulerCmdLineOptions
Definition: SchedulerCmdLineOptions.hh:45
DEFAULT_LOWMEM_MODE_THRESHOLD
static const int DEFAULT_LOWMEM_MODE_THRESHOLD
Definition: PreOptimizer.cc:62
SchedulerCmdLineOptions.hh
ControlFlowEdge
Definition: ControlFlowEdge.hh:50
SimValue
Definition: SimValue.hh:96
BoostGraph::outDegree
virtual int outDegree(const Node &node) const
DataDependenceGraph::combineNodes
void combineNodes(MoveNode &node1, MoveNode &node2, MoveNode &destination)
Definition: DataDependenceGraph.cc:2782
BasicBlockNode::basicBlock
TTAProgram::BasicBlock & basicBlock()
Definition: BasicBlockNode.cc:126
MoveNode::sourceOperation
ProgramOperation & sourceOperation() const
Definition: MoveNode.cc:453
assert
#define assert(condition)
Definition: Application.hh:86
DataDependenceGraph::deleteNode
void deleteNode(MoveNode &node)
Definition: DataDependenceGraph.cc:2882
TTAProgram::CodeSnippet::insertAfter
virtual void insertAfter(const Instruction &pos, Instruction *ins)
Definition: CodeSnippet.cc:462
DataDependenceGraphBuilder.hh
TTAProgram::Move::setDestination
void setDestination(Terminal *dst)
Definition: Move.cc:333
SchedulerCmdLineOptions::lowMemModeThreshold
virtual int lowMemModeThreshold() const
Definition: SchedulerCmdLineOptions.cc:310
TTAProgram::Terminal::operationIndex
virtual int operationIndex() const
Definition: Terminal.cc:364
PreOptimizer::checkGuardReversalAllowed
bool checkGuardReversalAllowed(DataDependenceGraph &ddg, DataDependenceGraph::EdgeSet &oEdges)
Definition: PreOptimizer.cc:326
BoostGraph< MoveNode, DataDependenceEdge >::EdgeSet
std::set< DataDependenceEdge *, typename DataDependenceEdge ::Comparator > EdgeSet
Definition: BoostGraph.hh:87
Instruction.hh
PreOptimizer::cfgAllowsJumpReversal
bool cfgAllowsJumpReversal(TTAProgram::Instruction &ins, ControlFlowGraph &cfg)
Definition: PreOptimizer.cc:562
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
ControlFlowGraph.hh
DataDependenceEdge::DEP_RAW
@ DEP_RAW
Definition: DataDependenceEdge.hh:47
PreOptimizer::tryToOptimizeAddressReg
bool tryToOptimizeAddressReg(DataDependenceGraph &ddg, ProgramOperation &po)
Definition: PreOptimizer.cc:87
TTAProgram::InstructionReferenceManager::hasReference
bool hasReference(Instruction &ins) const
Definition: InstructionReferenceManager.cc:143
TTAProgram::Move::guard
MoveGuard & guard() const
Definition: Move.cc:345
Application::cmdLineOptions
static CmdLineOptions * cmdLineOptions()
Definition: Application.cc:397
TTAProgram::Instruction::parent
CodeSnippet & parent() const
Definition: Instruction.cc:109
BasicBlockNode
Definition: BasicBlockNode.hh:64
PreOptimizer::PreOptimizer
PreOptimizer(InterPassData &data)
Definition: PreOptimizer.cc:69
TTAProgram::Terminal::isGPR
virtual bool isGPR() const
Definition: Terminal.cc:107
InterPassData
Definition: InterPassData.hh:48
Operation.hh
MoveNode::isSourceOperation
bool isSourceOperation() const
Definition: MoveNode.cc:168
TTAProgram::Terminal::value
virtual SimValue value() const
Definition: Terminal.cc:178
MoveNode::unsetSourceOperation
void unsetSourceOperation()
Definition: MoveNode.cc:760
Operation::readsMemory
virtual bool readsMemory() const
Definition: Operation.cc:242
PreOptimizer::tryToPrecalcConstantAdd
void tryToPrecalcConstantAdd(DataDependenceGraph &ddg, ProgramOperation &po)
Definition: PreOptimizer.cc:412
DataDependenceGraph::programOperationCount
int programOperationCount() const
Definition: DataDependenceGraph.cc:246
TTAProgram::Move
Definition: Move.hh:55
Bus.hh
ProgramOperation::inputMoveCount
int inputMoveCount() const
Definition: ProgramOperation.cc:600
BoostGraph::inEdges
virtual EdgeSet inEdges(const Node &node) const
TTAProgram::CodeSnippet
Definition: CodeSnippet.hh:59
ProgramOperation::outputMoveCount
int outputMoveCount() const
Definition: ProgramOperation.cc:610
PreOptimizer::tryToRemoveGuardInversingOp
ControlFlowGraph::NodeSet tryToRemoveGuardInversingOp(DataDependenceGraph &ddg, ProgramOperation &po, TTAProgram::InstructionReferenceManager *irm, ControlFlowGraph &cfg)
Definition: PreOptimizer.cc:244
ProgramOperation.hh
Operand.hh
MoveNode::isSourceVariable
bool isSourceVariable() const
Definition: MoveNode.cc:196
TTAProgram::TerminalImmediate
Definition: TerminalImmediate.hh:44
BoostGraph::outEdges
virtual EdgeSet outEdges(const Node &node) const
DataDependenceEdge::guardUse
bool guardUse() const
Definition: DataDependenceEdge.hh:100
MoveNode::destinationOperation
ProgramOperation & destinationOperation(unsigned int index=0) const
DataDependenceGraph::addNode
void addNode(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:144
Operation::operand
virtual Operand & operand(int id) const
Definition: Operation.cc:541
MoveNode::move
TTAProgram::Move & move()
SchedulerPass::interPassData
InterPassData & interPassData()
Definition: SchedulerPass.cc:53
DisassemblyRegister.hh
TTAProgram::Move::parent
Instruction & parent() const
Definition: Move.cc:115
CodeGenerator.hh
TTAProgram::InstructionReferenceManager
Definition: InstructionReferenceManager.hh:82
Program.hh
Operand::type
virtual OperandType type() const
Definition: Operand.cc:165
TerminalImmediate.hh
DataDependenceGraphBuilder
Definition: DataDependenceGraphBuilder.hh:70
RegisterFile.hh
TCEString
Definition: TCEString.hh:53
BasicBlock.hh
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
DataDependenceGraphBuilder::build
virtual DataDependenceGraph * build(ControlFlowGraph &cGraph, DataDependenceGraph::AntidependenceLevel antidependenceLevel, const TTAMachine::Machine &mach, const UniversalMachine *um=NULL, bool createMemAndFUDeps=true, bool createDeathInformation=true, llvm::AliasAnalysis *AA=NULL)
Definition: DataDependenceGraphBuilder.cc:2120
PreOptimizer::tryToRemoveEq
ControlFlowGraph::NodeSet tryToRemoveEq(DataDependenceGraph &ddg, ProgramOperation &po, TTAProgram::InstructionReferenceManager *irm, ControlFlowGraph &cfg)
Definition: PreOptimizer.cc:215
TTAProgram::Terminal::copy
virtual Terminal * copy() const =0
InstructionReferenceManager.hh
TTAProgram::Terminal
Definition: Terminal.hh:60
TTAProgram::Terminal::equals
virtual bool equals(const Terminal &other) const =0
DataDependenceEdge
Definition: DataDependenceEdge.hh:43
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
PreOptimizer.hh
ControlFlowGraphPass
Definition: ControlFlowGraphPass.hh:50
DisassemblyRegister::registerName
static TCEString registerName(const TTAMachine::RegisterFile &rf, int index, char delim='.')
Definition: DisassemblyRegister.cc:95
program
find Finds info of the inner loops in the program
Definition: InnerLoopFinder.cc:80
TTAMachine::RegisterFile
Definition: RegisterFile.hh:47
TTAProgram::Move::isJump
bool isJump() const
Definition: Move.cc:164
TTAProgram::CodeGenerator::createInverseGuard
static TTAProgram::MoveGuard * createInverseGuard(const TTAProgram::MoveGuard &mg, const TTAMachine::Bus *bus=NULL)
Definition: CodeGenerator.cc:837
Move.hh
TTAProgram::Terminal::isImmediate
virtual bool isImmediate() const
Definition: Terminal.cc:63
TTAMachine::BaseRegisterFile::width
virtual int width() const
DataDependenceGraph::copyDepsOver
EdgeSet copyDepsOver(MoveNode &node, bool anti, bool raw)
Definition: DataDependenceGraph.cc:2422
BoostGraph::nodeCount
int nodeCount() const
ProgramOperation::outputMove
MoveNode & outputMove(int index) const
Definition: ProgramOperation.cc:632
TTAProgram::Procedure
Definition: Procedure.hh:55
ProgramPass::executeProcedurePass
static void executeProcedurePass(TTAProgram::Program &program, const TTAMachine::Machine &targetMachine, ProcedurePass &procedurePass)
Definition: ProgramPass.cc:72
PreOptimizer::handleProgram
void handleProgram(TTAProgram::Program &program, const TTAMachine::Machine &targetMachine)
Definition: PreOptimizer.cc:81
ControlFlowEdge::isFalseEdge
bool isFalseEdge() const
Definition: ControlFlowEdge.cc:129
TTAProgram::Instruction::moveCount
int moveCount() const
Definition: Instruction.cc:176
DataDependenceGraph::getBasicBlockNode
const BasicBlockNode & getBasicBlockNode(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:186
PreOptimizer::handleProcedure
void handleProcedure(TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetMachine)
Definition: PreOptimizer.cc:484
DataDependenceEdge::edgeReason
EdgeReason edgeReason() const
Definition: DataDependenceEdge.hh:91
ControlFlowGraph
Definition: ControlFlowGraph.hh:100
TTAProgram::Move::setSource
void setSource(Terminal *src)
Definition: Move.cc:312
DataDependenceGraph::NO_ANTIDEPS
@ NO_ANTIDEPS
Definition: DataDependenceGraph.hh:79
ProgramOperation::removeOutputNode
void removeOutputNode(MoveNode &node, int outputIndex)
Definition: ProgramOperation.cc:214
ProgramOperation::inputMove
MoveNode & inputMove(int index) const
Definition: ProgramOperation.cc:621
TTAMachine::Machine
Definition: Machine.hh:73