OpenMP for loop fusion

[abidmalikwaterloo]

Summary

The patch combine two openmp for loop with static scheduling strategy having the same parameters.

[jdoerfert]

This patch *does not* perform loop fusion. Nor do we want it to. We want to deduplicate OpenMP runtime calls that are involved in OpenMP worksharing loops. Please make this clear in the commit message and description. The latter should go into more detail what is happening here and why.

There are various problems wrt. the coding standards. I will only comment on a few but the patch needs to be updated according to the coding standard and the surrounding code patterns.

Why are there no tests?

---

The code is complicated and hard to read, especially given the lack of comments and documentation. Please read through my inline comments. Afterwards, I suggest you start by

1. identifying call sites as the surrounding code does it, then
2. filter call sites that are not legible on their own, then
3. for each call site, find a matching one, if found, replace and rewrite and try again.

You should have test cases that are developed as part of the patch. You should also put early versions for review so you can get feedback.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

127

As mentioned in the main message, this does not perform loop fusion. It is a more complex deduplication of runtime calls that may enable loop fusion but for the sake of this patch and this code it is just runtime call deduplication.

168

While I am pretty sure the entire map construction is overly complicated and should be replaced, you can achieve the above with something like:

for (const auto &It : m)
  if (llvm::any_of(It.second, [I](CallInst *CI) { return I == CI;}))
    return true;
return false;

221

Why does it always return false?

227

