OpenASIP  2.0
Public Member Functions | Private Member Functions | List of all members
PreOptimizer Class Reference

#include <PreOptimizer.hh>

Inheritance diagram for PreOptimizer:
Inheritance graph
Collaboration diagram for PreOptimizer:
Collaboration graph

Public Member Functions

 PreOptimizer (InterPassData &data)
 
void handleProgram (TTAProgram::Program &program, const TTAMachine::Machine &targetMachine)
 
void handleProcedure (TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetMachine)
 
void handleControlFlowGraph (ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine)
 
void handleCFGDDG (ControlFlowGraph &cfg, DataDependenceGraph &ddg)
 
std::string shortDescription () const
 
- Public Member Functions inherited from ProcedurePass
 ProcedurePass (InterPassData &data)
 
virtual ~ProcedurePass ()
 
- Public Member Functions inherited from SchedulerPass
 SchedulerPass (InterPassData &data)
 
virtual ~SchedulerPass ()
 
InterPassDatainterPassData ()
 
virtual std::string longDescription () const
 
- Public Member Functions inherited from ProgramPass
 ProgramPass (InterPassData &data)
 
virtual ~ProgramPass ()
 
- Public Member Functions inherited from ControlFlowGraphPass
 ControlFlowGraphPass (InterPassData &data)
 
virtual ~ControlFlowGraphPass ()
 
void executeBasicBlockPass (ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine, BasicBlockPass &bbPass)
 

Private Member Functions

ControlFlowGraph::NodeSet inverseGuardsOfHeads (DataDependenceGraph &ddg, DataDependenceGraph::EdgeSet &oEdges)
 
bool checkGuardReversalAllowed (DataDependenceGraph &ddg, DataDependenceGraph::EdgeSet &oEdges)
 
bool tryToOptimizeAddressReg (DataDependenceGraph &ddg, ProgramOperation &po)
 
ControlFlowGraph::NodeSet tryToRemoveXor (DataDependenceGraph &ddg, ProgramOperation &po, TTAProgram::InstructionReferenceManager *irm, ControlFlowGraph &cfg)
 
ControlFlowGraph::NodeSet tryToRemoveEq (DataDependenceGraph &ddg, ProgramOperation &po, TTAProgram::InstructionReferenceManager *irm, ControlFlowGraph &cfg)
 
ControlFlowGraph::NodeSet tryToRemoveGuardInversingOp (DataDependenceGraph &ddg, ProgramOperation &po, TTAProgram::InstructionReferenceManager *irm, ControlFlowGraph &cfg)
 
bool cfgAllowsJumpReversal (TTAProgram::Instruction &ins, ControlFlowGraph &cfg)
 
void tryToPrecalcConstantAdd (DataDependenceGraph &ddg, ProgramOperation &po)
 

Additional Inherited Members

- Static Public Member Functions inherited from ProcedurePass
static void copyCfgToProcedure (TTAProgram::Procedure &procedure, ControlFlowGraph &cfg)
 
static void executeControlFlowGraphPass (TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetmachine, ControlFlowGraphPass &cfgp)
 
- Static Public Member Functions inherited from ProgramPass
static void executeProcedurePass (TTAProgram::Program &program, const TTAMachine::Machine &targetMachine, ProcedurePass &procedurePass)
 

Detailed Description

Definition at line 66 of file PreOptimizer.hh.

Constructor & Destructor Documentation

◆ PreOptimizer()

PreOptimizer::PreOptimizer ( InterPassData data)

Constructor. Initializes interpassData.

Parameters
dataInterPassData to store.

Definition at line 69 of file PreOptimizer.cc.

69  : ProcedurePass(data),
70  ProgramPass(data),
71  ControlFlowGraphPass(data) {
72 }

Member Function Documentation

◆ cfgAllowsJumpReversal()

bool PreOptimizer::cfgAllowsJumpReversal ( TTAProgram::Instruction ins,
ControlFlowGraph cfg 
)
private

Check that we can revert the out edges of the cfg when reverting a jump guard

Definition at line 562 of file PreOptimizer.cc.

563  {
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 }

References BasicBlockNode::basicBlock(), ControlFlowEdge::isFalseEdge(), ControlFlowEdge::isTrueEdge(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), BoostGraph< GraphNode, GraphEdge >::outDegree(), BoostGraph< GraphNode, GraphEdge >::outEdge(), and TTAProgram::Instruction::parent().

