Initial Commit: Based on TI OpenCL v0.8, originally based on clover.shamrock_v0.8

This is a continuation of the clover OpenCL project:
        http://people.freedesktop.org/~steckdenis/clover

based on the contributions from Texas Instruments for Keystone II DSP device:
        git.ti.com/opencl

and adding contributions from Linaro for ARM CPU-only support.

See README.txt for more info, and build instructions.

Signed-off-by: Gil Pitney <gil.pitney@linaro.org>

1 files changed, 194 insertions, 0 deletions

diff --git a/src/llvmopencl/LoopBarriers.cc b/src/llvmopencl/LoopBarriers.cc
new file mode 100644
index 0000000..5e4965f
--- /dev/null
+++ b/src/llvmopencl/LoopBarriers.cc
@@ -0,0 +1,194 @@
+// LLVM loop pass that adds required barriers to loops.
+// 
+// Copyright (c) 2011 Universidad Rey Juan Carlos
+//               2012-2014 Pekka Jääskeläinen / Tampere University of Technology
+// 
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+// 
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+// 
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+
+#include "config.h"
+#if (defined LLVM_3_1 or defined LLVM_3_2)
+#include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
+#else
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#endif
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include <iostream>
+
+#include "LoopBarriers.h"
+#include "Barrier.h"
+#include "Workgroup.h"
+
+//#define DEBUG_LOOP_BARRIERS
+
+using namespace llvm;
+using namespace pocl;
+
+namespace {
+  static
+  RegisterPass<LoopBarriers> X("loop-barriers",
+                               "Add needed barriers to loops");
+}
+
+char LoopBarriers::ID = 0;
+
+void
+LoopBarriers::getAnalysisUsage(AnalysisUsage &AU) const
+{
+  AU.addRequired<DominatorTree>();
+  AU.addPreserved<DominatorTree>();
+}
+
+bool
+LoopBarriers::runOnLoop(Loop *L, LPPassManager &LPM)
+{
+  if (!Workgroup::isKernelToProcess(*L->getHeader()->getParent()))
+    return false;
+
+  DT = &getAnalysis<DominatorTree>();
+
+  bool changed = ProcessLoop(L, LPM);
+
+  DT->verifyAnalysis();
+
+  return changed;
+}
+
+
+bool
+LoopBarriers::ProcessLoop(Loop *L, LPPassManager &LPM)
+{
+  bool isBLoop = false;
+  bool changed = false;
+
+  for (Loop::block_iterator i = L->block_begin(), e = L->block_end();
+       i != e && !isBLoop; ++i) {
+    for (BasicBlock::iterator j = (*i)->begin(), e = (*i)->end();
+         j != e; ++j) {
+      if (isa<Barrier>(j)) {
+          isBLoop = true;
+          break;
+      }
+    }
+  }
+
+  for (Loop::block_iterator i = L->block_begin(), e = L->block_end();
+       i != e && isBLoop; ++i) {
+    for (BasicBlock::iterator j = (*i)->begin(), e = (*i)->end();
+         j != e; ++j) {
+      if (isa<Barrier>(j)) {
+
+        // Found a barrier in this loop:
+        // 1) add a barrier in the loop header.
+        // 2) add a barrier in the latches
+        
+        // Add a barrier on the preheader to ensure all WIs reach
+        // the loop header with all the previous code already 
+        // executed.
+        BasicBlock *preheader = L->getLoopPreheader();
+        assert((preheader != NULL) && "Non-canonicalized loop found!\n");
+#ifdef DEBUG_LOOP_BARRIERS
+        std::cerr << "### adding to preheader BB" << std::endl;
+        preheader->dump();
+        std::cerr << "### before instr" << std::endl;
+        preheader->getTerminator()->dump();
+#endif
+        Barrier::Create(preheader->getTerminator());
+        preheader->setName(preheader->getName() + ".loopbarrier");
+
+        // Add a barrier after the PHI nodes on the header (the replicated
+        // headers will be merged afterwards).
+        BasicBlock *header = L->getHeader();
+        if (header->getFirstNonPHI() != &header->front()) {
+          Barrier::Create(header->getFirstNonPHI());
+          header->setName(header->getName() + ".phibarrier");
+          // Split the block to  create a replicable region of
+          // the loop contents in case the phi node contains a
+          // branch (that can be to inside the region).
+          //          if (header->getTerminator()->getNumSuccessors() > 1)
+          //    SplitBlock(header, header->getTerminator(), this);
+        }
+
+        // Add the barriers on the exiting block and the latches,
+        // which might not always be the same if there is computation
+        // after the exit decision.
+        BasicBlock *brexit = L->getExitingBlock();
+        if (brexit != NULL) {
+          Barrier::Create(brexit->getTerminator());
+          brexit->setName(brexit->getName() + ".brexitbarrier");
+        }
+
+        BasicBlock *latch = L->getLoopLatch();
+        if (latch != NULL && brexit != latch) {
+          // This loop has only one latch. Do not check for dominance, we
+          // are probably running before BTR.
+          Barrier::Create(latch->getTerminator());
+          latch->setName(latch->getName() + ".latchbarrier");
+          return changed;
+        }
+
+        // Modified code from llvm::LoopBase::getLoopLatch to
+        // go trough all the latches.
+        BasicBlock *Header = L->getHeader();
+        typedef GraphTraits<Inverse<BasicBlock *> > InvBlockTraits;
+        InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(Header);
+        InvBlockTraits::ChildIteratorType PE = InvBlockTraits::child_end(Header);
+        BasicBlock *Latch = NULL;
+        for (; PI != PE; ++PI) {
+          InvBlockTraits::NodeType *N = *PI;
+          if (L->contains(N)) {
+            Latch = N;
+            // Latch found in the loop, see if the barrier dominates it
+            // (otherwise if might no even belong to this "tail", see
+            // forifbarrier1 graph test).
+            if (DT->dominates(j->getParent(), Latch)) {
+              Barrier::Create(Latch->getTerminator());
+              Latch->setName(Latch->getName() + ".latchbarrier");
+            }
+          }
+        }
+        return true;
+      }
+    }
+  }
+
+  /* This is a loop without a barrier. Ensure we have a non-barrier
+     block as a preheader so we can replicate the loop as a whole. 
+
+     If the block has proper instructions after the barrier, it
+     will be split in CanonicalizeBarriers. */
+  BasicBlock *preheader = L->getLoopPreheader();
+  assert((preheader != NULL) && "Non-canonicalized loop found!\n");
+  TerminatorInst *t = preheader->getTerminator();
+  Instruction *prev = NULL;
+  if (&preheader->front() != t)
+    prev = t->getPrevNode();
+  if (prev && isa<Barrier>(prev))
+    {
+      BasicBlock *new_b = SplitBlock(preheader, t, this);
+      new_b->setName(preheader->getName() + ".postbarrier_dummy");
+      return true;
+    }
+
+  return changed;
+}
+