compiler/resolution/lowerIterators.cpp
// Replace a ForLoop with its inline equivalent, if possible.
// Otherwise, convert it into a C-style for loop.
// The given forLoop is converted unconditionally.
Replace a ForLoop with its inline equivalent, if possible.
Otherwise, convert it into a C-style for loop.
The given forLoop is converted unconditionally.
Replace a ForLoop with its inline equivalent if possible . Otherwise convert it into a C - style for loop . The given forLoop is converted unconditionally .
static void
expandForLoop(ForLoop* forLoop) {
  SymExpr*   se2      = forLoop->iteratorGet();
  VarSymbol* iterator = toVarSymbol(se2->symbol());
  bool converted = false;
  if (!fNoInlineIterators)
  {
    FnSymbol* iterFn = getTheIteratorFn(iterator->type);
    if (iterFn->iteratorInfo && canInlineIterator(iterFn) &&
        !isVirtualIterator(iterator)) {
      converted = expandIteratorInline(forLoop);
    }
  }
  if (! converted)
  {
    SET_LINENO(forLoop);
    Vec<Symbol*> iterators;
    Vec<Symbol*> indices;
    FnSymbol* iterFn = getTheIteratorFn(iterator->type);
    if (iterFn->throwsError()) {
      USR_FATAL("Throwing non-inlined iterators are not yet supported");
    }
    SymExpr*     se1       = toSymExpr(forLoop->indexGet());
    VarSymbol*   index     = toVarSymbol(se1->symbol());
    BlockStmt*   initBlock = new BlockStmt();
    BlockStmt*   testBlock = NULL;
    BlockStmt*   incrBlock = new BlockStmt();
    setupSimultaneousIterators(iterators, indices, iterator, index, forLoop);
    bool allOrderIndependent = true;
    for (int i = 0; i < iterators.n; i++) {
      Vec<Type*> children;
      VarSymbol* cond         = newTemp("_cond", dtBool);
      bool       isNotDynIter = false;
      getIteratorChildren(children, iterators.v[i]->type);
      forLoop->insertBefore(buildIteratorCall(NULL,         ZIP1,     iterators.v[i], children));
      forLoop->insertAtHead(buildIteratorCall(indices.v[i], GETVALUE, iterators.v[i], children));
      isNotDynIter = (children.n == 0);
      if (isNotDynIter) {
        initBlock->insertAtTail(buildIteratorCall(NULL, INIT, iterators.v[i], children));
        incrBlock->insertAtTail(buildIteratorCall(NULL, INCR, iterators.v[i], children));
      } else {
        forLoop->insertBefore(buildIteratorCall(NULL, INIT, iterators.v[i], children));
        forLoop->insertAtTail(buildIteratorCall(NULL, INCR, iterators.v[i], children));
      }
      forLoop->insertAtTail(buildIteratorCall(NULL, ZIP3, iterators.v[i], children));
      forLoop->insertAfter (buildIteratorCall(NULL, ZIP4, iterators.v[i], children));
      FnSymbol* iterFn = getTheIteratorFn(iterators.v[i]);
      if (isBoundedIterator(iterFn)) {
        if (testBlock == NULL) {
          if (isNotDynIter) {
            testBlock = buildIteratorCall(NULL, HASMORE, iterators.v[i], children);
          } else {
             block and add checks for
            forLoop->insertBefore(new DefExpr(cond));
            forLoop->insertBefore(buildIteratorCall(cond, HASMORE, iterators.v[i], children));
            forLoop->insertAtTail(buildIteratorCall(cond, HASMORE, iterators.v[i], children));
            testBlock = new BlockStmt(new SymExpr(cond));
          }
        } else if (!fNoBoundsChecks) {
          VarSymbol* hasMore    = newTemp("hasMore",    dtBool);
          VarSymbol* isFinished = newTemp("isFinished", dtBool);
          forLoop->insertBefore(new DefExpr(isFinished));
          forLoop->insertBefore(new DefExpr(hasMore));
          forLoop->insertAtHead(new CondStmt(new SymExpr(isFinished),
                                             new CallExpr(PRIM_RT_ERROR,
                                                          new_CStringSymbol("zippered iterations have non-equal lengths"))));
          forLoop->insertAtHead(new CallExpr(PRIM_MOVE, isFinished, new CallExpr(PRIM_UNARY_LNOT, hasMore)));
          forLoop->insertAtHead(buildIteratorCall(hasMore, HASMORE, iterators.v[i], children));
          forLoop->insertAfter(new CondStmt(new SymExpr(hasMore),
                                            new CallExpr(PRIM_RT_ERROR,
                                                         new_CStringSymbol("zippered iterations have non-equal lengths"))));
          forLoop->insertAfter(buildIteratorCall(hasMore, HASMORE, iterators.v[i], children));
        }
      }
      forLoop->insertAtHead(buildIteratorCall(NULL, ZIP2, iterators.v[i], children));
      iterFn->collapseBlocks();
      Vec<BaseAST*> asts;
      collect_asts_postorder(iterFn, asts);
      bool curOrderIndependent = false;
      if (CallExpr* singleLoopYield = isSingleLoopIterator(iterFn, asts)) {
        if (LoopStmt* loop = LoopStmt::findEnclosingLoop(singleLoopYield)) {
          curOrderIndependent = loop->isOrderIndependent() || forLoop->isOrderIndependent();
        }
      }
      allOrderIndependent = allOrderIndependent && curOrderIndependent;
    }
    forLoop->orderIndependentSet(allOrderIndependent);
    if (index != gVoid)
      forLoop->insertAtHead(index->defPoint->remove());
    if (testBlock == NULL) {
      testBlock = new BlockStmt();
      testBlock->insertAtTail(new SymExpr(gTrue));
    }
    CForLoop* cforLoop = CForLoop::buildWithBodyFrom(forLoop);
    cforLoop->loopHeaderSet(initBlock, testBlock, incrBlock);
    forLoop->replace(cforLoop);
  }
}
static void expandForLoop ( ForLoop * forLoop ) { SymExpr * se2 = forLoop -> iteratorGet ( ) ; VarSymbol * iterator = toVarSymbol ( se2 -> symbol ( ) ) ; bool converted = false ; if ( ! fNoInlineIterators ) { FnSymbol * iterFn = getTheIteratorFn ( iterator -> type ) ; if ( iterFn -> iteratorInfo && canInlineIterator ( iterFn ) && ! isVirtualIterator ( iterator ) ) { converted = expandIteratorInline ( forLoop ) ; } } if ( ! converted ) { SET_LINENO ( forLoop ) ; Vec < Symbol * > iterators ; Vec < Symbol * > indices ; FnSymbol * iterFn = getTheIteratorFn ( iterator -> type ) ; if ( iterFn -> throwsError ( ) ) { USR_FATAL ( " " ) ; } SymExpr * se1 = toSymExpr ( forLoop -> indexGet ( ) ) ; VarSymbol * index = toVarSymbol ( se1 -> symbol ( ) ) ; BlockStmt * initBlock = new BlockStmt ( ) ; BlockStmt * testBlock = NULL ; BlockStmt * incrBlock = new BlockStmt ( ) ; setupSimultaneousIterators ( iterators , indices , iterator , index , forLoop ) ; bool allOrderIndependent = true ; for ( int i = 0 ; i < iterators . n ; i ++ ) { Vec < Type * > children ; VarSymbol * cond = newTemp ( " " , dtBool ) ; bool isNotDynIter = false ; getIteratorChildren ( children , iterators . v [ i ] -> type ) ; forLoop -> insertBefore ( buildIteratorCall ( NULL , ZIP1 , iterators . v [ i ] , children ) ) ; forLoop -> insertAtHead ( buildIteratorCall ( indices . v [ i ] , GETVALUE , iterators . v [ i ] , children ) ) ; isNotDynIter = ( children . n == 0 ) ; if ( isNotDynIter ) { initBlock -> insertAtTail ( buildIteratorCall ( NULL , INIT , iterators . v [ i ] , children ) ) ; incrBlock -> insertAtTail ( buildIteratorCall ( NULL , INCR , iterators . v [ i ] , children ) ) ; } else { forLoop -> insertBefore ( buildIteratorCall ( NULL , INIT , iterators . v [ i ] , children ) ) ; forLoop -> insertAtTail ( buildIteratorCall ( NULL , INCR , iterators . v [ i ] , children ) ) ; } forLoop -> insertAtTail ( buildIteratorCall ( NULL , ZIP3 , iterators . v [ i ] , children ) ) ; forLoop -> insertAfter ( buildIteratorCall ( NULL , ZIP4 , iterators . v [ i ] , children ) ) ; FnSymbol * iterFn = getTheIteratorFn ( iterators . v [ i ] ) ; if ( isBoundedIterator ( iterFn ) ) { if ( testBlock == NULL ) { if ( isNotDynIter ) { testBlock = buildIteratorCall ( NULL , HASMORE , iterators . v [ i ] , children ) ; } else { forLoop -> insertBefore ( new DefExpr ( cond ) ) ; forLoop -> insertBefore ( buildIteratorCall ( cond , HASMORE , iterators . v [ i ] , children ) ) ; forLoop -> insertAtTail ( buildIteratorCall ( cond , HASMORE , iterators . v [ i ] , children ) ) ; testBlock = new BlockStmt ( new SymExpr ( cond ) ) ; } } else if ( ! fNoBoundsChecks ) { VarSymbol * hasMore = newTemp ( " " , dtBool ) ; VarSymbol * isFinished = newTemp ( " " , dtBool ) ; forLoop -> insertBefore ( new DefExpr ( isFinished ) ) ; forLoop -> insertBefore ( new DefExpr ( hasMore ) ) ; forLoop -> insertAtHead ( new CondStmt ( new SymExpr ( isFinished ) , new CallExpr ( PRIM_RT_ERROR , new_CStringSymbol ( " " ) ) ) ) ; forLoop -> insertAtHead ( new CallExpr ( PRIM_MOVE , isFinished , new CallExpr ( PRIM_UNARY_LNOT , hasMore ) ) ) ; forLoop -> insertAtHead ( buildIteratorCall ( hasMore , HASMORE , iterators . v [ i ] , children ) ) ; forLoop -> insertAfter ( new CondStmt ( new SymExpr ( hasMore ) , new CallExpr ( PRIM_RT_ERROR , new_CStringSymbol ( " " ) ) ) ) ; forLoop -> insertAfter ( buildIteratorCall ( hasMore , HASMORE , iterators . v [ i ] , children ) ) ; } } forLoop -> insertAtHead ( buildIteratorCall ( NULL , ZIP2 , iterators . v [ i ] , children ) ) ; iterFn -> collapseBlocks ( ) ; Vec < BaseAST * > asts ; collect_asts_postorder ( iterFn , asts ) ; bool curOrderIndependent = false ; if ( CallExpr * singleLoopYield = isSingleLoopIterator ( iterFn , asts ) ) { if ( LoopStmt * loop = LoopStmt :: findEnclosingLoop ( singleLoopYield ) ) { curOrderIndependent = loop -> isOrderIndependent ( ) || forLoop -> isOrderIndependent ( ) ; } } allOrderIndependent = allOrderIndependent && curOrderIndependent ; } forLoop -> orderIndependentSet ( allOrderIndependent ) ; if ( index != gVoid ) forLoop -> insertAtHead ( index -> defPoint -> remove ( ) ) ; if ( testBlock == NULL ) { testBlock = new BlockStmt ( ) ; testBlock -> insertAtTail ( new SymExpr ( gTrue ) ) ; } CForLoop * cforLoop = CForLoop :: buildWithBodyFrom ( forLoop ) ; cforLoop -> loopHeaderSet ( initBlock , testBlock , incrBlock ) ; forLoop -> replace ( cforLoop ) ; } }
Replace a ForLoop with its inline equivalent, if possible.
Replace a ForLoop with its inline equivalent if possible .
// This code handles zippered iterators, dynamic iterators, and any other // iterator that cannot be inlined. // When expanding a single-loop iterator with a single yield, the generated // code looks like: //   zip1(_iterator1); zip1(_iterator2); //   idx2 = getValue(_iterator2); idx1 = getValue(_iterator1); //   bool more1 = hasMore(iterator1); //   for (init(_iterator1), init(_iterator2); more1; incr(_iterator1), incr(_iterator2)) { //     zip2(_iterator); //     // Bounds checks inserted here. //     zip3(_iterator1); zip3(_iterator2); //     more = hasMore(iterator1); //   } //   zip4(_iterator2); zip4(_iterator1); // In zippered iterators, each clause may contain multiple calls to zip1(), // getValue(), etc.  These are inserted in the order shown. // In this event, the error handling pass added a PRIM_CHECK_ERROR // after the call to the iterator function. // Scroll backwards to find the error handling block. // TODO: finish this case //       I think we need to use the ForLoop's break label // For each iterator we add the zip* functions in the appropriate place and // if bounds checking was on, we insert the code for that. Note that this // code handles iterators that have regular loops, c for loops, and // dynamically dispatched iterators. The ordering is VERY important! // Add zip1 before the loop // Get the current value of the iterator. // add the init, and incr functions to the init, and incr blocks of the // c for loop. If the underlying iterator does not have a c for loop, // these blocks will be empty // for dynamically dispatched iterators, conditional checks and other // code are added in buildIteratorCall. These constructs aren't legal // in a c for loop, so instead of creating a well formed c for loop we // add the init before the loop, and the incr at the bottom of it. // Add zip3 and zip4 at tail and after the loop respectively. // note that we have found the first test // note that we have found the first test block and add checks for // more before and at the end of the loop. As mentioned above, // dynamic iterators generate things that can't be in the header of // the c for loop, so we generate a simple bool variable to put at // the test of the c for loop, and update that condition var before // the loop is run, and at the end of each iteration. // for all but the first iterator add checks at the beginning of each loop run // and a final one after to make sure the other iterators don't finish before // the "leader" and they don't have more afterwards. // Need to check if iterator will be inlined, isSingleLoopIterator() // doesn't handle arbitrary blockstmts well, so we collapse them first // If the iterator cannot be inlined a re-entrant advance function will // be built. This function maintains state and must be called in order. // If inlined, the iterator's loop will be order independent if it was // independent prior to inlining or the forLoop is order independent // The loop will be order independent if all the iters it zips are order // independent (all iters will be inlined and were all marked order // independent or the forLoop was marked independent prior zippering.) // 2015-02-23 hilde: // TODO: I think this wants to be insertBefore, and moved before the call // to getValue is inserted.  Check the order in the generated code to see // if this is the case.  Avoid moving the global void value when it is // the loop index. // Ensure that the test clause for completely unbounded loops contains // something. // testBlock is only non-NULL if isBoundedIterator() evaluates to true for // at least one of the iterators being zippered together. // NOAKES 2014/11/19: An error occurs if the replacement is moved to // earlier in the pass.  I have yet to identify the issue but suspect // that doing the copy too soon causes variables to cross from one // scope to another if done in mid-transformation. // Even for zippered iterators we only have one conditional test for the // loop. This takes that conditional and puts it into the test segment of // the c for loop.  Code in the initBlock and incrBlock clauses are each a // concatenation of the init() and incr() calls for all iterators being // zippered together.  The init() and incr() calls appear in the same order // as the iterators appear in the zip(,,) tuple.