CbC/CbC_llvm: lib/Transforms/Scalar/StructurizeCFG.cpp annotate

annotate lib/Transforms/Scalar/StructurizeCFG.cpp @ 121:803732b1fca8

LLVM 5.0

author	kono
date	Fri, 27 Oct 2017 17:07:41 +0900
parents	1172e4bd9c6f
children	3a76565eade5

rev	line source
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	1 //===- StructurizeCFG.cpp -------------------------------------------------===//
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	2 //
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	3 // The LLVM Compiler Infrastructure
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	4 //
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	5 // This file is distributed under the University of Illinois Open Source
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	6 // License. See LICENSE.TXT for details.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	7 //
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	8 //===----------------------------------------------------------------------===//
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	9
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	10 #include "llvm/ADT/DenseMap.h"
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	11 #include "llvm/ADT/MapVector.h"
95 afa8332a0e37 LLVM 3.8 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 83 diff changeset	12 #include "llvm/ADT/PostOrderIterator.h"
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	13 #include "llvm/ADT/STLExtras.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	14 #include "llvm/ADT/SmallPtrSet.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	15 #include "llvm/ADT/SmallVector.h"
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	16 #include "llvm/Analysis/DivergenceAnalysis.h"
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	17 #include "llvm/Analysis/LoopInfo.h"
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	18 #include "llvm/Analysis/RegionInfo.h"
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	19 #include "llvm/Analysis/RegionIterator.h"
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	20 #include "llvm/Analysis/RegionPass.h"
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	21 #include "llvm/IR/Argument.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	22 #include "llvm/IR/BasicBlock.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	23 #include "llvm/IR/CFG.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	24 #include "llvm/IR/Constant.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	25 #include "llvm/IR/Constants.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	26 #include "llvm/IR/Dominators.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	27 #include "llvm/IR/Function.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	28 #include "llvm/IR/InstrTypes.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	29 #include "llvm/IR/Instruction.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	30 #include "llvm/IR/Instructions.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	31 #include "llvm/IR/Metadata.h"
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	32 #include "llvm/IR/PatternMatch.h"
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	33 #include "llvm/IR/Type.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	34 #include "llvm/IR/Use.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	35 #include "llvm/IR/User.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	36 #include "llvm/IR/Value.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	37 #include "llvm/Pass.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	38 #include "llvm/Support/Casting.h"
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	39 #include "llvm/Support/Debug.h"
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	40 #include "llvm/Support/ErrorHandling.h"
95 afa8332a0e37 LLVM 3.8 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 83 diff changeset	41 #include "llvm/Support/raw_ostream.h"
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	42 #include "llvm/Transforms/Scalar.h"
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	43 #include "llvm/Transforms/Utils/SSAUpdater.h"
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	44 #include <algorithm>
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	45 #include <cassert>
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	46 #include <utility>
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	47
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	48 using namespace llvm;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	49 using namespace llvm::PatternMatch;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	50
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	51 #define DEBUG_TYPE "structurizecfg"
54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	52
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	53 // The name for newly created blocks.
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	54 static const char *const FlowBlockName = "Flow";
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	55
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	56 namespace {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	57
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	58 // Definition of the complex types used in this pass.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	59
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	60 using BBValuePair = std::pair<BasicBlock , Value >;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	61
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	62 using RNVector = SmallVector<RegionNode *, 8>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	63 using BBVector = SmallVector<BasicBlock *, 8>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	64 using BranchVector = SmallVector<BranchInst *, 8>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	65 using BBValueVector = SmallVector<BBValuePair, 2>;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	66
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	67 using BBSet = SmallPtrSet<BasicBlock *, 8>;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	68
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	69 using PhiMap = MapVector<PHINode *, BBValueVector>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	70 using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	71
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	72 using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	73 using BBPredicates = DenseMap<BasicBlock , Value >;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	74 using PredMap = DenseMap<BasicBlock *, BBPredicates>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	75 using BB2BBMap = DenseMap<BasicBlock , BasicBlock >;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	76
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	77 /// Finds the nearest common dominator of a set of BasicBlocks.
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	78 ///
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	79 /// For every BB you add to the set, you can specify whether we "remember" the
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	80 /// block. When you get the common dominator, you can also ask whether it's one
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	81 /// of the blocks we remembered.
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	82 class NearestCommonDominator {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	83 DominatorTree *DT;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	84 BasicBlock *Result = nullptr;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	85 bool ResultIsRemembered = false;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	86
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	87 /// Add BB to the resulting dominator.
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	88 void addBlock(BasicBlock *BB, bool Remember) {
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	89 if (!Result) {
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	90 Result = BB;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	91 ResultIsRemembered = Remember;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	92 return;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	93 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	94
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	95 BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	96 if (NewResult != Result)
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	97 ResultIsRemembered = false;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	98 if (NewResult == BB)
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	99 ResultIsRemembered \|= Remember;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	100 Result = NewResult;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	101 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	102
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	103 public:
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	104 explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	105
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	106 void addBlock(BasicBlock *BB) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	107 addBlock(BB, /* Remember = */ false);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	108 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	109
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	110 void addAndRememberBlock(BasicBlock *BB) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	111 addBlock(BB, /* Remember = */ true);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	112 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	113
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	114 /// Get the nearest common dominator of all the BBs added via addBlock() and
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	115 /// addAndRememberBlock().
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	116 BasicBlock *result() { return Result; }
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	117
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	118 /// Is the BB returned by getResult() one of the blocks we added to the set
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	119 /// with addAndRememberBlock()?
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	120 bool resultIsRememberedBlock() { return ResultIsRemembered; }
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	121 };
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	122
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	123 /// @brief Transforms the control flow graph on one single entry/exit region
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	124 /// at a time.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	125 ///
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	126 /// After the transform all "If"/"Then"/"Else" style control flow looks like
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	127 /// this:
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	128 ///
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	129 /// \verbatim
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	130 /// 1
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	131 /// \|\|
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	132 /// \| \|
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	133 /// 2 \|
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	134 /// \| /
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	135 /// \|/
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	136 /// 3
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	137 /// \|\| Where:
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	138 /// \| \| 1 = "If" block, calculates the condition
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	139 /// 4 \| 2 = "Then" subregion, runs if the condition is true
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	140 /// \| / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	141 /// \|/ 4 = "Else" optional subregion, runs if the condition is false
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	142 /// 5 5 = "End" block, also rejoins the control flow
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	143 /// \endverbatim
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	144 ///
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	145 /// Control flow is expressed as a branch where the true exit goes into the
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	146 /// "Then"/"Else" region, while the false exit skips the region
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	147 /// The condition for the optional "Else" region is expressed as a PHI node.
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	148 /// The incoming values of the PHI node are true for the "If" edge and false
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	149 /// for the "Then" edge.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	150 ///
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	151 /// Additionally to that even complicated loops look like this:
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	152 ///
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	153 /// \verbatim
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	154 /// 1
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	155 /// \|\|
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	156 /// \| \|
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	157 /// 2 ^ Where:
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	158 /// \| / 1 = "Entry" block
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	159 /// \|/ 2 = "Loop" optional subregion, with all exits at "Flow" block
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	160 /// 3 3 = "Flow" block, with back edge to entry block
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	161 /// \|
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	162 /// \endverbatim
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	163 ///
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	164 /// The back edge of the "Flow" block is always on the false side of the branch
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	165 /// while the true side continues the general flow. So the loop condition
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	166 /// consist of a network of PHI nodes where the true incoming values expresses
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	167 /// breaks and the false values expresses continue states.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	168 class StructurizeCFG : public RegionPass {
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	169 bool SkipUniformRegions;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	170
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	171 Type *Boolean;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	172 ConstantInt *BoolTrue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	173 ConstantInt *BoolFalse;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	174 UndefValue *BoolUndef;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	175
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	176 Function *Func;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	177 Region *ParentRegion;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	178
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	179 DominatorTree *DT;
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	180 LoopInfo *LI;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	181
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	182 SmallVector<RegionNode *, 8> Order;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	183 BBSet Visited;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	184
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	185 BBPhiMap DeletedPhis;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	186 BB2BBVecMap AddedPhis;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	187
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	188 PredMap Predicates;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	189 BranchVector Conditions;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	190
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	191 BB2BBMap Loops;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	192 PredMap LoopPreds;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	193 BranchVector LoopConds;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	194
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	195 RegionNode *PrevNode;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	196
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	197 void orderNodes();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	198
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	199 void analyzeLoops(RegionNode *N);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	200
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	201 Value invert(Value Condition);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	202
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	203 Value buildCondition(BranchInst Term, unsigned Idx, bool Invert);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	204
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	205 void gatherPredicates(RegionNode *N);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	206
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	207 void collectInfos();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	208
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	209 void insertConditions(bool Loops);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	210
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	211 void delPhiValues(BasicBlock From, BasicBlock To);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	212
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	213 void addPhiValues(BasicBlock From, BasicBlock To);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	214
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	215 void setPhiValues();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	216
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	217 void killTerminator(BasicBlock *BB);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	218
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	219 void changeExit(RegionNode Node, BasicBlock NewExit,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	220 bool IncludeDominator);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	221
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	222 BasicBlock getNextFlow(BasicBlock Dominator);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	223
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	224 BasicBlock *needPrefix(bool NeedEmpty);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	225
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	226 BasicBlock needPostfix(BasicBlock Flow, bool ExitUseAllowed);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	227
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	228 void setPrevNode(BasicBlock *BB);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	229
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	230 bool dominatesPredicates(BasicBlock BB, RegionNode Node);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	231
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	232 bool isPredictableTrue(RegionNode *Node);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	233
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	234 void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	235
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	236 void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	237
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	238 void createFlow();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	239
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	240 void rebuildSSA();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	241
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	242 public:
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	243 static char ID;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	244
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	245 explicit StructurizeCFG(bool SkipUniformRegions = false)
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	246 : RegionPass(ID), SkipUniformRegions(SkipUniformRegions) {
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	247 initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	248 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	249
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	250 bool doInitialization(Region *R, RGPassManager &RGM) override;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	251
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	252 bool runOnRegion(Region *R, RGPassManager &RGM) override;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	253
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	254 StringRef getPassName() const override { return "Structurize control flow"; }
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	255
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	256 void getAnalysisUsage(AnalysisUsage &AU) const override {
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	257 if (SkipUniformRegions)
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	258 AU.addRequired<DivergenceAnalysis>();
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	259 AU.addRequiredID(LowerSwitchID);
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	260 AU.addRequired<DominatorTreeWrapperPass>();
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	261 AU.addRequired<LoopInfoWrapperPass>();
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	262
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	263 AU.addPreserved<DominatorTreeWrapperPass>();
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	264 RegionPass::getAnalysisUsage(AU);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	265 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	266 };
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	267
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	268 } // end anonymous namespace
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	269
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	270 char StructurizeCFG::ID = 0;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	271
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	272 INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	273 false, false)
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	274 INITIALIZE_PASS_DEPENDENCY(DivergenceAnalysis)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	275 INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	276 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	277 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	278 INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	279 false, false)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	280
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	281 /// \brief Initialize the types and constants used in the pass
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	282 bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	283 LLVMContext &Context = R->getEntry()->getContext();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	284
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	285 Boolean = Type::getInt1Ty(Context);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	286 BoolTrue = ConstantInt::getTrue(Context);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	287 BoolFalse = ConstantInt::getFalse(Context);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	288 BoolUndef = UndefValue::get(Boolean);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	289
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	290 return false;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	291 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	292
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	293 /// \brief Build up the general order of nodes
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	294 void StructurizeCFG::orderNodes() {
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	295 ReversePostOrderTraversal<Region*> RPOT(ParentRegion);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	296 SmallDenseMap<Loop*, unsigned, 8> LoopBlocks;
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	297
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	298 // The reverse post-order traversal of the list gives us an ordering close
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	299 // to what we want. The only problem with it is that sometimes backedges
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	300 // for outer loops will be visited before backedges for inner loops.
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	301 for (RegionNode *RN : RPOT) {
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	302 BasicBlock *BB = RN->getEntry();
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	303 Loop *Loop = LI->getLoopFor(BB);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	304 ++LoopBlocks[Loop];
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	305 }
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	306
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	307 unsigned CurrentLoopDepth = 0;
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	308 Loop *CurrentLoop = nullptr;
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	309 for (auto I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	310 BasicBlock BB = (I)->getEntry();
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	311 unsigned LoopDepth = LI->getLoopDepth(BB);
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	312
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	313 if (is_contained(Order, *I))
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	314 continue;
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	315
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	316 if (LoopDepth < CurrentLoopDepth) {
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	317 // Make sure we have visited all blocks in this loop before moving back to
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	318 // the outer loop.
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	319
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	320 auto LoopI = I;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	321 while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) {
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	322 LoopI++;
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	323 BasicBlock LoopBB = (LoopI)->getEntry();
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	324 if (LI->getLoopFor(LoopBB) == CurrentLoop) {
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	325 --BlockCount;
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	326 Order.push_back(*LoopI);
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	327 }
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	328 }
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	329 }
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	330
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	331 CurrentLoop = LI->getLoopFor(BB);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	332 if (CurrentLoop)
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	333 LoopBlocks[CurrentLoop]--;
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	334
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	335 CurrentLoopDepth = LoopDepth;
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	336 Order.push_back(*I);
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	337 }
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	338
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	339 // This pass originally used a post-order traversal and then operated on
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	340 // the list in reverse. Now that we are using a reverse post-order traversal
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	341 // rather than re-working the whole pass to operate on the list in order,
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	342 // we just reverse the list and continue to operate on it in reverse.
60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	343 std::reverse(Order.begin(), Order.end());
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	344 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	345
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	346 /// \brief Determine the end of the loops
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	347 void StructurizeCFG::analyzeLoops(RegionNode *N) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	348 if (N->isSubRegion()) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	349 // Test for exit as back edge
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	350 BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	351 if (Visited.count(Exit))
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	352 Loops[Exit] = N->getEntry();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	353
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	354 } else {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	355 // Test for successors as back edge
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	356 BasicBlock *BB = N->getNodeAs<BasicBlock>();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	357 BranchInst *Term = cast<BranchInst>(BB->getTerminator());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	358
95 afa8332a0e37 LLVM 3.8 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 83 diff changeset	359 for (BasicBlock *Succ : Term->successors())
afa8332a0e37 LLVM 3.8 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 83 diff changeset	360 if (Visited.count(Succ))
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	361 Loops[Succ] = BB;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	362 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	363 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	364
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	365 /// \brief Invert the given condition
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	366 Value StructurizeCFG::invert(Value Condition) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	367 // First: Check if it's a constant
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	368 if (Constant *C = dyn_cast<Constant>(Condition))
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	369 return ConstantExpr::getNot(C);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	370
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	371 // Second: If the condition is already inverted, return the original value
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	372 if (match(Condition, m_Not(m_Value(Condition))))
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	373 return Condition;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	374
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	375 if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	376 // Third: Check all the users for an invert
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	377 BasicBlock *Parent = Inst->getParent();
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	378 for (User *U : Condition->users())
54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	379 if (Instruction *I = dyn_cast<Instruction>(U))
54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	380 if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	381 return I;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	382
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	383 // Last option: Create a new instruction
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	384 return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	385 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	386
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	387 if (Argument *Arg = dyn_cast<Argument>(Condition)) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	388 BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	389 return BinaryOperator::CreateNot(Condition,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	390 Arg->getName() + ".inv",
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	391 EntryBlock.getTerminator());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	392 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	393
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	394 llvm_unreachable("Unhandled condition to invert");
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	395 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	396
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	397 /// \brief Build the condition for one edge
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	398 Value StructurizeCFG::buildCondition(BranchInst Term, unsigned Idx,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	399 bool Invert) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	400 Value *Cond = Invert ? BoolFalse : BoolTrue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	401 if (Term->isConditional()) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	402 Cond = Term->getCondition();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	403
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	404 if (Idx != (unsigned)Invert)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	405 Cond = invert(Cond);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	406 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	407 return Cond;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	408 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	409
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	410 /// \brief Analyze the predecessors of each block and build up predicates
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	411 void StructurizeCFG::gatherPredicates(RegionNode *N) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	412 RegionInfo *RI = ParentRegion->getRegionInfo();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	413 BasicBlock *BB = N->getEntry();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	414 BBPredicates &Pred = Predicates[BB];
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	415 BBPredicates &LPred = LoopPreds[BB];
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	416
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	417 for (BasicBlock *P : predecessors(BB)) {
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	418 // Ignore it if it's a branch from outside into our region entry
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	419 if (!ParentRegion->contains(P))
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	420 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	421
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	422 Region *R = RI->getRegionFor(P);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	423 if (R == ParentRegion) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	424 // It's a top level block in our region
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	425 BranchInst *Term = cast<BranchInst>(P->getTerminator());
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	426 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	427 BasicBlock *Succ = Term->getSuccessor(i);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	428 if (Succ != BB)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	429 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	430
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	431 if (Visited.count(P)) {
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	432 // Normal forward edge
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	433 if (Term->isConditional()) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	434 // Try to treat it like an ELSE block
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	435 BasicBlock *Other = Term->getSuccessor(!i);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	436 if (Visited.count(Other) && !Loops.count(Other) &&
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	437 !Pred.count(Other) && !Pred.count(P)) {
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	438
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	439 Pred[Other] = BoolFalse;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	440 Pred[P] = BoolTrue;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	441 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	442 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	443 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	444 Pred[P] = buildCondition(Term, i, false);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	445 } else {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	446 // Back edge
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	447 LPred[P] = buildCondition(Term, i, true);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	448 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	449 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	450 } else {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	451 // It's an exit from a sub region
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	452 while (R->getParent() != ParentRegion)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	453 R = R->getParent();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	454
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	455 // Edge from inside a subregion to its entry, ignore it
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	456 if (R == N)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	457 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	458
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	459 BasicBlock *Entry = R->getEntry();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	460 if (Visited.count(Entry))
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	461 Pred[Entry] = BoolTrue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	462 else
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	463 LPred[Entry] = BoolFalse;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	464 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	465 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	466 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	467
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	468 /// \brief Collect various loop and predicate infos
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	469 void StructurizeCFG::collectInfos() {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	470 // Reset predicate
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	471 Predicates.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	472
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	473 // and loop infos
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	474 Loops.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	475 LoopPreds.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	476
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	477 // Reset the visited nodes
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	478 Visited.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	479
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	480 for (RegionNode *RN : reverse(Order)) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	481 DEBUG(dbgs() << "Visiting: "
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	482 << (RN->isSubRegion() ? "SubRegion with entry: " : "")
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	483 << RN->getEntry()->getName() << " Loop Depth: "
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	484 << LI->getLoopDepth(RN->getEntry()) << "\n");
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	485
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	486 // Analyze all the conditions leading to a node
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	487 gatherPredicates(RN);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	488
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	489 // Remember that we've seen this node
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	490 Visited.insert(RN->getEntry());
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	491
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	492 // Find the last back edges
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	493 analyzeLoops(RN);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	494 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	495 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	496
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	497 /// \brief Insert the missing branch conditions
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	498 void StructurizeCFG::insertConditions(bool Loops) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	499 BranchVector &Conds = Loops ? LoopConds : Conditions;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	500 Value *Default = Loops ? BoolTrue : BoolFalse;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	501 SSAUpdater PhiInserter;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	502
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	503 for (BranchInst *Term : Conds) {
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	504 assert(Term->isConditional());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	505
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	506 BasicBlock *Parent = Term->getParent();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	507 BasicBlock *SuccTrue = Term->getSuccessor(0);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	508 BasicBlock *SuccFalse = Term->getSuccessor(1);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	509
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	510 PhiInserter.Initialize(Boolean, "");
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	511 PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	512 PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	513
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	514 BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	515
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	516 NearestCommonDominator Dominator(DT);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	517 Dominator.addBlock(Parent);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	518
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	519 Value *ParentValue = nullptr;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	520 for (std::pair<BasicBlock , Value > BBAndPred : Preds) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	521 BasicBlock *BB = BBAndPred.first;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	522 Value *Pred = BBAndPred.second;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	523
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	524 if (BB == Parent) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	525 ParentValue = Pred;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	526 break;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	527 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	528 PhiInserter.AddAvailableValue(BB, Pred);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	529 Dominator.addAndRememberBlock(BB);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	530 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	531
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	532 if (ParentValue) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	533 Term->setCondition(ParentValue);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	534 } else {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	535 if (!Dominator.resultIsRememberedBlock())
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	536 PhiInserter.AddAvailableValue(Dominator.result(), Default);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	537
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	538 Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	539 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	540 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	541 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	542
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	543 /// \brief Remove all PHI values coming from "From" into "To" and remember
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	544 /// them in DeletedPhis
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	545 void StructurizeCFG::delPhiValues(BasicBlock From, BasicBlock To) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	546 PhiMap &Map = DeletedPhis[To];
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	547 for (Instruction &I : *To) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	548 if (!isa<PHINode>(I))
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	549 break;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	550 PHINode &Phi = cast<PHINode>(I);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	551 while (Phi.getBasicBlockIndex(From) != -1) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	552 Value *Deleted = Phi.removeIncomingValue(From, false);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	553 Map[&Phi].push_back(std::make_pair(From, Deleted));
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	554 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	555 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	556 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	557
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	558 /// \brief Add a dummy PHI value as soon as we knew the new predecessor
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	559 void StructurizeCFG::addPhiValues(BasicBlock From, BasicBlock To) {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	560 for (Instruction &I : *To) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	561 if (!isa<PHINode>(I))
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	562 break;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	563 PHINode &Phi = cast<PHINode>(I);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	564 Value *Undef = UndefValue::get(Phi.getType());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	565 Phi.addIncoming(Undef, From);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	566 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	567 AddedPhis[To].push_back(From);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	568 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	569
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	570 /// \brief Add the real PHI value as soon as everything is set up
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	571 void StructurizeCFG::setPhiValues() {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	572 SSAUpdater Updater;
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	573 for (const auto &AddedPhi : AddedPhis) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	574 BasicBlock *To = AddedPhi.first;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	575 const BBVector &From = AddedPhi.second;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	576
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	577 if (!DeletedPhis.count(To))
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	578 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	579
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	580 PhiMap &Map = DeletedPhis[To];
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	581 for (const auto &PI : Map) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	582 PHINode *Phi = PI.first;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	583 Value *Undef = UndefValue::get(Phi->getType());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	584 Updater.Initialize(Phi->getType(), "");
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	585 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	586 Updater.AddAvailableValue(To, Undef);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	587
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	588 NearestCommonDominator Dominator(DT);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	589 Dominator.addBlock(To);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	590 for (const auto &VI : PI.second) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	591 Updater.AddAvailableValue(VI.first, VI.second);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	592 Dominator.addAndRememberBlock(VI.first);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	593 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	594
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	595 if (!Dominator.resultIsRememberedBlock())
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	596 Updater.AddAvailableValue(Dominator.result(), Undef);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	597
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	598 for (BasicBlock *FI : From) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	599 int Idx = Phi->getBasicBlockIndex(FI);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	600 assert(Idx != -1);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	601 Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(FI));
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	602 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	603 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	604
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	605 DeletedPhis.erase(To);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	606 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	607 assert(DeletedPhis.empty());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	608 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	609
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	610 /// \brief Remove phi values from all successors and then remove the terminator.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	611 void StructurizeCFG::killTerminator(BasicBlock *BB) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	612 TerminatorInst *Term = BB->getTerminator();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	613 if (!Term)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	614 return;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	615
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	616 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	617 SI != SE; ++SI)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	618 delPhiValues(BB, *SI);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	619
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	620 Term->eraseFromParent();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	621 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	622
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	623 /// \brief Let node exit(s) point to NewExit
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	624 void StructurizeCFG::changeExit(RegionNode Node, BasicBlock NewExit,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	625 bool IncludeDominator) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	626 if (Node->isSubRegion()) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	627 Region *SubRegion = Node->getNodeAs<Region>();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	628 BasicBlock *OldExit = SubRegion->getExit();
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	629 BasicBlock *Dominator = nullptr;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	630
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	631 // Find all the edges from the sub region to the exit
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	632 for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	633 // Incrememt BBI before mucking with BB's terminator.
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	634 BasicBlock BB = BBI++;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	635
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	636 if (!SubRegion->contains(BB))
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	637 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	638
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	639 // Modify the edges to point to the new exit
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	640 delPhiValues(BB, OldExit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	641 BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	642 addPhiValues(BB, NewExit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	643
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	644 // Find the new dominator (if requested)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	645 if (IncludeDominator) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	646 if (!Dominator)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	647 Dominator = BB;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	648 else
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	649 Dominator = DT->findNearestCommonDominator(Dominator, BB);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	650 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	651 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	652
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	653 // Change the dominator (if requested)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	654 if (Dominator)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	655 DT->changeImmediateDominator(NewExit, Dominator);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	656
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	657 // Update the region info
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	658 SubRegion->replaceExit(NewExit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	659 } else {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	660 BasicBlock *BB = Node->getNodeAs<BasicBlock>();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	661 killTerminator(BB);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	662 BranchInst::Create(NewExit, BB);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	663 addPhiValues(BB, NewExit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	664 if (IncludeDominator)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	665 DT->changeImmediateDominator(NewExit, BB);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	666 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	667 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	668
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	669 /// \brief Create a new flow node and update dominator tree and region info
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	670 BasicBlock StructurizeCFG::getNextFlow(BasicBlock Dominator) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	671 LLVMContext &Context = Func->getContext();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	672 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	673 Order.back()->getEntry();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	674 BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	675 Func, Insert);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	676 DT->addNewBlock(Flow, Dominator);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	677 ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	678 return Flow;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	679 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	680
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	681 /// \brief Create a new or reuse the previous node as flow node
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	682 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	683 BasicBlock *Entry = PrevNode->getEntry();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	684
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	685 if (!PrevNode->isSubRegion()) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	686 killTerminator(Entry);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	687 if (!NeedEmpty \|\| Entry->getFirstInsertionPt() == Entry->end())
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	688 return Entry;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	689 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	690
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	691 // create a new flow node
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	692 BasicBlock *Flow = getNextFlow(Entry);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	693
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	694 // and wire it up
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	695 changeExit(PrevNode, Flow, true);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	696 PrevNode = ParentRegion->getBBNode(Flow);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	697 return Flow;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	698 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	699
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	700 /// \brief Returns the region exit if possible, otherwise just a new flow node
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	701 BasicBlock StructurizeCFG::needPostfix(BasicBlock Flow,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	702 bool ExitUseAllowed) {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	703 if (!Order.empty() \|\| !ExitUseAllowed)
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	704 return getNextFlow(Flow);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	705
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	706 BasicBlock *Exit = ParentRegion->getExit();
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	707 DT->changeImmediateDominator(Exit, Flow);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	708 addPhiValues(Flow, Exit);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	709 return Exit;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	710 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	711
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	712 /// \brief Set the previous node
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	713 void StructurizeCFG::setPrevNode(BasicBlock *BB) {
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	714 PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	715 : nullptr;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	716 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	717
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	718 /// \brief Does BB dominate all the predicates of Node?
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	719 bool StructurizeCFG::dominatesPredicates(BasicBlock BB, RegionNode Node) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	720 BBPredicates &Preds = Predicates[Node->getEntry()];
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	721 return llvm::all_of(Preds, [&](std::pair<BasicBlock , Value > Pred) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	722 return DT->dominates(BB, Pred.first);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	723 });
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	724 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	725
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	726 /// \brief Can we predict that this node will always be called?
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	727 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	728 BBPredicates &Preds = Predicates[Node->getEntry()];
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	729 bool Dominated = false;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	730
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	731 // Regionentry is always true
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	732 if (!PrevNode)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	733 return true;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	734
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	735 for (std::pair<BasicBlock, Value> Pred : Preds) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	736 BasicBlock *BB = Pred.first;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	737 Value *V = Pred.second;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	738
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	739 if (V != BoolTrue)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	740 return false;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	741
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	742 if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	743 Dominated = true;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	744 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	745
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	746 // TODO: The dominator check is too strict
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	747 return Dominated;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	748 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	749
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	750 /// Take one node from the order vector and wire it up
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	751 void StructurizeCFG::wireFlow(bool ExitUseAllowed,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	752 BasicBlock *LoopEnd) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	753 RegionNode *Node = Order.pop_back_val();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	754 Visited.insert(Node->getEntry());
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	755
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	756 if (isPredictableTrue(Node)) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	757 // Just a linear flow
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	758 if (PrevNode) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	759 changeExit(PrevNode, Node->getEntry(), true);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	760 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	761 PrevNode = Node;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	762 } else {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	763 // Insert extra prefix node (or reuse last one)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	764 BasicBlock *Flow = needPrefix(false);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	765
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	766 // Insert extra postfix node (or use exit instead)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	767 BasicBlock *Entry = Node->getEntry();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	768 BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	769
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	770 // let it point to entry and next block
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	771 Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	772 addPhiValues(Flow, Entry);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	773 DT->changeImmediateDominator(Entry, Flow);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	774
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	775 PrevNode = Node;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	776 while (!Order.empty() && !Visited.count(LoopEnd) &&
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	777 dominatesPredicates(Entry, Order.back())) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	778 handleLoops(false, LoopEnd);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	779 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	780
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	781 changeExit(PrevNode, Next, false);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	782 setPrevNode(Next);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	783 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	784 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	785
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	786 void StructurizeCFG::handleLoops(bool ExitUseAllowed,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	787 BasicBlock *LoopEnd) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	788 RegionNode *Node = Order.back();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	789 BasicBlock *LoopStart = Node->getEntry();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	790
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	791 if (!Loops.count(LoopStart)) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	792 wireFlow(ExitUseAllowed, LoopEnd);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	793 return;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	794 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	795
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	796 if (!isPredictableTrue(Node))
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	797 LoopStart = needPrefix(true);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	798
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	799 LoopEnd = Loops[Node->getEntry()];
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	800 wireFlow(false, LoopEnd);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	801 while (!Visited.count(LoopEnd)) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	802 handleLoops(false, LoopEnd);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	803 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	804
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	805 // If the start of the loop is the entry block, we can't branch to it so
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	806 // insert a new dummy entry block.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	807 Function *LoopFunc = LoopStart->getParent();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	808 if (LoopStart == &LoopFunc->getEntryBlock()) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	809 LoopStart->setName("entry.orig");
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	810
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	811 BasicBlock *NewEntry =
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	812 BasicBlock::Create(LoopStart->getContext(),
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	813 "entry",
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	814 LoopFunc,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	815 LoopStart);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	816 BranchInst::Create(LoopStart, NewEntry);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	817 DT->setNewRoot(NewEntry);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	818 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	819
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	820 // Create an extra loop end node
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	821 LoopEnd = needPrefix(false);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	822 BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	823 LoopConds.push_back(BranchInst::Create(Next, LoopStart,
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	824 BoolUndef, LoopEnd));
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	825 addPhiValues(LoopEnd, LoopStart);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	826 setPrevNode(Next);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	827 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	828
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	829 /// After this function control flow looks like it should be, but
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	830 /// branches and PHI nodes only have undefined conditions.
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	831 void StructurizeCFG::createFlow() {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	832 BasicBlock *Exit = ParentRegion->getExit();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	833 bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	834
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	835 DeletedPhis.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	836 AddedPhis.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	837 Conditions.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	838 LoopConds.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	839
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	840 PrevNode = nullptr;
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	841 Visited.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	842
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	843 while (!Order.empty()) {
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	844 handleLoops(EntryDominatesExit, nullptr);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	845 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	846
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	847 if (PrevNode)
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	848 changeExit(PrevNode, Exit, EntryDominatesExit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	849 else
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	850 assert(EntryDominatesExit);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	851 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	852
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	853 /// Handle a rare case where the disintegrated nodes instructions
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	854 /// no longer dominate all their uses. Not sure if this is really nessasary
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	855 void StructurizeCFG::rebuildSSA() {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	856 SSAUpdater Updater;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	857 for (BasicBlock *BB : ParentRegion->blocks())
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	858 for (Instruction &I : *BB) {
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	859 bool Initialized = false;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	860 // We may modify the use list as we iterate over it, so be careful to
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	861 // compute the next element in the use list at the top of the loop.
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	862 for (auto UI = I.use_begin(), E = I.use_end(); UI != E;) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	863 Use &U = *UI++;
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	864 Instruction *User = cast<Instruction>(U.getUser());
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	865 if (User->getParent() == BB) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	866 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	867 } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	868 if (UserPN->getIncomingBlock(U) == BB)
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	869 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	870 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	871
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	872 if (DT->dominates(&I, User))
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	873 continue;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	874
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	875 if (!Initialized) {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	876 Value *Undef = UndefValue::get(I.getType());
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	877 Updater.Initialize(I.getType(), "");
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	878 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	879 Updater.AddAvailableValue(BB, &I);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	880 Initialized = true;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	881 }
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	882 Updater.RewriteUseAfterInsertions(U);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	883 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	884 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	885 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	886
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	887 static bool hasOnlyUniformBranches(const Region *R,
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	888 const DivergenceAnalysis &DA) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	889 for (const BasicBlock *BB : R->blocks()) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	890 const BranchInst *Br = dyn_cast<BranchInst>(BB->getTerminator());
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	891 if (!Br \|\| !Br->isConditional())
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	892 continue;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	893
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	894 if (!DA.isUniform(Br->getCondition()))
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	895 return false;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	896 DEBUG(dbgs() << "BB: " << BB->getName() << " has uniform terminator\n");
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	897 }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	898 return true;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	899 }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	900
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	901 /// \brief Run the transformation for each region found
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	902 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	903 if (R->isTopLevelRegion())
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	904 return false;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	905
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	906 if (SkipUniformRegions) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	907 // TODO: We could probably be smarter here with how we handle sub-regions.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	908 auto &DA = getAnalysis<DivergenceAnalysis>();
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	909 if (hasOnlyUniformBranches(R, DA)) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	910 DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R << '\n');
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	911
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	912 // Mark all direct child block terminators as having been treated as
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	913 // uniform. To account for a possible future in which non-uniform
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	914 // sub-regions are treated more cleverly, indirect children are not
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	915 // marked as uniform.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	916 MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	917 for (RegionNode *E : R->elements()) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	918 if (E->isSubRegion())
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	919 continue;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	920
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	921 if (Instruction *Term = E->getEntry()->getTerminator())
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	922 Term->setMetadata("structurizecfg.uniform", MD);
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	923 }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	924
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	925 return false;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	926 }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	927 }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	928
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	929 Func = R->getEntry()->getParent();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	930 ParentRegion = R;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	931
77 54457678186b LLVM 3.6 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: 0 diff changeset	932 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
83 60c9769439b8 LLVM 3.7 Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> parents: 77 diff changeset	933 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	934
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	935 orderNodes();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	936 collectInfos();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	937 createFlow();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	938 insertConditions(false);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	939 insertConditions(true);
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	940 setPhiValues();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	941 rebuildSSA();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	942
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	943 // Cleanup
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	944 Order.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	945 Visited.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	946 DeletedPhis.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	947 AddedPhis.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	948 Predicates.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	949 Conditions.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	950 Loops.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	951 LoopPreds.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	952 LoopConds.clear();
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	953
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	954 return true;
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	955 }
95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	956
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	957 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	958 return new StructurizeCFG(SkipUniformRegions);
0 95c75e76d11b LLVM 3.4 Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	959 }

Mercurial > hg > CbC > CbC_llvm

annotate lib/Transforms/Scalar/StructurizeCFG.cpp @ 121:803732b1fca8