Referenced by tryToRemoveGuardInversingOp().

Here is the call graph for this function:

◆ checkGuardReversalAllowed()

bool PreOptimizer::checkGuardReversalAllowed ( DataDependenceGraph ddg,
DataDependenceGraph::EdgeSet oEdges 
)
private

Definition at line 326 of file PreOptimizer.cc.

328  {
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 }

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), MoveNode::destinationOperation(), DataDependenceEdge::guardUse(), BoostGraph< GraphNode, GraphEdge >::headNode(), BoostGraph< GraphNode, GraphEdge >::inEdges(), MoveNode::isDestinationOperation(), Operation::name(), and ProgramOperation::operation().

Referenced by tryToRemoveGuardInversingOp().

Here is the call graph for this function:

◆ handleCFGDDG()

void PreOptimizer::handleCFGDDG ( ControlFlowGraph cfg,
DataDependenceGraph ddg 
)

Definition at line 511 of file PreOptimizer.cc.

513  {
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 }

References Operation::name(), ProgramOperation::operation(), program, ControlFlowGraph::program(), DataDependenceGraph::programOperation(), DataDependenceGraph::programOperationCount(), Operation::readsMemory(), ControlFlowGraph::reverseGuardOnOutEdges(), tryToOptimizeAddressReg(), tryToPrecalcConstantAdd(), tryToRemoveEq(), and tryToRemoveXor().

Referenced by llvm::LLVMTCEIRBuilder::compileOptimized(), and handleControlFlowGraph().

Here is the call graph for this function:

◆ handleControlFlowGraph()

void PreOptimizer::handleControlFlowGraph ( ControlFlowGraph cfg,
const TTAMachine::Machine targetMachine 
)
virtual

Handles a single control flow graph.

The pass should work with any kind of control flow graph, it should not assume the CFG represents a whole procedure, for example.

Parameters
cfgThe control flow graph to handle.
machineThe target machine if any. (NullMachine::instance() if target machine is irrelevant).
Exceptions
Incase handling is unsuccesful for any reason (cfg might still get modified).

Reimplemented from ControlFlowGraphPass.

Definition at line 546 of file PreOptimizer.cc.

547  {
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 }

References DataDependenceGraphBuilder::build(), handleCFGDDG(), SchedulerPass::interPassData(), and DataDependenceGraph::NO_ANTIDEPS.

Referenced by handleProcedure().

Here is the call graph for this function:

◆ handleProcedure()

void PreOptimizer::handleProcedure ( TTAProgram::Procedure procedure,
const TTAMachine::Machine mach 
)
virtual

Handles a procedure.

Parameters
procedurethe procedure.
targetMachinetargetmachine. Not used at all.

Reimplemented from ProcedurePass.

Definition at line 484 of file PreOptimizer.cc.

485  {
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()*/);
502  cfg.updateReferencesFromProcToCfg();
503 
504  handleControlFlowGraph(cfg, mach);
505 
506  // copy back to the program.
507  cfg.copyToProcedure(procedure);
508 }

References Application::cmdLineOptions(), ControlFlowGraph::copyToProcedure(), DEFAULT_LOWMEM_MODE_THRESHOLD, handleControlFlowGraph(), TTAProgram::CodeSnippet::instructionCount(), SchedulerCmdLineOptions::lowMemModeThreshold(), and ControlFlowGraph::updateReferencesFromProcToCfg().

Here is the call graph for this function:

◆ handleProgram()

void PreOptimizer::handleProgram ( TTAProgram::Program program,
const TTAMachine::Machine targetMachine 
)
virtual

Handles a program.

Parameters
programthe program.
targetMachinetargetmachine. Not used at all.

Reimplemented from ProgramPass.

Definition at line 81 of file PreOptimizer.cc.

82  {
83  ProgramPass::executeProcedurePass(program, targetMachine, *this);
84 }

References ProgramPass::executeProcedurePass(), and program.

Here is the call graph for this function:

◆ inverseGuardsOfHeads()

ControlFlowGraph::NodeSet PreOptimizer::inverseGuardsOfHeads ( DataDependenceGraph ddg,
DataDependenceGraph::EdgeSet oEdges 
)
private