Please use modern C++. LLVM is currently based on C++14, for years we allow range based loops:
for (Instruction *I : instructions(F)) {

230

Please look take a look at deduplicateRuntimeCalls and deleteParallelRegions. Their we utilize a caching system to find calls to OpenMP runtime functions. It is important that we do not cause a constant overhead in this pass by scanning instructions multiple times.

239

Since you are interested in special stores only it would make sense to look for them explicitly, e.g., by following the uses of arguments passed into the __kmpc_for_static_init_4 call.

245

Most of these functions lack documentation and all of them lack comments explaining the code.
The names need to be adjusted wrt. the coding standard *and* to make them expressive. For example, "clean" is nothing I can associate with an action.

248

We cannot have stray debug output.

[jdoerfert]

You need to squash your commits or create the diff against the proper base commit. More comments inlined but there is a lot more to comment on.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

132–324

Having a function like this is often a side-effect of improper data-structures. If you need to cache all calls that have been looked at, add a SmallPtrSet<CallInst*, 8> to do so instead of iterating over all vectors that are keys in a map.

132–324

This class provides a way to access/iterate over all call sites of a known OpenMP runtime call. Please use that.

132–324

Please use llvm data structures and give variables proper names.

132–324

This function is quadratic in the number of __kmpc_static_init4 calls.

133

Changed should never be set to false once it is true. However, only because you do that this works. You need a local changed or just if(...) somewhere.

134

The formatting of this function makes it really hard to read it. Please clang-format your patch before uploading it.

134

Please do not iterate over the entire function, basically ever. Start with the things you are interested in and go from there. Iterating over the entire function is at some point costly and always wasteful.

138

No commented out code.

145

The example above is generally nice but maybe we should not print values in parallel, just initialize two arrays.

Style: Clang format all code and comments (=the entire file). Also adjust the indention in the example.

147

Nit: two spaces, if you write sentences add the '.'.

[jdoerfert]

This doesn't seem to use dominance at all. How do you handle

if (a) {
#pragma omp for
for (int i = 0; i < 10; i++)
  ;
} else {
#pragma omp for
for (int i = 0; i < 10; i++)
  ;
}

[lebedev.ri]

Hmm. Random question: are these optimizations friendly to the openmp tooling?

[jdoerfert]

In D75384#1933294, @lebedev.ri wrote:

Hmm. Random question: are these optimizations friendly to the openmp tooling?

Not yet but it's on my list. The plan was to start improving this once we have an "intrusive" transformation, e.g., parallel region merging I have downstream. As of now, I expect us to emit remarks that a tool can use to match the code and events seen at runimte with the input. Similarly, we need to deal with source location changes, update source locations when we merge calls, etc. (there is a TODO in OpenMPOpt already). Feedback on this is very welcome. I also wanted the input of @jmellorcrummey on that.

[abidmalikwaterloo]

In D75384#1932847, @jdoerfert wrote:

This doesn't seem to use dominance at all. How do you handle

if (a) {
#pragma omp for
for (int i = 0; i < 10; i++)
  ;
} else {
#pragma omp for
for (int i = 0; i < 10; i++)
  ;
}

if the value of a is known at the time of compilation, we will only have one "for loop". Therefore, for this specific case, the implemented technique will see only one "for loop" at the IR level. This case should be a problem.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

133

Changed variable is confused with the Changed variable within the run() function. Changed it to local "changed=false"

138

done

145

done

147

not sure what does this means. I should add ".. at the end of each comment line????

[abidmalikwaterloo]

In D75384#1955925, @abidmalikwaterloo wrote:

In D75384#1932847, @jdoerfert wrote:

This doesn't seem to use dominance at all. How do you handle

if (a) {
#pragma omp for
for (int i = 0; i < 10; i++)
  ;
} else {
#pragma omp for
for (int i = 0; i < 10; i++)
  ;
}

if the value of a is known at the time of compilation, we will only have one "for loop". Therefore, for this specific case, the implemented technique will see only one "for loop" at the IR level. This case should be a problem.

This can be done if we collapse the loops within basic blocks. Then this will make the two for loops independent of each other.

[jdoerfert]

Any update on this?

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

147

You should a dot, ".", at the end of a full sentence.

[jdoerfert]

Can you please diff this against the master branch (any commit). You updated it with a single commit against the old version of this patch. You should probably just merge all you have into a single commit for now.

openmp/runtime/src/kmp_sched.cpp

568 ↗

(On Diff #281030)

leftover

[jdoerfert]

Also clang format the patch please.

[abidmalikwaterloo]

The patch now handles conditional blocks containing parallel for loops.

[jdoerfert]

I don't see a difference in the diff.

[abidmalikwaterloo]

Yes, I am trying to figure it out why it is not loading my tests and changes

[abidmalikwaterloo]

I have been trying to update my patch by following the steps on:

https://llvm.org/docs/Contributing.html#how-to-submit-a-patch

However, I always end up loading nothing.

[sstefan1]

In D75384#2317444, @abidmalikwaterloo wrote:

I have been trying to update my patch by following the steps on:

https://llvm.org/docs/Contributing.html#how-to-submit-a-patch

However, I always end up loading nothing.

Looks like you have multiple commits and you are only including the last one. Have you considered putting everything in one commit and then you can update this revision?

[abidmalikwaterloo]

I tried almost everything. Let me try again.

[abidmalikwaterloo]

See the new patch

https://reviews.llvm.org/D90103

I have submitted the new patch As I could not upload the modifications through this thread.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

132–324

See the new patch
https://reviews.llvm.org/D90103

132–324

See the new patch

https://reviews.llvm.org/D90103

132–324

See the new patch

https://reviews.llvm.org/D90103

132–324

See the new patch

https://reviews.llvm.org/D90103

I removed this function in the new implementation.

134

See the new patch

https://reviews.llvm.org/D90103

I removed this in the new patch.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

OpenMPOpt(SmallPtrSetImpl<Function *> &SCC,
             CallGraphUpdater &CGUpdater)
       : M(*(*SCC.begin())->getParent()), SCC(SCC), ModuleSlice(ModuleSlice),
         OMPBuilder(M), CGUpdater(CGUpdater) {
     initializeTypes(M);
     initializeRuntimeFunctions();
     OMPBuilder.initialize();
   }
 
+  /// Loop fusion
+  struct OMPLoopFusion {
+    //
+    std::map<CallInst *, CallInst *> call_init_fini_mapping;
+    std::map<CallInst *, std::vector<CallInst *>> call_map;
+    std::map<Value *, Value *> store_op0_op1;
+    std::map<Value *, Value *> args_map;
+    CallInst *current_call_init_instruction = nullptr;
+  };
+
   /// Generic information that describes a runtime function
   struct RuntimeFunctionInfo {
     /// The kind, as described by the RuntimeFunction enum.
     RuntimeFunction Kind;
 
     /// The name of the function.
     StringRef Name;
 
bool run() {
     bool Changed = false;
 
     LLVM_DEBUG(dbgs() << TAG << "Run on SCC with " << SCC.size()
                       << " functions in a slice with " << ModuleSlice.size()
                       << " functions\n");
 
     Changed |= deduplicateRuntimeCalls();
     Changed |= deleteParallelRegions();
+    Changed |= runTheOMPLoopFusion();
 
     return Changed;
   }
 
 private:
+  /// Try to fuse OpenMP for loop with static scheduling
+  /// check if all parameters are same and the loops are adjacent
+  /// the two for loops can be used
+
+  bool runTheOMPLoopFusion() {
+    bool Changed = false;
+
+    for (Function *F : SCC) {
+      OMPLoopFusion OLF;
+      runOverTheBlock(F, &OLF);
+      checkTheCompatibility(&OLF);
+      Changed = cleanInstructions(&OLF);
+      replace_UseValues(F, &OLF);
+      // printFunction(F);
+    }
+    return Changed;
+  }
+
+  ///
+  //
+  bool find(CallInst *I, std::map<CallInst *, std::vector<CallInst *>> m) {
+    if (m.size() == 0)
+      return false;
+    for (auto itr = m.begin(); itr != m.end(); ++itr) {
+      if ((itr->second).size() == 0)
+        continue;
+      else {
+        for (auto itr1 = (itr->second).begin(); itr1 != (itr->second).end();
+             ++itr1) {
+          if (I == *itr1)
+            return true;
+        }
+      }
+    }
+    return false;
+  }
+
+  /// The following functions check the compatibility of the
+  //  __kmpc_for_static_init_4 call instructions for the fusion
+
+  bool checkTheCompatibility(OMPLoopFusion *OLF) {
+    bool compatible = true;
+    for (auto itr = OLF->call_init_fini_mapping.begin();
+         itr != OLF->call_init_fini_mapping.end(); ++itr) {
+      std::vector<CallInst *> v;
+      if (find(itr->first, OLF->call_map))
+        continue;
+      for (auto itr1 = itr; itr1 != OLF->call_init_fini_mapping.end(); ++itr1) {
+        if (itr == itr1)
+          continue;
+        else {
+          std::vector<Value *> v1, v2;
+          for (Value *arg : (itr->first)->args()) {
+            v1.push_back(arg);
+          }
+          for (Value *arg2 : (itr1->first)->args()) {
+            v2.push_back(arg2);
+          }
+          for (auto i = v1.begin(), j = v2.begin();
+               i != v1.end() && j != v2.end(); ++i, ++j) {
+            if (isa<Constant>(*i) && isa<Constant>(*j)) {
+              if (*i != *j) {
+                compatible = false;
+                break;
+              }
+            } else { // we have a pointer argument
+              if (OLF->store_op0_op1.find(*j)->second !=
+                  OLF->store_op0_op1.find(*i)->second) {
+                compatible = false;
+                break;
+              }
+            }
+          }
+          if (compatible) {
+            errs() << "Success"
+                   << "\n";
+            v.push_back(itr1->first);
+          } else
+            break;
+        }
+      }
+
+      OLF->call_map.insert({itr->first, v});
+      if (!compatible) {
+        compatible = true;
+      }
+    }
+    return false;
+  }
+
+  /// The function goes through each BB and check the call instructions
+  /// __kmpc_for_static_init_4 and __kmpc_for_static_fini
+  /// store the operands of the store instructios
+  void runOverTheBlock(Function *F, OMPLoopFusion *OLF) {
+    for (Function::iterator FI = F->begin(); FI != F->end(); ++FI) {
+      for (BasicBlock::iterator BBI = FI->begin(); BBI != FI->end(); ++BBI) {
+        if (CallInst *c = dyn_cast<CallInst>(BBI)) {
+          if (c->getCalledFunction()->getName() == "__kmpc_for_static_init_4") {
+            OLF->current_call_init_instruction = c;
+          } else if (c->getCalledFunction()->getName() ==
+                     "__kmpc_for_static_fini") {
+            OLF->call_init_fini_mapping.insert(
+                {OLF->current_call_init_instruction, c});
+          }
+        } else if (StoreInst *store = dyn_cast<StoreInst>(BBI)) {
+          OLF->store_op0_op1.insert(
+              {store->getOperand(1), store->getOperand(0)});
+        }
+      }
+    }
+  }
+
+  bool cleanInstructions(OMPLoopFusion *OLF) {
+    bool changed = false;
+    errs() << "[starting cleaning]"
+           << "\n";
+    for (auto itr = OLF->call_map.begin(); itr != OLF->call_map.end(); itr++) {
+      Instruction *I = OLF->call_init_fini_mapping.find(itr->first)->second;
+      int count = (itr->second).size();
+      if (count == 0)
+        continue;
+      else
+        I->eraseFromParent();
+      changed = true;
+      for (auto itr1 = (itr->second).begin(); itr1 != (itr->second).end();
+           itr1++) {
+        Instruction *I1 = *itr1;
+        I1->eraseFromParent();
+        for (auto itr2 = OLF->call_init_fini_mapping.begin();
+             itr2 != OLF->call_init_fini_mapping.end(); itr2++) {
+          if (*itr1 == itr2->first) {
+            Instruction *I2 = itr2->second;
+            if (count == 1 || count == 0)
+              break;
+            else {
+              I2->eraseFromParent();
+              count--;
+            }
+          }
+        }
+      }
+    }
+    errs() << "[Ending Cleaning]"
+           << "\n";
+    return changed;
+  }
+
+  void replace_UseValues(Function *F, OMPLoopFusion *OLF) {
+    std::vector<Instruction *> remove;
+    for (auto itr = OLF->call_map.begin(); itr != OLF->call_map.end(); itr++) {
+      std::vector<Value *> vm;
+      for (Value *arg : (itr->first)->args()) {
+        vm.push_back(arg);
+      }
+      for (auto itr1 = (itr->second).begin(); itr1 != (itr->second).end();
+           itr1++) {
+        std::vector<Value *> vs;
+        for (Value *arg : (*itr1)->args()) {
+          vs.push_back(arg);
+        }
+        for (auto vmitr = vm.begin(), vsitr = vs.begin();
+             vmitr != vm.end() && vsitr != vs.end(); vmitr++, vsitr++) {
+          if (isa<Constant>(*vmitr))
+            continue;
+          for (auto &BB : *F) {
+            for (auto &II : BB) {
+              Instruction *It = &II;
+              if (isa<CallInst>(It))
+                continue;
+              for (unsigned int k = 0; k < It->getNumOperands(); k++) {
+                if (It->getOperand(k) == *vsitr) {
+                  It->setOperand(k, *vmitr);
+                  if (isa<StoreInst>(It) && k > 0) {
+                    remove.push_back(It);
+                  }
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+    for (auto r = remove.begin(); r != remove.end(); r++)
+      (*r)->eraseFromParent();
+  }
+
+  void printFunction(Function *F) {
+    errs() << "\nThis is the new IR for the fused stuff\n\n";
+    F->print(errs(), nullptr);
+  }
+
   /// Try to delete parallel regions if possible
   bool deleteParallelRegions() {
     const unsigned CallbackCalleeOperand = 2;
 
     RuntimeFunctionInfo &RFI = RFIs[OMPRTL___kmpc_fork_call];
     if (!RFI.Declaration)
       return false;
 
     bool Changed = false;