+// XXX-comment: Finds the appropriate Value derived from an atomic load.
+// 'ChainedBB' contains all the blocks chained together with unconditional
+// branches from LI's parent BB to the block with the first store/cond branch.
+// If we don't find any, it means 'LI' is not used at all (which should not
+// happen in practice). We can simply set 'LI' to be acquire just to be safe.
+template <typename Vector>
+Instruction* findMostRecentDependenceUsage(LoadInst* LI, Instruction* LaterInst,
+ Vector* ChainedBB,
+ DominatorTree* DT) {
+ typedef SmallSet<Instruction*, 8> UsageSet;
+ typedef DenseMap<BasicBlock*, std::unique_ptr<UsageSet>> UsageMap;
+ assert(ChainedBB->size() >= 1 && "ChainedBB must have >=1 size");
+ // Mapping from basic block in 'ChainedBB' to the set of dependence usage of
+ // 'LI' in each block.
+ UsageMap usage_map;
+ auto* LoadBB = LI->getParent();
+ usage_map[LoadBB] = make_unique<UsageSet>();
+ usage_map[LoadBB]->insert(LI);
+
+ for (auto* BB : *ChainedBB) {
+ if (usage_map[BB] == nullptr) {
+ usage_map[BB] = make_unique<UsageSet>();
+ }
+ auto& usage_set = usage_map[BB];
+ if (usage_set->size() == 0) {
+ // The value has not been used.
+ return nullptr;
+ }
+ // Calculate the usage in the current BB first.
+ std::list<Value*> bb_usage_list;
+ std::copy(usage_set->begin(), usage_set->end(),
+ std::back_inserter(bb_usage_list));
+ for (auto list_iter = bb_usage_list.begin();
+ list_iter != bb_usage_list.end(); list_iter++) {
+ auto* val = *list_iter;
+ for (auto* U : val->users()) {
+ Instruction* Inst = nullptr;
+ if (!(Inst = dyn_cast<Instruction>(U))) {
+ continue;
+ }
+ assert(Inst && "Usage value must be an instruction");
+ auto iter =
+ std::find(ChainedBB->begin(), ChainedBB->end(), Inst->getParent());
+ if (iter == ChainedBB->end()) {
+ // Only care about usage within ChainedBB.
+ continue;
+ }
+ auto* UsageBB = *iter;
+ if (UsageBB == BB) {
+ // Current BB.
+ if (!usage_set->count(Inst)) {
+ bb_usage_list.push_back(Inst);
+ usage_set->insert(Inst);
+ }
+ } else {
+ // A following BB.
+ if (usage_map[UsageBB] == nullptr) {
+ usage_map[UsageBB] = make_unique<UsageSet>();
+ }
+ usage_map[UsageBB]->insert(Inst);
+ }
+ }
+ }
+ }
+
+ // Pick one usage that is in LaterInst's block and that dominates 'LaterInst'.
+ auto* LaterBB = LaterInst->getParent();
+ auto& usage_set = usage_map[LaterBB];
+ Instruction* usage_inst = nullptr;
+ for (auto* inst : *usage_set) {
+ if (DT->dominates(inst, LaterInst)) {
+ usage_inst = inst;
+ break;
+ }
+ }
+
+ assert(usage_inst && "The usage instruction in the same block but after the "
+ "later instruction");
+ return usage_inst;
+}
+