Definition at line 380 of file PreOptimizer.cc.

382  {
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 }

References assert, TTAProgram::CodeGenerator::createInverseGuard(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), MoveNode::destinationOperation(), DataDependenceGraph::getBasicBlockNode(), TTAProgram::Move::guard(), DataDependenceEdge::guardUse(), BoostGraph< GraphNode, GraphEdge >::headNode(), TTAProgram::Move::isJump(), TTAProgram::Move::isUnconditional(), MoveNode::move(), TTAProgram::Move::setGuard(), and ProgramOperation::switchInputs().

Referenced by tryToRemoveGuardInversingOp().

Here is the call graph for this function:

◆ shortDescription()

std::string PreOptimizer::shortDescription ( ) const
inlinevirtual

A short description of the pass, usually the optimization name, such as "basic block scheduler".

Returns
The description as a string.

Implements SchedulerPass.

Definition at line 86 of file PreOptimizer.hh.

86  {
87  return "optimizes away guard nagation operations, "
88  "uses opposite guards instead"; };

◆ tryToOptimizeAddressReg()

bool PreOptimizer::tryToOptimizeAddressReg ( DataDependenceGraph ddg,
ProgramOperation po 
)
private

Definition at line 87 of file PreOptimizer.cc.

88  {
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 }

References TTAProgram::Terminal::copy(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceGraph::getBasicBlockNode(), DataDependenceEdge::guardUse(), BoostGraph< GraphNode, GraphEdge >::headNode(), BoostGraph< GraphNode, GraphEdge >::inEdges(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), DataDependenceEdge::isBackEdge(), TTAProgram::Terminal::isGPR(), MoveNode::move(), TTAMachine::Component::name(), GraphNode::nodeID(), BoostGraph< GraphNode, GraphEdge >::outEdges(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), TTAProgram::Terminal::registerFile(), DisassemblyRegister::registerName(), DataDependenceGraph::renamedSimpleLiveRange(), TTAProgram::Move::setDestination(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), BoostGraph< GraphNode, GraphEdge >::tailNode(), and TTAMachine::BaseRegisterFile::width().

Referenced by handleCFGDDG().

Here is the call graph for this function:

◆ tryToPrecalcConstantAdd()

void PreOptimizer::tryToPrecalcConstantAdd ( DataDependenceGraph ddg,
ProgramOperation po 
)
private

Remove additions that can be removed staticly. LLVM leaves these when another ide of the addition is an address of a global variable.

Definition at line 412 of file PreOptimizer.cc.

413  {
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 }

References assert, DataDependenceGraph::deleteNode(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isSourceConstant(), MoveNode::isSourceVariable(), MoveNode::move(), TTAProgram::Instruction::moveCount(), Operation::name(), DataDependenceGraph::onlyRegisterRawSource(), ProgramOperation::operation(), ProgramOperation::outputMove(), TTAProgram::Move::parent(), TTAProgram::Instruction::parent(), TTAProgram::CodeSnippet::remove(), ProgramOperation::removeOutputNode(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), and MoveNode::unsetSourceOperation().

Referenced by handleCFGDDG().

Here is the call graph for this function:

◆ tryToRemoveEq()

ControlFlowGraph::NodeSet PreOptimizer::tryToRemoveEq ( DataDependenceGraph ddg,
ProgramOperation po,
TTAProgram::InstructionReferenceManager irm,
ControlFlowGraph cfg 
)
private

Definition at line 215 of file PreOptimizer.cc.

217  {
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 }

References Operand::BOOL, ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), SimValue::intValue(), TTAProgram::Terminal::isImmediate(), MoveNode::isSourceOperation(), MoveNode::move(), DataDependenceGraph::onlyRegisterRawSource(), Operation::operand(), ProgramOperation::operation(), TTAProgram::Terminal::operationIndex(), ProgramOperation::outputMoveCount(), TTAProgram::Move::source(), MoveNode::sourceOperation(), tryToRemoveGuardInversingOp(), Operand::type(), and TTAProgram::Terminal::value().

Referenced by handleCFGDDG().

Here is the call graph for this function:

◆ tryToRemoveGuardInversingOp()

ControlFlowGraph::NodeSet PreOptimizer::tryToRemoveGuardInversingOp ( DataDependenceGraph ddg,
ProgramOperation po,
TTAProgram::InstructionReferenceManager irm,
ControlFlowGraph cfg 
)
private

Definition at line 244 of file PreOptimizer.cc.

247  {
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 }

References TTAProgram::Instruction::addMove(), DataDependenceGraph::addNode(), assert, TTAProgram::Move::bus(), cfgAllowsJumpReversal(), checkGuardReversalAllowed(), DataDependenceGraph::combineNodes(), TTAProgram::Terminal::copy(), DataDependenceGraph::copyDepsOver(), DataDependenceGraph::deleteNode(), TTAProgram::Move::destination(), TTAProgram::Terminal::equals(), TTAProgram::InstructionReferenceManager::hasReference(), ProgramOperation::inputMove(), TTAProgram::CodeSnippet::insertAfter(), inverseGuardsOfHeads(), MoveNode::move(), TTAProgram::Instruction::moveCount(), BoostGraph< GraphNode, GraphEdge >::outEdges(), ProgramOperation::outputMove(), TTAProgram::Move::parent(), TTAProgram::Instruction::parent(), TTAProgram::CodeSnippet::remove(), and TTAProgram::Move::source().

Referenced by tryToRemoveEq(), and tryToRemoveXor().

Here is the call graph for this function:

◆ tryToRemoveXor()

ControlFlowGraph::NodeSet PreOptimizer::tryToRemoveXor ( DataDependenceGraph ddg,
ProgramOperation po,
TTAProgram::InstructionReferenceManager irm,
ControlFlowGraph cfg 
)
private

Tries to remove an unnecessary guard value xor before a conditional jump.

Tries to remove xor operation which is used for converting false boolean value into true boolean value which is then used for jump. The xor operation is removed and the jump predicate reversed.

Parameters
ddgThe datadependence graph of the whole function
poProgramOperation which is a xor operation
irminstructionreferencemanager of the program.
Returns
Basic block whose output edge predicates need to be reversed of cfg or NULL if no need to change cfg.

Definition at line 195 of file PreOptimizer.cc.

197  {
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 }

References ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), SimValue::intValue(), TTAProgram::Terminal::isImmediate(), MoveNode::move(), ProgramOperation::outputMoveCount(), TTAProgram::Move::source(), tryToRemoveGuardInversingOp(), and TTAProgram::Terminal::value().

Referenced by handleCFGDDG().

Here is the call graph for this function:

The documentation for this class was generated from the following files:
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
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
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
PreOptimizer::handleControlFlowGraph
void handleControlFlowGraph(ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine)
Definition: PreOptimizer.cc:546
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
TTAProgram::CodeSnippet::remove
virtual void remove(Instruction &ins)
Definition: CodeSnippet.cc:558
ProgramPass::ProgramPass
ProgramPass(InterPassData &data)
Definition: ProgramPass.cc:48
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
DataDependenceEdge::EDGE_REGISTER
@ EDGE_REGISTER
Definition: DataDependenceEdge.hh:53
ControlFlowGraphPass::ControlFlowGraphPass
ControlFlowGraphPass(InterPassData &data)
Definition: ControlFlowGraphPass.cc:42
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
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
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
PreOptimizer::cfgAllowsJumpReversal
bool cfgAllowsJumpReversal(TTAProgram::Instruction &ins, ControlFlowGraph &cfg)
Definition: PreOptimizer.cc:562
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
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
TTAProgram::Terminal::isGPR
virtual bool isGPR() const
Definition: Terminal.cc:107
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
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
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
TTAProgram::Move::parent
Instruction & parent() const
Definition: Move.cc:115
TTAProgram::InstructionReferenceManager
Definition: InstructionReferenceManager.hh:82
Operand::type
virtual OperandType type() const
Definition: Operand.cc:165
DataDependenceGraphBuilder
Definition: DataDependenceGraphBuilder.hh:70
TCEString
Definition: TCEString.hh:53
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
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
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
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
ProcedurePass::ProcedurePass
ProcedurePass(InterPassData &data)
Definition: ProcedurePass.cc:53
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
ProgramPass::executeProcedurePass
static void executeProcedurePass(TTAProgram::Program &program, const TTAMachine::Machine &targetMachine, ProcedurePass &procedurePass)
Definition: ProgramPass.cc:72
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
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